MaxPlan

Introduction

      MaxPlan is an automated optimal propositional based on a satisfiability (SAT) formulation of STRIPS planning. The key innovation of MaxPlan is its use of the long distance mutual exclusion (londex), a novel generalization of the classic mutual exclusion (mutex). Based on a multi-valued domain formulation, londex provides much stronger space pruning than mutex since it can capture constraints relating actions not only at the same time step but also across multiple time steps. Several other novel techniques, including backward level reduction, accumulative learning of clauses, and SAT constraint partitioning, are also developed to further improve the search efficiency for both satisfiability solving and unsatisfiability proving.
 

Winner of the 1st Prize, Optimal Planning Track, Deterministic Part of the 5th International Planning Competition (IPC5), 2006

The plots of the performance of all competing planners in the deterministic track of IPC5 can be found here. An archive with all results can be found here. You can download all the domains in IPC5 from here.

    
Software Download

      Source code

        32-bit executable for Linux

        64-bit executable for Linux

Example command:
         maxplan -path domain_path -problem strips_problem -cgproblem adl_problem -domain strips_domain -cgdomain adl_domain -timeout 1800 -solver minisat

Publications

• Y. Chen, X. Zhao, and W. Zhang, Long Distance Mutual Exclusion for Propositional Planning,
  International Joint Conference on Artificial Intelligence (IJCAI'07), 2007. [PS]
   
• Z. Xing, Y. Chen, and W. Zhang, MaxPlan: Optimal Planning by Decomposed Satisfiability and Backward Reduction,
  Proc. Fifth Int'l Planning Competition, Int'l Conf. on Automated Planning and Scheduling (ICAPS'06), pp.53-56, June 2006. [PDF]
   
• X. Zhao, Y. Chen, and W. Zhang, An Efficient and Integrated Strategy for Temporal Planning,
  The Third International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'06), pp. 273-287, June 2006. [PDF]
   
• X. Zhao, Y. Chen, and W. Zhang, Optimal Planning by Maximum Satisfiability and Accumulative Learning,
  Proc. International Conference on Automated Planning and Scheduling (ICAPS'06), pp. 442-447, June 2006. [PS]

 
Acknowledgments

This research is supported by funds from the Washington University in St. Louis, an Early Career Young Investigator Award from the Department of Energy, and National Science Foundation Grant IIS-0535257.

 

For questions or bug report, please contact rh11@cse.wustl.edu or zx2@cs.wustl.edu
Last updated on Nov 30, 2006