A Scalable, Distributed Algorithm for Efficient Task Allocation

DSpace/Manakin Repository

A Scalable, Distributed Algorithm for Efficient Task Allocation

Citable link to this page

. . . . . .

Title: A Scalable, Distributed Algorithm for Efficient Task Allocation
Author: Peleshchuk, Denis; Sander, Pedro; Grosz, Barbara

Note: Order does not necessarily reflect citation order of authors.

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.
Full Text & Related Files:
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.
Published Version: http://dx.doi.org/10.1145/545056.545098
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2562072

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7585]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters