Solving-a-randomly-generated-maze

Path finding on a randomly genearted maze

1. A maze is randomly generated with only black and white pixels. The probability of a pixel of being black is maintained at 30%.
2. BFS, DFS, Dijkstra's algorithm, Greedy BFS and A* --- these five path finding algorithm is used to find path between the top-left and bottom-right corner pixel.

• Output video links:

1. Dijkastra's Algorithm
2. Greedy Algorithm
3. Depth First Search
4. Breadth First Search
5. A* Algorithm

• Some snapshots:

Path finding on a map

Finding a route between start point(126,19) and the end point(257,183) on the given map(276x431).

• Output video links:

1. Dijkastra's Algorithm
2. Greedy Algorithm
3. Depth First Search
4. Breadth First Search
5. A* Algorithm

• Some snapshots:

Presentation Link:

Link of the presentation of the project.

---

Implementation of RRT in python

What is RRT?

• It is one of the various path planning algorithms. It’s a sampling-based algorithm that makes it very useful to plan high-dimensional robot paths.
• It starts with an empty tree. Then it generates random nodes in each iteration. Once a node is generated, it searches for an existing node present in the tree, which would have the minimum distance from that newly generated node. If there are no obstacles between the two nodes, a new edge is created between these two nodes and added to the tree. That’s how the tree expands and eventually finds its goal. Once the goal is reached, the path is shown between the starting node and the goal.

Features of RRT

1. It doesn’t ensure an optimal path.
2. The growth of trees is heavily biased towards unexplored regions.
3. Using a growth factor restricts the chances of going too far in the wrong direction, making the path smoother.
4. The generation of a random state precisely at the position of the goal or final state is very unlikely. That’s why a predefined area around the final state is kept.
5. It is better than search-based algorithms like A* when dealing with high-dimension robots.
6. Path found in RRT differs on average by a factor of 1.3 to 2.0 from the optimal path.
7. In the beginning, the tree expands non-uniformly to explore the four corners first. Once it’s achieved, the tree expands uniformly over the free space.
8. The generation of random vertices is independent of the position of the root vertex or starting point.
9. Once a tree is generated to find a goal state, we need not generate another new tree from scratch if the goal state position is changed, given that obstacles are not changing their position.

• Some snapshots: