Path Planning in Robotics
What is a path?
Path, as the name suggests is a set of waypoints which a Robot is expected to travel. There can be many criterions for deciding a path that the Robot should follow. Various optimisations, checks are made before deciding an optimial path.
Why Planning is important for Autonomous Robots?
Path planning is one of the most important primitives for autonomous mobile robots. The ability to be able to travel on its own by finding a collision free, optimal path is an important aspect of making robots autonomous
Path planning for Autonomous Robots
Path planning, as illustrated above is an important aspect of autonomous robots. There are various methods how a path is planned. There are various algorithms on path planning. Some of the common features of path planners are: 1. Given a start and a goal position(or pose), give out a set of states(positions or velocities) that the robot should take to reach the goal from start. 2. The path generated should be collision free with the obstacles in the environment. 3. Generally the path generated should optimise some hueristic(or parameter). 4. The path generated should be traversable by a robot given its dynamics.
Path Planning algorithms
The problem to find an optimal path has been studied since many decades. There are many algorithms that are graph-based, sampling-based. Each branch follows a particular approach to solve the path planning problem.
1. Graph based algorithms:
Graph based algorithms overlay a topological graph on a robots configurational space and perform search for an optimal path. Some of the notable graph-based algorithms are:
- Dijkstra’s Algorithm
- A-Star (A*)
- D-Star (D*)
2. Sampling based algorithms:
Sampling based algorithms represent the configuration space with a roadmap or build a tree, generated by randomly sampling states in the configuration space. Some of the notable sampling-based algorithms are:
- Rapidly exploring Random Tree (RRT)
- RRT Star (RRT*)
- Informed RRT Star
- Batch Informed Trees Star (BIT*)