Adopt: asynchronous distributed constraint optimization with quality guarantees.

*(English)*Zbl 1132.68706Summary: The Distributed Constraint Optimization Problem (DCOP) is a promising approach for modeling distributed reasoning tasks that arise in multiagent systems. Unfortunately, existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while allowing agents to operate asynchronously. We show how this failure can be remedied by allowing agents to make local decisions based on conservative cost estimates rather than relying on global certainty as previous approaches have done. This novel approach results in a polynomial-space algorithm for DCOP named Adopt that is guaranteed to find the globally optimal solution while allowing agents to execute asynchronously and in parallel. Detailed experimental results show that on benchmark problems Adopt obtains speedups of several orders of magnitude over other approaches. Adopt can also perform bounded-error approximation – it has the ability to quickly find approximate solutions and, unlike heuristic search methods, still maintain a theoretical guarantee on solution quality.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

68W15 | Distributed algorithms |

PDF
BibTeX
XML
Cite

\textit{P. J. Modi} et al., Artif. Intell. 161, No. 1--2, 149--180 (2005; Zbl 1132.68706)

Full Text:
DOI

##### References:

[1] | Armstrong, A.; Durfee, E., Dynamic prioritization of complex agents in distributed constraint satisfaction problems, (), 620-625 |

[2] | Barrett, A., Autonomy architectures for a constellation of spacecraft, () |

[3] | Bistarelli, S.; Montanari, U.; Rossi, F., Constraint solving over semirings, (), 624-630 |

[4] | Caulder, R.; Smith, J.E.; Courtemanche, A.J.; Mar, M.F.; Ceranowicz, A.Z., Modsaf behavior simulation and control, () |

[5] | Chalupsky, H.; Gil, Y.; Knoblock, C.A.; Lerman, K.; Oh, J.; Pynadath, D.V.; Russ, T.A.; Tambe, M., Electric elves: applying agent technology to support human organizations, (), 51-58 |

[6] | Collin, Z.; Dechter, R.; Katz, S., On the feasibility of distributed constraint satisfaction, (), 318-324 · Zbl 0747.68065 |

[7] | Collin, Z.; Dolev, S., Self-stabilizing depth first search, Inform. process. lett., 49, 297-301, (1994) · Zbl 0803.68041 |

[8] | Dechter, R.; Dechter, A.; Pearl, J., Optimization in constraint networks, () · Zbl 0678.68100 |

[9] | Fitzpatrick, S.; Meertens, L., An experimental assessment of a stochastic, anytime, decentralized, soft colourer for sparse graphs, () · Zbl 1054.68585 |

[10] | Frei, C.; Faltings, B., Resource allocation in networks using abstraction and constraint satisfaction techniques, (), 204-218 |

[11] | Freuder, E.C.; Quinn, M.J., Taking advantage of stable sets of variables in constraint satisfaction problems, (), 1076-1078 |

[12] | Hamadi, Y.; Bessière, C.; Quinqueton, J., Distributed intelligent backtracking, (), 219-223 |

[13] | Hirayama, K.; Yokoo, M., Distributed partial constraint satisfaction problem, (), 222-236 |

[14] | Hirayama, K.; Yokoo, M., An approach to over-constrained distributed constraint satisfaction problems: distributed hierarchical constraint satisfaction, () |

[15] | Kitano, H.; Todokoro, S.; Noda, I.; Matsubara, H., () |

[16] | Korf, R.E., Depth-first iterative-deepening: an optimal admissible tree search, Artificial intelligence, 27, 1, 97-109, (1985) · Zbl 0573.68030 |

[17] | Lemaitre, M.; Verfaillie, G., An incomplete method for solving distributed valued constraint satisfaction problems, () |

[18] | Liu, J.; Sycara, K., Exploiting problem structure for distributed constraint optimization, () |

[19] | Lynch, N., Distributed algorithms, (1996), Morgan Kaufmann San Mateo, CA · Zbl 0877.68061 |

[20] | Meseguer, P.; Jiménez, M.A., Distributed forward checking, () |

[21] | Modi, P.J.; Shen, W.; Tambe, M.; Yokoo, M., An asynchronous complete method for distributed constraint optimization, () |

[22] | Modi, P.J.; Ali, S.M.; Shen, W.; Tambe, M., Distributed constraint reasoning under unreliable communication, () |

[23] | P.J. Modi, Distributed constraint optimization for multiagent systems, PhD Thesis, University of Southern California, Marina del Rey, CA, 2003 |

[24] | Parunak, V.; Ward, A.; Fleischer, M.; Sauter, J.; Chang, T., Distributed component-centered design as agent-based distributed constraint optimization, () |

[25] | Schiex, T.; Fargier, H.; Verfaillie, G., Valued constraint satisfaction problems: hard and easy problems, Montreal, quebec, (), 631-639 |

[26] | Shen, W.-M.; Yim, M., Self-reconfigurable robots, IEEE trans. mechatron., 7, 4, (2002) |

[27] | Silaghi, M.C.; Sam-Haroud, D.; Faltings, B., Asynchronous search with aggregations, (), 917-922 |

[28] | (2001), BAE Systems, Ecm challenge problem |

[29] | Tambe, M., Towards flexible teamwork, J. artificial intelligence res., 7, 83-124, (1997) |

[30] | Yokoo, M., Distributed constraint satisfaction: foundation of cooperation in multi-agent systems, (2001), Springer Berlin · Zbl 0968.68150 |

[31] | Yokoo, M.; Hirayama, K., Distributed constraint satisfaction algorithm for complex local problems, () |

[32] | Zhang, W.; Wittenburg, L., Distributed breakout revisited, (), 352 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.