 |
Joelle Pineau, Sebastian Thrun, Dieter Fox
Mapping is the problem of generating models of a mobile robot's environment based on sensor data. Based on a stream of measurements from the robot's sensors, the goal of mapping is to determine the location of various entities, such as landmarks or obstacles, in a global frame of reference. To generate consistent maps of large-scale environments, the robot also has to solve a concurrent localization problem, which arises because robot odometry is often erroneous. Thus, the problem addressed in our research is a chicken-and-egg problem: Mapping is considered simple if the robot's location is known; and localization is considered simple if a map is readily available; but in combination the problem is hard.
Most successful navigation algorithms require the availability of maps, yet we lack general and scalable methods for automatically generating such maps. Such methods would facilitate the installation of mobile robots in indoor environments and enable robots to adapt to changes therein. At present, maps are usually generated manually, which involves significant time and money. This research, if successful, can also become a crucial step towards true robot autonomy. It can be combined with existing exploration and path planning strategies (in fact, we have done this in our lab), enabling robots to autonomously explore and build maps of large-scale environments.
Over the past two decades, the problem of building maps in indoor environments has received significant attention in the mobile robotics community. Previous approaches suffer from scaling limitations. Many of them make highly restrictive assumptions on the nature of the environment and the sensor input. With very few exceptions, previous approaches have not been able to map cyclic environments. They were often only tested in simulation.
Our approach is pervasively statistical in nature. It phrases the problem of concurrent mapping and localization as a constrained maximum likelihood estimation problem, where the objective is to find the most likely map given the data. With appropriate independence assumptions, the map likelihood function can be shown to be a function of two basic probabilistic models, a motion model, and a perceptual model. The motion model describes the effect of actions on a robot's pose, where pose comprises location and orientation. The perceptual model describes possible sensor readings for situations where both the map and the robot's pose are known. For mobile robots equipped with proximity sensors, both models are easily derived from the robot's physical properties.
Our approach applies the EM algorithm to find the most likely map under the data. EM is a well-known, efficient statistical algorithm for maximum likelihood estimation in high-dimensional spaces. In the context of our mapping problem, EM iterates two steps, a localization step and a mapping step. In the localization step, the map is fixed, and our approach computes probabilities over the robot's various poses in the data set. Since the map is assumed to be known, this step is a generalized version of Markov localization. In the mapping step, our approach computes the most likely map based on the pose estimates generated in the localization step. Since the robot's poses are fixed, generating the most likely map is mathematically straightforward. Our approach, thus, tackles the concurrent mapping and localization problem by solving two simpler problems: the problem of localization with a fixed map, and the problem of mapping under knowledge of the robot's poses. The iteration of these two steps leads to a local maximum of the map likelihood function, which usually coincides with the global maximum, and thus the most likely map.
This statistical approach has been implemented with two different representations; one in which all probabilities are approximated using piecewise constant functions, and one in which they are approximated using Normal distributions (Kalman filters). The first approximation is able to represent multi-modal distribution, hence can deal with global ambiguities that often arise in large-scale and cyclic environments. The second approximation can estimate the location of obstacles with floating-point accuracy, thus yields highly accurate maps. In combination, these methods have been found to generate maps whose size and accuracy are orders of magnitude better than maps generated with previous methods. Figure 1 shows examples of maps generated in environments of sizes up to 100 by 70 meters. In one case, the cumulative odometric error was larger than 70 meters.
|
Our current approach builds a single most likely representation of the entire mapped area. This is generally infeasible for larger environments, due to the processing requirements of applying the EM algorithm to very large data sets. A hierarchical map building approach will be considered to address scalability limitations. This approach relies on the construction of smaller-scale maps representing subsets of the environment. Maximum likelihood estimation is performed independently on each of these sub-maps. Contiguous sub-maps can then be combined into a larger map, assuming that the sub-maps are internally known with high confidence. The maximum likelihood estimation for the larger map optimizes the arrangement of the sub-maps, and consequently re-adjusts them necessary. This method would significantly increase flexibility. Arbitrary sized maps, representing subsets of the environment, could be built and used independently, without having to compute a map of the entire environment. The extension to multi-robot mapping and mapping of dynamic environments will be addressed. We also intend to develop an extension of the approach for autonomous exploration. Finally, the present approach will be adapted to generate and modify maps in real-time, such that only a limited history of past sensor readings need to be memorized.