Research Abstracts - 2007

Long-Term Autonomous Navigation And Mapping In Dynamic Environments

Aisha Walcott & John Leonard

Introduction

In the future, mobile robots equipped with on-board sensing and autonomy will operate in dynamic environments for great lengths of time: weeks, months, and even years. These mobile robots will live in uncertain, vast environments such as urban and rural regions, underwater regions, and Martian environments. As robots navigate for long periods, they will continuously collect large amounts of data. Thus, a method to collect, represent and maintain the data is required. Our work addresses this by developing navigation strategies for a mobile robot with a long-term persistent presence in dynamic environments; and, by developing algorithms to capture and update spatial and temporal data in an environment model.

Problem

The goal of this research is to develop efficient methods for a mobile robot to maintain an up-to-date model of its environment over long periods (Figure 1a). To achieve this goal our research focuses on three key challenges. The first challenge is to minimize the number of times the robot becomes “lost”. That is, the point in which the uncertainty in the robot's pose reaches a specific threshold. The second is to develop an exploration strategy in which the mobile robot is able to continuously cover unknown or changed regions in the environment. The third challenge is to develop a strategy that enables the robot to maintain an up-to-date model of places within the environment, while coping with physical changes. We demonstrate our research on an RWI B21 mobile robot as shown in Figure 1b. The robot is equipped with two 180o laser range scanners mounted in plane.

Figure 1a: Illustration of places changing with time.	Figure 1b: RWI B21 robot.

Approach

To enable a mobile robot to continuously update maintain a model of the dynamic physical world, we propose the robot architecture shown in Figure 2. Specifically, this research focuses on three components of the architecture: Navigation, Exploration, and Revisit Policy.

Figure 2: Robot autonomous system architecture.

Navigation

The Navigation module is responsible for planning the trajectories for the robot to follow. It is influenced by the Revisit Policy and the Exploration strategy and affects the way the robot interacts with its environment. We are developing a conservative navigation strategy, called “Out-and-Back”. The Out-and-Back strategy aims to minimize the probability of the robot becoming lost, while trading off fast coverage of its environment. The main idea of the Out-and-Back strategy is to incrementally build confident paths. One method to achieve this is for the mobile robot to continuously navigate over the same paths, and systematically extend these paths further.  This is illustrated in Figure 3. Our rationale for this approach is twofold. First, note that one of the robot’s challenges is to navigate in a dynamic environment while minimizing its pose uncertainty. The Out-and-Back strategy addresses this challenge by limiting the distance the robot travels while traveling into unknown regions. Secondly, this strategy enables the robot to potentially improve pose estimates when returning on the same path.

Figure 3: Out-and-Back navigation strategy.

Exploration

For a mobile robot to cover unknown spaces in the environment, we adopt an exploration strategy based on Sensor-based Random Trees (SRTs) [4]. Our approach is two unify the SRT exploration strategy with Out-and-Back navigation, see Figure 4. To accomplish this, we are addressing the following issues. First, [4] assumes perfect localization when developing the SRT algorithm. This, however, is not a realistic assumption particularly for long-term navigation in dynamic environments, and due to sensor and odometry errors.  Thus, a method to integrate localization with SRT exploration is required. A second issue is how to develop a strategy to incorporate the SRT data structure into the robot’s environment model. We are addressing these issues as we develop an algorithm that unifies the SRT exploration strategy with Out-and-Back navigation.

Figure 4: An example of a sensor-based random trees (SRT).

Revisit Policy

To develop a revisit policy, we assume that data at each place in the environment place change randomly and independently. Thus, we adopt a probabilistic model for change commonly used in reliability theory and Web dynamics [1]. Specifically, sequences of changes at each place are assumed to be independent and occur at random, and are modeled as a Poisson process.  The probability that a change occurs within a given time interval is modeled as an exponential distribution. We are applying this probabilistic model to develop pa policy for updating places in the robot's environment model. The robot will first need to make the decision to either update existing places represented in its environment model or to explore new territory. To make this decision we include the probability that the robot will observe a change at a place it revisits into a utility function.

Related Work

Our work draws from three areas of research. The first is simultaneous localization and mapping (SLAM) [1, 3, 5]. The second is autonomous exploration [4]. The third is probabilistic models for temporal data, specifically for very large-scale dynamic environments, such as the Web [1].

Research Support

This research is funded in part by ONR, the MIT Graduate Students Office, and the MIT Lemelson Fellowship.

References:

[1] P. Baldi, P. Frasconi and P. Smyth. Modeling the Internet and the Web : Probabilistic Methods and Algorithms. Chichester, England ; Hoboken, NJ: Wiley, pp. 285, 2003.

[2] P. Biber and T. Duckett. Dynamic maps for long-term operation of mobile service robots.  In The Proceedings of Robotics: Science and Systems, 2005.

[3] J. J. Leonard et. al. A computationally efficient method for large-scale concurrent mapping and localization.  In International Symposium on Robotics Research, 1999.

[4] G. Oriolo, M. Vendittelli, et. al. The SRT method: Randomized strategies for exploration. In the Proceedings- 2004 IEEE International Conference on Robotics and Automation, pp. 4688-4694, 2004.

[5] S. Thrun. Robotic mapping: A survey. In Exploring Artificial Intelligence  in the New Millenium. G. Lakemeyer and B. Nebel, Eds. Morgan Kaufmann, 2002.