Department of Industrial Engineering & Decision Analytics [Joint IEDA/ISOM] seminar - Min-Time Coverage in Constricted Environments with Networked Multiple Mobile Robotic Systems

We address some time-optimal coverage problems in the area of networked robotic systems, 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 problems is characterized as networked multiple mobile robotic systems (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. We provide a systematic introduction of the considered problems and formulate them as mixed integer programs (MIPs). Furthermore, we introduce a strong combinatorial relaxation that can significantly reduce the number of integer variables without compromising the correctness of the derived solutions with respect to the original formulation. Lastly, we 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 presented relaxation and heuristic algorithm.