Speedup Techniques for Switchable Temporal Plan Graph Optimization
Authors: He Jiang, Muhan Lin, Jiaoyang Li
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments conducted on four different map types with varying numbers of agents demonstrate that Improved GSES consistently achieves over twice the success rate of GSES and delivers up to a 30-fold speedup on instances where both methods successfully find solutions. |
| Researcher Affiliation | Academia | He Jiang, Muhan Lin, Jiaoyang Li Carnegie Mellon University EMAIL |
| Pseudocode | Yes | Algorithm 1 shows the pseudocode of GSES,4 a best-first search algorithm with each search node comprising three parts: an STPG, its execution cost, and the EATs of all vertices in its reduced TPG (Line 23). |
| Open Source Code | Yes | The code and benchmark are publicly available.7 https://github.com/Diligent Panda/STPG.git |
| Open Datasets | Yes | Following the setting in the baseline GSES paper (Feng et al. 2024), we evaluate algorithms on four maps from the MAPF benchmark (Stern et al. 2019) |
| Dataset Splits | No | For each map and each number of agents, we generate 25 different instances with start and goal locations evenly distributed. We then run 1-robust PBS on each instance to obtain the initial MAPF plans. We add the 1robust requirement (Atzmon et al. 2018) to PBS (Ma et al. 2019) because the original PBS does not resolve the following conflicts. Each solved instance is tested with 6 different delay scenarios. |
| Hardware Specification | Yes | All the experiments are conducted on a server with an Intel(R) Xeon(R) Platinum 8352V CPU and 120 GB RAM. |
| Software Dependencies | No | All the algorithms in the experiments are implemented in C++.6 MILP also uses a Python wrapper, so we count only its C++ solver s time for a fair comparison. |
| Experiment Setup | Yes | For each map and each number of agents, we generate 25 different instances with start and goal locations evenly distributed. We then run 1-robust PBS on each instance to obtain the initial MAPF plans. ... Each solved instance is tested with 6 different delay scenarios. We obtain a scenario by simulating the initial MAPF plan until some delays happen. An agent will be independently delayed for 10-20 steps with a constant probability p {0.002, 0.01, 0.03} at each step. We run 8 times for each scenario and set a time limit of 16 seconds for each run. |