Finding Optimal Cost-Bounded Plan Reductions: Refined Model

• URL: http://arxiv.org/abs/2607.25484v1
• Date: Tue, 28 Jul 2026 09:21:19 GMT
• Title: Finding Optimal Cost-Bounded Plan Reductions: Refined Model
• Abstract summary: We study the problem of extracting, from a precomputed plan, a valid subplan that maximizes utility while respecting a cost bound.<n>We show the decision variant is NP-complete and propose two exact methods to solve it: one via oversubscription planning (OSP) and another via Linear Programming (ILP)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Lose the Order, Keep the Hierarchy: Deordering HTN Plans [0.7773045483342574]
  Hierarchical Task Network (HTN) planning is a powerful planning formalism based on task decomposition.<n>Plan deordering has been extensively studied in classical planning but remains under-researched in the HTN setting.<n>We adapt two established plan deordering techniques from classical planning by extending the techniques to account for hierarchical decomposition constraints.
  arXiv  Detail & Related papers  (2026-09-03T14:27:58Z)
• Knowing What to Solve Before How: Preplan Empowered LLM Mathematical Reasoning [5.703029996279753]
  We propose PPC (Preplan-Plan-CoT), a framework that introduces an explicit problem-understanding stage, the preplan.<n>We show that PPC achieves the best results on 39 of 40 metrics, improving maj@16 and pass@16 by +2.23 and +3.06 over the strongest baseline.
  arXiv  Detail & Related papers  (2026-05-28T17:11:43Z)
• PaT: Planning-after-Trial for Efficient Test-Time Code Generation [25.264318601226265]
  Planning-after-Trial (PaT) is an adaptive policy for code generation that invokes a planner only upon verification failure.<n>We propose PaT, an adaptive policy for code generation that invokes a planner only upon verification failure.
  arXiv  Detail & Related papers  (2026-05-08T05:09:18Z)
• Planning with Minimal Disruption [9.722824469961925]
  In many planning applications, we might be interested in finding plans that minimally modify the initial state to achieve the goals.<n>In this paper, we formally introduce it, and define various planning-based compilations that aim to jointly optimize both the sum of action costs and plan disruption.
  arXiv  Detail & Related papers  (2025-08-21T08:38:17Z)
• PLAN-TUNING: Post-Training Language Models to Learn Step-by-Step Planning for Complex Problem Solving [66.42260489147617]
  We introduce PLAN-TUNING, a framework that distills synthetic task decompositions from large-scale language models.<n>Plan-TUNING fine-tunes smaller models via supervised and reinforcement-learning objectives to improve complex reasoning.<n>Our analysis demonstrates how planning trajectories improves complex reasoning capabilities.
  arXiv  Detail & Related papers  (2025-07-10T07:30:44Z)
• No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
  We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback.<n>It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time.<n>We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget
  arXiv  Detail & Related papers  (2025-06-16T08:42:31Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• Adversarial Plannning [8.930624061602046]
  Planning algorithms are used in computational systems to direct autonomous behavior. It is unclear how such algorithms will perform in the face of adversaries attempting to thwart the planner.
  arXiv  Detail & Related papers  (2022-05-01T21:43:06Z)
• Efficient Belief Space Planning in High-Dimensional State Spaces using PIVOT: Predictive Incremental Variable Ordering Tactic [11.878820609988693]
  We examine the problem of online decision making under uncertainty, which we formulate as planning in the belief space. We call this approach PIVOT: Predictive Incremental Variable Ordering Tactic. Applying this tactic can also improve the state inference efficiency.
  arXiv  Detail & Related papers  (2021-12-29T07:30:47Z)
• On Exploiting Hitting Sets for Model Reconciliation [53.81101846598925]
  In human-aware planning, a planning agent may need to provide an explanation to a human user on why its plan is optimal. A popular approach to do this is called model reconciliation, where the agent tries to reconcile the differences in its model and the human's model. We present a logic-based framework for model reconciliation that extends beyond the realm of planning.
  arXiv  Detail & Related papers  (2020-12-16T21:25:53Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.