Introduction
这项作业的目的是让你通过几种基本规划算法及其应用来积累经验。在实施和测试这些算法后，
你应该能够了解到规划中的现实挑战以及每种算法的优缺点。
Task 1: Global Planning
For both Task 1&2 of your planning homework, you will be using a map of the VivoCity level 2, as shown
below:
左图是原始的楼层平面图，而右图是灰度版本，将用于您的规划算法。整个地图的尺寸为1000 x
1000像素（网格单元），每个单元格代表一个0.2m x 0.2m的正方形区域。每个网格单元格属于两
种可能状态之一：空闲（值为255）或占用（值为0）。作为一个人，您的预期圆形足迹半径不少
于0.3m。
地图上有五个指定的关键位置您希望访问：start（起点）、snacks（小吃）、store（商
店）、movie（电影）、以及food（食物）。您的任务是规划一条路径/轨迹，连接每一对起点和
终点，并展示您的
在地图上规划路径，并计算您的计划总行程距离（以米为单位）。最后，利用您计算出的距离，
找到最有效的路线，即从目前位于二楼扶梯（起点）的位置出发，访问所有四个位置并返回起
点。在此任务中，您需要实现一个A规划算法。在您的算法中，您应该：
§ • 使用8连通邻居，其成本值为0.2米（左右）或0.282米(对角
线）(必做）。
§ • 计算到达目标所需的总行程距离（必做）。
§ • 您可以从以下1-2个想法中选择并尝试 （从下面选一个你认
为最快的）：
§ § Try different heuristic functions (also design your own)
§ § Try switch the start and goal positions
§ § Try search from both ends
§ § Degenerate the A algorithm to Dijkstra’s Algorithm
§ § Degenerate the A* algorithm to Greedy Best First Search
Algorithm
§ § Implement the Hybrid-A* algorithm
§ § Implement the RRT family
您的算法的输出应包括：
规划的路径：包括要按顺序访问的路径点序列，以最小化总行程距离。
总行程距离：沿着规划路径，相邻路径点之间的距离总和，以米为单位。
算法访问的所有单元格：指示算法执行过程中经过的所有单元格。
算法运行时间：算法计算最优路径所用的时间，以秒或毫秒为单位（比较必做算法和自
选算法，看自选算法快多少）。
其他关键性能指标：包括节点扩展数量、步骤数量、内存使用情况等其他与评估算法性
能或理解算法行为相关的信息。
在您的报告中，您应该：
记录算法的实现细节，以及对原始算法进行的改进（如果有）
· 比较不同算法/相同算法的不同设置之间的差异
· 描述您遇到的困难以及您的解决方案
· 识别您使用的方法的缺点，并提出改进建议
· 在表格中总结每对位置之间的最短距离：
From
To
start snacks store movie food
start 0.0
snacks 0.0
store 0.0
movie 0.0
food 0.0
任务2：“旅行购物者”问题
您现在位于VivoCity的二楼扶梯（起点），您希望访问所有四个位置，然后返回到扶梯处。根据
您在任务1中获得的距离表，找到您访问所有商店并返回起点位置的最佳路线。
- 模型问题描述和提出解决方法：
- 为了解决这个dai 写me5413问题，我将应用蚁群算法和遗传算法。以下是我对每种方法的实现细节：
- 比较蚁群算法和遗传算法计算得到的解决方案，可以观察到以下几点差异和特点：
- 显示地图上的最终最短路径和总距离：
路径跟踪
要控制机器人沿着给定的8字形轨迹移动，我们可以使用任何喜欢的算法，例如比例控制（P控制）。在P控制
中，机器人根据其当前位置与轨迹上所需位置之间的误差来调整其转向。
在以下位置用您自己的算法替换我们的模板代码：
src/me5413_world/include/me5413_world/path_tracker_node.hpp
src/me5413_world/src/path_tracker_node.cpp
src/me5413_world/cfg/path_tracker.cfg
· 在轨道上测试您的算法，并使用给定的指标报告您的跟踪准确性：
位置的均方根误差（RMSE）
方向的均方根误差（RMSE）
速度的均方根误差（RMSE）
· 一些建议：
您可以尝试Pure Persuit、LQR、MPC等算法。
您可以通过更改track_A_axis和track_B_axis的长度（以米为单位）来改变轨道的形状和
大小，并报告您的算法性能的变化。
Submitting your completed Homework Assignment:
代码：对于任务1和任务2，所有代码都应该在Jupyter Notebook中实现并提交，其中应显示所有输
出。对于任务3，所有代码都应该在您的代码库中实现，并作为GitHub代码库提交，提供链接。
请注意，在您自己的代码中，您应该遵循良好的代码风格，包括适当的命名惯例、信息性的文档
等（请参考Google Python风格指南、Google C++风格指南、C++核心指南、ROS C++风格指
南）。
报告：您应该总结您的观察、假设和您自己的实现细节在一个5页的报告中（如果您希望附加更
多的结果，请在附录中附上，但仅限于方程/算法/表/图，不包括文本段落）。
提交：生成一个无密码保护的zip文件夹，并将其上传到CANVAS - 在作业3下。我们将使用最新
版本，而不管由谁上传。Zip文件的名称为：HomeworkGroupNumber_Homework3.zip（例
如，43_Homework3.zip - 适用于43组）