Skip to main content

Research Repository

Advanced Search

A hybrid approach to solving coarse-grained DisCSPs.

Lee, David; Arana, Inés; Ahriz, Hatem; Hui, Kit-Ying

Authors

David Lee

Inés Arana

Hatem Ahriz

Kit-Ying Hui



Abstract

A coarse-grained Distributed Constraint Satisfaction Problem (DisCSP) consists of several loosely connected constraint satisfaction subproblems, each assigned to an individual agent. We present Multi-Hyb, a two-phase concurrent hybrid approach for solving DisCSPs. In the first phase, each agents subproblem is solved using systematic search which generates the key partial solutions to the global problem. Concurrently, a penalty-based local search algorithm attempts to find a global solution from these partial solutions. If phase 1 fails to find a solution, a phase 2 systematic search algorithm solves the problem using the knowledge gained from phase 1. We show that our approach is highly competitive in comparison with other coarse-grained DisCSP algorithms.

Citation

LEE, D., ARANA, I., AHRIZ, H. and HUI, K.-Y. 2009. A hybrid approach to solving coarse-grained DisCSPs. In Proceedings of the 8th International conference on autonomous agents and multiagent systems (AAMAS 2009), 10-15 May 2009, Budapest, Hungary. Richland, South Carolina: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) [online], pages 1235-1236. Available from: http://www.aamas-confer..._Abstract/C_SP_0555.pdf

Conference Name 8th International conference on autonomous agents and multiagent systems (AAMAS 2009)
Start Date May 10, 2009
End Date May 15, 2009
Online Publication Date Dec 31, 2009
Publication Date Dec 31, 2009
Deposit Date Jun 8, 2009
Publicly Available Date Jun 8, 2009
Publisher International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages 1235-1236
Keywords Artificial intelligence; Constraint satisfaction; Agent cooperation; Distributed problem solving
Public URL http://hdl.handle.net/10059/359
Publisher URL http://www.ifaamas.org/Proceedings/aamas09/pdf/02_Extended_Abstract/C_SP_0555.pdf

Files





You might also like



Downloadable Citations