Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning

• Olive Xavier

  Kyoto University

• Nakashima Hiroshi

  Kyoto University

抄録

In this paper, we discuss variable and value symmetries in distributed constraint reasoning and efficient methods to represent and propagate them in distributed environments. Unlike commonly used centralised methods which detect symmetries according to their global definition, we suggest here to define them at the individual constraint level, then define operations on those symmetries in order to propagate them through the depth-first search tree that is generated in efficient distributed constraint reasoning algorithms. In our algorithm, we represent constraints (or utility functions) by a list of costs: while the usual representation lists one cost for one assignation, we drastically reduce the size of that list by keeping only one cost for one class of equivalence of assignations. In practice, for a constraint with n symmetric variables defined on a domain of n symmetric values, this approach cuts down the size of the list of costs from nⁿ to p(n) (partition function of n), i.e., from 10¹⁰ to 42 when n = 10. We henceforth devised algorithms to process the sparse representations of utility functions and to propagate them along with symmetry information among distributed agents. We implemented this new representation of constraints and tested it with the DPOP algorithm on distributed graph colouring problems, rich in symmetries. Our evaluation shows that in 19% of execution instances we cut down 10 times the volume of communication spent, while no significant overhead appears in non symmetrical executions. These results open serious perspectives on a possible bounding of memory and communication bandwidth consumption in some subclass of distributed constraint reasoning problems.

収録刊行物

• Information and Media Technologies

  Information and Media Technologies 6 (3), 670-679, 2011

  Information and Media Technologies 編集運営会議

詳細情報

• CRID: 1390001205264520960
• NII論文ID: 130000969394
• DOI: 10.11185/imt.6.670
• ISSN: 18810896
• 本文言語コード: en
• データソース種別:
  • JaLC
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可