Xavier: Reliable Autonomous Indoor Navigation

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.

State of the Art:

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 [9]. The obstacle avoidance layer keeps the robot moving in a desired direction, while avoiding static and dynamic obstacles. It uses the Lane-Curvature Method [3] to find highly traversable lanes in the desired direction and uses the Curvature-Velocity Method [7] 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 [4]. 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 [6].

Xavier is also interfaced to the World Wide Web (http://www.cs.cmu.edu/~Xavier) [8]. 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.

Figure 1: The Xavier Mobile Robot and its Layered Control Architecture

Future Work:

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).


Joaquin Lopez Fernandez and Reid Simmons.
Robust execution monitoring for navigation plans.
In Proceedings International Conference on Intelligent Robotics and Systems, Vancouver, Canada, October 1998.

Karen Zita Haigh and Manuela M. Veloso.
Interleaving planning and robot execution for asynchronous user requests.
Autonomous Robots, 5(1):79-95, March 1998.

Nak Yong Ko and Reid Simmons.
The lane-curvature method for local obstacle avoidance.
In Proceedings International Conference on Intelligent Robotics and Systems, Vancouver, Canada, October 1998.

S. Koenig, R. Goodwin, and R.G. Simmons.
Robot navigation with markov models: A framework for path planning and learning with limited computational resources.
In L. Dorst, M. van Lambalgen, and F. Voorbraak, editors, Reasoning with Uncertainty in Robotics, volume 1093 of Lecture Notes in Artificial Intelligence, pages 322-337. Springer, 1996.

Sven Koenig and Reid Simmons.
Xavier: A robot navigation architecture based on partially observable markov decision process models.
In R.P. Bonasso D. Kortenkamp and R. Murphy, editors, Artificial Intelligence and Mobile Robots. MIT Press, 1998.

Reid Simmons.
Structured control for autonomous robots.
IEEE Transactions on Robotics and Automation, 10(1):34-43, February 1994.

Reid Simmons.
The curvature velocity method for local obstacle avoidance.
In Proc. IEEE International Conference on Robotics and Automation, pages 3375-3382, Minneapolis, MN, April 1996.

Reid Simmons, Joaquin Lopez Fernandez, Richard Goodwin, Karen Zita Haigh, Sven Koenig, and Joseph O'Sullivan.
Xavier: An autonomous mobile robot on the web.
Robotics and Automation Magazine, 1999.

Reid Simmons, Rich Goodwin, Karen Zita Haigh, Sven Koenig, and Joseph O'Sullivan.
A layered architecture for office delivery robots.
In W. Lewis Johnson, editor, Proc. Autonomous Agents '97, pages 245-252, Marina del Rey, CA, February 1997. ACM Press.

Reid Simmons and Sven Koenig.
Probabilistic navigation in partially observable environments.
In International Joint Conference on Artificial Intelligence, pages 1080-1087, Montreal, Canada, August 1995.

About this document...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998).
The translation was performed on 1999-02-21.


Now at University of Vigo, Vigo, Spain
Now at IBM T J Watson Research Center, Yorktown Heights, NY
Now at Honeywell Technology Center, Minneapolis, MN
Now at Chosun University, Seoul, Korea
Now at Georgia Institute of Technology, Atlanta, GA