Sensing Locations Positioning for Multi-robot Inspection Planning

Abstract

Problems of cooperative multi-robot inspection and exploration play an important role in many practical applications. This paper presents an algorithm for inspection planning based on decomposition of the problem into two subproblems - art gallery problem (AGP) that finds guards (sensing locations) and multiple traveling salesmen problem (MTSP) that connects the found guards by routes. While standard approaches for art gallery problem try to minimize a number of guards, the proposed method is designed to optimise lengths found by a MTSP solver and therefore to minimise time needed by a team of robots to inspect the working environment. The proposed algorithm has been implemented and tested. Influence of the method to quality of the inspection planning solution and comparison with the randomized dual sampling schema are discussed