Automated Generation of Understandable Contingency Plans

1 Introduction

Two closely related decision-theoretic planning paradigms have emerged in the area of planning under uncertainty: Markov Decision Processes (MDPs) have become a general framework for planning and reinforcement learning. Contin­ gency Planning (CP) on the other hand emphasizes compact­ ness and understandability of the solution. In both cases, an agent is manipulating an environment by performing actions with uncertain outcomes. In each move, the agent receives some reward and the overall goal is to maximize the cumula­ tive reward.

MDPs are solved by deriving a policy which maps domain states to actions, typically represented as a large table. Sev­ eral existing algorithms can construct optimal policies, but the results are not easy to visualize or understand. CP is an­ other widely used approach in stochastic domains which al­ lows plans to include branches that may depend on arbitrary memory states.

It is clear why optimal plans are desirable, but the issue of understandability is less obvious. In fact, for some ap­ plications, a plan represented as a large table mapping states to actions may be perfectly suitable. However, the lack of clarity has limited the adoption ofMDP planning in some ap­ plication domains such as space exploration with unmanned rovers. In this domain, communication with the agent is re­ stricted and due to high mission costs and associated risks, understanding and verifying plans are crucial.

We examine the relationship between policies and contin­ gency plans and define a precise measure of complexity of contingency plans. Then, we introduce a technique for auto­ mated contingency plan generation and briefly describe our experimental results. Finally, we conclude with a summary and future research directions.

2 Formal Problem Description

A Markov Decision Process (MDP) with goal states is a tu­ ple (S, A, P, R, so, G), where S = 81 x · · · x Sn is a fac­ tored state space and Si is the (finite) domain of feature i. A is a set of actions, P the transition probabilities, R the re­ ward expectations, s0 a known initial state and G a (possibly empty) set of absorbing terminal states.

A policy 1r : S --+ A is a mapping from states to ac­ tions. Following the notation in [Littman et al., 1998], a Contingency Plan for an MDP is a tuple (V, E, Vo, p, o), where (V, E) is a directed graph with start state v0 E V. p : V --+ A associates and action with each node of the graph. o : E --+ 2 8 labels each edge with a set of states.

An interval label descriptor maps state sets to sets of intervals over the feature domains defined as follows: 'Dint(o) E --+ {I1, ... ,Ik} where Ij is the set: {(Ll; Ul], ... , [Ln; Un]II ~ Li ~ ui ~ ISiJ'v'l ~ i ~ n}.

The complexity of a contingency plan does not reflect the computational complexity of constructing it, but is a measure of how hard it is to understand. Formally: Com­ plex(MDP,CP,'Dint(o))=JVI · ABF · ALDS, where ABF is the average branching factor of the graph and ALDS is the average label descriptor size. The size of a single label de­ scriptor is the number of constrained intervals.

The value of a policy reflects the expected discounted re­ turn when the agent selects action using 1r, starting from the initial state. It can be computed with standard algorithms such as value iteration. Similarly, the value of a contingency plan is the expected discounted return when the agent selects ac­ tion using p, starting from the initial node. By considering the Markov chain induced by the state set S x V, the same meth­ ods used to evaluate MDP policies can be used to evaluate a contingency plan.

3 Automated Contingency Plan Generation

Our approach to automatically generate more understandable (less complex) contingency plans relies on solving first the underlying MDP, obtaining an optimal policy 1r and creat­ ing an equivalent initial contingency plan from it: V = {vl, ... ,VIAI}, E = v XV, p(vi) = 7r(ai), o(vi,Vj) = {s E Sl1r(s) = aj}. Then, the following operators are used to reduce the complexity of the plan.

By performing a depth-first search over the set of all reach­ able edges between the state-node pairs inS x V, a reach­ ability analysis can be applied to remove states from label descriptors, edges from nodes and nodes from the graph.

Since a benefit of interval label descriptors is the ability to capture easily large sets of states and simplify the branch conditions, n-dimensional boxes to describe them more com­ pactly can be generated by merging intervals along the di­ mensions of the state space. This is in particular very effec­ tive if the order of feature values corresponds to some natural ordering.

By trading off optimality for clarity, interval descriptors can be merged even if there are a few states that make the merge operator not admissible.

Most importantly, the node-split operator splits a node of the plan graph into two and adapts the incoming and outgoing edges according to a given partition of the state space. This gives contingency plans their real strength: The current node of the graph then represents partial information about the cur­ rent state ("context information"), so less details of the actual state may be needed to make the branch decision on the next step. For instance, with a state setS = { u, v, w, x, y, z} and the partition 5 1 = {u,v,w},S2 = {x,y,z},theresultofa split operator is illustrated below:

4 Experimental Results

It turns out that combining these operators can significantly reduce the complexity of a contingency plan. This leads to the following search problem: Given the initial contingency plan defined above, find a contingency plan with the lowest com­ plexity, not giving up more that a certain fraction € of the op­ timality of the policy 1r. Unfortunately, two major obstacles make an exhaustive search intractable: The node-split oper­ ator is parameterized by a partition of the MDP state space, leading to a large number of possible splits and thus to a large branching factor. In addition, the computational complexity of reachability analysis is fairly high.

As a result, we decided to relax the requirement of mini­ mizing complexity and developed a method to combine the operators and automatically generate some understandable plans. Performance improvement can be obtained by choos­ ing a partition of the state space, split the nodes according to this partition, perform a reachability analysis and merge the interval descriptors subsequently. We implemented a hill­ climbing algorithm that used some domain-specific heuristics for choosing a partition and performed random restarts, lead­ ing to an interruptible anytime algorithm that performed well on a simple set of test problems.

For instance, in a maze domain with stochastic move ac­ tions, the algorithm took advantage of bottlenecks, tunnels and alternative branches. In a simulated planetary rover do­ main with uncertain action durations, some hints for good split partitions lead to dramatically decreased complexity. The resulting plan instructed the agent to perform certain ac­ tions until a resource (one feature of the factored state space) drops below a certain threshold. This was very easy to under­ stand for humans unlike the optimal policy given in the form of a huge lookup-table.

5 Conclusions

The main objective of this work has been to find solutions for decision-theoretic planning problems that are optimal (or near-optimal) and also compact and understandable. We de­ fined a measure of the complexity of contingency plans, re­ flecting their size, branching factor and the size of the label descriptors. The results we gained by experimenting with several plan-transformation operators are encouraging and show the potential of automated generation of understandable contingency plans.

There are several interesting directions for future research. First, a better measure of the plan complexity could be devel­ oped. Second, additional operators could be added. Third, the language for representing edge labels could be enriched. Finally, methods for finding good split partitions have to be found to create more reliable algorithms. The results reported in this paper provide a good framework for future exploration of these research directions.

Acknowledgments

Support for this work was provided in part by NASA under grant NAG-2- 1463. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not reflect the views of NASA.