Xavier: experience with a layered robot architecture

ABSTRACT

Office delivery robots have to perform many tasks such as picking up and delivering mail or faxes, returning library books, and getting coffee. They have to determine the order in which to visit locations, plan paths to those locations, follow paths reliably, and avoid static and dynamic obstacles in the process. Reliability and efficiency are key issues in the design of such autonomous robot systems. They must deal reliably with noisy sensors and actuators and with incomplete knowledge of the environment. They must also act efficiently, in real time, to deal with dynamic situations. To achieve these objectives, we have developed a robot architecture that is composed of four layers: obstacle avoidance, navigation, path planning, and task planning. The layers are independent, communicating processes that are always active, processing sensory data and status information to update their decisions and actions. A version of our robot architecture has been in nearly daily use in our building since December 1995. As of January 1997, the robot has traveled more than 110 kilometers (65 miles) in service of over 2500 navigation requests that were specified using our World Wide Web interface.

REFERENCES

• 1: Agre, P. E. and Chapman, D. Pengi: An implementation of a theory of activity. In <i>Proceedings of the National Conference on Artificial Intelligence (AAAI-87),</i> Seattle, WA. 1987, 268--272. Morgan Kaufmann, San Mateo, CA.
• 2: Arkin, R. C. Motor schema-based mobile robot navigation. <i>International Journal of Robotics Research,</i> 8(40):92--112.
• 3: Arkin, R. C. Integrating behavioral, perceptual and world knowledge in reactive navigation. <i>Robotics and Autonomous Systems,</i> 1990, 6:105--122.
• 4: Atkins, E. M., Durfee, E. H., and Shin, K. G. Detecting and reacting to unplanned-for world states. In <i>Papers from the 1996 AAAI Fall Symposium "Plan Execution: Problems and Issues,"</i> Boston, MA. 1996, 1--7. AAAI Press, Menlo Park, CA.
• 5: Borenstein, J. and Koren, Y. The vector field histogram---fast obstacle avoidance for mobile robots. <i>IEEE Transactions on Robotics and Automation,</i> 1991, 7(3):278--288.
• 6: Brooks, R. A. A robust layered control system for a mobile robot. <i>IEEE Journal of Robotics and Automation,</i> 1986, RA-2(1):14--23.
• 7: Buhmann, J., Burgard, W., Cremers, A. B., Fox, D., Hofmann, T., Schneider, F. E., Strikos, J., and Thrun, S. The mobile robot rhino. <i>AI Magazine,</i> Summer 1995, 16(2):31--38.
• 8: Congdon, C., Huber, M., Kortenkamp, D., Konolige, K., Myers, K., Saffiotti, A., and Ruspini, E. H. CARMEL vs. FLAKEY: A comparison of two winners. <i>AI Magazine,</i> Spring 1993, 14(1):49--57.
• 9: Connell, J. H., A behavior-based arm controller. <i>IEEE Journal of Robotics and Automation,</i> 1989, 5(6):784--791.
• 10: Connell, J. H. SSS: A hybrid architecture applied to robot navigation. In <i>Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 92),</i> Nice, France. 1992, 2719--2724. IEEE Press, New York, NY.
• 11: Evans, J. M. HelpMate: An autonomous mobile robot courier for hospitals. In <i>Proceedings of the International Conference on Intelligent Robots and Systems (IROS 94),</i> Munich, Germany. 1994, 1695--1700. IEEE Press, New York, NY.
• 12: Firby, J. R. An investigation into reactive planning in complex domains. In <i>Proceedings of the National Conference on Artificial Intelligence (AAAI-87),</i> Seattle, WA. 1987, 202--206. Morgan Kaufmann, San Mateo, CA.
• 13: Fox, D., Burgard, W. and Thrun, S. The dynamic window approach to collision avoidance. <i>IEEE Robotics and Automation Magazine.</i> 1997, 4(1):23--33.
• 14: Gat, E. Integrating planning and reacting in a heterogeneous asynchronous architecture for controlling real-world mobile robots. In <i>Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92),</i> Seattle, WA. 1992, 809--815. MIT Press, Cambridge, MA.
• 15: Goodwin, R. <i>Meta-Level Control for Decision-Theoretic Planners.</i> PhD thesis, School of Computer Science, Carnegie Mellon University, October 1996. Also available as technical report CMU-CS-90-109.
• 16: Karen Zita Haigh , Manuela M. Veloso, High-level planning and low-level execution: towards a complete robotic agent, Proceedings of the first international conference on Autonomous agents, p.363-370, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267741]
• 17: Hills, A. and Johnson, D. B. A wireless data network infrastructure at Carnegie Mellon University. <i>IEEE Personal Communications.</i> 1996, 3(1):56--63.
• 18: Mataric, M. J. Integration of representation into goal-driven behavior-based robots. <i>IEEE Transactions on Robotics and Automation,</i> 1992, 8(3):304--312.
• 19: McDermott, D. Planning reactive behavior: A progress report. In K. Sycara, editor, <i>Innovative Approaches to Planning, Scheduling and Control.</i> Morgan Kaufmann, San Mateo, CA, 1990, 450--458.
• 20: Hans Moravec, Sensor fusion in certainty grids for mobile robots, AI Magazine, v.9 n.2, p.61-74, July/August 1988
• 21: Nilsson, N. J. Shakey the robot. Technical Report 323, AI Center, SRI International, Menlo Park, CA, 1984.
• 22: Illah Nourbakhsh , Sarah Morse , Craig Becker , Marko Balabanovic , Erann Gat , Reid Simmons , Steven Goodridge , Harsh Potlapalli , David Hinkle , Ken Jung , David Van Vactor, The winning robots from the 1993 robot competition, AI Magazine, v.14 n.4, p.51-62, Winter 1993
• 23: Nourbakhsh, I. R. and Powers, R. and Birchfield, S. Dervish: An office navigating robot. <i>AI Magazine,</i> Summer 1995, 16(2):53--60.
• 24: O'Sullivan, J., Haigh, K. Z. and Armstrong, G. D. <i>Xavier Manual (Version 0.3).</i> School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1997. Unpublished Internal Manual, available at http://www.cs.cmu.edu/~Xavier/papers.html.
• 25: Payton, D. W., Rosenblatt, J. K., and Keirsey, D. M., Plan-guided reaction. <i>IEEE Transactions on Systems, Man, and Cybernetics,</i> 1990, 20(6):1370--1382.
• 26: Barney Pell , Douglas E. Bernard , Steve A. Chien , Erann Gat , Nicola Muscettola , P. Pandurang Nayak , Michael D. Wagner , Brian C. Williams, An autonomous spacecraft agent prototype, Proceedings of the first international conference on Autonomous agents, p.253-261, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267724]
• 27: Rafflin, C. and Fournier, A. Learning with a friendly interactive robot for service tasks in hospital environments. <i>Autonomous Robots,</i> 1996, 3(4):399--414.
• 28: Alessandro Saffiotti , Kurt Konolige , Enrique H. Ruspini, A multivalued logic approach to integrating planning and control, Artificial Intelligence, v.76 n.1-2, p.481-526, July 1995 [doi>10.1016/0004-3702(94)00088-I ]
• 29: Simmons, R. Structured control for autonomous robots. <i>IEEE Transactions on Robotics and Automation,</i> 1994, 10(1):34--43.
• 30: Simmons, R. The curvature-velocity method for local obstacle avoidance. In Proceedings of the <i>IEEE International conference on Robotics and Automation (ICRA '96),</i> Minneapolis, MN. 1996, 3375--3382. IEEE Press, New York, NY.
• 31: Reid Simmons , Richard Goodwin , Karen Zita Haigh , Sven Koenig , Joseph O'Sullivan, A layered architecture for office delivery robots, Proceedings of the first international conference on Autonomous agents, p.245-252, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267723]
• 32: Simmons, R. and Koenig, S. Probabilistic robot navigation in partially observable environments. In <i>Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95),</i> Montr&eacute;al, Qu&eacute;bec, Canada. 1995, 1080--1087. Springer-Verlag, Berlin, Germany.
• 33: Veloso, M. M., Carbonell, J., P&eacute;rez, M. A., Borrajo, D., Fink, E., and Blythe, J. Integrating planning and learning: The PRODIGY architecture. <i>Journal of Experimental and Theoretical Artificial Intelligence,</i> 1995, 7(1):81--120.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Office automation

General Terms:
Design, Measurement, Performance, Theory