The multigoal path planning problem (MTP) “is to find a closed shortest path in a polygonal map such that all goals [, which are represented as convex polygons,] are visited.” The problem deals with motion planning, which has important applications in such fields as artificial intelligence, architectural design, and automated surgery. An example of a practical application is planning for a robotic arm with minimal execution time and better utilization of tools. This paper provides algorithms for a general variant of the MTP problem, which is very important in applied computer science.

Algorithms are known for restricted variants of the problem. For example, there is an O(n³) algorithm for the safari route problem, where the goals are attached to the boundary of a simple polygon, and the route entry to a convex goal is allowed. There is an O(n log n) algorithm for the zookeeper problem, where the route entry to the convex goal is not allowed.

In this paper, the authors “present a self-organizing map (SOM) based algorithm for the general variant of the MTP [problem].” SOM is a computational model where interconnected nodes can compute values from inputs fed through the network. The problem variant is general in the sense that the polygonal domain is not necessarily a simple polygon, the goals need not be attached to the boundary of the polygonal domain, and the polygonal goals may overlap each other.

The authors provide experimental results based on the proposed algorithms. Theoretically, “the solution quality is not guaranteed” due to the use of approximation, but I believe the algorithms and the supporting structures would prove to be useful in practical applications from an engineering point of view. I recommend this paper to readers interested in computational geometry and robotics.