Introduction: The maze solver basically a search problem that defines paths an agent is looking for. The agent is a term used in Artificial...
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. What agent’s
function is to become an entity that comprehends from the environment that the
agent is based on and performs an operation on that environment. The
problem is discussed broadly in the problem statement section. This problem has
been solved in python. Since it’s a searching problem we can use DFS(Depth-First-Search)
and BFS(Breadth-First-Search). In this report, we will follow the DFS
algorithm.
This report is a part of the Artificial Intelligence course
Lab-work under the supervision of Nuruzzaman Faruqui, Lecturer of City
University, Bangladesh. This course offers students various up-to-date AI
topics. Students get to explore the real applicable approaches through AI. From
this course, students acquire a better knowledge of the functionality of AI and
how AI is making our daily life easier. This is the best Artificial
Intelligence course in Bangladesh
Problem Statement:
An example could be used regarding this problem. We all are familiar with google
maps. How google maps find the best route from one destination to another.
To
understand the problem, let’s focus on the google maps approach. As we can see from
the above picture, there are multiple routes for one destination. Usually, we
get confused about which way we should choose. Here google maps show its magic by
using machine learning. It looks into
various factors such as time, cost, number of vehicles i.e., traffic jams, etc.
and based on this data-analysis it gives us an optimized route that fits us.
Similarly, in the maze
solver problem, an agent has to look for paths to reach a target. Now there
could be many ways to meet the target and others may lead to a dead end. So, like
a maze solver, our goal is to help that agent find a path that will take it to its
target.
So, to do that let’s get
familiarized with few more terms that we will use to solve this maze. And those
are:
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.
Now before we jump into
the code let’ build the algorithm first. How we can make our agent move, how it
can apply actions to the environment. We don’t want any solutions which is not
optimized means path cost is high. We will have to make our algorithm according
to that.
Algorithm Description:
We will use three data
structures in the whole process. Let’s call them node, frontier, and explore.
What these can do? Well, the node is a data structure that will keep track of the agent’s
action, current state, parent state, and total cost of the path. If node B is a
current state of an agent, then node A would be its parent state. We can
generate all the possible paths in node sort of like trees.
Frontier is a unique data
structure that will store and remove nodes after agents perform any task. It
comes in handy when an agent faces multiple ways in its journey. If we focus on the
above picture, once the agent reach node B, it will have to choose between node
C and node D. This where the frontier data structure is needed. In frontier two
search algorithm can be chosen. One is Depth Fast Search (DFS) and the other is
Breadth Fast Search (BFS).
What DFS does is when the agent
enters into a node, it keeps traversing all the child nodes until the end. It
does not care whether the agent will meet the target state or not. We can use
the following figures again for the sake of simplicity. Once the agent reaches node B, in the frontier two-node C and D will be stored. Now for DFS stack means
last in first out. In our case, if D comes at last, so it will be removed from the
frontier. And the agent will visit node D and its child node.
For the BFS queue means the first
in first out procedure is used. In this solution, we will follow the BFS
approach.
 |
|||
And the last one we will use for our solution is
explored set. What it does is once a node is removed from Frontier, it will
store that node, just in case our agent does not move back in the parent node again
and falls into an infinite loop.
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 explanation
To get information about
functions, constants, and methods of python we will have an import sys module.
We will use a bunch of
classes to iterate the whole algorithm.
Since the node is working as our AI agent let’s give it a class and how can
we use an agent in our program. A node can have a parent node, we can take a certain action on a node, also a node’s position will refer to a class node. At
first, create a project with the help of an IDE, then make a file with an extension of “.py” and another one with an extension of “.txt”. So, we will create
constructors and instances of objects underclass node. In the __init__ refers to the initialization and
“self” represent instances of the object.
1. import sys
2. class Node():
3. def __init__(self, state , parent , action): #path cost will be determined later
4. self.state=state
5. self.parent=parent
6. self.action=action
Next, our whole procedure
will rely on the frontier. Let’s give this class name StackFrontier. In frontier, we
can add and remove nodes. That’s why a list was chosen. Before removing a node
from the frontier list, we need to check whether the list is empty or not. If it’s
not empty then we will remove the last node from the frontier and store the
remaining node inside the list. The last node will be removed because we are using
DFS.
1. class StackFrontier():
2. def __init__(self):
3. self.frontier=[]
4.
5. def add(self, node):
6. self.frontier.append(node)
7. def empty(self):
8. return len(self.frontier)==0
9. def remove(self):
10. if self.empty():
11. raise Exception("The frontier is empty")
12. else:
13. node=self.frontier[-1] #stack (last in first out
14. self.frontier=self.frontier[:-1] #everything from the end/ we took last node, rest is stored
15. return node #removing means returning node from frontier
16. def contains_state(self, state): #for expand
17. return any(node.state== state for node in self.frontier)
Then we will define our
maze. To do that let’s create another class Maze. In this class what mainly we
will do is the maze we want to solve must be in a text file inside the same
project. So that in the maze class we open, read, and manipulate that text file
to help understand our AI about the maze’s structure. As an example, if we take
the maze below then the starting point would be A and our goal state is B.
###
#########
# ################### # #
# #### # # # #
# ################### # # # #
# # # # #
##################### # # # #
# ## # # # #
# # ## ### ## ######### # # #
# # #
##B# # # #
# # ## ################ # # #
### ## #### # # #
### ############## ## # # # #
### ## # # # #
###### ######## ####### # # #
###### #### # #
A ######################
As we can see inside a
maze there are few open paths and blocks. In this case, # are used as blocks
and empty space is used as open paths. We will use a two-dimensional array to
locate the walls in the maze. To do that we need to first distinguish other
stuff from the maze. That is start, goal, and empty spaces. That way
successfully we can find our walls.
1. class Maze():
2. def __init__(self, filename):
3. with open(filename) as f:
4. contents = f.read()
5.
6. if contents.count("A") !=1:
7. raise Exception("The maze dosen't have a starting point")
8. if contents.count("B") !=1:
9. raise Exception("The dosen't have an exit")
10.
11. #study the structure of the maze
12. contents= contents.splitlines()
13. self.height=len(contents)
14. self.width = max(len(line) for line in contents) # maximum number of character is needed
15.
16. #look for walls
17. self.walls = []
18. for i in range(self.height):
19. row = []
20. for j in range(self.width):
21. try:
22. if contents[i][j] == "A":
23. self.start = (i, j)
24. row.append(False)
25. elif contents[i][j] == "B":
26. self.goal = (i, j)
27. row.append(False)
28. elif contents[i][j] == " ":
29. row.append(False)
30. else:
31. row.append(True) #current (i,j) is the walls
32. except IndentationError:
33. row.append(False)
34.
35. self.walls.append(row)
36.
37. self.solution = None
Now our computer can
understand the problem and solve it. But we, humans also need to understand the
solutions. That’s why let’s create a method “print”. Hereby using a two-dimensional array we will replace blocks that we located in our precious class with
"█" and empty space i.e., our solutions with “*”.
1. def print(self):
2. solution = self.solution[1] if self.solution is not None else None
3. print()
4. for i, row in enumerate(self.walls):
5. for j, col in enumerate(row):
6. if col:
7. print("█", end="")
8. elif (i, j) == self.start:
9. print("A" , end="")
10. elif (i, j) == self.goal:
11. print("B", end ="")
12. elif solution is not None and (i, j) in solution:
13. print("*" , end ="")
14. else:
15. print(" ", end="")
16. print() #if there is nothing inside the for loop,, error..to prevent error
17. print()
To check whether our
agent can make any transition we need to know about our neighbor’s. In this
method that’s what we do. To store the result of actions.
1. def neighbors(self, state):
2. row, col =state
3. candidates = [
4. ("up", (row -1, col)),
5. ("down",(row+1, col)),
6. ("left",(row,col-1)),
7. ("right",(row,col+1))
8. ]
9. result = []
10. for action,(r,c) in candidates:
11. if 0 <= r <self.height and 0<= c< self.width and not self.walls[r][c]: #to check if we have reached to the end of the maze
12. result.append((action,(r,c)))
13. return result
Next,
we will implement how to solve the maze with all the previous classes, methods
we just created.
So,
in the solve function, we will finally use the data structured explore to store
the node that is being removed by the frontier. So, we will have to call the
StackFrontier () function. If we do not find the goal state, we will simply add the
current node to the explored set.
1. def solve(self):
2. self.num_explored = 0
3. start = Node (state = self.start, parent =None , action = None) #instance of node and frontier
4. frontier = StackFrontier()
5. frontier.add(start) #add instance of node to the frontier
6.
7. self.explored= set()
8. while True:
9. if frontier.empty():
10. raise Exception("There is no solution")
11.
12. node = frontier.remove()
13. self.num_explored+=1
14.
15. if node.state == self.goal:
16. actions = []
17. cells = []
18.
19. while node.parent is not None:
20. actions.append(node.action)
21. cells.append(node.state)
22. node = node.parent
23. actions.reverse() # reverse the process to see the path from explored
24. cells.reverse()
25. self.solution = (actions, cells)
26. return
27. # if we do no find goal state....add current node to explorde set
28. self.explored.add(node.state)
29.
30. # ignoring already visited in exp set
31. for action, state in self.neighbors(node.state):
32. if not frontier.contains_state(state) and state not in self.explored:
33.
34. child = Node(state = state, parent= node , action=action) #object of node class called child
35. frontier.add(child)
To get a graphical image of our solution we will use the python imaging library PILLOW with
Image and ImageDraw.
The above image is the graphical representation of our maze. The yellow color represents
the solution to reach our goal state. That red mark defines start state A
and the green one represents goal state B.
We
will take another method outpu_image() which will make the graphical image.
Which are taken from ImageDraw official website. The following code explains
that.
1. def output_image(self, filename , show_solution=True, show_explored=True):
2. from PIL import Image, ImageDraw
3. cell_size = 50
4. cell_border = 2
5.
6. img = Image.new(
7. "RGBA",
8. (self.width * cell_size, self.height * cell_size),
9. "black"
10. )
11.
12. draw = ImageDraw.Draw(img)
13. solution = self.solution[1] if self.solution is not None else None
14. for i,row in enumerate(self.walls):
15. for j, col in enumerate(row):
16. if col:
17. fill = (40,40,40)
18. elif (i, j)==self.start:
19. fill=(255,0,0)
20. elif(i,j) == self.goal:
21. fill = (0,171,28)
22. elif solution is not None and show_solution and (i, j ) in solution:
23. fill = (220,235,113)
24. elif solution is not None and show_explored and (i, j) in self.explored:
25. fill = (212,97,85)
26. else:
27. fill = (237,240,252)
28. draw.rectangle(
29. ([(j * cell_size + cell_border, i * cell_size + cell_border),
30. ((j+1) * cell_size-cell_border,(i+1) * cell_size - cell_border)]),
31. fill = fill
32. )
33. img.save(filename)
34.
35. if len(sys.argv)!=2:
36. sys.exit("use this command: python maze.py maze1.txt")
37.
38. m=Maze(sys.argv[1])
39. print("Maze: ")
40. m.print()
41. print("Solving the maze...")
42. m.solve()
43. print("Number of explored states: ",m.num_explored)
44. print("Solution: ")
45. m.print()
46. m.output_image("The_Maze.png" , show_explored=True)
We should get the following
output:
Conclusion
The main reason for learning how the search
algorithm works in AI is you can acquire a better knowledge of the functionality of
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. Based on the decision the
agent makes we need to make our agent intelligent enough to take action. That
way our agent only can reach its goal.
As you can see, this course was instructed
that way, we go through the topic first, then apply what we learn into a real-life
problem. And solve it using python. I believe this is one of the best ways if
you are a beginner, just starting out in Artificial Intelligence. Without any
doubt, this course stands out as the best AI course in Bangladesh.
💜
ReplyDelete