A Strong Combinatorial Relaxation for the Problem of Min-Time Coverage in Constricted Environments

In a recent work, we introduced a new set of problems in the area of networked multiple mobile robotic systems that concern the time-optimal execution of certain coverage tasks taking place in constricted environments. That work provided the detailed problem definitions, positioned these problems in the context of the corresponding literature, formulated them as mixed integer programs (MIPs), and established their NP-hardness. This article introduces a strong combinatorial relaxation for these problems, and further establishes that the feasible solutions of these relaxations can be converted to feasible solutions for the original MIPs with equal or better objective values than the objective values of the converted solutions. The new results also enable the development of more efficient solution methods and heuristic approaches for the considered problems; this potential is addressed in the last part of this article.