cs188 project1实验

博主 8767 2021-10-12

高级人工智能-project 1 实验报告

实验内容:

指引链接:https://inst.eecs.berkeley.edu/~cs188/sp21/project1/

本次实验内容是帮助pacman找到路,这个路包括吃豆,或是到达特定的地方。
下载链接中包含的项目压缩包,解压,配置环境
项目需要编辑的文件:search.py,searchAgents.py
需要参考的文件:pacman.py,game.py,util.py

实验环境:windows10,python3.8.0

现在,pacman的世界只有wall和food,以及一个吃豆人,吃豆人需要从一个位置出发,到达指定goal的位置结束
Q1需要实现一个在吃豆人地图中的dfs算法,填充search.py中的depthFirstSearch function

思路:
本例为实现一个图的dfs,很容易想到用stack,util.py提供了stack的实现。为了让pacman在找路径的时候不走回头路,需要记录pacman访问过的节点,这里用python内置set来记录访问过的节点,set使用hash方法,查找效率高。利用stack的FILO特性,可以优先从深度上访问节点。每次从stack取出一个节点,如果这个节点没有访问过,那么走到这个节点,并且把该节点可以走的子节点加入栈中,再从stack取出一个节点,以此循环,直到找到goal的位置。找到goal以后,返回经过的路径即可。

代码:

def depthFirstSearch(problem):
    current_position = (problem.getStartState(), [])
    possible_nodes = util.Stack()
    visited_nodes = set()
    while not problem.isGoalState(current_position[0]):
        if current_position[0] not in visited_nodes:
            visited_nodes.add(current_position[0])
            children = problem.expand(current_position[0])  # Returns child states, a list of tuple(child, action, stepCost)
            for child in children:
                if child[0] not in visited_nodes:
                    possible_nodes.push((child[0], current_position[1] + [child[1]]))
        current_position = possible_nodes.pop()
        # print("current:", current_position)
    return current_position[1]

Q2需要实现一个在吃豆人地图中的bfs算法,填充search.py中的depthFirstSearch function。

思路:
bfs算法只需要把Q1中的stack改为queue即可。利用queue的FIFO特性,可以优先从广度上访问节点。每次从queue取出一个节点,如果这个节点没有访问过,那么走到这个节点,并且把该节点可以走的子节点加入栈中,再从queue取出一个节点,以此循环,直到找到goal的位置。找到goal以后,返回经过的路径即可。

def breadthFirstSearch(problem):
    current_position = (problem.getStartState(), [])
    possible_nodes = util.Stack()
    visited_nodes = set()
    while not problem.isGoalState(current_position[0]):
        if current_position[0] not in visited_nodes:
            visited_nodes.add(current_position[0])
            children = problem.expand(current_position[0])  # Returns child states, a list of tuple(child, action, stepCost)
            for child in children:
                if child[0] not in visited_nodes:
                    possible_nodes.push((child[0], current_position[1] + [child[1]]))
        current_position = possible_nodes.pop()
        # print("current:", current_position)
    return current_position[1]

Q3需要实现一个在吃豆人地图中的A*搜索算法,填充search.py中的aStarSearch function。
aStarSearch与dfs和bfs参数不同的地方在于多了一个启发式函数heuristic。heuristic用于估计一个状态到下一个状态的代价,容易想到使用小顶堆来实现状态的排列,堆中节点的权重是状态转换的真实cost和heuristic的和。理论上,该和越小,那么从该状态找到goal的时间、空间开销越小。利用小顶堆的特性,每次都从堆顶取cost和heuristic和最小的状态,如果状态所在节点没访问过,那么访问该节点,并找到节点的子节点们,子节点们的位置和代价组成的特定数据结构添加到堆中,子节点加入堆时的权重为:从初始状态到父节点状态的代价+父节点状态到子节点状态的代价+heuristic(child)。循环取堆顶状态,直到找到goal state。
代码:

def aStarSearch(problem, heuristic=nullHeuristic):
    current_position = (problem.getStartState(), [], 0)
    possible_nodes = util.PriorityQueue()
    visited_nodes = set()
    while not problem.isGoalState(current_position[0]):
        if current_position[0] not in visited_nodes:
            visited_nodes.add(current_position[0])
            children = problem.expand(current_position[0])  # Returns child states, a list of tuple(child, action, stepCost)
            for child in children:
                if child[0] not in visited_nodes:
                    cost = current_position[2] + child[2]
                    possible_nodes.push(
                        (child[0], current_position[1] + [child[1]], cost),
                        cost + heuristic(child[0], problem)
                    )
        current_position = possible_nodes.pop()
        # print("current:", current_position)
    return current_position[1]

Question 4 (3 points): Finding All the Corners

Q4需要我们重新定义problem,Q1~Q3的pacman都是到达一个具有food的特定位置,Q4中pacman需要到达map的4个角落:(1,1),(1,top),(right,1),(right,top)。我们需要编写searchAgents.py中的Class CornersProblem 。

思路:
首先需要重新定义pacman的状态state,这里使用state(position, visited_nodes())来表示。状态的第一个参数position表示pacman在map中的位置,为一个类似(x,y)的坐标,第二个参数visited_nodes是一个python tuple,其包括当前路径已经访问过的角落节点的所有坐标。所以,目标状态goal就是visited_nodes中包含所有4个角落坐标。

代码:

class CornersProblem(search.SearchProblem):

    def __init__(self, startingGameState):
        """
        Stores the walls, pacman's starting position and corners.
        """
        self.walls = startingGameState.getWalls()
        self.startingPosition = startingGameState.getPacmanPosition()
        top, right = self.walls.height-2, self.walls.width-2
        self.corners = ((1,1), (1,top), (right, 1), (right, top))
        for corner in self.corners:
            if not startingGameState.hasFood(*corner):
                print('Warning: no food in corner ' + str(corner))
        self._expanded = 0 # DO NOT CHANGE; Number of search nodes expanded
        # Please add any code here which you would like to use
        # in initializing the problem
        "*** YOUR CODE HERE ***"

    def getStartState(self):
        """
        Returns the start state (in your state space, not the full Pacman state
        space)
        """
        "*** YOUR CODE HERE ***"
        return self.startingPosition, tuple()  # set contains visited corner

    def isGoalState(self, state):
        """
        Returns whether this search state is a goal state of the problem.
        """
        "*** YOUR CODE HERE ***"
        return len(state[1]) == 4

    def expand(self, state):
        """
        Returns child states, the actions they require, and a cost of 1.

         As noted in search.py:
            For a given state, this should return a list of triples, (child,
            action, stepCost), where 'child' is a child to the current
            state, 'action' is the action required to get there, and 'stepCost'
            is the incremental cost of expanding to that child
        """

        children = []
        for action in self.getActions(state):
            # Add a child state to the child list if the action is legal
            # You should call getActions, getActionCost, and getNextState.
            "*** YOUR CODE HERE ***"
            next_state = self.getNextState(state, action)
            next_state_cost = self.getActionCost(state, action, next_state)
            children.append((next_state, action, next_state_cost))

        self._expanded += 1 # DO NOT CHANGE
        return children

    ## 获取可行方向
    def getActions(self, state):
        possible_directions = [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]
        valid_actions_from_state = []
        for action in possible_directions:
            x, y = state[0]
            dx, dy = Actions.directionToVector(action)
            nextx, nexty = int(x + dx), int(y + dy)
            if not self.walls[nextx][nexty]:
                valid_actions_from_state.append(action)
        return valid_actions_from_state

    def getActionCost(self, state, action, next_state):
        assert next_state == self.getNextState(state, action), (
            "Invalid next state passed to getActionCost().")
        return 1

    def getNextState(self, state, action):
        assert action in self.getActions(state), (
            "Invalid action passed to getActionCost().")
        x, y = state[0]
        dx, dy = Actions.directionToVector(action)
        nextx, nexty = int(x + dx), int(y + dy)
        "*** YOUR CODE HERE ***"
        next_pos = (nextx, nexty)
        st = list(state[1])
        if (next_pos in self.corners) and (next_pos not in st):
            st.append(next_pos)
        return next_pos, tuple(st)

    def getCostOfActionSequence(self, actions):
        """
        Returns the cost of a particular sequence of actions.  If those actions
        include an illegal move, return 999999.  This is implemented for you.
        """
        if actions == None: return 999999
        x,y= self.startingPosition
        for action in actions:
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]: return 999999
        return len(actions)

部分函数实现逻辑:

  • getStartState获取初始状态,返回元祖,第一个参数为初始坐标,第二个参数为空元祖
  • isGoalState获取是否为目标状态,当state[1]的长度为4时,即访问过所有角落时,达到目标状态,返回true;否则返回false
  • expand返回子节点状态,通过self.getActions获取可行方向action,通过self.getNextState(state, action)获取走该方向以后的状态,通过self.getActionCost(state, action, next_state)获取状态转换的开销(默认为1)
  • getNextState获取下一个状态,nxet_state状态的坐标容易获取,第二个参数需要检测坐标是否在角落坐标中,如果在,就把nxet_state状态的坐标加入元祖中

Question 5 (3 points): Corners Problem: Heuristic

Q5需要为Q4定义的problem设计一个启发式函数
思路:
Q4定义的problem中,当处于某个state时,可能有多个未访问corner,使用state的坐标计算到各个未访问corner的manhattan距离,选用最大的manhattan距离作为启发式函数值,理由是如果因为到达某个状态导致到某个corner的距离更远,那么先访问该状态的权重应该更低,代价应该更大,使得该状态在小顶堆中的位置尽可能深,这样该状态被优先访问的概率降低,也许能够先搜索到更优路线。

def cornersHeuristic(state, problem):
    corners = problem.corners # These are the corner coordinates
    walls = problem.walls # These are the walls of the maze, as a Grid (game.py)
    "*** YOUR CODE HERE ***"
    # def manhattanHeuristic(position, problem, info={})
    visited_corner = state[1]
    max_dist = 0
    # count = 0
    for corner in corners:
        if corner not in visited_corner:  # corner which is not visit
            #count = count + 1
            max_dist = max(max_dist, util.manhattanDistance(state[0], corner))
    #if count:
    #    return max_dist * 1.0 / count
    #else:
    #    return 0
    return max_dist

Question 6 (4 points): Eating All The Dots

Q6需要为一个新的problem(FoodSearchProblem)设计启发式函数,该problem定义与上述不同的地方在于,map中有多个坐标点上存在food,pacman需要将food吃完,达到目的。problem定义状态为元祖(position, foodGrid),第一个参数为pacman所在坐标,第二个参数为pacman所在map大小的网格(矩阵),矩阵每一个元素为true or false,true表示该位置上还有food,false表示该位置没有food。于是goal state即为state中参数二全为false。

思路:
当处于某个state时,此时可能有多个未吃的food存在,我们遍历所有的food位置,计算food坐标到当前状态坐标的maze distance(利用已有函数mazeDistance),选取最大的maze distance作为启发式函数的计算值。理由与Q5相似。如果因为到达某个状态导致到某个距离最远的food的距离更远,那么先访问该状态的权重应该更低,代价应该更大,使得该状态在小顶堆中的位置尽可能深,这样该状态被优先访问的概率降低,也许能够先搜索到更优路线。

代码:

def foodHeuristic(state, problem):
    position, foodGrid = state
    "*** YOUR CODE HERE ***"
    food_list = foodGrid.asList()
    max_dis = 0
    for food_pos in food_list:
        dis = mazeDistance(position, food_pos, problem.startingGameState)
        if dis > max_dis:
            max_dis = dis
    return max_dis

Q7需要为一个ClosestDotSearchAgent寻找到次优解,agent会指导pacman在一张具有多个food的map中行走,指导方法是pacman每次先去到最近的food处,然后再去下一个最近的food处,直到把所有food吃完。

思路:
首先需要重新定义problem,如何每次都先去找到距离最近的food:使用bfs,因为bfs从状态所在位置逐层扩散产生路径,距离最近的food一定最先被找到。于是修改AnyFoodSearchProblem中的isGoalState函数:

    def isGoalState(self, state):
        x,y = state

        "*** YOUR CODE HERE ***"
        return (x,y) in self.food.asList()

当访问到的坐标(x,y)位于food列表中某一个时,都达到目标状态,然后用bfs依次去找到目标状态(即找到最近food):

def findPathToClosestDot(self, gameState):
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"
        return search.bfs(problem)

实验结果

运行autograde,使用一些测试案例测试上述7个question的代码

Question q1
===========
*** PASS: test_cases/q1/graph_backtrack.test
*** 	solution:		['1:A->C', '0:C->G']
*** 	expanded_states:	['A', 'D', 'C']
*** PASS: test_cases/q1/graph_bfs_vs_dfs.test
*** 	solution:		['2:A->D', '0:D->G']
*** 	expanded_states:	['A', 'D']
*** PASS: test_cases/q1/graph_infinite.test
*** 	solution:		['0:A->B', '1:B->C', '1:C->G']
*** 	expanded_states:	['A', 'B', 'C']
*** PASS: test_cases/q1/graph_manypaths.test
*** 	solution:		['2:A->B2', '0:B2->C', '0:C->D', '2:D->E2', '0:E2->F', '0:F->G']
*** 	expanded_states:	['A', 'B2', 'C', 'D', 'E2', 'F']
*** PASS: test_cases/q1/pacman_1.test
*** 	pacman layout:		mediumMaze
*** 	solution length: 130
*** 	nodes expanded:		146

### Question q1: 4/4 ###


Question q2
===========
*** PASS: test_cases/q2/graph_backtrack.test
*** 	solution:		['1:A->C', '0:C->G']
*** 	expanded_states:	['A', 'B', 'C', 'D']
*** PASS: test_cases/q2/graph_bfs_vs_dfs.test
*** 	solution:		['1:A->G']
*** 	expanded_states:	['A', 'B']
*** PASS: test_cases/q2/graph_infinite.test
*** 	solution:		['0:A->B', '1:B->C', '1:C->G']
*** 	expanded_states:	['A', 'B', 'C']
*** PASS: test_cases/q2/graph_manypaths.test
*** 	solution:		['1:A->C', '0:C->D', '1:D->F', '0:F->G']
*** 	expanded_states:	['A', 'B1', 'C', 'B2', 'D', 'E1', 'F', 'E2']
*** PASS: test_cases/q2/pacman_1.test
*** 	pacman layout:		mediumMaze
*** 	solution length: 68
*** 	nodes expanded:		269

### Question q2: 4/4 ###


Question q3
===========
*** PASS: test_cases/q3/astar_0.test
*** 	solution:		['Right', 'Down', 'Down']
*** 	expanded_states:	['A', 'B', 'D', 'C', 'G']
*** PASS: test_cases/q3/astar_1_graph_heuristic.test
*** 	solution:		['0', '0', '2']
*** 	expanded_states:	['S', 'A', 'D', 'C']
*** PASS: test_cases/q3/astar_2_manhattan.test
*** 	pacman layout:		mediumMaze
*** 	solution length: 68
*** 	nodes expanded:		221
*** PASS: test_cases/q3/astar_3_goalAtDequeue.test
*** 	solution:		['1:A->B', '0:B->C', '0:C->G']
*** 	expanded_states:	['A', 'B', 'C']
*** PASS: test_cases/q3/graph_backtrack.test
*** 	solution:		['1:A->C', '0:C->G']
*** 	expanded_states:	['A', 'B', 'C', 'D']
*** PASS: test_cases/q3/graph_manypaths.test
*** 	solution:		['1:A->C', '0:C->D', '1:D->F', '0:F->G']
*** 	expanded_states:	['A', 'B1', 'C', 'B2', 'D', 'E1', 'F', 'E2']

### Question q3: 4/4 ###


Question q4
===========
*** PASS: test_cases/q4/corner_tiny_corner.test
*** 	pacman layout:		tinyCorner
*** 	solution length:		28

### Question q4: 3/3 ###


Question q5
===========
*** PASS: heuristic value less than true cost at start state
*** PASS: heuristic value less than true cost at start state
*** PASS: heuristic value less than true cost at start state
path: ['North', 'East', 'East', 'East', 'East', 'North', 'North', 'West', 'West', 'West', 'West', 'West', 'West', 'South', 'South', 'South', 'West', 'West', 'North', 'East', 'East', 'North', 'North', 'North', 'North', 'East', 'East', 'North', 'North', 'North', 'North', 'North', 'North', 'West', 'West', 'West', 'West', 'South', 'South', 'East', 'East', 'East', 'East', 'South', 'South', 'South', 'South', 'South', 'South', 'East', 'East', 'East', 'East', 'East', 'East', 'South', 'South', 'East', 'East', 'East', 'East', 'East', 'North', 'North', 'East', 'East', 'North', 'North', 'East', 'East', 'North', 'North', 'East', 'East', 'East', 'East', 'South', 'South', 'South', 'South', 'East', 'East', 'North', 'North', 'East', 'East', 'South', 'South', 'South', 'South', 'South', 'North', 'North', 'North', 'North', 'North', 'North', 'North', 'West', 'West', 'North', 'North', 'East', 'East', 'North', 'North']
path length: 106
*** FAIL: Heuristic resulted in expansion of 1357 nodes

### Question q5: 2/3 ###


Question q6
===========
*** PASS: test_cases/q6/food_heuristic_1.test
*** PASS: test_cases/q6/food_heuristic_10.test
*** PASS: test_cases/q6/food_heuristic_11.test
*** PASS: test_cases/q6/food_heuristic_12.test
*** PASS: test_cases/q6/food_heuristic_13.test
*** PASS: test_cases/q6/food_heuristic_14.test
*** PASS: test_cases/q6/food_heuristic_15.test
*** PASS: test_cases/q6/food_heuristic_16.test
*** PASS: test_cases/q6/food_heuristic_17.test
*** PASS: test_cases/q6/food_heuristic_2.test
*** PASS: test_cases/q6/food_heuristic_3.test
*** PASS: test_cases/q6/food_heuristic_4.test
*** PASS: test_cases/q6/food_heuristic_5.test
*** PASS: test_cases/q6/food_heuristic_6.test
*** PASS: test_cases/q6/food_heuristic_7.test
*** PASS: test_cases/q6/food_heuristic_8.test
*** PASS: test_cases/q6/food_heuristic_9.test
*** PASS: test_cases/q6/food_heuristic_grade_tricky.test
*** 	expanded nodes: 4137
*** 	thresholds: [15000, 12000, 9000, 7000]

### Question q6: 5/4 ###


Question q7
===========
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_1.test
*** 	pacman layout:		Test 1
*** 	solution length:		1
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_10.test
*** 	pacman layout:		Test 10
*** 	solution length:		1
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_11.test
*** 	pacman layout:		Test 11
*** 	solution length:		2
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_12.test
*** 	pacman layout:		Test 12
*** 	solution length:		3
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_13.test
*** 	pacman layout:		Test 13
*** 	solution length:		1
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_2.test
*** 	pacman layout:		Test 2
*** 	solution length:		1
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_3.test
*** 	pacman layout:		Test 3
*** 	solution length:		1
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_4.test
*** 	pacman layout:		Test 4
*** 	solution length:		3
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_5.test
*** 	pacman layout:		Test 5
*** 	solution length:		1
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_6.test
*** 	pacman layout:		Test 6
*** 	solution length:		2
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_7.test
*** 	pacman layout:		Test 7
*** 	solution length:		1
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_8.test
*** 	pacman layout:		Test 8
*** 	solution length:		1
[SearchAgent] using function depthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
*** PASS: test_cases/q7/closest_dot_9.test
*** 	pacman layout:		Test 9
*** 	solution length:		1

### Question q7: 3/3 ###


Finished at 21:05:01

Provisional grades
==================
Question q1: 4/4
Question q2: 4/4
Question q3: 4/4
Question q4: 3/3
Question q5: 2/3
Question q6: 5/4
Question q7: 3/3
------------------
Total: 25/25

分析实验结果,Q5的第三个test没有通过,我这里expand的节点为1357个,通过该test需要expand nodes在1200以下,我将最大manhattan距离改为到未访问节点的manhattan距离均值,仍未通过test。经与同学讨论,同学使用manhattan距离的expand nodes均在1200以下。因个人能力所限,查代码也没有查出原因。