PythonRobotics 如何用时空 A* 在动态障碍物环境中规划时间最优路径【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics在带动态障碍物的栅格环境中做路径规划时普通 A* 的代价是格子数无法保证路径在时间上最优。PythonRobotics 的TimeBasedPathPlanning模块提供了一套时空 A*Space-time A*示例代码代价改为到达节点所用的时间步数从而在避开移动障碍物的前提下规划出时间最优路径。本文说明如何安装依赖、运行官方示例、用单元测试验证结果以及如何调整网格和障碍物参数。准备环境按仓库文档的要求示例代码建议使用Python 3.12.x其他版本可能可用但官方只在该版本上做过测试。先克隆仓库并进入根目录然后在根目录安装依赖pip install -r requirements/requirements.txtrequirements/requirements.txt 中固定了numpy 2.3.5、matplotlib 3.11.0等版本时空 A* 的示例和测试依赖其中的 numpy、matplotlib 与 pytest。算法工作方式运行前先了解几个关键点便于看懂输出与标准 A* 不同时空 A* 的代价g(n)是到达该节点所用的时间步数启发函数是到目标的曼哈顿距离abs(dx) abs(dy)。在每个时间步可移动 1 格、也可以原地停留的假设下时间启发与距离启发等价最终路径在到达目标所需时间上最优。环境由 GridWithDynamicObstacles.py 中的Grid类建模内部维护一个 x、y、time 三维的 reservation matrix预订矩阵障碍物在创建时把完整运动轨迹写入该矩阵。后继节点有 5 种原地停留和上下左右移动。一个新节点只有在接下来 2 个时间步1 步进入、1 步离开都合法才会被生成这保证机器人在任何时刻都能离开当前格子。SpaceTimeAStar.py 中额外引入了 expanded set已扩展过的节点不再重复扩展文档给出的示例数据显示同一场景下节点扩展次数从 204490 次降到 2348 次规划耗时从 1.72 秒降到约 0.016 秒文档示例结果。BaseClasses.py 里对random和numpy.random统一设置了RANDOM_SEED 50随机障碍物的布局在多次运行间可复现。运行官方示例示例入口是 SpaceTimeAStar.py其main()的配置为起点(1, 5)、终点(19, 19)、21×21 网格、40 个障碍物障碍物排布取ARRANGEMENT1在网格中央沿 y 排成一行、沿 x 左右往返移动。按仓库文档进入目录后执行脚本的方式运行cd PathPlanning/TimeBasedPathPlanning python SpaceTimeAStar.py脚本中的两个模块级变量控制运行行为show_animation True默认规划完成后用PlotNodePath绘制机器人与障碍物随时间移动的动画verbose False默认传给SpaceTimeAStar.plan()置为True时会逐个打印被扩展的节点。运行结束会输出形如Planning took: x.xxxxx seconds的规划耗时具体数值取决于你的机器。验证规划结果仓库提供了对应的单元测试 tests/test_space_time_astar.py。该测试使用ARRANGEMENT1排布、起点(1, 11)、终点(19, 19)的 21×21 网格关闭动画后执行规划并断言三点路径包含 31 个节点路径最后一个节点的位置等于终点path.expanded_node_count 1000。在仓库根目录运行pytest tests/test_space_time_astar.py三条断言全部通过即说明该场景下时空 A* 的规划结果符合预期。NodePath对象定义见 Node.py还提供goal_reached_time()到达终点的时刻和positions_at_time每个时间步的位置映射可直接用于检查结果。自定义网格与障碍物在仓库根目录下编写脚本即可复用Grid和SpaceTimeAStar以下代码取自示例main()与测试文件的实际用法from PathPlanning.TimeBasedPathPlanning.GridWithDynamicObstacles import ( Grid, ObstacleArrangement, Position, ) from PathPlanning.TimeBasedPathPlanning.SpaceTimeAStar import SpaceTimeAStar import numpy as np start Position(1, 5) goal Position(19, 19) grid Grid( np.array([21, 21]), num_obstacles40, obstacle_avoid_points[start, goal], obstacle_arrangementObstacleArrangement.ARRANGEMENT1, ) path SpaceTimeAStar.plan(grid, start, goal, verboseTrue) print(path.goal_reached_time(), path.expanded_node_count)Grid构造函数的关键参数默认值见源码grid_sizenp.array([x 方向格数, y 方向格数])num_obstacles默认 40障碍物数量。若大于网格总格数构造时抛出Number of obstacles is greater than grid size!异常obstacle_avoid_points障碍物永远不会占据这些点官方示例用它避开起点和终点避免出现无解场景obstacle_arrangement默认RANDOMRANDOM为随机位置、随机移动ARRANGEMENT1为中央一列障碍物左右往返NARROW_CORRIDOR为静态障碍跳过中间一行time_limit默认 100仿真的总时间步数。规划时时间满足time 1 time_limit的节点会被跳过因此该值过小时可能找不到路径。如果开集的节点全部耗尽仍到达不了终点plan()会抛出No path found异常——这是文档给出的明确失败信号此时可调大time_limit、减少num_obstacles或更换障碍物排布。文档给出的替代方案Safe Interval Path Planningtime_based_grid_search 文档对比了同场景下的 SIPPSafe Interval Path Planning实现见 SafeInterval.py它预先计算每个格子的空闲时间区间来减少后继节点生成文档示例数据显示 Arrangement 1 从(1, 18)出发时SIPP 用 322 次扩展、0.00730 秒而时空 A* 用 2717154 次扩展、20.51330 秒。如果你的场景扩展次数很高可以按同一套Grid接口换用它作为可选分支。相关文档docs/modules/5_path_planning/time_based_grid_search/time_based_grid_search_main.rst 是该模块的总说明tests/test_safe_interval_path_planner.py 与 tests/test_space_time_astar.py 分别是两个规划器的验证入口。【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考