"Classical" Planning under Uncertainty*
Steve Hanks · 1996
Research in the classical paradigm has produced effective representations and algorithms for building courses of actions that achieve an input goal. For the most part these systems has~ also assumed an omnipotent and omniscient agent: the agent knows with certainty the initial state of the world and what changes its actions will make, and is assured that no exogenous forces will change the world. These assumptions result in two features of classical planners: the output is aa artifact that can be proved (by logical deduction) solve the planning problem, and execution-time feedback is irrelevant. While the classical certainty assumptions are justified in some problem domains and are reasonable approximations in others, an intelligent agent must in some cases cope with situations in which it has incomplete information, faulty sensors and effectors, and in which the world sometimes changes in ways the agent cannot predict perfectly. Our research is oriented toward relaxing the classical-planning certainty assumptions whih keeping the essence of the classical representations and algorithms: symbolic state and operator descriptions and problem solving ~- backchaining on goals and action preconditions. This paper describes a line of research oriented toward building planners in the classical style but with probabilistic semantics. The BURIDAN planner uses classical planning techniques to build straight-fine plans (without feedback) that probably achieve a goal; the C-BURIDAN planner extends the representation and algorithm to handle sensing actions and conditional plans. The CL-BURIDAN planner adds the concept of a looping construct. In each case the ability to plan in uncertain domains is gained without sacrificing the essence of classical state-space operators or goal-directed backchaining algorithms.