Uninformed search in Artificial Intelligence

This article was originally posted on Medium and Asheux

Search problems are quite popular these days in Artificial Intelligence and many algorithms have been proposed for solving problems of this kind. In this article, we will consider a popular search problem of finding your way through a maze and two simple algorithms used to solve this problem. The algorithms we will consider are the Depth-First search(DFS) and the Breadth-First search(BFS). Let's look at each of them.

Depth-First Search

Depth-First search is an algorithm for traversing tree data structures by starting at the root node and exploring deeper into the tree branch where possible then backtracks if there are no possible nodes to explore and the goal has not been reached.

The algorithm work by taking the current node otherwise known as root, checks and keeps track of its neighbors, expanding a random node among the neighboring nodes. This goes on and on until the goal is reached or a solution is found. It makes use of a stack data structure for adding and removing nodes(neighboring nodes) in a last-in-first-out data type format.

I will also use an auxiliary set for maintaining the explored nodes to make sure the algorithm does not visit nodes previously visited since this may cause an infinite loop. Let's demonstrate these visually.

Using the above search tree, let's have the algorithm find a path from A to E. The First thing is to initialize a stack with the starting node added to it, the goal which is E and explored set. As of now, our start node is A so we add it to our stack.

Next step, we remove the last item in our stack and explore its neighbors. Since we only have A, we expand it. Node A has just one neighbor, B. Add it to our stack as well as A to the explored set.

Now, we check if our stack has something, if yes, we remove the last item and explore it. In this case, it's node B. The neighbors of B are C and D. Therefore, we add them to the stack and B to the explored set.

Next, check the stack and remove the last item which is D and explore its adjacent nodes, F. Add F to the stack and D to explored set.

Next, we consider F since it's the last item in the stack. It has no neighbors, therefore, we consider this a dead end. In such a case we just add the node to the explored set and backtrack if the stack is not empty.

The stack has one item. We remove it and consider the neighbors which is a single node, E. Add E to the stack and C to the explored set.

Our stack has a single item, E. We remove it for exploring. There is no need to explore this one because it's our goal, therefore, we add it to the explored set and terminate the algorithm. The final path is;

Breadth-First Search

This algorithm is quite similar to the Depth-First search except that as opposed to using a stack to store the nodes like DFS, it uses a queue, a first-in-first-out data type. Also, BFS explores all the neighbor nodes of the current node before moving on to the nodes at the next depth level. To demonstrate this visually, we will use the last search tree and initialize node A as the root, a queue with the starting node A, and explored set.

As before, we remove the first node in our queue, explore its neighbors, add the neighbors in the queue and then add the removed node to the explored set. Node A has one neighbor, B. We consider this node.

Next, we remove B the same way and explore its neighbors, C, and D by adding them to the queue.

Now here's when things start to get interesting because instead of removing D as in the case for DFS, we remove C since it's the first node that came in first before D. Find neighbor nodes to C which is E, add to the queue and then add C to explored set.

The next node to remove is D. Its neighbor is F so we add F to the queue and D to the explored.

Next, we remove E. Since it's our goal, we add it to the explored and terminate the algorithm successfully. At this point, we have solved the problem.
Notice our queue still has an item because the AI reached the goal before exploring all the nodes.

The general pseudo-code;

- Initialize a stack/queue
- initialize an empty explored set
- While the stack/queue is not empty
     - Remove the last node from stack(DFS)/first from queue(BFS)
     - If node is the goal, terminate and return solution, otherwise
     - Find neighbor nodes of the removed node and store it in N
     - Add the removed node to the explored
     - For each node in N, add to stack/queue if they are not in either stack/queue or explored set
     - Repeat

Let's look at how these algorithms can work in practice by writing some code to solve a real problem. At the start of this article, I mentioned one of the classical problem in search called Maze solving. It's the same problem we will solve using these algorithms. The code will be written purely in Python programming language.

Note; you can use any language as long as you focus on the pseudo-code and not Python syntax since it may become confusing translating Python code to other languages.

First, we will define our maze in file called map.txt, can be any name; In the maze below, b represents the AI, e the door and # are the walls. I chose the simplest but you can try with a more sophisticated maze. The algorithm with still work correctly.

#######
#  #  #
#  # b#
#  #  #
e     #
#     #
#######

class Node:
  def __init__(self, root, action, state):
    self.state = state
    self.root = root
    self.action = action


class DFS:
  def __init__(self):
    self.stack = []

  def is_empty(self):
    """
    check if the stack is empty
    """
    return len(self.stack) == 0

  def add(self, node):
    """
    Add a new item to to end of a stack
    """
    self.stack.append(node)

  def remove(self):
    """
    Remove from the end of a stack, using the
    Last in first out(LIFO)
    """
    node = self.stack[-1]  # remove the last node from the stack
    self.stack = self.stack[:-1]  # update the stack

    return node

  def contains(self, state, iterable):
    """
    Check if an item exists in a listjg
    """
    for item in iterable:
        if item.state == state:
            return True
    return False

  def algorithm(self, start, goal, callback):
    """
    This algorithm go through all the possible nodes
    that can be explored in a graph and returns the optimum
    path used to reach the goal
    """
    explored = list()  # maintain all the nodes that have been visitted
    count = 0
    begin = start

    start_node = Node(root=None, action=None, state=begin)
    self.add(start_node)  # add start node to the our stack

    while not self.is_empty():
        node = self.remove()
        count += 1  # keep a count of the number of visited nodes

        if node and node.state == goal:  # go here if the current node is our goal
            explored = []

            # backtracking to find the path used to get to the goal
            # an optimum path
            while node.root:
                explored.append(node.state)
                node = node.root
            break

        n = callback(node.state)

        # use the current that's being exployed and expand it to get
        # it's neighbouring nodes for exploring
        for a, new_state in n:
            if not self.contains(new_state,
                                 self.stack) and not self.contains(
                                     new_state, explored):
                child_node = Node(root=node, action=a, state=new_state)
                self.add(child_node)
        explored.append(node)
    return count, list(reversed(explored))


class BFS(DFS): # Inherits from DFS since it has similar functionalities
    def remove(self):
        node = self.stack[
            0]  # Removing an item from the list at the zero index (FIRST IN FIRST OUT(FIFO) or queue)
        self.stack = self.stack[1:]

        return node

• Gist

The source code for parsing the maze is on GitHub, you can take a look at maze-solver.

Running the solver using the algorithm above we get;

I found this video quite interesting and informative. It decodes the whole idea of search problems in animated robots.

https://youtu.be/8dEdCea-UVU

Final word

Depth-First search and Breadth-First search are a kind of search algorithms that don't use any problem specific knowledge to find a solution to a search problem. In other words, they are not so intelligent.

There are a couple of algorithms that are intelligent or use problem specific knowledge to solve a search problem. We will look at some of them in future articles. These are;

• A* search algorithm
• Greedy best-first search
• Minimax
• Alpha-beta pruning

References

• Wikipedia: Depth-First Search algorithm
• Wikipedia: Breadth-First Search
• Introduction to Artificial Intelligence with Python
• DFS-traversal-of-a-tree-using-recursion
• Depth First Search
• Graph Traversal
• Introduction to Algorithms(CLRS) 3rd Edition, chapter 22, section 22.2 and section 22.3 p. 594 and p. 603