Inspection planning in the polygonal domain by Self-Organizing Map

Inspection planning is a problem of finding a (closed) shortest path from which a robot “sees” the whole workspace. The problem is closely related to the Traveling Salesman Problem (TSP) if the discrete sensing is performed only at the finite number of sensing locations. For the continuous sensing, the problem can be formulated as the Watchman Route Problem (WRP), which is known to be NP-hard for the polygonal representation of the robot workspace. Although several Self-Organizing Map (SOM) approaches have been proposed for the TSP, they are strictly focused to the Euclidean TSP, which is not the case of the inspection path planning in the polygonal domain. In this paper, a novel SOM adaptation schema is proposed to address both variants of the inspection planning with discrete and continuous sensing in the polygonal domain. The schema is compared with the state of the art SOM schema for the TSP in a set of multi-goal path planning problems and WRPs. The proposed algorithms are less computationally intensive (in order of tens) and provide better or competitive solutions.

► Inspection planning problem in the polygonal domain is solved using self-organizing maps. ► The discrete and continuous sensing models are considered in proposed approaches. ► The problems are formulated as the traveling salesman and watchman route problems. ► Proposed approaches are compared with previous ones in a set of realistic problems.