高级人工智能-project 1 实验报告
- 高级人工智能-project 1 实验报告
- 实验内容：
- Question 1 (4 points): Finding a Fixed Food Dot using Depth First Search
- Question 2 (4 points): Breadth First Search
- Question 3 (4 points): A* search
- Question 4 (3 points): Finding All the Corners
- Question 5 (3 points): Corners Problem: Heuristic
- Question 6 (4 points): Eating All The Dots
- Question 7 (3 points): Suboptimal Search
- 实验结果
- 实验内容：
实验内容：
指引链接：https://inst.eecs.berkeley.edu/~cs188/sp21/project1/
本次实验内容是帮助pacman找到路，这个路包括吃豆，或是到达特定的地方。
下载链接中包含的项目压缩包，解压，配置环境
项目需要编辑的文件：search.py，searchAgents.py
需要参考的文件：pacman.py，game.py，util.py
实验环境：windows10，python3.8.0
Question 1 (4 points): Finding a Fixed Food Dot using Depth First Search
现在，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]
Question 2 (4 points): Breadth First Search
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]
Question 3 (4 points): A* search
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
Question 7 (3 points): Suboptimal Search
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以下。因个人能力所限，查代码也没有查出原因。