0 引言

移动机器人的目标搜索是指以单个或多个移动机器人在工作环境中对单个或多个目标进行搜索, 以获取其信息或对其操作, 任务执行过程中涉及同步定位与建图(SLAM)、运动控制、路径规划、目标识别、追-逃行为等共性技术^[1-2].移动机器人路径规划可分为全局路径规划、局部路径规划、任务规划等, 移动机器人在目标搜索时的路径规划通常被视为任务规划, 其目的在于根据任务需求按照最短距离、最短时间、最大可靠性等预期目标生成一条最优或次优的可行路径^[3-4].

针对移动机器人目标搜索任务的问题, 现有研究通常设置待搜索目标在工作环境内服从均匀分布, 并以最短距离作为指标规划出用于跟踪的路径, 旨在减少获取目标所需的时间, 该方法得到的路径通常接近于时间最优, 属于次优选择^[4-5].Sarmiento等^[6]发现以最短距离作为指标为目标搜索规划路径, 忽略了移动机器人目标搜索过程中的大量不确定性因素, 包括目标分布的不确定性、环境的不确定性等, 其假设通常与实际情况不符.为使机器人目标搜索策略与现实工作环境具有更高的契合度, 文献[6]将概率方法引入到目标搜索中, 模仿人类搜索目标的策略构建相应的模型, 提出了以期望时间作为机器人目标搜索的优化指标, 并认为最优期望时间在很多情况下比最短距离方法更具有合理性, 但是该方法的缺陷是假设目标在观测点处服从均匀分布且与可行面积成正比关系, 属于非常理想的情况, 与机器人的实际工作环境有一定差距.Espinoza等^[7]在文献[6]的基础上将概率模型由二维平面延伸至三维空间, 通过移动机械臂的手眼来扩展机器人视野, 减少机器人本体移动, 从而构建了面向移动机械臂的最优期望时间目标搜索方法.文献[8]发现当工作空间存在回路时, 其在回路中的搜索方向会导致期望时间的差异, 并结合概率密度函数的实时更新进一步优化了机器人目标搜索的期望时间.文献[9]提出了以最大可靠性为优化指标的目标搜索方法, 尝试以最优安全性作为指标为移动机器人目标搜索规划路径.在基于观测序列规划的目标搜索问题中, 客观事实表明了目标在各观测点处的概率并不相等, 以最短距离为指标规划出的路径与以最短期望时间生成的路径并不一致.因此, 在以节省时间为目标的移动机器人目标搜索任务中, 长度最短的路径并非最佳选择.

针对以上问题, 本文按照最优期望时间指标进行路径寻优, 采用分层式规划策略.尽管蚁群算法在机器人路径规划中的应用不是很理想, 但其在旅行商问题等组合优化问题方面具有良好的表现, 所以本文上层拓扑序列规划采用蚁群算法搜索期望时间最优的观测点序列.因上层规划只给出节点序列, 无法提供适于机器人跟踪的局部路径, 故在下层特征地图中采用改进快速随机搜索树(RRT)算法(collision information detection-RRT, CID-RRT)生成易于机器人跟踪的轨迹.该算法在RRT的基础上引入碰撞信息检测和非完整约束, 从而使RRT可更快逃脱局部极小值, 规划出的路径更适用于非完整约束移动机器人跟踪^[10].

1 概率测算模型的构建

对于目标搜索策略而言, 移动机器人目标搜索采用的方法可分为连续与离散.其中: 连续搜索方法是模仿人类在工作环境中的搜索方式, 但对全局优化而言效率不高; 离散规划的思想是将整个观测区域划分为若干子观测区域, 在其区域中选取观测点, 并依次访问.针对两种方法的优势, 一些研究者将两者融合, 上层采用全局优化, 下层采用局部规划.基于最优期望时间的目标搜索定义如下.

定义1  对于移动机器人的工作环境$ S, U_{k}(V_{k}) $表示观测点$ V_{k} $所对应的可视区域, 并且该区域应满足

$ \begin{align} U_{k}(V_{k})\in S, \end{align} $

(1)

观测点应服从

$ \begin{align} V = \{ {{V}_{k}}|{{V}_{k}}\in S, k = 1, 2, \ldots, n\}. \end{align} $

(2)

其中: $ V $是观测点集, $ {V}_{k} $是环境$ S $中的第$ k $个观测点.基于期望时间的目标搜索路径规划问题是指在$ S $中生成观测点$ {V}_{k} $的最优访问路径.

在移动机器人的实际工作环境中, 物体的属性各异, 使得其出现在不同区域的概率通常差异非常大, 例如: 笔记本电脑出现在书房的概率远远高于出现在卫生间的概率, 平底锅出现在厨房的概率远远高于出现在卧室的概率.对此, 本文引入概率密度因子, 以$ {{U}_{k}}( {{\rho }_{k}}, {{V}_{k}}) $表示观测点$ {{V}_{k}} $所对应的可见区域, 其中$ {{\rho }_{k}} $是$ {{U}_{k}}( {{\rho }_{k}}, {{V}_{k}}) $的密度因子.该密度因子与物体出现在该区域的概率成正相关的关系, 表达式如下所示:

$ \begin{align} {{p}_{k}} = \frac{{\rm Area}( {{U}_{k}}( {{\rho }_{k}}, {{V}_{k}}) ){{\rho }_{k}}}{ \sum\limits_{k = 1}^{n}{({\rm Area}( {{U}_{k}}( {{\rho }_{k}}, {{V}_{k}} )){{\rho }_{k}})}}. \end{align} $

(3)

其中: $ n $表示观测点的数量; $ {{p}_{k}} $表示目标在观测点$ {{V}_{k}} $所覆盖区域存在的概率; $ {\rm Area}({{U}_{k}}({{\rho}_{k}}, {{V}_{k}})) $为观测点$ {{V}_{k}} $能“看到”的区域, 且

$ \begin{align} {{U}_{k}}( {{\rho }_{k}}, {{V}_{k}})\in S. \end{align} $

(4)

假设移动机器人匀速运动, 且其速度$ v = 1\, {\rm m/s} $, 则时间$ {t}_{k} $为

$ \begin{align} {{t}_{k}} = {{L}_{k}}/v, \end{align} $

(5)

其中$ {{L}_{k}} $为从起始点开始到第$ k $个观测点的路径之和.

根据文献[7]中的离散搜索理论, 在机器人的工作环境$ S $中, 移动机器人搜索目标物体属于离散事件的范畴, 其目标的概率分布如下式所示:

$ \begin{align} p( V = {{V}_{k}}) = {{p}_{k}}, \; k = 1, 2, \ldots, n, \end{align} $

(6)

搜索目标所用的期望时间为

$ \begin{align} E(T) = {{t}_{1}}{{p}_{1}}+{{t}_{2}}{{p}_{2}}+\ldots+{{t}_{n}}{{p}_{n}} = \sum\limits_{k = 1}^{n}{{{t}_{k}}{{p}_{k}}}. \end{align} $

(7)

其中: $ {{t}_{k}} $表示机器人从起点开始到第$ k $个观测点的时间, $ {{p}_{k}} $表示机器人在观测点$ k $处存在的概率.累积分布函数$ f\left( T \right) $表示为

$E\left( T \right) = \int_0^\infty {\left( {1 - P\left( {T \le t} \right)} \right){\rm{dt}} = \int_0^\infty {\left( {1 - f\left( T \right)} \right){\rm{d}}\mathit{t}.} } $

(8)

以4个节点为例, 其累积分布函数的示意图如图 1所示^[6].

2 基于蚁群算法的上层拓扑序列规划算法

近年来, 在基于概率的移动机器人目标搜方法中, 国内外研究者通常采用分层规划模式来生成符合指定指标的最优或次最优路径, 即: 在上层规划中根据任务需求优化节点访问序列, 如: 文献[11]以贪婪算法搜索拓扑序列, 其优点是计算复杂度低, 缺点则是很难得到全局最优方案.本文采用蚁群算法(ant colony optimization, ACO)来代替贪婪算法, ACO属于启发式搜索, 通过信息素正反馈机制得到全局效果较好的节点序列.

ACO算法属于群体随机优化方法, 在环境复杂时易陷入局部极小, 故本文通过限定信息素阈值来提高ACO算法的全局优化能力.蚂蚁在寻找最优解的过程中会分泌信息素, 蚂蚁选择下一步节点主要依靠信息素及启发式函数, 蚂蚁路径构建主要依靠如下公式:

${P_k}\left( {i, j} \right) = \left\{ {\begin{array}{*{20}{l}} {\frac{{{{\left[ {\tau \left( {i, j} \right)} \right]}^c}{{\left[ {\eta \left( {i, j} \right)} \right]}^d}}}{{\sum\limits_{j \in A\left( r \right)} {{{\left[ {\tau \left( {i, j} \right)} \right]}^c}{{\left[ {\eta \left( {i, j} \right)} \right]}^d}} }}, j \in A\left( r \right);}\\ {0, j \notin A\left( r \right).} \end{array}} \right.$

(9)

其中: $ j $为蚂蚁$ k $选取的下一个节点; $ \tau({i}, {j}) $为节点$ i $、$ j $之间的信息素强度; $ \eta({i}, {j}) $为启发式因素, 是节点$ j $与目标点之间距离的倒数; $ c $为信息素影响权重; $ d $为启发式因素影响权重; $ {P}_{k}({i}, {j}) $为蚂蚁$ k $从节点$ i $前往节点$ j $的概率值; $ A $为不在蚂蚁$ k $禁忌表的节点集合.

随着时间的推移, 信息素也会随之逐渐消逝, 每只蚂蚁经过一个节点后都通过下式对局部信息素进行更新:

$ \begin{align} \tau (r, s) = (1 - \rho ) \cdot \tau (r, s) + \rho \cdot \Delta \tau (r, s). \end{align} $

(10)

每只蚂蚁完成一次搜索之后, 按照下述公式进行全局信息素的更新:

$ \begin{align} &\tau (r, s) = (1 - \rho )\tau (r, s) + \rho \sum\limits_{k = 1}^m {\Delta \tau _{r, s}^k}; \end{align} $

(11)

$ \begin{align} &\varDelta \tau _{r, s}^k = \begin{cases} {Q}/{L_{k }}, \; (r, s) \in {R_{k}};\\[2pt] 0, \; {\rm otherwise}. \end{cases} \end{align} $

(12)

其中: $ \rho $为信息素挥发因子, $ Q $为与信息素强度相关的一个常数, $ {{L}_{k}} $为蚂蚁$ k $构建的路径长度, $ (r, s)\in{{R}_{k}} $表示蚂蚁$ k $所经过的边$ (r, s) $属于最短路径.

信息素影响因子$ c $越大, 蚂蚁走之前走过的路的可能性越大, 该值过大会导致ACO算法收敛于局部最优.ACO算法中, 启发式因素影响权重对算法的影响程度由$ d $来决定, $ d $值越大, 说明蚂蚁在该点距离目标的最优期望时间的可能性越大, 但易陷入局部最小值.原始算法中, $ c $、$ d $的值通常为定值, 在初始阶段, 不能保证可行解中的每一个可行点都受信息素的影响, 故本文在ACO算法初始阶段将$ c $、$ d $设定为较小的值, 从而提高算法的全局搜索能力, 在每次迭代后都按照下式对$ c $、$ d $进行更新:

$ \begin{align} \begin{cases} c = ( {{c}_{\max }}-{{c}_{0}})\dfrac{N}{D}+{{c}_{0}}, \\[9pt] d = ( {{d}_{\max }}-{{d}_{0}})\dfrac{N}{D}+{{d}_{0}}. \end{cases} \end{align} $

(13)

其中: $ {{c}_{0}} $、$ {{d}_{0}} $分别表示$ c $、$ d $的起始值, $ N $为当前ACO算法的迭代次数, $ D $为最大迭代次数.当迭代次数达到最大迭代次数时, 便不再对$ c $、$ d $值进行更新, 记为$ {{c}_{\max }} $和$ {{d}_{\max }} $.

为了提高ACO算法解的质量, 抑制算法收敛于局部最优值, 应用最大最小蚂蚁法, 在每次信息素更新后, 对节点$ i $、$ j $之间信息素强度$ {{\tau}_{ij}} $的值按照下式进行限制:

$ \begin{align} \begin{cases} {{\tau }_{\min }}, \; {{\tau }_{ij}}<{{\tau }_{\min }};\\[2pt] {{\tau }_{ij}}, \; {{\tau }_{\min }}<{{\tau }_{ij}}<{{\tau }_{\max }};\\[2pt] {{\tau }_{\max }}, \; {{\tau }_{ij}}>{{\tau }_{\max }}. \end{cases} \end{align} $

(14)

其中: $ {{\tau}_{ij}} $为节点$ i $、$ j $之间的信息素强度, $ {{\tau }_{\min}} $、$ {{\tau }_{\max }} $为信息素区间的上下限.将各条路径的信息素集中在区间$ [{{\tau }_{\min }}, {{\tau }_{\max }}] $, 这样能够提高其他路径被搜索的可能性, 同时还能避免提前收敛于局部最优^[12].

由ACO算法得到最优的期望时间序列的步骤如下:

step 1: 参数的初始化, 其中蚂蚁的最大迭代次数为$ D $, 信息素的初始值为常数, 信息素增量为0, 信息素影响权值$ c $和启发式影响权值$ d $设为较小的常数.

step 2: 蚂蚁$ i( i = 1, 2, \ldots, m ) $从起始位置出发, 并将起始点加入到禁忌表中, 根据式(9)选择下一个节点, 将该节点加到禁忌表.

step 3: 得到寻优期望时间的节点序列, 按照$ E = \sum\limits_{i = 1}^{n}{{{t}_{i}}{{p}_{i}}} $评估该节点序列的期望时间.

step 4: 根据期望时间和节点序列, 按照式(11)和(12)更新全局信息素, 再根据式(13)对信息素影响因子和启发式因素影响权重的值进行更新.完成本轮迭代后, 将禁忌表清空, 若未超出最大迭代次数，则返回step 2.

step 5: 当迭代次数$ > $最大迭代次数时, 算法结束, 依据$ \min\Big(E = \sum\limits_{i = 1}^{n}{{{t}_{i}}{{p}_{i}}}\Big) $, 得到最优期望时间的节点序列.

3 基于改进RRT的下层局部路径规划

上层基于拓扑地图所获得的拓扑点序列, 属于路径寻优的概要路线, 并不适用于机器人直接跟踪.因此, 本文采用改进快速随机搜索树算法进行节点间的路径寻优, 根据局部环境信息, 避开环境中的不可行区域, 生成一条易于跟踪的无碰可行路径.

RRT算法的扩展过程如图 2所示, 选出随机树中距离随机生成的点$ {{V}_{\rm rand}} $最近的树节点$ {{V}_{\rm nearest}} $, 并连接这两点.$ {{V}_{\rm nearest}} $沿着该直线移动一个步长$ \zeta $, 生成新的暂时树节点$ {{V}_{\rm new}} $, 并进行可行性分析.可行性分析一共返回两个结果: 1)点$ {{V}_{\rm nearest}} $到点$ {{V}_{\rm new}} $的线段不完全在可行空间内, 说明发生了碰撞, 更新碰撞信息, 并将该方向置为已扩展, 优先考虑距已扩展随机树最远的方向尝试扩展.2)点$ {{V}_{\rm nearest}} $到点$ {{V}_{\rm new}} $的路径若满足全局障碍物约束, 则将新生成的树节点$ {{V}_{\rm new}} $加入到随机树中; 若点$ {{V}_{\rm new}} $距目标最终区域的距离小于最大允许距离$ \epsilon $, 则完成规划^[13].

为降低RRT算法的随机性, 引入目标偏好机制

$ \begin{align} f(x) = \begin{cases} 1, \; {\rm rand}(\; )>{\mu };\\ 0, \; {\rm rand}(\; )<{\mu }. \end{cases} \end{align} $

(15)

设置一个阈值$ {{\mu }} $, 如果随机因子大于阈值$ {{\mu }} $, 则在地图上随机选取一个点作为下一个节点的生长方向; 如果小于阈值$ {{\mu }} $, 则将终点作为随机目标点.这样随机搜索树就能够从起点开始生长, 把终点当作目标, 规划出一条效率更高的路径^[14].

为解决目标偏好RRT易陷入局部极小值的问题, 引入碰撞检测机制, 碰撞检测示意图如图 3所示.在地图中随机生成点$ {{V}_{\rm rand}} $, 然后通过截取一个步长确定点$ {{V}_{\rm temp}} $, 因点$ {{V}_{\rm temp}} $与障碍物发生碰撞, 故考虑点$ {{V}_{\rm nearest}} $的其他方向, 优先选择离已扩展随机树最远的方向, 这样能避免同一位置节点重复扩展, 最终选取点$ {{V}_{\rm new}} $作为扩展点加入到随机树中^[8].

扩展过程中每次发生碰撞都会更新随机树上节点的碰撞概率, 如图 4所示, $ {{V}_{\rm init}} $是初次扩展的母节点, 其后依据图 4的方式逐渐向外生长, 初始化时各个节点均为未发生碰撞的状态, 令每个新节点上的$ a $为0.把即将扩展的新节点最临近节点记为$ {{V}_{\rm nearest}} $, 即将扩展的新节点和起始点中间有$ r $个节点, 当即将扩展的新节点发生碰撞时, $ {{V}_{\rm nearest}} $节点发生碰撞的方向会被置为已扩展, 同时碰撞概率$ a $会相应增加$ {1}/{n} $, 其中$ n $为常数, $ {{V}_{\rm nearest}} $节点的母节点的$ a $会增加$ {1}/{{{n}^{2}}} $.以此类推, $ {{V}_{\rm nearest}} $的$ r $阶母节点的$ a $相应增加$ {1}/{{{n}^{r+1}}} $, 一直将$ a $的信息扩展到根节点.碰撞概率$ a $的大小会影响路径的伸展方向, $ a $值越小, 说明在该扩展方向上碰到障碍物的概率越小.选择碰撞几率较小的方向来扩展有利于随机树远离障碍物, 同时也能使随机树快速摆脱局部极小值, 若某个树节点的碰撞概率大于某个阈值或者该树节点的各个方向都是已扩展状态, 则认为该节点的扩展价值不大, 在扩展过程中将不考虑该节点.

基于上层拓扑图的改进ACO算法得到优化后的节点访问序列, 然后在下层规划中采用CID-RRT算法进行局部路径规划, 经过两层优化后得到基于最优期望时间目标搜索路径规划算法如图 5所示.

4 实验结果分析

为了验证本文所提出观测点的上层序列规划以及下层CID-RRT路径规划能够优化目标搜索的期望时间, 本文在Matlab环境中进行验证, 处理器为Intel Core i5-3230M CPU @2.60 GHz, 内存2 GB.首先单独验证观测点的序列规划能够缩短目标搜索的期望时间; 然后在不同的地图环境下分别检验ACO算法和贪心算法基于最优期望时间的上层观测点序列规划的优劣, 以及RRT和CID-RRT对点与点之间的路径规划对于移动机器人目标搜索期望时间大小的影响, 并结合算法运行时间进行分析.

优化期望时间所获路径, 与以概率或长度为单目标进行优化有一定区别, 其效果与所采用的地图有一定关联.本文所提出算法在有的地图中优势较大, 有的则较小, 但是从期望时间来看, 一定优于单独优化概率或长度所生成路径的期望时间.

为了验证以期望时间为指标生成的观测点访问序列能对目标搜索的期望时间进行优化, 本文在地图环境中选取一个点作为起始点, 记为$ {{V}_{0}} $, 其后随机生成9个观测点分别记为$ {{V}_{1}}\sim{{V}_{9}} $.为了验证对点的序列优化能够得到更佳的期望时间具有普遍性, 再随机生成9个观测点发现目标的概率.在地图环境中选取的起始点与随机生成的9个观测点如图 6所示, 各个观测点上发现目标的概率如表 1所示, ACO算法相关参数如表 2所示.

贪心算法获得的序列和最优期望时间的序列如图 7和图 8所示.贪心算法获得的序列为$ {{V}_{0}} $-$ {{V}_{5}} $-$ {{V}_{2}} $-$ {{V}_{7}} $-$ {{V}_{1}} $-$ {{V}_{6}} $-$ {{V}_{8}} $-$ {{V}_{4}} $-$ {{V}_{9}} $-$ {{V}_{3}} $, 其期望时间为118.29 s; 最优期望时间的序列为$ {{V}_{0}} $-$ {{V}_{9}} $-$ V_5 $-$ {{V}_{8}} $-$ {{V}_{7}} $-$ {{V}_{3}} $-$ {{V}_{4}} $-$ {{V}_{6}} $-$ {{V}_{1}} $-$ {{V}_{2}} $, 其期望时间为74.81 s.由此可见, 对观测点的序列规划能够显著减小期望时间.

为了验证对上层观测点的序列规划能够得到更佳期望时间的普遍性, 随机生成100组观测点发现目标的概率分布, 分别计算贪心算法获得的序列与最优期望时间的序列对应的期望时间, 所得结果如图 9所示.

为验证本文所提出算法在移动机器人目标搜索任务中的有效性, 首先在上层的拓扑序列规划中将本文的ACO算法与贪心算法进行比较; 然后在下层的点对点规划中将原始RRT算法与本文改进的CID-RRT算法进行比较.环境的不同导致搜索结果存在差异, 所以本文采用不同的工作环境来验证所提出两层优化算法的有效性, 并搭建工作环境$ {{S}_{1}} $和工作环境$ {{S}_{2}} $, 分别如图 10和图 11所示.

对于移动机器人目标搜索任务而言, 期望以最少的观测点覆盖待搜索的空间, 这样能减少算法处理时间及所需搜索的路径长度, 有利于提高移动机器人目标搜索的效率.面向期望时间的搜索任务举例说明: 如图 10、图 11所示, 黑色区域代表障碍物, 为不可行区间, 其余区域为可行区域.$ {{V}_{0}} $为目标搜索的起始点, 通过对实验环境进行人工分析, 选取5个观测点, 分别命名为$ {{V}_{1}} $、$ {{V}_{2}} $、$ {{V}_{3}} $、$ {{V}_{4}} $、$ {{V}_{5}} $, 代表在该点有一定的概率发现搜索的目标.

每个观测点发现目标的概率估算过程: 首先将地图环境栅格化, 若栅格表征障碍物, 则令栅格值为0;若栅格表征地图环境的可行区域, 则令其栅格值为1.假设每个观测点都是光源, 其发射的光能够穿过栅格值为1的栅格, 不能穿过栅格值为0的栅格, 故地图环境中能被某个光源照亮的栅格便是该观测点的可见区域; 然后结合模拟空间中目标出现的概率及位置的关联人工设置每个观测点的密度因子$ {\rho}_{k} $; 最后通过式(3)得到目标在每个观测点的分布概率, 每个点的概率分布如表 3所示.搜索任务要求: 移动机器人从节点$ {{V}_{0}} $开始, 按照访问序列依次搜索每个观测点一次, 直至最后一个观测点, 停止搜索, 视为完成目标搜索任务.

在$ {{S}_{1}} $下分别测试贪心-RRT算法、ACO-RRT算法、贪心-CID-RRT算法和本文所提出算法目标搜索过程中的期望时间的优化情况.在仿真工作环境下, 为了减小机器人本身的形状对目标搜索问题的影响, 将移动机器人视为质点处理.分别用贪心-RRT算法、ACO-RRT、贪心-CID-RRT算法和本文所提出算法对目标搜索的路径进行规划, 生成的路径如图 12 $ \sim $图 15所示.

从图 12 $ \sim $图 15可见, 上层序列规划中基于贪心算法得到的观测点访问顺序为$ {{V}_{0}} $-$ {{V}_{3}} $-$ {{V}_{2}} $-$ {{V}_{4}} $-$ {{V}_{1}} $-$ {{V}_{5}} $, ACO算法生成的观测点访问顺序为$ {{V}_{0}} $-$ {{V}_{1}} $-$ {{V}_{2}} $-$ {{V}_{3}} $-$ {{V}_{4}} $-$ {{V}_{5}} $, 上层序列规划中只提供了机器人移动的概要路线, 为避开实际工作环境的不可行区域, 在下层规划中分别采用RRT、CID-RRT生成无碰撞局部路径.将4种算法在环境$ {{S}_{1}} $中运行50次, 其结果平均值见表 4.从运行时间角度看, 贪心-RRT算法、ACO-RRT算法、贪心CID-RRT算法、本文算法的运行时间分别为16.07 s、9.01 s、13.75 s、8.20 s, 由这些数据可见, 上层观测点序列规划及下层RRT算法的改进显著缩短了算法的运行时间.从期望时间指标来看, 贪心-RRT算法、ACO-RRT算法、贪心CID-RRT算法、本文算法得到的期望时间分别为144.74 s、94.64 s、131.93 s、84.59 s, 从这些数据可见, 经过ACO算法得到最优期望时间观测点访问序列能够极大地减小期望时间, 下层局部路径规划对期望时间指标影响较小.由数据可见, 本文所提出算法在期望时间这一指标上有了明显的缩短, 较贪心-RRT算法提高了41.56%.

为了验证本文所提出算法在移动机器人不取回搜索这类问题中的有效性, 将工作环境复杂化, 记为$ {{S}_{2}} $, 使模型更加贴合于实际环境, 并按式(3)对各个观测点的概率进行更新, 更新后各个观测点的概率如表 5所示.按照上面的步骤重复实验, 生成的路径如图 16$ \sim $图 19所示.将4种算法分别在环境$ {{S}_{2}} $中运行50次, 其结果平均值见表 6.

从图 16 $ \sim $图 19可见, 上层的贪心算法和ACO算法得到的观测点访问序列分别为$ {{V}_{0}} $-$ {{V}_{4}} $-$ {{V}_{3}} $-$ {{V}_{1}} $-$ {{V}_{2}} $-$ {{V}_{5}} $、$ {{V}_{0}} $-$ {{V}_{5}} $-$ {{V}_{4}} $-$ {{V}_{3}} $-$ {{V}_{2}} $-$ {{V}_{1}} $.由表 6可见, 贪心-RRT算法、ACO-RRT算法、贪心CID-RRT算法、本文算法得到的期望时间分别为132.62 s、85.46 s、126.97 s、81.59 s, 从这些数据可见, 经过ACO算法得到最优期望时间观测点访问序列, 能够很大程度地降低期望时间, 下层局部路径规划对期望时间指标影响较小.从运行时间角度看, 贪心-RRT算法、ACO-RRT算法、贪心CID-RRT算法、本文算法的运行时间分别为24.49 s、15.14 s、21.06 s、12.72 s.从这些数据可见, 上层序列点的规划明显减低了运行时间.综上所述, 本文所提出算法生成的搜索路径显然比贪心-RRT、ACO-CID-RRT等生成的节点访问顺序更加合理, 期望时间更小, 提高的百分比为38.48.对比表 4和表 6可见, 当观测点的概率发生变化时, 期望时间也会随之发生变化.

5 结论

针对概率地图下的移动机器人目标搜索问题, 本文提出了一种基于最优期望时间的分层式目标搜索路径规划方法.本文引入目标概率分布函数描述目标在环境中的分布特点, 在上层拓扑序列规划中采用改进ACO算法优化观测节点的访问序列; 在下层的点对点精细路径规划中, 以CID-RRT生成易于机器人跟踪的无碰撞局部路径.实验结果显示, 本文所提出算法能显著缩短移动机器人搜索获得目标的预期时间, 且具有良好的实时性.