基于顺序扩展一致性包算法的多无人机分布式任务分配

以异构多无人机协同执行复杂的耦合多任务为背景,提出一种求解分布式任务分配问题非死锁的顺序扩展一致性包算法.首先,建立考虑任务载荷资源、任务时序、威胁区等约束条件的时序多任务分配模型;其次,对一致性包算法的任务包构建过程和冲突消解规则进行扩展,并设计一种基于有向图深度优先搜索的方法进行任务方案的死锁检测和修正,以实现无冲突和无死锁的任务分配;然后,将关联任务之间的时序约束转化为软时间窗约束,利用顺序分层的策略进行求解;最后,为了提高任务分配结果的可靠性,采用Dubins曲线路径将航路规划耦合到任务分配中.仿真实验表明,所提出的算法能够快速有效地求解异构多无人机分布式耦合多任务分配问题,具备良好的最优性和时效性.     

多无人机空中加油的最优会合航路规划

为了空中加油能面向多架无人机,本文提出了空中加油的三维最优会合航路规划算法.多架无人机分布在不同区域,需要加油机沿预定的规划航路飞行会合,以完成空中加油任务.由于加油机可同时服务的受油机数量有限,需要寻找最优分配策略将无人机预分配至不同加油区域与之会合.本文首先根据加、受油机在各加油区域的最短会合时间,将最优分配问题建模为整数线性规划问题,求解得到加油机与各无人机的最优会合点.随后,本文提出了三维空间Dubins路径延长算法,保证各无人机按照分配结果与加油机同时到达会合点.最后,分别针对二维和三维多架无人机空中加油任务进行仿真.仿真结果表明本文提出的最优会合航路规划算法得到的Dubins航路,可以保证空中加油会合任务在最短时间内完成.     

面向目标跟踪的多机协同通信保持控制

由于无人机存在通信和测量约束的情况,远程无人机执行持续目标跟踪任务时无法直接与地面站保持通信,需要其他无人机作为通信中继方可与地面站建立可靠的通信连接.基于Dubins曲线,采用最小转弯半径和航向调整相结合的方法对具有初始和终止航向角约束的多无人机进行协同航路规划,确保所有无人机同时到达指定位置,形成多机协同通信保持的初始构型.针对随机移动目标,在多机协同通信保持的动态过程中,考虑平台性能、通信约束、碰撞规避等约束条件,采用非线性模型预测控制(NMPC)实现无人机协同分布式在线优化.在确保无人机通信中继保持的前提下,有效提高了算法的实时性.仿真结果表明了该算法的有效性.     

Multi-UAV Velocity and Trajectory Scheduling Strategies for Target Classification by a Single Human Operator

This work addresses the problem of enabling a single human operator to individually inspect targets for a fixed amount of time in a reconnaissance mission. The task of the operator is to classify the targets as friends or foes in real time, as they appear in video feeds from multiple UAVs. In order to account for cognitive limitations, the human is modeled as a single processing unit that can only execute one task at a time. A task is defined as a target inside the field of view of a given UAV, that needs to be inspected. Under the assumptions of this model, a linear program (LP) formulation is used to optimally find each task’s arrival time and latency in the system such that the human operator can inspect each target individually for some time Δt. Previous work by the authors investigated the idea of using UAV velocity modifications to meet the timing schedule specified by the LP solution. In this paper, the idea of UAV trajectory changes is introduced by modeling the UAVs as Dubins vehicles. Modifications to the bounds on the LP constraints are derived based on Dubins trajectories. The new bounds ensure that the LP solution returns a timing schedule achievable via maneuvers that combine velocity and trajectory changes to the UAVs’ flight plans. An on-line algorithm is developed that constructs and commands these velocity and trajectory changes in real time when conflicts arise. Correctness properties of this algorithm are analyzed and discussed for mission scenarios where the location of the targets is unknown and targets are discovered by the UAVs in real time.     

Co-operative path planning of multiple UAVs using Dubins paths with clothoid arcs

This paper describes co-operative path planning of a group of unmanned aerial vehicles (UAVs). The problem undertaken for this study is that of simultaneous arrival on target of a group of UAVs. The problem of path planning is formulated in order to produce feasible (flyable and safe) paths and the solution is divided into three phases. The first phase is that of producing flyable paths, the second is to add extra constraints to produce safe paths that do not collide with other UAV members or with known obstacles in the environment, and the third is to produce paths for simultaneous arrival. In the first phase, Dubins paths with clothoid arcs are used to produce paths for each UAV. These paths are produced using the principles of differential geometry. The second phase manipulate these paths to make them safer by meeting safety constraints: (i) to maintain minimum separation distance, (ii) to produce non-intersection of paths at equal lengths, and (iii) to fly-through intermediate way-points/poses. Finally, in the third phase, the simultaneous arrival is achieved by making all the paths equal in lengths. Some simulation results are given to illustrate the technique.     

Unsupervised learning‐based flexible framework for surveillance planning with aerial vehicles

The herein studied problem is motivated by practical needs of our participation in the Mohamed Bin Zayed International Robotics Challenge (MBZIRC) 2017 in which a team of unmanned aerial vehicles (UAVs) is requested to collect objects in the given area as quickly as possible and score according to the rewards associated with the objects. The mission time is limited, and the most time‐consuming operation is the collection of the objects themselves. Therefore, we address the problem to quickly identify the most valuable objects as surveillance planning with curvature‐constrained trajectories. The problem is formulated as a multivehicle variant of the Dubins traveling salesman problem with neighborhoods (DTSPN). Based on the evaluation of existing approaches to the DTSPN, we propose to use unsupervised learning to find satisfiable solutions with low computational requirements. Moreover, the flexibility of unsupervised learning allows considering trajectory parametrization that better fits the motion constraints of the utilized hexacopters that are not limited by the minimal turning radius as the Dubins vehicle. We propose to use Bézier curves to exploit the maximal vehicle velocity and acceleration limits. Besides, we further generalize the proposed approach to 3D surveillance planning. We report on evaluation results of the developed algorithms and experimental verification of the planned trajectories using the real UAVs utilized in our participation in MBZIRC 2017.     

Toward Optimal Rendezvous of Multiple Underwater Gliders: 3D Path Planning with Combined Sawtooth and Spiral Motion

In this paper, a path planning system is proposed for optimal rendezvous of multiple underwater gliders in three-dimensional (3D) space. Inspired by the Dubins Paths consisting of straight lines and circular arcs, this paper presents the first attempt to extend the 3D Dubins curve to accommodate the characteristic glider motions include upwards and downwards straight glides in a sawtooth pattern and gliding in a vertical spiral. This modified 3D Dubins scheme is combined with genetic algorithm (GA), together with a rendezvous position selection scheme to find rendezvous trajectories for multiple gliders with minimal energy consumption over all participating vehicles. The properties and capabilities of the proposed path planning methodology are illustrated for several rendezvous mission scenarios. First, a simple application was performed for a single glider to rendezvous with a fix dock. Simulation results show the proposed planner is able to obtain more optimized trajectories when compared with the typical Dubins trajectory with nominal velocity. Additional representative simulations were run to analyse the performance of this path planner for multiple gliders rendezvous. The results demonstrate that the proposed path planner identifies the optimal rendezvous location and generates the corresponding rendezvous trajectories for multiple gliders that ensures they reach their destination with optimized energy consumption.     

基于SEAD任务特性约束的协同任务分配方法

以多异构无人机执行SEAD任务为背景,开展协同任务分配问题建模、算法设计和仿真分析.采用图论的方法完成问题的建模,将无人机本体等效为Dubins Car模型,并对其在相应目标处执行侦查、打击、评估任务时的进入角度进行约束,通过Dubins路径完成对无人机飞行路径的等效,采用分布式遗传算法完成对问题的快速求解.研究结果表明,带有路径末端角度约束的任务分配问题具有较好的实用意义,分布式遗传算法可有效处理实时任务分配问题,完成任务空间的快速决策.     

A Minimum Risk Approach for Path Planning of UAVs

In the last years, the Flight Mechanics Research Group of Politecnico di Torino started a wide research activity, focused on exploration and implementation of path planning algorithms for commercial autopilots, typically adopted on unmanned vehicles. Different path planning approaches were implemented in a Matlab/Simulink based tool, generating waypoints sequences with four methods: geometric predefined trajectories, manual waypoints definition, automatic waypoints distribution (i.e. optimizing camera payload capabilities) and, finally, a comprehensive A*-based approach. The tool was also integrated with functions managing the maps used for planning. In this paper, two approaches to path planning in presence of orographic obstacles are detailed. The first algorithm is subdivided in three phases: the generation of a risk map associated with the ground orography, the transformation of the map in a digraph analyzed with the A* algorithm (to obtain the path with minimum risk/minimum distance) and finally the smoothing phase, to obtain a flyable waypoint sequence, realized with the Dubins curves. The structure of this method was defined and implemented, but its optimization is still in progress. The second algorithm is based on the same risk map, but optimizing polynomial curves with a genetic algorithm. This method produces a flyable waypoints sequence, minimizing a cost function reflecting path length and collision risk. An extension of this path solver, including aircraft performance constraints, was also considered. This method was tested on sample domains and its computational cost has still to be evaluated before the implementation in the tool.     

路网约束下异构机器人系统路径规划方法

由无人机(Unmanned aerial vehicles, UAV)和地面移动机器人组成的异构机器人系统在协作执行任务时,可以充分发挥两类机器人各自的优势.无人机运动灵活,但通常续航能力有限;地面机器人载荷多,适合作为无人机的着陆平台和移动补给站,但运动受路网约束.本文研究这类异构机器人系统协作路径规划问题.为了降低完成任务的时间代价,提出一种由蚁群算法(Ant colony optimization, ACO)和遗传算法(Genetic algorithm, GA)相结合的两步法对地面机器人和无人机的路线进行解耦,同时规划地面机器人和无人机的路线.第1步使用蚁群算法为地面机器人搜索可行路线.第2步对无人机的最优路径建模,采用遗传算法求解并将无人机路径长度返回至第1步中,用于更新路网的信息素参数,从而实现异构协作系统路径的整体优化.另外,为了进一步降低无人机的飞行时间代价,研究了无人机在其续航能力内连续完成多任务的协作路径规划问题.最后,通过大量仿真实验验证了所提方法的有效性.     

多约束条件下无人机航迹规划

针对多约束条件下的无人机航迹快速规划问题,建立了导航精度约束下无人机航迹规划模型,并设计了“基于Dijkstra算法的航迹规划法”求解模型。通过校正策略优选、校正方案优选和O-D邻接矩阵处理方式,简化搜索路径,降低计算量,提高执行效率,从而实现对传统Dijkstra算法的改进。在满足导航精度约束条件的前提下,以航迹长度最短和经过校正点数量最少为研究目标进行仿真实验,并将所得结果与传统Dijkstra算法和遗传算法所得结果分别进行对比,发现此算法在精度与复杂度方面均优于传统算法和遗传算法。此结果表明,导航精度约束下无人机航迹规划模型和“基于Dijkstra算法的航迹规划法”在解决多约束下无人机航迹规划问题方面具有一定的正确性、有效性和先进性。     

A vision-based collision avoidance technique for micro air vehicles using local-level frame mapping and path planning

This paper presents a vision-based collision avoidance technique for small and miniature air vehicles (MAVs) using local-level frame mapping and path planning. Using computer vision algorithms, a depth map that represents the range and bearing to obstacles is obtained. Based on the depth map, we estimate the range, azimuth to, and height of obstacles using an extended Kalman filter that takes into account the correlations between obstacles. We then construct maps in the local-level frame using cylindrical coordinates for three dimensional path planning and plan Dubins paths using the rapidly-exploring random tree algorithm. The behavior of our approach is analyzed and the characteristics of the environments where the local path planning technique guarantees collision-free paths and maneuvers the MAV to a specific goal region are described. Numerical results show the proposed technique is successful in solving path planning and multiple obstacle avoidance problems for fixed wing MAVs.     

基于GPS/DR的地图匹配方法的研究与实现

研究了地图辅助定位技术在GPS/DR组合定位系统中的应用,给出了一种基于D-S证据推理的地图匹配算法,该算法通过对车辆轨迹与数字地图模块提供的路径相比较,把基于各种传感器的车辆位置与道路网络联系起来,并通过匹配过程来确定车辆关于地图的最大可能位置.仿真实验结果表明,应用该地图匹配算法能够有效的提高组合定位系统的定位精度、减小误差,改善对航线的跟踪质量.     

中国邮递员问题的动态规划算法研究

在动态规划的决策过程思想基础上,针对无向中国邮递员问题,提出了一个新的搜索算法CPDPA(Chinese postman decision process algorithm),首次实现了中国邮递员问题的动态规划求解．针对中国邮递员问题不能直接应用于决策思想,提出了弧点转换算法CEPA(convert edge to Doint algorithm),建立了该问题适用于决策的模型．进而针对这一模型,提出了多阶段决策过程模型转换算法MDPMCA(multistep decision process model convert algorithm),转换所得模型符合多阶段决策过程需求,可用CPDPA算法求解中国邮递员问题．对每一算法都给出了其网络应用实例．对算法的正确性和理论性做出了证明,并对最优性原理在中国邮递员问题上做了一定扩展．     

基于Dubins路径的无人艇运动规划算法

针对无人艇运动规划问题,通过Dubins路径的理论分析,提出一种利用纯粹几何方法的Dubins路径计算方法。该方法中没有出现解方程组的运算,而是首先根据无人艇运动状态计算转向圆,然后利用几何方法计算转向圆间的公切线,最后通过公切线连接得到Dubins路径。通过5组仿真实验验证了所提方法的有效性。前4组仿真实验分别设计了计算Dubins路径过程中可能出现的各种情形,以验证算法适用于多种情况的Dubins路径计算。最后一组仿真实验用于无人艇的路径规划及运动状态调整,仿真结果表明,基于Dubins路径的无人艇运动规划算法是可行的。     

An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning

This paper formulates the global route planning problem for the unmanned aerial vehicles (UAVs) as a constrained optimization problem in the three-dimensional environment and proposes an improved constrained differential evolution (DE) algorithm to generate an optimal feasible route. The flight route is designed to have a short length and a low flight altitude. The multiple constraints based on the realistic scenarios are taken into account, including maximum turning angle, maximum climbing/gliding slope, terrain, forbidden flying areas, map and threat area constraints. The proposed DE-based route planning algorithm combines the standard DE with the level comparison method and an improved strategy is proposed to control the satisfactory level. To show the high performance of the proposed method, we compare the proposed algorithm with six existing constrained optimization algorithms and five penalty function based methods. Numerical experiments in two test cases are carried out. Our proposed algorithm demonstrates a good performance in terms of the solution quality, robustness, and the constraint-handling ability.     

基于最小二乘法的联合地图匹配算法的研究

地图匹配是车辆监控与管理系统的主要功能之一.从提高地图匹配算法准确率和缩短监控系统所需地图匹配时间的角度出发,提出了一种新的基于最小二乘法的联合地图匹配算法.该算法利用最小二乘法改进几何线到线地图匹配算法和拓扑结构地图匹配算法,根据路段混合使用算法,能实时准确地将行驶车辆匹配到相应的道路上.实验仿真表明,该算法为几何线到线在平行路段匹配不准的问题和拓扑范围越大匹配越不准的问题提供了有效的解决方法,具体可应用于路网密集的区域,为路网密集区域的道路定位与路径匹配提供准确和快捷的途径.     

多特征融合的异视角目标关联算法

目标关联在协同多目标探测中具有重要意义,受视角变换等因素的影响,传统目标关联算法在异视角目标观测情况下效果较差。本文提出了一种基于拓扑特征与颜色特征融合的无人机协同侦查目标关联算法,通过利用无人机提供的位置、姿态及其搭载传感器获得的多维特征数据,提取出目标的拓扑特征及颜色特征,并通过D-S证据理论融合多维特征,完成对异视角目标群的关联。实验表明,这种算法框架能够有效帮助无人机完成对目标群的关联任务。     

基于Multi-Agent系统的多飞行器协同路径规划方法的研究

无人多飞行器(UAV)协同技术是当前分布式人工智能的一个热点领域,其中一个关键技术在于如何实现多UAV集群根据复杂环境中目标、威胁、地形变化以及各UAV之间的性能约束动态进行实时性航路规划。提出一种基于Multi-agent系统的多UAV对实时动态多目标进行路径规划的方法。其核心是基于Multi-agent系统的decen-tralized控制方案。在Multi-agent平台上,实现了agent对于环境、目标、任务等路劲规划约束条件的建模,同时提出了多agent动态路径规划方法的实现方案。方案使用DisCSP模型框架,将基于真实复杂战场环境的实时路径规划问题所涉及的多复杂限制条件,抽象成Multi-agent系统中的各个约束条件,通过多agent间Dynamic Programming过程求解多UAV实时动态多目标的路径规划和协同任务分配的ABT算法,并实现在动态威胁和地形以及动态目标下具备集群协同能力的多UAV实时仿真系统。     

空地异构机器人系统协作巡逻路径规划方法EI北大核心CSCD

空地异构机器人系统由空中无人机和地面无人车组成,当两者协作执行持续巡逻任务时,使用无人车充当无人机的地面移动补给站能够解决无人机续航能力不足的问题.运动受限于路网中的无人车必须在适当地点为无人机补充能量,这使得两者的路径高度耦合,给空地协作路径规划带来了挑战.针对此问题,本文通过分析无人机能量、路网、空地汇合时间、巡逻任务全覆盖等多种约束,以无人机完成全部巡逻任务的总距离为代价,建立了空地协作巡逻路径规划模型.该模型可推广至多架无人机与多辆无人车协作的情形.然后,采用遗传算法与蚁群算法相融合的方法,对无人机巡逻路径和无人车能量补给路径进行优化求解.仿真实验表明,本文的方法不仅可以得到很好的路径规划结果,而且较其他算法具有更优的收敛性和执行速度.