第13卷第2期 智能系统学报 Vol.13 No.2 2018年4月 CAAI Transactions on Intelligent Systems Apr.2018 D0:10.11992/tis.201610006 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20170317.1937.008.html 移动机器人全覆盖信度函数路径规划算法 曹翔，俞阿龙 (淮阴师范学院物理与电子电气工程学院，江苏淮安223300) 摘要：针对移动机器人全覆盖路径规划问题，给出一种基于栅格信度函数的全覆盖路径规划算法。目的是为了控 制移动机器人能够遍历工作区域中所有的可到达点，同时保证能够自动避开障碍物。首先，根据环境的信息对栅格 地图进行赋值，使用不同的函数值表示障碍物、已覆盖栅格和未覆盖栅格：其次，判断机器人是否陷入死区引入不同 方向信度函数，对栅格函数值进行调整；最后，机器人根据栅格信度函数值规划覆盖路径。本文所提及的算法不仅能 够引导移动机器人实现工作区域的全覆盖而且能够快速逃离死区，实现覆盖路径的低重复率。仿真实验中，通过与 生物启发神经网络算法的比较，证明本文提及算法有更高的覆盖效率。 关键词：移动机器人；全覆盖路径规划；方向信度函数：栅格信度函数；重复率 中图分类号：TP273文献标志码：A文章编号：1673-4785(2018)02-0314-08 中文引用格式：曹翔，俞阿龙.移动机器人全覆盖信度函数路径规划算法J.智能系统学报，2018,13(2：314-321. 英文引用格式：CAO Xiang,YU Along.Complete-coverage path planning algorithm of mobile robot based on belief functionJ. CAAI transactions on intelligent systems,2018,13(2):314-321. Complete-coverage path planning algorithm of mobile robot based on belief function CAO Xiang,YU Along (School of Physics and Electronic Electrical Engineering,Huaiyin Normal University,Huaian 223300,China) Abstract:For the complete-coverage path planning of mobile robot,an algorithm based on grid belief function was pro- posed.The goal is to control a mobile robot to traverse all reachable locations in work area,while guarantee automatic obstacle avoidance.Firstly,the grid map is assigned with values according to the information of the environment,the obstacles,covered grids and uncovered grids are represented by using different function values,secondly,judging if a mobile robot is caught in dead zone or not,different direction belief functions are introduced to adjust the grid function values,lastly,the robot programs the covered path according to the grid belief function value.The proposed algorithm can guide a robot to realize full coverage of work area,rapidly escape from dead zone and achieve a low repetition rate of the covered path.In the simulation experiments,by compared with bio-inspired neural network algorithm,the al- gorithm proposed in the paper was verified to own high coverage efficiency. Keywords:mobile robot,complete-coverage path planning,direction belief function;grid belief function;repetition rate 移动机器人全覆盖路径规划是地形探测、地面成全覆盖路径规划需要解决3个问题4刀：1)需遍历 资源勘探、地面清洁、战地侦查等任务的重要组成 工作区域内除障碍物以外的全部区域；2)在遍历过 部分1。作为移动机器人领域核心研究问题之一， 程中有效避开所有障碍物；3)在遍历过程中要尽量 全覆盖路径规划一直受到广泛关注。移动机器人完 避免路径重复，缩短移动距离。迄今为止，关于全 收稿日期：2016-10-09.网络出版日期：2017-03-17. 覆盖路径规划的方法多种多样，各有优劣，主要的 基金项目：江苏省高校自然科学研究重大项目(16KJA460003) 通信作者：曹翔.E-mail:cxeffort@126.com. 方法可以分为：行为覆盖法)、区域分割法2、神
DOI: 10.11992/tis.201610006 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20170317.1937.008.html 移动机器人全覆盖信度函数路径规划算法 曹翔，俞阿龙 （淮阴师范学院 物理与电子电气工程学院，江苏 淮安 223300） 摘 要：针对移动机器人全覆盖路径规划问题，给出一种基于栅格信度函数的全覆盖路径规划算法。目的是为了控 制移动机器人能够遍历工作区域中所有的可到达点，同时保证能够自动避开障碍物。首先，根据环境的信息对栅格 地图进行赋值，使用不同的函数值表示障碍物、已覆盖栅格和未覆盖栅格；其次，判断机器人是否陷入死区引入不同 方向信度函数，对栅格函数值进行调整；最后，机器人根据栅格信度函数值规划覆盖路径。本文所提及的算法不仅能 够引导移动机器人实现工作区域的全覆盖而且能够快速逃离死区，实现覆盖路径的低重复率。仿真实验中，通过与 生物启发神经网络算法的比较，证明本文提及算法有更高的覆盖效率。 关键词：移动机器人；全覆盖路径规划；方向信度函数；栅格信度函数；重复率 中图分类号：TP273 文献标志码：A 文章编号：1673−4785(2018)02−0314−08 中文引用格式：曹翔, 俞阿龙. 移动机器人全覆盖信度函数路径规划算法[J]. 智能系统学报, 2018, 13(2): 314–321. 英文引用格式：CAO Xiang, YU Along. Complete-coverage path planning algorithm of mobile robot based on belief function[J]. CAAI transactions on intelligent systems, 2018, 13(2): 314–321. Complete-coverage path planning algorithm of mobile robot based on belief function CAO Xiang，YU Along (School of Physics and Electronic Electrical Engineering, Huaiyin Normal University, Huaian 223300, China) Abstract: For the complete-coverage path planning of mobile robot, an algorithm based on grid belief function was proposed. The goal is to control a mobile robot to traverse all reachable locations in work area, while guarantee automatic obstacle avoidance. Firstly, the grid map is assigned with values according to the information of the environment, the obstacles, covered grids and uncovered grids are represented by using different function values; secondly, judging if a mobile robot is caught in dead zone or not, different direction belief functions are introduced to adjust the grid function values; lastly, the robot programs the covered path according to the grid belief function value. The proposed algorithm can guide a robot to realize full coverage of work area, rapidly escape from dead zone and achieve a low repetition rate of the covered path. In the simulation experiments, by compared with bio-inspired neural network algorithm, the algorithm proposed in the paper was verified to own high coverage efficiency. Keywords: mobile robot; complete-coverage path planning; direction belief function; grid belief function; repetition rate 移动机器人全覆盖路径规划是地形探测、地面 资源勘探、地面清洁、战地侦查等任务的重要组成 部分[1-3]。作为移动机器人领域核心研究问题之一， 全覆盖路径规划一直受到广泛关注。移动机器人完 成全覆盖路径规划需要解决 3 个问题[4-7] ：1) 需遍历 工作区域内除障碍物以外的全部区域；2) 在遍历过 程中有效避开所有障碍物；3) 在遍历过程中要尽量 避免路径重复，缩短移动距离。迄今为止，关于全 覆盖路径规划的方法多种多样，各有优劣，主要的 方法可以分为：行为覆盖法[8-9] 、区域分割法[10-12] 、神 收稿日期：2016−10−09. 网络出版日期：2017−03−17. 基金项目：江苏省高校自然科学研究重大项目 (16KJA460003). 通信作者：曹翔. E-mail：cxeffort@126.com. 第 13 卷第 2 期 智 能 系 统 学 报 Vol.13 No.2 2018 年 4 月 CAAI Transactions on Intelligent Systems Apr. 2018
第2期 曹翔，等：移动机器人全覆盖信度函数路径规划算法 ·315· 经网络法31等。 数没有最优值，在实现算法时只能通过反复实验确 2000年Balch等1提出一种移动机器人行为覆 定，参数的设定存在人为不确定因素，从而影响其 盖路径规划方法，机器人根据简单的移动行为，尝 在线应用。 试性地覆盖工作区域，如果遇到障碍物，则执行对 对此，本文在栅格地图的基础上，引入方向信 应的转向命令。这种方法是一种以时间换空间的低 度函数的概念，提出一种移动机器人全覆盖信度函 成本策略，如不计时间可以达到全覆盖。该算法无 数路径规划策略。该策略计算量小、路径重复率 需了解整个作业区全貌，也不用依赖过多的传感 低，使得机器人不仅能够完成工作区域全覆盖任 器，处理器运算量也很小，是一种性价比很高的方 务，而且能够快速逃离死区。算法包括3个部分： 案。但是，行为全覆盖算法工作效率低，路径规划 )根据地面环境的状态对栅格地图进行赋值，使用 策略过于简单，面对复杂地形机器人经常无法逃离 不同的函数值表示障碍物、已覆盖栅格和未覆盖栅 死区四。 格；2)引入方向信度函数对栅格信度函数值进行优 为了使机器人能够逃离死区，同时减少算法的 化；3)机器人根据栅格信度函数进行覆盖路径规 计算量，Jin等o提出一种基于时空信息的全局导航 划。本文提出的基于栅格信度函数的移动机器人全 与局部导航组合的算法。该算法一方面能够通过局 覆盖路径规划算法能够实现动态工作区域的全覆盖， 部计算代替不必要的全局计算，减少了实时决策时 与生物启发神经网络算法相比有更短的覆盖路径。 局部最优导航的计算量；另一方面通过分层的方式 使机器人能够逃离死区。但是在局部与全局的转换 1 基于栅格信度函数的全覆盖路径规 过程中，当周围没有未覆盖的区域时，机器人需要 划算法 扩大邻近区域的面积来寻找未覆盖区域，这将导致 全覆盖路径规划是指移动机器人以尽可能低的 覆盖效率的降低，尤其是当未覆盖区域距离机器人 较远时以 路径重复率遍历工作区域中的全部可到达点，它包 含两个方面的技术指标，即区域覆盖率和路径重复 近年来，神经网络算法被应用到全覆盖路径规 划中1。利用神经网络的自学习、并行性等特性。 率。本文以弓形路径移动方式为基础，引入方向信 增强机器人的“智能”，提高覆盖效率。受神经网络 度函数对机器人移动路径进行优化，完成对工作区 结构与栅格地图单元类似的启发，加拿大学者S.X 域的全覆盖的同时降低路径重复率。 Yang1s.t6等提出一种基于生物启发神经网络的移 1.1栅格位置性质函数 动机器人全覆盖路径规划算法，将需要全覆盖的二 为了避免机器人与障碍物发生碰撞，防止机器 维栅格地图单元与生物启发神经网络的神经元一 人对同一栅格单元重复覆盖，将对栅格地图进行赋 对应起来，机器人实现全覆盖的实时路径规划是由 值。依据每个栅格的性质赋不同的信度函数值，表 神经元的活性值和机器人的上一位置产生的。该算 示出每个栅格的状态信息92。本节以二维的栅格 法完全根据栅格地图单元的性质（未搜索单元、已 地图为例说明怎样对栅格进行信度赋值。图1(a) 搜索单元还是障碍物)，决定神经元的输入，直接计 显示的是一个二维的栅格地图，工作区域被分成了 算神经元的活性值，不存在神经网络学习过程，算 9个栅格，其中黑色栅格表示被障碍物占领，白色栅 法实时性好，同时可以自动避障与逃离死区。 格表示自由空间，P。表示机器人当前所在的位置。 最近，Yan等在文献15-16的基础上，进一步 根据式(1)对栅格位置性质函数x,赋值，如栅格 将生物启发神经网络应用到水下机器人全覆盖路径 6表示障碍物，则被赋值为-o;栅格1、2、3、4、5、7、 规划中。该算法根据声呐传感器获取的信息，利用 8表示自由未被覆盖单元，则被赋值为1；栅格P。表 信息融合技术构建动态水下环境地图，根据水下感 示已被覆盖单元，则被赋值为0.5。 知的环境地图性质确定生物启发神经网络中神经元 (1, 该单元未覆盖 的活性值，水下机器人通过比较邻近神经元活性值 0.5,该单元被覆盖 (1) 进行路径规划，完成对工作区域的全覆盖，该方法 该单元是障碍物 将水下环境的地图构建与全覆盖路径规划有机结 式中x,表示第广个栅格的位置性质函数值。同时为 合，得到一套完整的水下机器人感知环境与全覆盖 了避免同一个栅格的反复覆盖，在此约定栅格被多 搜救方法。 覆盖一次，其位置性质函数值就减少0.5。假如栅 但是基于生物启发神经网络的全覆盖算法计算 格P。被覆盖过一次，其位置性质函数值为0.5；如果 量大，同时此种方法中神经网络模型的衰减率等参 栅格P被覆盖了两次，其位置性质函数值为0
经网络法[13-16]等。 2000 年 Balch 等 [8]提出一种移动机器人行为覆 盖路径规划方法，机器人根据简单的移动行为，尝 试性地覆盖工作区域，如果遇到障碍物，则执行对 应的转向命令。这种方法是一种以时间换空间的低 成本策略，如不计时间可以达到全覆盖。该算法无 需了解整个作业区全貌，也不用依赖过多的传感 器，处理器运算量也很小，是一种性价比很高的方 案。但是，行为全覆盖算法工作效率低，路径规划 策略过于简单，面对复杂地形机器人经常无法逃离 死区[9]。 为了使机器人能够逃离死区，同时减少算法的 计算量，Jin 等 [10]提出一种基于时空信息的全局导航 与局部导航组合的算法。该算法一方面能够通过局 部计算代替不必要的全局计算，减少了实时决策时 局部最优导航的计算量；另一方面通过分层的方式 使机器人能够逃离死区。但是在局部与全局的转换 过程中，当周围没有未覆盖的区域时，机器人需要 扩大邻近区域的面积来寻找未覆盖区域，这将导致 覆盖效率的降低，尤其是当未覆盖区域距离机器人 较远时[11-12]。 近年来，神经网络算法被应用到全覆盖路径规 划中[13-14]。利用神经网络的自学习、并行性等特性， 增强机器人的“智能”，提高覆盖效率。受神经网络 结构与栅格地图单元类似的启发，加拿大学者 S. X. Yang [15-16]等提出一种基于生物启发神经网络的移 动机器人全覆盖路径规划算法，将需要全覆盖的二 维栅格地图单元与生物启发神经网络的神经元一一 对应起来，机器人实现全覆盖的实时路径规划是由 神经元的活性值和机器人的上一位置产生的。该算 法完全根据栅格地图单元的性质 (未搜索单元、已 搜索单元还是障碍物)，决定神经元的输入，直接计 算神经元的活性值，不存在神经网络学习过程，算 法实时性好，同时可以自动避障与逃离死区。 最近，Yan[17]等在文献[15-16]的基础上，进一步 将生物启发神经网络应用到水下机器人全覆盖路径 规划中。该算法根据声呐传感器获取的信息，利用 信息融合技术构建动态水下环境地图，根据水下感 知的环境地图性质确定生物启发神经网络中神经元 的活性值，水下机器人通过比较邻近神经元活性值 进行路径规划，完成对工作区域的全覆盖，该方法 将水下环境的地图构建与全覆盖路径规划有机结 合，得到一套完整的水下机器人感知环境与全覆盖 搜救方法。 但是基于生物启发神经网络的全覆盖算法计算 量大，同时此种方法中神经网络模型的衰减率等参 数没有最优值，在实现算法时只能通过反复实验确 定，参数的设定存在人为不确定因素，从而影响其 在线应用[18]。 对此，本文在栅格地图的基础上，引入方向信 度函数的概念，提出一种移动机器人全覆盖信度函 数路径规划策略。该策略计算量小、路径重复率 低，使得机器人不仅能够完成工作区域全覆盖任 务，而且能够快速逃离死区。算法包括 3 个部分： 1) 根据地面环境的状态对栅格地图进行赋值，使用 不同的函数值表示障碍物、已覆盖栅格和未覆盖栅 格；2) 引入方向信度函数对栅格信度函数值进行优 化；3) 机器人根据栅格信度函数进行覆盖路径规 划。本文提出的基于栅格信度函数的移动机器人全 覆盖路径规划算法能够实现动态工作区域的全覆盖， 与生物启发神经网络算法相比有更短的覆盖路径。 1 基于栅格信度函数的全覆盖路径规 划算法 全覆盖路径规划是指移动机器人以尽可能低的 路径重复率遍历工作区域中的全部可到达点，它包 含两个方面的技术指标，即区域覆盖率和路径重复 率。本文以弓形路径移动方式为基础，引入方向信 度函数对机器人移动路径进行优化，完成对工作区 域的全覆盖的同时降低路径重复率。 1.1 栅格位置性质函数 ∞ 为了避免机器人与障碍物发生碰撞，防止机器 人对同一栅格单元重复覆盖，将对栅格地图进行赋 值。依据每个栅格的性质赋不同的信度函数值，表 示出每个栅格的状态信息[19-22]。本节以二维的栅格 地图为例说明怎样对栅格进行信度赋值。图 1(a) 显示的是一个二维的栅格地图，工作区域被分成了 9 个栅格，其中黑色栅格表示被障碍物占领，白色栅 格表示自由空间，Pc 表示机器人当前所在的位置。 根据式 (1) 对栅格位置性质函数 xj 赋值，如栅格 6 表示障碍物，则被赋值为- ；栅格 1、2、3、4、5、7、 8 表示自由未被覆盖单元，则被赋值为 1；栅格 Pc 表 示已被覆盖单元，则被赋值为 0.5。 xj = 1, 该单元未覆盖 0.5, 该单元被覆盖 −∞, 该单元是障碍物 (1) 式中 xj 表示第 j 个栅格的位置性质函数值。同时为 了避免同一个栅格的反复覆盖，在此约定栅格被多 覆盖一次，其位置性质函数值就减少 0.5。假如栅 格 Pc 被覆盖过一次，其位置性质函数值为 0.5；如果 栅格 Pc 被覆盖了两次，其位置性质函数值为 0。 第 2 期 曹翔，等：移动机器人全覆盖信度函数路径规划算法 ·315·
·316· 智能系统学报 第13卷 向信度函数值，即机器人下一步可能移动的8个邻 近栅格的优化函数值。 下一步OmW △ 当前位9 前一步 (xre yre) 在pyp) (a)路径选择方向 图2未陷入死区方向信度函数 0.5 0.75 Fig.2 The direction belief function in the free zone 机器人陷入死区是指它的周边相邻区域，或者 是边界，或者是障碍物，或者是已覆盖过的区域。 0.25 AUV 0.75 只有从死区逃离出来，才能继续完成全覆盖任务， 而逃离死区的路径，直接决定着全覆盖的路径重复 率。当机器人陷入死区后，为了让机器人以尽可能 0 0.25 0.5 短的路径逃离死区，本文提及的算法不再以当前位 置与下一步位置的移动角之差作为方向向导，而是 (b)各个栅格方向信度函数值 将当前位置与距离最近未覆盖栅格位置和下一步位 图1栅格地图 置的角度差作为移动的方向向导，引导机器人快速 Fig.1 The grid map 逃离死区。机器人陷入死区后的方向信度函数定义 1.2方向信度函数 为y;=cos△9，其中移动方向角之差△p,为 为了降低路径重复率，提高覆盖效率，对机器 Aj =or-0;=latan2(yT,-yp.,XT,-xp.)- (4) 人的移动路径进行优化，引入方向信度函数y。y定 atan2(ye-ypxp-xp.) 义为 式中：△是关于机器人当前位置和下一可能位置连 △8 线与机器人当前位置和最近未覆盖栅格连线夹角， 1- I' 机器人未陷入死区 (2) 如图3所示。(，y)为距离当前位置最近未覆盖 cos△p,机器人陷入死区 栅格的位置；是机器人当前位置和最近未覆盖栅 式(2)中方向信度函数的定义分为两种情况， 格位置之间的角度。式中△g,∈0，π]，当前位置与 当机器人未陷入死区时，y,是机器人当前位置与下 最近未覆盖栅格位置和下一步位置的角度差越小， 一位置移动方向角之差△8，的函数，是关于前一位置 方向信度函数越大，使得机器人移动方向始终指向 Pp、当前位置p和可能为下一位置p,的函数。此时 最近未覆盖的栅格。 方向信度函数为，=1-9，机器人移动方向角之 y最近未覆盖橱 格位置（① 差△9，表示为 (xnvn) △9，=9，-0.= latan2(Vn,-yp.:Xp -xp.)-atan2(ye.-ye,xp.-xp) (3) (xiVi) 式中：(xpe,ype)、(XFp:Yre)和(xpyp)分别为地图上机器 人的当前位置、前一步和下一步的位置坐标：是机 99 当前位置y) 器人前一步和当前位置之间的角度；0是机器人当 前位置和下一步位置之间的角度；△9∈0，π]，如 图2所示，若△0=0，则机器人沿着直线移动；若 图3陷入死区方向信度函数 △0，=立，则往相反方向移动。假设在图1的栅格地 Fig.3 The direction belief function in the dead zone 图中，机器人当前在中心栅格位置，前一步在栅格 13路径选择策略 5的位置，图1(b)给出了机器人各个相邻栅格的方 在栅格地图中，全覆盖路径规划问题就演变为
1.2 方向信度函数 yj yj 为了降低路径重复率，提高覆盖效率，对机器 人的移动路径进行优化，引入方向信度函数 。 定 义为 yj = 1− ∆θj π , 机器人未陷入死区 cos∆φj , 机器人陷入死区 (2) yj ∆θj pp pc pj yj = 1− ∆θj π ∆θj 式 (2) 中方向信度函数的定义分为两种情况， 当机器人未陷入死区时， 是机器人当前位置与下 一位置移动方向角之差 的函数，是关于前一位置 、当前位置 和可能为下一位置 的函数。此时 方向信度函数为 ，机器人移动方向角之 差 表示为 ∆θj = θj −θc = |atan 2(ypj −ypc , xpj − xpc )−atan 2(ypc −ypp , xpc − xpp )| (3) (xPc, yPc) (xPp, yPp) (xP j, yP j) θc θj ∆θj ∈ [0,π] ∆θj = 0 ∆θj = π 式中： 、 和 分别为地图上机器 人的当前位置、前一步和下一步的位置坐标； 是机 器人前一步和当前位置之间的角度； 是机器人当 前位置和下一步位置之间的角度； ，如 图 2 所示，若 ，则机器人沿着直线移动；若 ，则往相反方向移动。假设在图 1 的栅格地 图中，机器人当前在中心栅格位置，前一步在栅格 5 的位置，图 1(b) 给出了机器人各个相邻栅格的方 向信度函数值，即机器人下一步可能移动的 8 个邻 近栅格的优化函数值。 yj = cos∆φj ∆φj 机器人陷入死区是指它的周边相邻区域，或者 是边界，或者是障碍物，或者是已覆盖过的区域。 只有从死区逃离出来，才能继续完成全覆盖任务， 而逃离死区的路径，直接决定着全覆盖的路径重复 率。当机器人陷入死区后，为了让机器人以尽可能 短的路径逃离死区，本文提及的算法不再以当前位 置与下一步位置的移动角之差作为方向向导，而是 将当前位置与距离最近未覆盖栅格位置和下一步位 置的角度差作为移动的方向向导，引导机器人快速 逃离死区。机器人陷入死区后的方向信度函数定义 为 ，其中移动方向角之差 为 ∆φj = φT −θj = |atan 2(yT j −ypc , xT j − xpc )− atan 2(ypj −ypc , xpj − xpc )| (4) ∆φj (xT j, yT j) φT ∆φj ∈ [0,π] 式中： 是关于机器人当前位置和下一可能位置连 线与机器人当前位置和最近未覆盖栅格连线夹角， 如图 3 所示。 为距离当前位置最近未覆盖 栅格的位置； 是机器人当前位置和最近未覆盖栅 格位置之间的角度。式中 ，当前位置与 最近未覆盖栅格位置和下一步位置的角度差越小， 方向信度函数越大，使得机器人移动方向始终指向 最近未覆盖的栅格。 1.3 路径选择策略 在栅格地图中，全覆盖路径规划问题就演变为 (a) 䌛ᒰ䔵᠕ऽ 7 8 1 5 4 3 6 Pc 2 0.5 0.75 1 0.25 AUV 0.75 0 0.25 0.5 (b) र͖ᴱᵨऽԍᏒܩը 图 1 栅格地图 Fig. 1 The grid map Y O X ̷̬ₑ ᑿݹѹ㒚 ₑ̬ݹ (xpj, ypj) (xpc, ypc) (xpp, ypp) Δθj θj θc 图 2 未陷入死区方向信度函数 Fig. 2 The direction belief function in the free zone Y O X (xpj,ypj) ᑿݹѹ㒚 (xpc,ypc) Δφj ̷̬ₑ ᰬ䓽᱖㺲Ⰲᴱ ᵨѹ㒚 (xTj,yTj) θj φT 图 3 陷入死区方向信度函数 Fig. 3 The direction belief function in the dead zone ·316· 智 能 系 统 学 报 第 13 卷
第2期 曹翔，等：移动机器人全覆盖信度函数路径规划算法 ·317· 寻找机器人的下一个移动位置，只有准确找出了该 陷入死区。此时方向信度函数调整为y=cos△9， 位置，才能使机器人自主规划出一条切实可行的无 保证机器人向着未覆盖的区域移动。图5（©）显示 碰撞且重复率低的移动路径。为了避开障碍物并且 了机器人逃离死区的过程，图中黑色线段表示机器 能够完成工作区域的全覆盖，根据栅格位置性质函 人逃离死区的路径。通过图5中机器人路径的选择 数和方向信度函数，定义一个综合栅格信度函数F, 过程可知，本文提及的栅格信度函数全覆盖算法不 路径选择的原则是机器人始终向着综合栅格信度函 仅能够使机器人躲避障碍物，而且可以快速的逃离 数值最大的方向运动。其定义为 死区。 p←Fp,=max{F=x+cyj=1,2,…,k(5) 进一步分析机器人未陷入死区时每一步路径选 式中：p表示机器人下一个行驶位置；c是一个权值 择，表1列出了图5(a)中前6步机器人邻近位置的 常数，0<c<1;k是与当前栅格P相邻的栅格个数。 栅格信度函数值。如表所示，机器人初始位置是 根据式（⑤）可以发现机器人选择下一步路径的时 (1,1),由于靠近边界只有3个邻近栅格可以作为下 候，同时考虑了栅格的状态位置和转向，使得规划 步的位置，根据式(1)、(2)、（⑤）计算出其邻近栅格 出来的路径尽可能保持直行，减少转向。针对图 信度函数值分别为1.375、1.250和1.500，根据路径 1所示的栅格地图进行路径选择，首先根据式(1)确 选择策略选择最大值1.500对应的(x,y+1)作为下一 定每个栅格的位置性质函数x；由于机器人此时没 步的位置，即取(1,2)为机器人的下一步移动位置。 有进入死区，再根据式(2)和(3)计算出每个栅格的 随即(1,2)作为机器人的当前位置继续选择路径。 方向信度函数y(如图1(b)所示)：最后根据式(5)计 按照上述过程，(1,3)、(1,4)、(1,5)、(1,6)、(1,7)依次作 算出每一个栅格的综合信度函数（如图4所示），机 为机器人第3步、第4步、第5步、第6步、第7步 器人选择综合信度函数值最大的栅格5作为下一步 的位置。 运行的位置。 当机器人陷入死区以后，采用y,=cos△P,的方 向信度函数逃离死区。表2列出了图5(c)机器人 1.25 1.375 1.5 逃离死区过程中的栅格信度函数。如表所示，机器 人移动到(20,12)时陷入死区，此时离机器人当前位 置最近的未覆盖栅格是(20,10)，根据式(1)、(2)、 (⑤)计算出其邻近栅格信度函数值分别为-0、-0.646 AUV 1.375 0.500、0.147和-0.500，根据路径选择策略选择最大 值0.500对应的(x-1,y)作为下一步的位置，即取 (19,12)为机器人的下一步移动位置。随即(19,12) 0.5 1.125 1.25 作为机器人的当前位置继续选择路径。按照上述过 程，机器人依次选择(18,12)、(17,12)、(16,12) 图4各个栅格综合信度函数值 (15,11)作为移动位置。当机器人移动到(16,10)时 Fig.4 The comprehensive belief function of each grid 逃离死区。 为了进一步说明机器人的路径选择策略，图5 2仿真实验分析 显示了二维环境中基于栅格信度函数路径选择策略 的路径规划效果（设置参数c=0.5)。如图5(a)所 仿真实验设置工作区域的大小为100mxI00m, 示，机器人从起点(1,1)出发，在方向信度函数y,= 其中随机分布着各种形状的障碍物。本文提及的算 1-△的约束下，上下迂回来选择路径，保证了路径 法是在栅格地图中对移动机器人的全覆盖路径规划 T 进行研究，因此需对工作区域构建栅格地图。仿真 的规整和方向改变最少的效果。从栅格位置性质函 实验中设每个栅格面积为5m×5m,那么工作区域 数值来看，机器人覆盖过一次的地方，函数值变为 被构建为20×20的栅格地图。为了讨论路径规划算 0.5,而未覆盖过的地方，函数值为1，维持栅格位置 法效果，将每个机器人都视为质点，不考虑其形状， 性质函数值最高，“吸引”机器人前往。当机器人运 同时假设机器人是可以全方位运动的。所有的仿真 动到(2,20)时，右边出现障碍物，而根据本文算法的 实验设置参数c=0.5。本节通过动态障碍物环境中 定义障碍物的位置信度函数值为-。由于机器人 仿真实验，证明本文提及的栅格信度函数算法能够 总是选择栅格信度函数值最大栅格作为下一步移动 自动避开障碍物、逃离死区完成对工作区域的全覆 位置，因此在路径规划过程中将自动规避这些障碍 盖。同时，通过与生物启发神经网络算法的比较， 物区域。图5(b)显示了当机器人移动到(20,12)时 本文提及的算法有更高的覆盖效率
Fj 寻找机器人的下一个移动位置，只有准确找出了该 位置，才能使机器人自主规划出一条切实可行的无 碰撞且重复率低的移动路径。为了避开障碍物并且 能够完成工作区域的全覆盖，根据栅格位置性质函 数和方向信度函数，定义一个综合栅格信度函数 ， 路径选择的原则是机器人始终向着综合栅格信度函 数值最大的方向运动。其定义为 pj ⇐ FPj = max{Fj = xj +cyj , j = 1,2,···, k} (5) pj c 0 < c < 1 k pc xj yj 式中： 表示机器人下一个行驶位置； 是一个权值 常数， ； 是与当前栅格 相邻的栅格个数。 根据式 (5) 可以发现机器人选择下一步路径的时 候，同时考虑了栅格的状态位置和转向，使得规划 出来的路径尽可能保持直行，减少转向。针对图 1 所示的栅格地图进行路径选择，首先根据式 (1) 确 定每个栅格的位置性质函数 ；由于机器人此时没 有进入死区，再根据式 (2) 和 (3) 计算出每个栅格的 方向信度函数 (如图 1(b) 所示)；最后根据式 (5) 计 算出每一个栅格的综合信度函数 (如图 4 所示)，机 器人选择综合信度函数值最大的栅格 5 作为下一步 运行的位置。 c = 0.5 yj = 1− ∆θj π ∞ 为了进一步说明机器人的路径选择策略，图 5 显示了二维环境中基于栅格信度函数路径选择策略 的路径规划效果 (设置参数 )。如图 5(a) 所 示，机器人从起点 (1,1) 出发，在方向信度函数 的约束下，上下迂回来选择路径，保证了路径 的规整和方向改变最少的效果。从栅格位置性质函 数值来看，机器人覆盖过一次的地方，函数值变为 0.5，而未覆盖过的地方，函数值为 1，维持栅格位置 性质函数值最高，“吸引”机器人前往。当机器人运 动到 (2,20) 时，右边出现障碍物，而根据本文算法的 定义障碍物的位置信度函数值为- 。由于机器人 总是选择栅格信度函数值最大栅格作为下一步移动 位置，因此在路径规划过程中将自动规避这些障碍 物区域。图 5(b) 显示了当机器人移动到 (20,12) 时 陷入死区。此时方向信度函数调整为 yj = cos∆φj ， 保证机器人向着未覆盖的区域移动。图 5(c) 显示 了机器人逃离死区的过程，图中黑色线段表示机器 人逃离死区的路径。通过图 5 中机器人路径的选择 过程可知，本文提及的栅格信度函数全覆盖算法不 仅能够使机器人躲避障碍物，而且可以快速的逃离 死区。 (x, y+1) 进一步分析机器人未陷入死区时每一步路径选 择，表 1 列出了图 5(a) 中前 6 步机器人邻近位置的 栅格信度函数值。如表所示，机器人初始位置是 (1,1)，由于靠近边界只有 3 个邻近栅格可以作为下 一步的位置，根据式 (1)、(2)、(5) 计算出其邻近栅格 信度函数值分别为 1.375、1.250 和 1.500，根据路径 选择策略选择最大值 1.500 对应的 作为下一 步的位置，即取 (1,2) 为机器人的下一步移动位置。 随即 (1,2) 作为机器人的当前位置继续选择路径。 按照上述过程，(1,3)、(1,4)、(1,5)、(1,6)、(1,7) 依次作 为机器人第 3 步、第 4 步、第 5 步、第 6 步、第 7 步 的位置。 yj = cos∆φj ∞ (x−1, y) 当机器人陷入死区以后，采用 的方 向信度函数逃离死区。表 2 列出了图 5(c) 机器人 逃离死区过程中的栅格信度函数。如表所示，机器 人移动到 (20,12) 时陷入死区，此时离机器人当前位 置最近的未覆盖栅格是 (20,10)，根据式 (1)、(2)、 (5) 计算出其邻近栅格信度函数值分别为– 、–0.646、 0.500、0.147 和–0.500，根据路径选择策略选择最大 值 0.500 对应的 作为下一步的位置，即取 (19,12) 为机器人的下一步移动位置。随即 (19,12) 作为机器人的当前位置继续选择路径。按照上述过 程，机器人依次选择 (18,12)、(17,12)、(16,12)、 (15,11) 作为移动位置。当机器人移动到 (16,10) 时 逃离死区。 2 仿真实验分析 100 m× 5 m×5 m 20×20c = 0.5 仿真实验设置工作区域的大小为 100 m， 其中随机分布着各种形状的障碍物。本文提及的算 法是在栅格地图中对移动机器人的全覆盖路径规划 进行研究，因此需对工作区域构建栅格地图。仿真 实验中设每个栅格面积为 ，那么工作区域 被构建为 的栅格地图。为了讨论路径规划算 法效果，将每个机器人都视为质点，不考虑其形状， 同时假设机器人是可以全方位运动的。所有的仿真 实验设置参数 。本节通过动态障碍物环境中 仿真实验，证明本文提及的栅格信度函数算法能够 自动避开障碍物、逃离死区完成对工作区域的全覆 盖。同时，通过与生物启发神经网络算法的比较， 本文提及的算法有更高的覆盖效率。 AUV 1.25 1.375 1.5 −∞ 1.375 0.5 1.125 1.25 图 4 各个栅格综合信度函数值 Fig. 4 The comprehensive belief function of each grid 第 2 期 曹翔，等：移动机器人全覆盖信度函数路径规划算法 ·317·
·318· 智能系统学报 第13卷 未搜索单元。已搜索单元 18 1.0 16 14 0.5 0 -0.5 -10 0 10 10 20 x/m 10 x/m 0 m (a)机器人未陷入死区的移动路径 b)机器人未陷入死区的栅格信度函数 未搜索单元 已搜索单元■障碍物 18 1.0 6 AN 14 死区 0.5 0 10 -0.5 -1.0 20 10 10 10 230 x/m x/m (c)机器人陷入死区 (d机器人陷入死区的栅格信度函数 未搜索单元已搜索单元 0 1.0 0.5 12 0 ,10 -0.5 20 10 10 10 15 20 x/m 0 x/m (©)机器人逃离死区的移动路径 (①机器人逃离死区的栅格信度函数 图5机器人路径选择过程 Fig.5 The process of robot's path selection 表1机器人前7步的栅格信度函数值 表2机器人逃离死区的栅格信度函数值 Table 1 The grid belief function of robot for the first sev- Table 2 The grid belief function of robot escaping from en steps the dead zone 邻近位置 (1.1)(12)(13)(1,4)(15)(16) 邻近位置(20,12)(19,12)(18,12)(17,12)(16,12)(15,11) (x+1.+1) 1.3751.3751.3751.3751.3751.375 (x+1.+1) 0.1460.1460.1460.1460.000 (x+1,y) 1.2501.2501.2501.2501.2501.250 (x+1,y) 0.0000.0000.0000.000 -00 (x+1,1) 1.1251.1251.1251.1251.125 (x+1,1) -0.646-0.646-0.646-0.6461.500 x,上1) 0.5000.5000.5000.5000.500 (x-1) -00 -00 -00 -00 -00 0.854 (x-1,-1) (x-1,-1) -0.646-0.646-0.646-0.6460.8540.500 (x-1,y) (x-1,y)0.5000.5000.5000.5000.5000.147 (x-1,+1) (x-1,y+1)0.1470.1470.1470.1470.147-0.500 (x,+1) 1.5001.5001.5001.5001.5001.500 x,+1)-0.5000.0000.0000.0000.0000.147 下一步位置(1,2)(1,3)(1.4)(1,5)(1.6)(1,7刀 下一步位置(19,12)(18,12)(17,12)(16,12)(15,11)(16,10)
表 1 机器人前 7 步的栅格信度函数值 Table 1 The grid belief function of robot for the first seven steps 邻近位置 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (x+1, y+1) 1.375 1.375 1.375 1.375 1.375 1.375 (x+1, y) 1.250 1.250 1.250 1.250 1.250 1.250 (x+1, y–1) — 1.125 1.125 1.125 1.125 1.125 (x, y–1) — 0.500 0.500 0.500 0.500 0.500 (x–1, y–1) — — — — — — (x–1, y) — — — — — — (x–1, y+1) — — — — — — (x, y+1) 1.500 1.500 1.500 1.500 1.500 1.500 下一步位置 (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) 表 2 机器人逃离死区的栅格信度函数值 Table 2 The grid belief function of robot escaping from the dead zone 邻近位置 (20,12) (19,12) (18,12) (17,12) (16,12) (15,11) (x+1, y+1) — 0.146 0.146 0.146 0.146 0.000 (x+1, y) — 0.000 0.000 0.000 0.000 –∞ (x+1, y–1) — –0.646 –0.646 –0.646 –0.646 1.500 (x, y–1) –∞ –∞ –∞ –∞ –∞ 0.854 (x-1, y–1) –0.646 –0.646 –0.646 –0.646 0.854 0.500 (x–1, y) 0.500 0.500 0.500 0.500 0.500 0.147 (x–1, y+1) 0.147 0.147 0.147 0.147 0.147 –0.500 (x, y+1) –0.500 0.000 0.000 0.000 0.000 0.147 下一步位置 (19,12) (18,12) (17,12) (16,12) (15,11) (16,10) 䌛ᒰߔ宀⮰ࡦ₧ڑᱦஔϦ᱖䮣) a( ጞ᥈㉎ٯࢁ 䯈ⶹ➕ 20 18 16 14 12 10 8 6 4 2 5 10 15 20 ٯࢁ᱖᥈㉎ y/m x/m ܩᴱᵨԍᏒ⮰ࡦ₧ڑᱦஔϦ᱖䮣) b( 1.0 0.5 0 −0.5 −1.0 20 0 20 y/m x/m z/m 10 10 ࡦ₧ڑᱦஔϦ䮣) c( ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ ڑ䮣 ࡦ₧ 20 18 16 14 12 10 8 6 4 2 5 10 15 20 y/m x/m ܩᴱᵨԍᏒ⮰ࡦ₧ڑᱦஔϦ䮣) d( 1.0 0.5 0 −0.5 −1.0 20 0 20 y/m x/m z/m 10 10 (e) ᱦஔϦ䔯⻧₧ࡦ宀⮰ߔ䌛ᒰ 20 18 16 14 12 10 8 6 4 2 ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ 5 10 15 20 䔯⻧₧ࡦ y/m x/m (f) ᱦஔϦ䔯⻧₧ࡦ⮰ᴱᵨԍᏒܩ 1.0 0.5 0 −0.5 −1.0 20 0 20 y/m x/m z/m 10 10 图 5 机器人路径选择过程 Fig. 5 The process of robot’s path selection ·318· 智 能 系 统 学 报 第 13 卷
第2期 曹翔，等：移动机器人全覆盖信度函数路径规划算法 ·319· 2.1 动态障碍物环境中全覆盖路径规划 区域的全覆盖效果。本节针对动态障碍物对区域全 工作区域中，动态障碍物对机器人的路径规划 覆盖的影响进行研究。如图6(a)所示，机器人从 具有不容忽视的影响，尤其是机器人在执行地面全 (1,1)位置出发执行全覆盖任务。障碍物3是动态 覆盖式的地形勘探和数据测量等任务时，动态障碍 的，起初在地图上占据着相关区域，机器人无法对 物的出现不仅威胁机器人安全，还会妨碍其对整个 该区域进行覆盖，如图6(b)所示。 未搜索单元▣已搜索单元■障碍物 未搜索单元©已搜索单元■障碍物 20 20 18 18 16 16 14 14 2 盖区域 .10 疮障碍物 开形成) 0 15 20 10 15 x/m x/m (a)工作区初始状态 (b)动态障碍物离开 未搜索单元。已搜索单元■障碍物 未搜索单元。已搜索单元 ■障碍物 20 18 18 ● 16 6 14 12 未覆盖区域 10 动态障碍物 离开形成) 10 15 20 5 10 15 20 x/m x/m (©)机器人运动到未覆盖区域 (d)完成区域全覆盖 图6动态障碍物环境中的机器人全覆盖路径规划 Fig.6 Complete-coverage path planning of robot in the dynamic obstacle environment 随着机器人任务的继续执行，当机器人移动至 算法能够实现动态障碍物环境中的全覆盖路径规划。 300步时，障碍物3离开（图6(b)所示），地图上相关 2.2不同算法的比较 区域的栅格性质函数值变为1。当机器人移动到 为了进一步考察本文所提算法的性能，本节将 (20,4)时，正好执行完障碍物3离开前的地图覆盖， 与其他算法对区域覆盖率、路径重复率、总行程等 如图6(c)所示。但是此时由于障碍物离开留下的 指标进行比较。图7显示了两种不同算法对20×20 区域需要覆盖，因此根据快速逃离死区的规则，机 且存在不规则障碍物的栅格区域进行全覆盖路径规 器人从(20,4)再度出发，前往最近未覆盖栅格(14,11)， 划的结果。采用文献[17]的生物启发神经网络全覆 此时机器人采用y=cos△p,方向信度函数策略，以 盖方式得到的路径规划效果如图7(a)所示。采用 尽量短的路径到达未覆盖的区域。图6(c)中黑色 本文提及的栅格信度函数算法的路径规划结果如 线段为(20,4)到未覆盖区的移动路径。当机器人到 图7(b)所示。两种路径规划方法进行效果对比的 达未覆盖栅格(14,1山)之后，机器人恢复为，=1A 评价指标如表3所示。通过图7和表3的结果可 的方向信度函数规则，继续执行区域覆盖任务直至 知，虽然两种方法的区域覆盖率均达到100%，但是 完成，最终路径效果见图6()。由此可见，栅格信度 机器人逃离死区的路径有较大的区别。生物启发神 函数值能够跟随环境地图信息的变化而变化，从而 经网络算法由于陷入死区的位置离未覆盖区域较 指导机器人执行新区域覆盖任务。因此本文提及的 远，神经元的活性传递需要较长时间，使得机器人
2.1 动态障碍物环境中全覆盖路径规划 工作区域中，动态障碍物对机器人的路径规划 具有不容忽视的影响，尤其是机器人在执行地面全 覆盖式的地形勘探和数据测量等任务时，动态障碍 物的出现不仅威胁机器人安全，还会妨碍其对整个 区域的全覆盖效果。本节针对动态障碍物对区域全 覆盖的影响进行研究。如图 6(a) 所示，机器人从 (1,1) 位置出发执行全覆盖任务。障碍物 3 是动态 的，起初在地图上占据着相关区域，机器人无法对 该区域进行覆盖，如图 6(b) 所示。 yj = cos∆φj yj = 1− ∆θj π 随着机器人任务的继续执行，当机器人移动至 300 步时，障碍物 3 离开 (图 6(b) 所示)，地图上相关 区域的栅格性质函数值变为 1。当机器人移动到 (20,4) 时，正好执行完障碍物 3 离开前的地图覆盖， 如图 6(c) 所示。但是此时由于障碍物离开留下的 区域需要覆盖，因此根据快速逃离死区的规则，机 器人从 (20,4) 再度出发，前往最近未覆盖栅格 (14,11)， 此时机器人采用 方向信度函数策略，以 尽量短的路径到达未覆盖的区域。图 6(c) 中黑色 线段为 (20,4) 到未覆盖区的移动路径。当机器人到 达未覆盖栅格 (14,11) 之后，机器人恢复为 的方向信度函数规则，继续执行区域覆盖任务直至 完成，最终路径效果见图 6(d)。由此可见，栅格信度 函数值能够跟随环境地图信息的变化而变化，从而 指导机器人执行新区域覆盖任务。因此本文提及的 算法能够实现动态障碍物环境中的全覆盖路径规划。 2.2 不同算法的比较 为了进一步考察本文所提算法的性能，本节将 与其他算法对区域覆盖率、路径重复率、总行程等 指标进行比较。图 7 显示了两种不同算法对 20×20 且存在不规则障碍物的栅格区域进行全覆盖路径规 划的结果。采用文献[17]的生物启发神经网络全覆 盖方式得到的路径规划效果如图 7(a) 所示。采用 本文提及的栅格信度函数算法的路径规划结果如 图 7(b) 所示。两种路径规划方法进行效果对比的 评价指标如表 3 所示。通过图 7 和表 3 的结果可 知，虽然两种方法的区域覆盖率均达到 100%，但是 机器人逃离死区的路径有较大的区别。生物启发神 经网络算法由于陷入死区的位置离未覆盖区域较 远，神经元的活性传递需要较长时间，使得机器人 (a) ҈ࡦ⟣݉ᔭ 20 18 16 14 12 10 8 6 4 2 5 10 15 20 ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ y/m x/m 20 18 16 14 12 10 8 6 4 2 (c) ᱦஔϦ䓼ݜߔ᱖㺲Ⰲࡦഋ ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ 5 10 15 20 ᱖㺲Ⰲࡦഋ 喋ߔᔭ䯈ⶹ➕ ⻧ᐬᒎ喌 y/m x/m (d) Ⴘࡦഋڔ㺲Ⰲ ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ 20 18 16 14 12 10 8 6 4 2 5 10 15 20 y/m x/m 20 18 16 14 12 10 8 6 4 2 (b) ߔᔭ䯈ⶹ➕⻧ᐬ 5 10 15 20 ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ ᱖㺲Ⰲࡦഋ 喋ߔᔭ䯈ⶹ➕ ⻧ᐬᒎ喌 y/m x/m 图 6 动态障碍物环境中的机器人全覆盖路径规划 Fig. 6 Complete-coverage path planning of robot in the dynamic obstacle environment 第 2 期 曹翔，等：移动机器人全覆盖信度函数路径规划算法 ·319·
·320· 智能系统学报 第13卷 长期停留在死区，需要更长的路径才能逃离死区。 3结束语 而栅格信度函数算法在机器人陷入死区后能通过调 整方向信度函数的方法快速的逃离死区。图7中黑 本文采用栅格信度函数算法解决了移动机器人 色线段显示了两种不同算法逃离死区的路径。虽然 全覆盖路径规划问题。仿真实验证明本文所提算法 两种算法在未陷入死区前机器人移动路径相同，但 在二维障碍物环境中，不仅能够实现动态障碍物工 是由于逃离死区的路径不同，导致两种算法的重复 作区域的全覆盖，而且还能够快速逃离死区，降低 覆盖栅格数，路径重复率、总行程等指标的差异。 了机器人路径的重复率，提高了覆盖效率。限于篇 从表3可见生物启发神经网络算法的重复覆盖的栅 幅，本文未讨论实际的二维环境栅格地图的构建以 格有39块，而栅格信度函数算法只有23块；生物 及机器人的形状、转向幅度、定位对全覆盖路径规 启发神经网络算法的路径重复率几乎是本文算法 划的影响，后续研究将把栅格地图构建与全覆盖路 的2倍：总行程后者比前者少16步。结果表明基于 栅格信度函数的算法可以有效降低路径重复率，缩 径规划结合，研究移动机器人对真实环境的感知与 短行程，对于机器人来说路径规划更适合控制，更 路径规划方法。 节省能源。 参考文献： 未搜索单元 205 [山]简毅，张月.移动机器人全局覆盖路径规划算法研究进展 16 与展望U.计算机应用，2014,34(10)：2844-2849,2864. JIAN Yi.ZHANG Yue.Complete coverage path planning algorithm for mobile robot:progress and prospect[J].Journ- 10 al of computer applications,2014,34(10):2844-2849, 2864 [2]YAN Mingzhong,ZHU Daqi.An algorithm of complete coverage path planning for autonomous underwater vehicles ②ooooooooooo3 10 5 [J].Key engineering materials,2011,467-469:1377-1385. Ym (a)生物启发神经网络算法 [3)莫宏伟，马靖雯.一种生物地理学移动机器人路径规划算 法U.智能系统学报，2015,10(5)：705-711. 未搜索单元已搜索单元■障碍物 0 MO Hongwei,MA Jingwen.A biogeography-based mobile 18 robot path planning algorithm[J].CAAI transactions on in- telligent systems,2015,10(5):705-711. 14 [4]LI Yan,CHEN Hai,JOO ER MENG,et al.Coverage path planning for UAVs based on enhanced exact cellular de- composition method[J].Mechatronics,2011,21(5):876- 885 [)]蒲兴成，赵红全，张毅.细菌趋化行为的移动机器人路径 88888888888 规划几.智能系统学报，2014.91)69-75. J 10 15 20 PU Xingcheng.ZHAO Hongquan,ZHANG Yi.Mobile ro- x/m b)栅格信度函数算法 bot path planning research based on bacterial chemotaxis[J]. CAAI transactions on intelligent systems,2014,9(1): 图7不同算法全覆盖路径规划结果 69-75 Fig.7 The results of complete-coverage path planning [6]KAPANOGLU M.ALIKALFA M.OZKAN M.et al.A with different algorithms pattern-based genetic algorithm for multi-robot coverage 表3不同算法全覆盖路径规划性能比较 path planning minimizing completion time[J].Journal of in- Table 3 Performance comparison of complete-coverage path planning with different algorithms telligent manufacturing,2012,23(4):1035-1045. [刀杜鹏桢，唐振民，陆建峰，等.不确定环境下基于改进萤火 算法指标 生物启发神经网络算法栅格信度函数算法 虫算法的地面自主车辆全局路径规划方法).电子学报， 区域覆盖率% 100 100 2014.42(3):616-624 重复覆盖区域块 39 23 DU Pengzhen,TANG Zhenmin,LU Jianfeng,et al.Global 路径重复率% 11.04 6.51 path planning for ALV based on improved glowworm 总行程步 392 376 swarm optimization under uncertain environment[J].Acta
长期停留在死区，需要更长的路径才能逃离死区。 而栅格信度函数算法在机器人陷入死区后能通过调 整方向信度函数的方法快速的逃离死区。图 7 中黑 色线段显示了两种不同算法逃离死区的路径。虽然 两种算法在未陷入死区前机器人移动路径相同，但 是由于逃离死区的路径不同，导致两种算法的重复 覆盖栅格数，路径重复率、总行程等指标的差异。 从表 3 可见生物启发神经网络算法的重复覆盖的栅 格有 39 块，而栅格信度函数算法只有 23 块；生物 启发神经网络算法的路径重复率几乎是本文算法 的 2 倍；总行程后者比前者少 16 步。结果表明基于 栅格信度函数的算法可以有效降低路径重复率，缩 短行程，对于机器人来说路径规划更适合控制，更 节省能源。 3 结束语 本文采用栅格信度函数算法解决了移动机器人 全覆盖路径规划问题。仿真实验证明本文所提算法 在二维障碍物环境中，不仅能够实现动态障碍物工 作区域的全覆盖，而且还能够快速逃离死区，降低 了机器人路径的重复率，提高了覆盖效率。限于篇 幅，本文未讨论实际的二维环境栅格地图的构建以 及机器人的形状、转向幅度、定位对全覆盖路径规 划的影响，后续研究将把栅格地图构建与全覆盖路 径规划结合，研究移动机器人对真实环境的感知与 路径规划方法。 参考文献： 简毅, 张月. 移动机器人全局覆盖路径规划算法研究进展 与展望[J]. 计算机应用, 2014, 34(10): 2844–2849, 2864. JIAN Yi, ZHANG Yue. Complete coverage path planning algorithm for mobile robot: progress and prospect[J]. Journal of computer applications, 2014, 34(10): 2844–2849, 2864. [1] YAN Mingzhong, ZHU Daqi. An algorithm of complete coverage path planning for autonomous underwater vehicles [J]. Key engineering materials, 2011, 467-469: 1377–1385. [2] 莫宏伟, 马靖雯. 一种生物地理学移动机器人路径规划算 法[J]. 智能系统学报, 2015, 10(5): 705–711. MO Hongwei, MA Jingwen. A biogeography-based mobile robot path planning algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(5): 705–711. [3] LI Yan, CHEN Hai, JOO ER MENG, et al. Coverage path planning for UAVs based on enhanced exact cellular decomposition method[J]. Mechatronics, 2011, 21(5): 876– 885. [4] 蒲兴成, 赵红全, 张毅. 细菌趋化行为的移动机器人路径 规划[J]. 智能系统学报, 2014, 9(1): 69–75. PU Xingcheng, ZHAO Hongquan, ZHANG Yi. Mobile robot path planning research based on bacterial chemotaxis[J]. CAAI transactions on intelligent systems, 2014, 9(1): 69–75. [5] KAPANOGLU M, ALIKALFA M, OZKAN M, et al. A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time[J]. Journal of intelligent manufacturing, 2012, 23(4): 1035–1045. [6] 杜鹏桢, 唐振民, 陆建峰, 等. 不确定环境下基于改进萤火 虫算法的地面自主车辆全局路径规划方法[J]. 电子学报, 2014, 42(3): 616–624. DU Pengzhen, TANG Zhenmin, LU Jianfeng, et al. Global path planning for ALV based on improved glowworm swarm optimization under uncertain environment[J]. Acta [7] 表 3 不同算法全覆盖路径规划性能比较 Table 3 Performance comparison of complete-coverage path planning with different algorithms 算法指标 生物启发神经网络算法栅格信度函数算法 区域覆盖率/% 100 100 重复覆盖区域/块 39 23 路径重复率/% 11.04 6.51 总行程/步 392 376 (a) ⩋➕ज़ࣽ⺊㏻㑽㐈ッ∁ 20 18 16 14 12 10 8 6 4 2 5 10 15 20 ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ y/m x/m (b) ᴱᵨԍᏒܩッ∁ 20 18 16 14 12 10 8 6 4 2 5 10 15 20 ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ x/m y/m 图 7 不同算法全覆盖路径规划结果 Fig. 7 The results of complete-coverage path planning with different algorithms ·320· 智 能 系 统 学 报 第 13 卷
第2期 曹翔，等：移动机器人全覆盖信度函数路径规划算法 ·321· electronica sinica,2014,42(3):616-624. ment based on D-S data fusion real-time map building[J]. [8]BALCH T.The case for randomized search[C]//Proceed- International journal of distributed sensor networks,2012, ings of Workshop on Sensors and Motion,IEEE Internation- 2012:567959,doi:10.1155/2012/567959 al Conference on Robotics and Automation.San Francisco. [18]朱大奇，颜明重.移动机器人路径规划技术综述.控制 CA:IEEE Press,2000:213-215. 与决策，2010,25(7八：961-967. [9]HABIB M A,ALAM M S,SIDDQUE N H.Optimizing Zhu Daqi,Yan Mingzhong.Survey on technology of mo- coverage performance of multiple random path-planning ro- bile robot path planning[J].Control and decision,2010, bots[.Paladyn,2012,3(1):11-22. 25(7):961-967. [10]JIN Xin,GUPTA S,LUFF J M,et al.Multi-resolution nav- [19]LEE TK,BAEK S H,CHOI Y H,et al.Smooth coverage igation of mobile robots with complete coverage of un- path planning and control of mobile robots based on high- known and complex environments[C]//Proceedings of resolution grid map representation[J].Robotics and 2012 American Control Conference.Montreal:IEEE Press, autonomous systems,2011,59(10):801-812 2012:4867-4872 [20]欧阳鑫玉，杨曙光.基于势场栅格法的移动机器人避障 [11]YAZICI A,KIRLIK G,PARLAKTUNA O,et al.A dy- 路径规划[J.控制工程，2014,21(1)：134137 namic path planning approach for multirobot sensor-based OUYANG Xinyu,YANG Shuguang.Obstacle avoidance coverage considering energy constraints[J].IEEE transac- path planning of mobile robots based on potential grid tions on cybernetics,2014,44(3):305-314. method[J].Control engineering of china,2014,21(1): [12]HSU P M,LIN Chunliang,YANG Mengyao.On the com- 134137. plete coverage path planning for mobile robots[J].Journal [21]郝宗波，洪炳镕，黄庆成.基于栅格地图的机器人覆盖路 of intelligent and robotic systems,2014,74(3/4):945-963. 径规划研究).计算机应用研究，2007,24(10)：56-58. [13)邱雪娜，刘士荣，宋加涛，等.不确定动态环境下移动机 HAO Zongbo,HONG Bingrong,HUANG Qingcheng. 器人的完全遍历路径规划[J].机器人，2006,28(6)： Study of coverage path planning based on grid-map[J].Ap 586-592. plication research of computers,2007,24(10):56-58. QIU Xuena,LIU Shirong,SONG Jiatao,et al.A complete [22]SIPAHIOGLU A,KIRLIK G,PARLAKTUNA O,et al. coverage path planning method for mobile robots in uncer- Energy constrained multi-robot sensor-based coverage path tain dynamic environments[J].Robot,2006,28(6): planning using capacitated arc routing approach[J].Robot- 586-592. ics and autonomous systems,2010,58(5):529-538 [14]GUO Yi,BALAKRISHNAN M.Complete coverage con- trol for nonholonomic mobile robots in dynamic environ- 作者简介： ments[C]//Proceedings of 2006 IEEE International Confer- 曹翔，男，1981年，讲师，博士，主 ence on Robotics and Automation.Orlando,FL,USA: 要研究方向为机器人搜索、围捕、路径 IEEE Press,2006:17041709 规划。 [15]YANG S X,LUO Chaomin.A neural network approach to complete coverage path planning[J].IEEE transactions on systems,man,and cybernetics,part B:cybernetics,2004, 34(1:718-724 [16]LUO Chaomin,YANG S X.A bioinspired neural network 俞阿龙，男，1964年，教授，博士， 主要研究方向为测控技术、传感器技 for real-time concurrent map building and complete cover- 术、应用电子技术。 age robot navigation in unknown environments[J].IEEE transactions on neural networks,2008,19(7):1279-1298. [17]YAN Mingzhong,ZHU Daqi,YANG S X.Complete cov- erage path planning in an unknown underwater environ-
electronica sinica, 2014, 42(3): 616–624. BALCH T. The case for randomized search[C]//Proceedings of Workshop on Sensors and Motion, IEEE International Conference on Robotics and Automation. San Francisco, CA: IEEE Press, 2000: 213–215. [8] HABIB M A, ALAM M S, SIDDQUE N H. Optimizing coverage performance of multiple random path-planning robots[J]. Paladyn, 2012, 3(1): 11–22. [9] JIN Xin, GUPTA S, LUFF J M, et al. Multi-resolution navigation of mobile robots with complete coverage of unknown and complex environments[C]//Proceedings of 2012 American Control Conference. Montreal: IEEE Press, 2012: 4867–4872. [10] YAZICI A, KIRLIK G, PARLAKTUNA O, et al. A dynamic path planning approach for multirobot sensor-based coverage considering energy constraints[J]. IEEE transactions on cybernetics, 2014, 44(3): 305–314. [11] HSU P M, LIN Chunliang, YANG Mengyao. On the complete coverage path planning for mobile robots[J]. Journal of intelligent and robotic systems, 2014, 74(3/4): 945–963. [12] 邱雪娜, 刘士荣, 宋加涛, 等. 不确定动态环境下移动机 器人的完全遍历路径规划[J]. 机器人, 2006, 28(6): 586–592. QIU Xuena, LIU Shirong, SONG Jiatao, et al. A complete coverage path planning method for mobile robots in uncertain dynamic environments[J]. Robot, 2006, 28(6): 586–592. [13] GUO Yi, BALAKRISHNAN M. Complete coverage control for nonholonomic mobile robots in dynamic environments[C]//Proceedings of 2006 IEEE International Conference on Robotics and Automation. Orlando, FL, USA: IEEE Press, 2006: 1704–1709. [14] YANG S X, LUO Chaomin. A neural network approach to complete coverage path planning[J]. IEEE transactions on systems, man, and cybernetics, part B: cybernetics, 2004, 34(1): 718–724. [15] LUO Chaomin, YANG S X. A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments[J]. IEEE transactions on neural networks, 2008, 19(7): 1279–1298. [16] YAN Mingzhong, ZHU Daqi, YANG S X. Complete coverage path planning in an unknown underwater environ- [17] ment based on D-S data fusion real-time map building[J]. International journal of distributed sensor networks, 2012, 2012: 567959, doi: 10.1155/2012/567959. 朱大奇, 颜明重. 移动机器人路径规划技术综述[J]. 控制 与决策, 2010, 25(7): 961–967. Zhu Daqi, Yan Mingzhong. Survey on technology of mobile robot path planning[J]. Control and decision, 2010, 25(7): 961–967. [18] LEE T K, BAEK S H, CHOI Y H, et al. Smooth coverage path planning and control of mobile robots based on highresolution grid map representation[J]. Robotics and autonomous systems, 2011, 59(10): 801–812. [19] 欧阳鑫玉, 杨曙光. 基于势场栅格法的移动机器人避障 路径规划[J]. 控制工程, 2014, 21(1): 134–137. OUYANG Xinyu, YANG Shuguang. Obstacle avoidance path planning of mobile robots based on potential grid method[J]. Control engineering of china, 2014, 21(1): 134–137. [20] 郝宗波, 洪炳镕, 黄庆成. 基于栅格地图的机器人覆盖路 径规划研究[J]. 计算机应用研究, 2007, 24(10): 56–58. HAO Zongbo, HONG Bingrong, HUANG Qingcheng. Study of coverage path planning based on grid-map[J]. Application research of computers, 2007, 24(10): 56–58. [21] SIPAHIOGLU A, KIRLIK G, PARLAKTUNA O, et al. Energy constrained multi-robot sensor-based coverage path planning using capacitated arc routing approach[J]. Robotics and autonomous systems, 2010, 58(5): 529–538. [22] 作者简介： 曹翔，男，1981 年，讲师，博士，主 要研究方向为机器人搜索、围捕、路径 规划。 俞阿龙，男，1964 年，教授，博士， 主要研究方向为测控技术、传感器技 术、应用电子技术。 第 2 期 曹翔，等：移动机器人全覆盖信度函数路径规划算法 ·321·
