0
$\begingroup$

So i am using A* path finding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of the must pass nodes, to make sure they always go to each of these. My method for deciding which order nodes come in for their individual run through the algorithm is to use a distance between the person on the graph and the remaining nodes, the smallest distance will be put through the algorithm first.

Here is a diagram of what this looks like: enter image description here

The person must visit the blue node last, which is why the distance hasn't been included for that node.

As you can see, the bottom right pink node is the first node to go through the algorithm since they have the smallest distance.

Here is where i come across a problem:

If the algorithm tries to find a path to this node on the bottom right, the person will actually travel across the edge with weight 1, since the distance between the node on the other side of the edge with the weight of 1, to the end node, is 6.25 (using a ruler by hand and making sure the diagram stays the same size on my screen at all times for all distances measured).

Would this not mean the person ends up travelling through all of the other must pass nodes on the graph before they even reach the first must pass node?

Is my criteria for picking the next node for the algorithm wrong?

What am i doing here that is wrong? Or is this a fault with A*?

Note: The weights on each edge are measured fairly accurately by hand with a ruler, so i doubt that is the issue.

EDIT:

The one question i need answered is this. What is the best way to decide which node to path find for first? I'm starting to doubt if Euclidean distance is the best choice here.

$\endgroup$
0
$\begingroup$

Let's start this off with a quick review of A*. A* is a pathfinding algorithm that builds on some of the benefits that greedy searches and dijkstra searches have. Make sure that your implementation correctly combines both basic heuristics A* uses:

  1. g(N) = the cost to get from the starting node to the next node N
  2. h(N) = the estimated cost to get to the goal from N

By expanding the nodes with the lowest g(N) + h(N) first, A* quickly converges on the most efficient path when some costs are unknown. It's great for any graph search and I've used it to implement backtrackers for constraint solving.


Now, our review's over. Let's get to your problem!

You're trying to have a character visit certain subgoal nodes on the graph and finish on the goal node. This is actually a variant of the famous "Travelling Salesperson Problem". It is an example of an NP-complete problem, which means that even A* isn't going to help you solve it quickly; you'll be doing a lot of backtracking or trial-by-error no matter what algorithm you use.

In order to adapt A* to this problem, you will need to rewrite the logic for exiting the search. Instead of checking if N_i == Blue_1, you need to check if {Blue_1, Pink_1, Pink_2, Pink_3} is a subset of the path.

Right now your calculation for h(N) is based on Euclidean distance from Blue. Not a bad start, but it's not as efficient as simply setting h(N) = 0 on this problem; dijkstra search is better than a too-greedy A*. Because you aren't actually aiming for the blue node, you have an 'inadmissable' h(N) so you'll miss the optimal path sometimes:

"If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal."

You can get an admissible heuristic by setting h(N) = the distance to the nearest sub-goal. Once all sub-goals are reached, set h(N) = the distance from the blue goal. This means that each node in the pathfinder needs additional metadata. Add a field to pathfinding nodes that tracks which goals have already been hit.

$\endgroup$
4
  • $\begingroup$ I have two follow up questions: -Firstly, i don't understand how this is a TSP, since TSP requires every node to be reached once, and the starting node twice. -Secondly, i never actually calculate the euclidean distance from blue. I calculate the euclidean distance between the current node, and the next potential pink nodes. The blue euclidean distance is only calculated when finding the best path between the last pink node and the blue node. $\endgroup$ – Adam Cole Jan 10 at 11:04
  • $\begingroup$ Also - stackoverflow.com/questions/222413/… if i look here, most people are recommending using Dijkstra's algorithm for each individual path then adding them together $\endgroup$ – Adam Cole Jan 10 at 11:10
  • $\begingroup$ @AdamCole It's a variant of TSP. You are effectively finding a path between 4 cities. Sorry for mistaking your h(N) heuristic. The way you described it was as a measurement between another node and the end node, which I understood to be blue. There's many ways to approach this since it is NP-complete. Using Dijkstra search to add paths between nodes is another effective approach; similar to setting h(N) = 0, but includes a preprocessing phase to simplify the graph. You'll find that g(N) and h(N) are closely related to dijkstra's and greedy search respectively, and A* is a hybrid. $\endgroup$ – user4293 Jan 10 at 18:30
  • $\begingroup$ (Forgive my ignorance) why are are suggesting to set h(n) to 0? Are there nor far more problems with Dijkstra's algorithm than there are with A*? Does using A* not just wield more accurate results? albeit with the odd problematic vertex as is seen in my example. It's worth noting that this is just a simple example I'm using to prove my algorithm to be the right choice before i embark on a bigger project that can have any random vertexes or edges. @user4293 $\endgroup$ – Adam Cole Jan 11 at 6:31

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.