Finding-Shortest-Path-using-Breadth-First-Search-Algorithm

Point robot planning using BFS

Author: Yash Shah

About the Project: Implementation of Algorithm for finding a shortest path between two points in an area (with obstacles) using Breadth First Search in MATLAB.

Running The Program:

1. Open MATLAB and open [main.m] file in MATLAB.
2. Change the working directory to folder that contains [main.m] file.
3. Run the program
4. The program will generate a graph of the configuration space.
5. Follow the commands that appear on the Command Window. It will ask you to give coordinated of start and end point.
6. The program will take some time depending on the start and end point. Maximum it will take 7 mins for two extreme points.
7. The command window will continuously show the working node number(i.e the node that generates the children at that time).
8. Once the search is completed , open the minimized graph window, it will show the optimal path and the nodes expanded.
9. I have also included a extremes.jpg (in the same folder) file that shows the path for two extreme points ((0,0) and (250,150)).
10. I have also included a gif file visual.gif that shows the expansion of nodes visually.

Fig: Planning Algorithm GIF

Fig: Extreme Points

Contact: For more details and help contact ([email protected]).

Yash Shah UID: 115710498