2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Is your goal to visit all of the multiple targets, or is the goal simply to reach at least one of the multiple targets? $\endgroup$ – Dennis Soemers Sep 19 '18 at 8:45
  • 1
    $\begingroup$ An extensive list of possible strategies is given in the literature under the searchterm “multigoal pathplanning”. But I would guess, that this would be to easy. To research the topic in detail, it would be nice if some kind of bug, failed planning module or a misguided robot is available which can be fixed, solved and interpret in detail. So my request is to generate a non working system first or to search for a challenge in which the algorithm failed. $\endgroup$ – Manuel Rodriguez Sep 19 '18 at 20:28
  • $\begingroup$ Thanks for this question! (I'm grappling with how to balance multiple goals in a single agent.) $\endgroup$ – DukeZhou Sep 19 '18 at 20:46
  • $\begingroup$ I've add some context information to introduce the problem. $\endgroup$ – Manuel Rodriguez Sep 20 '18 at 13:20
2
$\begingroup$

If by "visit multiple targets", you mean "visit several points in the fastest order", you are no longer in a simple path-finding-style search problem, but instead in an optimization problem. This is roughly the difference between chapters 3 & 6 of Russell & Norvig's section on search.

To do this, you can't just change your heuristic, instead you need to reframe your problem:

  • Instead of states in your search being locations, they should be tours. Each state is a list of all the places you need to visit, in a specific order.

  • Instead of actions being movements from one location to another, they need to be transformations from one tour to another. For example, if you swap the order that you visit two adjacent locations, then you'll get a different tour. This gives you a way to "move" between tours.

  • A solution means visiting all the locations as fast as possible. If you know how to get between two locations, just store the distances, and then sum all the distances together to get the cost of a tour. If you don't know, you can just run A* from each place to each other place once, and then cache the distances afterwards.

  • A heuristic will depend on your domain. A reasonable start might be to assume that you can visit each location from the nearest other location you've already visited. Generally, heurstics based on the idea of minimum spanning trees are effective for this domain.

The real answer though, is to try a technique that is meant for this kind of problem, like a local search algorithm. Notice that if we know the cost of moving between any two points, we can just adopt a greedy approach: make the move that improves things the most each time. This is often faster than waiting for A* in practice if you just want a good solution, but it doesn't need to be the very best one.

$\endgroup$
  • $\begingroup$ Useful. Thanks for mentioning greedy. Sometimes good enough is good enough! $\endgroup$ – DukeZhou Sep 19 '18 at 20:48
0
$\begingroup$

Genetic algorithms are giving promising results for problems with multiple objectives[goals].

http://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf the above paper will give best algorithm for multi objectives

$\endgroup$
  • $\begingroup$ Welcome to AI.SE Sreedhar! While NSGA-II is a useful algorithm for multi-objective optimization, this question describes multi-goal path planning, which is a different topic. Multi-goal path planning has only one objective (minimize distance), so NSGA-II is not a suitable technique. $\endgroup$ – John Doucette Sep 19 '18 at 22:33
0
$\begingroup$

I see that the objective is to achieve multiple goals using A* algorithm. So if your problem is more like a Traveling Salesman Problem, which is what it kind of sounds like, you can refer to this post: https://stackoverflow.com/questions/4453477/using-a-to-solve-travelling-salesman The problem can be converted to a graph search problem, and could utilize Minimum Spanning Tree. A-star can be used to compute edge weight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.