Manuela Veloso and Jim Blythe
Recently, several researchers have demonstrated domains where partially-ordered planners outperform totally-ordered planners. Barrett and Weld build a series of artificial domains exploring the concepts of trivial and laborious serialisability, in which a partially-ordered planner, SNLP, consistently outperforms two totally-ordered planners. In this paper, we demonstrate that totally-ordered planners sometimes have an advantage over partially-ordered planners. We describe a series of domains in which PRODIGY 4.0 consistently outperforms SNIP, and introduce the concept of linkability to characterize the class of domains for which this happens. Linkability highlights the fact that partially-ordered planners commit to causal links in much the same way that totally-ordered planners commit to step ordering.