# Path Planning in Robots

Hello,

Navigation is undoubtedly a complex process when we attempt to build an autonomous robot for real-world conditions as this Rough Terrain Robot and path planning is essential to decide a safe path for the robot to move, avoiding all major obstacles. Hence it requires good and efficient algorithms for the smooth working of the system. Though there are numerous algorithms developed for this purpose, I would like to propose a combination of a few algorithms to implement the motion planning. Throughout the discussion, the terrain is considered to contain only static and no dynamic obstacles. However, algorithms can be modified to deal with dynamic conditions.

Let us break down this complex task into two major parts, i.e. **Global Path Planning** and **Local Path Planning**.

Global Path Planning

Here we look at the planning the path from the start to the end considering only major obstacles and ignoring the smaller ones. There are multiple ways of executing this, namely, visibility graphs, Voronoi diagrams, rapidly exploring random trees, etc. Here I would like to stress on the usage of **Voronoi Diagrams** approach to plan the path. Voronoi diagram is partitioning of a plane into regions based on distance to points in a specific subset of the plane [1].

The site points in the above figure refer to the obstacles and the edges are the safest path for the robot to move.

As in the above figure, there may be multiple paths in which we can travel from one point to the other. The efficiency of our system will be decided based on traversing through the quickest path. Hence we also need a way to do that. It can be done by well-known Dijkstra’s algorithm [2]. It finds the shortest path between the source node and destination node.

We first acquire the graph using Voronoi diagram and then use Dijkstra’s algorithm to find the shortest path. This way we can plan the global path. The developed Voronoi diagrams also act as a reference map for the robot. As the robot explores new terrains, it stores this information in form of these diagrams and hence implementing terrain learning.

The main task here is to identify the nodes through which the robot needs to travel and finding the shortest path.

Local Path Planning

Our main aim here is to take the robot safely from one node (vertex of Voronoi diagram) to another by deciding which obstacles can the robot go over and which it cannot and travel accordingly. Also, it may have to deviate a little from the path which was set through the global planning due to the practical constraint. Simple obstacle avoider algorithms with slight modification may be sufficient for this.

In basic obstacle avoiders, the robot changes its direction when it sees an obstacle. The priority for this change in direction is pre-defined. In our case, the priority should be modified based on whether the direction of motion is towards the node it is supposed to reach or not. Also, there should be a flexible constraint kept in the angle of deviation. If the deviation of the robot from the required direction is more than the set limit, the direction correction is required. This constraint needs to be kept flexible i.e. ignored when required because, if the robot finds no path to move forward or is covered by obstacles even in other sides, It has to move back and then correct its path.

# Conclusion

Making use of algorithms as above increases the stability and efficiency of the robot. As a trade off, it would also require higher processing power. This could either be achieved by having a better processor on board or getting the processing done on a remote PC.

I have only considered a couple of algorithms which I found suitable, I may have missed out something better. Please let us know if there’s any better way to implement navigation.

# References

[1] https://en.wikipedia.org/wiki/Voronoi_diagram

[2] http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

Gave a clear and concise idea of global and local path planning. Very helpful.

John Rodrigues

Harsha Alva

Concepts from this post could be used in CoffeeBot

Sounds interesting ,will get coffeeBot to Mangalore soon for testing