Learning and exploiting knowledge in multi-agent task allocation problems

ABSTRACT

Imagine a group of cooperating agents attempting to allocate tasks amongst themselves without knowledge of their own capabilities. Over time, they develop a belief of their own skill levels through failed attempts at completing the tasks they are assigned. How will various task allocation approaches perform when there exists this added level of complexity? In particular, we compare two task allocation strategies: a greedy, first-come-first-serve approach, and a more intelligent, best-fit method. By varying the number of tasks along with the amount of time it takes to complete those tasks, we find that the different task allocation methods work better in different situations. Because of the way the tasks are allocated by the two methods, the greedy approach does a better job of giving agents opportunities to learn their capabilities. Thus, the greedy approach allows for quicker learning and performs better on problems where the task durations are short, whereas the best-fit method performs better on problems where the task quantity and durations are large. What is needed is a hybrid method that balances between the exploration of the greedy approach and the exploitation of the best-fit method.

REFERENCES

• 1: C. Anderson and N. R. Franks. Teams in animal societies. Behavioural Ecology, 12(5):534--540, 2001.
• 2: 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.
• 3: B. P. Gerkey and M. J. Mataric. A formal analysis and taxonomy of task allocation in multi-robot systems. International Journal of Robotics Research, 23(9):939--954, September 2004.
• 4: Hoong Chuin Lau , Lei Zhang, Task Allocation via Multi-Agent Coalition Formation: Taxonomy, Algorithms and Complexity, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.346, November 03-05, 2003
• 5: 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.
• 6: 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]
• 7: F. R. Noreils. An architecture for cooperative and autonomous mobile robots. In Proceedings of the 1992 IEEE International Conference on Robotics and Automation, pages 2703--2710, May 1992.
• 8: R. G. Smith and R. Davis. Frameworks for cooperation in distributed problem solving. SMC-11(1):61--70, January 1981.

INDEX TERMS

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

General Terms:
Experimentation

Keywords:
multi-agent systems, task allocation