A Formal Basis for the Heuristic Determination of Minimum Cost Paths

By P. Hart, Nils J. Nilsson, B. Raphael. 1968

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “To compute ground-truth GED for training pair generation as well as similarity ranking evaluation, we have the following candidate GED computation algorithms: • A* (Hart et al., 1968): It is an exact GED solver, but due to the NP-hard nature of GED, it runs in exponential time complexity.”
A Survey of Autonomous Driving: Common Practices and Emerging Technologies (2019, methodology): “Graph search Dijkstra [250], A* [245], State lattice [251] Slow and jerky”
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, methodology): “The most prominent heuristic search algorithm is A* developed by Hart, Nilsson and Raphael [112].”
Go-Explore: a New Approach for Hard-Exploration Problems (2019, methodology): “to them is reminiscent of graph-search algorithms such as Dijkstra’s algorithm [97] and A* [98].”
Training a Natural Language Generator From Unaligned Data (2015, methodology): “The sentence planner is based on a variant of the A* algorithm (Hart et al., 1968; Och et al., 2001; Koehn et al., 2003).”
Theta*: Any-Angle Path Planning on Grids (2007, background): “Consistent h-values satisfy the triangle inequality, that is, the h-value of the goal vertex is zero and the h-value of any potential non-goal parent of any vertex is no greater than the distance from the potential non-goal parent of the vertex to the vertex plus the h-value of the vertex (Hart et a”
Path Planning for Autonomous Mobile Robots: A Review (2021, methodology): “[160] implemented a heuristic version, A*, to speed up computation.”
Path Planning for the Mobile Robot: A Review (2018, background): “Path planning is a kind of mapping from the perceptual space to the space of behavior, and the artiﬁcial neural network (ANN) can express the mapping relationship.”
Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation (2020, methodology): “In the context of pathfinding algorithms (Hart et al., 1968), this corresponds to searching with a non-admissible heuristic, that is, a heuristic that may underestimate the likelihood of completing partial translations.”
Best-First Beam Search (2020, methodology): “We prove that a speciﬁc best-ﬁrst prioritization scheme, as in classic A ˚ search (Hart et al., 1968), allows for the elimination of paths that will necessarily fall off the beam; for many scoring functions, including standard log-probability scoring, we can still guarantee the same k hypotheses as…”
Sampling-Based Robot Motion Planning: A Review (2014, methodology): “Search algorithms such as Dijkstra [26] and A* [27] find an optimal solution in a connectivity graph, whereas D* [28] and AD* [29] are tailored to dynamic graphs.”
Lifelong Navigation (2020, unknown): “Dijkstra’s algorithm [30], A* [31] or D* [32]) generates a path connecting start and goal, and while navigating, the robot needs to produce motion commands which follow this global path, observe its kinodynamic constraints, and avoid obstacles.”
Computer‐aided synthesis design: 40 years on (2012, methodology): “Selection of a precursor was performed using the A ∗ search algorithm, 118 which relies on a two-part cost estimation function 119 , 120 : the estimated cost to reach the current point in the plan, and an admissible estimate 121 of the cost to continue to the targeted starting material.”