h: the manhattan distance for all boxes to be in a goal spot.To check whether these algorithms are effective in finding a solution for the sokoban puzzle of the last post, I wrote a very basic implementation of the algorithms using: In IDA*, we do normal search until a certain bound, and if we didn’t find a solution up to that point, increase the bound. For instance, for problems related to moving an object along a matrix, euclidean or manhattan distance can be very useful. Here, “closest” is given by g+h and its effectiveness highly depends on choosing a smart value for h. Mainly, in A*, instead of traversing all the possible states using BFS or DFS, we use a priority queue and always take the state “closest” to a solution. IDA* (Iterative Deepening A*) requires less memory (no need to save all visited/closed states) but it may visit the same state more than once. A* (A-star) is a popular search algorithm that considers the distance from the starting node (g), and a heuristic distance to the solution (h). Sometimes, for planning problems (those in which we have to find out which steps have to be taken and in which order), we want to add our own heuristics, and in this case we may want to implement the search algorithm ourselves. In the previous post we saw how we can use PDDL to find a solution of a sokoban puzzle.
