A scalable, distributed algorithm for efficient task allocation

ABSTRACT

We present a distributed algorithm for task allocation in multi-agent systems for settings in which agents and tasks are geographically dispersed in two-dimensional space. We describe a method that enables agents to determine individually how to move so that they are, as a group, efficiently assigned to tasks. The method comprises two algorithms and is especially useful in environments with very large numbers of agent and task nodes. One algorithm adapts computational geometry techniques to determine adjacency information for the agent nodes given the geographical positions of agents and tasks. This adjacency information is used to determine the visible nodes that are most relevant to an agent's decision making process and to eliminate those that it should not consider. The second algorithm uses local heuristics based solely on an agent's adjacent nodes to determine its course of action. This method yields improved task allocations compared to previous algorithms proposed for similar environments. We also present a modification to the second algorithm that improves performance in environments in which multiple agents are required to complete a single task.

REFERENCES

• 1: Barber, C. B., Huhdanpaa, H. The Qhull software library. URL: http://www.geom.umn.edu/software/qhull/
• 2: Corkill, D. D., and Lesser, V. R. The use of meta-level Control for coordination in a distributed problem dolving network Proc. Int. Joint Conf. On AI, Karlsruhe, Germany, pp 748--756, 1986.
• 3: Delaunay, B. Sur la sphère vide. Bull. Acad. Sci. USSR(VII), Classe Sci. Mat. Nat., 793--800, 1934.
• 4: Ephrati, E., Pollack, M. E., Ur, S. Deriving multi-agent coordination through filtering strategies. Proceedings of 14th International Joint Conference on Artificial Intelligence, 1995.
• 5: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 6: Nick R. Jennings, Coordination techniques for distributed artificial intelligence, Foundations of distributed artificial intelligence, John Wiley & Sons, Inc., New York, NY, 1996
• 7: 0. Shehory, Coalition Formation for Large-Scale Electronic Markets, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.167, July 10-12, 2000
• 8: Thomas W. Malone, Modeling coordination in organizations and markets, Management Science, v.33 n.10, p.1317-1332, October 1, 1987 [doi>10.1287/mnsc.33.10.1317]
• 9: Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M. Coverage Problems in Wireless Ad-hoc Sensor Networks. Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, 2001.
• 10: Moni Naor , Larry Stockmeyer, What can be computed locally?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.184-193, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167149]
• 11: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 12: Sandholm, T., Lesser, V. Issues in automated negotiation and electronic commerce: Extending the contract net framework. Proceedings of the First International Conference on Multiagent Systems, 1995.
• 13: Onn Shehory , Sarit Kraus , Osher Yadgar, Goal Satisfaction in Large Scale Agent-Systems: A Transportation Example, Proceedings of the 5th International Workshop on Intelligent Agents V, Agent Theories, Architectures, and Languages, p.277-292, July 04-07, 1998
• 14: Onn Shehory, A Scalable Agent Location Mechanism, 6th International Workshop on Intelligent Agents VI, Agent Theories, Architectures, and Languages (ATAL),, p.162-172, July 15-17, 1999
• 15: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation