Distributed Constraint Satisfaction with Multiply Sectioned Constraint Networks
Date
2014
Authors
Xiang, Yang
Mohamed, Younis
Zhang, Wanling
Journal Title
Journal ISSN
Volume Title
Publisher
Inderscience
Abstract
We propose a new algorithmic framework, multiply sectioned constraint networks (MSCNs), for solving distributed constraint satisfaction problems (DisCSPs) with complex local problems. An MSCN is converted into a linked junction forest (LJF) and is solved by a complete algorithm. Its time complexity is linear on the number and size of local problems (each in charge by an agent) and is exponential on cluster size of LJF. We show that the MSCN-LJF algorithm is more efficient than junction tree-based DisCSP algorithms. When a DisCSP is not naturally an MSCN, we show how to convert it into an MSCN, so that any DisCSP can be solved as above.
Description
Journal webpage: http://www.inderscience.com/jhome.php?jcode=ijids
Keywords
Distributed constraint satisfaction problems, multiply sectioned constraint networks, linked junction forests, complex local problems, multiagent systems, junction trees.