A Scalable, Distributed Algorithm for Efficient Task Allocation

A Scalable, Distributed Algorithm for Efficient Task Allocation

DSpace/Manakin Repository

A Scalable, Distributed Algorithm for Efficient Task Allocation

dc.contributor.author	Peleshchuk, Denis
dc.contributor.author	Sander, Pedro
dc.contributor.author	Grosz, Barbara
dc.date.accessioned	2009-02-05T19:03:52Z
dc.date.issued	2002
dc.identifier.citation	Sander, Pedro V., Denis Peleshchuk, and Barbara J. Grosz. 2002. A scalable, distributed algorithm for efficient task allocation. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems: July 15-19, 2002, Plazzo re Enzo, Bologna, Italy, ed. International Joint Conference on Autonomous Agents and Multiagent Systems, and Cristiano Castelfranchi, 1191-1198. New York: ACM Press.	en
dc.identifier.uri	http://nrs.harvard.edu/urn-3:HUL.InstRepos:2562072
dc.description.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.	en
dc.description.sponsorship	Engineering and Applied Sciences	en
dc.publisher	Association for Computing Machinery	en
dc.relation.isversionof	http://dx.doi.org/10.1145/545056.545098	en
dash.license	LAA
dc.title	A Scalable, Distributed Algorithm for Efficient Task Allocation	en
dc.relation.journal	Proceedings of the First International Joint Conference on Autonomous Agents and Multi-agent Systems: Part 3	en
dash.depositing.author	Grosz, Barbara