Abstract
This paper presents two new bidirectional heuristic search algorithms for solving the shortest path problem on graphs: consistent-heuristic bucket-based bidirectional search (CBBS) and front-to-front GPU bidirectional search (FFGBS). CBBS uses a consistent heuristic and groups nodes into buckets that organize nodes based on estimated path cost and known heuristic errors. FFGBS splits the work between the CPU and GPU, with the GPU solving a front-to-front heuristic and the CPU choosing nodes to expand. This paper also includes a new front-to-front version of the GAP heuristic for the pancake problem that is efficient to solve on a GPU. Computational experiments for CBBS are performed on the pancake problem. CBBS is faster and requires less node expansions with the GAP-1 heuristic, compared to bidirectional state of the algorithms like DIBBS and DVCBS. Computational experiments for FFGBS are performed on the pancake problem and DIMACS road network, showing that FFGBS is consistently the fastest algorithm on all but the smallest pancake stacks when using the GAP-2 heuristic and is also the fastest algorithm on the largest road networks.
Similar content being viewed by others
Code availability
Algorithm implementation source code and testing framework are available at: https://github.com/tinamil/dibbs/releases/tag/two_algorithms-1.0
References
Alcázar, V., Riddle, P., Barley, M.: A unifying view on individual bounds and heuristic inaccuracies in bidirectional search. Proc. AAAI Conf. Artif. Intell. 34(03), 2327–2334 (2020)
Barker, J.K., Korf, R.E.: Limitations of front-to-end bidirectional heuristic search. In: Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)
Barley, M., Riddle, P., Lopez, C.L., Dobson, S., Pohl, I.S.: GBFHS: A generalized breadth-first heuristic search algorithm. In: Eleventh Annual Symposium on Combinatorial Search (2018)
de Champeaux, D.: Bidirectional heuristic search again. J. ACM 30(1), 22–32 (1983)
Chen, J., Holte, R.C., Zilles, S., Sturtevant, N.R.: Front-to-end bidirectional heuristic search with near-optimal node expansions. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, pp. 489–495 (2017)
Dantzig, G.: Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963)
Dijkstra, E.W., et al.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)
Dweighter, H.: Elementary problem: E2569. Am. Math. Mon 82(10), 1009–1010 (1975)
Eckerle, J., Chen, J., Sturtevant, N.R., Zilles, S., Holte, R.C.: Sufficient conditions for node expansion in bidirectional heuristic search. In: Twenty-Seventh International Conference on Automated Planning and Scheduling (2017)
Ghorpade, J., Parande, J., Kulkarni, M., Bawaskar, A.: GPGPU processing in CUDA architecture. Adv. Comput. Int. J. 3(1), 105–120 (2012)
Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Helmert, M.: Landmark heuristics for the pancake problem. In: Third Annual Symposium on Combinatorial Search (2010)
Holte, R.C., Felner, A., Sharon, G., Sturtevant, N.R.: Bidirectional search that is guaranteed to meet in the middle. In: Thirtieth AAAI Conference on Artificial Intelligence (2016)
Holte, R.C., Felner, A., Sharon, G., Sturtevant, N.R., Chen, J.: MM: a bidirectional search algorithm that is guaranteed to meet in the middle. Artif. Intell. 252, 232–266 (2017)
Intel: Intel 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4 (2020). https://software.intel.com/content/www/us/en/develop/download/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4.html. Accessed 19 Jan 2021
Jiang, J., Huang, H., Liao, J., Chen, S.: Extending Dijkstra’s shortest path algorithm for software defined networking. In: The 16th Asia-Pacific Network Operations and Management Symposium, pp. 1–4 (2014)
Kaindl, H., Kainz, G.: Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. 7, 283–317 (1997)
Nicholson, T.A.J.: Finding the shortest route between two points in a network. Comput. J. 9(3), 275–280 (1966)
NVIDIA: CUDA math api (2019). https://docs.nvidia.com/cuda/pdf/CUDA_Math_API.pdf. Accessed 19 Jan 2021
NVIDIA: Cuda c++ programming guide (2021). https://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf. Accessed 20 Jan 2021
Peyer, S., Rautenbach, D., Vygen, J.: A generalization of Dijkstra’s shortest path algorithm with applications to VLSI routing. J Discrete Algorithms 7(4), 377–390 (2009)
Pohl, I.S.: Bi-directional and heuristic search in path problems. PhD Thesis, Stanford University, Stanford, CA, USA (1969)
Pohl, I.S.: Bi-directional search. Mach. Intell. 6, 127–140 (1971)
Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Prentice Hall Press, Upper Saddle River (2009)
Sadhukhan, S.K.: A new approach to bidirectional heuristic search using error functions. In: Proceedings of 1st International Conference on Intelligent Infrastructure at the 47th Annual National Convention Computer Soceity of India (CSI-2012) (2012)
Sewell, E.C., Jacobson, S.H.: Dynamically improved bounds bidirectional search. Artif. Intell. 291, 103405 (2021)
Shperberg, S.S., Felner, A., Sturtevant, N.R., Hayoun, A., Shimony, S.E.: Enriching non-parametric bidirectional search algorithms. In: AAAI Conference on Artificial Intelligence, vol. 33 (2019)
Sint, L., de Champeaux, D.: An improved bidirectional heuristic search algorithm. J. ACM 24(2), 177–191 (1977)
Zahavi, U., Felner, A., Schaeffer, J., Sturtevant, N.: Inconsistent heuristics. In: Proceedings of the 22nd national conference on Artificial intelligence—Volume 2, AAAI’07, pp. 1211–1216. AAAI Press, Vancouver, British Columbia, Canada (2007)
Zeng, W., Church, R.L.: Finding shortest paths on real road networks: the case for A*. Int. J. Geograph. Inf. Sci. 23(4), 531–543 (2009)
Acknowledgements
We would like to thank the anonymous reviewers for their comments that resulted in a significantly improved manuscript.
Funding
S. H. Jacobson’s research was supported in part by the Air Force Office of Scientific Research (FA9550-19-1-0106). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the United States Air Force, Department of Defense, or the United States Government. Other authors did not receive support from any organization for the submitted work.
Author information
Authors and Affiliations
Contributions
All authors contributed to the algorithm conception and design. Algorithm C++ implementations and testing framework was written by John A. Pavlik with contributions to the testing framework from Edward C. Sewell. The first draft of the manuscript was written by John A. Pavlik and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.
Corresponding author
Ethics declarations
Conflict of interest
The authors have no conflicts of interest to declare that are relevant to the content of this article.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Pavlik, J.A., Sewell, E.C. & Jacobson, S.H. Two new bidirectional search algorithms. Comput Optim Appl 80, 377–409 (2021). https://doi.org/10.1007/s10589-021-00303-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-021-00303-5