Distributed collaborative complete coverage path planning based on hybrid strategy

Collaborative coverage path planning(CCPP) refers to obtaining the shortest paths passing over all places except obstacles in a certain area or space. A multi-unmanned aerial vehicle(UAV) collaborative CCPP algorithm is proposed for the urban rescue search or military search in outdoor environment.Due to flexible control of small UAVs, it can be considered that all UAVs fly at the same altitude, that is, they perform search tasks on a two-dimensional plane. Based on the agents’ motion characteristics and environmental information, a mathematical model of CCPP problem is established. The minimum time for UAVs to complete the CCPP is the objective function, and complete coverage constraint, no-fly constraint, collision avoidance constraint, and communication constraint are considered. Four motion strategies and two communication strategies are designed. Then a distributed CCPP algorithm is designed based on hybrid strategies. Simulation results compared with patternbased genetic algorithm(PBGA) and random search method show that the proposed method has stronger real-time performance and better scalability and can complete the complete CCPP task more efficiently and stably.

Complete Coverage Path Planning Based on Improved Area Division

It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the boustrophedon cell decomposition method is used to partition the map into sub-regions. The complete coverage paths within each sub-region are obtained by the Boustrophedon back-and-forth motions, and the order of traversal of the sub-regions is then described as a generalised traveling salesman problem with pickup and delivery based on the relative positions of the vertices of each sub-region. An adaptive large neighbourhood algorithm is proposed to quickly obtain solution results in traversal order. The effectiveness of the improved algorithm on traversal cost reduction is verified in this paper through multiple sets of experiments. .

Energy-Efficient UAVs Coverage Path Planning Approach

Unmanned aerial vehicles(UAVs),commonly known as drones,have drawn significant consideration thanks to their agility,mobility,and flexibility features.They play a crucial role in modern reconnaissance,inspection,intelligence,and surveillance missions.Coverage path planning(CPP)which is one of the crucial aspects that determines an intelligent system’s quality seeks an optimal trajectory to fully cover the region of interest(ROI).However,the flight time of the UAV is limited due to a battery limitation and may not cover the whole region,especially in large region.Therefore,energy consumption is one of the most challenging issues that need to be optimized.In this paper,we propose an energy-efficient coverage path planning algorithm to solve the CPP problem.The objective is to generate a collision-free coverage path that minimizes the overall energy consumption and guarantees covering the whole region.To do so,the flight path is optimized and the number of turns is reduced to minimize the energy consumption.The proposed approach first decomposes the ROI into a set of cells depending on a UAV camera footprint.Then,the coverage path planning problem is formulated,where the exact solution is determined using the CPLEX solver.For small-scale problems,the CPLEX shows a better solution in a reasonable time.However,the CPLEX solver fails to generate the solution within a reasonable time for large-scale problems.Thus,to solve the model for large-scale problems,simulated annealing forCPP is developed.The results show that heuristic approaches yield a better solution for large-scale problems within amuch shorter execution time than the CPLEX solver.Finally,we compare the simulated annealing against the greedy algorithm.The results show that simulated annealing outperforms the greedy algorithm in generating better solution quality.

Parameter value selection strategy for complete coverage path planning based on the Lüsystem to perform specific types of missions

We propose a novel parameter value selection strategy for the Lüsystem to construct a chaotic robot to accomplish the complete coverage path planning(CCPP)task.The algorithm can meet the requirements of high randomness and coverage rate to perform specific types of missions.First,we roughly determine the value range of the parameter of the Lüsystem to meet the requirement of being a dissipative system.Second,we calculate the Lyapunov exponents to narrow the value range further.Next,we draw the phase planes of the system to approximately judge the topological distribution characteristics of its trajectories.Furthermore,we calculate the Pearson correlation coefficient of the variable for those good ones to judge its random characteristics.Finally,we construct a chaotic robot using variables with the determined parameter values and simulate and test the coverage rate to study the relationship between the coverage rate and the random characteristics of the variables.The above selection strategy gradually narrows the value range of the system parameter according to the randomness requirement of the coverage trajectory.Using the proposed strategy,proper variables can be chosen with a larger Lyapunov exponent to construct a chaotic robot with a higher coverage rate.Another chaotic system,the Lorenz system,is used to verify the feasibility and effectiveness of the designed strategy.The proposed strategy for enhancing the coverage rate of the mobile robot can improve the efficiency of accomplishing CCPP tasks under specific types of missions.

Complete coverage path planning for an Arnold system based mobile robot to perform specific types of missions

We propose a contraction transformation algorithm to plan a complete coverage trajectory for a mobile robot to ac-complish specific types of missions based on the Arnold dynamical system. First, we construct a chaotic mobile robot by com-bining the variable z of the Arnold equation and the kinematic equation of the robot. Second, we construct the candidate sets including the initial points with a relatively high coverage rate of the constructed mobile robot. Then the trajectory is contracted to the current position of the robot based on the designed contraction transformation strategy, to form a continuous complete cov-erage trajectory to execute the specific types of missions. Compared with the traditional method, the designed algorithm requires no obstacle avoidance to the boundary of the given workplace, possesses a high coverage rate, and keeps the chaotic characteristics of the produced coverage trajectory relatively unchanged, which enables the robot to accomplish special missions with features of completeness, randomness, or unpredictability.

Development of Global Geographical Coverage Area for Terrestrial Networks Internetworked with Leo Satellite Network

Network planning, analysis and design are an iterative process aimed at ensuring that a new network service meets the needs of subscribers and operators. During the initial start-up phase, coverage is the big issue and coverage in telecommunications systems is related to the service area where a bare minimum access in the wireless network is possible. In order to guarantee visibility of at least one satellite above a certain satellite elevation, more satellites are required in the constellation to provide Global network services. Hence, the aim of this paper is to develop wide area network coverage for sparsely distributed earth stations in the world. A hybrid geometrical topology model using spherical coordinate framework was devised to provide wide area network coverage for sparsely distributed earth stations in the world. This topology model ensures Global satellite continuous network coverage for terrestrial networks. A computation of path lengths between any two satellites put in place to provide network services to selected cities in the world was carried out. A consideration of a suitable routing decision mechanism, routing protocols and algorithms were considered in the work while the shortest paths as well as the alternate paths between located nodes were computed. It was observed that a particular satellite with the central angle of 27°can provide services into the diameter of the instantaneous coverage distance of 4081.3 Km which is typical of wide area network coverage. This implies that link-state database routing scheme can be applied, continuous global geographical coverage with minimum span, minimum traffic pattern and latency are guaranteed. Traffic handover rerouting strategies need further research. Also, traffic engineering resources such as channel capacity and bandwidth utilization schemes need to be investigated. Satellite ATM network architecture will benefit and needs further study.

玻璃幕墙清洗机器人内螺旋完全遍历路径规划研究

针对高空复杂环境下玻璃幕墙清洗机器人的全方位无死角清洗问题,本文提出了一种基于改进蚁群算法的内螺旋完全遍历路径规划方法。首先在融合视觉传感器识别定位结果的基础上构建环境栅格地图;针对机器人全方位无死角遍历问题,以最大覆盖面积、最小重复路径及最大安全性为目标,通过内螺旋完全遍历算法实现清洗路径规划。在此基础上,针对机器人完全遍历易陷入死区问题,以最快规划、最少拐点及最快收敛为目标,通过改进蚁群算法规划出最优逃逸死区路线。改进方向以机器人4方位4领域移动为主,在启发函数中引入A^(*)算法的代价函数,同时在信息素更新中引入惩罚函数的思想。最后通过2种算法结合完成清洗区域的完全遍历,仿真结果表明:机器人在已知地图上通过4次规划后清洗覆盖率达到100%,行进重复率达到3.15%,实现了完全遍历。

灌溉机器人全覆盖路径规划方法

灌溉机器人全覆盖行动的各个任务具有较为明显的空间并行性,随着全覆盖范围扩大,在对覆盖区域进行分解阶段,需要充分考虑将整个区域空间分解为哪些区域。但是,灌溉机器人受到视觉感知区域限制,准确匹配和衔接路块间最近端点的难度较大,导致局部路点的连通和线路衔接出现差错,难以有效全覆盖。为了有效解决这一问题,提出一种灌溉机器人全覆盖路径规划方法。通过快速搜索随机算法展开需要覆盖区域的边界检测,考虑视觉传感器的感知范围受限因素,采用灰度质心法展开区域视图边界提取,根据提取结果建立地图。在地图上建立线段序列,通过曼哈顿最小距离原则连接地图上的部分路径线段,形成多个弓形线路块。使用分治算法匹配和衔接各个弓形线路块间最近端点对,引入改进A*算法对全局以及局部路点的连通和线路衔接,实现灌溉机器人的全覆盖路径规划。实验结果表明:针对简单灌溉区域,该方法的路径重复率为0.041%,灌溉覆盖率为98.90%;针对复杂灌溉区域,该方法的路径重复率为0.017%,灌溉覆盖率为99.87%。这说明针对不同的灌溉环境,该方法均可以实现理想的路径规划,不仅可以最大限度地实现全覆盖,并有效地减少路径冗余程度,可以获取理想的灌溉机器人全覆盖路径规划方案。

通信受限条件下多无人机协同环境覆盖路径规划

多无人机协同覆盖旨在有效分配多个无人机任务,实现给定区域的快速、高效全覆盖。然而,在现实应用场景中常常因为无人机之间距离超出通信范围,信号传输受阻,导致无人机之间的协作和信息交互面临极大挑战。为此,提出一种基于Deep Q Networks(DQN)的多无人机路径规划方法。采用通信中断率和最大通信中断时间两个指标来评价路径质量,通过构建与指标相关的奖励函数,实现了无人机团队的自主路径决策。仿真实验表明,所提方法在最短路径上可以与传统优化算法效果保持一致,权衡路径下在增加20%路径长度的情况下可以降低80%通信中断率,在全通信路径下则可以实现100%的全过程连接通信,因此可以根据不同的通信环境生成高效覆盖所有环境节点的路径。

移动机器人全覆盖路径的BINN-元胞自动机规划

为了实现机器人对工作区域的全覆盖,提出了基于生物激励神经网络-元胞自动机系统的全覆盖路径规划方法。介绍了生物激励神经网络算法的基本原理,分析了该算法在机器人陷入死区时无法逃逸的问题。基于元胞自动机系统设计了机器人逃逸机制,包括逃逸点的确定和逃逸路径的规划方法。在仿真环境下,将元胞系统逃逸机制与基本RRT、文献[10]的BINN-RRT逃逸机制进行对比,结果表明元胞系统逃逸机制的规划时间比基本RRT小2个数量级,比BINN-RRT小1个数量级,且逃逸路径短于另外两种方法,验证了元胞系统逃逸机制的有效性和优越性。基于BINN和元胞系统的全覆盖路径比BINN-RRT规划路径更加平滑,验证了全覆盖方法的优越性和有效性。

面向电磁目标探测的无人机集群区域分割方法

针对电磁目标搜索任务中现有覆盖式路径规划算法存在的无人机初始分布不合理、集群任务起止时间一致性差等问题,依据现实无人机集群集中投放的初始场景,设计了一种等时倾向的区域分割算法。该算法以最小化无人机间最大任务用时差为优化目标,通过改变无人机搜索区域大小影响无人机的任务用时。算法具有二级结构,第一级初始粗分割,解决边界点迭代次数过多的问题;第二级以任务时间偏差值作为调整值,保证了各机的任务用时一致性。仿真实验表明:该算法更适用于无人机集中投放的场景,缩短了无人机个体间的任务等待时间,便于资源的二次调度,有利于多阶次任务的同步执行。

基于生物启发神经网络的核辐射场区全覆盖路径规划

核辐射场区全覆盖路径规划对于辐射环境下区域作业者的辐射安全有重要意义。本研究基于生物启发神经网络算法,提出一种进行辐射剂量最优控制的全覆盖路径规划算法。首先,利用福岛核电站部分地形以及蒙特卡罗粒子输运程序分别构建模拟核辐射场区的障碍物分布和辐射剂量场,然后,采用Python语言进行算法仿真试验,模拟核辐射场区的每一个栅格定义为一个神经元,建立起生物启发神经网络,将栅格剂量率与神经元活性耦合实现路径规划的辐射剂量最优控制,分别采用单个、4个和8个移动单元进行仿真试验。结果表明:单个移动单元的规划路径在实现100%覆盖率,4%覆盖重复率的同时,能够优先覆盖低剂量区,延后覆盖高剂量区,实现了过程剂量和累积剂量的最优控制。为提高全覆盖的时间效率和获得更低的单体累积剂量,对算法进行多单元协同搜索的改进,结果表明:4单元和8单元仿真的覆盖重复率分别为5.72%和6.29%,1单元、4单元和8单元仿真完成全覆盖时间分别为30 min、9 min和4 min,时间效率成倍提高;最大单体累积剂量分别为4.11×10^(-3)mSv、1.28×10^(-3)mSv和0.85×10^(-3)mSv,也在显著降低。本文提出的算法能实现过程剂量和累积剂量最优控制的全覆盖路径规划,另外算法可以协同规划多单元路径,显著降低单体累积剂量,对辐射环境下区域作业的辐射防护有重要意义。

基于改进RRT的清扫机器人全覆盖路径规划

针对钢筋轧制车间中大型非结构化环境下清扫机器人在全覆盖路径规划时所面临的算法运行成本高、避障性能差和区域覆盖率低等问题,提出了一种利用单元分解法分区覆盖和融合跳点搜索法的RRT区域转移的全覆盖路径规划算法。利用MCD(movement cell decomposition)算法实现自由区域覆盖,为了解决区域间路径规划时的避障问题,引入融合跳点搜索策略的RRT算法,通过增加节点扩展的导向性,使其更偏向目标区域进行搜索,并利用贪婪算法裁剪冗余点修正路径以及三次B样条曲线法平滑处理。通过仿真与实验验证了算法在不同环境下的可行性和有效性,相比于其他方法所规划的路径更短且大大降低了路径重复率,提高了机器人避障效率的同时实现了全区域路径覆盖。

基于改进蚁群算法的凹区域无人侦察机覆盖航线规划

针对固定翼无人机的区域覆盖侦察航线规划问题,提出一种基于改进蚁群算法的凹区域覆盖航线规划方法。建立垂直载荷侦察模型,引入平行覆盖策略,通过旋转卡壳法确定飞行方向;针对不规则凹多边形区域,提出融合凹点移除和区域分解的多策略凹多边形转换方法;将覆盖航线规划问题转换为搜索最优条带遍历顺序的优化问题,建立Dubins转弯航线,通过在蚁群算法中改进启发函数、引入自适应信息素挥发系数和3-opt算法进行问题求解。实验结果表明,该方法能够高效实现凹区域转换,并获得长度更短的区域覆盖侦察航线,可为开展无人侦察机自主区域侦察研究提供理论支持。

基于改进鲸鱼优化算法的丘陵山区田块全覆作业路径规划

为了解决丘陵山区单田块作业全覆盖路径规划以及多田块作业最优遍历顺序求解的问题,提升丘陵山区农业机械的作业质量和能耗效率,该研究设计了一种基于改进鲸鱼优化算法的路径规划方法。首先利用电子地图获取作业区域的数字高程模型(digital elevation model,DEM)并提取作业区域经纬度信息,基于提取数据构建和绘制田块模型。然后,在单田块全覆盖路径规划中引入能耗模型用于寻找最佳作业方向角,以实现单田块作业能耗最优的全覆盖路径规划。最后,针对鲸鱼优化算法容易陷入局部最优和早熟的问题,利用Tent映射进行种群初始化,同时引入非线性收敛因子a*和路径长度最优为目标进行作业路径规划仿真试验。仿真结果表明,按照能耗最优规划路径完成田块作业需要的总能耗为1.3002×10^(7)J,比路径长度最优情况下的作业能耗减少22.26%,利用改进鲸鱼优化算法求解的遍历顺序进行遍历所消耗的能耗比鲸鱼优化算法求解遍历顺序进行遍历节省能耗11.71%,节能效果明显。

考虑子单元数量与起始位置的全覆盖路径规划

移动机器人的覆盖作业任务正朝着大面积和智能化方向发展,对全覆盖路径规划的覆盖效率与环境适应性提出迫切需求。为解决传统的牛耕单元分解法在复杂地图中适应性不足的问题,并提高覆盖效率,给出一种全覆盖路径规划方法。首先,在牛耕单元分解法的基础上,提出面积降序遍历与单调多边形判断的策略对子单元进行合并,减少约一半的子单元数量。最后,通过建立子单元起始位置与终止位置的映射关系,采用遗传算法优化子单元起始位置的选择和全局访问顺序。研究结果表明:1)文中算法在处理长宽为1300像素的地图时,能够在10 s内得到计算结果,并且相较于牛耕法、神经网络法和等高线法,计算时间随地图面积的增长率更小;2)相较于牛耕法、等高线法、神经网络法和能量最优法,文中算法的机器人总作业时间减少5.4%~47.0%,无效作业时间减少5.8%~29.2%;3)文中算法在1800张测试地图的平均覆盖率达到99.91%;4)统计检验进一步验证文中算法具有显著覆盖效率优势。

民机外表面上部自主视觉检查中的降维路径规划研究

传统的民机外表面检查过程中,人工目视检查存在成本高、效率低、工作时间长等诸多不足,而带有机载视觉系统的机器人可以安全、快速、准确地检查民机外表面。本文提出一种用于民机外表面上部自主视觉检查的三维覆盖路径规划方法。通过对民机外表面上部进行初步点云获取,对机身、机翼区域切片,将三维点云映射到平面,然后进行二维覆盖路径的规划及三维空间的路径复原,快速生成优化的三维全覆盖检查路径。结果表明,该方法可以缩短三维覆盖路径规划的时间,较大程度地降低民机外表面上部自主视觉检查的成本,推动自动化检查民机表面技术的发展。

基于电子海图的无人艇集群区域覆盖路径规划

[目的]针对无人艇(ASV)集群区域覆盖问题,设计一种基于电子海图信息系统(ECDIS)的多无人艇区域覆盖路径规划方法。[方法]首先,通过提取ECDIS中的海陆和水深信息,建立基于栅格化方法的无人艇集群覆盖区域环境模型。其次,提出一种基于轮盘选择法的区域划分方法,解决基于初始位置的区域划分方法区域划分不规则的问题,实现在栅格地图中对无人艇集群覆盖子区域的合理划分。最后,构建一种基于模板法的区域覆盖路径规划方法,解决生成树覆盖方法路径转弯数量较多的问题。[结果]搭建基于ECDIS的无人艇集群人机交互仿真平台,验证所提基于轮盘法和模板法的区域覆盖路径规划方法对优化规划路径转弯数量的有效性。[结论]采用所提基ECDIS的无人艇集群区域覆盖路径规划方法,实现多无人艇对海上目标任务区域的覆盖路径规划。

基于粒子群优化的多无人机区域覆盖航迹规划

针对多补给点的多无人机植保作业的航迹规划问题,建立了基于Voronoi图的无人机环境信息模型及作业区域划分,提出了基于粒子群优化(PSO)的航迹规划算法,充分考虑有效作业路径、总路径、总能耗及转弯次数等4个因素,对已知区域进行全覆盖路径规划。仿真结果表明:PSO算法与传统断点续飞方式相比,在有效作业率上提升了2.55%;在总路径、总耗能、综合代价上分别降低了2.55%、3.45%、1.04%。在PSO算法下,植保无人机有效作业率更高,无效路径更短,能量消耗更低,降低了经济成本。

基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划

基于爬壁机器人对混凝土桥梁健康进行自动巡检是推动桥梁管养智能化的有效途径,而合理的路径规划对机器人全面获取检测数据尤为重要。针对爬壁机器人电源重量限制与巡检时能源补充困难这一工程实际问题,充分考虑主梁、高墩等桥梁构件巡检场景,将能量消耗指标作为性能评价优化目标函数并建立相应约束条件,进而提出全覆盖路径规划评价模型。针对传统灰狼优化(GWO)算法易陷入局部最优的不足,提出一种改进的灰狼优化(IGWO)算法。IGWO算法通过K-means聚类改善了灰狼初始种群在搜索空间难以保持相对均匀分布的特性;以非线性收敛因子提高算法局部开发能力和全局搜索性能;结合粒子群算法个体优越性的思想对位置更新公式进行改进,提升算法的模型求解能力。仿真对比实验结果表明,IGWO算法相较于GWO、差分进化(DE)与遗传算法(GA)等全局优化算法,稳定性更好,能耗降低了10.2%~16.7%,迭代次数与求解时间分别减少了19.3%~36.9%和12.8%~32.3%,路径重复率降低了0.23~1.91个百分点,同时路径长度缩短1.6%~11.0%。