A Streamlined Heuristic for the Problem of Min-Time Coverage in Constricted Environments

摘要

The problem of min-time coverage in constricted environments concerns the employment of robotic fleets to support routine inspection and service operations within well-structured but constricted environments. In our previous work we have provided a detailed definition of this problem, specifying the objectives and the constraints involved, a Mixed Integer Programming (MIP) formulation for it, a formal analysis of its worst-case computational complexity, and additional structural properties of the optimal solutions that enable a partial relaxation of the original MIP formulation which preserves optimal performance. 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 the construction heuristic is polynomial with respect to the size of the problem-defining elements, its practical scalability has been limited by the requirement to formulate and solve a large number of linear programming formulations. In order to address this issue, this work presents a modified version of the heuristic that significantly reduces the computational times involved. Furthermore, we develop a local search method that further improves the solution obtained from the modified heuristic.Note to Practitioners—This paper concerns the application of the current and the emergent robotic technologies in the inspection and monitoring of remote and difficult-to access facilities, like underground utility networks and oil and gas pipeline networks. The constricted and remote nature of these environments necessitates the careful preservation of a wireless ad hoc communication network among the deployed robots and a command-&-control center that supervises the entire operation, and this need gives rise to some novel, very interesting and very challenging coordination and scheduling problems. We have undertaken the investigation of these problems in a recent series of papers, providing a systematic formal characterization of them, and some analytical results that have identified important underlying structure and have also led to the development of a pertinent heuristic approach. This work complements and extends those earlier developments by enhancing significantly the computational expediency of the aforementioned heuristic method, and further augmenting the resulting computational capability to a systematic search method that can iteratively improve any available initial solution.