Gradient field-based task assignment in an AGV transportation system

ABSTRACT

Assigning tasks to agents is complex, especially in highly dynamic environments. Typical protocol-based approaches for task assignment such as Contract Net have proven their value, however, they may not be flexible enough to cope with continuously changing circumstances. In this paper we study and validate the feasibility of a field-based approach for task assignment in a complex problem domain.In particular, we apply the field-based approach for task assignment in an AGV transportation system. In this approach, transports emit fields into the environment that attract idle AGVs. To avoid multiple AGVs driving towards the same transport, AGVs emit repulsive fields. AGVs combine received fields and follow the gradient of the combined fields, that guide them towards pick locations of transports. The AGVs continuously reconsider the situation of the environment and task assignment is delayed until the load is picked, improves the flexibility of the system.Extensive experiments indicate that the field-based approach outperforms the standard Contract Net approach on various performance measures, such as the average wait time of transports and throughput. Limitations of the field-based approach are an unequal distribution of wait times across different transports and a small increase of bandwidth occupation.

REFERENCES

• 1: Automatic Guided Vehicle Simulator, K. U. Leuven, 2005. http://www.es.kuleuven.ac.be/~distrinet/taskforces/agentwise/agvsimulator/.
• 2: Samir Aknine , Suzanne Pinson , Melvin F. Shakun, An Extended Multi-Agent Negotiation Protocol, Autonomous Agents and Multi-Agent Systems, v.8 n.1, p.5-45, January 2004 [doi>10.1023/B:AGNT.0000009409.19387.f8]
• 3: N. Boucke, D. Weyns, T. Holvoet, and K. Mertens. Decentralized allocation of tasks with delayed commencement. In Proceedings of European Workshop on Multiagent Systems, Barcelone, Spain, 2004.
• 4: G. Buchman, D. Cohen, P. Vemaza, and D. Lee. The University of Pennsylvania Robocup 2005 Legged Soccer Team. http://www.cis.upenn.edu/robocup/U Penn05.pdf, 2005.
• 5: Egemin Modular Controls Concept. EMC² project, IWT, Belgium. http://emc2.egemin.com/, 2005.
• 6: A. Farinelli, L. Iocchi, D. Nardi, and V. Ziparo. Task Assignment with Dynamic Perception and Constrained Tasks in a Multi-Robot System. Proceedings of the IEEE International Conference on Robotics and Automation, 2004.
• 7: Jacques Ferber, Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 8: P. Hart, N. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 1968.
• 9: A. Helleboogh, T. Holvoet, D. Weyns, and Y. Berbers. Extending time management support for multi-agent systems. In Multiagent and Multiagent-based Simulation, New York, USA, 2005.
• 10: T. Knabe, M. Schillo, and K. Fischer. Improvements to the FIPA Contract Net Protocol for Performance Increase and Cascading Applications. Proceedings of the Workshop on Multiagent Interoperability, 2002.
• 11: Tore Knabe , Michael Schillo , Klaus Fischer, Inter-organizational networks as patterns for self-organizing multiagent systems, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860783]
• 12: L. Breton, S. Maza, and P. Castagna. Simulation multi-agent de systèmes d'AGVs: comparaison avec une approche prédictive. 5^e Conférence Francophone de Modélisation et Simulation, 2004.
• 13: M. Mamei and F. Zambonelli. Motion coordination in the quake 3 arena environment: a field-based approach. First International Workshop on Environments for Multiagent Systems, 2003.
• 14: Marco Mamei , Franco Zambonelli, Programming Pervasive and Mobile Computing Applications with the TOTA Middleware, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom'04), p.263, March 14-17, 2004
• 15: M. Mamei, F. Zambonelli, and L. Leonardi. Co-Fields: A Physical Inspired Approach to Distributed Motion Coordination. IEEE Pervasive Computing, 2004.
• 16: F. D. Paoli and G. Vizzari. Context dependent management of field diffusion: an experimental framework. Workshop Dagli Oggetti agli Agenti, Villasimius, Italy, 2002.
• 17: W. Schols, T. Holvoet, N. Boucke, and D. Weyns. Gradient Field Based Transport Assignment in AGV Systems. In CW-425, Technical Report, Departement of Computer Science, Katholieke Universiteit Leuven, Belgium. http://www.cs.kuleuven.ac.be/publicaties/rapporten/CW/2005/.
• 18: Onn Shehory , Sarit Kraus , Osher Yadgar, Emergent cooperative goal-satisfaction in large-scale automated-agent systems, Artificial Intelligence, v.110 n.1, p.1-55, May 1999 [doi>10.1016/S0004-3702(99)00019-3]
• 19: R. G. Smith. The contract net protocol: High level communication and control in a distributed problem solver. In IEEE Transactions on Computers, C-29(12), 1980.
• 20: Danny Weyns , Tom Holvoet, A Formal Model for Situated Multi-Agent Systems, Fundamenta Informaticae, v.63 n.2-3, p.125-158, April 2004
• 21: Danny Weyns , Kurt Schelfthout , Tom Holvoet , Tom Lefever, Decentralized control of E'GV transportation systems, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082806]
• 22: Danny Weyns , Elke Steegmans , Tom Holvoet, Protocol Based Communication for Situated Multi-Agent Systems, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.118-125, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.218]
• 23: D. Weyns, E. Steegmans, and T. Holvoet. Towards active perception for situated multi-agent systems. Applied Artificial Intelligence, 18(8--9), 2004.

INDEX TERMS

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

General Terms:
Design