Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Introduction to the A* Algorithm (2014)

redblobgames.com

Post reply on HN
Print view View original

101–110 of 111 posts

Re: Introduction to the A* Algorithm (2014)

#101

Post by dataflow »

apnorton wrote: post #33

The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue: Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue) Di…

> This also helps me remember whether the estimate must over- or under-estimate: Since Dijkstra is making the estimate "0", clearly the "admissible heuristic" criteria must be an under-estimation.

You're thinking too hard. :-) Just think of a map the same way a 10-year-old would.

Straight-line (Euclidean) distance is the most obvious heuristic on a map for estimating distance, and it's admissible.

Straight lines minimize distances i.e. they never overestimate. Which is enough to remind you that you want an underestimate.

> the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue

A much less obvious but much more fascinating (IMO) way to look at A* is that A* is actually Dijkstra but with a modified graph, where you adjust the heuristic delta between each edge's vertices to the edge's weight.

To remember the sign of the adjustment with this method, just imagine the next vertex getting super close to the destination, and then work out whether the weight needs to increase or decrease significantly in that case. (It needs to decrease, given you're getting closer to the destination.)

Re: Introduction to the A* Algorithm (2014)

#102

Post by tsumnia »

upghost wrote: post #14

Interesting that this used to be called "AI". I'm still trying to figure out what to call the umbrella field of Artificial Intelligence now that "AI" has come to mean the genAI subset of DL which is a subset of ML which is a subset of what used to be called "AI".

The way I explain it to my students is through a venn diagram of "Traditional AI", "Machine Learning", and "Data Science" (though I suppose Gen AI is starting to form another circle). A* falls into the "Traditional AI" space, which is a mixed of state searching, logic representation, and statistics/probability (now called data science). What general public considers "AI" is where all the circles meet, and it means everything from Robots to if-else statements.

Re: Introduction to the A* Algorithm (2014)

#104

Post by throwawayoldie »

bonoboTP wrote: post #46
dspillett wrote: post #25

Earlier quoted context omitted.

> Interesting that this used to be called "AI". What has been called AI in gaming in the past is rich and varied, and goes all the way down to a computer control opponent “seeing” a player and opening fire, moving towards, or moving away. Any code controlling NPC was referred to as “the AI of the game” even if all the code was doing was applying a few simple rote rules rather than following an exactly pre-specified s…

Not just computer game AI. Literally university courses called "Artificial Intelligence" would teach A*, formal logic, planning, knowledge representation, etc. See for example the famous Russell-Norvig textbook. Since deep learning became dominant around 2012-2014, that conception of AI is now (somewhat deprecatingly) called GOFAI, or "good old-fashioned AI".

I'm old enough that my AI class in undergrad was taught from the first edition of Russell and Norvig. Neural networks (i.e. the basis of 95% of what today is called "AI") got one chapter, and it wasn't a long or detailed chapter either.

Re: Introduction to the A* Algorithm (2014)

#105

Post by throwawayoldie »

kriro wrote: post #80

Best introduction to A* in my opinion is travelling in Romania :) AI a Modern Approach.

"This problem assumes that the reader is not familiar with Romanian geography. We apologize to those who are unable to take advantage of this pedagogical device."

(Or words to that effect, it's been 20+ years since I read it.)

Re: Introduction to the A* Algorithm (2014)

#107

Post by JohnKemeny »

thaumasiotes wrote: post #89
JohnKemeny wrote: post #81

Earlier quoted context omitted.

OP's point is that · BFS is priority queue with key h(n) + g(n) , where h(n) = 0 , g(n) = #edges · Dijkstra's is priority queue with key h(n) + g(n) , where h(n) = 0 , g(n) = sum over edges · A* is priority queue with key h(n) + g(n) , where h(n) = heuristic(n) , g(n) = sum over edges It's cute.

> OP's point is that > BFS is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = #edges He doesn't say that, and it isn't true.

In (theoretical) computer science, we write "#xs" to denote "number of xs".

My sentence was supposed to be read as "g(n) = number of edges", and implicitly, of course (since we're talking about BFS), that means number of edges seen up until now, from ns perspective. And yes, n usually denotes the size of the graph, however, in the context of A*, we usually write n to denote the current node (as per AI:MA).

I take full responsibility. (Disclaimer: I'm a CS professor teaching BFS and Dijkstra's algorithm every semester and A* every 2nd year.)

Re: Introduction to the A* Algorithm (2014)

#108

Post by upghost »

throwawayoldie wrote: post #104
bonoboTP wrote: post #46

Earlier quoted context omitted.

Not just computer game AI. Literally university courses called "Artificial Intelligence" would teach A*, formal logic, planning, knowledge representation, etc. See for example the famous Russell-Norvig textbook. Since deep learning became dominant around 2012-2014, that conception of AI is now (somewhat deprecatingly) called GOFAI, or "good old-fashioned AI".

I'm old enough that my AI class in undergrad was taught from the first edition of Russell and Norvig. Neural networks (i.e. the basis of 95% of what today is called "AI") got one chapter, and it wasn't a long or detailed chapter either.

I guess the 5th edition will need to be called "Artificial Intelligence: An Outdated Approach".

I absolutely love that book. Maybe that's why I get a little cringey at the "AI" monicker for LLMs.

Re: Introduction to the A* Algorithm (2014)

#109

Post by noqc »

apnorton wrote: post #33

The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue: Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue) Di…

I think probably the easiest way to remember under/over is just to remember that euclidean distance is a very common admissible heuristic.

Re: Introduction to the A* Algorithm (2014)

#110

Post by ViscountPenguin »

gradstudent wrote: post #96
ViscountPenguin wrote: post #60

Earlier quoted context omitted.

Iirc, the best approaches for this nowadays are machine learning based. Otherwise, you probably want to do an exploration step first, and bake in the environment.

ML methods are poor pathfinders. I'm unaware of any pathfinding problem where SOTA is not dominated by state-space search.

I can't find any benchmarks, but here's an example of the sort of approach I was talking about:

https://www.researchgate.net/publication/355761412_Path_plan...

GOFAI techniques are: A) Usually unable to incorporate posteri knowledge of the environments they're working on. And B) Often entirely infeasible to adapt to take exploration costs into account.

I've heard of some GOFAI techniques for optimal unbiased pathfinding in unknown environments using optimal transport theory and the like. But unbiased methods are obviously going to lose out in real environments.

Post reply on HN