Time: Thursday, March 27, 14.30-15.30
Place: C3-204
Automated planning considers selecting and sequencing actions in order to change the state of a discrete system from some initial state to some goal state. This problem is fundamental in control and scheduling and also emerges in verification and theorem proving. Planning is PSPACE-complete, but good average performance has been obtained on deterministic benchmarks. Problems with non-deterministic actions, however, has turned out to be very hard. The currently best known approach is to employ the reduced ordered binary decision diagram (BDD) using techniques developed in symbolic model checking. However, this approach is challenged by a frequent blow-up of the BDDs and a limited number of solution concepts. In this talk, I will address both of these problems. I will first present a general framework called state-set branching that seamlessly combines BDDs and heuristic search. In an extensive experimental study of state-set branching applied to A*, it consistently outperforms the ordinary A* algorithm, except when the heuristic is very strong. In addition, it can improve the complexity of A* exponentially and often dominates both the ordinary A* algorithm and blind BDD-based search by several orders of magnitude. In the second part of the talk, I will show how state-set branching can be used to improve the performance of non-deterministic planning algorithms and finally introduce two new classes of algorithms that models faults and environment actions explicitly in order to produce fault tolerant plans and solutions for problems with adversarial environments.