A Multi-Goal Path Planning for Goal Regions in the Polygonal Domain.
Jan Faigl, Vojtěch Vonásek, Libor Přeučil · 2011
This paper concerns a variant of the multi-goal path planning problem in which goals may be polygonal regions. The problem is to find a closed shortest path in a polygonal map such that all goals are visited. The proposed solution is based on a self-organizing map algorithm for the traveling salesman problem, which is extended to the polygonal goals. Neurons’ weights are considered as nodes inside the polygonal domain and connected nodes represent a path that evolves according to the proposed adaptation rules. Performance of the rules is evaluated in a set of problems including an instance of the watchman route problem with restricted visibility range. Regarding the experimental results the proposed algorithm provides flexible approach to solve various NP-hard routing problems in polygonal maps.