Multiple Traveling Robot Problem: A Solution Based on Dynamic Task Selection and Robust Execution

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.