Adi Botea, Jussi Rintanen, et al.
IEEE Transactions on Smart Grid
Most existing pathfinding methods are based on runtime search. Despite an impressive progress achieved in recent years, search-based methods could explore, in bad cases, large portions of a map, leading to an increased running time. We take a significantly different approach from search-based methods. Given a map, our program precomputes all-pairs shortest paths (APSP) information. APSP data are compressed, reducing the size dramatically with no information loss. We call the resulting data a compressed path database (CPD). At runtime, optimal moves are retrieved one by one until a complete (or partial, if desired) optimal path is retrieved. CPDs lead to a fast path computation, eliminating the need for runtime search. The first move lag is very low, as each move is retrieved independently from subsequent moves. The price to pay includes a significant preprocessing time and memory to build and store a CPD.
Adi Botea, Jussi Rintanen, et al.
IEEE Transactions on Smart Grid
Mattia Chiari, Shizhe Zhao, et al.
ICAPS 2019
Radu Marinescu, Akihiro Kishimoto, et al.
AAAI 2020
Adi Botea, Akihiro Kishimoto, et al.
SoCS 2018