SAGAS: Semantic-Aware Graph-Assisted Stitching for Offline Temporal Logic Planning
Organizations: School of Automation and Intelligent Sensing, Shanghai Jiao Tong University
Abstract
Linear Temporal Logic (LTL) provides a rigorous framework for specifying long-horizon robotic tasks, yet existing approaches face a trade-off: model-based synthesis relies on accurate labeled transition systems, whereas learning-based methods often require online interaction, task-specific rewards, or specification-conditioned training. We study LTL-specified robotic planning and execution in an offline, model-free setting, where the agent is given only fixed, task-agnostic trajectory fragments, with no dynamics model, task demonstrations, or online data collection. To address this setting, we propose SAGAS, a framework that combines the compositionality of symbolic synthesis with the data-driven reachability structure learned from offline trajectories. SAGAS first learns a reusable latent reachability graph and a frozen goal-conditioned executor from fragmented offline data. For each new LTL formula, it performs task-time semantic graph augmentation to ground state-defined propositions on the learned graph and applies Büchi product search to synthesize a cost-aware accepting prefix--suffix waypoint plan executed by the frozen executor. This separation of learning and planning enables zero-shot generalization to unseen LTL formulas and new predicates supported by the offline data, without task-specific rewards, additional data collection, or policy retraining. Experiments on LTL task suites constructed from OGBench locomotion domains show that SAGAS achieves higher success rates and lower execution costs than baselines on diverse unseen tasks, with further evaluation in OGBench Scene demonstrating its applicability to robotic manipulation.
Figures & tables
| Domain | Method | Easy | Medium | Hard | |||
|---|---|---|---|---|---|---|---|
| SR (%) | NCC | SR (%) | NCC | SR (%) | NCC | ||
| AntMaze | SAGAS | ||||||
| LF-GAS | |||||||
| GA-GAS | |||||||
| AP-HIQL | |||||||
| HumanoidMaze | SAGAS | ||||||
Appendix figures & tables31 assets
Supplementary material from the paper’s appendix.
Appendix
| LTL formula structure | Semantic description |
|---|---|
| Reach: Eventually visit region . | |
| Safety: Always avoid region . | |
| Sequence: Visit . | |
| Coverage: Visit regions in any order. | |
| Conditional: Avoid until goal is reached. | |
| Patrol: Infinitely revisit . |
| Difficulty | Logical composition | Labeled regions |
|---|---|---|
| Easy | One template instance, no conjunction of multiple templates | At most 5 |
| Medium | Conjunction of up to 3 template instances | At most 5 |
| Hard | Conjunction of up to 4 template instances | At most 8 |
| Parameter | AntMaze | HumanoidMaze |
| Task cases per environment–difficulty pair | 100 | 100 |
| Anchor source | Dataset retrieval | Dataset retrieval |
| Initial anchors per proposition | 3 | 3 |
| Maximum candidate attempts per proposition | 50 | 50 |
| Soft-label threshold | 0.05 | 0.20 |
| Temporal-distance scale | 8 | 32 |
| Symbol | Main feature | Full joint condition |
|---|---|---|
| Drawer ready | ||
| Drawer open | ||
| Window ready | ||
| Window open | ||
| Cube at A, objects closed | ||
| Cube at B, objects open |
| Task family | Representative formula |
|---|---|
| Single-stage configuration | |
| Ordered two-stage manipulation | |
| Ordered three-stage manipulation | |
| Choice then configuration | |
| Negative-until | |
| Recurrent suffix |
| Environment | Difficulty | SAGAS | LF-GAS | GA-GAS | AP-HIQL | ||||
|---|---|---|---|---|---|---|---|---|---|
| SR (%) | NCC | SR (%) | NCC | SR (%) | NCC | SR (%) | NCC | ||
| Medium-Navigate | Easy | 78.0 | 79.0 | 68.0 | 70.0 | ||||
| Medium | 83.0 | 74.0 | 60.0 | 70.0 | |||||
| Hard | 65.0 | 60.0 | 54.0 | 61.0 | |||||
| All | 75.3 | 71.0 | 60.7 | 67.0 | |||||
| Large-Navigate | Easy | 73.0 | 67.0 | 59.0 | 77.0 | ||||
| Environment | Difficulty | SAGAS | LF-GAS | GA-GAS | AP-HIQL | ||||
|---|---|---|---|---|---|---|---|---|---|
| SR (%) | NCC | SR (%) | NCC | SR (%) | NCC | SR (%) | NCC | ||
| Medium-Navigate | Easy | 81.0 | 78.0 | 76.0 | 75.0 | ||||
| Medium | 66.0 | 66.0 | 55.0 | 77.0 | |||||
| Hard | 67.0 | 57.0 | 55.0 | 61.0 | |||||
| All | 71.3 | 67.0 | 62.0 | 71.0 | |||||
| Medium-Stitch | Easy | 68.0 | 72.0 | 69.0 | 74.0 | ||||
| Domain | Baseline | SR (pp) | NCC | |
|---|---|---|---|---|
| AntMaze | LF-GAS | |||
| GA-GAS | ||||
| AP-HIQL | ||||
| HumanoidMaze | LF-GAS | |||
| GA-GAS | ||||
| AP-HIQL |
| Setting | Difficulty | SAGAS | LF-GAS | GA-GAS | AP-HIQL |
|---|---|---|---|---|---|
| Ant giant-nav. | Easy | ||||
| Ant giant-nav. | Medium | ||||
| Ant giant-nav. | Hard | ||||
| Ant giant-stitch | Easy | ||||
| Ant giant-stitch | Medium | ||||
| Ant giant-stitch | Hard |
| Environment | Difficulty | SAGAS | LF-GAS | GA-GAS | AP-HIQL | |
|---|---|---|---|---|---|---|
| Medium-Navigate | Easy | 47 | ||||
| Medium | 46 | |||||
| Hard | 33 | |||||
| All | 126 | |||||
| Large-Navigate | Easy | 45 | ||||
| Medium | 39 |
| Environment | Difficulty | SAGAS | LF-GAS | GA-GAS | AP-HIQL | |
|---|---|---|---|---|---|---|
| Medium-Navigate | Easy | 56 | ||||
| Medium | 42 | |||||
| Hard | 34 | |||||
| All | 132 | |||||
| Medium-Stitch | Easy | 43 | ||||
| Medium | 41 |
| Dataset type | Tasks | SAGAS SR | AP-HIQL SR | SR (pp) |
|---|---|---|---|---|
| Navigate | 900 | 64.78% | 60.67% | |
| Stitch | 900 | 69.44% | 47.00% | |
| Explore | 600 | 86.00% | 33.83% | |
| All | 2,400 | 71.83% | 48.83% |
| Setting / task construction | Tasks | Accepting lassos | SR |
|---|---|---|---|
| (a) AntMaze: overlapping regions, | |||
| Giant-Stitch | 160 | 149/160 | 130/160 (81.3%) |
| Large-Explore | 160 | 143/160 | 130/160 (81.3%) |
| All overlapping-region tasks | 320 | 292/320 | 260/320 (81.3%) |
| (b) OGBench Scene: joint object configurations, | |||
| 24 formulas five initial states | 120 | 120/120 | 81/120 (67.5%) |
| Task family | Tasks | Accepting lassos | SR |
|---|---|---|---|
| AntMaze Giant-Stitch ( ) | |||
| Overlap event | 40 | 36/40 | 33/40 (82.5%) |
| Negative-until overlap | 40 | 37/40 | 34/40 (85.0%) |
| Recurrent overlap | 40 | 37/40 | 34/40 (85.0%) |
| Ordered overlap | 40 | 39/40 | 29/40 (72.5%) |
| AntMaze Large-Explore ( ) | |||
| Failure mode | Count | Failed cases (%) | All cases (%) |
|---|---|---|---|
| Prefix execution or semantic realization failure | 930 | 64.4 | 22.1 |
| Suffix-cycle or finite-lasso realization failure | 423 | 29.3 | 10.1 |
| No accepting prefix or suffix found | 90 | 6.2 | 2.1 |
| Domain | Cases | Successes | SR (%) | Prefix failure | Suffix failure | Planning failure |
|---|---|---|---|---|---|---|
| AntMaze | 2400 | 1724 | 71.8 | 417 (61.7%) | 206 (30.5%) | 53 (7.8%) |
| HumanoidMaze | 1800 | 1033 | 57.4 | 513 (66.9%) | 217 (28.3%) | 37 (4.8%) |
| Environment | Difficulty | SAGAS | w/o soft | w/o steering | |||
|---|---|---|---|---|---|---|---|
| SR (%) | NCC | SR (%) | NCC | SR (%) | NCC | ||
| Ant Large-Explore | Easy | ||||||
| Medium | |||||||
| Hard | |||||||
| Average | |||||||
| Humanoid Medium-Stitch | Easy | ||||||
| Setting | Spearman |
|---|---|
| AntMaze Giant-Navigate | 0.974 |
| AntMaze Giant-Stitch | 0.887 |
| AntMaze Large-Explore | 0.746 |
| AntMaze Large-Navigate | 0.973 |
| AntMaze Large-Stitch | 0.979 |
| HumanoidMaze Giant-Stitch | 0.893 |
| Data | Nodes | Edges | Accepting lassos | Time (s) | |||
| Medium | Hard | Medium | Hard | ||||
| AntMaze Large-Stitch (30 tasks per difficulty) | |||||||
| 6 | 100% | 3,500 | 86,194 | 30/30 | 27/30 | 3.80 | 10.08 |
| 8 | 100% | 1,563 | 29,166 | 30/30 | 28/30 | 1.81 | 4.10 |
| 10 | 100% | 855 | 10,710 | 30/30 | 27/30 | 1.13 | 2.01 |
| AntMaze Large-Explore (30 tasks per difficulty) | |||||||
| Coordinates | Support | Predicates | Connected | Matching states | Time (s) |
|---|---|---|---|---|---|
| 3 | 25% | 2 | 6/6 | 234.0–238.5 | 2.33–2.51 |
| 3 | 50% | 2 | 6/6 | 462.5–474.0 | 4.56–5.26 |
| 3 | 100% | 2 | 6/6 | 939.0 | 9.30 |
| 5 | 25% | 5 | 6/6 | 33.0–46.0 | 4.48–4.73 |
| 5 | 50% | 5 | 6/6 | 71.0–82.0 | 8.64–9.01 |
| 5 | 100% | 5 | 6/6 | 149.0 | 17.54 |
| Domain | Difficulty | Medium | Large | Giant |
|---|---|---|---|---|
| AntMaze | Easy | |||
| Medium | ||||
| Hard | ||||
| HumanoidMaze | Easy | |||
| Medium | ||||
| Hard |
| Stage | Median | p95 | Maximum |
|---|---|---|---|
| Semantic graph augmentation | 39.61 | 54.07 | 55.34 |
| Product search | 0.51 | 1.75 | 1.99 |
| Total planning | 40.63 | 55.38 | 57.09 |
| Setting | Est. states | Nodes | Edges | Compression | Support |
|---|---|---|---|---|---|
| AntMaze (29D state) | |||||
| Giant-Navigate | 1,000,000 | 978 | 7,522 | 1,022 | 27 / 244.8 |
| Giant-Stitch | 1,000,000 | 2,080 | 35,900 | 481 | 22 / 123.0 |
| Large-Explore | 5,000,000 | 2,514 | 34,390 | 1,989 | 18.5 / 129.0 |
| Large-Navigate | 1,000,000 | 1,092 | 12,310 | 916 | 22 / 196.9 |
| Large-Stitch | 1,000,000 | 1,563 | 29,166 | 640 | 24 / 169.0 |
| Difficulty | NBA states | DNF transitions |
|---|---|---|
| Easy | 5 / 32 / 32 | 15 / 243 / 243 |
| Medium | 6 / 29 / 33 | 19 / 243 / 340 |
| Hard | 16 / 217 / 1,520 | 81 / 5,265 / 80,379 |
| All | 7 / 90 / 1,520 | 27 / 1,299 / 80,379 |
| Difficulty | Cartesian states | Reachable states | Reachable edges |
|---|---|---|---|
| Easy | 12,630 / 83,251 / 159,240 | 12,600 / 81,659 / 127,392 | 437,414 / 2,211,939 / 5,618,768 |
| Medium | 16,318 / 74,047 / 159,240 | 14,227 / 72,031 / 103,507 | 415,586 / 3,173,433 / 4,557,727 |
| Hard | 33,534 / 262,726 / 414,336 | 23,178 / 256,878 / 378,726 | 805,823 / 11,338,466 / 18,863,198 |
| Variant | Median (s) | p95 (s) |
|---|---|---|
| On-demand A*, | 4.28 | 58.22 |
| On-demand Dijkstra, | 4.58 | 62.73 |
| Explicit-product Dijkstra, | 5.02 | 74.32 |
| Exhaustive accepting-endpoint reference | 5.33 | 77.59 |
| Feasibility agreement | Exact-cost agreement | Median time (s) | p95 time (s) | |
|---|---|---|---|---|
| 1 | 37/40 | 34/39 | 2.72 | 24.92 |
| 3 | 40/40 | 37/39 | 3.53 | 36.84 |
| 5 | 40/40 | 39/39 | 4.28 | 58.22 |
| 10 | 40/40 | 39/39 | 4.31 | 108.93 |
Robot Task Planning
Robot task planning turns goals and observations into executable actions while coordinating skills, motion, uncertainty, and safety.
See all 252 papers