A Multi-Robot Mission Planner by Means of Beam Search Approach and 2-Opt Local Search

Abstract

This paper deals with the optimisation of a multi-robot inspection mission in an industrial area. We aim to solve a specific combinatorial optimisation problem where a team of sensing mobile robots must gather several measurement tasks distributed over the state space. Based on previous work where a Hybrid Filtered Beam Search (HFBS) approach solves task assignment and planning for this specific problem, we focus on the planning aspect to improve the computed solution. Therefore, this planning problem is modeled as a one-depot multiple Travelling Salesman Problem (mTSP). As the performance of HFBS depends on the challenging selection of its suitable parameters, and considering the coupling between task assignment and task planning problems, we propose a local search algorithm that improves the solution and deals with the optimality issue.