Best First Search in a Grid World

• Inspiration: Norvig Chapter 3
• View the full code here: Github

Introduction

“Problem solving agents” are AIs that plan ahead a sequence of actions that lead to a goal state. “Searching” is how the agent finds the best path for it to take.

The easiest of these problems to start with are searching for a solution where the agent has information about environment. This could mean that we know things like the location or direction of the goal, etc.

Following these 4 steps would help the agent find a good solution to this kind of searching:

1. Goal Formulation
2. Problem Formulation
3. Search
4. Execution

Goal Formulation

Goals help the agent evaluate actions by focusing on an objective. This prunes away unnecessary actions from our search (faster results)

Given the grid world above, the “goal” of the agent is this:

• Agent starts at a random coordinate on the grid (S)
• The goal state is where the agent is at the goal cell (0)

I modeled the grid world by keeping a 2D array. Here, I created a game class which is initialized with random numbers in its constructor.

class Game:  
    def __init__(self):  
        coord_range = range(0, GAME_SIZE, 1)  
        self.goal = State(random.choice(coord_range), random.choice(coord_range))  
        cost_values = [" "]  
        self.grid = []  
        for i in range(0, GAME_SIZE, 1):  
            self.grid.append(random.choices(cost_values, k=GAME_SIZE))  
        self.grid[self.goal.x][self.goal.y] = "0"  
        self.initial = Node(random.choice(coord_range), random.choice(coord_range))  
        self.grid[self.initial.state.x][self.initial.state.y] = "S"

self.goal represents the coordinate where the goal is. It is a random coordinate within the grid. self.grid is populated with cost values. Here it is just for display but you can alter it to model more difficult terrain. self.initial is a random coordinate for where the agent starts.

The State and Node class that you see above will be described in the next sections.

Search Problem

Search problems are defined to have these properties:

• Possible states (State space)
• Initial state
• Actions
  • that the agent can do
• Transition model
  • what the result of each action is
• Action cost
  • of applying an action to reach a desired state

I’ve created a Node object that holds all the information of each state, the actions that can be performed as well as a nominal zero cost.

class Node:  
    def __init__(self, x, y):  
        self.state = State(x, y)          
        self.actions = []  
        if x != 0:  
            self.actions.append(Movement.LEFT)  
        if x != GAME_SIZE - 1:  
            self.actions.append(Movement.RIGHT)  
        if y != 0:  
            self.actions.append(Movement.UP)  
        if y != GAME_SIZE - 1:  
            self.actions.append(Movement.DOWN)  
        self.cost = 0

States: For this exercise, our states will be the grid world where the agent is in a different cell. So a 3x3 grid will have 9 different states corresponding to the agent in each square. This means for a grid of M rows and N columns, there will be M x N different states.

The states are a small data class that holds the coordinates. Yes. It can be simplified as a tuple but I find that creating a class for it would be more extensible for future. Classes also have a default __str__() function which can be overridden for better/easier printing.

class State:  
    def __init__(self, x, y):  
        self.x = x  
        self.y = y

Initial State: We will randomly assign a position on the grid for the agent to start This was assigned with the creation of the Game object.

Actions: The agent is free to move vertically and horizontally. However, it cannot pass the boundaries of the grid.

I’ve modelled these actions as an Enums so that the code is more readable than simply using integers.

class Movement(Enum):  
    LEFT = 0  
    UP = 1  
    RIGHT = 2  
    DOWN = 3

On the creation of each Node object, the actions are calculated based off their x and y coordinate. Actions that move the agent past the boundary are left out of the list. I use this action list to transition the agent to the next state.

self.actions = []  
if x != 0:  
	self.actions.append(Movement.LEFT)  
if x != GAME_SIZE - 1:  
	self.actions.append(Movement.RIGHT)  
if y != 0:  
	self.actions.append(Movement.UP)  
if y != GAME_SIZE - 1:  
	self.actions.append(Movement.DOWN)  

Transition Model: This might be overkill to spell out since movement and position are so intuitive. The result of the agent taking each movement action will shift it’s coordinate accordingly.

Action Cost: Moving in any direction have the same cost.

Doing the Search

This is where we pick the search algorithm. The first algorithm that is presented in Norvig is the Best First Search. I’ve implemented it like so:

def best_first_search(problem, eval_function):  
    node = problem.initial  
    frontier = [node]  
    reached = {node.state: node}  
    while frontier.__len__() != 0:  
        frontier.sort(key=eval_function, reverse=True)  
  
        node = frontier.pop()  
        time.sleep(2)  
        cls()  
        problem.grid[node.state.x][node.state.y] = 'X'  
        problem.print()  
        print("")  
        print(node)  
  
        if problem.is_goal(node):  
            return node  
  
        results = expand(problem, node)  
        for child in results:  
            key = child.state.__str__()  
            if key not in reached.keys():  
                reached[key] = child  
                frontier.append(child)  
  
    return None

Start with an initial node. The frontier represents all the nodes we’re yet to expand. The reached keeps track of all the positions on the grid we’ve checked so we don’t need to double up our efforts.

We sort the frontier by some kind of evaluation function. For this, I used the Manhattan distance to the goal. If you’ve never heard of that, it just means how many steps you need to take horizontally and vertically to get to the goal.

def eval_function(node):  
    x_diff = game.goal.x - node.state.x  
    y_diff = game.goal.y - node.state.y  
    return abs(x_diff) + abs(y_diff)

We sort the frontier reverse because we want to pop() the smallest distance first. What this code does in layman’s terms, is “out of all the options we have, pick the one with the smallest distance to the goal.”

Once we’ve picked the best next step, we chack whether it is the goal. If it is, then return it straight away. We don’t need to check any more states.

if problem.is_goal(node):  
    return node

Otherwise, expand out all the new options:

def expand(problem, node):  
    s_dash = []  
    for action in node.actions:  
        match action:  
            case Movement.LEFT:  
                n = Node(node.state.x - 1, node.state.y)  
                if node.state.x - 1 >= 0:  
                    s_dash.append(n)  
            case Movement.RIGHT:  
                n = Node(node.state.x + 1, node.state.y)  
                if node.state.x + 1 < GAME_SIZE:  
                    s_dash.append(n)  
            case Movement.UP:  
                n = Node(node.state.x, node.state.y - 1)  
                if node.state.y - 1 >= 0:  
                    s_dash.append(n)  
            case Movement.DOWN:  
                n = Node(node.state.x, node.state.y + 1)  
                if node.state.y + 1 < GAME_SIZE:  
                    s_dash.append(n)  
    return s_dash

To expand out, we go through each of the actions and create a new Node for each of the states. Here there’s a whole bunch of checks for the boundary cases. It is a duplicated check but good to keep in there as a safeguard just in case the action list does not respect the boundaries.

Now that we have expanded out the new options, we add it to the frontier list. That list will be sorted again in the next iteration and we can pick the best next node.

In Action

Here is the agent working out the steps to get to the goal.

We can see the AI expanding the nodes marked with X’s.

The Next Steps

• To see how I modified this program to implement a Breadth First Search, click here
• Or to see how to navigate through a randomly generated tree using Depth First Search, click here

View the full code here: Github