Efficient BDD-Based Planning for Non-Deterministic, Fault-Tolerant, and Adversarial Domains

摘要

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. 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). 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. 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 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.