Reid Simmons, Joaquin Fernandez1, Richard Goodwin2, Karen Zita Haigh3, Nak Yong Ko4, Sven Koenig5, and Joseph O'Sullivan
To be useful, autonomous mobile robots need to be able to reliably achieve high-level tasks, such as deliverying mail or patrolling buildings. Our work focuses on both the overall software architecture that can be used for such robot systems and the specific algorithms to achieve reliable, high-speed navigation. Our extensive experience over the years in testing the Xavier robot and in extending its capabilities has validated, to a large extent, our overall approach.
The world is on the verge of a revolution in the use of autonomous mobile robots in offices, homes, stores, hospitals, etc. However, commercially viable applications need robots that can achieve tasks autonomously, without tedious (and often error prone) human control. Having reliable autonomous robot systems that are easy to maintain and extend will go a long way towards making this a reality.
Xavier has been under development since 1993. At that time, few mobile robots existed that could navigate in unstructured, peopled environments, and even fewer with any significant reliability. Since then, the work done on Xavier, and elsewhere, has helped inspire a revolution in mobile robot systems. Today, many more robots exist that have reliable navigation capabilities. Xavier, however, remains one of the premier systems in reliable autonomous navigation.
Xavier (Figure 1, left) is built on top of a synchro-drive base from Real World Interface. The sensors on Xavier include bump panels, wheel encoders, a sonar ring, front-pointing and downward-pointing Nomadics laser light stripers, and a Sony color camera on a Directed Perception pan-tilt head. Xavier also has a speaker and speech-to-text card. Control, perception, and planning are performed on two on-board 200 MHz Pentium computers, running Linux. A 486 laptop on top of Xavier provides for graphical display and communication to the outside world via a Wavelan wireless Ethernet.
The Xavier navigation system uses a layered control architecture (Figure 1, right) consisting of servo-control (provided by the commercial base and pan-tilt head), obstacle avoidance, navigation, path planning, and task planning . The obstacle avoidance layer keeps the robot moving in a desired direction, while avoiding static and dynamic obstacles. It uses the Lane-Curvature Method  to find highly traversable lanes in the desired direction and uses the Curvature-Velocity Method  to switch between lanes and avoid dynamic obstacles. The navigation layer is responsible for getting the robot from one location to another. It uses a Partially Observable Markov Decision Process (POMDP) model to maintain a probability distribution of where the robot is at all times, choosing actions based on that distribution [10,5]. The path-planning layer uses a decision-theoretic approach to choose routes with high expected utility. It plans using a topological map, augmented with approximate metric information, and takes actuator and sensor uncertainty into account . Finally, the task-planning layer efficiently orders tasks, integrates newly received tasks, and monitors overall task completion [2,1]. The navigation system is implemented as a collection of asynchronous processes that are integrated and coordinated using the Task Control Architecture (TCA). TCA provides facilities for interprocess communication (message passing), task decomposition, task synchronization, execution monitoring, exception handling, and resource management .
Xavier is also interfaced to the World Wide Web (http://www.cs.cmu.edu/~Xavier) . For the past three years, people from all over the world have been able to command Xavier and monitor its travels. During that time, Xavier has traveled autonomously over 200 kilometers, while achieving 95% of its tasks.
We are currently getting Xavier to ride the elevators reliably and will be programming Xavier to deliver faxes in the near future. We continue to do research in execution monitoring and exception handling, and use Xavier for other projects, including robot learning, social interaction and multi-robot coordination (see related research summaries).