Weitere Kapitel dieses Buchs durch Wischen aufrufen
Multi-robot systems (MRSss) face several challenges, but the most typical problem is the multi-robot tasks allocation (MRTA). It consists in finding the efficient allocation mechanism in order to assign different tasks to the set of available robots. Toward this objective, robots will work as cooperative agents. MRTA aims at ensuring an efficient execution of tasks under consideration and thus minimizing the overall system cost. Various research works have solved the MRTA problem using the multiple traveling salesman problem (MTSP) formulation. In this context, an overview on MRTA and MTSP is given in this chapter. Furthermore, a summary of the related works is presented.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Diego, Pizzocaro and A. Preece. 2009. Towards a taxonomy of task allocation in sensor networks. In Proceedings of the 28th IEEE international conference on Computer Communications Workshops (INFOCOM), 413–414.
Nidhi, Kalra, Robert Zlot, M. Bernardine Dias, and Anthony Stentz. 2005. Market-based multirobot coordination: A comprehensive survey and analysis. Technical report, CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST.
Dias Bernardine, M., Robert Zlot, Nidhi Kalra, and Anthony Stentz. 2006. Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE 94 (7): 1257–1270. CrossRef
Brian, P.G., and M.J. Matarić. 2004. A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research 23 (9): 939–954. CrossRef
Sylvia C. Botelho and Rachid Alami. 1999. M+: a scheme for multi-robot cooperation through negotiated task allocation and achievement. In IEEE International Conference on Robotics and Automation, Proceedings, vol. 2, 1234–1239. IEEE.
Gerkey, B.P., and M.J. Mataric. 2002. Sold!: Auction methods for multirobot coordination. IEEE transactions on robotics and automation 18 (5): 758–768. CrossRef
Fang, Tang and Spondon Saha. 2008. An anytime winner determination algorithm for time-extended multi-robot task allocation. In ARCS, 123–130.
Zlot, Robert, and Anthony Stentz. 2006. Market-based multirobot coordination for complex tasks. The International Journal of Robotics Research 25 (1): 73–101. CrossRef
Barry L, Brumitt and Anthony Stentz. 1998. Grammps: A generalized mission planner for multiple mobile robots in unstructured environments. In IEEE International Conference on Robotics and Automation, Proceedings., vol. 2, 1564–1571. IEEE.
Philippe, Caloud, Wonyun Choi, J.-C. Latombe, Claude Le Pape, and Mark Yim. 1990. Indoor automation with many mobile robots. In IEEE International Workshop on Intelligent Robots and Systems’ 90. ’Towards a New Frontier of Applications’, Proceedings. IROS’90., 67–72. IEEE.
Parker, Lyne E. 1998. Alliance: An architecture for fault tolerant multirobot cooperation. IEEE transactions on robotics and automation 14 (2): 220–240. CrossRef
Brian, Barry, and Werger and M.J. Matarić. 2000. Broadcast of local eligibility for multi-target observation. Distributed autonomous robotic systems 4, 347–356. Berlin: Springer.
Sanem, Sariel and Tucker R. Balch. 2006. Efficient bids on task allocation for multi-robot exploration. In FLAIRS Conference, 116–121.
Sven Koenig, Craig A. Tovey, Xiaoming Zheng, and Ilgaz Sungur. 2007. Sequential bundle-bid single-sale auction algorithms for decentralized control. In IJCAI, 1359–1365.
Liu, Lin and Zhiqiang Zheng. 2005. Combinatorial bids based multi-robot task allocation method. In Proceedings of the 2005 IEEE International Conference on Robotics and Automation, ICRA, 1145–1150. IEEE.
Antidio, Viguria, Ivan Maza, and Anibal Ollero. 2008. S+ t: An algorithm for distributed multirobot task allocation based on services for improving robot cooperation. In IEEE International Conference on Robotics and Automation ICRA, 3163–3168. IEEE.
Ahmed M. Elmogy, Alaa M. Khamis, and Fakhri O. Karray. 2009. Dynamic complex task allocation in multisensor surveillance systems. In 2009 3rd International Conference on Signals, Circuits and Systems (SCS), 1–6. IEEE.
Ahmed M. Elmogy, Alaa M. Khamis, and Fakhri O. Karray. 2009. Market-based dynamic task allocation in mobile surveillance systems. In 2009 IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR), 1–6. IEEE.
Khamis, Alaa M., Ahmed M. Elmogy, and Fakhri O. Karray. 2011. Complex task allocation in mobile surveillance systems. Journal of Intelligent and Robotic Systems 64 (1): 33–55. CrossRef
Yan, Zhi, Nicolas Jouandeau, and Arab Ali Cherif. 2013. A survey and analysis of multi-robot coordination. International Journal of Advanced Robotic Systems 10 (12): 399. CrossRef
Michael M. Zavlanos, Leonid Spesivtsev, and George J. Pappas. 2008. A distributed auction algorithm for the assignment problem. In 47th IEEE Conference on Decision and Control CDC, 1212–1217. IEEE.
Nathan, Michael, Michael M. Zavlanos, Vijay Kumar, and George J. Pappas. 2008. Distributed multi-robot task assignment and formation control. In IEEE International Conference on Robotics and Automation ICRA, 128–133. IEEE.
Antidio, Viguria, and Ayanna M. Howard. 2009. An integrated approach for achieving multirobot task formations. IEEE/ASME Transactions on Mechatronics 14 (2): 176–186. CrossRef
Lingzhi, Luo, Nilanjan Chakraborty, and Katia Sycara. 2011. Multi-robot assignment algorithm for tasks with set precedence constraints. In 2011 IEEE International Conference on Robotics and Automation (ICRA), 2526–2533. IEEE.
Lingzhi, Luo, Nilanjan Chakraborty, and Katia Sycara. 2013. Distributed algorithm design for multi-robot task assignment with deadlines for tasks. In 2013 IEEE International Conference on Robotics and Automation (ICRA), 3007–3013. IEEE.
Charles, Pippin, Henrik Christensen, and Lora Weiss. 2013. Performance based task assignment in multi-robot patrolling. In Proceedings of the 28th annual ACM symposium on applied computing, 70–76. ACM.
Stefano, Giordani, Marin Lujak, and Francesco Martinelli. 2010. A distributed algorithm for the multi-robot task allocation problem. International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, 721–730. Berlin: Springer.
Holland, John H. 1975. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Michigan: U Michigan Press. MATH
András, Király, and János Abonyi. 2011. Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. Intelligent Computational Optimization in Engineering, 241–269. Berlin: Springer.
Jun, Li, Qirui Sun, MengChu Zhou, and Xianzhong Dai. 2013. A new multiple traveling salesman problem and its genetic algorithm-based solution. In 2013 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 627–632. IEEE.
Harpreet, Singh, and Ravreet Kaur. 2013. Resolving multiple traveling salesman problem using genetic algorithms. International Journal of Computer Science Engineering 3 (2): 209–212.
Shalini, Singh, and Ejaz Aslam Lodhi. 2014. Comparison study of multiple traveling salesmen problem using genetic algorithm. International Journal of Computer Science and Network Security (IJCSNS) 14 (7): 107–110.
Falkenauer, Emanuel. 1992. The grouping genetic algorithms-widening the scope of the gas. Belgian Journal of Operations Research, Statistics and Computer Science 33 (1): 79–102. MATH
Evelyn, C. 2007. Brown, Cliff T Ragsdale, and Arthur E Carter. A grouping genetic algorithm for the multiple traveling salesperson problem. International Journal of Information Technology and Decision Making 6 (02): 333–347. CrossRef
Alok, Singh, and Anurag Singh Baghel. 2009. A new grouping genetic algorithm approach to the multiple traveling salesperson problem. Soft Computing-A Fusion of Foundations, Methodologies and Applications 13 (1): 95–101.
Imen Châari, Anis Koubaa, Hachemi Bennaceur, Sahar Trigui, and Khaled Al-Shalfan. 2012. Smartpath: A hybrid aco-ga algorithm for robot path planning. In 2012 IEEE Congress on Evolutionary Computation (CEC), 1–8. IEEE.
Châari, Imen, Anis Koubâa, Sahar Trigui, Hachemi Bennaceur, Adel Ammar, and Khaled Al-Shalfan. 2014. Smartpath: An efficient hybrid aco-ga algorithm for solving the global path planning problem of mobile robots. International Journal of Advanced Robotic Systems 11 (7): 94. CrossRef
Anis, Koubâa, Sahar Trigui, and Imen Châari. 2012. Indoor surveillance application using wireless robots and sensor networks: Coordination and path planning, 19–57. Mobile Ad Hoc Robots and Wireless Robotic Systems: Design and Implementation.
Weimin, Liu, Sujian Li, Fanggeng Zhao, and Aiyun Zheng. 2009. An ant colony optimization algorithm for the multiple traveling salesmen problem. In 4th IEEE Conference on Industrial Electronics and Applications ICIEA, 1533–1537. IEEE.
Yousefikhoshbakht, Majid, Farzad Didehvar, and Farhad Rahmati. 2013. Modification of the ant colony optimization for solving the multiple traveling salesman problem. Romanian Academy Section for Information Science and Technology 16 (1): 65–80.
Venkatesh, Pandiri, and Alok Singh. 2015. Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing 26: 74–89. CrossRef
Dervis, Karaboga. 2005. An idea based on honey bee swarm for numerical optimization. Technical report, Technical report-tr06, Erciyes University, Engineering Faculty, Computer Engineering Department.
Reza, Ali, and Mehrabian and Caro Lucas. 2006. A novel numerical optimization algorithm inspired from weed colonization. Ecological Informatics 1 (4): 355–366.
Elad, Kivelevitch, Kelly Cohen, and Manish Kumar. 2013. A market-based solution to the multiple traveling salesmen problem. Journal of Intelligent and Robotic Systems, 1–20.
Kaisa, Miettinen. 2012. Nonlinear multiobjective optimization, vol. 12. Berlin: Springer Science and Business Media. MATH
Bolaños, R., M. Echeverry, and J. Escobar. 2015. A multiobjective non-dominated sorting genetic algorithm (nsga-ii) for the multiple traveling salesman problem. Decision Science Letters 4 (4): 559–568. CrossRef
Zhenzhen, Xu, Yiping Li, and Xisheng Feng. 2008. Constrained multi-objective task assignment for uuvs using multiple ant colonies system. In ISECS International Colloquium on Computing, Communication, Control, and Management CCCM’08, vol. 1, 462–466. IEEE.
Elango, Murugappan, Subramanian Nachiappan, and Manoj Kumar Tiwari. 2011. Balancing task allocation in multi-robot systems using k-means clustering and auction based mechanisms. Expert Systems with Applications 38 (6): 6486–6491. CrossRef
John, Bradford Gregory, and Heap and Maurice Pagnucco. 2012. Repeated sequential auctions with dynamic task clusters. In AAA I: 19972002.
Thibaut, Lust, and Jacques Teghem. 2010. The multiobjective traveling salesman problem: A survey and a new approach, 119–141. Berlin: Springer. MATH
Ke, Liangjun, Qingfu Zhang, and Roberto Battiti. 2013. Moea/d-aco: A multiobjective evolutionary algorithm using decomposition and antcolony. IEEE Transactions on Cybernetics 43 (6): 1845–1859. CrossRef
Vui Ann, Shim, Kay Chen Tan, and Kok Kiong Tan. 2012. A hybrid estimation of distribution algorithm for solving the multi-objective multiple traveling salesman problem. In 2012 IEEE Congress on Evolutionary Computation (CEC), 1–8. IEEE.
Wei, Peng, Qingfu Zhang, and Hui Li. 2009. Comparison between moea/d and nsga-ii on the multi-objective travelling salesman problem. Multi-objective memetic algorithms, 309–324.
- General Background on Multi-robot Task Allocation
- Chapter 6
Neuer Inhalt/© ITandMEDIA