main contribution is to bring to the fore its fundamental nature. The rest of the paper is organized as follows. In the next section, we present some preliminary notation to formally specify cost-based, size-based as well as cost-sensitive size-based search alternatives. Next, we present two abstract and fundamental search spaces, which demonstrate that *costbased* evaluation functions are 'always' needlessly prone to such traps (Section 3). Section 4 strengthens the intuitions behind this analysis by viewing A* search as flooding topological surfaces set up by evaluation functions. We will argue that of all possible topological surfaces (i.e., evaluation functions) to choose for search, cost-based is the worst. In Section 5, we put all this analysis to empirical validation by experimenting with LAMA (Richter and Westphal 2010) and SapaReplan. The experiments do show that size-based alternatives out-perform cost-based search. Modern planners such as LAMA use a plethora of improvements beyond vanilla A* search, and in the appendix we provide a deeper analysis on which extensions of LAMA seem to help it mask
(but not fully overcome) the pernicious effects of cost-based evaluation functions.

## 2 Setup And Notation

We gear the problem set up to be in line with the prevalent view of state-space search in modern, state-of-the-art satisficing planners. First, we assume the current popular approach of reducing planning to graph search. That is, planners typically model the state-space in a causal direction, so the problem becomes one of extracting paths, meaning plans do not need to be stored in each state. More important is that the structure of the graph is given *implicitly* by a procedure Γ, the child generator, with Γ(v) returning the local subgraph leaving v; i.e., Γ(v) computes the subgraph (N +[v], E({v}, V − v)) = ({u | vu ∈ E} +
v, {vu | vu ∈ E}) along with all associated labels, weights, and so forth. That is, our analysis depends on the assumption that *an implicit representation of the graph is the only computationally feasible representation*, a common requirement for analyzing the A∗family of algorithms (Hart, Nilsson, and Raphael 1968; Dechter and Pearl 1985).

The search problem is to find a path from an initial state, i, to some goal state in G. Let costs be represented as edge weights, say c(uv) is the cost of an edge from u to v. Let g
∗
c
(v) be the (optimal) cost-to-reach v (from i), and h
∗ c
(v) be the (optimal) cost-to-go from v (to the goal). Then f
∗
c
(v) := g
∗
c
(v)+h
∗
c
(v), the cost-through v, is the cost of the cheapest i-G path passing through v. For discussing smallest solutions, let f
∗
s
(v) denote the smallest i-G path through v.

It is also interesting to consider the size of the cheapest i-G
path passing through v, say ˆf
∗
s
(v).

We define a search node n as equivalent to a path represented as a linked list. In particular, we distinguish this from the state of n (its last vertex), n .v. We say n .a (for action) is the last edge of the path and n.p (for parent) is the subpath excluding n .a and n.v. With n .a an edge from v to u the function gc(n) (g-cost) is just the recursive formulation of path cost: gc(n) := gc(n.p) + c(vu)
(gc(n) := 0 if n is the trivial path). So g
∗(v) ≤ gc(n) for all i-v paths n, with equality for at least one of them. Similarly let gs(n) := gs(n.p) + 1 (initialized at 0), so that gs is an upper bound on g
∗
s
.

A goal is a target vertex where a plan may stop and be a valid solution. We fix a computed predicate G(t) (a blackbox) encoding the set of *goal* vertices. Let hc(v), the *heuristic*, be a procedure to estimate h
∗ c
(v). We call hc *admissible* if it is a guaranteed lower bound. Let hs(v) estimate the remaining depth to the nearest goal, and let hˆs(v) estimate the remaining depth to the cheapest reachable goal.

We focus on two different definitions of f (the evaluation function). Since we study cost-based planning, we consider fc(n) := gc(n)+hc(n .v); this is the (standard, cost-valued)
evaluation function of A∗: cheapest-completion-first. We compare this to fs(n) := gs(n) + hs(n.v), the canonical size-valued (or search distance) evaluation function, equivalent to fc under uniform weights. Any combination of gc and hc is *cost-based*; any combination of gs and hs is *sizebased* (e.g., breadth-first search is size-based). The evaluation function ˆfs(n) := gs(n) + hˆs(n.v) is also size-valued, but cost-sensitive and preferable.

BEST-FIRST-SEARCH(i, G, Γ, hc, EVALUATE)
1 INITIALIZE-SEARCH()
2 **while** *open* not empty 3 n = *open* . remove()
4 s = n .v 5 if BOUND-TEST() **then continue**
6 if GOAL-TEST() **then continue**
7 if DUPLICATE-TEST() **then continue**
8 *star* = Γ(s) // Expand s 9 for each edge a from s to a child s 0in *star* 10 n 0 = nhsas0i // Extend the path n 11 f = EVALUATE(n 0)
12 *open* .add(n 0, f)
13 **return** best-known-*plan* // Optimality is proven.
$\nabla\nabla\mathbf{L}\cup\mathbf{L}$
EVALUATE(n)
// What is the best measure on paths, γ(), to use?

1 s = n .v 2 n 0 = RELAXED-SOLVE(s, G*, . . .*)
3 f = γ(nn0)
// With f = g + h the first variations to consider are:
// g = gc(n), h = gc(n 0), and
// g = gs(n), h = gs(n 0).

4 **return** f BOUND-TEST()
// hc() **must** be a lower bound on h
∗
c
()
1 **return** gc(n) + hc(s) ≥ f
+
c INITIALIZE-SEARCH()
1 *open* = empty priority queue 2 *closed* = empty map from vertices to paths 3 f
+
c = ∞ // An upper bound on f
∗
c
(i)
4 best-known-*plan* = NULL
5 n = hii 6 f = EVALUATE(n) 7 *open* .add(*n, f*)