Project: Greedy On-Line Planning
(scroll down for publications)

Autonomous agents must be able to make good decisions in complex situations that involve a substantial degree of uncertainty, yet find solutions in a timely manner despite a large number of potential contingencies. Unfortunately, planning in non-deterministic domains is typically time-consuming due to the large number of contingencies. Thus, one needs planning techniques that speed up planning by sacrificing the optimality of the resulting plans. Greedy on-line planning methods interleave planning and plan execution to allow agents to gather information early and then use the acquired information right away for replanning, which reduces the amount of planning performed for unencountered situations and thus allows agents to plan efficiently and be reactive to their current situation. Agent-centered search and assumption-based planning are examples of greedy on-line planning techniques.

Agent-centered search restricts planning to the part of the domain around the current state of agents (local search), for example, the current locations of mobile robots. The part of the domain around the current state of agents is the part of the domain that is immediately relevant for them in their current situation because it contains the states that they will soon be in. Agent-centered search methods do not plan all the way from the start state to a goal state. Instead, they decide on the local search space, search it, and determine which actions to execute within it to gain information quickly. Then, they execute these actions (or only the first action) and repeat the overall process from their new state, until the planning task is solved. Examples are greedy localization and greedy mapping, two robot planning methods for localization and mapping, respectively.

Assumption-based planning, on the other hand, plans all the way from the start state to a goal state but makes assumptions about the outcomes of action executions. For example, planning is fast if it assumes that the domain is deterministic by ignoring all outcomes of each action but one. The agents then execute the plan. If an action execution results in a deleted outcome, the agents repeat the process from the state that resulted from the execution of the action, until the planning task is solved. An example is planning with the freespace assumption, a robot planning method for moving to a goal location in unknown terrain.

Both agent-centered search and assumption-based planning determine plans under the (wrong) assumption that agents do not gain information during their execution. This is why they are greedy planning methods. They interleave planning with plan execution and replan right away when the agents do obtain additional information, taking the new information into account. This is why they are on-line planning methods. Both agent-centered search and assumption-based planning trade-off planning time and plan-execution time to make planning fast. They share advantageous properties. For example, they do not need to be in control of the agents at all times and are thus easy to integrate into complete agent architectures.

Greedy on-line planning can be implemented efficiently with fast replanning methods and agent-centered search (real-time heuristic search) methods.

Representative Publications

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.

Home Page of Sven Koenig