Comparing Causal-Link and Propositional Planners: Tradeos between Plan Length and Domain Size

Recent studies have shown that propositional planners, which de-rive from Graphplan and SATPLAN, can generate signicantly 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: speci cally, they can generate plans only for smaller domains, where the size of a domain is dened 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-os between plan length and domain size, because it is straightforward to Partially supported by the Andrew Mellon Pre-doctoral Fellowship, awarded by th