| Héctor H. González-Baños
Honda R and D, Americas, 800 California St. Suite 300, Mountain View, CA
94041, USA and Jean-Claude Latombe Department of Computer
Science, Stanford University, Stanford, CA 94305, USA |
| In this paper, we investigate
safe and efficient map-building strategies for a mobile robot with imperfect
control and sensing. In the implementation, a robot equipped with a range
sensor builds a polygonal map (layout) of a previously unknown indoor environment.
The robot explores the environment and builds the map concurrently by patching
together the local models acquired by the sensor into a global map. A well-studied
and related problem is the simultaneous localization and mapping (SLAM)
problem, where the goal is to integrate the information collected during
navigation into the most accurate map possible. However, SLAM does not address
the sensor-placement portion of the map-building task. That is, given the
map built so far, where should the robot go next? This is the main question
addressed in this paper. Concretely, an algorithm is proposed to guide the
robot through a series of 'good' positions, where 'good' refers to the expected
amount and quality of the information that will be revealed at each new
location. This is similar to the next-best-view (NBV) problem studied in
computer vision and graphics. However, in mobile robotics the problem is
complicated by several issues, two of which are particularly crucial. One
is to achieve safe navigation despite an incomplete knowledge of the environment
and sensor limitations (e.g., in range and incidence). The other issue is
the need to ensure sufficient overlap between each new local model and the
current map, in order to allow registration of successive views under positioning
uncertainties inherent to mobile robots. To address both issues in a coherent
framework, in this paper we introduce the concept of a safe region, defined
as the largest region that is guaranteed to be free of obstacles given the
sensor readings made so far. The construction of a safe region takes sensor
limitations into account. In this paper we also describe an NBV algorithm
that uses the safe-region concept to select the next robot position at each
step. The new position is chosen within the safe region in order to maximize
the expected gain of information under the constraint that the local model
at this new position must have a minimal overlap with the current global
map. In the future, NBV and SLAM algorithms should reinforce each other.
While a SLAM algorithm builds a map by making the best use of the available
sensory data, an NBV algorithm, such as that proposed here, guides the navigation
of the robot through positions selected to provide the best sensory inputs. |
