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.

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.

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. .

Robot coverage algorithm under rectangular decomposition environment

The environment modeling algorithm named rectangular decomposition, which is composed of cellular nodes and interleaving networks, is proposed. The principle of environment modeling is to divide the environment into individual square sub-areas. Each sub-area is orientated by the central point of the sub-areas called a node. The rectangular map based on the square map can enlarge the square area side size to increase the coverage efficiency in the case of there being an adjacent obstacle. Based on this algorithm, a new coverage algorithm, which includes global path planning and local path planning, is introduced. In the global path planning, uncovered subspaces are found by using a special rule. A one-dimensional array P, which is used to obtain the searching priority of node in every direction, is defined as the search rule. The array P includes the condition of coverage towards the adjacent cells, the condition of connectivity and the priorities defined by the user in all eight directions. In the local path planning, every sub-area is covered by using template models according to the shape of the environment. The simulation experiments show that the coverage algorithm is simple, efficient and adapted for complex two- dimensional environments.

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.

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.

A hybrid weed optimized coverage path planning technique for autonomous harvesting in cashew orchards

A coverage path planning algorithm is proposed for discrete harvesting in cashew orchards.The main challenge in such an orchard is the collection of fruits and nuts lying on the floor.The manual collection of fruits and nuts is both time consuming and labour intensive.The scenario begs for automated collection of fruits and nuts.There are methods developed in research for continuous crop fields,but none for discrete coverage.The problem is visualized as a graph traversal problem and paths for autonomous maneuvering are generated.A novel Mahalanobis distance based partitioning approach for performing coverage is introduced.The proposed path planner was able to achieve a mean coverage of 52.78 percentage with a deviation of 18.95 percentage between the best and worst solutions.Optimization of the generated paths is achieved through a combination of local and global search techniques.This was implemented by combining a discrete invasive weed optimization technique with an improved 2-Opt operator.A case study is formulated for the fruit picking operations in the orchards of Puducherry.The performance of the proposed algorithm is benchmarked against existing methods and also with performance metrics such as convergence rate,convergence diversity and deviation ratio.The convergence rate was observed to be 99.97 percent and 97.83 percent for a dataset with 48 and 442 nodes respectively.The deviation ratio was 0.02 percent and 2.16 percent,with a convergence diversity of 1.18 percent and 30.14 percent for datasets with 48 and 442 nodes.The achieved solutions was on par with the global best solutions achieved so far for the test datasets.

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.

A chaotic coverage path planner for the mobile robot based on the Chebyshev map for special missions

We introduce a novel strategy of designing a chaotic coverage path planner for the mobile robot based on the Che- byshev map for achieving special missions. The designed chaotic path planner consists of a two-dimensional Chebyshev map which is constructed by two one-dimensional Chebyshev maps. The performance of the time sequences which are generated by the planner is improved by arcsine transformation to enhance the chaotic characteristics and uniform distribution. Then the coverage rate and randomness for achieving the special missions of the robot are enhanced. The chaotic Chebyshev system is mapped into the feasible region of the robot workplace by affine transformation. Then a universal algorithm of coverage path planning is designed for environments with obstacles. Simulation results show that the constructed chaotic path planner can avoid detection of the obstacles and the workplace boundaries, and runs safely in the feasible areas. The designed strategy is able to satisfy the requirements of randomness, coverage, and high efficiency for special missions.

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

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

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

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

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

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

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

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

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

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

基于栅格法的农业机器人路径规划方法研究

智能农业机器人是无人农场实现机器完全替换人工劳动的重要一环,而路径规划是农业机器人的重要关键技术。为此,针对农田特殊作业环境及农艺要求,提出了农业机器人全局路径规划方法和局部最优规划方法。阐述了农田全覆盖路径规划思想,设计了基于神经元激励网络法的全覆盖路径规划方法和基于Dijkstra算法的局部最优路径规划方法。通过MatLab仿真试验验证路径规划方法的可行性,建立栅格地图,并随机设置障碍物信息模拟实际作业环境。研究结果表明:生物激励与神经元激励两种规划方法覆盖完成率均为100%,路径长度与转弯次数两者相差不大,但神经元激励法的路径重复率5.49%远远小于生物激励法的12.66%;基于神经元激励网络法的全覆盖路径规划方法比生物激励网络法的全覆盖路径规划方法重耕率更低,可实现农田地块大规模覆盖作业;基于Dijkstra算法的局部最优路径规划方法可针对不同复杂程度的障碍物地图实现自主最优路径规划。

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

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

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

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

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

核辐射场区全覆盖路径规划对于辐射环境下区域作业者的辐射安全有重要意义。本研究基于生物启发神经网络算法,提出一种进行辐射剂量最优控制的全覆盖路径规划算法。首先,利用福岛核电站部分地形以及蒙特卡罗粒子输运程序分别构建模拟核辐射场区的障碍物分布和辐射剂量场,然后,采用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,也在显著降低。本文提出的算法能实现过程剂量和累积剂量最优控制的全覆盖路径规划,另外算法可以协同规划多单元路径,显著降低单体累积剂量,对辐射环境下区域作业的辐射防护有重要意义。

多机协同作业全覆盖路径规划

多机协同作业能够提升作业效率,节约作业时间,减少了农作物因收获不及时导致的粮食浪费。为此,以总的非工作距离和最长单车行驶距离为目标函数,建立虚拟的农田模型,将多机协同作业全覆盖路径规划问题转化为VRP问题,并使用改进的蚁群算法求解。仿真结果表明:改进后的算法有效;对比遗传算法和传统的蚁群算法,改进后的算法平均目标函数值分别降低了25.0%和11.25%;对比模拟退火算法,改进后的算法平均目标函数值降低了1.5%,算法稳定性更好,适用于更大规模农田的多机协同作业全覆盖路径规划问题求解。

不确定检测环境下强化学习覆盖路径规划研究

机器人扫描测量系统在汽车质量检测领域获得广泛应用,尤其数模环境下基于仿生优化算法的视点采样与路径规划研究取得较大进展。然而,基于名义数模环境的路径规划结果难以适用实际不确定性检测环境。为此,本文提出基于改进的蒙特卡洛树搜索的视点自适应采样方法,在线生成工业机器人运动轨迹。通过车门内板案例的对比分析,验证本文方法的有效性,为实现不确定制造环境下工艺路径的在线规划提供理论依据。