An Easy -Hard- Easy Cost Profile in Distributed Constraint Satisfaction

• Item type: Journal(1)
• 公開日: 2004-09-15
• タイトル: An Easy -Hard- Easy Cost Profile in Distributed Constraint Satisfaction
• タイトル / 言語: en
• タイトル: An Easy-Hard-Easy Cost Profile in Distributed Constraint Satisfaction
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 分散・協調AI
• 著者所属: Faculty of Maritime Sciences Kobe University
• 著者所属: Graduate School of Information Science and Electrical Engineering Kyushu University
• 著者所属: The Robotics Institute Carnegie Mellon University
• 著者所属(英): en
• 著者所属(英): Faculty of Maritime Sciences, Kobe University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): The Robotics Institute, Carnegie Mellon University
• 著者名: Katsutoshi, Hirayama; Makoto, Yokoo; Katia, Sycara
• 著者名(英): Katsutoshi, Hirayama; Makoto, Yokoo; Katia, Sycara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We first present an algorithm called multi-ABT as a baseline algorithm for solving distributed constraint satisfaction problems where each agent has multiple local variables. Then we show a cost profile of multi-ABT for various numbers of intra-agent constraints (constraints defined over variables of one agent) and inter-agent constraints (constraints defined over variables of multiple agents) in a distributed graph-coloring problem. This cost profile enabled us to make the following observations: (1) the satisfiability thresholds are identified in the narrow region on the x-y plane (where the x-axis is the number of intra-agent constraints and the y-axis is the number of inter-agent constraints) in which the sum of intra- and inter-agent constraints is constant and problem instances in the region (called the crossover belt) are likely to be expensive in terms of the median cost; (2) among problem instances on the crossover belt those with a smaller number of intra-agent constraints and a larger number of inter-agent constraints may be more expensive; and (3) for a fixed total number of variables problem instances on the crossover belt may be more expensive as the number of agents increases or the number of variables per agent decreases. Our further experiments suggest that these observations can be generalized to cases where different algorithms are applied or different sets of parameters of the problem are used.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We first present an algorithm called multi-ABT as a baseline algorithm for solving distributed constraint satisfaction problems where each agent has multiple local variables. Then, we show a cost profile of multi-ABT for various numbers of intra-agent constraints (constraints defined over variables of one agent) and inter-agent constraints (constraints defined over variables of multiple agents) in a distributed graph-coloring problem. This cost profile enabled us to make the following observations: (1) the satisfiability thresholds are identified in the narrow region on the x-y plane (where the x-axis is the number of intra-agent constraints and the y-axis is the number of inter-agent constraints) in which the sum of intra- and inter-agent constraints is constant, and problem instances in the region (called the crossover belt) are likely to be expensive in terms of the median cost; (2) among problem instances on the crossover belt, those with a smaller number of intra-agent constraints and a larger number of inter-agent constraints may be more expensive; and (3) for a fixed total number of variables, problem instances on the crossover belt may be more expensive as the number of agents increases or the number of variables per agent decreases. Our further experiments suggest that these observations can be generalized to cases where different algorithms are applied or different sets of parameters of the problem are used.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 45, 号 9, p. 2217-2225, 発行日 2004-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764