移动机器人全覆盖路径规划研究

移动机器人的全局路径规划基本上可分为起点到终点寻优和全覆盖寻优两种。所谓全覆盖寻优路径规划,是指移动机器人快速而高效率地走遍一个区域内除障碍物以外的全部地方。对全覆盖路径规划方法的研究现状加以分析、比较和归纳,对全覆盖路径规划方法的发展趋势和研究方向进行探讨,也介绍作者自己的研究工作,同时对国内外刚开始不久的多机器人协作在全覆盖路径规划领域的研究工作也予以介绍,最后归纳出全覆盖寻优路径规划的发展方向及待解决的问题。     

智能机械全覆盖路径规划算法综述

全覆盖路径规划算法是智能移动机械的核心内容之一,涉及军事、农业、生产制造和民用等多个应用领域,而应用环境包含了空中、地面和水下,因此关于全覆盖路径规划算法的研究具有很高的科研价值。从全覆盖路径规划算法的基本概念、工作条件、应用背景、国内外研究现状等方面对目前主流的规划算法进行了综述。根据工作环境信息是否已知,将其归类为“离线式”和“在线式”两种工作方式,并从覆盖完整程度、工作效率、能耗成本和实现难易程度等方面分析讨论了各种算法的优势与不足之处,并对全覆盖路径规划算法的研究趋势进行了展望。     

移动机器人全局覆盖路径规划算法研究进展与展望

首先通过势场栅格法、单元分解法、全局与局部转换法等三大方法介绍了单移动机器人各种不同的全覆盖算法,分析了各种不同算法的性能,指出了它们的优缺点,并对每种方法的改进方法进行了探讨分析;另外,针对多机器人协作全覆盖路径规划的研究,探讨了基于单机器人全覆盖路径规划算法和任务分配算法等结合得到的多机器人协作路径规划算法;最后探讨移动机器人全覆盖路径规划算法的研究方向。分析结果表明,对于移动机器人全覆盖算法的研究,可充分利用现有算法的优势互补,或借助多学科交叉的优势,寻找更有效的算法。     

多移动机器人区域分割优化覆盖算法研究

针对多机器人协作的全覆盖路径规划优化问题,提出了一种区域分割优化覆盖算法,完成多机器人对未知区域的快速、高效的覆盖任务.在移动机器人全覆盖路径规划研究中,将机器人的能量、速度、任务完成时间等作为限制条件,对所需机器人的数目、机器人分成的组数及机器人工作的起始位置进行规划,以实现利用最少数目的机器人完成给定区域的优化分割和覆盖.对比仿真实验,结果表明本方法在给定机器人数量的情况下,完成了最大区域的覆盖.该方法可以有效完成多机器人对未知区域的快速高效的搜索覆盖任务.     

基于鱼群算法的智能机器人全覆盖路径规划

为保证机器人的行驶轨迹可以全方位地的覆盖地图的全部坐标点,并降低路径重复率,基于鱼群算法设计智能机器人全覆盖路径规划方法。建立智能机器人死区脱困模型,计算栅格地图模型中的目标活性值,获取整体栅格数量,描述地图中栅格状态,得到脱困时的行驶角度差。基于鱼群算法设计全路径覆盖判定方法,描述不同目标鱼个体之间的距离,在三重移动目标坐标系下,获取元素坐标向量,建立每个目标点的求解代价和,计算下一个目标点行驶的最小距离。设计机器人全覆盖路径规划算法,判断当前位置是否为死区,获取路径规划的全局最优解,实现智能机器人的全覆盖路径规划。利用Matlab仿真软件完成智能机器人全覆盖路径规划实验。结果表明,在简单环境下,该路径规划方法覆盖率为100%,重复率为5.23%,路径长度为15.36m；在复杂环境下,该路径规划方法的覆盖率为100%,重复率则为10.24%,路径长度为20.34m。由此证明,该方法具有较好地规划效果较好。     

移动机器人全覆盖信度函数路径规划算法

针对移动机器人全覆盖路径规划问题,给出一种基于栅格信度函数的全覆盖路径规划算法。目的是为了控制移动机器人能够遍历工作区域中所有的可到达点,同时保证能够自动避开障碍物。首先,根据环境的信息对栅格地图进行赋值,使用不同的函数值表示障碍物、已覆盖栅格和未覆盖栅格;其次,判断机器人是否陷入死区引入不同方向信度函数,对栅格函数值进行调整;最后,机器人根据栅格信度函数值规划覆盖路径。本文所提及的算法不仅能够引导移动机器人实现工作区域的全覆盖而且能够快速逃离死区,实现覆盖路径的低重复率。仿真实验中,通过与生物启发神经网络算法的比较,证明本文提及算法有更高的覆盖效率。     

家用自主吸尘机器人的研究和开发

介绍了一种新型家用智能吸尘器，该吸尘器采用基于地图的全覆盖路径规划的方法，能在无人情况下自主工作，并且具有自动回避障碍等功能；文中详细介绍了基于地图的全覆盖路径规划算法的实现方法及其软件仿真，并对吸尘器的测控系统根据算法设计的要求进行了研究和设计；通过作者开发的算法仿真软件和设计的吸尘器测控系统实验模型的仿真和实验结果表明，文中介绍的这种基于地图的全覆盖路径规划方法的家用智能吸尘器在实际应用中是可行的。     

一种室内清扫机器人路径规划算法

清扫机器人作为服务机器人领域中的一个新产品已成为人们家庭当中的重要一员,全覆盖路径规划问题是其重要技术之一。提出一种新的路径规划算法,该算法对室内环境进行栅格模型建模,生成一个无向完全图G,对图 G 采用深度优先搜索和广度优先搜索,并应用拓扑排序动态更新图 G,生成最短全覆盖规划路径,最后用生成树来验证该算法的有效性和可行性。     

基于阿基米德螺线走法的全区域覆盖路径规划

路径规划是移动机器人实现智能化自主运动的基础,全区域覆盖路径规划是移动机器人路径规划中的一种特殊形式,在生产生活中应用广泛,如智能割草机器人、智能清洁机器人、生命探测机器人等。提出一种以阿基米德螺线为主要行走方式,用直线循环往复的行走方式补充边角区域的路径规划方法。重点研究了覆盖矩形中间区域所用阿基米德螺线行走方式。实验结果表明该方法简单有效,在无障碍的类圆形区域具有较好的适用性。     

关于智能机器人局部混沌评价全覆盖路径规划

针对智能机器人全覆盖路径规划问题,提出了一种局部混沌评价规划方法.考虑到机器人移动过程中的随机性与不可预知性,设计了具有反馈控制变量的四维混沌系统.将该系统与机器人运动模型融合,建立得到路径规划模型,同时引入耦合控制参数对系统误差进行调节,根据机器人的起始坐标和混沌起始状态参量,利用微分离散化处理便可计算出移动的路径点.考虑到路径规划的局部最优解,对机器人移动空间进行网格划分,根据激励计算动态网格活性值,利用网格活性对移动路径规划采取分流,进而得到分流后的局部路径与角位移变化量.与此同时,针对局部路径规划设计了相应的指标评价,用以校正规划结果.仿真结果表明,提出的局部混沌评价规划方法具有良好的路径全覆盖效果,同时获得了更低的路径重复率、移动距离,以及路径规划时间,有效提高了机器人的移动效率与控制平稳性.     

多机器人覆盖技术研究进展

系统地总结了当前覆盖问题的定义、分类和应用前景.对多机器人覆盖中关于通信、环境地图、路径规划算法及效果评价等方面的研究进展情况进行了阐述.分析并指出若干多机器人覆盖研究中的重点和难点问题:体系结构、通信技术、协商协作、地图表示、路径规划及效果评价,并对未来的研究发展方向进行了探讨.     

不确定动态环境下移动机器人的完全遍历路径规划

基于生物激励神经网络、滚动窗口和启发式搜索，提出了一种新的完全遍历路径规划方法．该方法用Grossberg的生物神经网络实现移动机器人的局部环境建模，将滚动窗口的概念引入到局部路径规划，由启发式算法决定滚动窗口内的局域路径规划目标．该方法能在不确定动态环境中有效地实现机器人自主避障的完全遍历路径规划．仿真研究证明了该方法的可用性和有效性．     

Coverage for robotics – A survey of recent results

This paper surveys recent results in coverage path planning, a new path planning approach that determines a path for a robot to pass over all points in its free space. Unlike conventional point-to-point path planning, coverage path planning enables applications such as robotic de-mining, snow removal, lawn mowing, car-body painting, machine milling, etc. This paper will focus on coverage path planning algorithms for mobile robots constrained to operate in the plane. These algorithms can be classified as either heuristic or complete. It is our conjecture that most complete algorithms use an exact cellular decomposition, either explicitly or implicitly, to achieve coverage. Therefore, this paper organizes the coverage algorithms into four categories: heuristic, approximate, partial-approximate and exact cellular decompositions. The final section describes some provably complete multi-robot coverage algorithms.     

Multiobjective coverage path planning: Enabling automated inspection of complex,real-world structures

An important open problem in robotic planning is the autonomous generation of 3D inspection paths – that is, planning the best path to move a robot along in order to inspect a target structure. We recently suggested a new method for planning paths allowing the inspection of complex 3D structures, given a triangular mesh model of the structure. The method differs from previous approaches in its emphasis on generating and considering also plans that result in imperfect coverage of the inspection target. In many practical tasks, one would accept imperfections in coverage if this results in a substantially more energy efficient inspection path. The key idea is using a multiobjective evolutionary algorithm to optimize the energy usage and coverage of inspection plans simultaneously – and the result is a set of plans exploring the different ways to balance the two objectives. We here test our method on a set of inspection targets with large variation in size and complexity, and compare its performance with two state-of-the-art methods for complete coverage path planning. The results strengthen our confidence in the ability of our method to generate good inspection plans for different types of targets. The method's advantage is most clearly seen for real-world inspection targets, since traditional complete coverage methods have no good way of generating plans for structures with hidden parts. Multiobjective evolution, by optimizing energy usage and coverage together, ensures a good balance between the two – both when 100% coverage is feasible, and when large parts of the object are hidden.     

基于动态矩阵的未知环境地图构建与路径规划

目前主流的SLAM地图构建方法在环境建模中一般要借助人机交互平台,人工成本高,独立性较差。提出基于动态矩阵的未知环境地图构建算法,可以在完全未知的陌生环境中,基于二维空间栅格地图建模并利用A*算法进行回溯,独立实现地图信息的全覆盖采集。针对传统的局部覆盖路径规划算法存在重复率高、运行效率低的问题,进行了改进设计,一旦检测到封闭区域则优先处理,并采用沿边循迹和牛耕式运动相结合的方法进行子区域路径规划。算法使用Matlab进行仿真设计,通过Webots机器人仿真平台进行了验证,仿真结果表明,改进算法与传统的局部覆盖算法相比,在子区域划分数目、回溯路径总长和路径重复率等指标上有明显提高。     

Coverage path planning on three‐dimensional terrain for arable farming

Field operations should be done in a manner that minimizes time and travels over the field surface and is coordinated with topographic land features. Automated path planning can help to find the best coverage path so that the field operation costs can be minimized. Intelligent algorithms are desired for both two‐dimensional (2D) and three‐dimensional (3D) terrain field coverage path planning. The algorithm of generating an optimized full coverage pattern for a given 2D planar field by using boustrophedon paths has been investigated and reported before. However, a great proportion of farms have rolling terrains, which have a considerable influence on the design of coverage paths. Coverage path planning in 3D space has a great potential to further optimize field operations. This work addressed four critical tasks: terrain modeling and representation, coverage cost analysis, terrain decomposition, and the development of optimized path searching algorithm. The developed algorithms and methods have been successfully implemented and tested using 3D terrain maps of farm fields with various topographic features. Each field was decomposed into subregions based on its terrain features. A recommended “seed curve” based on a customized cost function was searched for each subregion, and parallel coverage paths were generated by offsetting the found “seed curve” toward its two sides until the whole region was completely covered. Compared with the 2D planning results, the experimental results of 3D coverage path planning showed its superiority in reducing both headland turning cost and soil erosion cost. On the tested fields, on average the 3D planning algorithm saved 10.3% on headland turning cost, 24.7% on soil erosion cost, 81.2% on skipped area cost, and 22.0% on the weighted sum of these costs, where their corresponding weights were 1, 1, and 0.5, respectively. © 2011 Wiley Periodicals, Inc.     

Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction

Three-dimensional terrain reconstruction from 2D aerial images is a problem of utmost importance due its wide level of applications. It is relevant in the context of intelligent systems for disaster managements (for example to analyze a flooded area), soil analysis, earthquake crisis, civil engineering, urban planning, surveillance and defense research.It is a two level problem, being the former the acquisition of the aerial images and the later, the 3D reconstruction. We focus here in the first problem, known as coverage path planning, and we consider the case where the camera is mounted on an unmanned aerial vehicle (UAV).In contrast with the case when ground vehicles are used, coverage path planning for a UAV is a lesser studied problem. As the areas to cover become complex, there is a clear need for algorithms that will provide good enough solutions in affordable times, while taking into account certain specificities of the problem at hand. Our algorithm can deal with both convex and non-convex areas and their main aim is to obtain a path that reduces the battery consumption, through minimizing the number of turns.We comment on line sweep calculation and propose improvements for the path generation and the polygon decomposition problems such as coverage alternatives and the interrupted path concept. Illustrative examples show the potential of our algorithm in two senses: ability to perform the coverage when complex regions are considered, and achievement of better solution than a published result (in terms of the number of turns used).