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

Planning allows intelligent systems, such as robots and web agents, to select actions aimed at achieving their goals. However, traditional planning algorithms 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 current planners are unable, for example, to realize that it might be better to quickly find a sub-optimal 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. This project enables more robust and general—purpose intelligent systems by developing new ‘situated planning’ algorithms that are self-aware enough to overcome this limitation.

We adopt the popular framework of planning as heuristic search and consider two settings for situated planning. The first is the traditional batch setting, in which all decisions are made before execution begins. We address three main challenges: 1) How to formalize a heuristic search meta-level model of planning while time passes, and how hard is it to solve (‘computational complexity”). 2) How to simplify the resulting meta-level problem so that it can be approximately solved repeatedly in real—time during the planning process, using effective greedy schemes and heuristics. And 3) how to quickly estimate the information needed for metareasoning. We extend prior work on time-aware search strategies with the rich heuristic information available in domain—independent planning, resulting in practical situated planning methods.

Second, we consider the setting where planning is interleaved with action execution, through incremental planning. This generalizes batch planning and covers the ease in which a currently executing plan can be improved on the fly. There are three additional fundamental challenges here: 4) Including tradeoffs of plan quality in the meta-level model, in a scheme that attempt to improve plan quality at little risk of failure due to excessive planning time. 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. This involves allocating planning time between the current decision and future decisions, again a meta-level problem. Solving these problems will result in flexible planners that can robustly change their behavior in a time—aware way between batch and incremental as needed due to real—time constraints.