A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Abstract
Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
A* was selected over Monte Carlo Tree Search for building ERCs because its behavior is more consistent and reproducible.
“Finally, we chose to use A* (Hart, Nilsson, and Raphael 1968) as part of the approach to creating ERCs over other popular algorithms like Monte Carlo Tree Search (Chaslot et al. 2006) due to its more consistent and reproducible behavior.”
From Expressive Response Curves: Testing Expressive Game Feel with A* (2023) · cites this paper as Hart, Nilsson, and Raphael 1968
A* visits graph nodes breadth-first and uses a priority queue keyed on cost and heuristic values to steer the search toward a goal.
“A* uses a breadth-first approach to visiting graph nodes and a priority queue based on cost and heuristic values to guide the search towards a specific goal (Hart, Nilsson, and Raphael 1968).”
From Expressive Response Curves: Testing Expressive Game Feel with A* (2023) · cites this paper as Hart, Nilsson, and Raphael 1968
A* need not visit every node in a graph, and without an admissible heuristic it need not find an optimal path.
“Unlike breadth-first search, A* is not guaranteed to visit every node in a graph, nor is it guaranteed to find an optimal path without an admissible heuristic, a heuristic function which never over-estimates the distance to the goal (Hart, Nilsson, and Raphael 1968).”
From Expressive Response Curves: Testing Expressive Game Feel with A* (2023) · cites this paper as Hart, Nilsson, and Raphael 1968
Cites
Freimer, M. L., Bellman, R., & Dreyfus, S. E. (1964) · Journal of the American Statistical Association · doi:10.2307/2282884 · Cited by 2,173 · see citing works
Bellman, R., & Dreyfus, S. E. (1962) · Princeton University Press eBooks · doi:10.1515/9781400874651 · Cited by 1,973 · see citing works
The shortest path through a maze
Moore, E. (1959) · Medical Entomology and Zoology · Cited by 756 · see citing works
Solutions of the Shortest-Route Problem—A Review
Pollack, M., & Wiebenson, W. (1960) · Operations Research · doi:10.1287/opre.8.2.224 · Cited by 114 · see citing works
Finite Graphs and Networks, An Introduction with Applications.
Harary, F., Busacker, R. G., & Saaty, T. L. (1967) · American Mathematical Monthly · doi:10.2307/2314099 · Cited by 104 · see citing works
Flagged first, then by citations
2 of the 7 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
(1988) · Cited by 16,582 · see citing works
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B. A., Čáp, M., Yong, S. Z., Yershov, D. S., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,601 · see citing works
ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees
Zhang, C., Rabiee, M., Sayyari, E., & Mirarab, S. (2018) · BMC Bioinformatics · doi:10.1186/s12859-018-2129-y · Cited by 2,471 · see citing works
An algorithm for planning collision-free paths among polyhedral obstacles
Lozano‐Pérez, T., & Wesley, M. A. (1979) · Communications of the ACM · doi:10.1145/359156.359164 · Cited by 2,281 · see citing works
A Survey of Autonomous Driving: <i>Common Practices and Emerging Technologies</i>
Yurtsever, E., Lambert, J., Carballo, A., & Takeda, K. (2020) · IEEE Access · doi:10.1109/access.2020.2983149 · Cited by 1,889 · see citing works
“Graph search Dijkstra [250], A* [245], State lattice [251] Slow and jerky”
BackgroundMethodEXPERT SYSTEMS WITH APPLICATIONS
Communication, S., Been-chian Chien, A., Jung Yi Lin, A., Tzung-pei Hong, B., & Com/locate/eswa, W. E. (2004) · Expert Systems with Applications · doi:10.1016/j.eswa.2004.10.010 · Cited by 1,670 · see citing works
Depth-first iterative-deepening
Korf, R. E. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90084-0 · Cited by 1,621 · see citing works
A new Fruit Fly Optimization Algorithm: Taking the financial distress model as an example
Pan, W.-T. (2011) · Knowledge-Based Systems · doi:10.1016/j.knosys.2011.07.001 · Cited by 1,540 · see citing works
Sonar-based real-world mapping and navigation
Elfes, A. (1987) · IEEE Journal on Robotics and Automation · doi:10.1109/jra.1987.1087096 · Cited by 1,397 · see citing works
Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2014) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2014.6942976 · Cited by 1,282 · see citing works
Conflict-based search for optimal multi-agent pathfinding
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. (2014) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.006 · Cited by 1,268 · see citing works
Badue, C. S., Guidolini, R., Carneiro, R. V., Azevedo, P., Cardoso, V. B., Forechi, A., Jesus, L. F. R., Berriel, R. F., Paixão, T. M., Mutz, F. W., et al. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113816 · Cited by 1,257 · see citing works
Artificial Intelligence: A New Synthesis
(1998) · Elsevier eBooks · doi:10.1016/c2009-0-27773-7 · Cited by 1,207 · see citing works
Tree of Thoughts: Deliberate Problem Solving with Large Language Models
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., & Narasimhan, K. (2023) · arXiv · doi:10.48550/arxiv.2305.10601 · Cited by 1,158 · see citing works
Learning to act using real-time dynamic programming
Barto, A. G., Bradtke, S. J., & Singh, S. P. (1995) · Artificial Intelligence · doi:10.1016/0004-3702(94)00011-o · Cited by 1,108 · see citing works
Generalized best-first search strategies and the optimality of A*
Dechter, R., & Pearl, J. (1985) · Journal of the ACM · doi:10.1145/3828.3830 · Cited by 1,069 · see citing works
Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges
Aggarwal, S., & Kumar, N. (2019) · Computer Communications · doi:10.1016/j.comcom.2019.10.014 · Cited by 1,000 · see citing works
Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments
Dolgov, D., Thrun, S., Montemerlo, M., & Diebel, J. R. (2010) · The International Journal of Robotics Research · doi:10.1177/0278364909359210 · Cited by 986 · see citing works
Auto-Keras: An Efficient Neural Architecture Search System
Jin, H., Song, Q., & Hu, X. (2019) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3292500.3330648 · Cited by 963 · see citing works
Longair, M., Baker, D. A., & Armstrong, J. D. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr390 · Cited by 939 · see citing works
Continuous speech recognition by statistical methods
Jelinek, F. (1976) · Proceedings of the IEEE · doi:10.1109/proc.1976.10159 · Cited by 922 · see citing works
Korf, R. E. (1990) · Artificial Intelligence · doi:10.1016/0004-3702(90)90054-4 · Cited by 916 · see citing works
Map-matching for low-sampling-rate GPS trajectories
Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., & Huang, Y. (2009) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1653771.1653820 · Cited by 817 · see citing works
McMurchie, L., & Ebeling, C. (1995) · ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA) · doi:10.1145/201310.201328 · Cited by 807 · see citing works
Sampling-Based Robot Motion Planning: A Review
Elbanhawi, M., & Simić, M. (2014) · IEEE Access · doi:10.1109/access.2014.2302442 · Cited by 793 · see citing works
A review of mobile robots: Concepts, methods, theoretical framework, and applications
Rubio, F., Valero, F., & Llopis-Albert, C. (2019) · International Journal of Advanced Robotic Systems · doi:10.1177/1729881419839596 · Cited by 763 · see citing works
Computing the shortest path: A search meets graph theory
Goldberg, A. V., & Harrelson, C. (2005) · doi:10.5555/1070432.1070455 · Cited by 741 · see citing works
Silver, D. (2005) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v1i1.18726 · Cited by 740 · see citing works
Reconciling schemas of disparate data sources
Doan, A., Domingos, P., & Halevy, A. Y. (2001) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/375663.375731 · Cited by 732 · see citing works
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
Geisberger, R., Sanders, P., Schultes, D., & Delling, D. (2008) · Springer eBooks · doi:10.1007/978-3-540-68552-4_24 · Cited by 728 · see citing works
Automatic Planning of Manipulator Transfer Movements
Lozano‐Pérez, T. (1981) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1981.4308589 · Cited by 680 · see citing works
A Review of Motion Planning for Highway Autonomous Driving
Claussmann, L., Revilloud, M., Gruyer, D., & Glaser, S. (2019) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2913998 · Cited by 678 · see citing works
Autoware on Board: Enabling Autonomous Vehicles with Embedded Systems
Kato, S., Tokunaga, S., Maruyama, Y., Maeda, S., Hirabayashi, M., Kitsukawa, Y., Monrroy, A., Ando, T., Fujii, Y., & Azumi, T. (2018) · ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS) · doi:10.1109/iccps.2018.00035 · Cited by 667 · see citing works
Perception, Planning, Control, and Coordination for Autonomous Vehicles
Pendleton, S., Andersen, H., Du, X., Shen, X., Meghjani, M., Eng, Y., Rus, D., & Ang, M. (2017) · Machines · doi:10.3390/machines5010006 · Cited by 657 · see citing works
A Survey and Analysis of Multi-Robot Coordination
Yan, Z., Jouandeau, N., & Ali-Chérif, A. (2013) · International Journal of Advanced Robotic Systems · doi:10.5772/57313 · Cited by 651 · see citing works
Approximate graph edit distance computation by means of bipartite graph matching
Riesen, K., & Horst Bunke, A. (2008) · Image and Vision Computing · doi:10.1016/j.imavis.2008.04.004 · Cited by 651 · see citing works
Theta*: Any-Angle Path Planning on Grids
Daniel, K., Nash, A., Koenig, S., & Felner, A. (2010) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2994 · Cited by 641 · see citing works
Wang, L., & Liu, H. (2006) · International Journal of Geographical Information Systems · doi:10.1080/13658810500433453 · Cited by 627 · see citing works
Similarity of business process models: Metrics and evaluation
Dijkman, R., Dumas, M., van Dongen, B. F., Käärik, R., & Mendling, J. (2010) · Information Systems · doi:10.1016/j.is.2010.09.006 · Cited by 612 · see citing works
Route Planning in Transportation Networks
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_2 · Cited by 610 · see citing works
Zafarani, R., Abbasi, M. A., & Liu, H. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139088510 · Cited by 608 · see citing works
Motion Planning for Autonomous Driving: The State of the Art and Future Perspectives
Teng, S., Hu, X., Deng, P., Li, B., Li, Y., Ai, Y., Yang, D., Li, L., Xuanyuan, Z., Zhu, F., et al. (2023) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2023.3274536 · Cited by 602 · see citing works
Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization
Phung, M. D., & Ha, Q. P. (2021) · Applied Soft Computing · doi:10.1016/j.asoc.2021.107376 · Cited by 583 · see citing works
Perceptual Structures and Distributed Motor Control
Arbib, M. A. (1981) · Comprehensive physiology · doi:10.1002/cphy.cp010233 · Cited by 576 · see citing works
De Novo Design and Structural Characterization of Proteins and Metalloproteins
DeGrado, W. F., Summa, C. M., Pavone, V., Nastri, F., & Lombardi, A. (1999) · Annual Review of Biochemistry · doi:10.1146/annurev.biochem.68.1.779 · Cited by 572 · see citing works
DeepRoadMapper: Extracting Road Topology from Aerial Images
Máttyus, G., Luo, W., & Urtasun, R. (2017) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.372 · Cited by 568 · see citing works
Neural RRT*: Learning-Based Optimal Path Planning
Wang, J., Chi, W., Li, C., Wang, C., & Meng, M. Q. ‐. (2020) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2020.2976560 · Cited by 565 · see citing works
An Open Approach to Autonomous Vehicles
Kato, S., Takeuchi, E., Ishiguro, Y., Ninomiya, Y., Takeda, K., & Hamada, T. (2015) · IEEE Micro · doi:10.1109/mm.2015.133 · Cited by 563 · see citing works
A Mobile Automaton: An Application of Artificial Intelligence Techniques
Nilsson, N. J. (1969) · doi:10.21236/ada459660 · Cited by 549 · see citing works
Self-citationSeparate-and-Conquer Rule Learning
Fürnkranz, J. (1999) · Artificial Intelligence Review · doi:10.1023/a:1006524209794 · Cited by 531 · see citing works
Tu, E., Zhang, G., Rachmawati, L., Rajabally, E., & Huang, G.-B. (2017) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2017.2724551 · Cited by 521 · see citing works
Usov, I., Nyström, G., Adamčík, J., Handschin, S., Schütz, C., Fall, A. B., Bergström, L., & Mezzenga, R. (2015) · Nature Communications · doi:10.1038/ncomms8564 · Cited by 495 · see citing works
Overview of the PALM model system 6.0
Maronga, B., Banzhaf, S., Burmeister, C., Esch, T., Forkel, R., Fröhlich, D., Fuka, V., Gehrke, K. F., Geletič, J., Giersch, S., et al. (2020) · Geoscientific model development · doi:10.5194/gmd-13-1335-2020 · Cited by 491 · see citing works
Path Planning for Autonomous Mobile Robots: A Review
Sánchez-Ibáñez, J. R., Pérez-del-Pulgar, C. J., & Garcia-Cerezo, A. J. (2021) · Sensors · doi:10.3390/s21237898 · Cited by 485 · see citing works
Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment
Tang, G., Tang, C., Claramunt, C., Hu, X., & Zhou, P. (2021) · IEEE Access · doi:10.1109/access.2021.3070054 · Cited by 483 · see citing works
Campbell, S. M., Naeem, W., & Irwin, G. W. (2012) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2012.09.008 · Cited by 478 · see citing works
Engineering Route Planning Algorithms
Delling, D., Sanders, P., Schultes, D., & Wagner, D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02094-0_7 · Cited by 466 · see citing works
Computing Systems for Autonomous Driving: State of the Art and Challenges
Liu, L., Lu, S., Ren, Z. G., Wu, B., Yao, Y., Zhang, Q., & Shi, W. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.3043716 · Cited by 463 · see citing works
Nazarahari, M., Khanmirza, E., & Doostie, S. (2018) · Expert Systems with Applications · doi:10.1016/j.eswa.2018.08.008 · Cited by 461 · see citing works
Proceedings of the 2002 Winter Simulation Conference
Henderson, S. G., Biller, B., Hsieh, M. H., Shortle, J., Tew, J. D., Barton, R. R., Xu, J., Yang, F., & Wan, H. (2002) · Winter Simulation Conference · doi:10.1109/wsc.2002.1166355 · Cited by 459 · see citing works
Path Planning for the Mobile Robot: A Review
Zhang, H.-Y., Lin, W., & Chen, A. (2018) · Symmetry · doi:10.3390/sym10100450 · Cited by 455 · see citing works
Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2015) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2015.7139620 · Cited by 454 · see citing works
Optimization-Based Collision Avoidance
Zhang, X., Liniger, A., & Borrelli, F. (2020) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2019.2949540 · Cited by 451 · see citing works
Heuristic search viewed as path finding in a graph
Pohl, I. (1970) · Artificial Intelligence · doi:10.1016/0004-3702(70)90007-x · Cited by 439 · see citing works
Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation
Hauck, S., & DeHon, A. M. (2007) · Cited by 437 · see citing works
Travel time estimation for urban road networks using low frequency probe vehicle data
Jenelius, E., & Koutsopoulos, H. N. (2013) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2013.03.008 · Cited by 433 · see citing works
A perception‐driven autonomous urban vehicle
Leonard, J., How, J., Teller, S., Berger, M., Campbell, S., Fiore, G., Fletcher, L., Frazzoli, E., Huang, A., Karaman, S., et al. (2008) · Journal of Field Robotics · doi:10.1002/rob.20262 · Cited by 429 · see citing works
Artificial intelligence: foundations of computational agents
(2010) · Choice Reviews Online · doi:10.5860/choice.48-2130 · Cited by 424 · see citing works
Jhala, R., & Majumdar, R. (2009) · ACM Computing Surveys · doi:10.1145/1592434.1592438 · Cited by 417 · see citing works
Sang, H., You, Y., Sun, X., Zhou, Y. S., & Liu, F. (2021) · Ocean Engineering · doi:10.1016/j.oceaneng.2021.108709 · Cited by 417 · see citing works
A Survey of Path Planning Algorithms for Mobile Robots
Karur, K., Sharma, N., Dharmatti, C., & Siegel, J. E. (2021) · Vehicles · doi:10.3390/vehicles3030027 · Cited by 412 · see citing works
Adaptive Locomotion of a Multilegged Robot over Rough Terrain
McGhee, R. B., & Iswandhi, G. (1979) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1979.4310180 · Cited by 410 · see citing works
Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy
Ziebart, B. D. (2010) · doi:10.1184/r1/6720692 · Cited by 400 · see citing works
Zeng, Z., Tung, A. K. H., Wang, J., Feng, J., & Zhou, L. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687631 · Cited by 397 · see citing works
Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2015) · Cited by 397 · see citing works
Using interpolation to improve path planning: The Field D * algorithm
Ferguson, D., & Stentz, A. (2006) · Journal of Field Robotics · doi:10.1002/rob.20109 · Cited by 395 · see citing works
Differentially constrained mobile robot motion planning in state lattices
Pivtoraiko, M., Knepper, R. A., & Kelly, A. (2009) · Journal of Field Robotics · doi:10.1002/rob.20285 · Cited by 394 · see citing works
Filtered beam search in scheduling†
Ow, P. S., & Morton, T. E. (1988) · International Journal of Production Research · doi:10.1080/00207548808947840 · Cited by 390 · see citing works
An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures
Zulehner, A., Paler, A., & Wille, R. (2018) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2018.2846658 · Cited by 382 · see citing works
Research Advances and Challenges of Autonomous and Connected Ground Vehicles
Eskandarian, A., Wu, C., & Sun, C. (2019) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2958352 · Cited by 380 · see citing works
Finding Optimal Solutions to Cooperative Pathfinding Problems
Standley, T. (2010) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v24i1.7564 · Cited by 370 · see citing works
Vision-based navigation and guidance for agricultural autonomous vehicles and robots: A review
Bai, Y., Zhang, B., Xu, N., Zhou, J. C., Shi, J., & Diao, Z. (2022) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2022.107584 · Cited by 372 · see citing works
Subdimensional expansion for multirobot path planning
Wagner, G., & Choset, H. (2014) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.001 · Cited by 365 · see citing works
Ligand docking to proteins with discrete side-chain flexibility
Leach, A. R. (1994) · Journal of Molecular Biology · doi:10.1016/s0022-2836(05)80038-5 · Cited by 363 · see citing works
Dynamic Programming Approaches for the Traveling Salesman Problem with Drone
Bouman, P., Agatz, N. A. H., & Schmidt, M. (2017) · Networks · doi:10.1002/net.21864 · Cited by 359 · see citing works
Fischler, M. A., Tenenbaum, J. M., & Wolf, H. C. (1981) · Computer Graphics and Image Processing · doi:10.1016/0146-664x(81)90056-3 · Cited by 355 · see citing works
Searching for solutions in games and artificial intelligence
Allis, L. V. (1994) · doi:10.26481/dis.19940923la · Cited by 350 · see citing works
Heuristic shortest path algorithms for transportation applications: State of the art
Fu, L., Sun, D., & Rilett, L. R. (2005) · Computers & Operations Research · doi:10.1016/j.cor.2005.03.027 · Cited by 342 · see citing works
An agent-based model for risk-based flood incident management
Dawson, R., Peppé, R., & Wang, M. (2011) · Natural Hazards · doi:10.1007/s11069-011-9745-4 · Cited by 336 · see citing works
Usov, I., & Mezzenga, R. (2015) · Macromolecules · doi:10.1021/ma502264c · Cited by 335 · see citing works
Finding shortest paths on real road networks: the case for A*
Zeng, W. H., & Church, R. L. (2008) · International Journal of Geographical Information Systems · doi:10.1080/13658810801949850 · Cited by 332 · see citing works
Airborne Communication Networks: A Survey
Cao, X., Yang, P., Alzenad, M., Xi, X., Wu, D., & Yanikomeroglu, H. (2018) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2018.2864423 · Cited by 331 · see citing works
The increasing cost tree search for optimal multi-agent pathfinding
Sharon, G., Stern, R., Goldenberg, M., & Felner, A. (2012) · Artificial Intelligence · doi:10.1016/j.artint.2012.11.006 · Cited by 330 · see citing works
Robust algorithm for real-time route planning
Szczerba, R. J., Galkowski, P., Glicktein, I. S., & Ternullo, N. J. (2000) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/7.869506 · Cited by 328 · see citing works
Survey of Robot 3D Path Planning Algorithms
Yang, L., Qi, J., Song, D., Xiao, J., Han, J., & Xia, Y. (2016) · Journal of Control Science and Engineering · doi:10.1155/2016/7426913 · Cited by 327 · see citing works
Singh, Y., Sharma, S. K., Sutton, R., Hatton, D. C., & Khan, A. (2018) · Ocean Engineering · doi:10.1016/j.oceaneng.2018.09.016 · Cited by 327 · see citing works
Path planning algorithms in the autonomous driving system: A comprehensive review
Reda, M., Onsy, A., Ghanbari, A., & Haikal, A. (2024) · Robotics Auton. Syst. · doi:10.1016/j.robot.2024.104630 · Cited by 312 · see citing works
Path Smoothing Techniques in Robot Navigation: State-of-the-Art, Current and Future Challenges
Ravankar, A. A., Ravankar, A. A., Kobayashi, Y., HOSHINO, Y., & Peng, C.-C. (2018) · Sensors · doi:10.3390/s18093170 · Cited by 320 · see citing works
TINA: a natural language system for spoken language applications
Seneff, S. (1992) · Cited by 320 · see citing works
Smoothed A* algorithm for practical unmanned surface vehicle path planning
Song, R., Liu, Y., & Bucknall, R. W. G. (2018) · Applied Ocean Research · doi:10.1016/j.apor.2018.12.001 · Cited by 317 · see citing works
- Authors
- Hart, P., Nilsson, N., & Raphael, B.
- Affiliations
- SRI International (US)
- Venue
- IEEE Transactions on Systems Science and Cybernetics
- Published
- 1968
- Volume
- 4
- Issue
- 2
- Pages
- 100-107
- ISSN
- 0536-1567 (ISSN-L)
- OpenAlex
- W1969483458
- Cited by
- 12,738
- References
- 7
- Citations by year
- 2026: 965 · 2025: 1216 · 2024: 1078 · 2023: 893 · 2022: 855 · 2021: 939 · 2020: 707 · 2019: 610 · 2018: 584 · 2017: 493 · 2016: 471 · 2015: 456 · 2014: 437 · 2013: 466 · 2012: 364
- FWCI
- 7.97
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Systems Science and Cybernetics (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Keywords
- least-cost path, shortest path, graph search, heuristic search, search strategies, optimality, heuristic information
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
