这是EECS492课程2024年秋季作业1的相关内容，包括作业截止日期（2024年9月27日晚上11:59）、提交指南（需提交书面部分的PDF和完成的Agent.py文件到Gradescope，注意相关政策和要求）、评分政策（可在成绩公布后一周内提交重新评分请求）。作业内容包括书面部分（50分）和编程部分（50分），书面部分涵盖设计agents（如tic – tac – toe agent的PEAS描述和环境特征）、搜索相关问题（如不同搜索方法下节点的扩展顺序、砖排序机器的搜索算法设计、启发式函数相关问题、爬山算法相关问题）；编程部分需使用Python完成Agent.py文件，实现特定的搜索算法（BFS、DFS、UCS、A – Star）来搜索迷宫，迷宫可能有多个目标，需修改启发式为到最近目标的欧几里得距离，并完成相关函数。
EECS 492 – 作业1（2024年秋季）
截止日期：2024年9月27日晚上11:59
2024年9月17日
后勤
提交指南
重要提示：您必须仔细阅读教学大纲中关于作业的政策。它讨论了什么算作迟到以及迟到将如何处罚。请确保您已阅读并理解学术诚信部分，包括关于协作和使用生成式AI的部分。生成式AI部分还包括一个示例引用和解释的链接。您将对遵守这些政策负责，违规行为将报告给荣誉委员会。 本次作业的截止日期为2024年9月27日晚上11:59。提交使用Gradescope进行跟踪。书面部分和编程部分将分别评分和处罚。请注意，您对已在Gradescope上提交的作业所做的任何更改都算作重新提交。 您必须向Gradescope提交以下文件（请注意，有两个单独的Gradescope提交）： 1. 包含书面部分解决方案的清晰可读的PDF。您可以手写解决方案，使用平板电脑，或在LATEX中排版解决方案。我们只要求您使其易于阅读，不要过于冗长，以便评分者不会难以理解您的写作。您必须单独将书面部分提交到Gradescope。 2. 完成的Agent.py文件到编程部分。
评分政策
重新评分请求必须在项目成绩公布后的一周内提交给Gradescope。后期的重新评分请求将不被接受。我们将提供解决方案以及使用的确切评分标准。
1 书面[50分]
1.1 设计agents[5.5分]
井字棋是一种两个玩家轮流在三乘三的网格中用X或O标记空格的游戏。游戏的目标是第一个在水平、垂直或对角线上放置三个自己的标记（见图1）。
图1：一场井字棋游戏，O玩家获胜，因为它在对角线上有三个标记。 您现在的任务是为井字棋agent开发一种AI算法。该agent是一个可以在纸上用钢笔与另一个agent（人类或机器人）对战的机器人。该agent必须能够： • 检测标记是X还是O • 在九个网格中的一个中绘制标记 • 检测纸上的空网格和已存在的标记 • 使用此信息确定它是否赢得、输掉或平局 请注意，该agent不仅仅玩一次，而是一个应该能够根据需要多次玩多个游戏的机器人。现在，回答以下问题 – 请注意，其中一些情况可能不明确，因此请证明您的答案并明确说明任何假设 （a）为任务环境创建PEAS描述，其中任务环境包括agent玩的所有游戏。 （b）确定环境的特征，并简要说明为什么您以这种方式描述环境 提醒一下，环境的特征如下： • 完全可观察与部分可观察 • 单agent与多agent • 确定性与非确定性 • 情节性与连续性 • 静态与动态 • 离散与连续 • 已知与未知
1.2 实践搜索[18分]
考虑图2所示的搜索树，包括节点A到K。节点A的状态是我们的初始状态（显示为橙色）。节点G和J共享相同的状态，并且是有效的目标（显示为蓝色）。边旁边的标签是与该边的顶点之间的路径相关联的成本。 假设当一个节点被扩展时，它的子节点将以这样的顺序添加到前沿中，即当节点被弹出时，它们将从左到右被访问。也就是说，对于广度优先搜索，最左边分支的子节点首先被添加。对于深度优先搜索，最右边分支的子节点首先被添加（参见R & N教科书中的图3.11）。 对于使用优先级队列的前沿，具有相同优先级（路径成本、启发式值或路径成本和启发式值的总和）的节点将按字母顺序弹出。例如，如果节点B和节点C具有相同的优先级，则节点B首先弹出，然后是节点C。
图2：搜索树，带路径成本 | ℎ() | | —- | | A 3 | | B 4 | | C 7 | | D 5 | | E 15 | | F 14 | | G 0 | | H 1 | | I 6 | | J 0 | | K 8 |
图3：状态的启发式值 为您提供了一个可接受的启发式函数，如图3所示，它给出了每个节点状态的启发式函数的值。对于以下搜索方法，列出从前沿扩展节点的顺序（即，从开始到达到目标为止，您调用EXPAND(node)的所有节点）。请展示您的工作以获得部分学分。 （a）广度优先搜索 （b）深度优先搜索。在从前沿弹出并调用Ex - pand(node)之前进行目标测试。 （c）迭代深化。请参阅更新的讲座幻灯片以获取精确的伪代码。 （d）统一成本搜索 （e）使用提供的启发式函数的贪婪最佳优先搜索 （f）使用提供的启发式函数的A – Star搜索
1.3 砖块排序机器[8分]
一家砖块工厂生产不同风格的砖块，他们希望将这些砖块装在一批板条箱中运出，每个板条箱只包含一种类型的砖块；然而，现在每个板条箱都是随机装载的。工厂刚刚安装了一个机器人手臂，安装在板条箱存储区上方的线性轨道上，他们想使用它来对板条箱进行排序。板条箱都排成一行，手臂可以采取三种动作： 1. 向左或向右移动一个板条箱的距离， 2. 从下面的板条箱中抓取特定类型的砖块， 3. 将其持有的砖块放置到下面的板条箱中。 请注意，手臂一次只能持有一块砖块！ 您的工作是设计一种搜索算法，该算法将找到导致每个板条箱只包含一种砖块的最短动作序列。幸运的是，您提前知道每个板条箱的初始内容。为以下每个元素提供清晰详细的描述。您不需要提供实现细节，除非您想（例如，您不需要说“我会使用哈希表来”），但您的描述应该包含足够的细节，以表明您考虑了算法可能的实现方式。 （a）状态空间：定义状态空间的离散信息片段。换句话说，当考虑特定状态时，您需要知道的所有事情是什么？ （b）动作：根据您的状态表示，三个动作中的每一个如何从探索的状态生成后继状态。 （c）目标测试：根据您的状态表示，一个状态成为目标状态必须满足什么条件。 （d）搜索算法：哪种（非启发式）搜索算法最适合此任务，以及定义其前沿的数据结构。证明您的选择。考虑空间和时间复杂度。提示：考虑您的状态空间的结构以及到达集是否有益。
1.4 启发式[9分]
（a）骑士是一种国际象棋棋子，以“L”形移动。一个骑士移动是垂直两个方格和水平一个方格，或水平两个方格和垂直一个方格。每个骑士移动的成本为1。您给定一个国际象棋棋盘，有一个起始方格和一个结束方格，您的任务是找到骑士从起始方格到结束方格所需的最少骑士移动次数。解释为什么曼哈顿距离在这里对于A – Star不是一个一致的启发式，并开发您自己的一致启发式。请证明您提出的启发式是一致的。
图4：有效的骑士移动，由小黑方块表示 （b）考虑一个具有单个目标的网格世界，允许的移动是LEFT、RIGHT、UP和DOWN（您无法对角线移动）。每个移动LEFT、RIGHT、UP和DOWN的成本为1。让h1(s)是从状态s到目标的曼哈顿距离，让h2(s)是从s到目标的欧几里得距离。您还有以下函数h3： 函数h3()：
← 一个从1到10的随机数，包括1和10；
如果 ≤ 3 则
返回 `h1(s)`；
结束
返回 `h2(s)`；h3是一个一致的启发式吗？证明您的答案。
1.5 爬山[9.5分]
您的朋友用一个两位数字的PIN码保护他们的每个文件，但由于他们总是忘记，他们决定实现一个使用爬山算法自动找到它的AI agent。每个PIN由两个整数i1和i2组成，每个整数可以取值从0到9。他们实现了以下agent – agent自动提交一个候选PIN，如果正确，文件将解锁。如果猜测的PIN不正确，agent将收到一个衡量猜测有多好的分数。如果输入的两个数字是i1和i2，则返回的分数是h(i1, i2) = 11 + |i1 - 1| + 11 + |i2 - 2| 然后，agent使用爬山算法尝试找到PIN。该算法通过创建所有相差一个数字的猜测来生成邻居。换句话说，如果当前状态是(i1, i2)，则生成的邻居是(i1 - 1, i2)，(i1 + 1, i2)，(i1, i2 - 1)和(i1, i2 + 1)。该算法不会生成任何超出有效（0,0）到（9,9）范围的状态。在h值出现平局的情况下，选择值最低的状态。 （a）假设PIN的初始猜测是（5,5），实际PIN是（1,2）。列出爬山算法采取的步骤，直到它终止。如果它没有终止，请解释原因。 （b）这个算法是否保证找到正确的PIN码？解释您的答案。您可以使用像GeoGebra这样的绘图工具来帮助您解决这个问题。 （c）现在假设算法被硬编码为在n步后终止。如果 （i）n = 10 （ii）n = 20 您对（b）部分的答案是否会改变 （d）假设我们稍微修改一下启发式，使其现在为：h(i1, i2) = |11 + (i1 - 1) + 11 + (i2 - 2)| 这个版本的爬山搜索是否保证找到解决方案？解释您的答案。
2 编程[50分]
2.1 设置
本课程的所有编程作业都使用Python。如果您是Python新手或不太有经验，请来到办公时间；我们很乐意帮助您！我们还建议您查看Google Drive上资源文档中的Python部分。我们还分享了一个文档“调试提示”来帮助您调试代码。 我们强烈建议您在“Coding”文件夹下为作业创建一个新的虚拟环境。然后，您可以通过运行命令“python -m pip install -r requirements.txt”来安装所需的依赖。
2.2 问题陈述
在这个编程部分，您将编写一个搜索迷宫的agent。更具体地说，您将实现以下搜索算法（图搜索） – • BFS（不是使用FIFO队列的最佳优先搜索） • DFS • UCS • A – Star 与讲座和以前的示例不同，这些迷宫可能（或可能不）有多个目标。因此，我们将修改我们的启发式为到最近目标的欧几里得距离。 完成Agent.py文件并将其提交到Gradescope。我们将使用自动评分器在10个测试迷宫上对每个算法进行评估。在Agent.py中，您必须完成以下函数 i. heuristic_function：返回AStar节点的坐标与结束坐标之间的最小欧几里得（直线）距离 ii. A – star节点的三个比较函数__eq__，__lt__，__gt__ iii. goal_test iv. expand_node v. bfs vi. dfs vii. ucs viii. astar 为了简单起见，请直接将节点添加到前沿，而不是更新现有节点。 在开始之前，请仔细阅读Maze.py和Agent.py！文件在每个需要您添加代码的地方都用TODO进行了注释，并包含了多个关于如何进行的注释、提示和建议。util.py用于帮助IDE进行类型检查，请随意忽略它。此外，您永远不需要修改maze.py或util.py。
迷宫结构
每个测试用例都是一个文本文件（保存为.test文件，但您可以在任何文本编辑器中打开它）。以下是测试用例1的样子：
3 3
1 1 1 1
...
A∗B
...输入的第一行列出了迷宫的宽度（w）和高度（h）。 第二行输入列出了向左、向右、向上和向下移动的成本。接下来的三行描绘了网格中的元素。‘A’表示agent的起始点。’B’表示目标状态。’.’表示agent可以自由着陆的点，而’*’表示墙壁。
2.3 本地测试
我们提供了四个测试用例，您可以使用它们来测试您的实现。您可以使用python LocalTest.py {TESTNUMBER} {SEARCH ALGORITHM}来运行它。 也就是说，我们没有为它们提供解决方案。LocalTest.py文件将向您展示迷宫的样子以及您的agent找到的路径。您可以解决迷宫并确定您的算法是否正确工作。 测试用例1、2和3在Gradescope上是相同的。没有隐藏的测试用例 – 您在Gradescope上的得分是您可以预期在此部分获得的分数。 运行LocalTest.py对测试用例1进行BFS和DFS后，您应该看到的示例如图5所示。红色点是起始位置，黄色星是目标，绿色箭头表示算法找到的路径。灰色单元格表示墙壁，而单元格根据算法执行过程中它们被扩展的早晚进行着色。蓝色越深，扩展越早。白色单元格尚未被扩展。
（a）BFS
（b）DFS
图5：BFS和DFS在测试用例1上找到的预期路径