基于栅格地图的环境空间划分与遍历VIP免费

第二届全国先进制造装备与机器人技术论文集基于栅格地图的环境空间划分与遍历阮晓钢，徐绍敏(北京工业大学电控学院人工智能与机器人研究所，北京100022)■要：本文针对室内清洁机器人的特殊工作环境．提出了一种环境区域划分与遍历方浩；该方法基于栅格地图来描述环境，对环境地图进行分区，通过自由区域联结图广度优先搜索及深度优先遍历NfSIIC)形成方形区域遣历顺序，对机器人追历环境的路线进行导航．实验研究表明栅格地图表示环境对于区蛾划分与区域表示更容易；呆用WSDC算法产生的区域追历顺序导航机器人运动，可以减少机器人的运动距离，提高工作效率．关键牢：路径规划、栅格地图、区域追历、导航中圈舟类号：TP24DivisionandCoverageoftheWorkingEnvironmentbasedonGridMapRuanXiaogang,XuShaomin(BeijingUniversityofTechnology,TheInstituteofA[andRobotics,Beijing100022)Abstract：Thistextaimingatthespecialworkenvironmentoftheindoorcleaningrobot,presentsamethodtodivideandcovertheworkspace；ThemethodexpressestheenvironmentbasedOilthegrjdmap；Divide，andadoptaWidth-firstSearchandDepth-firstCoverage{WSDC)methodtogainacoverage-orderofthesquarefree-areastOnavigatetherobotmovement．Theexperimentprovesthatusing鲥dmapt0expresstheenvironmentiseasierforthedivisionandrepresentation：AccordingtotheordergainedbythealgorithmofWSDCt0navigatetherobotcouldroducethedistanceofmovementandimprovetheworkingefficiency．Keyword：pathplanning、gridmap、areacovel．age、navigation1前言室内自主清洁机器人的工作的运动过程就是机器人可达空间的遍历过程，第一次工作时它的工作环境是陌生的，工作效率也是最低的．它需要建立环境的抽象描述IIoJ，即地图；以后工作，可以利用已建立的地图，进行路径规划得到一种较优的路径，是提高室内清洁机器人的工作效率的必要条件。目前，路径规划问题已经有很多研究。大部分还是针对两点之间的运动路径规划”l，对于区域遍历的路径规划较少，有的提出了一种螺旋形导航算#掣⋯，实现自由区域的遍历，也有的提出基于标点定位的清扫机器人遍历算法[51等，这些算法都没有考虑机器人运动效率的提高。还有的提出的区域分解的方法Iooj，只考虑了自由空间的划分可以减少运动路线的重复，没有解决在不同区域之间大幅度转移的问题，同时基于拓扑图的环境描述地图不利于区域划分。表示一个区域需要大量的数据。O第二届全国先进制造装备与机器人技术论文集本文的主要工作是针对室内清洁机器人的特殊工作环境，提出一种环境区域划分与遍历方法；该方法基于栅格地图来描述环境．对环境地图进行分区。通过自由区域联结图J“度优先搜索及深度优先遍历(WSDC)形成方形区域遍历顺序，对机器人遍历环境的路线进行导航。2基于栅格地图的环境描述通过对室内环境进行观察可以看出，室内物体大部分为方形的，至少可也看成近似方形物体：本文对环境进行二维空间建模，把室内环境地图用二维数组map表示，在障碍物占有区域内的坐标点上用””标定，表示此坐标与相邻的标有””的坐标之间的区域为障碍物区域，未标定区域为自由区域，它可以分割为"个方形区域，用n×2×2的三维数纽庙，∞，farea[k，：，：1表示分割出的的k个方形自由区域，它存储的是方形区域的左下和右上顶点的坐标；如图l。区域ABFH所围的区域为障碍物区域，区域BCIDGEHF所围的区域为自由区域，它可以分割为三个方形区域2、3和4．其farea[I，：。：】_【A(f，J)I(i，川表示第一个方形自由区域(区域2)。用二位数组narea表示各个方形自由区域的相邻区域，用直观方法表示就是联结图。最终环境地图的符号表示：EM=a本文的主要内容是利用栅格描述的环境中的～些重要的转折点实现自由空间的划分，提出一种较优的路径规划方法，实现区域间的高效转移。EG34HF++1+++2矗BC图1确定区域3自由空间划分及合并算法O栅格地图描述的环境的中物体的顶点在四个方向上的延长线总会有交点，这些交点及顶点的集合。统一用来确定剩余自由区域。在确定各个区域的过程中...