PythonRobotics 中的 Bug 算法二维路径规划Bug0 / Bug1 / Bug2 原理与源码实战【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRoboticsBug 算法是一类经典的反应式reactive二维路径规划方法机器人不需要提前构建完整环境地图仅依靠朝向目标直线移动 碰到障碍物后沿边界绕行两条简单规则即可到达目标点。本文以 PythonRobotics 仓库的 PathPlanning/BugPlanning/bug.py 为核心系统讲解 Bug0、Bug1、Bug2 三种变体的算法逻辑、类与方法的实现细节、默认仿真场景的构造方式并结合 tests/test_bug.py 说明如何验证算法正确性。读完本文后你将能独立运行该示例、理解三种 Bug 算法的差异并能在自己的二维栅格场景中复用这套实现。Bug 算法是什么只靠直行 贴墙完成规划Bug 算法Bug Algorithm是移动机器人路径规划中最基础的一类方法其核心思想是机器人不需要知道全局障碍物分布只需两种行为即可完成从起点到目标点的导航直行toward goal沿当前点与目标点的连线方向贪婪移动绕行boundary following一旦直行路径被障碍物阻挡就贴着障碍物边界绕行直到满足离开条件。这种遇到墙就沿着墙走的策略使得 Bug 算法天然适用于仅有局部传感信息如接触传感器或短程测距的移动机器人。在 PythonRobotics 中该模块被归类于路径规划模块Path Planning对应文档为 bugplanner_main.rst其算法思路参考自 ECE452 课程关于 Bug 算法的公开讲义。三种变体Bug0、Bug1、Bug2 的决策差异bug.py中的BugPlanner类一次性实现了三种经典变体它们的绕行-离开判定策略各不相同变体直行撞墙后绕行策略离开条件路径质量Bug0任意方向开始绕行沿边界绕行期间不断尝试重新直行一旦直行方向不再被障碍物阻挡就立即脱离边界最差可能反复绕行但行为最简单Bug1沿边界完整绕行一圈绕行一整圈并记录距目标最近的点回到最初撞击点后再从最近点出发直行保证收敛但绕行开销最大Bug2记录目标连线M-line绕行时持续跟踪与目标点的距离变化当距离由减小转为增大即经过最近点时离开边界通常比 Bug1 短但不保证全局最优从源码结构看这三种变体共享同一套底层移动原语直行、绕行只是绕行状态机中何时切换回直行模式的判断逻辑不同分别对应类中的bug0()、bug1()、bug2()三个方法bug.py 第 55/116/193 行起。源码剖析BugPlanner 类的核心机制构造函数预处理障碍物外边界BugPlanner的构造函数bug.py 第 13-33 行接收起点(start_x, start_y)、目标点(goal_x, goal_y)和障碍物栅格坐标列表(obs_x, obs_y)并做了一件关键预处理对每个障碍物格子做 8 邻域膨胀生成障碍物外边界点集out_x/out_y。for o_x, o_y in zip(obs_x, obs_y): for add_x, add_y in zip([1, 0, -1, -1, -1, 0, 1, 1], [1, 1, 1, 0, -1, -1, -1, 0]): cand_x, cand_y o_x add_x, o_y add_y # 若候选点本身不是障碍物格子则加入外边界集合这段代码的意义在于把实心障碍物外壳化。后续mov_to_next_obs()bug.py 第 39-53 行在绕行模式下会按右、上、左、下的优先级[1,0,-1,0]与[0,1,0,-1]从当前位置探测相邻的外边界点作为下一步落脚点从而实现沿障碍物边缘移动的效果同时通过visited_x/visited_y记录已访问点防止原地打转。mov_normal贪婪直行mov_normal()bug.py 第 35-37 行是朝目标直行的实现def mov_normal(self): return self.r_x[-1] np.sign(self.goal_x - self.r_x[-1]), \ self.r_y[-1] np.sign(self.goal_y - self.r_y[-1])它利用np.sign()在 x、y 两个方向上分别取朝目标前进 1 格的方向即每个时间步最多移动一个栅格两个坐标可同时变化即允许 8 方向移动。r_x/r_y保存了机器人的历史轨迹r_x[-1]即当前位置。碰撞检测与绕行状态机以 Bug0 为例bug.py 第 55-114 行主循环维护一个mov_dir状态normal直行 /obs绕行直行态计算mov_normal()的候选点若该候选点命中out_x/out_y中的任一边界点则判定撞墙清空访问记录并切换到绕行态绕行态调用mov_to_next_obs()沿边界走一格同时每次试探mov_normal()的方向若直行方向已不再被原始障碍物obs_x/obs_y注意此处用实心障碍物而非外边界阻挡则切回直行态。Bug1bug.py 第 116-191 行在此基础上增加了一个绕行一整圈的机制绕行过程中用欧氏距离np.linalg.norm(...)持续记录距目标最近的点(exit_x, exit_y)当重新回到起始撞击点back_to_start标志后通过del self.r_x[-len(visited_x):]回退轨迹并开始第二轮绕行直到再次到达最近点才切回直行。Bug2bug.py 第 193-274 行则预先沿起点-目标连线模拟一遍直行把这条线上所有会撞到障碍物的撞击点记录到hit_x/hit_y图中以菱形标记绕行时每经过一个预记录的撞击点就删除一个从而在距离由减转增的最近点离开边界。main 函数默认仿真场景与障碍物布局main()bug.py 第 277-329 行接收三个布尔参数bug_0, bug_1, bug_2控制执行哪种算法默认场景参数为起点(s_x, s_y) (0.0, 0.0)目标点(g_x, g_y) (167.0, 50.0)障碍物为 7 个矩形栅格块通过嵌套range循环逐格填充矩形块x 范围y 范围块 120–3920–39块 260–9940–79块 3120–13980–99块 480–1390–19块 50–1960–99块 620–3980–99块 7120–15940–597 个矩形块在 0~167 × 0~100 的栅格区域中形成一条蜿蜒的巷道迫使机器人多次绕障正好能直观对比三种 Bug 算法的绕行路径差异。文件末尾的入口bug.py 第 332-333 行默认只运行 Bug0if __name__ __main__: main(bug_0True, bug_1False, bug_2False)如何运行与可视化该模块只依赖numpy与matplotlib二者均在 requirements/requirements.txt 中。安装依赖后直接执行脚本即可看到动画pip install -r requirements/requirements.txt python PathPlanning/BugPlanning/bug.py默认运行 Bug0。如果想对比三种算法可临时修改__main__入口或直接导入调用from PathPlanning.BugPlanning.bug import BugPlanner, main # 方式一一次跑三种算法需自行修改入口参数 main(bug_0True, bug_1True, bug_2True) # 方式二构造自己的场景 planner BugPlanner(start_x0.0, start_y0.0, goal_x167.0, goal_y50.0, obs_xo_x, obs_yo_y) planner.bug1()运行时show_animation全局开关bug.py 第 10 行控制是否实时绘制障碍物以黑色点绘制、起点为绿色圆圈、目标为蓝色叉号、外边界为灰色点、红色折线为机器人轨迹plt.pause(0.001)实现逐帧动画Bug2 还会用菱形标记预计算的撞击点。测试验证三种算法的收敛性检查仓库为 Bug 规划提供了单元测试 tests/test_bug.py测试逻辑非常简洁def test_1(): m.show_animation False m.main(bug_0True, bug_1True, bug_2True)该测试先将show_animation置为False关闭 GUI 绘图以便在无头环境运行随后在默认场景上一次执行 Bug0、Bug1、Bug2 三种算法。由于三种算法的主循环都以当前位置等于目标点作为终止条件if self.r_x[-1] self.goal_x and self.r_y[-1] self.goal_y: break测试能够顺利通过本身即验证了在默认场景下三种 Bug 变体都能收敛到目标点。这也印证了 Bug 类算法的核心性质——只要目标点可达机器人最终必然到达目标。适用场景与局限性从实现细节可以看出这份 Bug 规划实现有以下特点与边界离散栅格模型位置是整数栅格坐标运动通过np.sign逐格推进属于 8 连通移动不包含速度、航向角等运动学约束适用于点状机器人的概念验证无需全局地图算法只依赖当前点邻域的碰撞查询符合反应式导航的设定路径非最优Bug 系列只保证能到不保证路径最短Bug1 保证可达但绕行最长Bug2 通常更短但不保证全局最优适用前提要求目标点在障碍物外部且与起点可达否则主循环可能无法终止。若需要更高质量的结果可转向仓库中基于采样的方法如 RRT、RRTStar或基于优化的方法如 LQRRRTStar。但作为理解反应式导航的第一课Bug0/Bug1/Bug2 的实现清晰、逻辑完整、动画直观是阅读源码学习路径规划状态机的理想入口。【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考