Best heuristic for A* search

Question

I'm implementing the Ricochet Robots game using the A* search. The goal of the game is to put a specific robot in a specific location of the board. The board can have several walls and there are 3 more robots that can be moved.

I'm using the manhattan distance as the heuristic, but the search is not working in all scenarios I try, sometimes I get an infinite loop. I believe it is due to the fact that there are obstacles in the board.

What would be the best heuristic for this case?

This is the code for the a* search function. It receives the heuristic function as input. The node is an object that has the current state and the current board.

def astar_search(problem, h, display=False):
    h = memoize(h or problem.h, 'h')
    return best_first_graph_search(problem, lambda n: n.path_cost + h(n), display)

def best_first_graph_search(problem, f, display=False):
    f = memoize(f, 'f')
    node = Node(problem.initial)
    frontier = PriorityQueue('min', f)
    frontier.append(node)
    explored = set()
    while frontier:
        node = frontier.pop()
        if problem.goal_test(node.state):
            if display:
                print(len(explored), "paths have been expanded and", len(frontier), "paths remain in the frontier")
            return node
        explored.add(node.state)
        for child in node.expand(problem):
            if child.state not in explored and child not in frontier:
                frontier.append(child)
            elif child in frontier:
                if f(child) < frontier[child]:
                    del frontier[child]
                    frontier.append(child)
    return None

Great! Can you add a bit more code to show how you evoke the algorithm? The goal is to create a reproducible example so that others can help pinpoint where things are going wrong. That means helper functions like memoize should all be declared in the minimal example. (This code looks clean by the way!) — duhaime
Manhattan distance is not an admissible heuristic for this problem. An admissible heuristic is one that never overestimates the number of moves needed to reach the goal. An easy way to remember that rule is that h(x)=0 is always admissible. For example: the goal is red, and the red robot is on the correct row, 10 spaces from the goal. There are no walls or robots blocking the path. The manhattan distance is 10, but the number of moves needed to reach the goal is 1. The manhattan distance overestimates the number of moves. — user3386109

BlueRaja - Danny Pflughoeft BlueRaja - Danny Pflughoeft · Accepted Answer · 2020-10-29T02:35:45

The heuristic used by A* must never overestimate the cost. Since it's possible to move an arbitrary distance using one move in Ricochet Robots, Manhatten Distance will not work as a heuristic.

The only valid heuristic I can think of is "2 if not on the same row+column, otherwise 1 if not the end goal", since diagonal moves are not possible.

Best heuristic for A* search

1 Answers