Linkability: Examining Causal Link Commitments in Partial-Order Planning

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.