profile pic

Precise Asteroid

Welcome to Amir's Blog 👋

A* Routing Algorithm

2020-05-25

Lately I decided taking on Udacity's C++ Nano Degree.

Being a product manager, a C++ course is not an obvious pick. However Udacity suggested I take it, before I take their autonomous driving course in order to sharpen the coding skills one needs in order to pass that path. On top of that the C++ Nano Degree deals with real world problems I run into on my daily work such as route calculation, traffic handling and on, so it was not a hard decision to make.

I also love coding so why not enjoy through the process of learning.

Strangly when honing my product management skills I usually pick items from both sides of the spectrum:

  • Deep technical - they help me build confidence with both developers and customers
  • Business and Strategy - because making progress is less important IMHO than the destination

I usually pass on tactics. kind of think that's not the biggest bang for the buck.

A*?

A* is considered an extention of Diejksra algorithm and is one of the most commonly used algorithms in the navigation space.

I got so proud when I ran my ever first route algorithm and got the following result

Successful Root

In the following section I will go through the main steps.

1. Calculate Start and End nodes

The inputs to the algorithm are two geolocations. The star and end points. The geolcoations are not necesseraly on the network graph and therefore we first search for the closest graph nodes to these points

Rational:
well at some point you need to join the network, and the shorten the better is a fine assumption.

Find Closest Nodes

2. Find Neighbords of Current node that have not been visited

For a given current note, find all nodes that have not been visited yet (by that very step) and that are directly connected with the current node

distance = std::sqrt(std::pow((x - other.x), 2) + std::pow((y - other.y), 2));

neighbors

H Value and G Value

G is the cost of the next move. In our case it is the distance from the current node to its neighbor

H is a huriestic function value of the cost from the neighbord to the end node. In this instance I chose H as the euclidean distance to the end node. Any admissable function will do though. Admissable function is one that does not overestimate the cost of reaching the goal.

G and H Values

Rational:
We then sum them both, and prefer to pick the one with the minimal (G+H) as the next move, since it represents a move that would minimize the cost function.

3. Final Steps

In every step, populate the OpenList with neigbors that have not been visited before. When doing so and for each candidate:

  • Sign visited = True
  • Calclate G,H

Then replace the current node with the one from the Open List with the smallest G+H value and start again.

Also maker super to tie both nodes thought the parent_node pointer, so you could assemeble the route when the goal is reached.

The caluculation finally stops when the end_node was selected as the current node. You can now go back by traversgin the route from the end_node to the start_node, through the node.parent_node links. While doing so you could sum the distances in order to get the route's overall distance.

That's it. you are done

Conclusions

That was the first real C++ assignment in the course, and as such I had to jump through hoops in order to have it run locally on my Mac. During that process I had to:

  • Switch from VSCode to Xcode, as I could not debug with the first (must say that I think the combination Cmake, VSCode, Mac does not seem to be mature)
  • Building the project
  • Remoe the rust I had with C++ pointers and references

But I very much enjoyed it. Looking forward to the next assignment.

Made by Amir 💚