资源免费
我们一直在努力

CN105922267B一种清扫机器人全覆盖遍历路径规划算法的设计方法[caired.com-彩红网3D模型下载CG模型平面素材专利检索网站源码]

本发明公开了一种清扫机器人全覆盖遍历路径规划算法的设计方法,它具体包括以下主要过程:利用Standard混沌方程生成矩形区域内的遍历清扫轨迹,矩形子区域分解,矩形迭代子区域的构造,最优子区域衔接路径的构造,矩形过渡子区域和重复子区域的构造,最优全覆盖遍历清扫连通图的构造,迭代子区域的自动衔接,可行区域内的全覆盖遍历清扫任务实现。本发明算法重复率低,覆盖率高,不存在清扫盲区;算法规划效率高,不需要确定起点和终点;算法简单,容易实现。本发明能够很好地满足机器人室内清扫并实现全覆盖遍历路径规划的任务。
CN105922267B一种清扫机器人全覆盖遍历路径规划算法的设计方法[caired.com-彩红网3D模型下载CG模型平面素材专利检索网站源码]
技术领域

[0001] 本发明涉及一种移动机器人路径规划方法,具体地说是一种清扫机器人全覆盖遍 历路径规划算法的设计方法,属于机器人路径规划技术领域。

背景技术

[0002] 随着经济建设的飞速发展和现代人生活节奏的加快,越来越多的人希望从繁重的 家务劳动中解脱出来,智能化清扫机器人的出现正好满足了这种需求。清扫机器人在室内 环境下运动,实现清扫、避障、路径规划等功能,这里尤其涉及到一项关键技术一一全覆盖 遍历路径规划算法,随着人工智能控制技术的发展和智能服务机器人的广泛应用,目前这 项技术已经得到了深入研究。

[0003] 全覆盖路径规划是指机器人以尽可能低的重复率遍历环境中的全部无障区,其目 标是在封闭区域内实现最大覆盖率和最小重复率的行走路径。目前已经涌现出了很多相关 算法。按照对环境的了解程度,全覆盖路径规划可分为两类:无环境模型的规划和基于环境 模型的规划。环境未知情况下主要采用随机算法。随机算法不需要进行规划,所需的硬件设 备的成本低,易实现,目前在大部分的家用清扫机器人里面仍旧使用。缺点在于重复率高, 效率低。不基于地图的非随机移动策略均有不同程度的盲目性,难以提高覆盖效率。为了提 高规划效率,大部分研究工作首先进行未知环境的地图重构,将未知环境转换为已知环境 进行路径规划。因此目前已知环境下的路径规划算法研究较多。

[0004] 已知环境下基于地图的全覆盖路径规划包括环境建模和路径搜索策略两个子问 题。环境建模方法主要有势场栅格表示法、可视图法和拓扑图法等。势场栅格表示法是将运 行区域划分为大致与机器人等大的小栅格,然后将根据机器人周围环境的状态对栅格进行 赋值。常用的基于赋值栅格的搜索算法有Yang.S.X和Meng.M提出的基于生物激励神经网络 算法,算法将房间划分成的小栅格作为一个神经元,通过生物激励神经网络模型的动力学 激励公式来判断栅格的激励值大小。该算法的缺陷是随着环境规模的增大,存储栅格信息 的空间也相应增大,路径规划的计算复杂程度也随之增大。杜元源等在发明专利“一种应用 于扫地机器人的改进势场栅格法”(专利号:CN201510701062.X)中,结合牛耕式全覆盖路径 规划算法使机器人在已知环境中规划出全局清扫路径,用以减少路径死节点与清扫盲点。 可视图建模方法中经典的搜索算法是Neumann de Carvalho R等提出的模板法。模板法将 机器人的行为划分为多种固定的模板,根据实际位置选择合适的模板,最后实现路径的遍 历。此算法有利于编程,但机器人对环境的识别能力应较高,不适合较为复杂的环境。基于 拓扑图模型常用的搜索算法是区域分解法。这种方法将机器人所要遍历的区域根据环境中 的障碍物或其它方法分为若干子区域,通过对各子区域的遍历实现对整个区域的遍历。这 种思想在很大的程度上降低了全局覆盖实现的难度,因此对区域分解法的研究是近年来的 主要趋势。

[0005] 区域分解法主要研究三方面的内容:目标区域的分解、子区域衔接和区域分解后 子区域内的遍历方法。对目标区域进行分解是区域分解法的第一步骤,分解的结果直接影 响各子区域间的衔接和各子区域内的遍历。因此目标区域的分解是至关重要的一步,也是 目前研究的较多而且较成熟的一个方面。区域分解算法主要有Latombe提出的Trapezoidal (梯形)分解法和Howie Choset提出的Boustrophedon (牛耕式)算法。Trapezoidal算法将环 境分解为梯形块,在单个分块中机器人通过往返移动来进行遍历。Boustrophedon算法是 Trapezoidal算法的改进,其目的是减少由于分块过多而造成的重复遍历。在此基础上衍生 出许多其他的算法。Wes I ey H Huang提出了线扫法,把“水平切割线”改为“任意倾角切割 线”,把减少转弯次数即子区域总高度作为确定倾角的目标。田春颖等提出了矩形分解算 法,对环境中的障碍物实行矩形化建模。在子区域分割工作完成之后,面临的就是子区域衔 接问题了。目前普遍用到的方法是将子区域中心点抽象出来,构造成求解旅行商问题的优 化连通图。求解方法有连续Hopfield人工神经网络,状态树搜索算法等。这些算法随着子区 域的变大,不能保证搜索全覆盖距离最短。单元分解后子区域内的遍历方法有随机算法、梳 状遍历和螺旋收缩式。随机算法最简单,但不能保证全覆盖,覆盖效率也较低。梳状遍历会 留有由障碍物遮挡引起的未覆盖区域,障碍物越多,未覆盖区域就越多。螺旋收缩式的优点 是可以走非矩形螺旋,缺陷是会留有未覆盖的区域,即陷入某个螺旋旋涡出不来,最终按结 束条件停止行进。

[0006] 基于区域分解的机器人全覆盖路径规划的方法可以将复杂的问题简单化,其中区 域分解法已经相对成熟,但是子区域的衔接和子区域内部的遍历的研究仍处于初级阶段, 子区域衔接算法复杂,子区域内的遍历区域存在重复遍历、盲区等问题。针对这些情况,设 计一个切实可行、易于工程实现和具有较优覆盖效率的的移动机器人全覆盖路径规划算 法,具有重要的理论研究意义和社会应用价值。

发明内容

[0007] 针对现有技术的不足,本发明提出一种清扫机器人全覆盖遍历路径规划算法的设 计方法,能够使清扫机器人遍历区域重复率低、覆盖率高且不存在清扫盲区,并且满足清扫 机器人在室内清扫实现全覆盖遍历任务。

[0008] 本发明解决其技术问题采取的技术方案是:一种清扫机器人全覆盖遍历路径规划 算法的设计方法,具体包括以下步骤:

[0009] 步骤一:选择Standard混纯方程及其仿射变换产生矩形区域内的遍历清扫轨迹;

[0010] 步骤二:将一个含有矩形障碍物的封闭清扫环境采用多条平行分割线沿着障碍物 和清扫环境边缘对可行清扫区域进行分割,并把机器人可行清扫区域划分成若干个矩形子 区域Sx,其中下标X表示各个子区域的编号;

[0011] 步骤三:根据各个矩形子区域之间的邻接关系将矩形子区域Sx组合为若干个矩形 迭代子区域Sb,其中z表示矩形迭代子区域的编号,所有的迭代子区域组合为整个可行清 扫区域,并求出各个迭代子区域Sb内的Standard仿射变换方程;因此对整个可行清扫区域 的清扫就分解为对各个迭代子区域的清扫;

[0012] 步骤四:将矩形迭代子区域S1^根据相邻关系勾画出可遍历空间的连通路,然后根 据连通路求出最优子区域衔接路径;

[0013] 步骤五:根据最优子区域衔接路径中矩形迭代子区域的邻接关系,构造出相邻 矩形迭代子区域Sb之间的矩形过渡子区域ST_Z和重复子区域Sm其中z表示矩形迭代子区 域的编号,并求出各个矩形过渡子区域St_z内的Standard仿射变换方程;

[0014] 步骤六:将矩形过渡子区域ST_Z和重复子区域Sclz插入到所求出的最优子区域衔接 路径中,产生全覆盖遍历连通图;

[0015] 步骤七:根据全覆盖遍历连通图中矩形迭代子区域的邻接关系,利用矩形过渡子 区域ST_Z、重复子区域Sclz和矩形过渡子区域ST_Z内的Standard仿射变换所产生的遍历轨迹, 进行矩形迭代子区域的自动衔接;当机器人遍历完一个迭代子区域,通过重复子区域Sclz和 过渡子区域ST_zg动衔接到下一个迭代子区域,直到所有迭代子区域遍历完成为止;

[0016] 步骤八:根据全覆盖遍历连通图设计清扫机器人全覆盖遍历程序的流程图,用以 实现机器人遍历清扫任务;在可行清扫区域内,初始化清扫机器人的起点以及清扫一次所 需要的总的迭代次数,选择清扫方向为顺时针或逆时针迭代,然后根据全覆盖遍历连通图 中的迭代顺序以及流程图程序,利用Standard仿射变换产生的轨迹依次实现各个矩形子区 域内的遍历清扫,以及子区域的自动衔接,直至整个遍历清扫任务完成。

资源下载

隐藏内容:******,购买后可见!

下载价格: 彩虹币

您需要先后,才能购买资源

赞(0) 打赏
未经允许不得转载:彩红网 » CN105922267B一种清扫机器人全覆盖遍历路径规划算法的设计方法[caired.com-彩红网3D模型下载CG模型平面素材专利检索网站源码]
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏