  Recently, several researchers have found that cost-based satisficing search
with A* often runs into problems. Although some "work arounds" have been
proposed to ameliorate the problem, there has not been any concerted effort to
pinpoint its origin. In this paper, we argue that the origins can be traced
back to the wide variance in action costs that is observed in most planning
domains. We show that such cost variance misleads A* search, and that this is
no trifling detail or accidental phenomenon, but a systemic weakness of the
very concept of "cost-based evaluation functions + systematic search +
combinatorial graphs". We show that satisficing search with sized-based
evaluation functions is largely immune to this problem.
