`A*` removing a node from frontier

Question

This is a A* algorithm I wrote, in the evaluation I was told "Your implementation performs the goal test when a successor is added to the frontier, not when it's removed: this compromises optimality". What does it mean "not when it's removed"?

Here's my code:

def solve(problem, heuristic) :
    """ 
    A* search algorithm finding the shortest path.

    Returns:
        A list of actions.
    """
    s0 = problem.get_initial_state()
    queue = PriorityQueue()
    queue.push((0,s0,[]),0)  # second 0 is priority
    cost_so_far = dict()
    cost_so_far[s0] = 0

    while not queue.is_empty():
        current_cost, s, actions = queue.pop()
        for successor, action, cost in problem.get_successors(s):
            new_cost = current_cost + cost
            if problem.goal_test(successor):
                return actions + [action]
            else:
                h = heuristic(successor, problem)
                if successor not in cost_so_far or cost_so_far[successor] > new_cost + h:
                    cost_so_far[successor] = new_cost + h
                    queue.push((new_cost, successor, actions + [action]), new_cost + h)

Modified version (Updates)

def solve(problem, heuristic) :
    """ 
    A* search algorithm finding the shortest path.

    Returns:
        A list of actions.
    """
    s0 = problem.get_initial_state()
    queue = PriorityQueue()
    queue.push((s0,[]),0)  # 0 is the priority
    cost_so_far = {s0:0}

    while not queue.is_empty():
        s, actions = queue.pop()

        if problem.goal_test(s):
                return actions

        for successor, action, cost in problem.get_successors(s):
            successor_cost = current_cost + cost
            new_cost = successor_cost + heuristic(successor, problem)

            if successor not in cost_so_far or cost_so_far[successor] > new_cost:
                    cost_so_far[successor] = new_cost
                    queue.push((successor, actions + [action]), new_cost)

Answer 1

Say your graph looks like this:

    9
S ----- G
 \     /
 1\   /1
   \ /
    W

You need to get from the start node S to the goal node G along the cheapest path possible. The S-G edge has a cost of 9, while the edges connecting to waypoint W each have cost 2.

Your algorithm would look through the neighbors of S to add nodes to the frontier, find G, and return the expensive, direct S-G path immediately, without ever finding the path through waypoint W.

Instead, you need to perform the goal test for a node when you pop the node from the priority queue. At this point, it's guaranteed that you've found the cheapest path to the node, not just some path to the node.