A*, Dijkstra and BFS Algorithms for a Rigid Robot in a Custom Map

Path planning for autonomous robots can often be a time-consuming process. Many algorithms have been developed to create a map of a previously unknown environment and then efficiently reach from a start location to the end location in minimum time or by traveling minimum distance possible.

This project deals with building a custom shape map in python 3 using the half plane method, augmenting the obstacle space into configuration space using Minkowski distance and then implementing A*, Dijkstra and Brute force algorithm for the same start position and the goal position. The final output will be shown in a GUI drawn using OpenCV in Python.

Fig: The final output for the 3 algorithms shown together, the yellow portion shows the nodes explored while the blue region shows the augmented obstacle space from the already formed black obstacle space. The red dot in each shows the goal position while the green indicates the start position.

The initial image of the map is shown below, the same has to be plotted in python and the obstacle space will be defined using half plane method.

Fig: Initial map of the workspace

The axes defined in the OpenCV take (0,0) for an image at the top left corner.

The half-plane method is dividing the given space into 2 regions and then finding which space a particular point lies in with respect to the plane drawn.

Part A: Defining the Map and the obstacle…