|
Robot Mapping and Navigation
|
| |
|
Robots move about, avoiding objects using various sensors to detect things that are near the robot. The robot may or may not create a map within its memory of its local area. Such a map is not used to avoid objects, but may be of use later to determine a path to a desired location. Finding a viable path to a destination is known as Navigation.
|
| |
|
| |
|
Mapping is the action of creating a grid of cells in memory, then assigning values to the individual cells to indicate either what may be in it, or normally, just an indication of whether the robot can pass through the cell or not.
|
| |
|
One viable mapping method is to have a grid of cells which is large enough to encompass the area that the robot will operate within. Immovable cell contents such as walls and structural items should be indicated by a high value in a cell. Smaller values can be used to indicate moveable objects, such as people, furniture, etc. A minus value would indicate a cell that has not been investigated. A zero value would indicate that the cell is empty and can be traversed by the robot. (An option would be to have zero indicate unknown and one indicate flat and clear, if negative numbers are an issue.)
|
| |
|
As a robot moves about, it will update its map with information received from its sensors. Immovable objects should never be modified (yes, it is possible that it was knocked down somehow but it is more likely that the robot is not actually looking at it where it thinks it is). Moveable objects may have moved and no longer block the robot’s path.
|
| |
|
Sensor information will either indicate that something has been spotted (possibly with distance information), or will indicate that no object is within the sensor’s range. If an object is detected, the map cell that it is in can be updated to indicate its existence. Also, the cells between the robot and the object can reliably be updated to indicate that they are clear. If no object is detected, then the first map cell in the sensor’s detection direction can reliably be updated as clear, but cells further out should probably not be updated. You might think that the cells out to the sensor’s detection range can all be updated, but since sensor effectiveness is subject to fluctuation, it seems best to only update the first cell and then update other cells as you approach and find nothing there.
|
| |
|
| |
|
Navigation is the action of finding a path through the map from the current location to the desired location.
|
| |
|
There are several methods of determining an available path from the current location to a desired destination. Each method will need to select a cell to move to next. If you plot the current location and the desired location on a grid, you will be able to create a rectangle which connects the two locations. There are then two common methods of selecting the next cell:
|
| |
|
(1) Short-Side Preferred – travel along the short side of the rectangle to where it connects to the long side, then turn in that direction to the destination. This method generally results in an L shaped path with adjustments made for obstructions.
|
| |
|
(2) Long-Side Preferred – Travel along the long side of the rectangle constantly re-computing the rectangle. This method will result in the long side eventually becoming the short side and the robot will follow a jagged path between the two side to the destination.
|
| |
|
Once it is decided which side is preferred, then the robot must decide to use one of the following path selection methods:
|
| |
|
(1) A behavioral method might be to select the next adjacent cell that is available to the robot (hopefully in the desired direction if it is not obstructed). The robot will move into the selected cell and continue to select the next available cell until it reaches it destination or determines that it is not possible to do so.
|
| |
|
(2) Build a path list of cells that will be traversed in memory until a solution is found, and only move once the solution is found. The path will be created by repeatedly choosing the next cell until the destination is achieved, just like method one, but may have to branch and return and try other branches to arrive at a solution. This method will generally take less time and distance to complete the tasks since dead ends and reversals are all carried out in the program whether than by motor movement.
|
| |
|
| |
|
Debugging Maps and Navigation is more of a simulation or visualization. Data is captured during the operation of the robot, then replayed in a viewer to determine how correctly the robot behaved. It is possible to decide methods of improving the robot control code based on observing its behavior.
|
| |
|
The DPRG Remote Robot Control API provides for the robot to have an encoded string containing the data accumulated from its sensors during each main program loop. There is also an encoded string indicating the next action that the robot should take, along with optional debugging data from the methods exercised in the process. With these pieces of data, along with the current map, which should include the location and facing direction of the robot, and possibly the results of key method to be able to review which one caused an incorrect behavior, it should be possible to create a display of the run for later review. I plan to create a Windows program to import/export map data and visualize to run.
|
| |
|
Where I Plan To Go From Here
|
| |
|
I will be implementing the robot code in Python and the debugging code in VB.NET, but I plan to first work through the logic in pseudo-code. This will allow readers who do not use the same programming environment as I do to more easily create a version of this system in their own preferred language.
|
| |