本系列文章主要对Bug类路径规划算法的原理进行介绍，在本系列的第一篇文章中按照时间顺序梳理了自1986年至2018年Bug类路径规划算法的发展，整理了13种BUG系列中的典型算法，从本系列的第二篇文章开始依次详细介绍了其中具有代表性的BUG1、BUG2、Tangent BUG、I-BUG、RandomBug、BugFlood等算法。
本篇文章作为本系列文章第五篇文章，主要对RandomBug 算法进行介绍
本系列其他文章见：BUG系列路径规划算法原理介绍——总结篇
一、RandomBug 算法简介
RandomBug 算法是由青岛科技大学的徐啟蕾老师于2014年在论文《RandomBug: Novel Path Planning Algorithm in Unknown Environment》提出的一种新颖的完全未知环境中全向自主移动机器人路径规划和避障策略，通过不断迭代沿着路径移动、检测障碍物、计算中间点并重新生成路径等动作来生成无碰撞且可行的路径。
论文链接：《RandomBug: Novel Path Planning Algorithm in Unknown Environment》
论文PDF下载链接（已开放存取）： Microsoft Word - Qi-lei Xu_TOEE.doc
本文中所有示例图及公式均来源于以上论文
二、RandomBug 算法的路径表示及运动方式
在RandomBug 算法中，路径由一系列向量组成的路径向量集描述，在路径向量集中，每个向量代表总路径中的一部分分段路径，且前一个向量的终点是后一个向量的起点，这样向量集中的向量按照顺序就组成了规划的路径，很显然从起点到目标点的总路径由一系列折线组成，每一段折线都是路径向量集中的一个向量。下式中Pi代表路径向量集，a_i1 ~ a_in代表组成路径的有序分段路径，并且每个a_ik中储存了每段路径的长度||a_ik||,以及与上一段路径的夹角θ_ik ，取值范围为-π ~ π ，论文中取顺时针方向为正。
这样机器人只需要沿着当前路径段a_ik直行||a_ik||距离，然后旋转a_ik+1度，再沿着路径段a_ik+1，直行||a_ik+1||距离…以此类推即可达到目标点，即在机器人运动过程中仅包含沿着当前路径段直行，和旋转至下一个路径段的方向两种基础运动单元。
三、RandomBug 算法的流程
在RandomBug 算法中，首先，机器人根据起始位置和目标位置，建立初始路径向量集（此时向量集仅存在一个向量，即由起始位置指向目标位置的向量）。然后，判断路径向量集中的向量是否被障碍物阻塞，即判断路径上是否存在障碍物。当存在有障碍物时，在以当前位置为圆心，传感器探测距离为半径上限，机器人的安全距离为半径下限的圆环区域内随机生成一些中间点，然后选择最优的中间点插入到当前路径矢量集中来重新生成路径矢量集。以此循环，直至机器人达到目标位置。
接下来，我们对上述描述中的一些细节展开介绍
（1）如何判断障碍物是否在当前路径中？
在下图中，机器人当前位于q处，且传感器探测到障碍物所在位置Po，向量q- Po与当前路径段q - q_goal的夹角为ψ，向量向量q- Po的模记为d，图中的大圆表示传感器的探测范围,其半径为R_mnge，小圆表示机器人的安全距离，其半径为R_safe，当满足以下两个条件时，认为判断障碍物在当前路径中。
① d * sin |ψ| < R_safe (本条件用于确保代理与障碍物保持安全距离。)
② d不大于当前路径剩余距离与R_safe之差
（2）如何选择最佳中间点？
在下图中当机器人移动到位置q时，它可以检测到当前路径的障碍物点po。然后，随机生成了下图中显示的10个中间点p1~p10，并舍弃掉位于障碍物内的点，比如图中的p4，且当障碍物上的点超过一半时，这些点需要再次随机生成。
然对所有不在障碍物内的点pk，计算Si=d（q，pk）+ d（pk，goal），并选择Si最小值对应的那个pi点作为选择的最佳中间点插入到路径向量集中。d（q，pk）即为路径段a_k1的模长，即为从当前位置q到pi点的路径长度，同理d（pk，goal）即为路径段a_k2的模长，即为从当pi点到目标点goal的路径长度
四、RandomBug 算法规划示例
以下面的第一幅图为例，最初机器人从起始点q_start出发时初始化的路径向量集为Po,仅包含一个向量a_01，由起点指向终点，然后机器人开始沿着a_01运动至图中a_11末端所示位置时发现了障碍物，然后以该位置为圆心，按照上文介绍的方法，得到中间点p，路径集也由P0，变为P1，P1中包含如图中所示的三个向量。
论文中均采用的余弦定理来求解a_13和θ_13，其实完全可以更简单的利用两点间距离公式求a_13，以及点积公式的变形形式求θ_13。
注：下图中所有图片及数学表达式均来源于文章开始处提到的论文
附：余弦定理及点积公式
五、实验验证
论文中的实验结果表明，当传感器范围和随机点数量不变时，通过减小安全半径或增加随机中间点的数量，规划的路径可以更靠近障碍物轮廓。
在特殊情况下，比如狭窄的通道，安全半径不能太大，否则机器人将无法通过狭窄的通道移动，并且路径长度会增加。
通过增加随机中间点的数量，路径变得更平滑，而时间成本和路径长度却大大增加。为了避免局部最优，随机点的数量不能太大。因为随机点的模长范围是从安全半径到传感器范围，所以可以通过减小传感器范围在一定程度上减少插入点的数量。
不同参数下的规划结果示例如下（来源于论文）
