Recap

In my previous project post, I had implemented a simple agent to navigate through a grid world to find a goal state.

Let’s make it harder!

In the first project, the agent was given an oracle that could tell how close a state is to the goal. This makes the problem somewhat easier.

We can make the problem a little harder by removing this extra information. This type of problem is called an uninformed search. There are many different types of algorithms that specialise in solving these. You can read about them in more depth here.

This would be a great opportunity to explore, implement and showcase a simple breadth-first search.

Implementation

Rather than rewrite a whole new model, I kept most of the environment and problem code from my best first search project and only modified the search algorithm into breadth first search.

The BFS algorithm was implemented like this:

def breadth_first_search(problem):
    node = problem.initial
    if problem.is_goal(node):
        return node
    frontier = [node]
    reached = {node.state.__str__()}
    while frontier.__len__() != 0:
        time.sleep(DISPLAY_INTERVAL)
        cls()
        node = frontier.pop(0)
        problem.grid[node.state.x][node.state.y] = "X"
        problem.print()
        print(node)
        if problem.is_goal(node):
            return child
        for child in expand(problem, node):
            s = child.state
            if s.__str__() not in reached:
                reached.add(s.__str__())
                frontier.append(child)
    return None

Just like the previous project, the initial state of the agent was randomly generated and accessed via problem.initial I do an initial check to see if our starting position is the goal. If it is, I don’t need to load expensive resources like arrays or sets into memory.

Just like the best-first search, we need to create a list to store the frontier nodes to check next. This list will be accessed as a first-in first-out queue. The nodes that we expand out will be placed at the end to ensure that the frontier nodes are ordered by distance. Because of this data structure, we don’t need to do expensive reordering of the frontier.

The set of reached nodes can be modelled as a set instead of a dictionary. This is because I don’t need to access the node from here. The frontier can supply that for us.

When I take the next node from the frontier queue, I mark the grid for visibility and print the grid to the screen. Then, the node is expanded and all the expanded nodes that haven’t been reached are added to the frontier.

Showcase

Here it is in action! I chose to showcase how the algorithm searches for a far goal state. The algorithm is thorough (complete) because every cell that are N steps away is checked before checking cells that are N + 1 steps away.