Multiple Traveling Robot Problem: A Solution Based on Dynamic Task Selection and Robust Execution
- 27 March 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ASME Transactions on Mechatronics
- Vol. 14 (2) , 198-206
Abstract
The multiple traveling robot problem (MTRP), the real-world version of the well-known NP-hard multiple traveling salesman problem (MTSP), asks for finding routes of robots to visit a set of targets. Various objectives may be defined for this problem (e.g., minimization of total path length, time, etc.). The overall solution quality is dependent on both the quality of the solution constructed by the paths of robots and the efficient allocation of the targets to robots. Unpredictability of the exact processing times of tasks, unstable cost values during execution, and inconsistencies due to uncertain information further complicate MTRP. This paper presents a multirobot cooperation framework employing a dynamic task selection scheme to solve MTRP. The proposed framework carries out an incremental task allocation method that dynamically adapts to current conditions of the environment, thus handling diverse contingencies. Globally efficient solutions are obtained through mechanisms that result in the allocation of the most suitable tasks from dynamically generated priority-based rough schedules. Since the presented approach is for real-world task execution, computational requirements are kept at a minimum, and the framework is designed to be applicable on real robots even with limited capabilities. The efficiency and the robustness of the proposed scheme is evaluated through experiments both in simulations and on real robots.Keywords
This publication has 11 references indexed in Scilit:
- Naval Mine Countermeasure MissionsIEEE Robotics & Automation Magazine, 2008
- Multirobot-Based Nanoassembly Planning with Automated Path GenerationIEEE/ASME Transactions on Mechatronics, 2007
- Coordinated multi-robot explorationIEEE Transactions on Robotics, 2005
- Simple auctions with performance guarantees for multi-robot task allocation2005
- Robot exploration with combinatorial auctions2004
- A distributed tasks allocation scheme in multi-UAV context2004
- Opportunistic optimization for market-based multirobot control2003
- TSPLIB—A Traveling Salesman Problem LibraryINFORMS Journal on Computing, 1991
- The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem SolverIEEE Transactions on Computers, 1980
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957