Abstract
The distributed constraint satisfaction problem is a general framework used to represent problems in distributed multi-agent systems. In this paper, we describe a detailed investigation of handling over-constrained satisfaction problems in a dynamic and multi-agent environment. We introduce a new algorithm, Over-constrained Dynamic Agent Ordering, that treats under and over-constrained problems uniformly. While the existing approaches generally only consider a single variable per agent, the proposed algorithm can handle multiple variables per agent. In this approach, we use the degree of unsatisfiability as a measure for relaxing constraints, and hence as a way to guide the search towards the best possible solution(s). Through an experimental study, we demonstrate that our algorithm performs better than the one based on asynchronous weak commitment search.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Freuder, E.C., Wallace, R.J.: Partial constraint satisfaction. Artificial Intelligence 58(1-3), 21–70 (1992)
Hirayama, K., Yokoo, M.: Distributed partial constraint satisfaction problem. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 222–236. Springer, Heidelberg (1997)
Hirayama, K., Yokoo, M.: An approach to over-constrained distributed constraint satisfaction problems: Distributed hierarchical constraint satisfact. In: Proceedings of the Fourth International Conference on MultiAgent Systems, ICMAS 2000 (2000)
Mailler, R., Lesser, V.: Solving Distributed Constraint Optimization Problems Using Cooperative Mediation. In: AAMAS 2004, pp. 438–445. IEEE Computer Society, Los Alamitos (2004)
Minton, S., Johnston, M.D., Philips, A.B., Laird, P.: Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 161–205 (1992)
Modi, P.J., Shen, W.-M., Tambe, M., Yokoo, M.: An asynchronous complete method for distributed constraint optimization. In: Proceedings of the second international joint conference on Autonomous agents and multiagent systems, pp. 161–168. ACM Press, New York (2003)
Yokoo, M.: Constraint relaxation in distributed constraint satisfaction problem. In: Proceedings of 5th International Conference on Tools with Artificial Intelligence, pp. 56–63 (1993)
Yokoo, M., Durfee, E.H.: Distributed constraint optimization as a formal model of partially adversarial cooperation. Technical Report CSE-TR-101-91, Ann Arbor, MI 48109 (1991)
Yokoo, M., Hirayama, K.: Distributed constraint satisfaction algorithm for complex local problems. In: Proceedings of the Third International Conference on Multiagent Systems (ICMAS 1998), pp. 372–379 (1998)
Zhou, L., Thornton, J., Sattar, A.: Dynamic agent ordering in distributed constraint satisfaction problems. In: Gedeon, T(T.) D., Fung, L.C.C. (eds.) AI 2003. LNCS (LNAI), vol. 2903, pp. 427–439. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhou, L., Sattar, A., Goodwin, S. (2005). Handling Over-Constrained Problems in Distributed Multi-agent Systems. In: Kégl, B., Lapalme, G. (eds) Advances in Artificial Intelligence. Canadian AI 2005. Lecture Notes in Computer Science(), vol 3501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11424918_2
Download citation
DOI: https://doi.org/10.1007/11424918_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25864-3
Online ISBN: 978-3-540-31952-8
eBook Packages: Computer ScienceComputer Science (R0)