Maze Solver- The search algorithm (Instructor Name: Nuruzzaman Faruqui)

 The Maze:

A maze is a path or collection of paths, typically from an entrance to a goal. The word is used to refer both to branching tour puzzles through which the solver must find a route, and to simpler non-branching patterns that lead unambiguously through a convoluted layout to a goal.

 Introduction

The maze solver basically a search problem that defines paths an agent is looking for. The agent is a term used in Artificial Intelligence to solve several kinds of search problems like the maze solver. Rational agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve a specific problem and provide the best result. We use search algorithm and solve the maze. The automation of operations in various factories, certain robots that can make decisions without human help, cars that can drive alone this type of problem solve need maze solver.

 

 This is an important part of Artificial Intelligence course and this  lab report is done by myself under the supervision of Nuruzzaman Faruqui, lecturer of City University, Bangladesh. From this course we get to explore the real applicable approaches through AI and also acquires better knowledge of the functionality of AI and how AI is making our daily life easier. That's why this is the best Artificial Intelligence course in Bangladesh.  

 

Problem Statement: 

The automation of operations in various factories, certain robots that can make decisions without human help, cars that can drive alone this type of problem solve need maze solver. We solve any maze to maintain some state by state. Those state are given bellow-

Initial State: It means exactly what it sounds. Where the agent begins its journey.

Actions: In any state, the agent can perform its operation to move toward the target state. That agent has to make choices for that. This set of choices are evaluated as actions.

Transition Model: After performing action there’s a change or movement that occurs in any state of an environment. The transition model describes that change through the result function.

Goal Test: After the transition model, the agent must look at whether the new state it’s in is the target state it was searching for or not.

Path cost: Once the agent reaches the target state it can determine the total cost it had to spend since the beginning of its journey. The cost provides numerical values.

 The Maze solver algorithm using Stack and Queue Frontier is given bellow-

Algorithm

1.      A frontier that contains the initial state.

2.      An empty explored set

Repeat

3.      If the frontier is empty.

a.       Stop. No solution to the problem.

4.      Remove a node from the frontier. This node will be considered and move to explored set.

5.      If the node contains goal state,

a.        return the solution. Stop.

6.      Else

a.       Add the current node to the explored set.

b.      Expand node. Add resulting nodes to the frontier if they aren’t already in the frontier.

 

Code Commentary: 

import sys

class Node():

    def __init__(self, state, parent, action):
        self.state = state
        self.parent = parent
        self.action = action

class StackFrontier():

    def __init__(self):
        self.frontier = []

    def add(self, node):
        self.frontier.append(node)

    def empty(self):
        return len(self.frontier) == 0

    def remove(self):
        if self.empty():
            raise Exception("The frontier is empty")
        else:
            node = self.frontier[-1]
            self.frontier = self.frontier[:-1]
            return node

    def contains_state(self, state):
        return any(node.state == state for node in self.frontier)

# Instead of Stack we have to use Queue

class Maze():

    def __init__(self, filename):

        with open(filename) as f:
            contents = f.read()

        if contents.count("A") != 1:
            raise Exception("The maze doesn't have a starting point")
        if contents.count("B") != 1:
            raise Exception("The maze doesn't have a exit (exit means goal)")

        # Study the structure of the maze (We will start from here)

        contents = contents.splitlines()
        self.height = len(contents)
        self.width = max(len(line) for line in contents)

        # We want to track the walls here
        self.walls = []
        for i in range(self.height):
            row = []
            for j in range(self.width):
                try:
                        if contents[i][j] == "A":
                            self.start = (i, j)
                            row.append(False)
                        elif contents[i][j] == "B":
                            self.goal = (i, j)
                            row.append(False)
                        elif contents[i][j] == " ":
                            row.append(False)
                        else:
                            row.append(True)
                except IndexError:
                    row.append(False)

            self.walls.append(row)

        self.solution = None

    def print(self):
        solution = self.solution[1] if self.solution is not None else None
        print()
        for i, row in enumerate(self.walls):
            for j, col in enumerate(row):
                if col:
                    print("█", end="")
                elif (i, j) == self.start:
                    print("A", end="")
                elif (i, j) == self.goal:
                    print("B", end="")
                elif solution is not None and (i, j) in solution:
                    print("*", end="")
                else:
                    print(" ", end="")
            print()
        print()


    def neighbors(self, state):
        row, col = state
        candidates = [
            ("up", (row - 1, col)),
            ("down", (row + 1, col)),
            ("left", (row, col-1)),
            ("right", (row, col+1))
        ]
        result = []
        for action, (r, c) in candidates:
            if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
                result.append((action, (r, c)))
        return result

    def solve(self):

        self.num_explored = 0

        start = Node(state=self.start, parent=None, action=None)
        frontier = StackFrontier()
        frontier.add(start)

        self.explored = set()

        while True:
            if frontier.empty():
                raise Exception("There is no solution")

            node = frontier.remove()
            self.num_explored += 1

            if node.state == self.goal:
                actions = []
                cells = []

                while node.parent is not None:
                    actions.append(node.action)
                    cells.append(node.state)
                    node = node.parent
                actions.reverse()
                cells.reverse()
                self.solution = (actions, cells)
                return
            self.explored.add(node.state)

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

    def output_image(self, filename, show_solution=True, show_explored=True):
        from PIL import Image, ImageDraw
        cell_size = 50
        cell_border = 2

        img = Image.new(
            "RGBA",
            (self.width * cell_size, self.height * cell_size),
            "black"
        )

        draw = ImageDraw.Draw(img)

        solution = self.solution[1] if self.solution is not None else None
        for i, row in enumerate(self.walls):
            for j, col in enumerate(row):
                if col:
                    fill = (40, 40, 40)
                elif(i, j) == self.start:
                    fill = (255, 0, 0)
                elif (i, j) == self.goal:
                    fill = (0, 171, 28)
                elif solution is not None and show_solution and (i, j) in solution:
                    fill = (220, 235, 113)
                elif solution is not None and show_explored and (i, j) in self.explored:
                    fill = (212, 97, 85)
                else:
                    fill = (237, 240, 252)

                draw.rectangle(
                    ([(j * cell_size + cell_border, i * cell_size + cell_border),
                      ((j + 1) * cell_size - cell_border, (i + 1) * cell_size - cell_border)]),
                    fill = fill
                )
        img.save(filename)

if len(sys.argv) != 2:
    sys.exit("use this command: python maze.py maze1.txt")

m = Maze(sys.argv[1])
print("This is our Maze:")
m.print()
print("Solving the maze ...")
m.solve()
print("Number of explored states: ", m.num_explored)
print("This is the Solution: ")
m.print()
m.output_image("The_Maze.png", show_explored=True)

 

Result:

We implement the maze solving algorithm in Python Language.

 

Conclusion:

In this lab work we discussed the introduction of Maze Solver, then how to solve this problem with AI. This kind of work teach how the machine decides search algorithm works in AI, How can we use AI in our daily life to make things easier? The above problem we just solved is a great example of that. To solve the search problem, we have an agent. That agent we need to make intelligent. So that it can make a decision when it encounters some difficulties to find the path. In above this discussion we with help of maze solving algorithm we can make things more easier.