Search-based Planning for Large Dynamic Environments

Maxim Likhachev

School of Computer Science, Carnegie Mellon University

 

Thesis Committee:

Geoff Gordon (co-chair), Carnegie Mellon University
Sebastian Thrun (co-chair), Stanford University
Manuel Blum, Carnegie Mellon University
Sven Koenig, University of Southern California

 

Abstract

Agents operating in the real world often have to act under the conditions where time is critical: there is a limit on the time they can afford to spend on deliberating what action to execute next. Planners used by such agents must produce the best plans they can find within the amount of time available. The strategy of always searching for an optimal plan becomes infeasible in these scenarios. Instead, we must use an anytime planner. Anytime planners operate by quickly finding a highly suboptimal plan first, and then improving it until the available time runs out.

In addition to the constraints on time, world models used by planners are usually imperfect and environments are often dynamic. The execution of a plan therefore often results in unexpected outcomes. An agent then needs to update the model accordingly and re-execute a planner on the new model. A planner that has a replanning capability (a.k.a. an incremental planner) can substantially speed up each planning episode in such cases, as it tries to make use of the results of previous planning efforts in finding a new plan.

Combining anytime with replanning capabilities is thus beneficial. For one, at each planning episode it allows the planner to produce a better plan within the available time: both in finding the first plan as well as in improving it, the planner can use its replanning capability to accelerate the process. In addition, the combination allows one to interleave planning and execution effectively. While the agent executes the current plan, the planner can continue improving it without having to discard all of its efforts every time the model of the world is updated.

This thesis concentrates on graph-based searches. It presents an alternative view of A* search, a widely popular heuristic search in AI, and then uses this view to easily derive three versions of A* search: an anytime version, an incremental version and a version that is both anytime and incremental. Each of these algorithms is also able to provide a non-trivial bound on the suboptimality of the solution it generates. We believe that the simplicity, the existence of suboptimality bounds and the generality of the presented methods contribute to the research and development of planners well suited for systems operating in the real world.