Error with optimality in Iterative Deepening Depth First Search algorithm

Question

I have implemented a version of Rush Hour (the puzzle board game) in Python as a demonstration of some AI algorithms. The game isn't important, because the AI is relatively independent of its details: I've attempted to implement a version of iterative deepening depth-first search in Python as follows (note that this code is almost directly copied from Russell and Norvig's AI text, 3rd edition, for those of you who know it):

def depth_limited_search(game, limit):

    node = GameNode(game)

    frontier = []

    #frontier = Queue.Queue()

    frontier.append(node)

    #frontier.put(node)

    frontier_hash_set = set()

    frontier_hash_set.add(str(node.state))

    explored = set()

    cutoff = False

    while True:

        if len(frontier) == 0:

        #if frontier.empty():

           break

        node = frontier.pop()

        #node = frontier.get()

        frontier_hash_set.remove(str(node.state))

        explored.add(str(node.state))

        if node.cost > limit:

            cutoff = True

        else:

            for action in node.state.get_actions():

                child = node.result(action)

                if str(child.state) not in frontier_hash_set and str(child.state) not in explored:

                    if child.goal_test():

                        show_solution(child)

                        return child.cost

                    frontier.append(child)

                    #frontier.put(child)

                    frontier_hash_set.add(str(child.state))

    if cutoff:

        return 'Cutoff'

    else:

        return None

def iterative_deepening_search(game):

    depth = 0

    while True:

        result = depth_limited_search(game, depth)

        if result != 'Cutoff':

            return result

        depth += 1

The search algorithm, as implemented, does return an answer in a reasonable amount of time. The problem is that the answer is non-optimal. My test board of choice has an optimal answer in 8 moves, however, this algorithm returns one using 10 moves. If I replace the lines above commented outlines with the commented lines, effectively turning the iterative deepening depth-first search into an iterative deepening breadth-first search, the algorithm DOES return optimal answers!

I've been staring at this for a long time now trying to figure out how a simple change in traversal order could result in nonoptimality, and I'm unable to figure it out. Any help pointing out my stupid error would be greatly appreciated.

Answer 1

The problem arises here:

if str(child.state) not in frontier_hash_set and str(child.state) not in explored:

In this DFS iteration, child.state may have been inserted into the frontier or set of visited states, but with a greater cost.

Clearly, you will not reach the aim with a limit of less than 3. But when the limit is 3, your DFS may first visit A, B, and C. Then when it backtracks to S, visits D, and tries to visit C, it will not push C onto the stack because you visited it earlier.

To correct this, you need to "un-visit" states as you backtrack. Implementation-wise it is probably most straightforward to write your algorithm recursively and pass copies of your explored-state set in a functional style.

If you wish to know more about Artificial Intelligence then visit this Artificial Intelligence Course.