Robots that are highly adaptable and flexible have the potential to have a very broad impact on society, as household helpers, hospital assistants and aides to first responders.  Making that potential a reality will require robots that are substantially more capable of intelligent decision-making than existing robots.

Our overall goal is to develop the estimation, planning, and control techniques necessary to enable robots to perform robustly and intelligently in complex uncertain domains.  Robots operating in such domains have to deal explicitly with uncertainty.  Sensing is increasingly reliable, but inescapably local: robots cannot see, immediately, inside cupboards, under collapsed walls, or into nuclear containment vessels.  Task planning, whether in household or disaster-relief domains, requires explicit consideration of uncertainty and the selection of actions at both the task and motion levels to support gathering information.

In order to explicitly consider the effects of uncertainty and to generate actions that gain information, it is necessary to plan in belief space: that is, the space of the robot's beliefs about the state of its environment, which we will represent as probability distributions over states of the environment.  For planning purposes,the initial state is a belief state and the goal is a set of belief states: for example, a goal might be for the robot to believe with probability greater than 0.99 that all of the groceries are put away, or that there are no survivors remaining in the rubble. 

Planning in belief space beautifully integrates perception and action, both of which affect beliefs in ways that can be modeled and thus exploited to achieve an ultimate goal.  However, planning in belief space for realistic problems poses some substantial challenges: (a) belief spaceis generally a high-dimensional continuous space (of distributions) and (b) the outcomes of actions and (especially) perception makes the process dynamics highly non-deterministic.  

Our approach to robust behavior in uncertain domains is founded on the notion of integrating estimation, planning, and execution in a feedback loop.  A plan is made, based on the current belief state; the first step is executed; an observation is obtained; the belief stateis updated; the plan is recomputed, if necessary, etc.  We call this online replanning.  In contrast to the more typical method offinding a complete policy for all possible belief states in advance, this strategy allows planning to be efficient but approximate: it isimportant that the first step of the plan be useful, but the rest will be re-examined in light of the results of the first step.

A critical component of such a system is a planner that works effectively in very high-dimensional geometric problems that have substantial uncertainty:   robot trying to assemble ingredients for cooking a meal has to work in a space that is made up of the positions, orientations, and other aspects of a large number of objects; it will have localized uncertainty about some of the objects and may have very little information about others.  Planning for the robot is not just motion planning:  it must decide what order to move objects in, how to grasp them, where to place them, and soon.  It must also plan to gain information, including deciding whereto look, determining that it must move objects out of the way to get an unoccluded view, or selecting a cupboard to search for a particularobject it needs.

We have developed a hierarchical approach to solving such planning problems, which performs a temporal decomposition by planning operations at multiple levels of abstraction; this ensures that problems to be addressed by the planner are always reasonably small, making planning feasible.  We have used this planning method...

Please report errors in award information by writing to: awardsearch@nsf.gov.