第1期 肖国宝，等：一种基于改进Theta'的机器人路径规划算法 ·59. 三维路径规划比较常见的算法有A·[8]、Diskstra、 D·-lite、贪婪搜索、四/八叉树搜索9以及这些算法 的改进「1o1.采用的搜索策略如宽度优先、深度优 5 先、启发式、非启发式搜索等 经典的启发式搜索算法一A·算法是由P.E. Hart等在20世纪60年代提出的，该算法在各个领 域得到了广泛的应用[2].A·算法也是目前用来解 决游戏地图路径搜索问题最优的算法，但该算法只 图1城市环境模型 能用在格子环境中，这在一定程度上限制了其进一 Fig.1 Urban environment model 步的推广.Alex等在2007年提出了一种A*算法的 20 变种一Theta'算法31，突破了格子的限制，允许 16 》」 以任意角度改变路径的方向. 12 绿汤 启发函数是评定候选扩展节点的方法，以便确 定哪个节点最有可能在通向目标的最佳路径上，它 ® 将会影响到整个算法的性能和效果.在大部分启发 16 粉 式搜索算法中的启发函数只估算到起始点和目标点 八®12160 的代价，没有合理地利用障碍物信息，这会限制其用 图2普通环境模型 于解决机器人路径规划问题时的进一步推广。 Fig.2 Common environment model 本文将局部环境的障碍物对机器人产生的斥力 任意时刻，在二维地图中，机器人的运动方向有 作为惩罚函数引入到启发函数中，为机器人提供了 8个，如图3所示，机器人可以到达相邻栅格的各个 更加可靠的启发信息.首先，利用仿真实验的数据统 顶点；在三维地图中，机器人的运动方向有26个，如 计合理地选择惩罚函数权重，以确定启发函数；然后 图4所示，机器人可以到达相邻立方格的各个顶点 在此启发策略的基础上，改进A·算法的变种 Theta·算法，用PS_Theta·算法对路径进行平滑处 理，优化路径. 1算法描述 1.1三维环境模型 移动机器人环境模型问题就是机器人根据传感 图3二维运动方向 器的感知获得环境的二维或三维空间模型.单元分 Fig.3 The direction of movement in 2-D environment 解建模是典型的环境模型，其主要思想是将环境离 散化为若干个规则的相同大小的基本单元一三维 的立方格，通过二值信息便可以对障碍物和自由空 间进行标识，因此使用简单的传感器即可获得创建 地图的信息.然而，立方格的大小直接影响着移动机 器人环境信息存储量的大小和规划时间的长短，立 方格选得小，环境分辨率高，但环境信息存储量大， 图4三维运动方向 相应的干扰信号相对增加，使得决策工作量加大，最 Fig.4 The direction of movement in 3-D environment 终导致规划速度变慢，降低系统的实时性；当立方格 机器人路径规划问题就是在图中寻找一个从起 变大时，虽然抗干扰能力增强，但环境分辨率下 始点S到目标点T之间点的集合，并要求相邻点之 降，在密集障碍物环境中不利于规划出有效的路 间的线段连接没有经过障碍物， 径4 1.2改进启发函数 在Matlab7.6中建立2种常见的模型：1)城市环 在启发式搜索算法中，引入当前节点x的启发 境模型，如图1；2)普通环境模型，如图2.其中，将机器 式估价函数f(x),其函数的定义式为 人看作质点，不能碰到环境中的任何障碍物. f(x)=a×g(x)+B×h'(x). (1)