一种移动机器人的全覆盖路径规划方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN108981710A(43)申请公布日2018.12.11(21)申请号201810889370.3(22)申请日2018.08.07(71)申请人北京邮电大学地址100876北京市海淀区西土城路10号(72)发明人张雪松陈佳钟康学净明安龙(74)专利代理机构北京航智知识产权代理事务所(普通合伙)11668代理人程连贞陈磊(51)Int.Cl.G01C21/20(2006.01)G05D1/02(2006.01)权利要求书2页说明书6页附图8页(54)发明名称一种移动机器人的全覆盖路径规划方法(57)摘要本发明提供了一种移动机器人的全覆盖路径规划方法，该方法通过解决优化分割覆盖及这个过程中的路径规划问题实现的新的覆盖算法，该算法不需要预先知道地图空间环境，在覆盖的同时进行区域划分，并且这个过程是增量式覆盖，实现动态覆盖划分，并且可对动态出现的障碍物做实时选择规划，从而实现避障完成覆盖的双重任务。该方法不仅可以运用于拓扑环境规则的地图环境，而且同样适用于复杂区域环境空间，相比于牛耕分割算法更具优势。CN108981710ACN108981710A权利要求书1/2页1.一种移动机器人的全覆盖路径规划方法，其特征在于，该方法包括以下步骤：1)初始化机器人位置，首先在地图空间内容初始化一个移动机器人的位置，这个位置在覆盖过程中是任意选择的，随后通过安装在移动机器人上的传感器去增量式获取当前位置的未探索区域；2)最大联通区域确定，采用最大联通区域矩形来量化地图区域环境，使得移动机器人可以避免环境边缘和小区域因素影响，实现最大程度覆盖，最大联通区域矩形是包含未覆盖最大联通区域，双边平行于边界的矩形；3)牛耕行走覆盖区域，基于步骤2)中确定的矩形区域，在区域内部利用牛耕折返行走来覆盖每个矩形区域，完成特定增量区域内部路径的全覆盖；4)构造回溯列表，移动机器人从某一位置开始行走覆盖，在沿着一个方向行走过程中，边行走边寻找确定回溯点，所述回溯点是指当前位置存在自由可行路径的点，在增量覆盖的同时将这些回溯点添加到回溯列表记录下来，用作遇到关键点后回溯寻找依据；5)寻找最优回溯点，当移动机器人在遇到关键点位置后，通过回溯列表中存储的回溯点寻找一个最佳的回溯点作为当前点到下一个开始点的路径，要求当前关键点和回溯点的距离最小，利用欧氏距离或曼哈顿距离计算两点距离；6)A*路径规划，基于步骤5)中确定的回溯点，计算出一条从当前关键点到该回溯点的最短路径，选取A*算法作为路径规划方法，计算出最短路径，同时考虑行走过程中两点之间的障碍物信息，实现两点之间的避障处理。7)A*路径平滑，移动机器人在通过A*路径规划找到最短路径后，进一步对该路径做一次平滑处理，以尽可能减少覆盖步长，利用两点之间的可视性来确定路径中间的下一个位置。2.根据权利要求1所述的一种移动机器人的全覆盖路径规划方法，其特征在于，所述步骤4)中构造回溯列表的方法为：首先，判断当前点S是否为回溯点，根据其八邻域的代价和来计算，将当前点S的八邻域划分为自由区域点、封锁区域点和不关心点，以Ns＝{S1,S2,S3,S4,S5,S6,S7,S8}代表当前点S的八个方向：东，东北，北，西北，西，西南，南，东南，对于其中任意两个点Si∈Ns、Sj∈Ns定义一个评估函数：然后，定义一个目标函数μs来判断当前点S是否为回溯点：μs＝b(S1,S8)+b(S1,S2)+b(S5,S6)+b(S5,S4)+b(S7,S6)+b(S7,S8)(2)当μs≥1时，这个点即为回溯点。3.根据权利要求1所述的一种移动机器人的全覆盖路径规划方法，其特征在于，所述步骤5)中寻找最优回溯点的的方法为：Ssp＝argmin(f(S，SCP))(3)其中S∈L，L是回溯点列表，f(S，SCP)是距离代价函数，为两点之间的欧式距离，从回溯点列表中找到代价最小的下一个区域起始点Ssp。4.根据权利要求1所述的一种移动机器人的全覆盖路径规划方法，其特征在于，所述步骤6)中A*路径算法为：2CN108981710A权利要求书2/2页F＝G+H(4)F为当前点的距离代价值，G为起始点到当前点的实际距离，H为当前点到终点估计距离，每次选择代价函数值最小的进行行走，同时动态更新当前周围节点的估计代价并把决定行走的节点添加到父列表中，遇到终点后，通过逆向遍历父列表节点得到最终的规划路径。3CN108981710A说明书1/6页一种移动机器人的全覆盖路径规划方法技术领域[0001]本发明涉及移动机器人应用技术领域，尤其涉及一种移动机器人的全覆盖路径规划方法。背景技术[0002]全覆盖路径规划技术是指移动机器人从一个区域或者感兴趣的空间内找到一条穿过空间内所有点的路径，并且