Some structural results for the problem of Min-Time Coverage in Constricted Environments

Abstract

In a recent work, we introduced a new set of problems in the area of networked robotic systems that concern the time-optimal execution of certain coverage tasks taking place in constricted environments. That work provided the detailed problem definitions, a complete representation of these problems in terms of Mathematical Programming (MP) formulations, and a formal analysis of their worst-case computational complexity. The current work establishes some structural results for the considered problems that are useful for the strengthening of the aforementioned MIP formulations and for the further development of pertinent heuristic solution methods for these problems. We demonstrate the first possibility in this paper, and we defer the second one to future work.