Rune Møller Jensen

Efficient BDD-Based Planning for Non-Deterministic, Fault-Tolerant, and Adversarial Domains Degree Type: Ph.D. in Computer Science
Advisor(s): Manuela Veloso, Randal E. Bryant
Graduated: August 2003

Abstract:

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 a wide range of industrial and academic fields including robotics, automation, embedded systems, and operational re-search. Planning with non-deterministic actions can be used to model dynamic environments and alternative action behavior. One of the currently best known approaches is to employ reduced ordered Binary Decision Diagrams (BDDs) to represent and generate plans using techniques developed in symbolic model checking. However, the approach is challenged by a frequent blow-up of the BDDs representing the search frontier and a limited number of solution classes. This thesis addresses both of these problems. With respect to the first, it contributes a general framework called state-set branching that seamlessly combines classical heuristic search and BDD-based search. Our experimental results show that the performance of state-set branching often dominates both blind BDD-based search and ordinary heuristic search. In addition, it consistently outperforms any previous approach, we are aware of, to guide a BDD-based search. We show that state-set branching naturally generalizes to non-deterministic planning and introduce heuristically guided versions of the current BDD-based non-deterministic planning algorithms.

With respect to the second problem, the thesis introduces two frameworks called fault tolerant planning and adversarial planning. Fault tolerant planning addresses domains where non-determinism is caused by rare errors. The current solution classes handle this situation poorly by taking all fault combinations into account or produce too weak solutions. The thesis contributes a new class of solutions called fault tolerant plans that are robust to a limited number of faults. In addition, it introduces specialized BDD-based algorithms for synthesizing fault tolerant plans.

Adversarial planning considers situations where non-determinism is caused by uncontrollable, but known, environment actions. The current solution classes of BDD-based non-deterministic planning assume a "friendly" environment and may never reach a goal state if the environment is hostile and informed. The thesis contributes efficient BDD-based algorithms for synthesizing winning strategies for such problems.

Thesis Committee:
Manuela M. Veloso (Co-Chair)
Randal E. Bryant (Co-Chair)
Reid Simmons
Paolo Traverso (IRST, Trento, Italy)

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Automated planning, heuristic search, binary decision diagrams, artificial intelligence, symbolic model checking, controller synthesis