COMP3702作业2 代写

该文档是关于COMP3702课程作业2的介绍，作业主题是BeeBot MDP。学生需要为在六边形环境中运行的BeeBot开发规划算法，使其能够推动、拉动和旋转蜂蜜“Widgets”以重新定位它们到目标蜂巢位置。作业包括编程和报告两部分，占总成绩的20%，需要通过Gradescope提交。文档详细介绍了BeeBot的环境表示、代理及其动作、动作成本、障碍物、Widgets、目标、交互模式以及作为MDP的相关内容，并提供了支持代码和测试用例，学生需要实现价值迭代（VI）和策略迭代（PI）等MDP算法。

COMP3702人工智能（2024年第二学期）

作业2：BeeBot MDP

关键信息： – 截止日期：2024年9月20日星期五下午1点 – 本作业评估你为具有挑战性的问题开发离散搜索技术的技能。 – 作业2占你最终成绩的20%。 – 本作业由两部分组成：（1）编程和（2）报告。 – 这是一个个人作业。 – 代码和报告都将通过Gradescope（https://www.gradescope.com/）提交。你可以在Blackboard上找到COMP3702 Gradescope网站的链接。 – 你的代码（第1部分）将使用Gradescope代码自动评分器进行评分，使用在https://github.com/comp3702/2024-Assignment-2-Support-Code提供的支持代码中的测试用例。 – 你的报告（第2部分）应符合提供的模板，为.pdf格式，并根据格式a2 – COMP3702 – [SID].pdf命名。报告将由教学团队评分。

BeeBot AI环境 你被要求为自动控制BeeBot开发一种规划算法，BeeBot是一只在六边形环境中运行的蜜蜂，能够推动、拉动和旋转蜂蜜“Widgets”，以便将它们重新定位到目标蜂巢位置。为了帮助你完成这项任务，我们提供了BeeBot环境的支持代码，你将与之接口来开发你的解决方案。为了最优地解决一个关卡，你的AI智能体必须有效地找到一系列动作，以便每个目标单元格都被一个Widget的一部分占据，同时产生最小的可能动作成本。对于A2，BeeBot环境已被扩展为对动作的非确定性结果进行建模。成本和动作有效性现在被奖励函数所取代，其中动作成本由收到的负奖励表示，当发生碰撞（蜜蜂或蜂蜜Widget与障碍物之间，或Widget之间）时会产生额外的惩罚（即负奖励）。游戏环境的更新以粉色字体表示。

BeeBot的关卡由一个六边形的单元格网格组成，每个单元格包含一个表示单元格类型的字符。一个示例游戏关卡如图1所示。

图1：BeeBot的示例游戏关卡，展示了基于字符和GUI可视化器的表示

环境表示

六边形网格 环境由一个六边形网格表示。六边形网格的每个单元格由（行，列）坐标索引。六边形网格从上到下，从左到右索引。也就是说，左上角的坐标为（0，0），右下角的坐标为（nrows – 1，ncols – 1）。偶数编号的列（从0开始）在行的上半部分，奇数编号的列在行的下半部分。一个示例如图2所示。

____ ____
/ \ / \
/row 0 \____/row 0 \____...
\col 0 / \col 2 / \
\____/row 0 \____/row 0 \...
/ \col 1 / \col 3 /
/row 1 \____/row 1 \____/...
\col 0 / \col 2 / \
\____/row 1 \____/row 1 \...
\col 1 / \col 3 /
... \____/... \____/
......

图2：示例六边形网格展示了行和列的索引顺序 六边形网格中的两个单元格如果共享一条边，则被认为是相邻的。对于每个非边界单元格，有6个相邻单元格。

BeeBot智能体及其动作 BeeBot蜜蜂占据六边形网格中的一个单元格。在可视化中，蜜蜂由标记为“R”的单元格表示（或图形可视化器中的蜜蜂）。单元格标记为“*”的一侧（或图形可视化器中的箭头）表示蜜蜂的前方。蜜蜂的状态由其（行，列）坐标和其方向（即其前方指向的方向）定义。在每个时间步，智能体被提示选择一个动作。蜜蜂有4个可用的标称动作： – 前进→移动到蜜蜂前方方向的相邻单元格（保持相同的方向） – 后退→移动到蜜蜂前方相反方向的相邻单元格（保持相同的方向） – 左转→向左旋转（相对于蜜蜂的前方，即逆时针）60度（留在同一单元格） – 右转→向右旋转（即顺时针）60度（留在同一单元格）每次蜜蜂选择一个动作时，蜜蜂有固定的概率（作为每个测试用例的参数给出）在执行所选标称动作之前“漂移”60度顺时针或逆时针方向（每个漂移方向的概率分开）。漂移发生的概率取决于选择的标称动作，某些动作更有可能导致漂移。顺时针和逆时针漂移是互斥事件。此外，蜜蜂还有固定的概率（也作为每个测试用例的参数给出）“双重移动”，即执行标称选择的动作两次。双重移动发生的概率取决于选择的动作。双重移动可能与漂移（顺时针或逆时针）同时发生。每个动作后收到的奖励是标称动作和任何额外（漂移/双重移动）动作收到的奖励中最小/最负的。蜜蜂的前方配备了一个夹具，允许它操纵蜂蜜Widgets。当蜜蜂的前方与一个蜂蜜Widget相邻时，执行“前进”动作将导致Widget被推动，而执行“后退”动作将导致蜂蜜Widget被拉动。

动作成本 每个动作都有相关的成本，表示执行该动作使用的能量量。如果蜜蜂移动而不推动或拉动蜂蜜Widget，动作的成本由基本动作成本ACTION_BASE_COST[a]给出，其中“a”是执行的动作。如果蜜蜂推动或拉动蜂蜜Widget，则会额外增加ACTION_PUSH_COST[a]的成本，因此总成本为ACTION_BASE_COST[a] + ACTION_PUSH_COST[a]。成本在支持代码的constants.py文件中详细说明：

ACTION_BASE_COST = {FORWARD: 1.0, REVERSE: 1.0, SPIN_LEFT: 0.1, SPIN_RIGHT: 0.1}
ACTION_PUSH_COST = {FORWARD: 0.8, REVERSE: 0.5, SPIN_LEFT: 0.0, SPIN_RIGHT: 0.0}

障碍物 六边形网格中的一些单元格是障碍物。在可视化中，这些单元格用字符“X”填充（在图形可视化器中表示为黑色单元格）。任何导致蜜蜂或蜂蜜Widget的任何部分进入障碍物的动作都会导致碰撞，导致智能体收到负的障碍物碰撞惩罚作为奖励。这个奖励取代了智能体原本会产生的移动成本。六边形网格的外部边界与障碍物的行为相同。此外，环境现在包含一种额外的障碍物类型，称为“荆棘”。荆棘的行为与障碍物相同，但当发生碰撞时，会收到不同（更大）的惩罚作为奖励。因此，避免与荆棘碰撞比避免与障碍物碰撞更为重要。荆棘在基于文本的可视化中用“!!!”表示，在图形可视化中用红色单元格表示。

Widgets 蜂蜜Widgets是占据六边形网格多个单元格的对象，可以由BeeBot蜜蜂旋转和平移。每个蜂蜜Widget的状态由其中心位置（行，列）坐标和其方向定义。蜂蜜Widgets具有旋转对称性 – 旋转对称的方向被认为是相同的。在可视化中，环境中的每个蜂蜜Widget都被分配一个唯一的字母“a”，“b”，“c”等。被蜂蜜Widget占据的单元格用分配给该Widget的字母标记（用圆括号包围）。蜂蜜Widget的中心位置用大写字母标记，而所有其他被Widget占据的单元格用小写字母标记。有三种可能的蜂蜜Widget类型，称为Widget3，Widget4和Widget5，其中尾随的数字表示蜂蜜Widget占据的单元格数量。这三种蜂蜜Widget类型的形状及其可能的方向如图3至图5所示。

VERTICAL

_____
SLANT_LEFT / \ SLANT_RIGHT
_____ / (a) \ _____
/ \ \ / / \
/ (a) \_____/ (a) \ \_____/ (a) \
\ / \ / \ / \ /
\_____/ (A) \_____ / (A) \ _____/ (A) \_____/
\ / \ \ /
_____/ (A) \_____ \_____/
/ \ / \ / \
/ (a) \_____/ (a) \ / (a) \
\ / \ / \ /
\_____/ \_____/ \_____/

图3：Widget3

UP DOWN

_____ _____ _____
/ \ / \ / \
/ (a) \ / (a) \_____/ (a) \
\ / \ / \ /
\_____/ \_____/ (A) \_____/
/ \ \ /
_____/ (A) \_____ \_____/
/ \ / \ / \
/ (a) \_____/ (a) \ / (a) \
\ / \ / \ /
\_____/ \_____/ \_____/

图4：Widget4

SLANT_RIGHT SLANT_LEFT

_____ _____
HORIZONTAL / \ / \
_____ _____ / (a) \_____ _____/ (a) \
/ \ / \ \ / \ / \ /
/ (a) \_____/ (a) \ \_____/ (a) \ / (a) \_____/
\ / \ / / \ / \ / \
\_____/ (A) \_____/ _____/ (A) \_____/ \_____/ (A) \_____
/ \ / \ / \ / \ / \
/ (a) \_____/ (a) \ / (a) \_____/ \_____/ (a) \
\ / \ / \ / \ / \ /
\_____/ \_____/ \_____/ (a) \ / (a) \_____/
\ / \ /
\_____/ \_____/

图5：Widget5 两种类型的Widget移动是可能的 – 平移（中心位置的变化）和旋转（方向的变化）。当蜜蜂的前方与一个蜂蜜Widgets的单元格相邻，使得蜜蜂的方向与蜂蜜Widget的中心位置对齐时，平移发生。平移导致Widget的中心位置向与蜜蜂相同的方向移动。当平移发生时，蜂蜜Widget的方向不会改变。当执行“前进”或“后退”动作时，可能会发生平移。对于导致平移的动作要有效，移动的Widget的所有单元格的新位置不得与环境边界、障碍物、任何其他蜂蜜Widgets的单元格或蜜蜂的新位置相交。当蜜蜂的新位置与一个蜂蜜Widget的单元格相交，但蜜蜂的方向不指向该Widget的中心时，旋转发生。旋转导致蜂蜜Widget围绕其中心点旋转，导致Widget改变方向。当旋转发生时，中心点的位置不会改变。旋转只能发生在“前进”动作中 – 在“前进”会导致Widget旋转的情况下执行“后退”被认为是无效的。以下图表显示了每个蜂蜜Widget类型的哪些移动会导致平移或旋转，箭头表示蜜蜂可以推动或拉动Widget以导致Widget平移或旋转的方向。在未标记箭头的方向上推动被认为是无效的。

前进平移

后退平移

前进顺时针旋转

后退逆时针旋转

图6：Widget3的平移和旋转

前进平移

后退平移

前进顺时针旋转

后退逆时针旋转

图7：Widget4的平移和旋转

前进平移

后退平移

前进顺时针旋转

后退逆时针旋转

图8：Widget5的平移和旋转

目标六边形网格包含许多“目标”蜂巢单元格，必须用蜂蜜填充。在可视化中，这些单元格用“tgt”标记（在图形可视化器中为橙色单元格）。为了使BeeBot环境被认为已解决，每个目标单元格必须被一个蜂蜜Widget的一部分占据。环境中的目标数量始终小于或等于所有蜂蜜Widgets占据的单元格总数。

交互模式 了解游戏的一个好方法是玩它。你可以通过从终端启动交互式游戏会话来玩游戏，以了解它的工作原理，对于图形可视化器，使用以下命令：

$ python play_game.py.txt

对于命令行ASCII字符基于的可视化器，使用以下命令：

$ python play.py.txt

其中.txt是一个有效的测试用例文件（来自支持代码，相对于当前目录的路径），例如testcases/ex1.txt。根据你的python安装，你应该使用python，python3或py运行代码。在交互模式下，输入你选择的动作的符号（在命令行版本中按回车键）来执行动作：按’W’移动蜜蜂前进，’S’移动蜜蜂后退，’A’将蜜蜂向左转（逆时针），’D’将蜜蜂向右转（顺时针）。使用’Q’退出模拟，使用’R’将环境重置为初始配置。

BeeBot作为MDP 在本作业中，你将编写一个程序的组件来玩BeeBot，目标是使用基于马尔可夫决策过程（MDP）框架的各种顺序决策算法找到问题的高质量解决方案。本作业将测试你为实际问题定义MDP并开发有效的MDP精确算法的技能。

提供给你的内容 我们以Python的形式提供支持代码，包括： 1. 一个表示BeeBot游戏地图的类和一些辅助函数 2. 一个解析方法，用于接受输入文件（测试用例）并将其转换为BeeBot地图 3. 一个测试器 4. 测试和评估你的解决方案的测试用例 5. 一个允许你交互式玩BeeBot的脚本 6. 一个解决方案文件模板支持代码可以在以下位置找到：https://github.com/comp3702/2024-Assignment-2-Support-Code。代码的自动评分将通过Gradescope进行，因此你可以评估你的提交并根据此反馈继续改进它 – 强烈鼓励你利用此反馈。你也可以使用提供的tester.py文件在本地进行测试。

你的作业任务 你的任务是开发计算策略的算法，并撰写一份报告来测试你对算法的理解和分析其性能。你将根据提交的代码（第1部分，60%）和报告（第2部分，40%）进行评分。这些百分比将按比例缩放到本评估项目的20%课程权重。提供的支持代码将BeeBot制定为MDP，你的任务是提交实现以下MDP算法的代码： – 价值迭代（VI） – 策略迭代（PI） 个别测试用例指定将应用哪种策略（价值迭代/策略迭代），但你可以修改测试用例中指定的策略，以比较你的两种算法的性能。请注意，你对测试用例所做的任何本地更改都不会修改Gradescope上的测试用例（你的编程组件将根据此进行评分）。更高级别的测试用例的难度将设计为需要更高级的解决方案（例如线性代数策略迭代）。一旦你实现并测试了上述算法，你将完成“第2部分 – 报告”部分中列出的问题并将报告提交给Gradescope。下面将更详细地说明编程和报告部分所需的内容。

第1部分 – 编程任务 你的程序将使用在https://github.com/comp3702/2024-Assignment-2-Support-Code提供的支持代码中的测试用例，通过Gradescope自动评分器进行评分。

与测试用例和自动评分器的交互 我们现在为你提供一些详细信息，解释你的代码将如何与测试用例和自动评分器交互（特别感谢Nick Collins和Aryaman Sharma）。关于BeeBot实现的信息在作业2支持代码README.md和代码注释中提供。使用提供的solution.py模板文件实现你的解决方案。你需要填写以下方法存根： – init(game_env) – vi_initialise() – vi_is_converged() – vi_iteration() – vi_plan_offline() – vi_get_state_value() – vi_select_action() – pi_initialise() – pi_is