Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
スポンサーリンク
概要
- 論文の詳細を見る
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 nn to p(n) (partition function of n), i.e., from 1010 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.
論文 | ランダム
- D-12-72 動画像を用いた一般物体のカテゴリ識別に関する検討(D-12.パターン認識・メディア理解,一般セッション)
- 登録有形文化財(建造物)群馬県庁本庁舎の改修方法と改修工事概要, 八木真爾, 角幸博, 513
- 9237 朝鮮王朝実録からみた楼亭建築 : 韓国楼亭建築の保存と活用に関する研究5(東洋・韓国(1),建築歴史・意匠)
- 9016 近代における民家と日本的造形に関する研究(建築史・建築意匠・建築論)
- 9018 明治初期建築におけるメートル法から尺寸法への変換について : 神子畑鉱山事務舎での11分割法の試み(建築史・建築意匠・建築論)