Nick Roy

Profile picture for user Nick Roy
Associate Professor

As computers become ubiquitous, the range of devices that must understand their physical context will increase substantially. Robots, computers and embedded devices need not only to be able to sense their environment, but should also integrate information from the environment into all decision making. Many of the open questions in robotics are instances of how to integrate spatial and temporal reasoning into computation systems: what are appropriate models of the world, how to automatically build such models, and how to generate reliable actions in the real world.

My research has focussed specifically on the problems that result from uncertainty in the world, such as sensor noise or unpredictable action outcome. Probabilistic, decision-theoretic models have proven to be ideally suited for state estimation in the face of uncertainty; I believe that such models can be equally useful for planning. For example, I have formulated algorithms for a class of planning models called Partially Observable Markov Decision Processes (POMDPs). The POMDP framework is a general model for planning with incomplete information, however, it suffers from substantial computational intractability. My contribution has been an approach for finding approximate policies for large (and currently unsolvable) POMDP models that are relevant to real world systems.

POMDP policies are computed over beliefs (probability distributions over states), and one major source of POMDP intractability is that the space of beliefs grows in dimensionality with the size of the state space. My approach stems from the observation that only certain features of the belief space may be necessary for finding good policies. For instance, many problems exhibit a specific kind of sparse structure in the belief space; by taking advantage of this structure, it is possible to approximate very high-dimensional belief spaces with very low-dimensional representations. I have developed an algorithm that uses a dimensionality reduction technique, called Exponential Family Principal Components Analysis, to find a compact representation of the belief space. By planning only over this low-dimensional space of belief features, the vast majority of implausible beliefs are eliminated from consideration. This approximation allows for much more efficient planning, with relatively little loss in policy performance for many problems.

These kinds of approximation models naturally grow out of real world problems, and I believe it is essential to work with deployed systems, performing real tasks, to gain insight into the best way to address interesting scientific problems. For example, my experience with Minerva, the tour-guide robot in the Smithsonian Museum, led me to develop Coastal Navigation, a motion planning strategy that trades off the costs of motion and of positional uncertainty, to achieve goals with maximum likelihood. I have also been a lead developer of the Nursebot, a robot for assisting nurses and the elderly with daily activities. One of the most valuable lessons from this domain is the need for both state estimation and planning techniques that can cope with a wide variety of human behaviours.

I intend to continue working on the issue of planning under uncertainty, motivated by mobile robots in a variety of environments, but also with regard to a wide range of applications. Unfortunately, existing algorithms are limited in a number of ways. The kinds of environmental models that robots can build reliably is very restricted: while robots can now build two-dimensional maps of connected spaces, the technologies used to build these maps do not scale well to large spaces, to higher dimensions, or to simpler representations for low-power devices. More flexible representations, and algorithms for reasoning about these representations in a wider variety of tasks, are essential for better integration of physical modelling and reasoning in many domains.

I am also very interested exploring robot autonomy, especially in human interaction. Most standard models of interaction are based on abstract game-theoretic principles; consequently, almost no deployed systems make use of these models. Additionally, while there are a wide variety of algorithms for detecting and modelling people, there are few if any principled ways for integrating people into general decision making.

In general, my research reflects the belief that decision-theoretic models give tremendous promise of principled spatial and temporal reasoning, integrated in a range of computational devices. However, there are many open questions, and consequently a great number of scientific challenges and opportunities to which I look forward.