PATH PLANNING PROJECTS

The aim of this project was to find all the possible states of the 8-Puzzle starting from the given initial state and using the brute force search algorithm (BFS) find the path to reach the goal state using the possible states.

In the Dijkstra algorithm, we can find an optimal solution from the start position to the goal position by implementing small changes to the BFS algorithm. Here, we will assume that all the actions do not have the same cost associated with them. Djikstra is a priority queue which does not just pop the last element but pops the element which has the least cost attached to it.

A* adds another cost to the previously calculated cost in the Djikstra’s algorithm called as the cost to go, it is heuristic in nature, which means that as per the map, we know where the goal location is. The cost to go is calculated by finding the distance of the child node formed from the goal node. The calculated distance can be a Manhattan distance or Euclidean distance.

In this project, we designed an astar algorithm for Turtlebot in a 3D environment to find the shortest path between the start and goal position as well as avoiding the obstacles.

In this project, we designed a dijikstra algorithm for an AGV in a rectangular environment to find the path with the shortest distance and least time.