Re:Introduction to the A* Algorithm
by deadbabe on Wednesday June 18, 2025 @11:58AM
(#44311005)
A* is simple enough, but how do you handle pathfinding when the environment isn’t known to the entity?
[ Parent
| on HN ]
Re:Introduction to the A* Algorithm
by ViscountPenguin on Wednesday June 18, 2025 @12:45PM
(#44311406)
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.
Re:Introduction to the A* Algorithm
by gradstudent on Wednesday June 18, 2025 @08:09PM
(#44314339)
ML methods are poor pathfinders. I'm unaware of any pathfinding problem where SOTA is not dominated by state-space search.
Re:Introduction to the A* Algorithm
by ViscountPenguin on Thursday June 19, 2025 @11:37PM
(#44324508)
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.
Re:Introduction to the A* Algorithm
by SnowflakeOnIce on Wednesday June 18, 2025 @12:49PM
(#44311455)
Re:Introduction to the A* Algorithm
by gradstudent on Wednesday June 18, 2025 @08:08PM
(#44314331)
SLAM is for mapping. For planning (and execution) in unknown environments, probably something like D* Lite.