Volume 3 · Issue 10 (2026)
DOI number:
10.66521/2938-9933-2026102903
Applicability Boundaries and an Evaluation Protocol for a Differential Heuristic in Segmented SIPP for Risk-Aware 3-D UAV Path Finding
Jingyu Li1, Juan Pan2,*
1Academy of Telecommunications Technology, Beijing, China
2China Academy of Information and Communications Technology, Beijing, China
Corresponding Author: Juan Pan (2087800775@qq.com)
Abstract: This paper reports two things together: a lower bound for segmented safe-interval path planning (SIPP), and the audit protocol that decides whether the bound earns its keep. The setting is three-dimensional multi-agent path finding (MAPF) over static risk-weighted edges. For each agent a, one reverse Dijkstra pass from its own goal ga fills a table Ha[x] equal to the exact static spatial distance Cspace*(x). The table has a single source: it answers “cost from s to ga” and holds no entry for “cost from s to an intermediate via-point v”. The bound Hdiff(s,v)=Ha[s]-Ha[v] closes that gap at no second table, and admissibility and consistency are proved on the static spatial graph. On the 18-agent benchmark, low-level expansions fall from 98926 to 19641 (-80.1%). Over 24 Latin-hypercube scenes the median saving per high-level node is 3.02-fold (quartiles 1.80, 3.91). Under pure CBS at w=1.0 the net factor is 0.99—no gain, and we report it as such. Two boundaries surfaced during the audits. Adding a turn cost while the low-level state carries only the voxel position costs 0.38%–0.95% of low-level optimality; an inadmissible Euclidean control returns feasible paths 16.15% above the optimum at the root. Section 5 states the protocol in full. Focal-CBS solves 24 of 24 scenes under the tested budgets; prioritized planning solves 4. The a posteriori ratio is ρ≤1.000434 with the prioritized-planning cost as numerator. Every exactness claim concerns the static spatial graph; optimality for general time-varying SIPP is not established here.
Keywords: Multi-UAV path planning; Conflict-based search; Safe-interval path planning; Admissible heuristic; True-distance heuristic; Differential lower bound; Evaluation protocol; Benchmark design
References
[1]
G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” Artificial Intelligence, vol. 219, pp. 40–66, 2015, doi: 10.1016/j.artint.2014.11.006.
[2]
M. Barer, G. Sharon, R. Stern, and A. Felner, “Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem,” Proc. Int. Symp. Combinatorial Search, vol. 5, no. 1, pp. 19–27, 2014, doi: 10.1609/socs.v5i1.18315.
[3]
N. R. Sturtevant, A. Felner, M. Barer, J. Schaeffer, and N. Burch, “Memory-based heuristics for explicit state spaces,” Proc. Int. Joint Conf. Artificial Intelligence, pp. 609–614, 2009.
[4]
A. V. Goldberg and C. Harrelson, “Computing the shortest path: A* search meets graph theory,” Proc. ACM–SIAM Symp. Discrete Algorithms, pp. 156–165, 2005.
[5]
K. C. Ng and H. Zhang, “Differential heuristics for search,” Proc. Int. Conf. Tools with Artificial Intelligence, pp. 98–105, 2002.
[6]
M. Phillips and M. Likhachev, “SIPP: Safe interval path planning for dynamic environments,” Proc. IEEE Int. Conf. Robotics and Automation, pp. 5628–5635, 2011, doi: 10.1109/ICRA.2011.5980306.
[7]
A. Andreychuk, K. Yakovlev, P. Surynek, D. Atzmon, and R. Stern, “Multi-agent pathfinding with continuous time,” Artificial Intelligence, vol. 305, Art. no. 103662, 2022, doi: 10.1016/j.artint.2022.103662.
[8]
A. Andreychuk and K. Yakovlev, “Multi-agent path finding with kinematic constraints via conflict based search,” in Robotics and Artificial Intelligence, LNCS, vol. 12412, pp. 29–45, 2020, doi: 10.1007/978-3-030-59535-7_3.
[9]
W. Hoenig, T. K. Kumar, L. Cohen, H. Ma, H. Xu, N. Ayanian, and S. Koenig, “Multi-agent path finding with kinematic constraints,” Proc. Int. Conf. Automated Planning and Scheduling, vol. 26, no. 1, pp. 477–485, 2016, doi: 10.1609/icaps.v26i1.13796.
[10]
M. Cap, M. Vokrinek, and A. Kleiner, “Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures,” Proc. Int. Conf. Automated Planning and Scheduling, vol. 25, no. 1, pp. 324–332, 2015, doi: 10.1609/icaps.v25i1.13696.
[11]
H. Ma, D. Harabor, P. J. Stuckey, J. Li, and S. Koenig, “Searching with consistent prioritization for multi-agent path finding,” Proc. AAAI Conf. Artificial Intelligence, vol. 33, no. 1, pp. 7643–7650, 2019, doi: 10.1609/aaai.v33i01.33017643.
[12]
H. T. To, S. Nguyen, and N. H. Pham, “CAHC: A general conflict-aware heuristic caching framework for multi-agent path finding,” arXiv:2512.12243, 2025, doi: 10.48550/arXiv.2512.12243.
[13]
Y. Yu and M. Le, “A spatio-temporal collaborative improved multi-strategy dung beetle optimization algorithm for 3D path planning of multiple unmanned aerial vehicles in urban environments,” Aerospace, vol. 13, no. 6, Art. no. 506, 2026, doi: 10.3390/aerospace13060506.
[14]
M. C. Gencal, B. Ata, M. Kurucan, et al., “An improved roosters algorithm for constrained 3D UAV path planning in urban environments,” Scientific Reports, vol. 15, Art. no. 40975, 2025, doi: 10.1038/s41598-025-24752-8.
[15]
T. Lei, S. Liu, and Y. Lei, “Hierarchical path planning for low-altitude logistics UAVs in complex urban environments: An enhanced weighted A* approach with geometric smoothing,” Frontiers in Robotics and AI, vol. 13, Art. no. 1802470, 2026, doi: 10.3389/frobt.2026.1802470.
[16]
D. B. Johnson, “Efficient algorithms for shortest paths in sparse networks,” J. ACM, vol. 24, no. 1, pp. 1–13, 1977, doi: 10.1145/321992.321993.
[17]
M. D. McKay, R. J. Beckman, and W. J. Conover, “A comparison of three methods for selecting values of input variables in the analysis of output from a computer code,” Technometrics, vol. 21, no. 2, pp. 239–245, 1979, doi: 10.1080/00401706.1979.10489755.
[18]
M. Likhachev, G. J. Gordon, and S. Thrun, “ARA*: Anytime A* with provable bounds on sub-optimality,” in Advances in Neural Information Processing Systems, vol. 16, pp. 767–774, 2003.
[19]
J. T. Thayer and W. Ruml, “Bounded suboptimal search: A direct approach using inadmissible estimates,” Proc. Int. Joint Conf. Artificial Intelligence, pp. 674–679, 2011.
[20]
J. Li, W. Ruml, and S. Koenig, “EECBS: A bounded-suboptimal search for multi-agent path finding,” Proc. AAAI Conf. Artificial Intelligence, vol. 35, no. 14, pp. 12353–12362, 2021, doi: 10.1609/aaai.v35i14.17466.
Download PDF