What does a KeyError: <bound method > mean and how do I fix it?

Question

I am trying to create the degrees project from CS50 Intro to AI. In the project I have to find the shortest path between two actors through the movies they have starred in like the Six Degrees of Bacon Game. To do this I have been trying to change the solve function in maze.py from the lecture.

I am receiving the following error:

KeyError: <bound method QueueFrontier.remove of <util.QueueFrontier object at 0x00000276751F1CD0>>

The following is my function:

def shortest_path(source, target):
    start = Node(state=source, parent=None, action=None)
    frontier = QueueFrontier()
    frontier.add(start)

    explored = set()

    while True:
        if frontier.empty():
            return None
        node = frontier.remove
        explored.add(node)

        if node == target:
            movies = []
            actors = []
            while node.parent is not None:
                movies.append(node.movie)
                actors.append(node.actor)
                node = node.parent
            movies.reverse()
            actors.reverse()
            target = (movies, actors)
            return
        
        explored.add(node)

        for action, state in neighbors_for_person(node):
            if not frontier.contains_state(state) and state in explored:
                child = Node(state=state, parent=node, action=action)
                frontier.add(child)

The comments below have fixed my previous problem. Now whenever I test the code with two actors, nothing happens; the text cursor only blinks.

Below is my updated code:

def shortest_path(source, target):
    start = Node(state=source, parent=None, action=None)
    frontier = QueueFrontier()
    frontier.add(start)

    explored = set()

    while True:
        if frontier.empty():
            return None
        node = frontier.remove()
        explored.add(node)
 
        #All of the errors are in this block of code
        if node.state == target:
            print("this happens")
            actions = []
            cells = []
            while node.parent is not None:
                cells.append(node.state)
                actions.append(node.action)
                node = node.parent
            cells.reverse()
            actions.reverse()
            target = (actions, cells)
            return target
        

        for action, state in neighbors_for_person(node.state):
            if not frontier.contains_state(state) and  state not in explored:
                child = Node(state=state, parent=node, action=action)
                frontier.add(child)

Note: The print statement does not print anything in the terminal.

Answer 1

The comments above solve 2 problems, but there are still others. You can find these by going through your code and checking variable values on each while loop. Use the debugger or add print statements.

The 'Not connected' error is due to 3 errors in the if node == target block. They are:

1. Confusing the variable node (which is a Node object) with the person's id (saved as node.state and is an integer stored as a string variable). This occurs in multiple places:
   • When you check node == target you will always get False (because a Node will not be equal to the target person's id).
   • When you create the movies and actors lists, you use node.movie and node.actor (instead of .action and .state). You haven't gotten an error (yet) because you never enter this code block due to error 1 above.
2. You don't return anything after you create the movies and actors lists.
3. In addition, you create a tuple from the 2 lists, but it's not what you think. (You will get an error if you return target as-is.)

Your logic to check neighbors and add new nodes needs attention. Your if statement has and state in explored. You only want to add nodes if state is NOT in explored. Also, checking the explored set first is faster than checking the list (which is slow for large lists).

Finally, your implementation of the explored set is flawed, so it doesn't really improve performance. This set represents all actor ids that have been added to the frontier. We do this so we don't add the same actor twice. Your code doesn't add actor ids until you pop them from the frontier. Once you get this working correctly, the explored set will include every actor you have added to the frontier (even those removed them during the search). Then you can remove not frontier.contains_state(state) from the if statement, because it is redundant. Note: you have explored.add(node)in 2 places. The 2nd is a duplicate of the 1st.