Optimally Relaxing Partial-Order Plans with MaxSAT

Abstract

Partial-order plans (POPs) are attractive because of their least commitment nature, providing enhanced plan flexibility at execution time relative to sequential plans. Despite the appeal of POPs, most of the recent research on automated plan generation has focused on sequential plans. In this paper we examine the task of POP generation by relaxing or modifying the action orderings of a plan to optimize for plan criteria that promotes flexibility in the POP. Our approach relies on a novel partial weighted MaxSAT encoding of a plan that supports the minimization of deordering or reordering of actions. We further extend the classical least commitment criterion for a POP to consider the number of actions in a solution, and provide an encoding to achieve least commitment plans with respect to this criterion. We compare the effectiveness of our approach to a previous approach for POP generation via sequential-plan relaxation. Our results show that while the previous approach is proficient at heuristically finding the optimal deordering of a plan, our approach gains greater flexibility with the optimal reordering.