PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sebastian Escobar, Morteza Lahijanian

arXiv:2609.07905v1cs.ROcs.FL

TL;DR

TPOs provide interpretable mission specifications, but their timing and task-activation expressivity is limited. This paper introduces cTPOs and an MILP-based decomposition approach; benchmarks report speedups of up to four orders of magnitude over the monolithic MILP while preserving plan optimality.

  • Problem

    TPOs have limited expressivity for timing constraints between unordered events and for subtasks conditional on environmental events.

    Source: §I · p. 1, B. Conditional TPOs with Complex Guards · p. 2

  • Method

    The paper extends TPO planning to cTPOs and decomposes specifications into self-contained substructures solved as smaller MILPs and composed into a globally optimal plan.

    Source: §I · p. 1, §III · p. 3

  • Results

    Up to 4 orders of magnitude speedup over the monolithic MILP is reported for complex instances, with decomposition preserving plan optimality.

    Source: §V · p. 8

  • Takeaways & Limitations

    cTPOs provide a task-specification framework for complex timing constraints between unordered events and conditionally activated task structures.

    Source: §V · p. 8

    As cTPO complexity grows, solving a single MILP over a larger event set can become intractable.

    Source: 1) Complexity · p. 5

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper extends interpretable TPO mission specifications to handle richer timing and conditional tasks while retaining formal planning. It frames this extension against the need to balance expressivity, interpretability, rigor, and computational tractability.

I. INTRODUCTION

  • Robotic missions can combine precedence, deadlines, and conditional obligations, while specification languages must balance expressivity, human interpretability, formal rigor, and computational tractability.The paper identifies TPO limitations in expressing timing constraints between unordered events and conditional subtasks.Source: §I · p. 1

A. Timed Partial Order (TPO)

  • TPOs represent missions as DAGs whose edges encode precedence and clocks impose timing constraints; the graphical form supports direct interpretation and modification.TPO planning can be formulated as a variation of the Generalized Traveling Salesman Problem and solved using MILP.Source: §I · p. 1

I. INTRODUCTION

  • cTPOs add generalized clock-difference guards and conditionally activated tasks to TPOs, and their planning can be formulated as an MILP.The decomposition approach is complete and preserves plan optimality, with benchmarks reporting speedups of up to four orders of magnitude over the monolithic MILP.Source: §I · p. 1

B. Conditional TPOs with Complex Guards

Conditional TPOs extend TPOs with timing constraints between events regardless of precedence and with tasks activated by environmental conditions. These additions allow specifications to express requirements that ordinary TPOs cannot capture.

B. Conditional TPOs with Complex Guards

  • The extensions address requirements ordinary TPOs cannot express, including a conditional ECG pickup and delivery and timing constraints between unordered events.In the hospital example, the ECG tasks are triggered if the robot passes near the Cardiac Wing, while the blood draw and imaging scan must occur within 20 minutes of each other.Source: B. Conditional TPOs with Complex Guards · p. 2
  • Generalized guard conditions allow richer, precedence-free constraints, including sums of clock differences, expressing timing constraints between arbitrary event pairs regardless of their precedence relation.One condition is |c2 − c3| ≤ 20.Source: B. Conditional TPOs with Complex Guards · p. 2
  • Boolean activation conditions make an event and its precedence, timing, and clock-reset constraints required only when its condition is true.Otherwise, that event and its associated constraints are not required; setting every activation condition to true recovers a TPO.Source: B. Conditional TPOs with Complex Guards · p. 3

C. Robot Model

The robot is modeled as a deterministic transition system, and task synthesis seeks a valid plan with a minimum-duration trajectory satisfying the cTPO. Plans generate trajectories whose event traces are checked for compatibility with the specification.

C. Robot Model

  • A deterministic transition system represents robot evolution using states, actions, event labels, and atomic-proposition labels.Its state set and action set are finite; proposition labels identify which atomic propositions hold in each state.Source: C. Robot Model · p. 3
  • A valid action plan generates a trajectory, and its duration is the sum of transition durations along that trajectory.The set of valid plans is denoted Γ.Source: C. Robot Model · p. 3
  • A plan satisfies a cTPO when its timed trace is compatible with the specification under the valuation of its atomic propositions.The paper first defines a valuation for each proposition in AP, then checks compatibility under that valuation.Source: C. Robot Model · p. 3
  • The synthesis problem is to find a valid plan whose trajectory satisfies the cTPO and has minimum duration.The objective is to minimize trajectory duration over valid plans.Source: C. Robot Model · p. 3

III. APPROACH

The approach reduces cTPO planning to a routing-and-scheduling problem, solves it exactly with an MILP, and decomposes the specification to improve scalability while preserving global optimality.

III. APPROACH

  • The approach expresses cTPO compatibility through event timestamps and reduces planning to GTSP-TWPR.This reduction is described in Section III-A.Source: §III · p. 3
  • An MILP extending with proposition tracking and conditional activation constraints solves the resulting problem exactly.This formulation is described in Section III-B.Source: §III · p. 3
  • Sub-TPO decomposition solves self-contained substructures as smaller MILPs and composes their solutions into a globally optimal plan.This decomposition is described in Section III-C.Source: §III · p. 3

A. Reduction to GTSP-TWPR

The reduction recasts cTPO satisfaction as selecting and scheduling event visits in a GTSP-TWPR. Event timestamps express the timing guards as scheduling constraints, including relative windows between unordered, clock-coupled events.

A. Reduction to GTSP-TWPR

  • cTPO satisfaction reduces to selecting locations for active events, ordering visits, and scheduling them to meet timing constraints.Because clocks reset only at events, clock values at event firing can be represented as differences between event timestamps, yielding linear inequalities.Source: A. Reduction to GTSP-TWPR · p. 4
  • The reduction yields absolute event windows, relative windows for precedence-ordered pairs, and precedence-free relative windows for clock-coupled unordered pairs.The precedence-free relative window is the novel case admitted by the generalized guards.Source: A. Reduction to GTSP-TWPR · p. 4
  • The resulting GTSP-TWPR tour visits exactly one node from each active group and minimizes makespan subject to precedence and relative-window constraints.The graph also imposes per-group time windows.Source: A. Reduction to GTSP-TWPR · p. 4
  • The graph groups states by event or proposition labels; its edges encode permitted transitions, precedence, and connections for proposition detection.Travel costs are shortest-path durations, while dwell costs apply when a node has a self-loop action.Source: A. Reduction to GTSP-TWPR · pp. 4–5
  • An MILP enforces the timing windows and proposition tracking that the graph construction alone does not capture.The graph encodes precedence order, while the MILP handles the remaining timing and proposition requirements.Source: A. Reduction to GTSP-TWPR · pp. 4–5

B. MILP Formulation

The MILP jointly chooses a minimum-makespan tour, infers environmental propositions, and enforces timing and coverage constraints for active events. Proposition tracking connects the robot’s route to conditional task activation within a single solve.

B. MILP Formulation

  • The MILP jointly selects a minimum-makespan tour, infers which propositions hold along it, and enforces timing and coverage constraints only for active events.The novel proposition-tracking and conditional-activation constraints couple route choice to event activation and its timing requirements.Source: B. MILP Formulation · p. 5
  • Binary routing variables represent traversed edges, visit-time variables record node arrival times, and proposition and activation variables encode environmental conditions and conditional events.A proposition is true when the tour visits one of its proposition nodes; an event’s activation indicator is true when its Boolean condition holds.Source: B. MILP Formulation · p. 5
  • Flow, event-coverage, travel-time, and timing-window constraints define the tour, while conditional timing constraints apply only when their events are active.Timing windows include both precedence-linked bounds and bounds relating events without precedence relations.Source: B. MILP Formulation · p. 5
  • Boolean activation formulas are translated into binary constraints, with nested formulas handled recursively.Table I presents the linearization relating event activation indicators to proposition variables.Source: B. MILP Formulation · p. 5, Table I · p. 5

1) Complexity:

The section characterizes the computational cost of the MILP and develops a decomposition into isolated sub-TPOs. The algorithm identifies locally maximal sub-TPOs, solves them separately, and composes an optimal global plan.

1) Complexity:

  • GTSP-TWPR is NP-hard; the MILP has O(N 2+n·r) binary variables and O(r·N 2) constraints, with exponential worst-case time in binary-variable count and polynomial per branch-and-bound node in constraint count.Source: 1) Complexity · p. 5
  • Timing constraints have a dual computational effect: adding them strengthens the branch-and-bound bound but increases solve time per node, and sparser timing constraints can increase solve time in practice.As the cTPO grows in events and propositions, solving a single MILP can become intractable.Source: 1) Complexity · p. 5

C. Sub-TPO Decomposition

  • Sub-TPOs isolate internally coupled events behind a single entry and exit, so they can be solved as smaller MILPs and composed back into the global plan.The decomposition changes one large exponential-size problem into a sum of problems exponential only in each subproblem’s size.Source: C. Sub-TPO Decomposition · pp. 5–6
  • A sub-TPO’s internal events must satisfy graph, precedence, clock, and activation isolation conditions relative to events outside the sub-TPO.Its entry and exit are unique; internal events have no cross-boundary dependencies under the listed isolation conditions.Source: C. Sub-TPO Decomposition · p. 6
  • The algorithm considers initial or articulation events as candidate entries, partitions reachable descendants, and prunes events that violate sub-TPO isolation.The pruning procedure accepts a set only if it has at least two events and exactly one exit.Source: C. Sub-TPO Decomposition · p. 6
  • The decomposition algorithm returns exactly all locally maximal sub-TPOs, and solving the resulting reduced high-level TPO yields a plan with the monolithic optimum makespan.The locally maximal sub-TPOs are pairwise disjoint.Source: C. Sub-TPO Decomposition · pp. 6–7

IV. EXPERIMENTS

The evaluation uses illustrative examples and randomly generated benchmarks to examine cTPO expressivity and compare decomposition with monolithic MILP planning. The tool is implemented with Gurobi and ROS.

IV. EXPERIMENTS

  • The evaluation has illustrative examples and benchmarks comparing decomposition against monolithic MILP on randomly generated problems.The examples are intended to show interpretability, plan correctness, and how environmental propositions can change optimal plans.Source: §IV · p. 7
  • The benchmark comparison measures decomposition against monolithic MILP, while the illustrative examples examine how environmental conditions affect optimal plans.The benchmark instances are randomly generated; the paper reports the examples and benchmarks as separate evaluation stages.Source: §IV · p. 7
  • The tool uses Python, Gurobi as its MILP solver, and ROS integration for robot deployment.Benchmarks ran on a MacBook Air M3 with 16 GB RAM; robot experiments used ROS with RViz visualization.Source: §IV · p. 7

1) Warehouse Inspection:

The warehouse example makes the optimal inspection plan depend on Shelf B’s position relative to an oil spill. One placement avoids the spill; the other triggers a cleaning sequence.

1) Warehouse Inspection:

  • The task requires inspecting Shelves A, B, and C, returning to the loading dock, and completing a mandatory charging event.The two environments differ only in Shelf B’s position relative to the spill zone.Source: 1) Warehouse Inspection · p. 7
  • Table II reports the illustrative examples’ robot DTS and induced graph sizes alongside monolithic MILP solve times, averaged over three trials.The warehouse environments are shown in Fig. 4b–4c.Source: Table II · p. 7, 1) Warehouse Inspection · p. 7
  • Shelf B placement changes the optimal plan: one layout avoids the spill, while the other traverses it and triggers three cleaning areas.The robot must complete the cleaning sequence before proceeding after traversing the spill zone.Source: 1) Warehouse Inspection · p. 7

2) Mars Rover Atmospheric Science Mission:

The rover mission illustrates how outcrop conditions change the optimal plan, while random TPO and cTPO benchmarks compare decomposition with monolithic MILP. The conclusion reports preserved plan optimality and speedups up to four orders of magnitude.

V. CONCLUSION

2) Mars Rover Atmospheric Science Mission:

  • When the outcrop condition is triggered, the optimal rover plan executes e6 and e7 before activation rather than avoiding the region.The mission requires the rover to navigate to e6 and collect a sample at e7 within 30 time units if it passes through an outcrop.Source: 2) Mars Rover Atmospheric Science… · pp. 7–8

1) Sub-TPO Decomposition on Random TPOs:

  • Several orders of magnitude growth in monolithic solve time contrasts with decomposition times roughly below 1 s, with speedups exceeding three orders on the hardest TPO instances.The sharpest monolithic solve-time increases correspond to sparser timing constraints, which reduce MILP pruning and enlarge the feasible region.Source: 1) Sub-TPO Decomposition on Random TPOs · p. 8

2) Sub-TPO Decomposition on Random cTPOs:

  • Over 90% of feasible cTPO instances favor decomposition, with speedups reaching four orders of magnitude on the hardest instance.Decomposition times also grow with problem difficulty because the high-level MILP jointly resolves proposition values and tour structure; speedup varies with proposition formulas and activation structure.Source: 2) Sub-TPO Decomposition on Random cTPOs · p. 8

V. CONCLUSION

  • cTPOs add generalized clock-difference guards and environment-dependent activation to specify timing across unordered events and conditional task structures.The conclusion presents these extensions as addressing TPO expressiveness limitations in robotic task planning.Source: §V · p. 8
Loading 2609.07905v1…