Python Forum

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.

[Image: maze-example.png]

Here is the code for a working example of the depth first search (provided by the class).

Hide/Show

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.

Hide/Show

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!

RockBlok