在不改变原动作顺序前提下，从计划中删减低效动作以适配新预算约束。
Finding Optimal Cost-Bounded Plan Reductions: Refined Model
- 基于原始计划顺序，删减低效动作以满足成本限制
- 通过整数规划优化，实现高实用性子计划的快速求解
- 适合需要动态调整计划成本的应用场景
在某些实际应用中，计划可能因新增预算约束而变得不可行，但必须保持原计划的动作及其顺序。本文研究如何从预计算的计划中提取一个有效子计划，在遵守成本上限的前提下最大化效用。每个目标具有对应效用值，通过移除支持低效用目标的动作来缩减计划，同时保证执行可行性与原始动作顺序不变。我们证明该决策问题为NP完全，并提出两种精确求解方法：一种基于超订计划（OSP），另一种基于整数线性规划（ILP）。本文扩展了2026年发表于ICAPS的前期工作，引入更精炼的ILP建模方式，显著减小模型规模并提升计算效率。
原文摘要 · Abstract (English)
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). This paper extends our previous work published at ICAPS 2026 (Del Toro, Fuentetaja, and García-Olaya 2026b). While the core framework remains as introduced there, we further introduce a refined ILP formulation that significantly decreases the model size and improves computational efficiency.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。