
2 Cities 3 Cities

Mode Score Rank Score Rank

Hybrid 88.8% 1 43.1% 2

Size 83.4% 2 43.7% 1

Size, tie-break on cost 82.1% 3 43.1% 2

Cost, tie-break on size 77.8% 4 33.3% 3

Cost 77.8% 4 33.3% 3

Table 2: IPC metric on SapaReplan variants in ZenoTravel.

In support of the position we demonstrated the technical difficulties arising from such use of a cost-based evaluation function, largely by arguing that the size-based alternative is a notably more effective default strategy. We argued that using cost as the basis for plan evaluation is a purely exploitative perspective, leading to least interruptible behavior.

Being least interruptible, it follows that implementing costbased search will typically be immediately harmful to that particular application. But regardless of whether the particular instance demonstrates the rule or the exception, the lasting harm is in reinforcing the wrong definition of satisficing search in the first place. In conclusion, as a rule: Cost-based search is harmful.

## References

[Benton et al. 2010] Benton, J.; Talamadupula, K.; Eyerich, P.;
Mattmuller, R.; and Kambhampati, S. 2010. G-value plateaus: ¨
A challenge for planning. In *ICAPS*. AAAI Press.

[Blum and Furst 1995] Blum, A. L., and Furst, M. L. 1995. Fast planning through planning graph analysis. AIJ 1636–1642.

[Dechter and Pearl 1985] Dechter, R., and Pearl, J. 1985. Generalized best-first search strategies and the optimality of A*. ACM
32(3):505–536.

[Hart, Nilsson, and Raphael 1968] Hart, P. E.; Nilsson, N. J.; and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. *IEEE Transactions on Systems Science and* Cybernetics 4:100–107.

[Helmert, Do, and Refanidis 2008] Helmert, M.; Do, M.; and Refanidis, I. 2008. The deterministic track of the international planning competition. http://ipc.informatik.

uni-freiburg.de/ .

[Kautz and Selman 1999] Kautz, H., and Selman, B. 1999. Unifying SAT-based and graph-based planning. In *IJCAI*. Morgan Kaufmann.

[Pearl 1984] Pearl, J. 1984. Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

[Pohl 1973] Pohl, I. 1973. The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving. In *IJCAI*.

[Richter and Westphal 2010] Richter, S., and Westphal, M. 2010.

The LAMA planner: Guiding cost-based anytime planning with landmarks. *JAIR* 39:127–177.

[Thayer and Ruml 2010] Thayer, J., and Ruml, W. 2010. Finding acceptable solutions faster using inadmissible information. In *Proceedings of the International Symposium on Combinatorial Search*.

## A Deeper Analysis Of The Results In Travel Domain

In this section we analyze the reported behavior of LAMA
and SapaReplan in greater depth. We begin with a general analysis of the domain itself and the behavior of (simplistic)
systematic state-space search upon it, concluding that costbased methods suffer an enormous disadvantage. The empirical results are not nearly so dramatic as the dire predictions of the theory, or at least do not appear so. We consider to what extent the various additional techniques of the planners
(violating the assumptions of the theory) in fact mitigate the pitfalls of ε-cost, and to what extent these only serve to mask the difficulty.

## A.1 Analysis Of Travel Domain

We argue that search under fc pays a steep price in time and memory relative to search under ˆfs. The crux of the matter is that the domain is reversible, so relaxation-based heuristics cannot penalize fruitless or even counter-productive passenger movements by more than the edge-weight of that movement. Then plateaus in g are plateaus in f, and the plateaus in gc are enormous.

First note that the domain has a convenient structure: The global state space is the product of the state space of shuffling planes around between cities/airports via the fly action (expensive), and the state space of shuffling people around between (stationary) planes and cities/airports via the board/debark actions (cheap). For example, in the rendezvous problems, there are 5 4 = 625 possible assignments of planes to cities, and (5 + 4)2k possible assignments of passengers to locations (planes + cities), so that the global state space has exactly 5 4· 9 2kreachable states (with k the number of passengers at one of the origins).8 Boarding and debarking passengers is extremely cheap, say on the order of cents, while flying planes between cities is quite a bit more expensive, say on the order of hundreds of dollars (from the perspective of passengers). So 1 ε ≈ 10000 for this domain - a constant, but much too large to ignore.

To analyze state-space approaches in greater depth let us make all of the following additional assumptions: The heuristic is relaxation-based, imperfect, and in particular heuristic error is due to the omission of actions from relaxed solutions relative to real solutions. Heuristic error is not biased in favor of less error in estimation of needed fly actions - in this problem planes are *mobiles* and *containers* whereas people are only *mobiles*. Finally, there are significantly but not overwhelmingly more passengers than planes.

Then consider a child node, in plane-space, that is in fact the correct continuation of its parent, but the heuristic fails to realize it. So its f is higher by the cost or size of one plane movement: 1 under normalized costs. Moreover assume that moving passengers is not heuristically good (in this particular subspace). (Indeed, moving passengers is usually a bad idea.) Then moving a passenger increases fc by at most 2ε (and at least ε), once for gc and once for hc.

As 1 2ε ≈ 5000 we have that search under fc explores the passenger-shuffling space of the parent to, at least, *depth* 5000. Should the total heuristic error in fact exceed one fly action, then each such omission will induce backtracking to a further 5000 levels: for any search node n reached by a fly action set ec(n) = fc(x)−fc(n) with x some solution of interest (set es similarly). Then if search node n ever appears on the open list it will have its passenger-shuffling subspace 8Fuel and zoom are distracting aspects of ZenoTravel-STRIPS,
so we remove them. Clever domain analysis could do the same.