Almost A* Search for Planning: SWISH Notebook

A SWISH notebook.

I do a lot with situations and actions so was wanting to investigate using A* search to get from an initial situation to a goal situation, thought it may be of interest to some of you as well.

I say it’s almost A* because A* has costs associated with each edge but in my use case these costs are unknown (and irrelevant), so this would be A* with a cost of 0 for each edge. Seen as the cost is 0, I didn’t include it in the implementation.

This is making use of library(heap) and many of the ord_* predicates for more efficient set operations, which I think is quite interesting! I also chose a “bad” example case that has to go against the heuristic to complete, it’d be interesting to compare against DFS with Extended List for efficiency.

–Edit–
If you’re interested in actual A*, the previous is adapted in this SWISH Notebook, which gives a cost of 1 to each action and finds the optimum solution but in about 1.5 seconds rather than 0.2 seconds.

6 Likes