Research map / Video / Video segmentation and tracking
Temporal Task and Motion Planning with Metric Time for Multiple Object Navigation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes Temporal Task and Motion Planning (TTAMP) with metric time and simultaneous object motion, and presents T-TAMPEST, an interleaved incremental-SMT and sampling-based motion planning solver with five new benchmarks.
Problem
Integrating metric time (durations, deadlines, overlapping actions) into Task and Motion Planning for concurrent multi-object navigation, where existing TAMP ignores temporal constraints and temporal planners ignore motion feasibility.
Approach
Interleaves an incremental SMT-based temporal planner with a sampling-based motion planner (ST-RRT*); geometric obstacle/unreachable-region data prunes symbolic space, while motion failures on overlapping actions are encoded as temporal constraints (ordering, durations, waiting times) that prune classes of temporal plans.
Key results
- On Timed Doors, the full geometric refinement (All) solved 32 of 48 instances in 134.98 s average versus 29 in 351.09 s without refinements.
- On MAJSP, All solved 15 of 36 instances in 352.54 s average versus 14 in 615.79 s for None.
- Across all benchmarks, No-Refinements and Only-Reachables solve about 10% more instances than All-Refinements, while All reduces overall running time by about 20%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add full geometric refinements for unreachable locations and blocking obstacles (ablation) | T-TAMPEST · Timed Doors | average running time on solved instances: 351.09 s -> 134.98 s | Helped |
| Add full geometric refinements for unreachable locations and blocking obstacles (ablation) | T-TAMPEST · Timed Doors | solved instances: 29 -> 32 | Helped |
| Add full geometric refinements for unreachable locations and blocking obstacles (ablation) | T-TAMPEST · MAJSP | average running time on solved instances: 615.79 s -> 352.54 s | Helped |
| Add full geometric refinements for unreachable locations and blocking obstacles (ablation) | T-TAMPEST · MAJSP | solved instances: 14 -> 15 | Helped |
| Add full geometric refinements for unreachable locations and blocking obstacles (ablation) | T-TAMPEST · Driverlog | solved instances: 12 -> 10 | Hurt |
| Add full geometric refinements for unreachable locations and blocking obstacles (ablation) | T-TAMPEST · Kitting | solved instances: 33 -> 26 | Hurt |
| Add full geometric refinements for unreachable locations and blocking obstacles (ablation) | T-TAMPEST · Floortile | solved instances: 64 -> 53 | Hurt |
| Use full geometric refinements instead of no geometric refinements (ablation) | T-TAMPEST · all benchmark instances | overall running time: ∼20% | Helped |
| Use only unreachable-target refinements instead of full geometric refinements (ablation) | T-TAMPEST · Timed Doors | average running time on solved instances: 136.07 s -> 134.98 s | No clear effect |
| Use only blocking-obstacle refinements instead of full geometric refinements (ablation) | T-TAMPEST · Kitting | solved instances: 26 -> 35 | Helped |
| Use only blocking-obstacle refinements instead of full geometric refinements (ablation) | T-TAMPEST · Floortile | average running time on solved instances: 500.70 s -> 565.67 s | No clear effect |
| Use only unreachable-target refinements instead of full geometric refinements (ablation) | T-TAMPEST · MAJSP | solved instances: 15 -> 15 | No clear effect |
Surprising findings
- Full geometric refinement reduces total running time but solves about 10% fewer instances than No-Refinements or Only-Reachables across all benchmarks.
- Kitting and Floortile scale poorly because of SMT encoding size, despite the motion component being light.
Limitations
- The approach is incomplete; completeness is left for future work.
- Scalability is limited by the SMT encoding for domains with many non-geometric actions such as Kitting and Floortile.
- Only tested in 2D simulated maps with a sampling-based motion planner; no real-robot experiments.
Experimental setup
Datasets: five TTAMP benchmarks (Timed Doors, Driverlog, Kitting, MAJSP, Floortile)
Benchmarks: Timed Doors Driverlog Kitting MAJSP Floortile
Metrics: number of instances solved average running time on solved instances percentage of time in motion planner
Baselines: T-TAMPEST(None) T-TAMPEST(Only-Reachable) T-TAMPEST(Only-Obstacles)
Builds on: PDDL 2.1 Level 3 Panjkovic and Micheli SMT-based planning encoding Tosello et al. 2024 TAMP modeling tool and geometric learning ST-RRT*
Closest papers by meaning
- Physics-informed Temporal Difference Metric Learning for Robot Motion Planning (ICLR 2025 · similarity 0.84)
- Zero-Shot Trajectory Planning for Signal Temporal Logic Tasks (NeurIPS 2025 · similarity 0.83)
- TP-MDDN: Task-Preferenced Multi-Demand-Driven Navigation with Autonomous Decision-Making (NeurIPS 2025 · similarity 0.83)
- Automatic Selection of Macro-Events for Heuristic-Search Temporal Planning (AAAI 2025 · similarity 0.83)
- Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI 2024 · similarity 0.83)
- Abstract Action Scheduling for Optimal Temporal Planning via OMT (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.