Figure 1
Mobile robots have long held a fascination, from science fiction (Star Wars' R2D2 and C3PO, Forbidden Planet's Robby) to science fact. For artificial intelligence researchers, the lure has been to enable a machine to emulate the behavioral, perceptual, and cognitive skills of humans, and to investigate how an artifact can successfully interact, in real time, with an uncertain, dynamic environment. While most research has focused on autonomous navigation and on software architectures for autonomous robots, mobile robots have also been used for investigating planning, MANIPULATION AND GRASPING, learning, perception, human-robot interaction (such as gesture recognition), and robot-robot (multiagent) interaction. Representative applications for mobile robots include service robots (mail delivery, hospital delivery, cleaning), security, agriculture, mining, waste remediation and disposal, underwater exploration, and planetary exploration, such as NASA's Sojourner Rover on Mars.
At the most basic level, mobile robots must perceive the world, decide what to do based on their goals and perceptions, and then act. The first two issues are the most challenging: how to reliably perceive the world with uncertain, unreliable sensors, and how to make rational decisions about what to do in the face of UNCERTAINTY about the perceived world and the effects of actions (both the robot's and those of other agents). For example, a mobile robot for the home must perceive furniture, stairs, children, pets, toys, and so on, and decide how to act correctly in a myriad of different situations.
Early work in indoor mobile robots demonstrated some basic capabilities of robots to perceive their environment (e.g., Stanford's CART; Moravec 1983), plan how to accomplish relatively simple tasks (e.g., SRI's Shakey; Fikes, Hart, and Nilsson 1972), and successfully move about in (relatively) unstructured environments. Early outdoor mobile ro-bots, such as Carnegie Mellon's Navlab (Thorpe 1990), demonstrated similar capabilities for on-road vehicles. For these robot systems, speed was not much of an issue, nor was reacting to a dynamically changing environment -- it was enough just to operate successfully using a sequential perceive/decide/act cycle in a previously unknown, albeit static, world. These and similar efforts resulted in new planning and plan execution algorithms (e.g., STRIPS; Fikes, Hart, and Nilsson 1972; see also PLANNING), new techniques to perceive the environment (Moravec 1983, 1988), and new software architectures for integrating and controlling complex robot systems (Thorpe 1990).
Starting in the mid-1980s, research focused more heavily on improving capabilities for navigating in more unstructured, dynamic environments, which typically involved handling greater levels of uncertainty. Notable advances were made in perceiving obstacles, avoiding obstacles, and in map-based navigation (following a map to get from location to location, without getting lost).
A key component to successful navigation is reliable perception of objects (obstacles) that may impede motion. For indoor mobile robots, a ring of ultrasonic sensors is often used for obstacle detection. These sensors give reasonably good range estimates, and the data can be improved by integrating measurements over time to reduce sensor noise (e.g., the occupancy grids of Moravec 1988). Outdoor robots often use stereo vision (see also MACHINE VISION and STEREO AND MOTION PERCEPTION). While computationally expensive, stereo has the advantages of being able to detect objects at greater distances and with good resolution. It also gives three-dimensional data, which is important for outdoor, rough-terrain navigation. Color vision has also been successfully employed, especially to detect boundaries, such as between walls and floors. Other researchers have investigated using lasers (e.g., Sojourner), radar, and infrared sensors to detect objects in the environment.
Deciding how to move is often divided into local navigation (obstacle avoidance), for reacting quickly, and global, map-based navigation, for planning good routes. Many techniques have been developed for avoiding obstacles while continuing to move toward some desired goal. The potential field approach (Khatib 1985; Arkin 1989) treats obstacles as repulsive forces and goals as attractors. The vector sum of all forces is used to determine the desired robot heading. This calculation can be done very quickly, enabling robots to avoid moving obstacles, as well. The vector field histogram approach (Borenstein 1991) essentially looks for wide openings through which to head. It overcomes some of the problems the potential field approach has in dealing with crowded environments. More recently, real-time obstacle avoidance algorithms have been developed that take the robot's dynamics into account, enabling much higher travel speeds (Fox, Burgard, and Thrun 1997). Also, approaches using machine learning techniques to learn how to avoid obstacles have proven effective, especially for high-speed highway travel (Thorpe 1990; see also ROBOTICS AND LEARNING and REINFORCEMENT LEARNING)
Early approaches to global, map-based navigation were based on metric maps -- geometrically accurate, usually grid-based, representations. To estimate position with respect to the map, robots would typically use dead reckoning, (also called "internal odometry" -- measuring position and orientation by counting wheel rotations). Such approaches were not very reliable: Position, and especially orientation, error would gradually increase until the robot was hopelessly lost. (On the other hand, widespread use of the Global Positioning System or GPS and inertial navigation units or INUs have made position estimation a non-issue for many outdoor robots.)
To avoid this problem of "dead reckoning error," and to avoid the need for geometrically accurate maps, researchers developed landmark-based navigation schemes (Kuipers and Byun 1993; Kortenkamp and Weymouth 1994). In these approaches, the map is represented as a topological graph, with nodes representing landmarks ("important places," such as corridor junctions or doorways) and with arcs representing methods for traveling from landmark to landmark (e.g., "Turn right and travel forward, using local obstacle avoidance"). Each landmark is associated with a set of features that can be used by the robot to determine when it has arrived at that place. Researchers have used both sonar (e.g., to detect corridor junctions) and vision as the basis for defining landmarks (Kortenkamp and Weymouth 1994). Landmark-based navigation can be fairly reliable and is readily amenable to learning a map of the environment. It has difficulties, however, in situations where landmarks can be easily confused (e.g., two junctions very near one another) or where the robot misses seeing particular landmarks.
Figure 1
To combine the best of the metric and landmark-based schemes, some researchers have investigated probabilistic approaches that explicitly represent map, actuator, and sensor uncertainty. One approach uses partially observable Markov decision process (POMDP) models to model the robot's state -- its position and orientation (Nourbakhsh, Powers, and Birchfield 1995; Simmons and Koenig 1995). The robot maintains a probability distribution over what state it is in, and updates the probability distribution based on Bayes's rule as it moves and observes features (see also HIDDEN MARKOV MODELS). The robot associates actions with either states or probability distributions, and uses its belief state to decide how to best move. Such probabilistic navigation approaches tend to be very reliable: While the robot may never know exactly where it is, neither does it ever (or rarely) get lost. The approach has been used in an office delivery robot, Carnegie Mellon's Xavier (Simmons et al. 1997; see figure 1), which has traveled over 150 kilometers with a 95 percent success rate, and in a museum tour guide robot, Bonn University's Rhino, which has a greater than 98 percent success rate in achieving its intended tasks.
A sequential perceive/decide/act cycle is often inadequate to ensure real-time response. Mobile robots must be able to do all this concurrently. To this end, much research in mobile robots has focused on execution architectures that support concurrent perception, action, and planning (see also INTELLIGENT AGENT ARCHITECTURE). Behavior-based architectures consist of concurrently operating sets of behaviors that process sensor information and locally de-termine the best action to take (Brooks 1986; see also BEHAVIOR-BASED ROBOTICS). The decisions of all applicable behaviors are arbitrated using different types of voting mechanisms. Behavior-based systems tend to be very reactive to change in the environment and can be very robust, but it is often difficult to ensure that unintended interactions among behaviors do not occur. An executive (or sequencer) is often used to manage the flow of control in robot systems. The executive is typically responsible for decomposing tasks into subtasks, sequencing tasks and dispatching them at the right times, and providing constructs for monitoring execution and handling exceptions (Firby 1987; Gat 1996; Simmons 1994). Tiered (or layered) architectures integrate planners, an executive, and behaviors in a hierarchical fashion, to enable very complex and reliable behavior (Bonasso et al. 1997). While such layered architectures are relatively new, they have proven to be quite flexible and are rapidly gaining popularity. Other architectural approaches include layers of more and more abstract feedback loops (Albus 1991) and architectures where the role of the planner is to provide schedules that can be guaranteed to run on a real-time system (Musliner, Durfee, and Shin 1993).
Albus, J. (1991). Outline for a theory of intelligence. IEEE Transactions on Systems, Man and Cybernetics 21(3):473-509.
Arkin, R. (1989). Motor schema-based mobile robot navigation. International Journal of Robotics Research 8(4):92-112.
Bonasso, R. P., R. J. Firby, E. Gat, D. Kortenkamp, D. Miller, and M. Slack. (1997). Experiences with an architecture for intelligent, reactive agents. Journal of Experimental and Theoretical Artificial Intelligence 9(2).
Borenstein, J., and Y. Koren. (1991). The vector field histogram: Fast obstacle avoidance for mobile robots. IEEE Transactions on Robotics and Automation 7(3):278-288.
Brooks, R. (1986). A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automation RA-2(1).
Fikes, R., P. Hart, and N. Nilsson. (1972). Learning and executing generalized robot plans. Artificial Intelligence 3:1-4.
Firby, R. J. (1987). An investigation into reactive planning in complex domains. In Proceedings of the Sixth National Conference on Artificial Intelligence, San Francisco: Morgan Kaufman, pp. 202-206.
Fox, D., W. Burgard, and S. Thrun. (1997). The dynamic window approach to collision avoidance. IEEE Robotics and Automation 4(1):23-33.
Gat, E. (1996). ESL: A language for supporting robust plan execution in embedded autonomous agents. In Proceedings AAAI Fall Symposium on Plan Execution: Problems and Issues. Boston, MA: AAAI Press, Technical Report FS-96-01.
Khatib, O. (1985). Real-time obstacle avoidance for manipulators and mobile robots. In Proceedings IEEE International Conference on Robotics and Automation, St. Louis, pp. 500-505.
Kortenkamp, D., and T. Weymouth. (1994). Topological mapping for mobile robots using a combination of sonar and vision sensing. In Proceedings of the Twelfth National Conference on Artificial Intelligence, Seattle.
Kuipers, B., and Y. Byun. (1993). A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems 8:47-63.
Moravec, H. (1983). The Stanford Cart and the CMU Rover. Proceedings of the IEEE 71:872-884.
Moravec, H. (1988). Sensor fusion in certainty grids for mobile robots. AI magazine 9(2):61-74.
Musliner D., E. Durfee, and K. Shin. (1993). CIRCA : A cooperative intelligent real-time control architecture. IEEE Transactions on Systems, Man, and Cybernetics 23(6).
Nourbakhsh, I., R. Powers, and R. Birchfield. (1995). DERVISH : An office-navigating robot. AI magazine 16:53-60.
Simmons, R. (1994). Structured control for autonomous robots. IEEE Transactions on Robotics and Automation 10(1):34-43.
Simmons, R., and S. Koenig. (1995). Probabilistic navigation in partially observable environments. In Fourteenth International Joint Conference on Artificial Intelligence, San Francisco: Morgan Kaufman, pp. 1080-1087.
Simmons. R, R. Goodwin, K. Z. Haigh, S. Koenig, and J. O'Sullivan. (1997). A layered architecture for office delivery robots. In First International Conference on Autonomous Agents. Marina del Rey, CA.
Thorpe, C., Ed. (1990). Vision and Navigation: The Carnegie Mellon Navlab. Norwell: Kluwer.
Arkin, R. (1998). Behavior-Based Robotics. Cambridge, MA: MIT Press.
Balabanovic, M., et al. (1994). The winning robots from the 1993 Robot Competition. AI magazine.
Brooks, R. (1991). Intelligence without representation. Artificial Intelligence 47(1-3): 139 - 160.
Hinkle, D., D. Kortenkamp, and D. Miller. (1995). The 1995 Robot Competition and Exhibition (plus related articles in same issue). AI magazine 17(1).
Jones, J., and A. Flynn. (1993). Mobile Robots: Inspiration to Im-plementation. Wellesley: Peters.
Kortenkamp, D., I. Nourbakhsh, and D. Hinkle. (1996). The 1996 AAAI Mobile Robot Competition and Exhibition (plus related articles in same issue). AI magazine 18(1).
Kortenkamp, D., P. Bonasso, and R. Murphy, Eds. (1998). Artificial Intelligence and Mobile Robots. Cambridge, MA: MIT Press.
Raibert, M. (1986). Legged Robots That Balance. Cambridge, MA: MIT Press.
Simmons, R. (1994). The 1994 AAAI Robot Competition and Exhibition (plus related articles in same issue). AI magazine 16(2).
Song, S., and K. Waldron. (1989). Machines That Walk: The Adap tive Suspension Vehicle. Cambridge, MA: MIT Press.
Copyright © 1999 Massachusetts Institute of Technology