Back
to indexSebastian Thrun, Arno Buecken, Wolfram Burgard, Dieter Fox, Thorsten Froehlinghaus, Daniel Hennig, Thomas Hofmann, Michael Krell, Timo Schmidt
Summary
This paper was a summary presentation of the overall state of the Carnegie Mellon Autonomous Navigation projects over the last few years. First, it started with general algorithmic models, where the central clock was disregarded in a distributed model. CMU seems to favor the any-time approach, which provides algorithmic output whenever the algorithm is complete.
Mapping
Grid-based maps were used, where each square contains the probability of an obstacle in that location. A sonar sensor interpretation map was outlined, where sonar readings were mapped in space. A second model was generated using stereo vision. A key note here is to find the co-occurances of vertical edges to correlate the different stereo pairs. Proximity of the camera to an object is measured by the amplitude and the phase of filter responses. A limitation of stereo vision is recognized that large, unstructured shapes such as walls may not be accurately mapped. A great picture displays the map each approach generates seperately, showing the combined map (taking the maximum occupancy value and smoothing) with both stereo vision and sonar is cleaner than either alone. Topology maps are also explored, where each grid location contains the occupancy value, with edges denoting a path between grid nodes. This isn't the lined topo map we would expect from GSPS, but rather a grid of critical points denoting areas to travel, where all feature values are the same on one grid location. Its an efficient representation of the world, since it reduced to a space of nodes and edges.
Localization
"Localization is the process of aligning the robot's local coordinate system with the global coordinate system of the map." Two methods are explored: position tracking, and global localization, basically dead reckoning and GPS respectively. Here's another great picture where the error margin of the dead reckoning system grows as the robot continues to explore its space. Good point: if a robot moves to a position, it is unlikely the position is occupied.Use walls for orientation indoors. Plan global paths offline. Best results are likely to occur by combining GPS and dead reckoning.
Navigation
Global planner uses a local reactive collision avoidance to navigate through a map that it generated. Cost for traversing to a grid cell is its occupancy value. Update map with value iteration, or probablistic modeling of the likelyhood of an occupied square. Update only a specific region in the map, directly in front of the robot, called the "window". Use "triplet planning" - move the robot forward, right, left each move. Reactive collision avoidance routine has hard and soft constraints. Hard constraints (requirements) are torque limits and safety margins, soft constraints (preferances) are target heading, clearance, and translational velocity. See the map for velocity space, and the map for the soft constraints plotted on a 3D surface. Good point: increase robot's size in its model to increase clearance. Segmentation: merge cells with similar characteristics together. Subsample images to reduce resolution and increase efficiency.
Keywords
navigation, map, sonar, stereo vision, localization, collision avoidance, distributed processing
Rating
9
Bibtex Entry
@techreport{ thrun96map,
author = "Sebastian Thrun and Arno Buecken and Wolfram Burgard and Dieter Fox and Thorsten Froehlinghaus and Daniel Hennig and Thomas Hofmann and Michael Krell and Timo Schmidt",
title = "Map Learning and High-Speed Navigation in {RHINO}",
number = "IAI-TR-96-3",
year = "1996",
url = "citeseer.nj.nec.com/thrun98map.html"
}