DCOPolis: a framework for simulating and deploying distributed constraint reasoning algorithms

ABSTRACT

The proliferation of mobile computers---such as laptops, personal digital assistants, and smart phones---has propelled distributed computing into mainstream society. Over the past decade these technologies have spurred interest in both decentralized multiagent systems and wireless mobile ad-hoc networks. Such networks, however, present many challenges to information sharing and coordination. Interference, obstacles, and other environmental effects conspire with power-and processing-limited hardware to impose a number of challenging networking characteristics. Messages are routinely lost or delayed, connections may be only sporadically available, and network transfer capacity is nowhere near that available on modern wired networks. It is therefore imperative to emphasize local decision making and autonomy over a centralized analogue, insofar as it is possible. The majority of such decentralized decision making can be seen as a fundamental problem of propagating and then solving systems of constraints, otherwise known as Distributed Constraint Reasoning (DCR).

REFERENCES

• 1: Anton Chechetka , Katia Sycara, No-commitment branch and bound search for distributed constraint optimization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160900]
• 2: John Davin , Pragnesh Jay Modi, Impact of problem centralization in distributed constraint optimization algorithms, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082633]
• 3: A. Haeberlen, A. Mislove, A. Post, and P. Druschel. Fallacies in evaluating decentralized systems. In Proceedings of the Fifth International Workshop on Peer-to-Peer Systems, February 2006.
• 4: 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]
• 5: A. Meisels, E. Kaplansky, I. Razgon, and R. Zivan. Comparing performance of distributed constraints processing algorithms. In Proceedings of the Third International Workshop on DCR, 2002.
• 6: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, An asynchronous complete method for distributed constraint optimization, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860602]
• 7: A. Petcu and B. Faltings. A distributed, complete method for multi-agent constraint optimization. In Proceedings of the Fifth International Workshop on DCR, September 2004.
• 8: E. Sultanik, R. Lass, and W. Regli. DCOPolis: A framework for simulating and deploying distributed constraint optimization algorithms. In Proceedings of the Ninth International Workshop on DCR, Providence, RI, September 2007.
• 9: Roie Zivan , Amnon Meisels, Message delay and DisCSP search algorithms, Annals of Mathematics and Artificial Intelligence, v.46 n.4, p.415-439, April 2006 [doi>10.1007/s10472-006-9033-2]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.3 Applications

Keywords:
distributed constraint reasoning, middleware, simulation