In one of my courses, "Mobile Robotics," we're supposed to program "lego robots" that have various sensors (light, sonar etc) to do funky stuff. First however, we simulate our robots using the PlayerStage environment.

In one of my recent labs, I had to build a map of the robot's world using only its laser sensors to detect obstacles. The laser sensors typically have a span of 90 degrees, with a laser ray emitted at every degree. By measuring the time taken for the ray to hit an obstacle and return, the distance to the obstacle can be measured. Of course, the robot is constantly moving, and the laser sensors aren't perfect, so they don't always return the most accurate readings!

Take a look at the world I used. The robot's starting orientation is arbitrary (in this case it starts off at the bottom left corner at an angle to the horizontal).

The robot is programmed to move to a goal position, avoiding obstacles using the "force potential" method. A resultant vector (direction) is calculated by considering all obstacles in the robot's immediate vicinity as exerting repulsive forces, and the goal position as exerting a strong attractive force.

The software maintains an internal representation of the world using a large 2 dimensional array. Each cell represents a 10cm x 10cm grid position in the world. Cells that are occupied are coloured black, empty cells white, and cells that have not yet been explored are marked grey.

The goal is to map as much of the world as possible in the shortest time. In addition, I didn't want to complicate matters and decided against using any path planning algorithms.

The problem is challenging, and my solution isn't optimal, however it does produces reasonable results. When the robot's laser sensors detect an obstacle, the corresponding cell in the internal map representation is marked as occupied. In addition, all cells in the line segment connecting the robot to the obstacle are marked as unoccupied.

That works well, but we want the robot to explore areas that it hasn't visited yet! The world occupies just 1/9ths of the robot's internal map representation. Can we just pick a random unexplored area in the world and move toward it? Of course there might be a number of obstacles preventing that. We might be able to break down the problem into a number of sub-goals designed to avoid obstacles directly in the path of the robot's path. Or, the unexplored area might be in a boxed enclosure. When do we decide to give up on the goal?

My algorithm instead explores an area in the immediate vicinity of the robot (for example a rectangular area, centered on the robot). It picks a random position in this area that has not been visited, and checks to see if there is a straight line path to it without any obstacles in the robot's way. If so, the robot moves toward that goal exploring areas around the goal.

I omit the implementation details (force potential method, detecting obstacles in a straight line path) for brevity's sake, besides it isn't too hard anyway. This method actually turns out to be pretty effective. It explores a fair amount of the world in reasonable time, is able to navigate through narrow pathways and squeeze itself through tiny openings!

Take a look at the map of the world generated after 5 minutes of running time...

... and 20 minutes...

Anyone have better (and simple) ideas?

View gallery