I played with the Pacman programming assignment given to the Standford class (NOT to our online class) and found a result for the trickySearch Q7 problem with only 379 search nodes expanded. In the statement of the question, it is said that it is hard to get fewer than 7000 nodes expanded. Thus, the result I get seems almost too good to be true. As far as I can tell, by putting an explicit check to verify that the heuristic cost never decreases by more than 1 at each step in the expansion, my heuristic is consistent. I am also pretty sure that it is admissible. Is there anything else I can do to verify that I use a valid heuristic? I should note that the heuristic I use is particularly suited to maze layouts like the trickySearch one. When I use it for the seemingly simpler tinySearch, I get 568 nodes expanded. asked 16 Oct '11, 02:12 aroberge Have you tried running it on mediumSearch?
(16 Oct '11, 06:03)
Maxim
Yes, and I had to stop it since, after 20 minutes of run time, it had not come up with a solution and was requiring over 2GB of memory.
(16 Oct '11, 08:31)
aroberge
can you link to the assignment pages and any other references pls ;)
(16 Oct '11, 08:34)
Merlin
http://robots.stanford.edu/cs221/progAssignments/PA1/search.html
(16 Oct '11, 08:45)
aroberge
Those assignments were a blast. I got 6,110 nodes expanded for trickySearch and 414 nodes expanded on tinySearch (using the AStarFoodSearchAgent).
(27 Nov '11, 03:25)
Tom Chappell

I'd say your heuristic function is overfit to that one particular maze ;) answered 31 Oct '11, 10:26 rhasarub :D Actually, that might be partly true... It would work really well for similar mazes, those for whom the manhattan distance is a huge undermeasurement due to the presence of long and narrow deadend corridors...
(31 Oct '11, 10:54)
aroberge

Here is a graph of the costs along the optimal path in trickySearch, with the estimated remaining cost (heuristic) stacked above the computed cost (which is of course linear). The heuristic is the aforementioned minimum spanning tree (MST) length + cost to the closest food. Things to note are:
Of course the graph doesn't prove anything. To prove consistency (or at least, to convince myself), this is my reasoning:
answered 17 Jan '12, 19:13 ibatugow 
@gbayliss Stanford course downloads are on the course schedule here but already the lecture 1 link is busted.
@aroberge Can you offer any tips for installing cs221 code and Python  was it easy to get working? answered 16 Oct '11, 09:25 martinhumby Python is extremely easy to install. If you have a Mac or a Linux box, it should be there already. If not, head to python.org and follow the links. As for "installing" the code, you simply have to download it, unzip it somewhere. Simply typing "python a_program.py" will run it  no installation step needed.
(16 Oct '11, 09:37)
aroberge
I should have clarified what I meant about installing the code: I was referring to the code samples for the assignment  not Python itself.
(18 Oct '11, 11:10)
aroberge
Thanks for your help, sorry not replying earlier. Loaded pacman under Ubuntu on VirtualBox. Great stuff but going to find getting to grips with the Python code hard  untyped variables makes understanding harder I think.
(18 Oct '11, 19:12)
martinhumby

I have a similar issue with Q4, my implementation of astar seems to find the correct solution much faster than stated in the problem. With the null heuristic, my astar finds the best solution in 435 nodes when they say 549. answered 16 Oct '11, 20:11 Benoit Ambry For me, it's 538 nodes expanded  much closer to theirs. I can see a difference in a few nodes, given a choice of "left" vs "right" branch for choosing successors, but I am puzzled as to how yours is so much lower. In the case I wrote about, it's all due to a "clever" choice of heuristics  where I get at least an order of magnitude difference better than what could be expected...
(16 Oct '11, 20:25)
aroberge
1
No, I have a bug, that is clear. I think it is missing some of the branches and it finds the proper solution by luck. The null heuristic always returns 0.
I found actually, I wrote f(n) = h(n) instead of f(n) = g(n) + h(n). now I have 538!
(16 Oct '11, 20:35)
Benoit Ambry
If you are like me, you may find it useful to include a check like:
. if h_cost  new_h_cost > successor[2]:
. print "consistency problem", h_cost, new_h_cost, successor[0]
in your Astar code. This helped me identify some errors in my heuristic functions.
(16 Oct '11, 20:41)
aroberge
Yeah I have that already, I'm on Q6 and a bad heuristic can really take the astar algo down.
(16 Oct '11, 20:44)
Benoit Ambry
Huh, that's funny that you guys are both getting 538 nodes expanded on this one. I got 549 nodes expanded with the manhattanHeuristic, the same as they predicted.
(27 Nov '11, 03:36)
Tom Chappell

I have had a few seemingly ok heuristics for Q7  one that finds the optimal solution with 10849 expanded nodes, one that finds an almost optimal solution in 7389 expanded nodes. (The heuristics are taking topology of the maze into account) However, on mediumSearch, the only solutions I could find before my computer melted (rather, ran out of memory) were clearly suboptimal solutions (pacmans oscillating left and right in the maze, eating a few dots on the rigth, turning around, nibbling on the left and back again) that were found in less than 20'000 expanded notes. The heuristics were not admissable for those. Question: Has anyone found a heuristic that solves mediumSearch optimally and finishes in finite time / memory? I have an idea for a solution, but that would require a totally different solution state. I have already spent way too much time on this heuristic and would like to know if there's hope to actually solve it. answered 31 Oct '11, 05:19 jcfischer So I have a heuristic that works in all mazes but mediumSearch and bigSearch. (trickySearch with optimal solution in 9615 expanded nodes). Would be interesting to hear from others how they are faring. I suspect that my heuristic would solve mediumSearch, but I haven't been able to run it to completion.
(31 Oct '11, 06:00)
jcfischer
I have run mediumSearch with my heuristic and it didn't complete before it ate up 6 GB of memory...
(31 Oct '11, 11:27)
jcfischer
found a really good article about heuristics for A* search and how it influences the speed and accuracy of the search: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
(01 Nov '11, 12:47)
jcfischer

Mine does Q7 with 5893 nodes expanded... What are other peoples' results? (Mine completes in 1.2 seconds) I have Q4 as 547 nodes expanded with a "total cost of 210". @aroberge I'm interested in your check for consistency... What is h_cost and what is new_h_cost? answered 27 Nov '11, 01:34 bnsh Actually... I think I see. So, h_cost is the heuristic of the current position, and new_h_cost must be the heuristic for the successor... I am curious if my heuristic for Q7 is inconsistent or not, given how easy it was to get 5893 as an answer. More later.
(27 Nov '11, 01:41)
bnsh
Yep! Sure enough! Consistency problems! Damnit! hehe...
(27 Nov '11, 01:43)
bnsh
For Q7, I got:
6,110 nodes expanded, total cost 60 (trickySearch)
414 nodes expanded, total cost 27 (tinySearch)
For Q4, I got:
549 nodes expanded, total cost 210
(I've got the heuristic consistency check in my aStarSearch)
(27 Nov '11, 04:14)
Tom Chappell
Q7: (tricky search) 60 cost, 215 expanded in 0.1 seconds. Consistency is guarantied by heuristic construction. However, I've inserted code to check for consistency on each step. No warnings so far.
tinySearch  27 cost, 52 expanded. smallSearch  34 cost, 57 expanded.
Heuristic is O(n^3), where n is a number of food dots.
(27 Nov '11, 04:33)
red75prim
In Q7 my best score in trickySearch is:
Path found with total cost of 60 in 1.6 seconds
Search nodes expanded: 1130
@red75prim
I'm interested in what heuristic you used. Could we contact by email? (It should appear in my profile)
(04 Jan '12, 17:47)
maacruz
@maacruz, I can't see your email. However, I can give a hint: consider the length of minimum spanning tree for remaining food dots.
BTW, I implemented slightly different priority queue to get 215 expanded nodes. If program uses util.PriorityQueue, then it expands 255 nodes.
(05 Jan '12, 03:52)
red75prim
@red75prim: Hey, I did the same thing ! Length of minimumum spanning tree (using maze distances) + distance to closest food. 247 nodes expanded with the stock util.PriorityQueue in 0.1 s. I used Dijkstra and a cache to speed up the calculations.
(05 Jan '12, 06:19)
ibatugow
@ibatugow. Cache, yes, but I was too lazy to implement Dijkstra's algo...
[Staring at source code]
Well, yes, it's Dijkstra (BFS + tuned getSuccessors).
(05 Jan '12, 07:29)
red75prim
Thanks! But I think it is an inconsistent heuristic (I can think of one such a tree where you remove a node and the resulting total length then is greater), or I'm not making the right approach (my implementation is inconsistent). My email is maacruz in gmail.
(16 Jan '12, 18:38)
maacruz
Looking back...
With my first approach for Q7, TrickySearch I got:
5380 nodes expanded, total path cost 60, in 1.8 seconds
A solution with 215 nodes expanded is pretty impressive. I am also curious about the approach taken here.
(16 Jan '12, 21:36)
egoots
Finally got it. Needed a small trick (which I had used in my previous heuristic) with packman to solve the inconsistency.
255 nodes expanded in trickySearch in 1.4 seconds (completely unoptimized although I cache things)
(17 Jan '12, 18:38)
maacruz
maacruz: could you email me? myusername at gmail dot com
(17 Jan '12, 18:42)
aroberge
Anyone have pointers on how to actually implement the MST based on a maze?
(07 Feb '13, 19:45)
AstarC

Thanks! But I think it is an inconsistent heuristic (I can think of one such a tree where you remove a node and the resulting total length then is greater), or I'm not making the right approach (my implementation is inconsistent). My email is maacruz in gmail. answered 16 Jan '12, 18:38 maacruz Yes, the heuristic value can increase, but what the consistency condition says is that the (cost up to now + heuristic value) cannot decrease. In other words, the estimated remaining cost cannot decrease faster than the computed cost increase. It doesn't preclude the heuristic function to increase, as long as it stays admissible (i.e., not larger than the remaining optimal cost).
(17 Jan '12, 05:08)
ibatugow
