Are multiagent algorithms relevant for real hardware?: a case study of distributed constraint algorithms

ABSTRACT

Researchers building multi-agent algorithms typically work with problems abstracted away from real applications. The abstracted problem instances allow systematic and detailed investigations of new algorithms. However, a key question is how to apply algorithm, developed on an abstract problem, in a real application. In this paper, we report on what was required to apply a particular distributed resource allocation algorithm developed for an abstract coordination problem in a real hardware application. A probabilistic representation of resources and tasks was used to deal with uncertainty and dynamics and local reasoning was used to deal with delays in the distributed resource allocation algorithm. The probabilistic representation and local reasoning enabled the use of the multi-agent algorithm which, in turn, improved the overall performance of the system.

REFERENCES

• 1: Collin and Dechter. A distributed solution to the network consistency problem. AI Journal, pages 242--251, 1990.
• 2: Steve Hanks , Martha E. Pollack , Paul R. Cohen, Benchmarks, test beds, controlled experimentation, and the design of agent architectures, AI Magazine, v.14 n.4, p.17-42, Winter 1993
• 3: 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]
• 4: P. J. Modi, W. Shen, and M. Tambe. Distributed constraint optimization and its application. Technical Report ISI-TR-509, University of Southern California/Information Sciences Institute, 2002.
• 5: 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]
• 6: S. Parsons, C. Sierra, and N. R. Jennings, Agents that negotiate by arguing. Journal of Logic and Computation, 1998.
• 7: BAE Systems/Sanders. ECM challenge problem. http://www.sanders.com/ants/ecm.htm, 2001.
• 8: Noam M. Shazeer , Michael L. Littman , Greg A. Keim, Solving crossword puzzles as probabilistic constraint satisfaction, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.156-162, July 18-22, 1999, Orlando, Florida, United States
• 9: O. Shehory and S. Kraus. Task allocation via coalition formation among autonomous agents. In Proceedings of IJCAI'95, pages 655--661, 1995.
• 10: William E. Walsh , Michael P. Wellman, A Market Protocol for Decentralized Task Allocation, Proceedings of the 3rd International Conference on Multi Agent Systems, p.325, July 03-07, 1998
• 11: 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]