Multi-agent task allocation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multi-agent task allocation: learning when to say no

Full text

Pdf (374 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 10th annual conference on Genetic and evolutionary computation table of contents

Atlanta, GA, USA

SESSION: Artificial life, evolutionary robotics, adaptive behavior, evolvable hardware papers table of contents

Pages 201-208

Year of Publication: 2008

ISBN:978-1-60558-130-9

Authors

Adam Campbell	University of Central Florida, Orlando, FL, USA
Annie S. Wu	University of Central Florida, Orlando, FL, USA
Randall Shumaker	Institute for Simulation and Training, Orlando, FL, USA

Sponsors

ACM: Association for Computing Machinery
SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 108, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1389095.1389128 What is a DOI?

ABSTRACT

This paper presents a communication-less multi-agent task allocation procedure that allows agents to use past experience to make non-greedy decisions about task assignments. Experimental results are given for problems where agents have varying capabilities, tasks have varying difficulties, and agents are ignorant of what tasks they will see in the future. These types of problems are difficult because the choice an agent makes in the present will affect the decisions it can make in the future. Current task-allocation procedures, especially the market-based ones, tend to side-step the issue by ignoring the future and assigning tasks to agents in a greedy way so that short-term goals are met. It is shown here that these short-sighted allocation procedures work well in situations where the ratio of task length to team size is small, but their performance decreases as this ratio increases. The adaptive method presented here is shown to perform well in a wide range of task-allocation problems, and because it requires no explicit communication, its computational costs are independent of team size.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. P. Bertsekas. Auction algorithms for network flow problems: A tutorial introduction. Computational Optimization and Applications, 1:7--66, December 1992.
	2	Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
	3	Hesham El-Rewini , Hesham H. Ali , Ted Lewis, Task Scheduling in Multiprocessing Systems, Computer, v.28 n.12, p.27-37, December 1995 [doi>10.1109/2.476197]
	4	U. Faigle. Some recent results in the analysis of greedy algorithms for assignment problems. OR Spectrum, 15(4):181--188, December 1994.
	5	N. R. Franks. Teams in social insects: group retrieval of prey by army ants (eciton burchelli, hymenoptera: Formicidae). Behavioral Ecology and Sociobiology, 18(6):425--429, 1986.
	6	D. Gale. The Theory of Linear Economic Models. McGraw-Hill Book Company, Inc., New York, 1960.
	7	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	8	B. P. Gerkey and M. J. Matarić. Sold!: Market methods for multi-robot coordination. IEEE Transactions on Robotics and Automation, 18(5):758--768, October 2002.
	9	B. P. Gerkey and M. J. Matarić. A formal analysis and taxonomy of task allocation in multi-robot systems. International Journal of Robotics Research, 23(9):939--954, September 2004.
	10	H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1):83--97, 1955.
	11	T. H. Labella, M. Dorigo, and J.-L. Deneubourg. Efficiency and task allocation in prey retrieval. In Proceedings of the 1st International Workshop on Biologically Inspired Approaches to Advanced Information Technology, pages 274--289, 2004.
	12	Kristina Lerman , Chris Jones , Aram Galstyan , Maja J Mataríc, Analysis of Dynamic Task Allocation in Multi-Robot Systems, International Journal of Robotics Research, v.25 n.3, p.225-241, March 2006 [doi>10.1177/0278364906063426]
	13	T. C. Lueth and T. Laengle. Task description, decomposition and allocation in a distributed autonomous multi-agent robot system. In Proceedings of International Conference on Intelligent Robots and Systems, pages 1516--1523, September 1994.
	14	Maja J. Matarić , Gaurav S. Sukhatme , Esben H. Østergaard, Multi-Robot Task Allocation in Uncertain Environments, Autonomous Robots, v.14 n.2-3, p.255-263, March-May 2003 [doi>10.1023/A:1022291921717]
	15	E. H. Østergaard, M. J. Matarić, and G. S. Sukhatme. Distributed multi-robot task allocation for emergency handling. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Wailea, Hawaii, October 2001.
	16	L. E. Parker. Alliance: An architecture for fault-tolerant multi-robot cooperation. IEEE Transactions on Robotics and Automation, 14(2):220--240, 1998.
	17	F. Ravary, E. Lecoutey, G. Kaminski, N. Châline, and P. Jaisson. Individual experience alone can generate lasting division of labor in ants. Current Biology, 17:1308--1312, 2007.
	18	P. R. Wurman, R. D'Andrea, and M. Mountz. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. In AAAI, pages 1752--. AAAI Press, 2007.