Event Location: NSH 3305

Abstract: Planning with uncertainty in the model of the environment is a common, and difficult, problem. Typically, any differences in the past observations between two states causes the planner to plan for them as completely different states. This work is based on the fact that not all past observations are relevant to the future actions in the planner. In cases where two nodes in the search space differ only by some past observation, representing them both as a single node reduces the size of the search space. Unfortunately this is not always a correct assumption, as the planner might revisit the location where the differing observation was made (requiring the observation be remembered).

An algorithm, called AVR (assume, validate, repair) is introduced which takes advantage of this characteristic by modifying the search space to avoid the duplicate effort required to plan for different observed values which do not end up affecting a portion of the solution. This algorithm works by assuming that two nodes will have the same solution and combining them, validating that assumption during the rest of the planning cycle, and repairing the search graph if that assumption turns out to be incorrect. In this way it can greedily reduce the size of the search space while still guaranteeing an optimal solution.

Committee:Alonzo Kelly, Chair

Reid Simmons

Maxim Likhachev

Nicholas Roy, Massachusetts Institute of Technology