Answers.Body: <p>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 &amp; 6 of <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Russell &amp; Norvig's</a> section on search.</p>
  
  <p>To do this, you can't just change your heuristic, instead you need to reframe your problem:</p>
  
  <ul>
  <li><p>Instead of states in your search being locations, they should be <em>tours</em>. Each state is a list of all the places you need to visit, <em>in a specific order</em>.</p></li>
  <li><p>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.</p></li>
  <li><p>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. </p></li>
  <li><p>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 <a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree" rel="nofollow noreferrer">minimum spanning trees</a> are effective for this domain. </p></li>
  </ul>
  
  <p>The real answer though, is to try a technique that is meant for this kind of problem, like a <a href="https://en.wikipedia.org/wiki/Local_search_(optimization)" rel="nofollow noreferrer">local search algorithm</a>. 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-19T16:52:46.447Z
Answers.LastActivityDate: 2018-09-19T16:52:46.447Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>Genetic algorithms are giving promising results for problems with multiple objectives[goals].</p>
  
  <p><a href="http://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf" rel="nofollow noreferrer">http://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf</a>
  the above paper will give best algorithm for multi objectives</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-19T22:33:38.960Z
Answers.Text: 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.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-19T22:16:15.720Z
Answers.LastActivityDate: 2018-09-19T22:16:15.720Z
Answers.UserDisplayName: Sreedhar Veluri
Answers.Body: <p>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:
  <a href="https://stackoverflow.com/questions/4453477/using-a-to-solve-travelling-salesman">https://stackoverflow.com/questions/4453477/using-a-to-solve-travelling-salesman</a>
  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. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-07T21:59:25.943Z
Answers.LastActivityDate: 2019-10-07T21:59:25.943Z
Answers.UserDisplayName: kartthikbala2205
Body: <p>Usually, using the <a href="https://en.wikipedia.org/wiki/Taxicab_geometry" rel="nofollow noreferrer">Manhattan distance</a> 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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-19T14:46:21.853Z
Comments.Text: 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](https://ai.stackexchange.com/a/8045/2444) seems to assume something different. So, this shows that it's very important that we ask for clarification.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-19T14:57:56.447Z
Comments.Text: By the way, [here](https://ai.stackexchange.com/q/2342/2444) is a related question.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-09-19T08:45:24.923Z
Comments.Text: Is your goal to visit *all* of the multiple targets, or is the goal simply to reach *at least one* of the multiple targets?
Comments.UserDisplayName: Dennis Soemers
Tags: <search><heuristics><a-star>
Title: What heuristic to use when doing A* search with multiple targets?
UserDisplayName: dragan
ThreadText: # What heuristic to use when doing A* search with multiple targets?
  
  (Asked by: username_0 on 2018-09-19)
  
  Usually, using the [Manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry) 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?
  
  **Tags:** search, heuristics, a-star
  
  > **Comments:**
  > **username_2**: Is your goal to visit *all* of the multiple targets, or is the goal simply to reach *at least one* of the multiple targets?  
  > **username_1**: 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, username_2 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](https://ai.stackexchange.com/a/8045/2444) seems to assume something different. So, this shows that it's very important that we ask for clarification.  
  > **username_1**: By the way, [here](https://ai.stackexchange.com/q/2342/2444) is a related question.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2018-09-19. Score: 2
  
  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](http://aima.cs.berkeley.edu/) 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](https://en.wikipedia.org/wiki/Minimum_spanning_tree) 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](https://en.wikipedia.org/wiki/Local_search_(optimization)). 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.
  
  
  ---
  
  ### Answer by username_4 on 2018-09-19. Score: 0
  
  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
  
  > **Comments:**
  > **username_3**: Welcome to AI.SE username_4! 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.  
  
  ---
  
  ### Answer by username_5 on 2019-10-07. Score: 0
  
  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.
  
  
  ---
  
  