|
Autonomous agents that act in the real-world can often improve their success by capturing
the uncertainty that arises because of their imperfect knowledge and potentially faulty actions. By
making plans robust to uncertainty, agents can be prepared to counteract plan failure or act upon
information that becomes available during plan execution. Such robust plans are valuable, but are
often difficult to construct when uncertainty is high and goal achievement requires many actions.
Unfortunately, current approaches to planning under uncertainty are not scalable: they focus on
small problems where the challenge is finding an optimal solution.
I study (non-deterministic and probabilistic) conformant and conditional planning in large
problems where just finding a feasible solution is the challenge. I develop scalable heuristic search
techniques that are inspired both by optimal approaches to planning under uncertainty (based on
Markov decision processes) and scalable approaches for classical planning (based on planning graph
reachability heuristics). Specifically, I develop measures for the cost of completing partial plans,
heuristics that estimate the measures, efficient data-structures and inference techniques to compute
the heuristics, and a multi-objective heuristic search algorithm that uses the heuristics. Through
extensive empirical evaluation, I show the resulting set of techniques significantly improves the
scalability of planning under uncertainty.
| |
