Traffic Scheduling of Networked Multiple Mobile Robot Systems in Constricted Environments

Abstract

We address some new traffic scheduling problems for multiple mobile robot systems (MMRS), where a fleet of robots must execute a set of inspection tasks in a constricted operational environment like an underground utility or pipeline network. During the execution of these tasks, the robots must maintain a multi-hop wireless communication network connecting them with each other and with a command-&-control center that supervises the entire operation – this class of MMRS is characterized as networked MMRS in the robotics community. Employing networked MMRS in constricted environments introduces new resource allocation structures and traffic dynamics that transcend the state of the art of the corresponding theory and challenge our current understandings and insights for these dynamics and their effective management. In a series of our previous works, we have provided a systematic introduction of the considered problem, a mixed integer programming (MIP) formulation for it, a formal analysis of its worst-case computational complexity, and additional structural results for its optimal solutions that also enable a partial relaxation of the original MIP formulation preserving optimal performance. In this work, we leverage these structural results to develop a powerful heuristic algorithm capable of efficiently solving larger problem instances that are not amenable to the previous methods. Numerical experiments demonstrate the effectiveness and computational efficiency of the heuristic algorithm.