ROBOT MAPPING AND MOTION PLANNING

The aim of this project is to map an unknown area of approximately 150sq feet. The area was populated with randomly placed convex and concave obstacles, alcoves and remnants of black balloons…. The robots mission is to explore the area entirely and build up a probabilistic roadmap of its journey.

APPROACH

The final algorithm developed considers several different factors. The outline is given below and salient features are discussed thereafter.

1. Rotate the sensors and build up a local map of the area surrounding the robot. This has two parts:

a. In the area where a cell is detected, add a numerical value to the ‘certainty’ value in the cell indicating that there is an object.

b. Subtract a value from the cells that lie in between the robot and the obstacle indicating that there is free space there.

2. Use the current location of the robot and the local map to update the global map.

3. Lock the values indicating the certainty that there is an object at a particular location close to the robot. Set the cells around the current location to indicate that the area has been closely scanned.

4. Check the local area in front and around the robot to try to move. Move forward if possible or turn and then move forward.

5. Move until the robot is in an area that has not been explored.

6. While all the above is going on the robot is sending data back to the PC and updating the roadmap.

7. Go to step 1.

Design Considerations

Rotating Ultra sonic sensors

In order to scan around the object we used two ultra sonic sensors mounded on a gearing mechanism attached to a servo. This enabled the sensors, which were mounted in opposite directions to sweep out a full scan circle. Please see the picture with the rotating sensors mounted on the top of the robot.

Minimum number of turns:

The robot will be controlled using open loop control and hence the problem of error propagation is large. This is most evident in the turning procedures. Hence, we designed an algorithm to explore the maze with as few turns as possible. This amounts to going straight until hitting an obstacle and then making a distinct turning action or known angle before moving off in a straight line again.

We also tried to integrate a rate gyro into the turning algorithm so as to improve the turning accuracy. However, we found that the output varied depending on the supply voltage and required recalibration over time or every time the battery was changed. The calibration was also found to be non-linear with respect to rotation direction and speed of rotation. Hence, we decided to use a timer to clock out a desired turn time at constant turning command signal to the motors.

Random walk

After several different algorithms were tried in an effort to explore the maze, the best method was eventually found to be a quasi random approach. This was achieved by including a random component in the turn angle that changed each time the robot hit an obstacle. On a head on approach to an obstacle the turn was between 120 and 240 degrees where as when an obstacle was on either side of the robot the turn was between 25 and 50 degrees away from the obstacle. The result of this was that the robot very rarely got stuck in small areas – and even managed to navigate its way through small openings! If given enough we found that the robot could get to EVERY point in the maze!

Problem with Ultra Sonics spreading out…

The ultra-Sonics wait for a sound wave reflection to record a time and the compute a get a distance to the nearest obstacle. However, because the wave spreads out there is a range of approximately 30 degrees where they would pick up the same distance for any object within the range. The problem with this is that the sensors start to approximate straight edges with semi-circles when a fair distance away. They also expand point objects into arcs! In order to overcome this we only store obstacles if they are with in a small range of the robot. This ensured that we were close enough to the object to get a good estimate of it position, size and orientation. The size of each step forward before scanning had to be scaled to achieve a balance between speed and accuracy. (Too little takes to long…..to far makes arcs out of straight walls)

Mark your territory

Once we have scanned an object we held the values of the cells with in a certain range of the robot (about 16 inches). We also marked this territory as being visited so we could see where the robot had been and where it still had to explore.

Don’t stop where you have been…..

In an effort to speed up the scanning process there is little point in stopping to scan where we have already been. Hence we added an algorithm to check that we have not already scanned the area we are about to stop in. If we have then we keep walking – otherwise we stop for some data. This improves the speed GREATLY later in the mapping process.

This function was also extended to take into account that at any time we may be right on the edge of the previously scanned area and stopping to do a scan would actually add a lot of good information This was particularly useful when exploring along walls and in corners where previous robot pass may have gone nearby, but not actually located and locked the position of the wall.

Visual basic interface.

In order to see what was going on we built a VB interface that communicated data to and fro through the micro hopper to the PC. The mapping array that was constructed and updated was sent, row by row to the vb interface where the level of certainty of an obstacle was graduated in colors. The interface also allowed for a threshold algorithm that could give better results by removing many of the small scanning errors. It also allowed for updates on position as discussed in the next section.

Problems with open loop? No!

As could be expected out robot slowly drifted away from where is thought it actually was. The effect increased greatly as the robot starts to make frequent turns and weave out of small awkward areas. In order to overcome this we added a position update feature to the VB code that enabled us to send a command to the robot telling its actual location. By simply clicking and holding the mouse pointer at the position in the scanned area displayed on the VB screen where the robot is and then dragging a line in the direction that the robot is facing before releasing you are able to correct the robot at any time! This could be considered to be like GPS or a manual feedback type approach.

Results

The mapping procedure worked really well. In particular the random walk procedure ensured that we eventually covered the whole maze! However, there were some frustrations with the ultra sonic sensors measuring any distance with in 30 degrees. The open loop control / manually closed loop control in the end turned out to work EXTREMELY well and allowed for good mapping.

Photo of mapped area

Have a look at this…..pretty hard…..and the robot did it all!

Map of area

Note this map does not correspond to the picture above……but I will try to get one soon..

Video of scanning

We have three videos for you:

For a short clip of the sensors rotating: Click here to download.

We have a video of the robot moving in the maze – click this to get it..

And finally we have a shot of the VB interface getting updated….click here.

Conclusions

The project was a success. We learn a lot about motion planning, DSP programming, memory allocation, motion planning, VB interfacing and how to go for several nights with only a few hours sleep. Improvements that could be made would be to add feedback control to the position computations and thus not loose track of position over time. This might also allow for continuous motion of the robot – the obstacle region being updated as is moves.

Zip file of code

DSP Files

VB Files

Flash Files