路径算法 1..1 智能寻找可走路线 我们所要实施的算法必须根据时间，加速度，角速度等数据来引导机器人寻找最优的路径从 起始状态到达末状态。然而其中包含了一些问题，如何利用移动当中的机器人来获得所有的 数据从而建立模型而且我们要尽量减少外界不利的因素对于机器人寻找路径的影响。其次， 我们要如何通过这些数据来引导机器人找到最佳的路径方案。 首先我们来解决如何获得最准确的数据并建立数据模型，我们知道机器人本身是在不断运动 的，而置于环境中的物体是静止的，所以我们要通过感应器不断的去获取周围环境的信息， 并进行快速处理。信息无法快速探测到或无法快速处理，将会导致我们的机器人发生撞击， 堵塞，或错误选择路径或自身无法运行。 撞击：机器人与其他物体撞击造成损坏 堵塞：机器人被动车堵塞住无法正常运行。 错误选择路径：由于信息的错误或处理的不及时，机器人造成错乱。 自身无法运行：自身程序陷入死循环无法正常运作。 图书馆我们可以将环境简化，只将人和书架归为障碍物，书架是固定的已知的，所以我们可 以事先将他们的坐标确定，而人我们可以通过红外线热源探测仪去测量或则或是感知和原有 的设定进行对照。 1.2.最小路径 当未遇到障碍物时，我们采用 Dijkstra 算法或 BUG 来计算最短路径。首先最短的路径是指 在带权的有向图中寻找从指定起点到终点的一条具有最小权值总和的路径问题，如果把权值 看成是弧的长度属性，那么目标路径就是从起点到终点的最短路径。 首先我们要计算二点之间的最短距离。根据已经设计的电子地图，我们需要制定一个各个目 的地到达的优先顺序。实际行走中我们还会遇到一些不可知的障碍物，我会在 1.3 中详细说 明如何绕过障碍物的 BUG 算法。电子地图路径优先算法： S=起点位置 Tt=终点位置(T1.T2,T3....)表示各个终点的位置 建立一个二维数组 M,将每个坐标点以二维坐标的现实存储在二维数组当中 Select path() For(i=l；i<=总目标点数；i¨) {利用改进BUG算法计算当前位置与第i个目标 点的最短路径，记为path【i】存入临时库中 机器人按照路径规划前行} 再次利用改进BUG算法计算最后一个目标点到 还书处的最短路径，记为p【i】【总目标点+l】存入临时 库中 机器人直接从最后一个目标点返回还书处} 1.3，遇到障碍物时的 BUG 算法 当测到有实际物体的距离大于我们所归定的距离时，我们并将其视为障碍物。首先，我们需 要等待 2 分钟，探测物体是否消失若物体消失，我们则按照既定的路线执行，若物体未能消 失，我们则通过切线滚动的 BUG 算法来实现绕行。BUG 算法是一个局部的最优算法，机器人 只在它所能探测到的地方进行最优的路径选择。此算法的优点是根据环境来决定是否扩大探 测范围，避免构造整个环境窗口，降低时间复杂度，增加计算的效率。 

1.3.1 绕障碍物滚动行走模式 机器会探测前方扇形区域内作为滚动窗口的信息来规划路径，当探测到障碍物时，障碍物可 见定点必定分布在原定路线的二侧。把障碍物的顶点分为二组，图中以蓝色点来表示。左侧 顶点表示为 L，右侧顶点表示为 R。另外设 O1，O2，分别为二组当中距离路径直线最远的点。 D=d1(xo1)+d2(xo2)+d3(ox).（xo1,xo1 是当前机器人到 o1,o2 点的距离,ox 代表障碍物到目 标的距离，引入这个数值主要是避免当局部信息不完整时，机器人进入错误的数据路径） 判断d1和d2,的距离，如果d12 倍的机器人碰撞直径（H为线段GK 与CD 的交点）；第三步：设线段CD 为虚 拟障碍物，陷阱区域中的障碍物由凹边形变为凸多边形，机器人按切线算法向正右方前进至 越过D 点大于2 倍的机器人直径到M 点；第四步：机器人到达M 点就表示已经走出陷阱区域， 于是重新按上文提出的切线算法进行路径规划。 备注：分离点：绕过障碍物时探索线的起点登入点：：当前点可见的障碍物上最近的顶点 引用康 亮，赵春霞，郭剑辉 

（南京理工大学计算机与科学技术学院，南京 210094） 未知环境下改进的基于BUG算法的移动机器人路径规 划