Consider the maze shown below. The yellow cells represent the walls. We want to find the way from node $A$ located in cell (0,7) (bottom left) to $B$ located in cell (8,0) (top right). Implement a Depth First Search that would escape from the maze and reach position $B$. Start by building the graph corresponding to the feasible paths (i.e. connecting the blue cells). Then implement DFS and apply it, starting with $A$ as your root node.
You may want to implement functions ind2num and ind2num to go back and forth between the number of the cell and its position on the grid.
import scipy.io as sio
import matplotlib.pyplot as plt
Maze = sio.loadmat('MazeMat.mat')['MazeMat']
plt.imshow(Maze)
plt.show()
# put your code here
# put your code here
We now want to implement an informed search method. Code the A$^*$ search algorithm using as your heuristic the distance as the crow flies between the current node and the objective node.
# put your code here
Test your algorithms on the Maze below. Starting from the yellow square and trying of reach the exit (light blue).
import scipy.io as sio
import matplotlib.pyplot as plt
Maze2 = sio.loadmat('mazeImage.mat')['mazeImage']
plt.imshow(Maze2)
plt.show()
Depth First Search can actually be used to generate mazes. Follow the steps below to generate your own map.
Choose the initial cell, mark it as visited and push it to the stack
While the stack is not empty:
def MazeGeneration(n):
'''the function should take as input the size of the maze and should return
a starting point (location of PACMAN, P in yellow), an exit
location (E in light blue as above) and a binary image of the maze '''
return Maze, P, E
Once you are done with 1.4., try to implement a Maze generating function that takes an input a PacMan location, an exit location, and a size parameter and return the binary image of the maze. (hint: use the bidirectional search approach)
def Bidirectional_MazeGeneration(n, P, E):
'''The function should take as input a starting point ('Pacman location'),
an Exit location 'E' and should return the image/map of the maze'''
return Maze
Now that you are comfortable with Search methods, Maze and object oriented programming, we want to combine the tools to define a basic search agent.
The Escape Agent will inherit from the class Agent. It should have an initialization function which takes as argument the search method (as a string) that it is going to use to escape the maze. The list of possible inputs should include 'BFS', 'DFS', 'Astar', 'BF'. It should also contain an argument indicating the problem we want to solve (for the moment the only value this argument should take is 'escape'). Finally, for the informed search methods, it should contain the name of the heuristic used. We will consider two heuristics which you should define as separate functions (outside the class):
The Agent should also contain a function 'program' which takes as input the state of the environment (current position + list of admissible neighbors)
The Maze environment should contain an initialization function which generates a random maze. This environment should also contain a function 'get_nextState' which for any given state returns the possible neighbors of that state. The 'program' function of the agent will then choose its next move among those states (possibly with the heuristic function).
In this first exercise, the Agent should keep track of a list of actions (generated when the original state is given. At each step, it should then take its next action from the list)
class Agent:
'''Class should contain basic parameters common to all the agents'''
def __init__(self, program=None):
self.actions = [] # should contain the list of actions as
# returned by the search algorithm
class EscapeAgent(Agent):
'''The Escape Agent'''
def __init__(self, SearchFun = 'DFS', problem = 'escape', heuristic = None):
'''Function should initilize the agent with a Search Method and possible heuristic'''
self.searchMethod = SearchFun
def generateActions(self, initialState):
# Apply the Search Method
return self.actions
def program(self, state):
return self.actions[0]
class MazeEnvironment:
def __init__(self):
self.agents = [] # should keep a list of agents
def get_nextStates(self, state):
'''Function should generate the neighboring states.
This function will be used later when adding other elements in the maze'''
def step():
'''enable the agent to move one step: Take action from list of actions
and modify state of the environment'''
def addSearchAgent():
Run your agent on various mazes generated through the environment and display the path followed by your agent
# put your code here
maxStep = # choose a number of steps
for step in range(0,maxStep):
MazeEnvironment.step()
We now want to improve the environment. The first improvement we will consider are food pellets. Those should be represented by green pixels on the path of the agent. The Food Agent should inherit all the search methods from the class SearchAgent but now, each time it found a food pellet, it should recompute the path to the next pellet.
The MazeEnvironment_withFood class should thus encode the location of the food pellets and update the list of locations whenever the agents captured one of the pellets.
class FoodAgent(SearchAgent):
'''Class should contain basic parameters common to all the agents'''
def __init__(self, program=None):
class MazeEnvironment_withFood:
self.status = [] # should be updated when
def __init__(self):
'''should generate a maze with a few food pellets located on the path'''
def get_nextStates(self, state):
'''should return the neighbors of the current state'''
def step():
def addSearchAgent():
A ghost is an additional (fixed) position on the path. When the agent notices it, it should backtrack and look for another path that avoids this ghost.
class Ghost:
'''Class should contain '''
def __init__(self, position):
self.position = position
class MazeEnvironment_withFood_and_Ghosts:
self.status = [] # should be updated when
def __init__(self):
'''should generate a maze with a few food pellets and ghosts'''
def get_nextStates(self, state):
'''should return the neighbors of the current state'''
def step():
def addSearchAgent():
Once you have successfully coded the fixed ghost framework, try to enable the ghosts to move throughout the maze. Concretely, this means you now update the position of the ghost at random (following from the set of connected neighbors). Note that a ghost can be located on top of a pellet. Only one of the two will be visible (except if you improve the display). Just keep track of both positions.
class MazeEnvironment_withFood_and_MovingGhosts:
self.status = [] # should be updated when
def __init__(self):
'''should generate a maze with a few food pellets and ghosts'''
def get_nextStates(self, state):
'''should return the neighbors of the current state'''
def step():
self.status = # update the positions of the ghosts
def addSearchAgent():
Update the environement of your choice to keep track of a list each frame. One possibility is for the function step to return the current frame. Then use matplotlib animation API (or any other movie generating library) to generate the movie of your agent's escape.
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
# put your code here