Project 1: Search

Due: 2025.09.21.

---

---

介绍

在这个项目中，你的吃豆人智能体将在他的迷宫世界中寻找路径，包括到达一个特定的位置，以及有效地收集食物。你需要结合我们课堂所学的知识，实现 depthFirstSearch、uniformCostSearch等通用搜索算法及启发式函数，并将其应用于吃豆人场景。

本次作业所需的文件为：Lab1.zip

你需要编辑的文件

文件	作用
search.py	包含所有的搜索算法
searchAgents.py	包含所有基于搜索的智能体

你或许需要查看的文件

文件	作用
pacman.py	运行吃豆人游戏的主文件。这个文件描述了一个Pacman GameState类型
game.py	这是吃豆人游戏运行的逻辑。该文件描述了几个支持类型，如AgentState、Agent、Direction和Grid
util.py	用于实现搜索算法的有用数据结构

你无需关心的文件

文件	作用
graphicsDisplay.py	Graphics for Pacman
graphicsUtils.py	Support for Pacman graphics
textDisplay.py	ASCII graphics for Pacman
ghostAgents.py	Agents to control ghosts
keyboardAgents.py	Keyboard interfaces to control Pacman
layout.py	Code for reading layout files and storing their content
testParser.py	Parses autograder test and solution files
testClasses.py	General autograding test classes
searchTestClasses.py	Project 1 specific autograding test classes

熟悉吃豆人

吃豆人生活在一个明亮的蓝色世界里，有蜿蜒的走廊和美味的圆形食物。在这个世界高效地游走将是吃豆人掌握自己领域的第一步。

searchAgents.py中包含了一个最简单的智能体称为GoWestAgent，它在吃豆人世界中无脑地向西走，偶尔可以赢。运行指令如下：

python pacman.py --layout testMaze --pacman GoWestAgent

注意：

• --layout参数指定了一个游戏地形，testMaze是一个笔直的形状。
• --pacman参数指定了运行何种智能体，GoWestAgent即最简单的智能体。

如果地形需要智能体转向，那么GoWestAgent就会卡住，例如：

python pacman.py --layout tinyMaze --pacman GoWestAgent

如果智能体卡住，你可以使用组合键Ctrl + C退出程序。

此外，pacman.py支持很多可选参数，你可以列出它所支持的参数，通过运行：

python pacman.py -h

解决问题

熟悉完吃豆人世界之后，你需要结合课堂提到的搜索算法及启发函数设计，完成下面的5个问题。

在searchAgents.py文件中，你可以找到SearchAgent这个类，该类负责在吃豆人世界中规划一条路径，并一步一步地执行，它的框架已经被完整地实现了，无需你进行修改。但是规划过程中所需要的搜索算法没有被实现，这正是你要做的事情。请你在search.py中实现以下4种搜索算法。

在此之前，你可以运行以下命令测试SearchAgent是否能够正常运行：

python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch

所有搜索函数最终返回返回将agent从起点引导到终点的action列表。

结合我们课件中介绍的搜索算法及实现方式，你实现的搜索相关函数可以借助util.py中提供的Stack、Queue和PriorityQueue数据结构。

注意，在实现你的搜索算法时，避免扩展任何已经访问过的状态,否则可能会影响我们的评分。

一个示例：广度优先搜索

目标：使用广度优先搜索（BFS）找到一个固定的食物点。填充search.py中有关广度优先搜索的部分：

def breadthFirstSearch(problem): 
    """Search the shallowest nodes in the search tree first.""" 
    "*** YOUR CODE HERE ***" 
    # 采用utils提供的数据结构，构建一个队列 
    Frontier = util.Queue() 
    # 创建已访问节点集合 
    Visited = [] 
    # 将(初始节点,空动作序列)入队 
    Frontier.push( (problem.getStartState(), []) ) 
    # 将初始节点标记为已访问节点 
    Visited.append( problem.getStartState() ) 
    # 判断队列非空 
    while Frontier.isEmpty() == 0: 
        # 从队列中弹出一个状态和动作序列 
        state, actions = Frontier.pop() 
        # 判断是否为目标状态，若是则返回到达该状态的累计动作序列 
        if problem.isGoalState(state): 
            return actions  
        # 遍历所有后继状态 
        for next in problem.getSuccessors(state): 
            # 新的后继状态 
            n_state = next[0] 
            # 新的action 
            n_direction = next[1] 
            # 若该状态没有访问过 
            if n_state not in Visited: 
                # 计算到该状态的动作序列，入队 
                Frontier.push( (n_state, actions + [n_direction]) ) 
                Visited.append( n_state )

测试代码如下：

python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

函数解释

函数名	参数	返回值	函数介绍
problem.getStartState()	None	Tuple[(x, y)]	返回开始位置(x,y)
problem.isGoalState()	state	bool	判断位置是否为终点
problem.getSuccessors()	state	List[ (dst, action, cost) ]	返回状态state的后继状态（边）列表，每条边包含下一个状态（位置）dst，到达该状态（位置）的动作action，边权cost
problem.getCostOfActions()	List[ action ]	int	返回执行一段行为序列的所需的代价，序列必须使智能体合法移动

注意：

• state是一个元组(int, int)，即当前的位置坐标。
• 为了最终得到从起点到终点的action列表，你需要将中间状态（位置），以及从起点到达该状态（位置）的action列表等信息共同存储到算法对应的数据结构中，参考示例代码（breadthFirstSearch）。

题目1：深度优先搜索

目标：使用深度优先算法（DFS）找到一个固定的食物点。

填充search.py中有关深度优先搜索的部分:

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()) ) 
    """ 
    "*** YOUR CODE HERE ***" 
    util.raiseNotDefined()

请使用util中的数据结构实现DFS，而不要使用递归。

一旦你编写完，你可以运行以下命令，在不同难度的地图上验证你的实现：

python pacman.py -l tinyMaze -p SearchAgent

python pacman.py -l mediumMaze -p SearchAgent

python pacman.py -l bigMaze -z .5 -p SearchAgent

题目2：一致代价搜索

虽然BFS会找到通往目标的最少行动路径，但我们可能想要找到其他意义上的“最佳”路径。

比如，尝试mediumDottedMaze的游戏地形，上面的方法就行不通了：

python pacman.py -l mediumDottedMaze -p SearchAgent

通过改变成本函数，我们可以鼓励吃豆人寻找不同的路径。例如，我们可以对幽灵出没地区的危险步骤收取更高的代价，或对食物丰富地区的步骤收取更低的代价，理性的agent应该相应地调整其行为。

请在search.py中的uniformCostSearch函数中实现一致代价搜索（UCS）算法。

同样地，你应该在util.py查找一些可能有用的数据结构。

填充search.py中有关一致代价搜索的部分：

def uniformCostSearch(problem): 
    """Search the node of least total cost first.""" 
    "*** YOUR CODE HERE ***" 
    util.raiseNotDefined()

完成算法后，使用如下指令进行测试。现在，你应该在以下三个游戏地形中观察到成功的行为，其中下面的智能体都是采用UCS算法的智能体，仅在它们使用的成本函数上有所不同（智能体和成本函数已经为你写好了）。

python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs

python pacman.py -l mediumDottedMaze -p StayEastSearchAgent

python pacman.py -l mediumScaryMaze -p StayWestSearchAgent

题目3：迭代加深的深度优先搜索

迭代加深的深度优先搜索兼容了BFS和DFS的优势，

请你填充填充search.py中的iterativeDeepeningSearch相关部分。在这里，我们给出了一种可能的实现方式，你只需要填充其中的核心逻辑实现函数depthLimitedSearch（提示：除了中间状态（位置），以及从起点到达该状态（位置）的action列表的信息，你还需要传入当前状态对应的深度到你的数据结构中）。

你也可以自己从零开始实现iterativeDeepeningSearch。

def iterativeDeepeningSearch(problem): 
    """ 
    Search using iterative deepening search. 
    """ 
    def depthLimitedSearch(problem, limit): 
        """ 
        Helper function to perform depth-limited search with a given depth limit. 
        Returns the solution path if found within the limit, None otherwise. 
        """ 
        "*** YOUR CODE HERE ***" 
    depth_limit = 0 
    while True: 
        result = depthLimitedSearch(problem, depth_limit) 
        if result is not None: 
            return result 
        depth_limit += 1 
        if depth_limit > MAX_DEPTH:  # maximum 
            break 
    util.raiseNotDefined()

完成算法后，使用如下指令进行测试。

python pacman.py -l mediumMaze -p SearchAgent -a fn=iter

题目4：A*算法

def aStarSearch(problem, heuristic=nullHeuristic): 
    """Search the node that has the lowest combined cost and heuristic first.""" 
    "*** YOUR CODE HERE ***" 
    util.raiseNotDefined()

A*接收一个启发式函数作为参数。这里启发式函数的函数接收两个参数:搜索问题中的状态（主要参数）和问题本身（用于访问一些信息）。search.py中的nullHeuristic是一个平凡的启发式函数例子。

你可以使用我们已经给出的Manhattan distance heuristic（在searchAgents.py中已经实现为Manhattan heuristic）在最初的问题上测试你的A*实现，即通过迷宫找到到达固定位置的路径。

完成算法后，使用如下指令进行测试：

python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic

题目5：启发函数设计

请先确保你已经完成A*算法再完成本题

本题目涉及的getStartState，isGoalState和getSuccessors函数与上面的问题略有不同。为了方便，我们已在searchAgents.py的CornersProblem类中给出了具体的实现方式，你可以仔细阅读并利用其更好地解决本问题。

运行下面的指令，这是我们要解决的cornersproblem。你可以看到当启发函数恒为0时，模型需要较多的步数才能完成游戏。

python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5

实现一个非平凡一致性启发函数，即完成searchAgents.py的cornersHeuristic。

def cornersHeuristic(state, problem): 
    """ 
    A heuristic for the CornersProblem that you defined. 
    state:   The current search state 
             (a data structure you chose in your search problem) 
    problem: The CornersProblem instance for this layout. 
    This function should always return a number that is a lower bound on the 
    shortest path from the state to a goal of the problem; i.e.  it should be 
    admissible (as well as consistent). 
    """ 
    corners = problem.corners # These are the corner coordinates 
    walls = problem.walls # These are the walls of the maze, as a Grid (game.py) 
    node = state[0] 
    Visited_Corners = state[1] 
    h_sum = 0 
    "*** YOUR CODE HERE ***" 
    return h_sum # Default to trivial solution

完成算法后，再次运行如下代码进行验证：

python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5

你应该观察到所需步数小于原先的。请注意，步数可能会作为本题的评分标准之一。

注意：你的启发函数必须是非平凡的非负的一致的启发函数才能得到所有分数。确保你的启发函数给每个目标状态评估的值都返回0，并且永远不会返回负值。

代码提交与评分

你只需要填写search.py和searchAgents.py的部分内容。最终，你只需要打包提交这两个文件。请注意，不要修改文件内其它无关的部分，否则可能无法正常获得本次项目的分数。

请各位同学将第一次实践作业上传至NJU_box_Project1, 提交的压缩包以“学号+姓名”的格式命名。

学术诚信

我们会将你的代码与课堂上其他提交的代码进行逻辑查重。如果你拷贝了别人的代码，并做一些微小的修改，我们会很容易发现，请不要尝试。我们相信你们会独立完成作业。

致谢

本次项目相关代码部分基于UC Berkeley CS188改写，项目文档部分基于北京大学《人工智能引论》课程，所有使用及改写均遵循相关协议。感谢他们为社区做出的贡献。