Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of adapting precomputed plans to new budget constraints while maintaining the original action order and executability. By focusing on maximizing utility through the removal of low-utility goals, the authors establish that the decision variant of this problem is NP-complete and introduce two exact solution methods: oversubscription planning (OSP) and Integer Linear Programming (ILP). Experimental results demonstrate that ILP significantly outperforms OSP, offering a viable approach for scenarios where plan structure is critical.
Extracting high-utility subplans under cost constraints reveals that ILP can dramatically enhance plan efficiency without sacrificing structure.
In some real applications a plan may later become unfeasible due to newly imposed budget constraints, yet, at the same time, using only the original actions of the plan and their order is mandatory. In this paper, we study the problem of extracting, from a precomputed plan, a valid subplan that maximizes utility while respecting a cost bound. Each goal is given a utility value and the plan is reduced by removing actions that support low-utility goals, while preserving both executability and the original action order. We show the decision variant is NP-complete and propose two exact methods to solve it: one via oversubscription planning (OSP) and another via Integer Linear Programming (ILP). Experiments show that ILP outperforms OSP, providing a practical solution in domains where maintaining the structure of the original plan is essential.