3 ms·

Again, a great article, but I feel like some of the general thinking behind heuristics is getting lost. Heuristics can be significantly more interesting than di

by dj-wonk 12y ago

Again, a great article, but I feel like some of the general thinking behind heuristics is getting lost. Heuristics can be significantly more interesting than distance between two points. This isn't a huge criticism. In this context -- pathfinding on a grid -- complicated heuristics may not be needed. When I first read about A* a long time ago I remember, for example, reading about how static summaries of chess board positions may be useful heuristics. Developing pieces towards the center of the board is often better, for example. To me, seeing this was an "ah ha" moment for heuristics: use them if they are cheap and (sometimes) informative, relative to the search cost.

gamegoblin 12y ago
I once wrote an A* algorithm to solve a 15-puzzle (the thing with 15 sliding tiles and 1 empty space, often depicting a picture, or just the numbers). An easy heuristic that vastly improves the search: the sum of the manhattan distances of the pieces' current locations to their final positions. So, as you said, rather than thinking about distance only in a Euclidean space, A* heuristics are much more general -- any metric that measures "done-ness".
- deleted 12y ago
  [deleted]
- wlievens 12y ago
  For an AI course we had to write a solver for a puzzle using a heuristic. We had a reference solution step count to aim towards. After many hours of tweaking I still could not solve it. I had writ and rewritten quite complicated heuristics but to no avail, until at one point I stumbled on a nearly optimal solution. Upon reading my code again I noticed that a stray parenthes and a forgivinv lisp parser had caused most of my heuristic's code to be ignored. The simplest thing Just Worked :-)
psycovic23 12y ago
This is a very interesting area of research. The state of the art in motion planning for robotics actually uses multiple heuristics at once with A*. http://www.roboticsproceedings.org/rss10/p56.pdf http://www.roboticsproceedings.org/rss10/p56.pdf

by dj-wonk 12y ago

gamegoblin 12y ago

I once wrote an A* algorithm to solve a 15-puzzle (the thing with 15 sliding tiles and 1 empty space, often depicting a picture, or just the numbers). An easy heuristic that vastly improves the search: the sum of the manhattan distances of the pieces' current locations to their final positions. So, as you said, rather than thinking about distance only in a Euclidean space, A* heuristics are much more general -- any metric that measures "done-ness".

deleted 12y ago
[deleted]
wlievens 12y ago
For an AI course we had to write a solver for a puzzle using a heuristic. We had a reference solution step count to aim towards. After many hours of tweaking I still could not solve it. I had writ and rewritten quite complicated heuristics but to no avail, until at one point I stumbled on a nearly optimal solution. Upon reading my code again I noticed that a stray parenthes and a forgivinv lisp parser had caused most of my heuristic's code to be ignored. The simplest thing Just Worked :-)

psycovic23 12y ago

This is a very interesting area of research. The state of the art in motion planning for robotics actually uses multiple heuristics at once with A*. http://www.roboticsproceedings.org/rss10/p56.pdf http://www.roboticsproceedings.org/rss10/p56.pdf