Research Interests
I believe automated planning will play a major role in fighting the rapidly growing complexity of our society. The goal of my research is to identify areas in which planning can be beneficially applied and develop planning algorithms, data structures, and domain representations suitable for solving problems within these areas. I am particularly interested in:

Embedded Control. Modern electronic products are comprised of many components that must interact closely in order for the product to work correctly. The complexity of the product must be hidden from the user, but often it is not. By stating the rules of interaction, universal plans can be automatically generated and embedded in the product to change the configuration of subcomponents from one desirable system state to another.

Mission Planning. Planning missions for disaster relief happens in dynamic and unpredictable environments. Large scale planning and scheduling is needed to allocate resources and satisfy temporal constraints. These plans, however, must take uncertainty into account. It is necessary to produce plans that can cope with failures and uncontrollable activity. Re-planning is often a too reactive approach for handling uncertainty. We need planners that upfront make plans robust to failure.

Reconfiguration. Reconfiguration of power grids, processing plants, space probes and other complex electromechanical systems is becoming an overwhelming manual task. Powerful planning and scheduling systems are needed to compute reconfiguration strategies that fulfill the systems safety and activity requirements.

Resynchronization. Robotic production lines have migrated from the car industry to the full range of industries assembling standard consumer products. Too often, however, such production lines have costly down periods due to local errors that make their physical and digital state out of sync. These resynchronization problems require flexible production control with complete state awareness and fault tolerance.

Traffic Safety. It is intriguing that, while large computer systems flawlessly moves billions of bits per second, physical transportation is still a daring task. Traffic control is widely a manual task, but to become safe, it needs to be automated.

 
Approach

For the last 5 years I have focused on a new fusion of symbolic model checking and artificial intelligence (AI). The idea is to depart from an explicit representation of planning domains and instead use an implicit state-space representation and search technique developed in symbolic model checking based on reduced ordered Binary Decision Diagrams (BDDs).

The size of a BDD does not depend on the size of the state-space it represents. For regularly structured domains, it may be exponentially smaller. Since BDD manipulation is polynomial, this compactness translates directly into speed of the BDD-based planning algorithms.

Non-Deterministic Planning

BDD-based planning currently dominates non-deterministic planning since non-sequential conditional plans can be efficiently represented by BDDs. I have developed a specification language NADL and a planning system UMOP for synthesizing plans for non-deterministic domains. UMOP includes all current BDD-based planning algorithms (strong, strong cyclic, and weak). In contrast to previous domain specification languages, NADL defines the behavior of the environment explicitly as a set of uncontrollable agents. An interesting advantage of this approach is that it has made it possible to extend UMOP with algorithms that reason about the actions of the environment to handle situations where the environment is assumed to be adversarial. I am currently working a temporal version of NADL called ASynchronous Evolving Tasks (ASET). ASET seems to be the first planning language for defining durative actions that are non-deterministic both with respect to temporal extension and effects. ASET is targeted towards mission planning, but fits equally well in a discrete event system setting e.g. for manufacturing or embedded control.

Non-deterministic planning and decision theoretic planning are closely related. Basically a non-deterministic planning domain is a Markov Decision Process (MDP) where the transition probabilities have been removed. For this reason, BDD-based non-deterministic planning algorithms typically can handle much larger domains than MDP solvers even when these are based on Algebraic Decision Diagrams (ADDs). The lack of probabilities, however, makes it impossible for non-deterministic planners to identify very unlikely execution paths. To address this problem, I have introduced fault tolerant planning for non-deterministic domains. The idea is to divide actions effects into likely primary effects (success) and unlikely secondary effects (failure) and thus take transition probabilities into account without modeling these directly. In this way, we can recast a plan with high probability of success as a plan with high tolerance for failures occurring during execution. Fault tolerant planning has been demonstrated in a variety of control domains and it has successfully been applied to reconfiguration planning in the Livingstone model of NASA's Deep Space One (DS1) probe used for the Remote Agent Experiment.

Heuristic BDD-Based Search

My thesis introduces a general approach called state-set branching for combining heuristic and BDD-based search. The key idea is to use the image and preimage computation of a disjunctive or conjunctive transition relation partitioning not only to compute the search frontier but also to split it into sets of states associated with identical heuristic search information. Even though partitioning is widely used in model checking, the idea of using a partitioning for propagating heuristic search information is novel. A detailed investigation of state-set branching has been conducted via an implementation of A* called SetA*. SetA* dominates A* when the heuristic is weak. This is a powerful property, since weak heuristics often are easy to define, while strong heuristics can take years or decades to develop (as for the (n-1)^2 - puzzles). In addition to AI-search, state-set branching can be applied to symbolic model checking for fast counter example generation. More interestingly, however, it also applies to strong, strong cyclic, weak, and fault tolerant non-deterministic planning.

Configuration

Lately I have been working on BDD-based configuration. The idea is to compile a BDD representing the solution space of a Constraint Satisfaction Problem (CSP). The approach is particularly useful for interactive configuration where a specialized polynomial BDD operation can be used to compute the possible values of unassigned variables. This enables fast backtrack-free configuration suitable for the internet. An interactive configuration process may also, however, be viewed as an interactive execution of non-deterministic plan for reaching a complete configuration. For some planning problems this approach may suffice and since it only is needed to compute the set of valid states of the domain, it may scale to larger domains than non-deterministic planning.