Usually, using the Manhattan distance as a heuristic function 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?
$\begingroup$
$\endgroup$
3
-
4$\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 ♦Commented Sep 19, 2018 at 8:45
-
$\begingroup$ For readers, please, next time you see a question that needs to be clarified, you should ask for clarification before providing an answer. Meanwhile, you should flag (or vote) the question to be closed. In this case, Dennis was doing the right thing. It's not completely whether the problem is to find the shortest path to multiple targets or to one of the targets. Another answer seems to assume something different. So, this shows that it's very important that we ask for clarification. $\endgroup$– nbroCommented Nov 19, 2020 at 14:46
-
$\begingroup$ By the way, here is a related question. $\endgroup$– nbroCommented Nov 19, 2020 at 14:57
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
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.
answered Sep 19, 2018 at 16:52
$\begingroup$
$\endgroup$
1
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
-
$\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$ Commented Sep 19, 2018 at 22:33
$\begingroup$
$\endgroup$
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.
