Artificial Intelligence - UC Berkeley’s Project Search
The aim of this project is to get you acquainted with AI search techniques and how to derive heuristics in Pacman, as well as to understand the Python-based Pacman infrastructure.
Project link: UC Berkely - CS 188
Complete Github Repo: https://github.com/abhinavcreed13/ai-pacman-project-search
Task 1: Finding a Fixed Food Dot using Depth First Search
In searchAgents.py, you’ll find a fully implemented SearchAgent, which plans out a path through Pacman’s world and then executes that path step-by-step. The search algorithms for formulating a plan are not implemented – that’s your job. As you work through the following questions, you might find it useful to refer to the object glossary (the second to last tab in the navigation bar above).
First, test that the SearchAgent is working correctly by running:
python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch
The command above tells the SearchAgent to use tinyMazeSearch as its search algorithm, which is implemented in search.py. Pacman should navigate the maze successfully.
Implementation
def depthFirstSearch(problem):
"""
Search the deepest nodes in the search tree first.
Your search algorithm needs to return a list of actions that reaches the
goal. Make sure to implement a graph search algorithm.
To get started, you might want to try some of these simple commands to
understand the search problem that is being passed in:
print("Start:", problem.getStartState())
print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
print("Start's successors:", problem.getSuccessors(problem.getStartState()))
"""
class SearchNode:
"""
Creates node: <state, action, parent_node>
"""
def __init__(self, state, action=None, parent=None):
self.state = state
self.action = action
self.parent = parent
def extract_solution(self):
""" Gets complete path from goal state to parent node """
action_path = []
search_node = self
while search_node:
if search_node.action:
action_path.append(search_node.action)
search_node = search_node.parent
return list(reversed(action_path))
start_node = SearchNode(problem.getStartState())
if problem.isGoalState(start_node.state):
return start_node.extract_solution()
frontier = util.Stack()
explored = set()
frontier.push(start_node)
# run until stack is empty
while not frontier.isEmpty():
node = frontier.pop() # choose the deepest node in frontier
explored.add(node.state)
if problem.isGoalState(node.state):
return node.extract_solution()
# expand node
successors = problem.getSuccessors(node.state)
for succ in successors:
# make-child-node
child_node = SearchNode(succ[0], succ[1], node)
if child_node.state not in explored:
frontier.push(child_node)
# no solution
util.raiseNotDefined()
Task 2: Breadth First Search
Implement the breadth-first search (BFS) algorithm in the breadthFirstSearch function in search.py. Again, write a graph search algorithm that avoids expanding any already visited states. Test your code the same way you did for depth-first search.
python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5
Implementation
def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
class SearchNode:
"""
Creates node: <state, action, parent_node>
"""
def __init__(self, state, action=None, parent=None):
self.state = state
self.action = action
self.parent = parent
def extract_solution(self):
""" Gets complete path from goal state to parent node """
action_path = []
search_node = self
while search_node:
if search_node.action:
action_path.append(search_node.action)
search_node = search_node.parent
return list(reversed(action_path))
def is_in_frontier(self, data_structure):
for n in data_structure.list:
if n.state == self.state:
return True
return False
start_node = SearchNode(problem.getStartState())
if problem.isGoalState(start_node.state):
return start_node.extract_solution()
frontier = util.Queue() # FIFO
frontier.push(start_node)
explored = set()
while not frontier.isEmpty():
node = frontier.pop() # choose the shallowest node in frontier
explored.add(node.state)
if problem.isGoalState(node.state):
return node.extract_solution()
successors = problem.getSuccessors(node.state)
for succ in successors:
child_node = SearchNode(succ[0], succ[1], node)
if child_node.state not in explored and\
not child_node.is_in_frontier(frontier):
frontier.push(child_node)
# no solution
util.raiseNotDefined()
Task 3: Varying the Cost Function
By changing the cost function, we can encourage Pacman to find different paths. For example, we can charge more for dangerous steps in ghost-ridden areas or less for steps in food-rich areas, and a rational Pacman agent should adjust its behavior in response.
Implement the uniform-cost graph search algorithm in the uniformCostSearch function in search.py. We encourage you to look through util.py for some data structures that may be useful in your implementation. You should now observe successful behavior in all three of the following layouts, where the agents below are all UCS agents that differ only in the cost function they use (the agents and cost functions are written for you):
python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
python pacman.py -l mediumScaryMaze -p StayWestSearchAgent
Implementation
def uniformCostSearch(problem):
"""Search the node of least total cost first."""
class SearchNode:
"""
Creates node: <state, action, cost, parent_node>
"""
def __init__(self, state, action=None, path_cost = 0, parent=None):
self.state = state
self.action = action
self.parent = parent
if parent:
self.path_cost = path_cost + parent.path_cost
else:
self.path_cost = path_cost
def extract_solution(self):
""" Gets complete path from goal state to parent node """
action_path = []
search_node = self
while search_node:
if search_node.action:
action_path.append(search_node.action)
search_node = search_node.parent
return list(reversed(action_path))
def is_in_priority_queue(self, priority_queue):
""" Check if the node is already in the priority queue """
for index, (p, c, i) in enumerate(priority_queue.heap):
if i.state == self.state:
return True
else:
return False
start_node = SearchNode(problem.getStartState())
if problem.isGoalState(start_node.state):
return start_node.extract_solution()
frontier = util.PriorityQueue() # FIFO
frontier.push(start_node, start_node.path_cost)
explored = set()
while not frontier.isEmpty():
node = frontier.pop() # chooses the lowest-cost node in frontier
# goal-test
if problem.isGoalState(node.state):
return node.extract_solution()
if node.state not in explored:
explored.add(node.state)
successors = problem.getSuccessors(node.state)
for succ in successors:
child_node = SearchNode(succ[0], succ[1], succ[2], node)
frontier.update(child_node, child_node.path_cost)
# no solution
util.raiseNotDefined()
Task 4: A* search
Implement A* graph search in the empty function aStarSearch in search.py. A* takes a heuristic function as an argument. Heuristics take two arguments: a state in the search problem (the main argument), and the problem itself (for reference information). The nullHeuristic heuristic function in search.py is a trivial example.
You can test your A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic (implemented already as manhattanHeuristic in searchAgents.py).
python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar heuristic=manhattanHeuristic
Implementation
def aStarSearch(problem, heuristic=nullHeuristic):
"""Search the node that has the lowest combined cost and heuristic first."""
# class to represent SearchNode
class SearchNode:
"""
Creates node: <state, action, f(s), g(s), h(s), parent_node>
"""
def __init__(self, state, action=None, g=None, h=None,
parent=None):
self.state = state
self.action = action
self.parent = parent
# heuristic value
self.h = h
# combined cost
if parent:
self.g = g + parent.g
else:
self.g = 0
# evaluation function value
self.f = self.g + self.h
def extract_solution(self):
""" Gets complete path from goal state to parent node """
action_path = []
search_node = self
while search_node:
if search_node.action:
action_path.append(search_node.action)
search_node = search_node.parent
return list(reversed(action_path))
# make search node function
def make_search_node(state, action=None, cost=None, parent=None):
if hasattr(problem, 'heuristicInfo'):
if parent:
# same parent - avoid re-calculation
# for reducing computations in logic
if parent == problem.heuristicInfo["parent"]:
problem.heuristicInfo["sameParent"] = True
else:
problem.heuristicInfo["sameParent"] = False
# adding parent info for reducing computations
problem.heuristicInfo["parent"] = parent
# get heuristic value
h_value = heuristic(state, problem)
return SearchNode(state, action, cost, h_value, parent)
# create open list
open = util.PriorityQueue()
node = make_search_node(problem.getStartState())
open.push(node, node.f)
closed = set()
best_g = {} # maps states to numbers
# run until open list is empty
while not open.isEmpty():
node = open.pop() # pop-min
if node.state not in closed or node.g < best_g[node.state]:
closed.add(node.state)
best_g[node.state] = node.g
# goal-test
if problem.isGoalState(node.state):
return node.extract_solution()
# expand node
successors = problem.getSuccessors(node.state)
for succ in successors:
child_node = make_search_node(succ[0],succ[1],succ[2], node)
if child_node.h < float("inf"):
open.push(child_node, child_node.f)
# no solution
util.raiseNotDefined()
Task 5: Iterative Deepening Search
Implement the Iterative Deepening Search algorithm. You should be able to test the algorithm using the following command:
python pacman.py -l tinyMaze -p SearchAgent -a fn=ids
Implementation
def iterativeDeepeningSearch(problem):
"""Search the deepest node in an iterative manner."""
class SearchNode:
"""
Creates node: <state, action, depth, parent_node>
"""
def __init__(self, state, action=None, depth = 0, parent=None):
self.state = state
self.action = action
self.parent = parent
if parent:
self.depth = depth + parent.depth
else:
self.depth = depth
def extract_solution(self):
""" Gets complete path from initial state to goal state """
action_path = []
search_node = self
while search_node:
if search_node.action:
action_path.append(search_node.action)
search_node = search_node.parent
return list(reversed(action_path))
# limit for IDS
limit = 0
# controlling infinite loop
LOOP_COUNT = 0
LOOP_LIMIT = 999999999
# running iteratively
# increasing limit until goal-state is found
while True:
# no solution hard limit check
if LOOP_COUNT == LOOP_LIMIT:
break
node = SearchNode(problem.getStartState())
# goal-test
if problem.isGoalState(node.state):
return node.extract_solution()
frontier = util.Stack() # LIFO stack
explored = set() # empty set
frontier.push(node)
# run until frontier is empty
while not frontier.isEmpty():
node = frontier.pop() # choose the deepest node in frontier
explored.add(node.state)
# never expand branch farther than the limit
if node.depth < limit:
# expand node
successors = problem.getSuccessors(node.state)
for succ in successors:
# make-child-node
# path step cost is considered as depth
child_node = SearchNode(succ[0], succ[1], succ[2], node)
# child.STATE is not in explored
if child_node.state not in explored:
# GOAL-TEST done on generation
if problem.isGoalState(child_node.state):
return child_node.extract_solution()
frontier.push(child_node)
# goal-state not found -> increase limit by 1
limit += 1
LOOP_COUNT += 1
# no solution
util.raiseNotDefined()
Task 6: Enforced Hill Climbing (EHC) algorithm
Implement the Enforced Hill Climbing algorithm discussed in lectures, using Manhattan Distance as the heuristic. Note that you don’t have to implement Manhattan Distance, as this has already been implemented for you in the template code, although you will need to call the heuristic from inside your search. You should be able to test the algorithm using the following command:
python pacman.py -l mediumMaze -p SearchAgent -a fn=ehc,heuristic=manhattanHeuristic
Implementation
def enforcedHillClimbing(problem, heuristic=nullHeuristic):
"""
Local search with heuristic function.
You DO NOT need to implement any heuristic, but you DO have to call it.
The heuristic function is "manhattanHeuristic" from searchAgent.py.
It will be pass to this function as second arguement (heuristic).
"""
# class to represent SearchNode
class SearchNode:
"""
Creates node: <state, action, h(s), parent_node>
"""
def __init__(self, state, action=None, h = None, parent=None):
self.state = state
self.action = action
self.parent = parent
self.h = h
def extract_solution(self):
""" Gets complete path from goal state to parent node """
action_path = []
search_node = self
while search_node:
if search_node.action:
action_path.append(search_node.action)
search_node = search_node.parent
return list(reversed(action_path))
# make search node function
def make_search_node(state, action = None, parent = None):
h_value = heuristic(state, problem)
return SearchNode(state, action, h_value, parent)
# improve helper function
def improve(node_to_improve):
queue = util.Queue() # FIFO queue
queue.push(node_to_improve)
closed = set()
while not queue.isEmpty():
node = queue.pop() # pop-front
if node.state not in closed:
closed.add(node.state)
if node.h < node_to_improve.h:
return node
successors = problem.getSuccessors(node.state)
for succ in successors:
new_node = make_search_node(succ[0], succ[1], node)
queue.push(new_node)
# fail
return None
# main iterative loop
node = make_search_node(problem.getStartState())
while not problem.isGoalState(node.state):
node = improve(node)
if node:
return node.extract_solution()
else:
# no solution
util.raiseNotDefined()
Task 7: Challenge Question (more difficult)
This part involves solving a more complicated problem. Just like in Q7 of the Berkerley Pacman framework, you will be required to create an agent that will eat all of the food (dots) in a maze. Before doing so, however, the agent must eat a Capsule that is present in the maze. Your code should ensure that no food is eaten before the Capsule. You can assume that there is always exactly one Capsule in the maze, and that there will always be at least one path from Pacman’s starting point to the capsule that doesn’t pass through any food.
In order to implement this, you should create a new problem called CapsuleSearchProblem and a new agent called CapsuleSearchAgent. You will also need to implement a suitable capsuleProblemHeuristic. You may choose to implement other helper classes/functions.
You should be able to test your program by running the following code (in one line):
python pacman.py -l capsuleSearch -p CapsuleSearchAgent
-a fn=astar,prob=CapsuleSearchProblem,heuristic=capsuleProblemHeuristic
An agent that eats the capsule then proceeds to eat all of the food on the maze will receive 2 marks. The remaining 2 marks will be based on the performance of your agent (i.e. number of nodes expanded), as in Q7 of the Berkeley problem. Since you are using the A* algorithm, however, the number of node expansions required for each grade will vary.
Indicative marks are shown below for node exapansions on the testing files simpletest.test and corner_tiny_corner.test which are used by the autograder for checking your submission. Note that we will test your submission on different layouts, however this will give you a good guide for comparing the expected performance of your solution:
| simpletest (node expansions) | Marks | corner_tiny_corner (node expansions) | Marks | Total marks |
|---|---|---|---|---|
| < 210 | 2 | < 2185 | 2 | 4 |
| > 210 | 1.75 | > 2185 | 1.75 | 3.5 |
| > 213 | 1.5 | > 3516 | 1.5 | 3 |
| > 644 | 1.25 | > 4558 | 1.25 | 2.5 |
| > 853 | 1 | > 5542 | 1 | 2 |
Implementation:
https://github.com/abhinavcreed13/ai-pacman-project-search/blob/main/searchAgents.py#L545
Marks achieved:
| simpletest (node expansions) | Marks | corner_tiny_corner (node expansions) | Marks | Total marks |
|---|---|---|---|---|
| 65 | 2/2 | 89 | 2/2 | 4/4 |
Cheers!
Leave a comment