A* Path Planning

So, what is A* exactly?

A* is an algorithm is the most widely used path-planning algorithm. It is used to find the shortest path between two nodes or points on a graph, taking into account both the distance between the nodes and the estimated distance to the target node.

The algorithm works by maintaining a priority queue of nodes to be explored. The priority of each node is determined by a combination of the distance from the start node and the estimated distance to the target node, which is calculated using a heuristic function. The algorithm explores nodes in order of increasing priority until the target node is reached or all nodes have been explored.

One of the key advantages of the A* algorithm is that it is guaranteed to find the shortest path if the heuristic function is admissible and consistent. An admissible heuristic never overestimates the distance to the target node, and a consistent heuristic satisfies a stronger condition that ensures that the heuristic estimate of the distance between any two nodes is less than or equal to the actual distance between those nodes.

Overall, the A* algorithm is a powerful and widely used tool in computer science and artificial intelligence, with applications in areas such as game development, robotics, and logistics planning.

In the above figure, we are able to see various nodes numbered as 0,1,2,3,4,5 and in this case, our starting node is 0 and the end node is 5.

---

ENPM 661 Path Planning Project

• GitHub

Specific to my project for ENPM661, we were given a field that contains obstacles of a certain size and we need to optimize the algorithm so traversal is quickest from user-given input of the start and end node.

The assumptions for the following project are as follows:

1. Euclidean Distance from the goal is the Heuristic
2. A threshold of 1.5 units of distance from the goal is considered as the goal reached
3. Each step has a cost of 0.5 and the allowed theta threshold is 30 degrees

The conditions for this A* path planning is that for each node, we have 5 directions specified by 60,30,0,-30,-60 degrees from the original orientation which is specified by the user.

The code accepts the following inputs from the users and performs the A* path planning, it also takes into consideration the robot’s radius and an additional user-defined clearance.

Enter Clearance of the Robot: 2

Enter the Radius of the Robot: 2

Enter Step size of the Robot: 1

Enter coordinates for Start Node: 11 11

Enter Orientation of the robot at start node: 30

Enter coordinates for Goal Node: 238 588

Enter Orientation of the robot at goal node: 60

Note: If the radius of the robot and the clearance combined create a hindrance in the path of the robot, it will stop the navigation and give an error. Please retry in that case. The sum of two cannot be greater than 4 to reach every coordinate of the given field.