第1期 肖国宝，等：一种基于改进Theta'的机器人路径规划算法 ·61 2)合理地将障碍物信息引入到启发函数后，可以得 到B9的线段，但E1不会成为B9的父节点，路径经过了 到更优的路径（当0=0时，A·算法采用的是普通的启 点C6.分析其原因在于Basic Theta的扩展方式[B],即 发策略)；3)当比例大于10时，各项数据指标趋于稳 2个顶点之间并不会随意形成父节点与子节点的关系 定；4)从多个指标衡量，最佳的比例为(/B)=(1/7). 6 8910 同样，采用其他启发式搜索算法作为测试算法，其数据 统计也能够反应出类似的趋势 1.3 Basic Theta*算法及其改进 Basic Theta算法是一种栅格路径规划算法，也 是A·算法的一种变种，其最大的改进在于它不要 求搜索树节点的父节点必须是其相邻的节点，因此 图5 Theta·算法规划轨迹演示 所求解路径的轨迹不限制在栅格的横向与纵向，理 Fig.5 The path planning demo of Theta'algorithm 论上允许以任意角度改变路径的方向[] 对路径进行平滑处理能够有效地优化路径20] 在估价函数的选取上，Basic Theta算法与A· 在经过Basic Theta*算法搜索找到路径后，中间经过 算法是一致的，故在使用其解决路径规划问题时，式 的点会大量减少，对其进一步平滑可以在较短的时 (3)作为其启发函数能够获取更优的路径.该算法 间内完成.具体平滑步骤如下. 在搜索中设置了2个表：OPEN表和CLOSE表. 1)获取Basic Theta规划后的路径轨迹节点集合 OPEN表保存了所有已扩展而未被考察过的节点， 2)选择集合中的起始点为平滑的基准点x。 CLOSE表记录了已被考察过的节点. 3)判断节点x与节点：是否相通，其中，节点z Basic Theta算法的步骤如下[9 为节点y的后续节点，节点y为节点x的后续节点： 1)初始化OPEN、CLOSE表，并将起始点S放入 ①若相通，去除中间节点y,即将节点x的后续节 到OPEN表中. 点修改为节点：，相应地，节点：的父节点为节点x; 2)如果OPEN表为空，表示没有找到路径，退出. ②否则，将基准点更新为节点y.如此循环，直 3)从OPEN表中找出最佳节点，作为当前节点 到节点y为目标点时，循环结束，转到4) x,并将其从OPEN表移到CLOSE表中 4)平滑完毕后，从目标点回溯到起始点，重新 4)判断当前节点x是否为目标点，如果是，则通 组成最佳的节点集合. 过节点x的父节点，一直遍历到起点，找到路径的节 由Basic Theta·算法与平滑步骤组成PS_The 点集合，搜索结束；否则，转至5) a算法，针对图5中Basic Theta算法规划的轨迹， 5)开始扩展当前节点x,找到当前节点的所有 PS_Theta算法能够进一步优化路径，如图6所示， 后续节点集合U并遍历集合内节点.如果遍历的节 光滑度是路径轨迹优越性的重要指标，光滑的轨迹 点y:不在OPEN或者CLOSE表中，将该节点y:加 能够有效提高机器人到达目标点的效率，可以尽可 入OPEN表中，计算该节点y:的估计值，并记录其 能地满足非完整性约束的条件」 父节点为x;否则，转至6). A 6 10 6)判断当前节点x的父节点x'与遍历的节点y 是否相通（节点之间的线段没有经过障碍物）： ①若相通，比较当前节点的父节点x'的代价 D g(x)和OPEN表中的代价g(y:),如果g(x)较小， 则更新表中的代价，并将节点y:的父节点指向x'； ②若不相通，直接比较当前节点的代价g(x)和 图6PS_Theta·算法规划轨迹演示 OPEN表中的代价g(y:),如果g(x)较小，则更新表 Fig.6 The path planning demo of PS Theta'algorithm 中的代价及父节点 2 7)按照估价值递增顺序，对OPEN表中的节点 仿真与结果分析 进行排序，转向2) 2.1二维随机环境下的路径规划问题 Basic Theta算法能够突破格子的限制，找到可行 本文在Matlab7.6环境下对算法进行验证和比 路径，但该算法存在着一些缺陷，即最先找到的路径并 较.在二维环境下，采用本文提出的改进启发式搜索 不能保证路径最短.如图5所示，最短路径应该是E1 策略，对A·[】、Basic Theta[ia]与PS_Theta算法