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.
