一种清扫机器人全覆盖遍历路径规划算法的设计方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN105922267A(43)申请公布日2016.09.07(21)申请号201610487847.6(22)申请日2016.06.28(71)申请人山东理工大学地址255000山东省淄博市张店区新村西路266号(72)发明人李彩虹宋勇王凤英王志强梁振英李贻斌(74)专利代理机构济南诚智商标专利事务所有限公司37105代理人李修杰(51)Int.Cl.B25J9/16(2006.01)权利要求书3页说明书12页附图6页(54)发明名称一种清扫机器人全覆盖遍历路径规划算法的设计方法(57)摘要本发明公开了一种清扫机器人全覆盖遍历路径规划算法的设计方法，它具体包括以下主要过程：利用Standard混沌方程生成矩形区域内的遍历清扫轨迹，矩形子区域分解，矩形迭代子区域的构造，最优子区域衔接路径的构造，矩形过渡子区域和重复子区域的构造，最优全覆盖遍历清扫连通图的构造，迭代子区域的自动衔接，可行区域内的全覆盖遍历清扫任务实现。本发明算法重复率低，覆盖率高，不存在清扫盲区；算法规划效率高，不需要确定起点和终点；算法简单，容易实现。本发明能够很好地满足机器人室内清扫并实现全覆盖遍历路径规划的任务。CN105922267ACN105922267A权利要求书1/3页1.一种清扫机器人全覆盖遍历路径规划算法的设计方法，其特征是，包括以下步骤：步骤一：选择Standard混沌方程及其仿射变换产生矩形区域内的遍历清扫轨迹；步骤二：将一个含有矩形障碍物的封闭清扫环境采用多条平行分割线沿着障碍物和清扫环境边缘对可行清扫区域进行分割，并把机器人可行清扫区域划分成若干个矩形子区域Sx，其中下标x表示各个子区域的编号；步骤三：根据各个矩形子区域之间的邻接关系将矩形子区域Sx组合为若干个矩形迭代子区域SI_z，其中z表示矩形迭代子区域的编号，所有的迭代子区域组合为整个可行清扫区域，并求出各个迭代子区域SI_z内的Standard仿射变换方程；步骤四：将矩形迭代子区域SI_z根据相邻关系勾画出可遍历空间的连通路，然后根据连通路求出最优子区域衔接路径；步骤五：根据最优子区域衔接路径中矩形迭代子区域SI_z的邻接关系，构造出相邻矩形迭代子区域SI_z之间的矩形过渡子区域ST_z和重复子区域SO_z，其中z表示矩形迭代子区域的编号，并求出各个矩形过渡子区域ST_z内的Standard仿射变换方程；步骤六：将矩形过渡子区域ST_z和重复子区域SO_z插入到所求出的最优子区域衔接路径中，产生全覆盖遍历连通图；步骤七：根据全覆盖遍历连通图中矩形迭代子区域的邻接关系，利用矩形过渡子区域ST_z、重复子区域SO_z和矩形过渡子区域ST_z内的Standard仿射变换所产生的遍历轨迹，进行矩形迭代子区域的自动衔接；当机器人遍历完一个迭代子区域，通过重复子区域SO_z和过渡子区域ST_z自动衔接到下一个迭代子区域，直到所有迭代子区域遍历完成为止；步骤八：根据全覆盖遍历连通图设计清扫机器人全覆盖遍历程序的流程图，用以实现机器人遍历清扫任务；在可行清扫区域内，初始化清扫机器人的起点以及清扫一次所需要的总的迭代次数，选择清扫方向为顺时针或逆时针迭代，然后根据全覆盖遍历连通图中的迭代顺序以及流程图程序，利用Standard仿射变换产生的轨迹依次实现各个矩形子区域内的遍历清扫，以及子区域的自动衔接，直至整个遍历清扫任务完成。2.如权利要求1所述的一种清扫机器人全覆盖遍历路径规划算法的设计方法，其特征是，在步骤一中，Standard混沌方程是一个简单的二维动力学方程，Standard混沌方程的离散化形式表示为：式中，(xn,yn)为清扫机器人全覆盖遍历路径的运行轨迹坐标，K为混沌状态参数。3.如权利要求2所述的一种清扫机器人全覆盖遍历路径规划算法的设计方法，其特征是，当K＝8时方程(1)的映射方程为：2CN105922267A权利要求书2/3页在方程(2)中，随机给定一个初始值(x0,y0)，可以求出它任意时刻的迭代值(xn,yn)；通过仿射变换将清扫机器人全覆盖遍历路径的运行轨迹(xn,yn)映射到一个任意大小的矩形区域内，仿射变换方程为：其中，(a,b)是平移变换，(c,d)是比例变换，(xn,yn)是清扫机器人清扫轨迹点的坐标，将时间序列中所有相邻的轨迹点(xn,yn)和(xn-1,yn-1)依次连接起来就形成了机器人矩形区域内的遍历清扫轨迹。4.如权利要求1所述的一种清扫机器人全覆盖遍历路径规划算法的设计方法，其特征是，在步骤二中，Standard混沌方程所产生的清扫轨迹是一个吸引子，分布在一个有限的矩形区域内，通过仿射变换映射到任意大小的矩形区域内，从而将含有矩形障碍物的封闭清扫环境划分为若干个矩形子区域。5.如