Improvements to the Generate-and-Complete Approach to Conformant Planning

Improvements to the Generate-and-Complete Approach to Conformant Planning

Liangda Fang, Min Zhan, Jin Tong, Xiujie Huang, Ziliang Chen, Quanlong Guan

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 8500-8509. https://doi.org/10.24963/ijcai.2025/945

Conformant planning is a computationally challenging task that generates an action sequence to achieve goal condition with uncertain initial states and non-deterministic actions. The generate-and-complete (in short, GC) approach shows superior performance on conformant planning, which iteratively enumerates the solution of a planning subproblem for a single initial state and attempts to extend it for all initial states until a conform solution is found. However, two major drawbacks of the GC approach hinder its performance: the computational overhead due to state exploration and the insertion of many redundant actions. To overcome the above drawbacks, we improve both verification and completion procedures. Experimental results show that the improved GC planner has significant improvements over the original GC approach in many instances with a large number of initial states. Our approach also outperforms all of state-of-the-art planners, solving 989 instances in comparison to 784, which is the most solved by DNF.
Keywords:
Planning and Scheduling: PS: Planning with Incomplete Information
Planning and Scheduling: PS: Planning algorithms
Planning and Scheduling: PS: Planning under uncertainty