Comparing causal-link and propositional planners: Tradeoffs between plan length and domain size

Recent studies have shown that propositional planners, which de-rive from Graphplan and SATPLAN, can generate significantly longer
plans than causal-link planners. We present experimental evidence
demonstrating that while this may be true, propositional planners
also have important limitations relative to the causal-link planners:
specifically, they can generate plans only for smaller domains, where
the size of a domain is defined by the number of distinguishable objects
it contains. Our experiments were conducted in the domain of code
optimization, in which the states of the world represent states of the
computer program code and the planning operators are the optimiza-
tion operators. This domain is well-suited to studying the trade-offs
between plan length and domain size, because it is straightforward to manipulate both these factors. On the basis of our experiments, we conclude that causal-link and propositional planners have complementary strengths.