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.

Radio Coverage Mapping in Wireless Sensor Networks

Radio coverage directly affects the network connectivity, which is the foundational issue to ensure the normal operation of the network. Many efforts have been made to estimate the radio coverage of sensor nodes. The existing approaches (often RSSI measurement-based), however, suffer from heavy measurement cost and are not well suitable for the large-scale densely deployed WSNs. NRC-Map, a novel algorithm is put forward for sensor nodes radio coverage mapping. The algorithm is based on the RSSI values collected by the neighbor nodes. According to the spatial relationship, neighbor nodes are mapping to several overlapped sectors. By use of the least squares fitting method, a log-distance path loss model is established for each sector. Then, the max radius of each sector is computed according to the path loss model and the given signal attenuation threshold. Finally, all the sectors are overlapped to estimate the node radio coverage. Experimental results show that the method is simple and effectively improve the prediction accuracy of the sensor node radio coverage.

基于路径相似表与个体迁移策略的多路径覆盖测试

将遗传算法用于多路径覆盖测试中是个研究热点,在新旧种群迭代过程中,旧种群中可能包含其他子种群的优秀个体,这部分个体未被充分利用,造成资源浪费;同时,种群中的个体数会远大于可达路径数,而每个个体都会经过某一条可达路径,这样会有多个个体经过同一条路径,导致重复计算个体与目标路径的相似度。基于此,提出结合路径相似表与个体迁移的多路径覆盖测试方法以提高测试效率。通过路径相似表存储已计算得到的路径相似度值,避免该值被重复计算,减少测试时间。在进化过程中,将个体路径与其他目标路径进行比较,若相似度达到阈值,则将此优秀个体迁移至该路径对应的子种群中,提高个体利用率并减少进化代数。由实验可知,该方法与其他六种同类经典方法在八个程序上的平均生成时间降低最高达44.64%,最低为2.64%,平均进化代数降低最高达35.08%,最低为6.13%,故该方法有效地提高了测试效率。

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

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

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

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

结合SVM与XGBoost的链式多路径覆盖测试用例生成

机器学习方法可很好地与软件测试相结合,增强测试效果,但少有学者将其运用于测试数据生成方面.为进一步提高测试数据生成效率,提出一种结合SVM(support vector machine)和XGBoost(extreme gradient boosting)的链式模型,并基于此模型借助遗传算法实现多路径测试数据生成.首先,利用一定样本训练若干个用于预测路径节点状态的子模型(SVM和XGBoost),通过子模型的预测精度值筛选最优子模型,并根据路径节点顺序将其依次链接,形成一个链式模型C-SVMXGBoost(chained SVM and XGBoost).在利用遗传算法生成测试用例时,使用训练好的链式模型代替插桩法获取测试数据覆盖路径(预测路径),寻找预测路径与目标路径相似的路径集,对存在相似路径集的预测路径进行插桩验证,获取精确路径,计算适应度值.在交叉变异过程中引入样本集中路径层级深度较大的优秀测试用例进行重用,生成覆盖目标路径的测试数据.最后,保留进化生成中产生的适应度较高的个体,更新链式模型C-SVMXGBoost,进一步提高测试效率.实验表明,C-SVMXGBoost较其他各对比链式模型更适合解决路径预测问题,可提高测试效率.并且通过与已有经典方法相比,所提方法在覆盖率上提高可达15%,平均进化代数也有所降低,在较大规模程序上其降低百分比可达65%.

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

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

面向动态学习环境的自适应学习路径推荐模型

自适应学习路径作为实现个性化学习的一项关键技术,受到研究者广泛关注。近年来,强化学习成为自适应学习路径推荐的主流方法,但在动态学习环境表征的完整性和学习路径的适应性方面仍存在不足。基于此,文章提出了融合领域知识特征的自适应学习路径推荐模型。首先,模型将知识点概念覆盖和难度两个特征引入动态学习环境中,使对动态学习环境的表征更完整。其次,采用深度强化学习算法实现学习路径的推荐,提升学习路径的适应性。最后,开展技术对比实验和应用实验。技术对比实验表明,该模型提高了学习路径的有效性和适应性。应用实验表明,该模型可以准确地判断学习者的薄弱知识点概念,并能为学习者推荐适合其认知特征的自适应学习路径。

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

[目的]针对无人艇(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,也在显著降低。本文提出的算法能实现过程剂量和累积剂量最优控制的全覆盖路径规划,另外算法可以协同规划多单元路径,显著降低单体累积剂量,对辐射环境下区域作业的辐射防护有重要意义。

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

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

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

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