第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 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 移动机器人全覆盖路径规划是地形探测、地面 资源勘探、地面清洁、战地侦查等任务的重要组成 部分[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