Matthew Hoeing
ABSTRACT
Over the past few years, swarm based systems have emerged as an attractive paradigm for building large scale distributed systems composed of numerous independent but coordinating units. In our previous work, we have developed a protoype system called COMSTAR (Cooperative Multi-agent Systems for automatic TArget Recognition) using a swarm of unmanned aerial vehicles(UAVs) that is capable of identifying targets in software simulations of reconnaissance operations. Experimental results from the simulations of the COMSTAR system show that task selection among the UAVs is a crucial operation that determines the overall efficiency of the system. Previously described techniques for task selection among swarm units use a centralized server such as a ground control station to coordinate the activities of the swarm units. However, such systems are not truly distributed since the behavior of the swarm units is predominantly directed by the centralized server's task allocation algorithm. In this paper we focus on the problem of distributed task selection in a swarmed system where each swarm unit decides on the tasks it will execute by sharing information and coordinating its actions with other swarm units without the intervention of a centralized ground control station supervising its activities. Specifically, we build our task selection algorithm on an auction-based algorithm for task selection in robotic swarms described by Kalra et al. We report experimental results in a simulated environment with 18 robots and 20 tasks and compare the performance of our auction-based algorithm with other heuristic-based task selection strategies in multi-agent swarms. Our simulation results show that the auction-based algorithm improves the task completion times by 30-60% and reduces the communication overhead by as much as 90% with respect to other heuristic-based strategies maintaining similar performance in load balancing.
- W. Agassounon, A. Martinoli, K. Easton, "Macroscopic Modeling of Aggregation Experiments using Embodied Agents in Teams of Constant and Time-Varying Sizes," Autonomous Robots, vol. 17, no. 2-3, 2004, pp. 163--192. Google Scholar
Digital Library
- R. Alami, S. Fleury, M. Herrb, F. Ingrand, and F. Robert, "Multi-robot cooperation in the MARTHA project," IEEE Robotics and Automation, vol. 5, no. 1, 1998, pp. 36--47.Google ScholarCross Ref
- O. Babaoglu, H. Meling, A. Montresor, "Anthill: A Framework for the Development of Agent-Based Peer-to-Peer Systems," Proc. of the 22th Intl. Conf. on Distributed Computing Systems, Vienna, Austria, July 2002. Google ScholarDigital Library
- S. Beshers and J. Fewell. Models of Division of Labor in Social Insects. Annual Review of Entomology, vol. 46, 2001, pp. 413--440.Google ScholarCross Ref
- E. Bonabeau, M. Dorigo and G. Theraulaz, "Swarm Intelligence: From Natural to Artificial Systems," Oxford University Press, 1999. Google ScholarDigital Library
- V. A. Cicirello and S. F. Smith. Wasp-like Agents for Distributed Factory Coordination. Journal of Autonomous Agents and Multi-Agent Systems, vol. 8, no. 3, 2004, pp. 237--266. Google ScholarDigital Library
- P. Dasgupta, S. O'Hara, P. Petrov, "A Multi-agent UAV Swarm for Automatic Target Recognition," Lecture Notes in Computer Science, vol. 3890, (Proc. of the 1st Intl. Workshop on Defense Applications of Multi-agent Systems (DAMAS)), 2005, pp. 80--91. Google ScholarDigital Library
- M. B. Dias, R. M. Zlot, N. Kalra, and A. Stentz, "Market-Based Multirobot Coordination: A Survey and Analysis," Tech. report CMU-RI-TR-05-13, Robotics Institute, Carnegie Mellon University, 2005.Google Scholar
- S. Edwards, "Swarming on the Battlefield: Past, present and future," RAND National Security Research Division Report, 2000.Google Scholar
- F. Gaudiano, E. Bonabeau, and B. Shargel, "Evolving behaviors for a swarm of unmanned air vehicles," Proc. of the 2005 IEEE Swarm Intelligence Symposium, Pasadena, CA, 2005.Google Scholar
- B. Gerkey, "On multi-robot task allocation," Ph.D Thesis, Univ. of Southern California, 2003. Google ScholarDigital Library
- M. Hoeing, P. Dasgupta, "Dynamic Pricing Algorithms for Market based Distributed Task Selection in Multi-agent Swarms," Proc. IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT'06), Hong Kong, 2006, pp. 113--116. Google ScholarDigital Library
- M. Jager and B. Nebel, "Dynamic Decentralized Area Partitioning for Cooperating Cleaning Robots," Proceedings of the 2002 IEEE International Conference on Robotics and Automation, Washington, DC, USA, 2002, pp. 3577--3582.Google Scholar
- M. Jelasity and O. Babaoglu, "T-Man: Gossip-based overlay topology management," In Proceedings of the 3rd International Workshop on Engineering Self-Organising Applications (ESOA'05), Utrecht, July 2005. Google ScholarDigital Library
- N. Kalra and A. Martinoli, "A Comparative Study of Market-Based and Threshold-Based Task Allocation," Proc. 8th Intl. Symp. on Distributed Autonomous Robotic Systems (DARS'06), Minneapolis, MN, 2006.Google ScholarCross Ref
- T. Lemaire, R. Alami, and S. Lacroix, "A distributed tasks allocation scheme in multi-uav context," IEEE International Conference on Robotics and Automation, New Orleans, LA (USA), April 2004.Google Scholar
- L. Li, A. Martinoli, Y. Abu-Mostafa, "Learning and Measuring Specialization in Collaborative Swarm Systems," Adaptive Behavior, Adaptive Behavior, Vol. 12, No. 3--4, 2004, pp. 199--212. Google ScholarDigital Library
- R. Mailler, V. Lesser, B. Horling, "Cooperative Negotiation for soft real-time distributed resource allocation," Proc. of 2nd Intl. Conf. on Autonomous Agents and Multi-Agent Systems, 2003, pp. 576--583. Google ScholarDigital Library
- R. Mailler, V. Lesser, "A cooperative mediation based protocol for dynamic, distributed resource allocation," IEEE Trans. on System, Man, Cybernetics, Part C. Google ScholarDigital Library
- D. Miller, P. Dasgupta, T. Judkins, "Distributed task selection in multi-agent based swarms using heuristic strategies," Lecture Notes in Computer Science, vol. 4433, (Proc. 2nd Swarm Robotics Workshop, Rome, Italy), 2006, pp. 158--172. Google ScholarDigital Library
- P. Modi, W. Shen, M. Tambe, and M. Yokoo, "Adopt: asynchronous distributed constraint optimization with quality guarantees," Artificial Intelligence, vol. 161, no. (1--2), 2005, pp. 149--180. Google ScholarDigital Library
- R. Montemanni, L. Gambardella, A. Rizzoli, A. Donati, "Ant Colony System for a Dynamic Vehicle Routing Problem," J. Combinatorial Optimization, vol. 10, no. 4, 2005, pp. 327--343.Google ScholarCross Ref
- C. Oritz, R. Vincent and B. Morriset, "Task Inference and Distributed Task Management in the Centibots Robotic System," Proc. of the 4th Joint International Conference on Autonomous Agents and Multi-Agent Systems, Utrecht, The Netherlands, 2005, pp. 870--877. Google ScholarDigital Library
- L. Parker, Distributed Algorithms for Multi-Robot Observation of Multiple Moving Targets, Autonomous Robots, vol. 12, no. 3, 2002, pp. 231--255. Google ScholarDigital Library
- J. Sauter, R. Matthews, H. Parunak, and S. Brueckner, "Performance of Digital Pheromones for Swarming Vehicle Control," Proc. 4th Intl. Conf. on Autonomous Agents and Multi-Agent Systems, Utrecht, The Netherlands, 2005, pp. 903--910. Google ScholarDigital Library
- O. Shehory, S. Kraus, "Methods for task allocation via agent coalition formation," Artif. Intell., vol. 101 no. 1--2, 1998, pp. 165--200. Google ScholarDigital Library
- R. Smith, "The contract net protocol: High-level communication and control in a distributed problem {see pdf for details}. Google ScholarDigital Library
Index Terms
- Auction-based multi-robot task allocation in COMSTAR
Recommendations
Distributed task selection in multi-agent based swarms using heuristic strategies
SAB'06: Proceedings of the 2nd international conference on Swarm roboticsSwarm-based systems have emerged as an attractive paradigm for implementing distributed autonomous systems for various applications in commercial, military and business domains. One of the major operations in a swarm-based system is to ensure that the ...
Optimal bid valuation using path finding for multi-robot task allocation
When multiple robots are supposed to operate together, coordination and communication issues arise. "Which robot should execute which task?" is the key question of the multi-robot task allocation problem. Properly allocating tasks among robots so as to ...
An auction-based rescue task allocation approach for heterogeneous multi-robot system
AbstractNowadays, robots are faced with real-time, dynamic, complex and confrontational working environment. It is significant to analyze task allocation in multi-robot systems. In this paper, a dynamic auction approach for differentiated tasks under cost ...
Comments