NSF-BSF: RI: Small: Planning and Acting While Time Passes

University Of New Hampshire, Durham NH

Investigators

Abstract

Planning allows intelligent systems to select actions aimed towards achieving their goals. However, traditional planning methods assume that the world evolves slowly enough, or that the problems to be solved are sufficiently simple, that the world can be considered static during planning. This limitation means that most current planners are unable, for example, to realize that it might be better to quickly find a suboptimal plan to take the bus that is about to leave, rather than to carefully deliberate about optimal plans and thereby miss the bus altogether. Currently, planning representations and algorithms are laboriously manually engineered to ensure that the system responds quickly enough for the intended application, essentially ducking the issue of the passage of time while the system is planning. This project enables more robust and general-purpose intelligent systems by developing new "situated planning" methods that reason about their own reasoning enough to overcome this limitation. The project will consider two settings for situated planning. The first is the traditional batch setting, in which all decisions are made before plan execution begins. Three challenges will be addressed: 1) Formalizing a model of planning while time passes and analyzing its computational complexity, 2) Simplifying the resulting "reasoning about reasoning" problem enough that it can be approximately solved repeatedly during the planning process, including identifying tractable subclasses and greedy heuristics, and 3) Estimating the information needed for doing this reasoning on-line. The second setting is incremental planning, where execution of actions can be interleaved with additional planning. Three additional challenges will be addressed: 4) Formalizing situated planning with action costs , 5) Developing a continual situated planner that improves a plan while it is being executed, and 6) Addressing online situated planning, where actions can be dispatched for execution before a complete plan has been found. Solving these situated planning problems will result in practical and flexible planners that can smoothly interpolate their behavior in a time-aware way between batch and incremental as appropriate, thereby broadening the range of applications that can be addressed by intelligent systems. Project results will be integrated into the open source OPTIC planner and ROSPlan robot control framework. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.