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

Review on Coverage Path Planning Algorithm for Intelligent Machinery

摘要:

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

Abstract:

The coverage path planning algorithm is indispensable to intelligent mobile machines, such as demining robots, autonomous underwater vehicles, plant protection UAVs, automatic painting robots, cleaning robots and some other applications, involving many areas like military, agriculture, manufacturing and civilian, so the algorithm has rich value on scientific research and business market. In this article, a variety of current mainstream coverage path planning algorithms are described. Based on the working environment information is known or not, coverage path planning algorithms are divided into two types of “off-line” and “on-line”. This article introduces off-line algorithms such as trapezoidal decomposition, boustrophedon cellular decomposition, line-sweep-based decomposition method, grid method of known spaces and quad-tree method, on-line algorithms such as neural network-based coverage, grid-based coverage using spanning trees and so on. This article also analyses and compares coverage completeness, efficiency, energy costs and achievement difficulty of each coverage path planning algorithm, advantages and pitfalls of each algorithm are pointed out. The technology development trends of coverage path planning algorithm for intelligent machinery are given in this article, multi-intelligent fusion algorithm can compensate for deficiencies of single-intelligent one, and it will be the future trend.