The problem of multi-goal path planning was introduced in an ICRA paper in the year 2011:
“Multi-goal planning is a task which arises in many robotics applications. It combines the challenging requirements of planning feasible point-to-point trajectories in obstacle-filled — and possibly high-dimensional -- state spaces with the complexity of combinatorial optimization.” Brendan Englot: Multi-Goal Feasible Path Planning Using Ant Colony Optimization, 2011 (page 1)
The difficulty of solving this complex task is described at page 3:
“constructing a graph which describes feasible paths over all goal-to-goal pairings is a costly task. [..] In obstacle-filled and high-dimensional configuration spaces with many goals, joining all goals into a single connected component may be very costly, and especially challenging if we are undertaking a kinodynamic planning task.” (page 3)
Usually, using the Manhattan Distance is enough when we do an A* search with one target. However, it seems like for multiple goals, this is not the most useful way. Which heuristic do we have to use when we have multiple targets?