Avoiding An Obstacle Using The Pledge Algorithm

Avoiding An Obstacle Using The Pledge Algorithm

Moti Ben-Ari

Escaping from a maze is a classic problem that a robot can implement. The same algorithms can be adapted for avoiding an obstacle: if the robot is moving in the direction of a goal (call it "north" for convenience) and if it encounters a wall, it runs an algorithm to escape the maze until it can move freely north.

A simple algorithm for escaping a maze is to follow a wall, keeping it always on one side. For the Thymio, it is easier to follow a line on the floor because there are no true side-facing sensors for detecting a wall. The robot must keep track of its absolute direction so that it knows when it is facing north again. The Thymio does not have a compass or a gyroscope so it cannot directly measure its direction. The best solution is to use an inclined plane and to use the yaw (left-right) and pitch (up-down) accelerometers to measure 90 degree turns. (Thanks to Francesco Mondada for this idea!)

This image shows a board inclined on a stack of books at an angle of about 20 degrees:

setup1.jpg

You will have to experiment with the angle and the accelerometer thresholds to find a combination that works: a greater angle will make it easier to distinguish the different headings, but will make it harder for the Thymio to move. To avoid excessive oscillations when following the line that might be interpreted as turns, I used both ground sensors to follow the edge of the line: one sensor on the tape and the other off the tape.

For the obstacle use a "G" diagram with a long overhanging top line. Set the robot to go north. The robot moves until it encounters the line, at which point it follows the line. When it loses the line while pointing north, it has passed the obstacle and moves straight.

What does "north" mean? Intuitively, it means that the sum of the turns is a multiple of 360 degrees, that is, turn_sum mod 360 = 0. You can see in this video that this does not work, because the robot gets caught in an infinite loop:

A modification by John Pledge fixes the bug (second video): the robot leaves the obstacle only when the sum of the turns is 0 degrees:

Download the source code

Source code

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License