# Obstacle avoidance algorithm

## TARGET

The task I have taken as a challenge is to make a GPS-guided robot incorporated with features like Arduino for programming, ultrasonic sensors for obstacle avoidance and a GPS module to specify the way points location (from starting point to end point).

This robot should be able to avoid both static and moving obstacles while moving to its end point assigned from the GPS. I have found the robot manoeuvring around both static and moving obstacles to be a bit challenging. I was wondering if there is an effective obstacle avoidance algorithm that I can use.

I will appreciate it if I could get some helpful suggestions and insights.

• Pathfinding usually relies on the obstacles/path being known to the algorithm. The most basic form of obstacle avoidance is simply trying to get around it. This can be done by checking if there is an object infront of the robot, and if so, go to the right (and ocassionaly check if the obstacle is still there). Just try to program this out and then find scenario's where it makes sense to go back, to check if you can go around the left side. It can often help to think of how YOU would solve this problem if you were the robot.
– Paul
Mar 26 '17 at 9:02

In a real world scenario, your robot would know its start point and end point but due the limited range of its sensors (radar/ sonar/ visual) and the inability to "see" around corners, it would never be able to plan a full route at the very start of its journey. It would need to start the journey, detect obstacles as it moved and then re-calculate its path as it proceeds to its destination.

There is a very simple weighted index algorithm called the 'Bubble Rebound Algorithm' to accomplish this type of maneouvering developed by IOAN SUSNEA, VIOREL MINZU and GRIGORE VASILIU.

Be aware however, that this is NOT a 'Maze Solving' algorithm. It is only meant for avoiding obstacles.

But first I suggest you take a look at my blog post about the python simulation I wrote using this algorithm. This will help you understand what is going on and give you a broad idea about how the problem is solved.

I also made two very important modifications (which I have described in the blog) to the algorithm that help the robot actually reach a destination.

On the blog post you will find a link to the source code hosted at codeskulptor and a YouTube video demonstrating the algorithm at work.

The problem

Given an unknown graph (or just world), a robot/person should be able to find a way between two points.

Pathfinding is often done on a known world, this website allows you to check out the different algorithms, which very much look like what you want to achieve.

Since you mentioned moving obstacles, you may also look at collision avoidance algorithms. But it depends on if the moving obstacles themselves also avoid collisions. To be able to avoid moving obstacles, you'll have to be able to know their location, direction and speed, to be able to calculate where you would collide (and how to avoid it). But usually, just braking whenever they get too close may just work (maybe even drive backwards if they get even closer).

The approach

So, we've got a startpoint and an endpoint. Our initial plan would be to travel straight from start to end, since this is obviously the shortest path.

But it would be ideal if there wasn't an obstacle, and for us to verify our approach, we'll just think of an obstacle. Let's say there is a wall right in front of you, what are you going to do? You can't see where it ends (I believe your robot doesn't), so you're just going to walk around it, you could choose a random way, (left or right, maybe even backwards)

What algorithm

Basically you want to get to the endpoint, so you're going to have an algorithm that has some kind of "fitness" based on how close you are to the endpoint.

You could:

• Brute force: Try every single route, until you've found the way.
• Right hand rule: I've heard that, in mazes, if you always hold your right hand against the (right) wall, eventually you'll get to the end.
• Greedy algorithm: Just move towards the point, if you can't go any furhter, choose whatever seems to get you closer. If nothing is getting you any closer, choose the route that moves away the least.
• Heuristic algorithm: Move one way, until choosing another round will be more likely to be a solution, then choose to go down another lane. Until this one seems to be leading you away.
• Search algorithm, like breadth first or depth first search, check this video

Just try some of the algorithms, to see which one works best. Or try to determine/explain why one algorithm is/should be better than the other.