Evaluating the performance of DCOP algorithms in a real world, dynamic problem

ABSTRACT

Complete algorithms have been proposed to solve problems modelled as distributed constraint optimization (DCOP). However, there are only few attempts to address real world scenarios using this formalism, mainly because of the complexity associated with those algorithms. In the present work we compare three complete algorithms for DCOP, aiming at studying how they perform in complex and dynamic scenarios of increasing sizes. In order to assess their performance we measure not only standard quantities such as number of cycles to arrive to a solution, size and quantity of exchanged messages, but also computing time and quality of the solution which is related to the particular domain we use. This study can shed light in the issues of how the algorithms perform when applied to problems other than those reported in the literature (graph coloring, meeting scheduling, and distributed sensor network).

REFERENCES

• 1: Ana L. Bazzan, A Distributed Approach for Coordination of Traffic Signal Agents, Autonomous Agents and Multi-Agent Systems, v.10 n.1, p.131-164, January 2005 [doi>10.1007/s10458-004-6975-9]
• 2: Michael Benisch , Norman Sadeh, Examining DCSP coordination tradeoffs, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160896]
• 3: E. Camponogara and W. Kraus Jr. Distributed learning agents in urban traffic control. In F. Moura-Pires and S. Abreu, editors, EPIA, pages 324--335, 2003.
• 4: C. Diakaki, M. Papageorgiou, and K. Aboudolas. A multivariable regulator approach to traffic-responsive network-wide signal control. Control Engineering Practice, 10(2):183--195, February 2002.
• 5: Kurt Dresner , Peter Stone, Multiagent Traffic Management: A Reservation-Based Intersection Control Mechanism, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.530-537, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.190]
• 6: P. B. Hunt, D. I. Robertson, R. D. Bretherton, and R. I. Winton. SCOOT - a traffic responsive method of coordinating signals. TRRL Lab. Report 1014, Transport and Road Research Laboratory, Berkshire, 1981.
• 7: P. Lowrie. The Sydney coordinate adaptive traffic system - principles, methodology, algorithms. In Proceedings of the International Conference on Road Traffic Signalling, Sydney, Australia, 1982.
• 8: Rajiv T. Maheswaran , Milind Tambe , Emma Bowring , Jonathan P. Pearce , Pradeep Varakantham, Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.310-317, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.257]
• 9: Roger Mailler , Victor Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.438-445, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.249]
• 10: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, Adopt: asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence, v.161 n.1-2, p.149-180, January 2005 [doi>10.1016/j.artint.2004.09.003]
• 11: Luis Nunes , Eugenio Oliveira, Learning from Multiple Sources, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1106-1113, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.159]
• 12: Denise de Oliveira , Ana L. C. Bazzan , Victor Lesser, Using cooperative mediation to coordinate traffic lights: a case study, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082544]
• 13: D. Oliveira, P. Ferreira, A. L. C. Bazzan, and F. Klügl. A swarm-based approach for selection of signal plans in urban scenarios. In Proceedings of Fourth International Workshop on Ant Colony Optimization and Swarm Intelligence - ANTS 2004, volume 3172 of Lecture Notes in Computer Science, pages 416--417, Berlin, Germany, 2004.
• 14: M. Papageorgiou, C. Diakaki, V. Dinopoulou, A. Kotsialos, and Y. Wang. Review of road traffic control strategies. Proceedings of the IEEE, 91(12):2043--2067, December 2003.
• 15: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In L. P. Kaelbling and A. Saffiotti, editors, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, pages 266--271, Edinburgh, Scotland, August 2005. Professional Book Center.
• 16: A. Petcu and B. Faltings. MB-DPOP: A new memory-bounded algorithm for distributed optimization. In M. M. Veloso, editor, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), pages 1452--1457, Hyderabad, India, January 2007.
• 17: Bruno C. da Silva , Eduardo W. Basso , Ana L. C. Bazzan , Paulo M. Engel, Dealing with non-stationary environments using context detection, Proceedings of the 23rd international conference on Machine learning, p.217-224, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143872]
• 18: Bruno Castro da Silva , Robert Junges , Denise de Oliveira , Ana L. C. Bazzan, ITSUMO: an Intelligent Transportation System for Urban Mobility, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160920]
• 19: TRANSYT-7F. TRANSYT-7F User's Manual. Transportation Research Center, University of Florida, 1988.
• 20: Makoto Yokoo , Edmund H. Durfee , Toru Ishida , Kazuhiro Kuwabara, The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.673-685, September 1998 [doi>10.1109/69.729707]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms

Keywords:
coordination, distributed constraint optimization, traffic control