Constrain relaxation in distributed constraint satisfaction problems

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

14 被引用数 (Scopus)

抄録

The distributed constraint satisfaction problem (DSCP) formulation has recently been identified as a general framework for formalizing various Distributed Artificial Intelligence problems. In this paper, we extend the DCSP formalization by introducing the notion of importance values of constraints. With these values, we define a solution criterion for DCSPs, that are over-constrained (where no solution satisfies all constraints completely). We show that agents can find an optimal solution with this criterion by using the asynchronous incremental relaxation algorithm, in which the agents iteratively apply the asynchronous backtracking algorithm to solve a DCSP, while incrementally relaxing less important constraints. In this algorithm, agents act asynchronously and concurrently, in contrast to traditional sequential backtracking techniques, while guaranteeing thee completeness of the algorithm and the optimality of the optimality. Furthermore, we show that, in this algorithm, agents can avoid redundant computation and achieve a five-fold speed-up in example problems by maintaining the dependencies between constraint violations (nogoods) and constraints.

本文言語英語
ホスト出版物のタイトルProceedings of the International Conference on Tools with Artificial Intelligence
編集者 Anon
出版社Publ by IEEE
ページ56-63
ページ数8
ISBN(印刷版)0818642009
出版ステータス出版済み - 1993
外部発表はい
イベントProceedings of the 5th International Conference on Tools with Artificial Intelligence TAI '93 - Boston, MA, USA
継続期間: 11月 8 199311月 11 1993

出版物シリーズ

名前Proceedings of the International Conference on Tools with Artificial Intelligence
ISSN(印刷版)1063-6730

その他

その他Proceedings of the 5th International Conference on Tools with Artificial Intelligence TAI '93
CityBoston, MA, USA
Period11/8/9311/11/93

!!!All Science Journal Classification (ASJC) codes

  • ソフトウェア

フィンガープリント

「Constrain relaxation in distributed constraint satisfaction problems」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル