Mariia Bai, Andreea Stroia, Hala Albahloul
Programming path planning algorithm for robot. Go from start point to the goal point in 8*8 grid.
A* is a graph traversal and path search algorithm. Starting from a specific starting node of a graph, it aims to find apath to the given goal point having the smallest cost
We are going to take this grid as an example:
The grid has a start point, an end point and obstacles
-
First, it checks for neighbours. Because our robot can move up, down, right or left, it checks for the neighbour that has smallest cost.
-
The smallest cost, f is the sum of g and h, where:
- g = the movement cost to move from the starting point to a given square on the grid, following the path generated to get there
- h = the estimated movement cost to move from that given square on the grid to the final destination
In our modification of A*, we are using only g with cost = 1
-
At each iteration, the f value is calculated (wave)
-
It keeps track of the paths originating from the start point
-
The algorithm is extending the paths one grid cell at a time until its termination criterion is satisfied, which is meeting the end point
-
Specifying the start and end ponts
-
Creating an open list to store all the point that can be taken into account when calculating the path
-
Creating a closed list that stores all the nodes that have been visited. In original A* we would do this, but in our modification we don't need it, because we will always have one best path.
-
We start with the start point and check its children (up, down, left and right)
-
We check if the children are in the maze boundaries, if the identify as an obstacle, or if they were already visited. If they meet any of these requirements, then we skip to the next child and do not calculate the f value, nor assign it to the open list. Otherwise, we calculate the g and h cost that form the final f.
-
We then check for the child with the lowest f and make this child the current point. We also append it to the closed list to form the path later (dont append in our modification)
-
The iteration continues until the current point will have the same x and y positions as the end point.
-
The path will be returned taken into account the parents of the points. The path is calculated backwards, starting with the end point and tracing back the parents accordingly.
