Min-Time Coverage in Constricted Environments with Arbitrary Guidepath Networks

Abstract

In a recent research program, we have undertaken the investigation of robotic traffic management problems arising when a fleet of networked mobile robots is employed in the support of certain coverage tasks that take place in physically constricted environments. But our past investigation of these problems is restricted to the case where the guidepath networks supporting the robot traffic have a dendritic topology. In the current work, we extend the investigation of the considered problems to the case where the underlying guidepath networks have an arbitrary topology. We provide (i) detailed descriptions of the considered problems in this new operational setting, (ii) analytical characterizations of these problems that take the form of integer programming formulations, and (iii) strong combinatorial relaxations for the derived formulations that are applicable to larger problem instances. A numerical experiment presented in the last part of the manuscript demonstrates and assesses the efficacy and the tractability of the analytical developments. We also notice that the undertaken extension of the past results is a nontrivial task, for the reasons that are explained in the manuscript.<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup>This work was partially supported by NSF grant ECCS-1707695.