Posts: 23
Threads: 11
Joined: Nov 2023
Not really sure this could be called homework as there aren't any assignments, but it feels like a homework-ish question so figure I'd post it here. This is part of a self paced Edx class with youtube videos.
I'm trying to learn how to set up heuristics for the Greedy Best First Search.
Basically the idea is to call the python file and the maze file from the command line.
Ie.. typing on the command line something like this: python "maze - DFS - CLI.py" "maze.txt" the text file is literally just a few number signs denoting walls in the maze.
maze.txt would look like this. Sorry about picture, but I couldn't get the blank spaces to show up properly.
This maze example is 7 rows by 12 Columns.
Here is the code for a working example of the depth first search (provided by the class).
import sys
class Node():
def __init__(self, state, parent, action):
self.state = state #Current State
self.parent = parent #State before the Current State
self.action = action #Action Taken on Current State to Generate Next State
#In This Case Not Tracking the Path Cost until the end, but the path cost could be tracked here.
#The Class Stack Frontier is used to keep track of the explored states for DFS
#Stack Frontier is for DFS
class StackFrontier():
#Initially creates a frontier objects
def __init__(self):
self.frontier = [] #with an empty set
#Adds node to frontier object LIFO stack
def add(self, node):
self.frontier.append(node)
#Check if the frontier contains a specific state
def contains_state(self, state):
return any(node.state == state for node in self.frontier)
#Check if the frontier is empty
def empty(self):
return len(self.frontier) == 0
#Remove something from the frontier. If its empty give error.
def remove(self):
if self.empty():
raise Exception("empty frontier")
else:
node = self.frontier[-1]
self.frontier = self.frontier[:-1] #if python gets to the end of the list, ie point zero in the list, it will wrap around to the last item in the list with this technique.
return node
#A new class that INHERITS from the StackFrontier Class with the exception that the way it removes
#Queue Frontier is for BFS.
class QueueFrontier(StackFrontier):
def remove(self):
if self.empty():
raise Exception("empty frontier")
else:
node = self.frontier[0] #Sets frontier to the first node
self.frontier = self.frontier[1:] #Returns the first node
return node
class Maze():
def __init__(self, filename):
# Read file and set height and width of maze
with open(filename) as f:
contents = f.read()
# Validate start and goal
if contents.count("A") != 1:
raise Exception("maze must have exactly one start point")
if contents.count("B") != 1:
raise Exception("maze must have exactly one goal")
# Determine height and width of maze
contents = contents.splitlines()
self.height = len(contents)
self.width = max(len(line) for line in contents)
# Keep track of walls
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):
"""Finds a solution to maze, if one exists."""
# Keep track of number of states explored
self.num_explored = 0
# Initialize frontier to just the starting position
start = Node(state=self.start, parent=None, action=None)
frontier = StackFrontier() #Initialize object as Class Stack Frontier
frontier.add(start)
# Initialize an empty explored set
self.explored = set()
# Keep looping until solution found
while True:
# If nothing left in frontier, then no path
if frontier.empty():
raise Exception("no solution")
# Choose a node from the frontier
node = frontier.remove()
self.num_explored += 1
# If node is the goal, then we have a solution
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
# Mark node as explored
self.explored.add(node.state)
# Add neighbors to frontier
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=False):
from PIL import Image, ImageDraw
cell_size = 50
cell_border = 2
# Create a blank canvas
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):
# Walls
if col:
fill = (40, 40, 40)
# Start
elif (i, j) == self.start:
fill = (255, 0, 0)
# Goal
elif (i, j) == self.goal:
fill = (0, 171, 28)
# Solution
elif solution is not None and show_solution and (i, j) in solution:
fill = (220, 235, 113)
# Explored
elif solution is not None and show_explored and (i, j) in self.explored:
fill = (212, 97, 85)
# Empty cell
else:
fill = (237, 240, 252)
# Draw cell
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("""Usage: python "maze - DFS - CLI.py" "maze.txt"""")
m = Maze(sys.argv[1])
print("Maze:")
m.print()
print("Solving...")
m.solve()
print("States Explored:", m.num_explored)
print("Solution:")
m.print()
m.output_image("maze - DFS - CLI.png", show_explored=True)
My question is about my attempt to modify the above code to add a heuristic to follow the Greedy Best First Search algorithm.
I tried to modify the solve function as follows
def solve(self):
"""Finds a solution to maze, if one exists."""
# Keep track of number of states explored
self.num_explored = 0
# Initialize frontier to just the starting position
start = Node(state=self.start, parent=None, action=None)
frontier = StackFrontier() #Initialize object as Class Stack Frontier
frontier.add(start)
# Initialize an empty explored set
self.explored = set()
# Keep looping until solution found
while True:
# If nothing left in frontier, then no path
if frontier.empty():
raise Exception("no solution")
# Choose a node from the frontier - Removes the Current node and sets it to explored.
node = frontier.remove()
self.num_explored += 1 #Update the Number of states explored. Ie.. first loop removes initial state and increments to 1 from zero.
# If node is the goal, then we have a solution
if node.state == self.goal:
actions = [] #Initialize Action List so we can backtrack the steps taken to reach the goal
cells = [] #Initialize Cells List so we can Back Track steps taken to reach the goal.
while node.parent is not None:
actions.append(node.action) #Fills Actions List with the Actions taken. LIFO
cells.append(node.state) #Fills Cells List with Cells taken. LIFO
node = node.parent #Continues working backwards until there are no parents. Ie.. start state is reached.
actions.reverse() #Reverses List so we can see the solution from first step
cells.reverse() #Reverses List so we can see the solution from first step
self.solution = (actions, cells) #saves the solution to the object
return
# Mark node as explored, no need to re-examine if the node is checked in the future.
self.explored.add(node.state)
#Make an array to store manhattan distance values
MD = []
#row, col = node.state
#print("row ", row)
#print("column ", col)
goal_row, goal_col = self.goal
#print("maze goal row ", goal_row)
#print("maze goal col ", goal_col)
# Add neighbors to frontier - Look at all the neighboring Cells
for action, state in self.neighbors(node.state):
#If the state is not in the frontier and if its not in the explored set, then add to the frontier as a child.
if not frontier.contains_state(state) and state not in self.explored:
child = Node(state=state, parent=node, action=action)
row, col = node.state
MD.append([abs(goal_row - row) + abs(goal_col - col), state, node, action])
MD.sort() #sort the lowest path cost to be first
child = Node(state = MD[0][1], parent = MD[0][2], action = MD[0][3])
frontier.add(child) #add the best node to the frontier based on the sorted list above? Here's my full broken code if you want to see it also.
import sys
class Node():
def __init__(self, state, parent, action):
self.state = state #Current State
self.parent = parent #State before the Current State
self.action = action #Action Taken on Current State to Generate Next State
#In This Case Not Tracking the Path Cost until the end, but the path cost could be tracked here.
#The Class Stack Frontier is used to keep track of the explored states for DFS
#Stack Frontier is for DFS
class StackFrontier():
#Initially creates a frontier objects
def __init__(self):
self.frontier = [] #with an empty set
#Adds node to frontier object LIFO stack
def add(self, node):
self.frontier.append(node)
#Check if the frontier contains a specific state
def contains_state(self, state):
return any(node.state == state for node in self.frontier)
#Check if the frontier is empty
def empty(self):
return len(self.frontier) == 0
#Remove something from the frontier. If its empty give error.
def remove(self):
if self.empty():
raise Exception("empty frontier")
else:
node = self.frontier[-1] #LIFO - Last in First out. If you index into a list with -1, it gets you the last item in a list.
self.frontier = self.frontier[:-1] #if python gets to the end of the list, ie point zero in the list, it will wrap around to the last item in the list with this technique.
return node
#A new class that INHERITS from the StackFrontier Class with the exception that the way it removes
#Queue Frontier is for BFS.
class QueueFrontier(StackFrontier):
def remove(self):
if self.empty():
raise Exception("empty frontier")
else:
node = self.frontier[0] #FIFO - Removes First Node in.
self.frontier = self.frontier[1:] #Returns the first node
return node
class Maze():
def __init__(self, filename):
# Read file and set height and width of maze
with open(filename) as f:
contents = f.read()
# Validate start and goal
if contents.count("A") != 1:
raise Exception("maze must have exactly one start point")
if contents.count("B") != 1:
raise Exception("maze must have exactly one goal")
# Determine height and width of maze
contents = contents.splitlines()
self.height = len(contents)
self.width = max(len(line) for line in contents)
# Keep track of walls
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):
"""Finds a solution to maze, if one exists."""
# Keep track of number of states explored
self.num_explored = 0
# Initialize frontier to just the starting position
start = Node(state=self.start, parent=None, action=None)
frontier = StackFrontier() #Initialize object as Class Stack Frontier
frontier.add(start)
# Initialize an empty explored set
self.explored = set()
# Keep looping until solution found
while True:
# If nothing left in frontier, then no path
if frontier.empty():
raise Exception("no solution")
# Choose a node from the frontier - Removes the Current node and sets it to explored.
node = frontier.remove()
self.num_explored += 1 #Update the Number of states explored. Ie.. first loop removes initial state and increments to 1 from zero.
# If node is the goal, then we have a solution
if node.state == self.goal:
actions = [] #Initialize Action List so we can backtrack the steps taken to reach the goal
cells = [] #Initialize Cells List so we can Back Track steps taken to reach the goal.
while node.parent is not None:
actions.append(node.action) #Fills Actions List with the Actions taken. LIFO
cells.append(node.state) #Fills Cells List with Cells taken. LIFO
node = node.parent #Continues working backwards until there are no parents. Ie.. start state is reached.
actions.reverse() #Reverses List so we can see the solution from first step
cells.reverse() #Reverses List so we can see the solution from first step
self.solution = (actions, cells) #saves the solution to the object
return
# Mark node as explored, no need to re-examine if the node is checked in the future.
self.explored.add(node.state)
#Make an array to store manhattan distance values
MD = []
#row, col = node.state
#print("row ", row)
#print("column ", col)
goal_row, goal_col = self.goal
#print("maze goal row ", goal_row)
#print("maze goal col ", goal_col)
# Add neighbors to frontier - Look at all the neighboring Cells
for action, state in self.neighbors(node.state):
#If the state is not in the frontier and if its not in the explored set, then add to the frontier as a child.
if not frontier.contains_state(state) and state not in self.explored:
child = Node(state=state, parent=node, action=action)
row, col = node.state
MD.append([abs(goal_row - row) + abs(goal_col - col), state, node, action])
MD.sort() #sort the lowest path cost to be first
child = Node(state = MD[0][1], parent = MD[0][2], action = MD[0][3])
frontier.add(child) #add the best node to the frontier based on the sorted list above?
def output_image(self, filename, show_solution=True, show_explored=False):
from PIL import Image, ImageDraw
cell_size = 50
cell_border = 2
# Create a blank canvas
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):
# Walls
if col:
fill = (40, 40, 40)
# Start
elif (i, j) == self.start:
fill = (255, 0, 0)
# Goal
elif (i, j) == self.goal:
fill = (0, 171, 28)
# Solution
elif solution is not None and show_solution and (i, j) in solution:
fill = (220, 235, 113)
# Explored
elif solution is not None and show_explored and (i, j) in self.explored:
fill = (212, 97, 85)
# Empty cell
else:
fill = (237, 240, 252)
# Draw cell
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("""Usage: python "maze - GBFS - CLI.py" "maze.txt"""")
m = Maze(sys.argv[1])
print("Maze:")
m.print()
print("Solving...")
m.solve()
print("States Explored:", m.num_explored)
print("Solution:")
m.print()
m.output_image("maze - GBFS - CLI.png", show_explored=True)
I'm not sure what I'm doing wrong, but I'm open to suggestions or better approaches to adding the heuristic into this type of maze solving problem.
Thanks again for the help!
|