Research Abstracts - 2007

Introduction

For autonomous artificial decision-makers to solve realistic tasks, they need to deal with searching through large state and action spaces under time pressure. We study the problem of planning in such domains and show how structured representations of the environment's dynamics can help partition the action space into a set of equivalence classes at run time. The partitioned action space is then used to produce a reduced set of actions. This technique speeds up search and can yield significant gains in planning efficiency. We want planning techniques that can deal with large state spaces and large, stochastic action sets, since most compelling, realistic domains have these characteristics.

Intelligent agents that operate continuously in highly complex domains (household robots, office assistants, logistics support systems) will have to solve planning problems ``in the wild''; that is, problems that are formulated as subproblems of very large domains. This is in contrast to most planning problems addressed today, which are carefully formulated by humans to contain only domain aspects actually relevant to achieving the goal. Generally speaking, planning in a formalized model of the agent's entire ``wild'' environment will be intractable; instead, the agent will have to find ways to reformulate the problem into a more tractable version that contains only the relevant information.

One source of difficulty in a complex domain is the existence of large numbers of objects that are either irrelevant to the planning problem or, worse, relevant but unnecessary. Consider an assembly robot, with a box of thousands of identical gears. The robot needs one of those gears to do its job, so those gears aren't irrelevant. But, because they are equivalent, it ought to be able to consider only a single one of them. Our goal in this work is to exploit the effective equivalence of objects in order to simplify planning.

The complexity of planning is driven primarily by the length of the solution and the branching factor of the search. The solution length can sometimes be effectively reduced using hierarchical techniques. The branching factor can often be reduced, in effect, by an efficient heuristic. We will provide a novel method for reducing the branching factor by dynamically grouping the agent's actions into state-dependent equivalence classes, and only considering a single action from each class in the search. This method can dramatically reduce the size of the search space, while preserving correctness and completeness of the planning algorithm. It can be combined with heuristic functions and other methods for improving planning speed.

Planning Strategy

A typical forward-search planner has the basic structure:

1. Start with agenda containing the ground initial state s_0
2. Select a state s from the agenda
3. If s satisfies the goal, return
4. Find the set A of ground actions applicable in s
5. For each a \in A, add the successor of s under a to the agenda; return to step 2

Our approach will replace step 4 with: 4'. Find the set A of equivalence classes of actions applicable in s, which will only generate a single successor state for each equivalence class.

The figure below illustrates this method. Consider a domain with three helicopters and two aircraft carriers in which the goal is to fly each of the helicopters onto a carrier, but in which we don't care which helicopters are on which carriers. We'll just consider a single action schema {\em fly(h,c)} that moves a helicopter from the ground to a carrier. In this figure, we have an example domain in which the task is to fly each of the three helicopters onto one of two carriers. In part (a) is a cartoon of the search tree if we were to enumerate all the ground actions. However, there are only a few qualitatively different states, shown zoomed-in in part (b), which shows the much-reduced tree derived from action-equivalences. If we could eliminate distinguishing between actions that produce equivalent states, as in this example, our search tree would be much more compact.

Initially, all of the helicopters are interchangeable and so are the carriers; so, all of the actions involving flying a helicopter to a carrier are equivalent, and one of them ( fly(h1,c1)) is chosen arbitrarily. At this point, h1 is distinct from h2 and h3, and the two carriers are distinct from one another. There are four possible actions, but we find that fly(h2,c1) is equivalent to fly(h3,c1) and that fly(h2,c2) is equivalent to fly(h3,c2), so we really only have a branching factor of two. Now there are two distinct states in our search: (A) in which there are two helicopters on one carrier and (B) in which there is one helicopter on each carrier. In state (A) there are two distinct actions, because the carriers are distinct; in state (B) there is only one action, because the carriers have become equivalent again. This dynamic process of discovering action equivalence is very powerful, making only as many distinctions as necessary.

Experimental Validation

We performed a study to illustrate the computational savings of planning with equivalence-class sampling. We compared three algorithms in two domains.

The first set of experiments was done in the ICAPS 2004 blocks-world domain [1] in which the number of blocks is increased. The second set of experiments was done in an adaptation of the AIPS 2002 ``depot'' domain [2], a logistics domain, in which the number of crates in the domain increases.

In the figure above, we compare algorithm performance when the problem difficulty increases solely as a function of domain size. Reducing the branching factor by using equivalence classes keeps growth small. At left, results for the blocks-world domain; and, at right, for depot.

And here, we compare, at each plan step, the number of ground actions in the whole ground action space (dashed line) vs. the number expanded when using equivalence partitions (solid line). Note the log scale on the y-axis. Curves are shown for a selection of domains to avoid clutter: 7, 32 and 100 blocks, and 5, 50, and 200 crates.

Conclusion

The principal contribution of this work is to establish that a planning procedure that uses only equivalence-class representatives is complete whenever the original planning procedure, which had access to the whole action space, is complete. We need the following pieces: first, whenever goal is satisfied in a particular state s, then it must be satisfied by any state in s's equivalence class; second, equivalent actions taken from equivalent states produce equivalent successor states. These pieces let us construct an inductive argument to show that, from a given starting state, the successive substitution of one ground action by another in its equivalence class leads us to a state that still satisfies the goal. [3]

We show that any serial plan that exists in the full action space has an equivalent version in the partitioned space.

Taking advantage of structured action representations helps us ignore the distracting complexity and focus instead on the interesting complexity in a problem. We provide a formal basis for computing action equivalence classes that guarantees a complete planning procedure while significantly reducing the branching factor of the search. While our original motivation is the the \rebp\ algorithm, our findings are useful for efficient planning in general.

Acknowledgements

CALO: This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA), through the Department of the Interior, NBC, Acquisition Services Division, under Contract No. NBCHD030010.

References: