Best heuristic for A* search

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