Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Speedup Techniques for Switchable Temporal Plan Graph Optimization
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.
Improves the optimal GSES search for Switchable Temporal Plan Graph optimization with stronger admissible heuristics, full edge grouping, prioritized branching, and incremental longest-path computation, yielding IGSES.
Problem
Finding the minimum-execution-cost acyclic Temporal Plan Graph under agent delays (STPG optimization) is too slow for practical use at scale with optimal methods like MILP and GSES.
Approach
Speeds up GSES with four techniques: a stronger admissible heuristic estimating future cost from unsettled switchable edges (via vertex slack and a greedy edge-weighted vertex cover), full maximal edge grouping that finds all groupable switchable edges, smallest-edge-slack-first branching, and incremental forward/backward longest path computation.
Key results
- IGSES consistently achieves over twice the success rate of GSES across maps and agent counts.
- IGSES achieves up to a 30-fold speedup over GSES on instances solved by both methods (10- to 30-fold per the paper), with over 90% reduction in expanded nodes.
- Full grouping reduces the number of edge groups substantially compared with simple grouping (e.g., Random map 1176 to 733 groups at p=0.01).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IGSES instead of GSES | STPG optimization · Random-32-32-10 | search time (s): 1.421 -> 0.043 | Helped |
| Use IGSES instead of GSES | STPG optimization · Warehouse-10-20-10-2-1 | search time (s): 3.805 -> 0.120 | Helped |
| Use IGSES instead of GSES | STPG optimization · Lak303d | search time (s): 2.608 -> 0.221 | Helped |
| Use IGSES instead of GSES | STPG optimization · Paris_1_256 | search time (s): 5.221 -> 0.321 | Helped |
| Add full grouping instead of no grouping (ablation) | GSES · All four maps | search time (s): Random-32-32-10: 1.421 -> 0.945; Warehouse-10-20-10-2-1: 3.805 -> 1.519; Lak303d: 2.608 -> 1.021; Paris_1_256: 5.221 -> | Helped |
| Use full grouping instead of simple grouping (ablation) | GSES with edge grouping · All four maps | search time (s): Random-32-32-10: 1.082 -> 0.945; Warehouse-10-20-10-2-1: 1.783 -> 1.519; Lak303d: 1.242 -> 1.021; Paris_1_256: 3.131 -> | Helped |
| Use random branching instead of Agent-First branching (ablation) | Full grouping · All four maps | search time (s): Random-32-32-10: 0.945 -> 1.555; Warehouse-10-20-10-2-1: 1.519 -> 2.685; Lak303d: 1.021 -> 2.644; Paris_1_256: 2.770 -> | Hurt |
| Use Earliest-First branching instead of Agent-First branching (ablation) | Full grouping · All four maps | search time (s): Random-32-32-10: 0.945 -> 1.185; Warehouse-10-20-10-2-1: 1.519 -> 2.354; Lak303d: 1.021 -> 1.481; Paris_1_256: 2.770 -> | Hurt |
| Use Smallest-Edge-Slack-First instead of Agent-First branching (ablation) | Full grouping · All four maps | search time (s): Random-32-32-10: 0.945 -> 0.915; Warehouse-10-20-10-2-1: 1.519 -> 1.472; Lak303d: 1.021 -> 1.027; Paris_1_256: 2.770 -> | Helped |
| Add stronger heuristics (ablation) | Full grouping + Smallest-Edge-Slack-First · All four maps | search time (s): Random-32-32-10: 0.915 -> 0.169; Warehouse-10-20-10-2-1: 1.472 -> 0.832; Lak303d: 1.027 -> 0.871; Paris_1_256: 2.472 -> | Helped |
| Add incremental implementation (ablation) | Full grouping + Smallest-Edge-Slack-First + stronger heuristics · All four maps | search time (s): Random-32-32-10: 0.169 -> 0.043; Warehouse-10-20-10-2-1: 0.832 -> 0.120; Lak303d: 0.871 -> 0.221; Paris_1_256: 1.561 -> | Helped |
Surprising findings
- Random and Earliest-First branching are slower than GSES's Agent-First default on several maps, so the branching choice matters and smallest-edge-slack-first is needed to gain speed.
Limitations
- Still an exact search that does not scale to very large instances; success rates remain low at 100+ agents.
- Greedy matching gives only an underestimate of the minimum vertex cover, so the heuristic is not tight.
- Evaluated only with unit edge costs in the main text and on four maps.
Experimental setup
Datasets: MovingAI MAPF benchmark maps (Random-32-32-10, Warehouse-10-20-10-2-1, Lak303d, Paris_1_256)
Benchmarks: Random-32-32-10 Warehouse-10-20-10-2-1 Lak303d Paris_1_256
Metrics: success rate search time number of expanded nodes speedup
Baselines: GSES MILP CBS-D
Builds on: GSES Switchable Temporal Plan Graph PBS k-robust PBS Weighted Pairwise Dependency Graph CBS
Closest papers by meaning
- Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI 2024 · similarity 0.92)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.91)
- Windowed MAPF with Completeness Guarantees (AAAI 2025 · similarity 0.89)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.88)
- Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic (AAAI 2025 · similarity 0.87)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.87)
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.