### Rune Jensen

*Carnegie Mellon School of Computer Science*

**Time: Thursday, March 27, 14.30-15.30**

**Place: C3-204**

### Efficient BDD-based Algorithms for Heuristic Search
and Automated Planning

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.