
Research
Abstracts  2007 
Computing Equivalence Classes for PlanningNatalia H. Gardiol & Leslie Pack KaelblingIntroductionFor autonomous artificial decisionmakers 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 statedependent 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 StrategyA typical forwardsearch planner has the basic structure:
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 zoomedin in part (b), which shows the muchreduced tree derived from actionequivalences. 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 ValidationWe performed a study to illustrate the computational savings of planning with equivalenceclass sampling. We compared three algorithms in two domains. The first set of experiments was done in the ICAPS 2004 blocksworld 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. ConclusionThe principal contribution of this work is to establish that a planning procedure that uses only equivalenceclass 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. AcknowledgementsCALO: 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:[1] website. IPC04 Homepage: 4th International Planning Competition. 2004. [2] website. IPC02 Homepage: 2nd International Planning Competition. 2002. [3] Gardiol, Natalia H. and Kaelbling, Leslie Pack. Computing Action Equivalences for Planning Under time constraints. Cambridge, MA, 2006. 

