无人机雨车辆路径规划算法 改进 A星算法以及JPS 优化版本 考虑到了对角障碍物的阻塞和绕路情况

当然以下是整理后的内容带图片的文档算法课程作业A路径规划与 JPS 扩展*主要探讨了 A* 路径规划算法并附带实现了Jump Point Search (JPS)的改进版本支持对角障碍物的阻塞与绕路处理。注所有代码都包含详细注释。 点击在线尝试→ Binder目录展示柜./src目录结构一些个人心得2.1 梳理一下2.2 JPS 算法碎碎念容易被绕进去的地方3.1 强制邻居是怎么引导扩展结点的对角障碍物的处理4.1 初探4.2 绕过对角障碍物4.3 修正绕路后的搜索策略其他需要说明的地方5.1 生成问题时去除对角障碍物踩到的一个坑不足之处总结0. 展示柜A* 算法带对角障碍物绕路机制的Jump Point Search (JPS)算法1. ./src 目录结构src ├── algorithms # 算法实现 │ ├── __init__.py │ ├── a_star.py # A* 算法 │ ├── a_star_jps.py # A* Jump Point Search 版本 │ ├── a_star_jps_detour.py # JPS 版支持对角障碍绕路 │ ├── a_star_jps_detour_fixed.py # 最优版 JPS修正绕路后的搜索策略 │ ├── a_star_jps_detour_failed.py # 绕路失败的版本 │ ├── algorithm_base.py # 算法基类 │ ├── states.py # 算法状态枚举 │ └── utils.py # 工具类方向处理相关 ├── exceptions │ └── __init__.py # 自定义异常 ├── problems │ ├── __init__.py │ ├── cell_status.py # 格子状态枚举 │ ├── drawer.py # 问题绘制模块 │ ├── generator.py # 随机问题生成 │ ├── problem.py # 问题类用于表示二维栅格图 │ └── utils.py # 工具方法 ├── test.py # 测试用例 ├── requirements.txt # Python 依赖 ├── problem.bin # 示例问题pickle 格式 └── visualization ├── __init__.py ├── algo_animator.py # 算法动画化模块 ├── problem_visualizer.py # 问题可视化模块 ├── result_visualizer.py # 结果可视化模块 └── utils.py # 可视化相关工具方法说明每个算法实现的.py文件头部均包含文档注释具体内容可以查看源码。示例问题可以通过Problem.from_file方法载入。调用方法请参考test.py文件以及各个方法的docstring注释。2. 一些个人心得2.1 梳理一下Dijkstra 算法逐步扩展路径最短的结点虽然能找到最优路径但扩展速度缓慢适合边权非负的场景。A* 算法在 Dijkstra 的基础上加入启发式信息加速搜索过程但启发式计算方式对性能有较大影响。Jump Point Search (JPS)算法通过跳点大幅减少扩展结点数量是 A* 的一种重要优化。核心思想扩展结点的策略。JPS 算法的优化点强制邻居引导结点扩展找到跳点。跳点扩展目标不是所有邻居而是跳点。2.2 JPS 算法碎碎念在 JPS 中扩展结点仅限于跳点而不是 A* 的邻居从而显著减少扩展数量。优化点主要在扩展策略。JPS 的两个核心概念强制邻居Forced Neighbor通过其引导扩展跳点。跳点Jump Point算法扩展的实际目标。总结相比 A*JPS 改进的重点在“扩展结点的部分”。3. 容易被绕进去的地方3.1 强制邻居是如何引导扩展的强制邻居的作用用于判定跳点。用于引导扩展结点方向。例水平/竖直方向沿路径方向扩展遇到强制邻居新增扩展方向。对角方向同时沿水平和竖直方向移动遇到障碍物时强制新增方向。以下图示展示扩展方式4. 对角障碍物的处理4.1 初探diagonal_obstacles参数控制是否允许穿过对角障碍物。如下示例Case 1简单对角障碍Case 2复杂对角障碍4.2 绕过对角障碍物对于复杂障碍JPS 可通过额外记录“绕路结点”实现绕行如下图4.3 修正绕路后的搜索策略修正策略将绕路结点临时加入open_list并强制搜索平行方向确保找到最优路径。示例5. 其他需要说明的地方5.1 生成问题时去除对角障碍物示例未去除对角障碍物去除对角障碍物6. 踩到的一个坑绕路结点加入open_list时的注意事项不标记其坐标避免与其他结点冲突。不加入closed_list仅作为临时结点。7. 不足之处在障碍物复杂的图中修正后的 JPS 求解速度仍慢于 A*。跳点搜索耗时较高特别是在随机障碍物分布的情况下。8. 总结通过实现 JPS 及其改进版深刻体会到路径规划的趣味与复杂性。特别是在绕路与搜索策略修正部分算法的设计与优化充满挑战和成就感