Abstract
In addition to the capability to navigate from a point of origin to a given goal and avoiding all static and dynamic obstacles, a mobile robot must posses another two competencies: map building and localization in order to be useful. A mobile robot acquires information of its environment via the process of map building. Map building for mobile robots are commonly divided into occupancy grid and topological maps. Occupancy-grid maps seek to represent the geometric properties of the environment. Occupancy-grid mapping was first suggested by Elfes in 1987 and the idea was published in his Ph.D. thesis (A. Elfes, 1989) in 1989. Topological mapping was first introduced in 1985 as an alternative to the occupancy- grid mapping by R. Chatila and J.-P. Laumond (R. Chatila, & J.-P. Laumond, 1985). Topological maps describe the connectivity of different locations in the environment. The pose of a mobile robot must be known at all times for it to navigation and build a map accurately. This is the problem of localization and it was first described in the late 1980’s by R. Smith et al (R. Smith et al, 1980). Some key algorithms for map building and localization will be discussed in this article.
TopMap Building
As seen from the integrated algorithm from part I of the article, a mobile robot must be able to acquire maps of an unknown environment to achieve higher level of autonomy. Map building is the process where sensory information of the surrounding is made comprehensive to a mobile robot. In this section, two key approaches for map building: occupancy-grid and topological mapping are discussed.
Key Terms in this Chapter
Odometry: A method to do position estimation for a wheeled vehicle during navigation by counting the number of revolutions taken by the wheels that are in contact with the ground.
Recursive Algorithm: It refers to a type of computer function that is applied within its own definition. The extended Kalman filter and particle filter are recursive algorithms because the outputs from the filters at the current time step are used as inputs in the next time step.
Curse of Dimensionality: This term was first used by Richard Bellman. It refers to the problem of exponential increase in volume associated with adding extra dimensions to a mathematical space.
Jacobians: The Jacobian is a first-order partial derivatives of a function. Its importance lies in the fact that it represents the best linear approximation to a differentiable function near a given point.
Gaussian Distribution: It is also known as normal distribution. It is a family of continuous probability distributions where each member of the family is described by two parameters: mean and variance. This form of distribution is used by the localization with extended Kalman filter algorithm to describe the posterior belief distribution of the robot pose.
Predicted Belief: It is also known as the prior belief. It refers to the probability distribution of the robot pose estimate interpreted from the known control data and in the absence of the sensor measurement data.
Posterior Belief: It refers to the probability distribution of the robot pose estimate conditioned upon information such as control and sensor measurement data. The extended Kalman filter and particle filter are two different methods for computing the posterior belief.