

![0_image_0.png](0_image_0.png)

Figure 1: Rendezvous problems. Diagonal edges cost 7,000,

![0_image_1.png](0_image_1.png)

Table 1: IPC metric on LAMA variants.

this latter modification LAMA-size. Ultimately, the observation is that LAMA-size outperforms LAMA - no trivial feat, particularly for such a small change in implementation.

LAMA4 defies analysis in a number of ways: *landmarks*,
preferred operators, dynamic evaluation functions, *multiple* open lists, and *delayed evaluation*, all of which effect potential search plateaus in complex ways. Nonetheless, it is essentially a cost-based approach.

Results.5 With more than about 8 total passengers, LAMA
is unable to complete any search stage except the first (the greedy search). For the same problems, LAMA-size finds the same first plan (the heuristic values differ, but not the structure), but is then subsequently able to complete further stages of search. In so doing it sees marked improvement in cost; on the larger problems this is due only to finding better variants on the greedy plan. Other domains are included for broader perspective, woodworking in particular was chosen as a likely counter-example, as all the actions concern just one type of physical object and the costs are not wildly different. For the same reasons we would expect LAMA to out-perform LAMA-size in some cost-enhanced version of Blocksworld. For a comprehensive empirical analysis, see (Richter and Westphal 2010).

## 5.2 Sapareplan

We also consider the behavior of SapaReplan on the simpler set of problems.6 This planner is much less sophisticated in terms of its search than LAMA, in the sense of being much closer to a straight up implementation of weighted A*
search. The problem is just to swap the locations of passengers located on either side of a chain of cities. A plane starts on each side, but there is no actual advantage to using more than one (for optimizing either of size or cost): the second 4Options: 'fFlLi'.

5New best plans for Elevators were found (largely by LAMAsize). The baseline planner's score is 71.8% against the better reference plans.

6Except that these problems are run on all of ZenoTravel.

plane exists to confuse the planner. Observe that smallest and cheapest plans are the same. So in some sense the concepts have become only superficially different; but this is just what makes the problem interesting, as despite this similarity, still the behavior of search is strongly affected by the nature of the evaluation function. We test the performance of ˆfs and fc, as well as a hybrid evaluation function similar to ˆfs + fc (with costs normalized). We also test hybridizing via tie-breaking conditions, which ought to have little effect given the rest of the search framework.

Results.7 The size-based evaluation functions find better cost plans faster (within the deadline) than cost-based evaluation functions. The hybrid evaluation function also does relatively well, but not as well as could be hoped. Tiebreaking has little effect, sometimes negative.

We note that Richter and Westphal (2010) also report that replacing cost-based evaluation function with a pure sizebased one improves performance over LAMA in multiple other domains. Our version of LAMA-Size uses a costsensitive size-based search, and our results, in the domains we investigated, seem to show bigger improvements over LAMA.

Finally, while LAMA-size outperforms LAMA, our theory of ε-cost traps suggests that cost-based search should fail even more spectacularly. In the appendix, we take a much closer look at one domain–the travel domain–and present a detailed study of which extensions of LAMA help it temporarily mask the pernicious effects of cost-based search. Our conclusion is that both LAMA and SapaReplan manage to find solutions to problems in the travel domain despite the use of a cost-based evaluation function by using various tricks to induce a limited amount of *depth-first behavior* in an A∗-framework. This has the potential effect of delaying exploration of the ε-cost plateaus slightly, past the discovery of a solution, but still each planner is ultimately trapped by such plateaus before being able to find really good solutions.

In other words, such tricks are mostly serving to mask the problems of cost-based search (and ε-cost), as they merely delay failure by just enough that one can imagine that the planner is now effective (because it returns a solution where before it returned none). Using a size-based evaluation function more directly addresses the existence of cost plateaus, and not surprisingly leads to improvement over the equivalent cost-based approach - even with LAMA.

6 Conclusion The practice of combinatorial search in automated planning is*satisficing*. There is a great call for deeper theories of satisficing search, and one perhaps significant obstacle in the way of such research is the pervasive notion that perfect problem solvers are the ones giving only perfect solutions. Actually implementing cost-based, systematic, combinatorial, search reinforces this notion, and therein lies its greatest harm.

7The results differ markedly between the 2 and 3 city sets of problems because the sub-optimal relaxed plan extraction in the 2-cities problems coincidentally produces an essentially perfect heuristic in many of them. One should infer that the solutions found in the 2-cities problems are sharply bimodal in quality and that the meaning of the average is then significantly different than in the 3-cities problems.