Conditional Timed Partial Orders: An Expressive and Interpretable Framework for Robot Task Specification and Planning

• URL: http://arxiv.org/abs/2609.07905v1
• Date: Mon, 07 Sep 2026 19:18:17 GMT
• Title: Conditional Timed Partial Orders: An Expressive and Interpretable Framework for Robot Task Specification and Planning
• Abstract summary: Conditional TPOs (cTPOs) provide an interpretable framework for robot task specification with planning algorithms based on mixed-integer linear programming (MILP)<n>We show that planning for cTPOs also reduces to an MILP problem; however, the added expressivity results in significantly larger MILPs that can become computationally intractable.<n>We propose a decomposition algorithm that partitions a cTPO into smaller sub-TPOs, yielding a sequence of smaller MILP problems.
• Score: 9.370068250965433
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Timed Partial Orders (TPOs), originally proposed for workflows, provide an interpretable framework for robot task specification with planning algorithms based on mixed-integer linear programming (MILP). However, TPOs are limited in expressivity, capturing only partial-order events with simple timing constraints. In this paper, we introduce Conditional TPOs (cTPOs), which extend TPOs with richer relative-timing constraints and conditional event activations based on environmental conditions. We show that planning for cTPOs also reduces to an MILP problem; however, the added expressivity results in significantly larger MILPs that can become computationally intractable. To address this challenge, we propose a decomposition algorithm that partitions a cTPO into smaller sub-TPOs, yielding a sequence of smaller MILP problems. We prove that this decomposition is complete and preserves plan optimality while improving the interpretability of complex tasks. Experimental results demonstrate the effectiveness of cTPOs as a task specification framework and the efficiency of our decomposition approach, achieving up to four orders of magnitude speedup over the monolithic MILP.

Related papers

• Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs [53.412166189410904]
  We use supervised learning as a computational proxy to establish a hierarchy of commonly adopted RL oracles under low-rank Markov Decision Processes (MDPs)<n>Motivated by this observation, we propose a novel optimistic actor-critic algorithm that relies solely on the policy evaluation oracle.<n>We prove that our algorithm outperforms the existing sample complexity guarantees for low-rank MDPs while avoiding computationally expensive planning or optimization oracles commonly assumed in prior works.
  arXiv  Detail & Related papers  (2026-05-02T04:46:54Z)
• SPPO: Sequence-Level PPO for Long-Horizon Reasoning Tasks [41.49967840381499]
  Sequence-Level PPO (SPPO) is a scalable algorithm that harmonizes the sampletextual efficiency of PPO with the stability of outcome-based updates.<n>SPPO significantly surpasses standard PPO and matches the performance of computation-heavy group-based methods.
  arXiv  Detail & Related papers  (2026-04-10T01:58:21Z)
• MATEO: A Multimodal Benchmark for Temporal Reasoning and Planning in LVLMs [2.1793134762413433]
  AI agents need to plan to achieve complex goals that involve orchestrating perception, sub-goal decomposition, and execution.<n>Existing research on foundational models' understanding of temporal execution is limited to automatically derived annotations, approximations of the TEO as a linear chain, or text-only inputs.<n>We introduce MATEO, a benchmark designed to assess and improve the temporal reasoning abilities of Large Vision Language Models (LVLMs) required for real-world planning.
  arXiv  Detail & Related papers  (2026-02-16T09:41:50Z)
• Graph-Enhanced Deep Reinforcement Learning for Multi-Objective Unrelated Parallel Machine Scheduling [0.0]
  This paper proposes a Deep Reinforcement Learning framework using Proximal Policy Optimization (PPO) and a Graph Neural Network (GNN)<n>The GNN effectively represents the complex state of jobs, machines, and setups, allowing the PPO agent to learn a direct scheduling policy.
  arXiv  Detail & Related papers  (2026-02-08T16:54:47Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  We propose an end-to-end deep learning (DL) framework with low inference complexity for symbol-level precoding.<n>We show that the proposed framework captures substantial performance gains of optimal SLP, while achieving an approximately 80-times speedup over conventional methods.
  arXiv  Detail & Related papers  (2025-10-02T15:15:50Z)
• 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)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  We present Recipe2Plan, a novel benchmark framework based on real-world cooking scenarios.<n>Unlike conventional benchmarks, Recipe2Plan challenges agents to optimize cooking time through parallel task execution.
  arXiv  Detail & Related papers  (2025-03-04T03:27:02Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents.<n>Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• Capacity-Aware Planning and Scheduling in Budget-Constrained Multi-Agent MDPs: A Meta-RL Approach [12.116400321124594]
  We study capacity- and budget-constrained multi-agent MDPs (CB-MA-MDPs)<n>We propose a two-stage solution that remains tractable for large systems.
  arXiv  Detail & Related papers  (2024-10-28T17:48:45Z)
• Benchmarking Agentic Workflow Generation [80.74757493266057]
  We introduce WorfBench, a unified workflow generation benchmark with multi-faceted scenarios and intricate graph workflow structures.<n>We also present WorfEval, a systemic evaluation protocol utilizing subsequence and subgraph matching algorithms.<n>We observe that the generated can enhance downstream tasks, enabling them to achieve superior performance with less time during inference.
  arXiv  Detail & Related papers  (2024-10-10T12:41:19Z)
• Unified Task and Motion Planning using Object-centric Abstractions of Motion Constraints [56.283944756315066]
  We propose an alternative TAMP approach that unifies task and motion planning into a single search. Our approach is based on an object-centric abstraction of motion constraints that permits leveraging the computational efficiency of off-the-shelf AI search to yield physically feasible plans.
  arXiv  Detail & Related papers  (2023-12-29T14:00:20Z)
• Conformal Temporal Logic Planning using Large Language Models [26.793426646439073]
  We consider missions that require accomplishing multiple high-level sub-tasks expressed in natural language (NL), in a temporal and logical order.<n>Our goal is to design plans, defined as sequences of robot actions, accomplishing-NL tasks.<n>We propose HERACLEs, a hierarchical neuro-symbolic planner that relies on a novel integration of existing symbolic planners.
  arXiv  Detail & Related papers  (2023-09-18T19:05:25Z)
• PromptSum: Parameter-Efficient Controllable Abstractive Summarization [4.145362426026615]
  We introduce PromptSum, a method combining PT with a multi-task objective and discrete entity prompts for abstractive summarization. Our model competitive ROUGE results on popular abstractive summarization benchmarks coupled with a strong level of controllability through entities.
  arXiv  Detail & Related papers  (2023-08-06T13:54:14Z)
• On efficient computation in active inference [1.1470070927586016]
  We present a novel planning algorithm for finite temporal horizons with drastically lower computational complexity. We also simplify the process of setting an appropriate target distribution for new and existing active inference planning schemes.
  arXiv  Detail & Related papers  (2023-07-02T07:38:56Z)
• Sequence-Based Plan Feasibility Prediction for Efficient Task and Motion Planning [36.300564378022315]
  We present a learning-enabled Task and Motion Planning (TAMP) algorithm for solving mobile manipulation problems in environments with many articulated and movable obstacles. The core of our algorithm is PIGINet, a novel Transformer-based learning method that takes in a task plan, the goal, and the initial state, and predicts the probability of finding motion trajectories associated with the task plan.
  arXiv  Detail & Related papers  (2022-11-03T04:12:04Z)

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.