A Survey on Plan Optimization

A Survey on Plan Optimization

Pascal Bercher, Patrik Haslum, Christian Muise

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Survey Track. Pages 7941-7950. https://doi.org/10.24963/ijcai.2024/879

Automated Planning deals with finding a sequence of actions that solves a given (planning) problem. The cost of the solution is a direct consequence of these actions, for example its number or their accumulated costs. Thus, in most applications, cheaper plans are preferred. Yet, finding an optimal solution is more challenging than finding some solution. So, many planning algorithms find some solution and then post-process, i.e., optimize it -- a technique called plan optimization. Over the years many different approaches were developed, not all for the same kind of plans, and not all optimize the same metric. In this comprehensive survey, we give an overview of the existing plan optimization goals, their computational complexity (if known), and existing techniques for such optimizations.
Keywords:
Planning and Scheduling: General
Planning and Scheduling: PS: Hierarchical planning
Planning and Scheduling: PS: Other
Planning and Scheduling: PS: Theoretical foundations of planning