Handling uncertainty of resource division in multi agent system using game against nature

• Autorzy: Skrzypczyk K. , Mellado M.

Identyfikatory

DOI

10.2478/acsc-2014-0021

• Języki publikacji: EN

Abstrakty

EN

This paper addresses the problem of resource division for robotic agents in the framework of Multi-Agent System. Knowledge of the environment represented in the system is uncertain, incomplete and distributed among the individual agents that have both limited sensing and communication abilities. The pick-up-and-collection problem is considered in order to illustrate the idea presented. In this paper a framework for cooperative task assignment to individual agents is discussed. The process of negotiating access to common resources by intercommunicating agents is modeled and solved as a game against Nature. The working of the proposed system was verified by multiple simulations. Selected, exemplary simulations are presented in the paper to illustrate the approach discussed.

Słowa kluczowe

EN

multi-agent system; distributed system; negotiations; uncertainty; game theory

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2014
• Tom: Vol. 24, no. 3
• Strony: 351--373
• Opis fizyczny: Bibliogr. 34 poz., rys.

Twórcy

autor

Skrzypczyk K.

• Institute of Automatic Control, Silesian University of Technology, Gliwice, Poland

autor

Mellado M.

• Instituto de Automática e Informática Industrial Universidad Politecnica de Valencia, Spain

Bibliografia

• [1] C. Baldassano and N. E. Leonard: Explore vs. exploit: Task allocation for multi-robot foraging. Preprint. 2009. Available online http://www.princeton.edu/naomi/publications.html.
• [2] R. P. Bonasso, D. Kortenkamo, D. P. Miller and M. Slack: Experiences with an architecture for intelligent, reactive agents. In M. WOOLDRIDGE, J.P. MULLER and M. TAMBE eds. Intelligent Agents II. Lecture Notes in Articial Intellignce 1037 New York, Springer-Verlag, 1996, 187-202.
• [3] R. A. Brooks: Intelligence without representation. Artificial Intelligence, 47(1-3), (1991), 139-159.
• [4] W. Burgard, M. Moors, D. Fox, R. Simmons and S. Thrun: Collaborative multi-robot exploration. Proc. IEEE Int. Conf. on Robotics and Automation, San Francisco, CA, (2000), 476-481.
• [5] C. Candea, H. Hu, L. Iocchi, D. Nardi and M. Piaggio: Coordination in Multi-Agent RoboCup Teams. Robotics and Autonomous Systems, 36 (2001), 67-86.
• [6] X. Cheng, J. Shen, H. Liu and G. Gu: Multi-robot cooperation based on hierarchical reinforcement learning. Lecture Notes in Computer Science, 4489 2007, 90-97.
• [7] R. Fierro, A. Das, J. Spletzer, J. Esposito, V. Kumar, J. P. Ostrowski, G. Pappas, C. J. Taylor, Y. Hur, R. Alur, I. Lee, G. Grudic and J Southall: A framework and architecture for multi-robot coordination. International J. of Robotics Research, 21(10-11), (2002), 977-995.
• [8] B. P. Gerkey and M. J. Mataric: Sold!: Auction methods for multi-robot coordination. IEEE Trans. on Robotics and Automation, 18(5), (2002), 758-768.
• [9] R. Ghrist and S. M. Lavalle: Nonpositive curvature and pareto-optimal coordination of robots. SIAM J. of Control and Optimization, 45(5), (2006), 1697-1713.
• [10] I. Harmati and K. Skrzypczyk: Robot team coordination for target tracking using fuzzy logic controller in game theoretic framework. J. of Robotics and Autonomous Systems, 57(1), (2009), 75-86.
• [11] J. Jones and M. Mataric: Adaptive division of labor in large-scale minimalist multi-robot systems. Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, Las Vegas, (2003), 1969-1974.
• [12] N. Kalra and A. Martinoli: Comparative study of market-based and threshold-based task allocation. Distributed Autonomous Robotic Systems, 7 (2006), 91-101.
• [13] G. A. Kaminka, D. Erusalimchik and S. Kraus: Adaptive multi-robot coordination: A Game-Theoretic perspective. Proc. of IEEE Int. Conf. on Robotics and Automation, Anchorage, Alaska, USA, (2010), 328-334.
• [14] M. Klusch and A. Gerber: Dynamic coalition formation among rational agents. IEEE Intelligent Systems, 17(3), (2002), 42-47.
• [15] J. K. Kok and M. T. J. Spaan and N. Vlassis: Non-communicative multi-robot coordination in dynamic environments. Robotics and Autonomous Systems, 50(2-3), (2005), 99-114. [
• [16] K. Kosuge, Y. Hirata, H. Asama, H. Kaetsu, and K. Kawabata: Motion control of multiple autonomous mobile robots handling a large object in coordination. Proc. IEEE Int. Conf. on Robotics and Automation, Detroit, MI, (2000), 2666-2673.
• [17] S. M. Lavalle and S. A. Hutchinson: Game theory as a unifying structure for a variety of robot tasks. Proc. IEEE Int. Symp. on Intelligent Control, (1993), 429-434.
• [18] Y. Li and X. Chen: Modeling and simulation of swarms for collecting objects. Robotica, 00 (2005), 1-10.
• [19] J. Lawton, B. Young and R. Beard: A decentralized approach to elementary formation maneuvers. Proc. IEEE Int. Conf. on Robotics and Automation, San Francisco, CA, (2000), 2728-2733.
• [20] Y. Meng: Multi-robot searching using Game-Theory based approach. Int. J. of Advanced Robotic Systems, 5(4), (2008), 341-350.
• [21] D. P. Straffin: Game Theory and Strategy. The Mathematical Association of America. 1993.
• [22] I. Rekleitisy, V. Lee-Shuey, A. P. New and H. Choset: Limited communication, Multi-Robot Team based coverage. Proc. of Int. Conf. on Robotics and Automation, New Orleans, LA, (2004), 3463-3468.
• [23] Y. Shoham and K. L. Brown: Multiagent systems: Algorithmic, Game- Theoretic, and logical foundations. Cambridge University Press, NY, USA, 2009. ISBN: 978-0-521-89943-7.
• [24] K. Skrzypczyk: On multi agent coordination in the presence of incomplete information. Proc. Int. Conf. on Artificial Intelligence and Soft Computing, Zakopane, Poland, (2008), 1254-1256.
• [25] M. Song, G. Gu, R. Zhang and X. Wang: A method of multi-robotformation with the least total cost. Int. J. of Informationand System Science, 1(3-4), (2005), 364-371.
• [26] P. Stone and M. Veloso: Multiagent systems: A survey from the machine learning perspective. Technical report, CMU-CS-97-193, School of Computer Science, Carnegie Mellon University, 1997.
• [27] T. Sugar and V. Kumar: Control and coordination ofmultiple mobile robots in manipulation and material handling tasks. In P. CORKE and J. TREVELYAN eds. Experimental Robotics VI: Lecture Notes in Control and Information Sciences, 250 15-24, Berlin: Springer-Verlag, 2000.
• [28] K. Sycara: 1998: Multiagent systems. Artificial Intelligence Magazine, 19(2), (1998), 79-92.
• [29] R. J. Wilson: Introduction to Graph Theory. 3rd ed., New York: Longman Scientific & Technical, 1987. ISBN 0-582-44685-6.
• [30] K. J. Winkfeld and G. Zlotkin: Multiagent negotiation under time constraints. Artificial Intelligence, 75 (1995), 297-345.
• [31] M. Wooldridge and N. Jennings: Intelligent agents: Theory and practice. Knowledge Engineering Review, 10(2), (1995), 115-152.
• [32] M. Wooldridge: An Introduction to Multiagent Systems. Johnn Wiley & Sons Ltd, UK, 2009, ISBN:978-0-470-51946-2.
• [33] D. Vail and M. Veloso: Dynamic multi-robot coordination. In A. SCHULTZ, L. PARKER and F. SCHNEIDER, eds. Multi-Robot Systems: From Swarms to Intelligent Automata, 2 Kluwer Academic Publishers, the Netherlands, 2003, 87-98.
• [34] M. Mellado and K. Skrzypczyk: Information fusion in Multi-Agent System based on reliability criterion. In A. NAWRAT and Z. KUS eds. Vision Based Systems for UAV Applications. Series: Studies in Computational Intelligence, Springer, 481 2013, 207-217, ISBN: 978-3-319-00368-9.