For a robot to operate in a complex environment over a period of hours or days, it must be able to plan actions involving large numbers of objects and long time horizons. Furthermore it must be able to plan and carry out actions in the presence of uncertainty, both in the outcome of its actions and in the actual state of the world. Thus, key challenges are hedging against bad outcomes, dealing with exogenous dynamics, performing efficient re-planning, and determining conditions for correctness and completeness.
This project will develop an approach to robot planning that addresses these challenges by integrating several key ideas: (1) Planning in belief space, that is, the space of probability distributions over the underlying state space, to enable a principled approach to planning in the presence of state uncertainty; (2) Planning with simplified models and re-planning as necessary to enable planning efficiently with outcome uncertainty while still enabling action choices based on looking ahead into likely outcomes; (3) Combining logical and geometric reasoning to enable detailed planning in large state spaces involving many objects; and (4) Hierarchical planning with interleaved execution to enable plans with very long time horizons by breaking up the planning problem into a sequence of smaller problems.
The methods developed will be tested in a system that combines planning, perception and execution for real physical robots navigating and manipulating objects in real, complex environments. The software developed in this project will be freely available as a collection of ROS (Robot Operating System) modules for easy porting to a wide variety of robots. The research in this project will contribute materials for two courses that the PIs are developing: (1) a lab-based introduction to electrical engineering and computer science based on mobile robots (currently taken by around 500 MIT students per year) and (2) a new project-based senior-level subject on robot planning and perception. All of the materials for these subjects will be available freely through MIT's OpenCourseWare site.
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 for mobile pick-and-place problems on the Willow Garage PR2 robot. In one example, we gave the robot a repeated sequence of goals to place first a (blue) soda box and then a (red) soup can into a region at the left end of a cupboard on a table (see acoompanying image). The initial position of the objects in the cupboard and the position of the robot relative to the cupboard was only known very roughly. The robot executed this sequence several times. The accompanying image shows key frames from the actual executionof the first goal: to place the soda in the target region from its initial position on the top shelf. This required moving the soup canout of the way (since it is blocking the target region) by placing iton the table. Since the initial approach to the soup required asubstantial base motion, the robot performs an observation before grasping, which requires moving the hand out of the way so it can see the soda. Throughout, the robot decides autonomously what sensory information is required and initiates the appropriate perceptual actions. This sequence illustrates the power of the planning and execution system which integrates perception, geometric and probabilistic reasoning, motion planning and decision-theoretic planning.
