Artificial Intelligence - UC Berkeley’s Project Search

10 minute read

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

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()

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()

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()

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