Aero-Astro Magazine Highlight

Social robots, smart systems

By Nicholas Roy

Decision-theoretic models and principled spatial and temporal reasoning will increasingly be an essential capability for any computational device that must operate for any length of time.

Nicholas Roy is developing intelligent estimation and planning algorithms that allow his robot dog to learn the shape of the ground via data from sensors such as the laser on its back. The dog applies the information to select footholds as it traverses rugged and uneven terrain. (William Litant photograph)

Unmanned vehicles that can deliberately move around and accomplish complex tasks without human intervention rely both on their knowledge of the world around them and their location in it. For example, even basic navigation and control largely requires external positioning systems such as GPS and pre-existing maps of the world. In indoor domains or the urban canyon, accurate maps and GPS are usually not available, greatly limiting the extent to which unmanned vehicles can be utilized in these domains. Unmanned air vehicles typically cannot fly autonomously in the urban canyon, and unmanned ground vehicle control often falls back on human operators.

My goals are to build unmanned vehicles that can fly without GPS through unmapped indoor environments and unmapped cities, to build social robots that can quickly learn what the user wants without being annoying or intrusive, and to build smart systems that know how to allocate their own computational resources. To accomplish this vision, I am developing intelligent inference and planning algorithms for autonomous unmanned vehicles that do not rely on external infrastructure, pre-existing maps or models. These algorithms will lead to robots that can immediately start autonomous operations with no prior information, automatically learning and adapting to the world around them in real-time, allowing them to be more easily deployed in new environments.

Mapping challenges

However, a technical limitation is that most existing intelligent decision-making algorithms assume that the world is known accurately and precisely. For example, robotics has seen tremendous growth in the deployment of autonomous systems that can build their own robust models from partial or noisy sensor information. Statistical inference algorithms allow a robot to collect sensor data (such as camera images or range data) and assemble this data into a globally consistent map of the world. Once enough data has been collected and a complete and precise map has been generated, it can then be used by a robot to plan tasks and trajectories through the environment. Even though the mapping process understands how the effects of sensor noise and incomplete observations must be captured in the map, the underlying assumption of the planner is that the map is correct and complete. As a result, robotic planners often cannot be used with partial, incomplete, or uncertain maps. Furthermore, autonomous vehicles do not have a way to make decisions about how to complete the map, or even what additional information is needed for the task at hand.

Separating modeling and planning into two distinct processes has long simplified both problems, but for many domains, building complete and accurate maps becomes increasingly difficult, and the planner becomes susceptible to model errors. If the planner does not understand how to learn more about the world, the robot cannot plan sensing actions to improve its own performance. I refer to this problem as the “model-uncertainty” planning problem, where an autonomous vehicle must know how to make decisions with incomplete and uncertain knowledge as it learns about the world around it.

Previous work in this area has led to algorithms for efficient planning with restricted forms of uncertainty where the domain is small or the uncertainty has few degrees of freedom, allowing computationally efficient representations and solution techniques. However, planning in uncertain and incomplete models is a much larger class of problems, where the size and structure of the domain is much less tractable. As a result, my group is using machine learning techniques as a robust and computationally tractable way to address the model-uncertainty planning problem. Machine learning gives planning algorithms a way to find structure in this class of problems and form good policies, trading the additional cost of learning for dramatically reducing the cost of solving new problems. Learning requires substantial initial investment in training the system, but in most cases yields very fast responses after training. Learning can also be carried out incrementally, giving algorithmic robustness in domains that can change over time.

While Nicholas Roy looks on, grad student Ruijie He inspects an autonomous wheelchair, an intelligent assistive technology project under development in Roy's lab. The goal is to make assistive devices such as wheelchairs usable by a wider group of people with cognitive and physical deficits, and to develop smart interaction technologies that make the devices easier to use. (William Litant photograph)

My group is applying these ideas in a variety of domains, given by the following example applications.

The belief roadmap algorithm

One example problem my group has studied is trajectory planning for a micro air vehicle navigating indoors using a laser range finder of limited range to track its position. When the laser range finder cannot sense the local environment (e.g., in the middle of a large room), the vehicle can become lost and the vehicle velocity estimate can begin to drift substantially, leading both to errors in the desired trajectory and high-speed collisions with objects in the environment. By incorporating the uncertainty of the sensor data into the planning process using an algorithm known as the “belief roadmap” algorithm, we can construct large trajectories in high-dimensional spaces as efficiently as conventional trajectory planners that assume a known position estimate. The BRM algorithm allows the MAV to fly reliably and autonomously in locations that are normally inaccessible to unmanned air vehicles.

A second example problem is trajectory generation for vehicles exploring an unknown environment. When a robot is exploring a new environment, there is a natural tension between investigating as much of the environment as possible, and revisiting already-explored parts in the process of firming up the knowledge the robot already has. Balancing these two competing objectives is an optimization problem that cannot be solved efficiently. Instead, we have shown that reinforcement learning algorithms can be used to learn good exploration strategies from the robot's previous experience of different strategies. We are also applying this reinforcement learning technique to the problem of sensor trajectory planning in the weather domain to enable a team of UAVs making weather measurements to maximize the accuracy of prediction models. Furthermore, we are using related learning techniques to allow a quadruped robot to learn three-dimensional models of terrain from sensor data as it walks.

This coupling of terrain model learning and planning allows legged robots to walk across rugged and uneven surfaces without prior maps of the terrain.

We have shown that the same technologies can be used to optimize a human-robot interaction system. We are developing a robotic wheelchair for use by people with limited motor control but high-level cognitive function. Our goal is to develop an intelligent dialogue system that can interact with a human in the wheelchair using natural language to understand what the human wants the wheelchair to do. While human-robot interaction may appear to be a dramatically different problem than map exploration, it can be framed as a model-uncertainty planning problem, where the sensor data is now a speech-recognition system, and the decision-making involves choosing how to respond to human requests. Existing dialogue interaction systems describe how to interact with people assuming a known behavioral model that includes vocabulary, word preferences, and how the user’s intentional behaviors can change over time. If however, the model is inconsistent with the actual person’s behavior, the robot may do exactly the wrong thing, leading to failures and user frustration. The objective of model-uncertainty planning in this domain is to learn a model of human behavior during dialogue with a robot. Given an initial, approximate estimate over possible behavior models, we can converge to a good estimate of user preferences more quickly and generate good dialogue policies. This allows us to generate dialog policies that are accurate with limited prior knowledge and minimal user training.

I intend to continue working on the issue of planning under uncertainty, motivated by autonomous vehicles in both remote and populated environments, but also with regard to a wide range of applications. In general, my research reflects the belief that decision-theoretic models and principled spatial and temporal reasoning will increasingly be an essential capability for any computational device that must operate for any length of time; there are many open questions, and, consequently, a great number of scientific challenges and opportunities.

Nicholas Roy is an Assistant Professor in the Massachusetts Institute of Technology Aeronautics and Astronautics Department. He received a B.Sc. and an M.Sc. from McGill University (1995 and 1997), and his Ph.D. from Carnegie Mellon University (2003). His specializations include robotics, machine learning, autonomous systems, planning and reasoning, and human-computer interaction. He may be reached at nickroy@mit.edu.