Linkability: Examining Causal Link Commitments in Partial-Order Planning

Manuela Veloso and Jim Blythe, In proceedings of the 2nd conference on AI Planning Systems, 1994.


Recently, several researchers have demonstrated domains where partially-ordered planners outperform totally-ordered planners. In [Barrett and Weld, 93], Barrett and Weld build a series of artificial domains exploring the concepts of trivial and laborious serializability, 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 SNLP, 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.