Optimal Partial-Order Plan Relaxation via MaxSAT. Muise, C., Beck, J. C., & McIlraith, S. A. Journal of Artificial Intelligence Research, 2016.
Optimal Partial-Order Plan Relaxation via MaxSAT [pdf]Paper  abstract   bibtex   3 downloads  
Partial-order plans (POPs) are attractive because of their least-commitment nature, which provides enhanced plan flexibility at execution time relative to sequential plans. Current research on automated plan generation focuses on producing sequential plans, despite the appeal of POPs. In this paper we examine POP generation by relaxing or modifying the action orderings of a sequential plan to optimize for plan criteria that promote flexibility. Our approach relies on a novel partial weighted MaxSAT encoding of a sequential plan that supports the minimization of deordering or reordering of actions. We further demonstrate how to remove redundant actions from the plan. Our partial weighted MaxSAT encoding allows us to compute a POP from a sequential plan effectively. We compare the efficiency of our approach to previous methods for POP generation via sequential-plan relaxation. Our results show that while an existing heuristic approach consistently produces the optimal deordering of a sequential plan, our approach has greater flexibility when we consider reordering the actions in the plan while also providing a guarantee of optimality. We also investigate and confirm the accuracy of the standard $\flex$ metric typically used to predict the true flexibility of a POP as measured by the number of linearizations it represents.
Downloads: 3
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021