A streamlined heuristic for the problem of Min-Time Coverage in Constricted Environments (Extended Abstract)

The problem of min-time coverage in constricted environments concerns the employment of networked robotic fleets for the support of routine inspection and service operations taking place in well-structured but constricted environments. In a series of previous works, we have provided a detailed definition of this problem, a Mixed Integer Programming (MIP) formulation for it, a formal analysis of its worst-case computational complexity, additional structural results for its optimal solutions that also enable the solution of the problem through a partial relaxation of the original MIP formulation, and we have further employed these structural results towards the development of a construction heuristic for this problem. But while the worst-case computational complexity of this heuristic is polynomial with respect to the size of the problem-defining elements, its practical scalability has been challenged by the need to solve a large (super-linear) number of linear programming formulations. This work introduces a modified version of the heuristic that has reduced very drastically the involved computational times.