CN102929285A - Multi-target distribution and flight path planning method for multiple rescue helicopters - Google Patents

Abstract

Translated fromChinese

本发明公开一种多救援直升机多目标分配与航迹规划方法，涉及航空应急救援技术领域。包括航空救援任务执行可行度评估与灾区地图图像处理；通过救援任务执行可行度评估获得可行度矩阵；将可行度矩阵作为解矩阵X_ij的系数矩阵，用匈牙利算法针对救援直升机和目标点之间数量不相同的任务求解分配结果；采用图像处理方法、形态学特征提取安全区域拓扑结构得到航迹解空间，利用启发式A*搜索算法在航迹解空间中得到最短路径，结合多机多目标分配结果，形成直升机执行救援任务的应急预案；调用Google Earth飞行模拟API演示应急救援预案，做飞行前准备，提高航空应急救援效率和安全性。本方法简单、时间复杂度低、航迹规划过程直观、结果清晰。

The invention discloses a multi-rescue helicopter multi-target allocation and track planning method, and relates to the technical field of aviation emergency rescue. Including aviation rescue mission execution feasibility evaluation and disaster area map image processing; the feasibility matrix is obtained through the rescue mission execution feasibility evaluation; the feasibility matrix is used as the coefficient matrix of the solution matrix X_ij , and the Hungarian algorithm is used for the distance between the rescue helicopter and the target point. Solve the distribution results for tasks with different numbers; use image processing methods and morphological features to extract the topological structure of the safe area to obtain the track solution space, and use the heuristic A* search algorithm to obtain the shortest path in the track solution space, combined with multi-machine and multi-target Assign the results to form an emergency plan for helicopters to perform rescue missions; call the Google Earth flight simulation API to demonstrate the emergency rescue plan, make pre-flight preparations, and improve the efficiency and safety of aviation emergency rescue. The method is simple, has low time complexity, intuitive trajectory planning process and clear results.

Description

Translated fromChinese

多救援直升机多目标分配与航迹规划方法Multi-target allocation and trajectory planning method for multiple rescue helicopters

技术领域technical field

本发明涉及航空应急救援技术领域，尤其涉及重大自然灾害条件下航空应急救援预案，为提高航空应急救援效率和安全性提供丰富的救援前准备的一种多救援直升机多目标分配以及救援飞行航迹的规划方法。The present invention relates to the technical field of aviation emergency rescue, in particular to the aviation emergency rescue plan under the condition of major natural disasters, a multi-rescue helicopter, multi-target allocation and rescue flight track that provide abundant pre-rescue preparations for improving the efficiency and safety of aviation emergency rescue planning method.

背景技术Background technique

重大自然灾害发生后，以通用航空直升机为基础的飞行救援具有快速、高效、受地理空间限制较少等优势，能够深入受灾严重地区进行侦查、运送伤员和物资，对减少人民生命财产损失有着重要意义。然而，由于我国缺乏一套较为完善的航空救援运行法规及应急救援方案，救援效率低下且安全性得不到保障。以“5.12”汶川大地震为例，民航局调集了三十一架民航直升机实施救援，然而由于灾区资料和飞行情报准备准备不足，飞行员在不熟悉地形、气象信息、救援目标和受灾严重程度情况下执行救援任务，救援初期的效率和飞行安全受到很大影响。由此可见，航空应急救援飞行前准备对于救援任务的执行显得至关重要，而救援路线的规划又是飞行准备中的核心问题，必须在保证航空救援飞行安全的前提下，快速规划出能在最短时间内能完成救援任务的可行飞行路径。同时，由于重大灾害发生后，往往需要多架直升机对多个救援目标点同时进行搜索救援，如何合理地对直升机和目标点的分配、规划救援飞行的往返路径、制定航空应急救援预案，是提高航空应急救援效率和安全性的关键问题。After the occurrence of major natural disasters, the flight rescue based on general aviation helicopters has the advantages of being fast, efficient, and less restricted by geographical space. It can go deep into the severely affected areas for investigation, transport the wounded and supplies, and play an important role in reducing the loss of people's lives and property. significance. However, due to the lack of a relatively complete aviation rescue operation regulations and emergency rescue plan in our country, the rescue efficiency is low and the safety cannot be guaranteed. Taking the "5.12" Wenchuan Earthquake as an example, the Civil Aviation Administration mobilized 31 civil aviation helicopters to carry out rescue operations. However, due to insufficient preparation of disaster area data and flight information, the pilots were not familiar with the terrain, weather information, rescue targets and the severity of the disaster. The efficiency and flight safety in the early stage of rescue will be greatly affected. It can be seen that the pre-flight preparation for aviation emergency rescue is very important for the execution of rescue missions, and the planning of rescue routes is the core issue in flight preparation. The feasible flight path that can complete the rescue mission in the shortest time. At the same time, due to the occurrence of major disasters, multiple helicopters are often required to search and rescue multiple rescue targets at the same time. How to reasonably allocate helicopters and target points, plan the round-trip path of rescue flights, and formulate aviation emergency rescue plans is the key to improving Key issues of aviation emergency rescue efficiency and safety.

国内的航迹规划研究主要集中在军事领域，包括军用飞机、巡航导弹、可移动机器人等。航迹规划的本质是路径搜索问题，常用算法主要有基于概略图的规划方法和基于单元分解的规划方法。其中，基于概略图的方法通常用于平面且实时性要求较低的航迹规划，基于单元分解的方法规划精度受到单元格划分精细程度的限制，单元格划分越细则规划航迹越优。但是数据量和计算量会增大，规划耗时增加。国外学者提出采用动态规划的方法和0-1规划（BIP）算法求解三维航迹，该方法计算简单且能避免陷入局部最优。多机协同搜索问题的本质是多目标的分配问题，常用算法有基于分层模糊推理的方法、遗传算法、蚁群算法和模拟退火算法等，这些算法都有效地解决了所用领域的多目标分配问题，但是在航空应急救援领域的应用目前还未曾见到。Domestic research on trajectory planning is mainly concentrated in the military field, including military aircraft, cruise missiles, and mobile robots. The essence of trajectory planning is a path search problem, and the commonly used algorithms mainly include planning methods based on outline graphs and planning methods based on cell decomposition. Among them, the method based on the outline map is usually used for planar and less real-time track planning. The planning accuracy of the method based on cell decomposition is limited by the fineness of the cell division. The finer the cell division, the better the planning track. However, the amount of data and calculation will increase, and the planning time will increase. Foreign scholars have proposed to use the method of dynamic programming and 0-1 programming (BIP) algorithm to solve the three-dimensional track. This method is simple to calculate and can avoid falling into local optimum. The essence of the multi-machine collaborative search problem is the assignment of multi-objectives. Commonly used algorithms include methods based on hierarchical fuzzy reasoning, genetic algorithms, ant colony algorithms, and simulated annealing algorithms. However, the application in the field of aviation emergency rescue has not been seen yet.

发明内容Contents of the invention

本发明目的在于提供一种救援直升机多机多目标分配与飞行航迹的规划方法，以期建立重大自然灾害条件下，多个救援直升机对多个救援目标实施救援的统一预案；为提高救援飞行的安全性和效率做好充分的飞行前准备。The purpose of the present invention is to provide a rescue helicopter multi-machine multi-target distribution and planning method of flight track, in order to establish a unified plan for multiple rescue helicopters to rescue multiple rescue targets under the condition of major natural disasters; Safety and efficiency are fully prepared before flight.

实现本发明目的之技术解决方案如下：一种多救援直升机多目标分配与航迹规划方法，包括航空救援任务执行可行度评估与灾区地图图像的处理；所述的救援任务执行可行度评估是指分析某直升机实施某次救援任务的可行性，获得可行度矩阵；将可行度矩阵作为解矩阵X_ij的系数矩阵，选用匈牙利算法针对救援直升机和目标点之间数量不相同的任务求解多直升机与救援目标之间的分配结果；所述的灾区地图图像的处理是指从数字高程地图中提取单层等高线图，并对该图进行二值化图像处理得到以等高线表示的障碍物图，其中黑色表示障碍物，白色表示可供飞行区域；利用形态学膨胀方法剔除白色飞行区域内的不安全区域，并使用腐蚀和骨架化方法提取安全飞行区域的拓扑结构，从而得到以二值图像表示的航迹规划解空间；选用启发式最短路径搜索算法A*算法在二维平面上搜索得到最短航迹；结合多机多目标分配结果，形成直升机执行救援任务的应急预案；调用Google Earth飞行模拟API演示应急救援预案，做充分的飞行前准备。The technical solution to realize the object of the present invention is as follows: a multi-objective distribution and track planning method of multi-rescue helicopters, including air rescue mission execution feasibility evaluation and disaster area map image processing; described rescue mission execution feasibility evaluation refers to Analyze the feasibility of a helicopter to implement a certain rescue mission, and obtain the feasibility matrix; use the feasibility matrix as the coefficient matrix of the solution matrix X_ij , and use the Hungarian algorithm to solve the task of multi-helicopter and target points with different numbers. Allocation results between rescue targets; the processing of the disaster area map image refers to extracting a single-layer contour map from a digital elevation map, and performing binary image processing on the map to obtain obstacles represented by contour lines In the figure, black represents obstacles, and white represents available flight areas; use morphological expansion method to remove unsafe areas in white flight areas, and use corrosion and skeletonization methods to extract the topology of safe flight areas, so as to obtain binary values The trajectory planning solution space represented by the image; the heuristic shortest path search algorithm A* algorithm is used to search the shortest trajectory on the two-dimensional plane; combined with the results of multi-aircraft and multi-target allocation, an emergency plan for helicopter rescue missions is formed; Google Earth is called The flight simulation API demonstrates the emergency rescue plan and makes full pre-flight preparations.

进一步地，所述的救援任务执行可行度评估包括对基地与目标点之间的距离、海拔高度、净空环境、地理环境、任务类型等影响因素的评估，针对可行度评估影响因素中的定量因子如海拔高度采用基于阈值的区间量化处理方法进行定量评估，而对定性因子如任务类型采用模糊综合评价方法转换为定量评估；再利用专家调查法得到影响因素的权重值，利用线性加权求和得到可行度值，该值越大表明该机越适合执行该项救灾任务；通过两次循环得到可行度矩阵。Further, the evaluation of the feasibility of the execution of the rescue mission includes the evaluation of the distance between the base and the target point, the altitude, the clearance environment, the geographical environment, the task type and other influencing factors, and the quantitative factors in the influencing factors of the feasibility assessment are For example, the altitude is quantitatively evaluated by the threshold-based interval quantification processing method, and the qualitative factors such as task type are converted into quantitative evaluation by using the fuzzy comprehensive evaluation method; then the expert survey method is used to obtain the weight value of the influencing factors, and the linear weighted sum is used to obtain Feasibility value, the larger the value, the more suitable the aircraft is to perform the disaster relief mission; the feasibility matrix is obtained through two loops.

进一步地，所述的灾区地图图像的处理包括如下步骤：Further, the processing of the disaster area map image includes the following steps:

（1）获得SRTM数字高程地图后，用Global Mapper输出矢量DEM文件；(1) After obtaining the SRTM digital elevation map, use Global Mapper to output the vector DEM file;

（2）用Surfer输出单层等高线图；(2) Use Surfer to output a single-layer contour map;

（3）用Matalab二值化处理得到等高线表示的障碍物图；(3) Use Matalab binarization to obtain the obstacle map represented by contour lines;

（4）用Matalab对障碍物图进行膨胀和腐蚀；(4) Dilate and corrode the obstacle map with Matalab;

（5）骨架化特征提取，得到以二值图像表示的航迹规划空间。(5) Skeletonized feature extraction to obtain the track planning space represented by binary images.

更进一步地，所述获得SRTM数字高程地图后还需要进行如下操作步骤：Furthermore, after the SRTM digital elevation map is obtained, the following steps are required:

（1）使用地图绘制软件Global Mapper将SRTM格式数据转换为XYZ格式，并保存为等高线地图KML文件；(1) Use the mapping software Global Mapper to convert the SRTM format data into XYZ format, and save it as a contour map KML file;

（2）加载等高线地图KML文件获得灾区数字地图；(2) Load the contour map KML file to obtain the digital map of the disaster area;

（3）利用A*算法在二维平面上搜索得到最短航迹结合多直升机与救援目标之间的分配结果，形成直升机执行救援任务的应急预案。(3) Using the A* algorithm to search on the two-dimensional plane to obtain the shortest track combined with the allocation results between multiple helicopters and rescue targets, an emergency plan for helicopters to perform rescue missions is formed.

本发明主要解决了两个关键问题：The present invention mainly solves two key problems:

（1）研究并提出了基于救援任务可行度的多机多目标协同搜索算法，将应急救援直升机合理地分配到目标点，避免由于救援目标的盲目性导致的混乱局面，提高了航空应急救援效率；(1) Research and propose a multi-aircraft multi-target collaborative search algorithm based on the feasibility of rescue missions, reasonably assign emergency rescue helicopters to target points, avoid the chaos caused by the blindness of rescue targets, and improve the efficiency of aviation emergency rescue ;

（2）提出了救援直升机执行任务的航迹规划设计方案：首先利用数学形态学图像处理技术对数字高程地图和等高线地图进行处理，得到以二值图像表示的航迹规划空间，并基于启发式最短路径搜索算法求解出二维平面上的最短路径；然后根据直升机的飞行性能和救援任务的特点，将三维空间航迹规划问题分解为多个二维平面航迹规划问题；最后，结合多机多目标分配算法，制定救援直升机执行救援任务的预案，为救援飞行前准备提供了详细参考，提高了应急救援的效率和安全性。(2) A trajectory planning and design scheme for rescue helicopter missions is proposed: firstly, the digital elevation map and contour map are processed by mathematical morphology image processing technology, and the trajectory planning space represented by binary images is obtained, and based on The heuristic shortest path search algorithm solves the shortest path on the two-dimensional plane; then, according to the flight performance of the helicopter and the characteristics of the rescue mission, the three-dimensional space trajectory planning problem is decomposed into multiple two-dimensional plane trajectory planning problems; finally, combined with The multi-aircraft multi-target allocation algorithm formulates a plan for rescue helicopters to carry out rescue missions, providing detailed reference for preparations before rescue flights, and improving the efficiency and safety of emergency rescue.

本发明具有如下优点与积极效果：The present invention has following advantage and positive effect:

1、水平航迹规划通常采用构造Voronoi图，并给图中多边形设置权重，然后通过建立目标函数求代价最小的边作为最短路径；本发明采用图像处理方法、形态学特征提取安全区域拓扑结构得到航迹解空间，并利用启发式A*搜索算法在航迹解空间中得到最短路径；该方法简单、时间复杂度低、航迹规划过程直观、结果清晰。1. Horizontal track planning usually adopts the construction Voronoi diagram, and sets weights for the polygons in the figure, and then seeks the side with the smallest cost by establishing an objective function as the shortest path; the present invention uses image processing methods and morphological features to extract the topological structure of the safe area to obtain Track solution space, and use the heuristic A* search algorithm to obtain the shortest path in the track solution space; the method is simple, the time complexity is low, the track planning process is intuitive, and the result is clear.

2、基于可行度矩阵的多直升机多目标分配算法全面考虑了影响航空应急救援任务可行性，针对救援直升机数量和受灾点个数不匹配问题，采用扩展的匈牙利算法转换为平衡指派问题，通过求解可行度矩阵的解矩阵即可得到直升机与灾区目标点间的分配方案；该方法将理论联系实际，形成了切实可行的直升机多目标分配方案。2. The multi-helicopter and multi-objective allocation algorithm based on the feasibility matrix fully considers the feasibility of affecting aviation emergency rescue tasks. For the mismatch between the number of rescue helicopters and the number of disaster-stricken points, the extended Hungarian algorithm is used to convert it into a balanced assignment problem. By solving The solution matrix of the feasibility matrix can be used to obtain the allocation scheme between the helicopter and the target points in the disaster area; this method combines theory with practice and forms a feasible multi-objective allocation scheme for helicopters.

3、结合直升机多目标分配方案和航迹规划方法形成重大自然灾害条件下的航空应急救援方案，并基于该方案开发了航空应急救援指挥辅助系统，该系统能快速加载受灾区域的数字等高线图，通过设置受灾点和指挥中心的位置、救援资源，快速形成合理的应急救援预案，并调用Google Earth飞行模拟功能进行将预案进行演示，为提高航空应急救援效率和安全性作充分的飞行前准备。3. Combining the helicopter multi-target allocation scheme and the trajectory planning method to form an aviation emergency rescue scheme under the condition of major natural disasters, and based on this scheme, an aviation emergency rescue command auxiliary system was developed, which can quickly load the digital contour of the disaster-affected area Figure, by setting the location of the disaster point and command center, and rescue resources, quickly form a reasonable emergency rescue plan, and call the flight simulation function of Google Earth to demonstrate the plan, in order to improve the efficiency and safety of aviation emergency rescue before flight. Prepare.

附图说明Description of drawings

图1是本发明所述直升机多目标分配与航迹规划方法流程框图示意图。Fig. 1 is a schematic block diagram of the flow chart of the helicopter multi-target allocation and track planning method according to the present invention.

图2是本发明所述方法在计算机系统主流程中框图示意图。Fig. 2 is a schematic block diagram of the main flow of the computer system in the method of the present invention.

图3是将灾区等高线数字地图进行二值化图像处理后得到的障碍物示意图。Fig. 3 is a schematic diagram of obstacles obtained by binarizing the contour digital map of the disaster area.

图4是将障碍物图进行形态学图像处理方法后得到的二维飞行轨迹空间示意图。Fig. 4 is a schematic diagram of the two-dimensional flight track space obtained by subjecting the obstacle map to the morphological image processing method.

图5是二维飞行轨迹空间中利用启发式A*搜索算法得到的最短飞行路径示意图。Fig. 5 is a schematic diagram of the shortest flight path obtained by using the heuristic A* search algorithm in the two-dimensional flight trajectory space.

图6是标有救援任务的起点和终点的灾区数字高程地图示意图。Fig. 6 is a schematic diagram of a digital elevation map of the disaster area marked with the starting point and the ending point of the rescue mission.

图7是2100米所在高度层上的二维航迹解空间示意图。Figure 7 is a schematic diagram of the two-dimensional track solution space on the altitude layer of 2100 meters.

图8是3000米所在高度层上的二维航迹解空间示意图。Figure 8 is a schematic diagram of the two-dimensional track solution space on the altitude layer of 3000 meters.

图9是3000米所在高度层上对应的最短飞行航迹示意图。Figure 9 is a schematic diagram of the shortest flight path corresponding to the altitude of 3000 meters.

具体实施方式Detailed ways

下面结合附图对本发明的实施作进一步说明。The implementation of the present invention will be further described below in conjunction with the accompanying drawings.

参见图1所示，多救援直升机多目标分配与航迹规划方法，包括航空救援任务执行可行度评估与灾区地图图像的处理；所述的救援任务执行可行度评估是指分析某直升机实施某次救援任务的可行性，获得可行度矩阵；将可行度矩阵作为解矩阵X_ij的系数矩阵，选用匈牙利算法针对救援直升机和目标点之间数量不相同的任务求解多直升机与救援目标之间的分配结果；所述的灾区地图图像的处理是指从数字高程地图中提取单层等高线图，并对该图进行二值化图像处理得到以等高线表示的障碍物图，其中黑色表示障碍物，白色表示可供飞行区域；利用形态学膨胀方法剔除白色飞行区域内的不安全区域，并使用腐蚀和骨架化方法提取安全飞行区域的拓扑结构，从而得到以二值图像表示的航迹规划解空间；选用启发式搜索算法A*算法在以二值图像表示的航迹规划解空间即二维平面上搜索得到最短航迹；结合多机多目标分配结果，形成直升机执行救援任务的应急预案；调用Google Earth飞行模拟API演示应急救援预案，做充分的飞行前准备。Referring to Fig. 1, multi-rescue helicopter multi-target assignment and track planning method, including aviation rescue mission execution feasibility evaluation and disaster area map image processing; described rescue mission execution feasibility evaluation refers to the analysis of certain helicopter implementation Feasibility of the rescue mission, obtain the feasibility matrix; use the feasibility matrix as the coefficient matrix of the solution matrix X_ij , and use the Hungarian algorithm to solve the assignment between multiple helicopters and rescue targets for tasks with different numbers of rescue helicopters and target points Result; the processing of the disaster area map image refers to extracting a single-layer contour map from the digital elevation map, and carrying out binarization image processing on this map to obtain an obstacle map represented by contour lines, wherein black represents obstacles The white color represents the available flight area; the unsafe area in the white flight area is eliminated by using the morphological expansion method, and the topology of the safe flight area is extracted by using the erosion and skeletonization method, so as to obtain the flight path planning represented by the binary image Solution space; use the heuristic search algorithm A* algorithm to search for the shortest track in the track planning solution space represented by a binary image, that is, a two-dimensional plane; combine the results of multi-aircraft and multi-target allocation to form an emergency plan for helicopter rescue missions ;Call the Google Earth flight simulation API to demonstrate the emergency rescue plan and make full pre-flight preparations.

所述救援任务执行可行度评估是基于救援任务可行度的多机多目标分配，针对多目标点搜救任务类型、直升机性能、救援途中气象和地理环境不同，对救援任务执行的可行度进行评估，根据任务可行度矩阵对救援直升机进行合理的分配。可行度评估通常考虑下列因素：救援目标点任务类型及紧要程度，例如搜寻人员、空投物资、探察灾情、遥感摄影等，目标点与救援指挥中心的距离、目标作业点的地理要素特征，例如海拔高度、净空情况、地形特征，救援直升机性能特征，例如航程、飞行高度、搭载能力等，救援目标点气象特征，例如能见度、有无威胁低空飞行安全的云等天气现象。针对可行度评估影响因子中如“目标点与灾区的距离”可以采用基于阈值的区间量化方式进行定量评估，而对“任务类型、航空器性能”等定性评估因子采用模糊综合评价方法转换为定量评估，最后对各要素可行度评价值进行加权求和得到某直升机执行某救援任务的可行度。The evaluation of the execution feasibility of the rescue mission is based on the multi-aircraft multi-target allocation of the rescue mission feasibility, and the feasibility of the rescue mission execution is evaluated according to the different types of multi-target search and rescue missions, helicopter performance, weather and geographical environment during the rescue, According to the mission feasibility matrix, the rescue helicopters are allocated reasonably. Feasibility assessment usually considers the following factors: the type and urgency of the task of the rescue target point, such as searching for personnel, airdropping materials, detecting disaster situations, remote sensing photography, etc., the distance between the target point and the rescue command center, and the geographical features of the target operating point, such as altitude Altitude, clearance, terrain features, performance characteristics of rescue helicopters, such as range, flight altitude, carrying capacity, etc., meteorological characteristics of rescue target points, such as visibility, and weather phenomena such as clouds that threaten low-altitude flight safety. The threshold-based interval quantification method can be used for quantitative evaluation of the influencing factors of feasibility evaluation, such as "the distance between the target point and the disaster area", while the qualitative evaluation factors such as "task type, aircraft performance" can be converted into quantitative evaluation by fuzzy comprehensive evaluation method , and finally the feasibility evaluation value of each element is weighted and summed to obtain the feasibility of a helicopter performing a rescue mission.

多救援直升机进行多目标救援的评估问题可以描述成：n架直升机参与m个目的点搜寻救援工作，其中第i架航空器执行第j个目的点任务可行度为c_ij(1≤i≤n,1≤j≤m)，由元素c_ij构成的矩阵C称为可行度矩阵，记为C=(c_ij)_n×m，可行度越高表示该航空器更适于执行该点的任务。针对救援直升机和目标点之间数量不相同的任务指派问题，拟采用添加虚拟变量的方式转换为平衡指派问题，然后选用匈牙利算法来求解。The evaluation problem of multi-target rescue by multiple rescue helicopters can be described as: n helicopters participate in the search and rescue work of m destination points, and the feasibility of the i-th aircraft to perform the mission of the j-th destination point is c_ij (1≤i≤n, 1≤j≤m), the matrix C composed of elements c_ij is called the feasibility matrix, denoted as C=(c_ij )_n×m , the higher the feasibility, the more suitable the aircraft is to perform the task at that point. Aiming at the task assignment problem with different numbers of rescue helicopters and target points, it is proposed to convert it into a balanced assignment problem by adding dummy variables, and then use the Hungarian algorithm to solve it.

平衡指派问题的系数矩阵C_ij的任意一行（列）各元素中分别减去该行（列）的最小元素得到新矩阵

则以

为系数矩阵的问题的最优解与以原矩阵C_ij为系数矩阵的问题有相同最优解。匈牙利算法通过等效变换找到与原系数矩阵等效的新矩阵，使得该新矩阵中不同行列均有零元素，将解矩阵X_ij对应位置上的元素置为1，其余位置为0，这就得到了平衡指派问题的最优解。具体步骤为：A new matrix is obtained by subtracting the minimum element of the row (column) from each element of any row (column) of the coefficient matrix C_ij of the balanced assignment problem

then take

The optimal solution of the problem with C ij as the coefficient matrix has the same optimal solution as the problem with the original matrix C_ij as the coefficient matrix. The Hungarian algorithm finds a new matrix equivalent to the original coefficient matrix through equivalent transformation, so that there are zero elements in different rows and columns in the new matrix, and the elements in the corresponding positions of the solution matrix X_ij are set to 1, and the remaining positions are 0, which is The optimal solution of the balanced assignment problem is obtained. The specific steps are:

a）对系数矩阵进行等效变换，对矩阵中每行元素减去该行最小元素，再对每列元素减去该列最小元素，对于0元素跳过，不做处理。如：a) Perform an equivalent transformation on the coefficient matrix, subtract the minimum element of the row from each row element in the matrix, and then subtract the minimum element of the column from each column element, and skip the 0 element without processing. like:

${\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>=</span>=</span>\left(\begin{array}{ccc}\mathrm{<span><span>6</span>6</span>}& \mathrm{<span><span>8</span>8</span>}& \mathrm{<span><span>6</span>6</span>}\\ \mathrm{<span><span>7</span>7</span>}& \mathrm{<span><span>7</span>7</span>}& \mathrm{<span><span>9</span>9</span>}\\ \mathrm{<span><span>10</span>10</span>}& \mathrm{<span><span>9</span>9</span>}& \mathrm{<span><span>12</span>12</span>}\end{array}\right)<span><span>\&RightArrow;</span>\&Right\; Arrow;</span>\left(\begin{array}{ccc}\mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>2</span>2</span>}& \mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>2</span>2</span>}\\ \mathrm{<span><span>1</span>1</span>}& \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>3</span>3</span>}\end{array}\right)<span><span>\&RightArrow;</span>\&Right\; Arrow;</span>\left(\begin{array}{ccc}\mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>2</span>2</span>}& \mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>1</span>1</span>}\\ \mathrm{<span><span>1</span>1</span>}& \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>2</span>2</span>}\end{array}\right)<span><span>=</span>=</span>{{\mathrm{<span><span>C</span>C</span>}}^{<span><span>*</span>*</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>1</span>1</span>}<span><span>)</span>)</span>$

b）如果能找出n个独立的0元素，则已获得最优解。b) If n independent 0 elements can be found, the optimal solution has been obtained.

c）从只有一个0元素的行开始，将该0元素标记为表示这行所代表的航空器仅有一个目的地可被指派，然后划去

所在的行中所有其他0元素，记为Φ，表示该列表示的目的地已经被指派。c) Starting with a row with only one 0 element, mark that 0 element as Indicates that the aircraft represented by this line has only one destination to which it can be assigned, then strike out

All other 0 elements in the same row, denoted as Φ, indicate that the destination represented by this column has been assigned.

d）给只有一个0元素的列中的0元素标记为然后划掉其所在列的其余0元素，记为Φ。d) Label 0 elements in columns with only one 0 element as Then cross out the rest of the 0 elements in the column, denoted as Φ.

e）重复步骤3、4，直到所有0元素被标记和划掉。e) Repeat steps 3 and 4 until all 0 elements are marked and crossed out.

f）如仍有未标记的0元素，相同行（或列）中0元素至少有两个（表示该行所代表的航空器可以指派给两个目的地），此时可能有多个解。这时可以从剩余0元素最少的行开始，比较该行各0元素中所在列中的0元素的数目，选择0元素最少的列的0元素标记，然后划掉同行同列中其他的0元素，反复进行直到所有0元素都被标记或划掉。f) If there are still unmarked 0 elements, there are at least two 0 elements in the same row (or column) (indicating that the aircraft represented by this row can be assigned to two destinations), and there may be multiple solutions at this time. At this time, you can start from the row with the least remaining 0 elements, compare the number of 0 elements in the column of each 0 element in the row, select the 0 element mark of the column with the fewest 0 elements, and then cross out other 0 elements in the same column in the same row, Repeat until all 0 elements are marked or crossed out.

g）若

元素的数目l等于矩阵的阶数，则表示已获得指派问题的最优解。g) if

The number l of elements is equal to the order of the matrix, which means that the optimal solution to the assignment problem has been obtained.

以

为例，先标记元素

划掉

然后标记

划掉

最后标记

得到$\left(\begin{array}{ccc}\mathrm{\&Phi;}& 2& \&CircleTimes;\\ \&CircleTimes;& \mathrm{\&Phi;}& 1\\ 1& \&CircleTimes;& 2\end{array}\right),$由于l=n=3,因而得到最优解。by

For example, first mark the element

cross out

then mark

cross out

last mark

get$\left(\begin{array}{ccc}\mathrm{\&Phi;}& 2& \&CircleTimes;\\ \&CircleTimes;& \mathrm{\&Phi;}& 1\\ 1& \&CircleTimes;& 2\end{array}\right),$ Since l=n=3, the optimal solution is obtained.

直升机i{321}（2）helicopter i{321} (2)

目的点j  {213}Destination point j {213}

针对救援直升机与目标点数量不一致的情况（n<m或n>m），即系数矩阵不为方阵，可以把系数矩阵C补成方阵（如n<m时，在C中增加（m-n）行0元素），得到方阵

然后对Q应用匈牙利算法，直到得到最优解。例如：For the situation where the number of rescue helicopters and target points is inconsistent (n<m or n>m), that is, the coefficient matrix is not a square matrix, the coefficient matrix C can be supplemented into a square matrix (for example, when n<m, add (mn ) row 0 element), get the square matrix

The Hungarian algorithm is then applied to Q until an optimal solution is obtained. For example:

${\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>=</span>=</span>\left(\begin{array}{cccc}\mathrm{<span><span>1</span>1</span>}& \mathrm{<span><span>5</span>5</span>}& \mathrm{<span><span>6</span>6</span>}& \mathrm{<span><span>3</span>3</span>}\\ \mathrm{<span><span>3</span>3</span>}& \mathrm{<span><span>2</span>2</span>}& \mathrm{<span><span>3</span>3</span>}& \mathrm{<span><span>8</span>8</span>}\end{array}\right)<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>3</span>3</span>}<span><span>)</span>)</span>$

令$Q_{\mathrm{ij}}=\left(\begin{array}{cccc}1& 5& 6& 3\\ 3& 2& 3& 8\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)\&RightArrow;\left(\begin{array}{cccc}0& 4& 5& 2\\ 1& 0& 1& 6\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)\&RightArrow;\left(\begin{array}{cccc}\&CircleTimes;& 4& 5& 2\\ 1& \&CircleTimes;& 1& 6\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)---\left(4\right)$make$Q_{\mathrm{ij}}=\left(\begin{array}{cccc}1& 5& 6& 3\\ 3& 2& 3& 8\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)\&Right\; Arrow;\left(\begin{array}{cccc}0& 4& 5& 2\\ 1& 0& 1& 6\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)\&Right\; Arrow;\left(\begin{array}{cccc}\&CircleTimes;& 4& 5& 2\\ 1& \&CircleTimes;& 1& 6\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)---\left(4\right)$

此时不满足最优解条件，对子矩阵$\left(\begin{array}{cc}5& 2\\ 1& 6\end{array}\right)$继续采用匈牙利算法，得$\left(\begin{array}{cc}5& 2\\ 1& 6\end{array}\right)\&RightArrow;\left(\begin{array}{cc}3& 0\\ 0& 5\end{array}\right)\&RightArrow;\left(\begin{array}{cc}3& \&CircleTimes;\\ \&CircleTimes;& 5\end{array}\right),$则最优分配方案为：At this time, the optimal solution condition is not satisfied, and the submatrix$\left(\begin{array}{cc}5& 2\\ 1& 6\end{array}\right)$ Continuing to use the Hungarian algorithm, we get$\left(\begin{array}{cc}5& 2\\ 1& 6\end{array}\right)\&Right\; Arrow;\left(\begin{array}{cc}3& 0\\ 0& 5\end{array}\right)\&Right\; Arrow;\left(\begin{array}{cc}3& \&CircleTimes;\\ \&CircleTimes;& 5\end{array}\right),$ Then the optimal allocation scheme is:

直升机i{1212}（5）helicopter i{1212} (5)

目标点j{1243}Target point j{1243}

所述救援任务执行可行度评估包括对基地与目标点之间的距离、海拔高度、净空环境、地理环境、任务类型等影响因素的评估，针对可行度评估影响因素中的定量因子如海拔高度采用基于阈值的区间量化处理方法进行定量评估，而对定性因子如任务类型采用模糊综合评价方法转换为定量评估；再利用专家调查法得到影响因素的权重值，利用线性加权求和得到可行度值，该值越大表明该机越适合执行该项救灾任务；通过两次循环得到可行度矩阵。The evaluation of the execution feasibility of the rescue mission includes the evaluation of the distance between the base and the target point, the altitude, the clearance environment, the geographical environment, the task type and other influencing factors. Quantitative evaluation based on the interval quantitative processing method based on the threshold value, and the fuzzy comprehensive evaluation method is used to convert qualitative factors such as task types into quantitative evaluation; then the expert investigation method is used to obtain the weight value of the influencing factors, and the linear weighted sum is used to obtain the feasibility value. The larger the value, the more suitable the aircraft is to perform the disaster relief mission; the feasibility matrix is obtained through two loops.

${\mathrm{<span><span>c</span>c</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>=</span>=</span>\underset{\mathrm{<span><span>k</span>k</span>}<span><span>=</span>=</span>\mathrm{<span><span>1,2,3,4,5</span>1,2,3,4,5</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}{\mathrm{<span><span>\&omega;</span>\&omega;</span>}}_{\mathrm{<span><span>k</span>k</span>}}{\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>k</span>k</span>}}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>6</span>6</span>}<span><span>)</span>)</span>$

其中c_ij表示第i架直升机执行第j项任务的可行度值(1≤i≤n,1≤j≤m)。ω_k表示该因素的权重值，f_k表示第k项因素的可行度。由元素c_ij构成的矩阵C称为可行度矩阵，记为C=(c_ij)_n×m。Where c_ij represents the feasibility value of the i-th helicopter to perform the j-th task (1≤i≤n, 1≤j≤m). ω_k represents the weight value of the factor, and f_k represents the feasibility of the kth factor. The matrix C composed of elements c_ij is called the feasibility matrix, which is recorded as C=(c_ij )_n×m .

具体设置为：The specific settings are:

1）基地与目标点之间距离f_d，根据常见的机型性能从0km～1000km按50km等间隔划分，f_d取值为20～0。f_d=0表示该目标点超出直升机航程。1) The distance f_d between the base and the target point is divided into equal intervals of 50 km from 0 km to 1000 km according to the performance of common aircraft types, and the value of f_d is 20 to 0. f_d =0 means that the target point is beyond the range of the helicopter.

2）目标点海拔高度f_h，包括海拔高度，净空情况，地形情况。从0m～5000m按500m等间隔划分，f_h取值为10～0。f_h=0表示该目标点超出直升机升限。2) Altitude f_h of the target point, including altitude, clearance, and terrain. From 0m to 5000m, it is divided into equal intervals of 500m, and the value of f_h is 10 to 0. f_h =0 means that the target point exceeds the ceiling of the helicopter.

3）目标点净空情况f_c属于定性指标，采用三级量化指标，用0表示净空条件差，所以航空器均不能降落；1表示净空条件一般，可酌情降落；2表示净空条件好，一般均可降落。3) The clearance condition of the target point f_c is a qualitative indicator, and a three-level quantitative index is adopted. 0 indicates that the clearance condition is poor, so the aircraft cannot land; landing.

4）目标点地理环境f_t属于定性指标，采用三级量化，0表示地形险要，不宜降落；1表示地形情况一般，可酌情降落；2表示地形平坦，一般可降落。4) The geographical environment of the target point f_t is a qualitative indicator, which adopts three-level quantification. 0 means that the terrain is dangerous and it is not suitable to land; 1 means that the terrain is general and can be landed as appropriate;

5）任务类型f_m属于定性指标，分为遥感摄影，目标搜寻，物资投放，人员营救，按任务紧要程度分别赋值为1，2，3，4.5) The task type f_m is a qualitative indicator, which is divided into remote sensing photography, target search, material delivery, and personnel rescue, and is assigned a value of 1, 2, 3, and 4 according to the urgency of the task.

可行度影响因子与权重值关系表：Feasibility impact factor and weight value relationship table:

从图1还可以看出所述的灾区地图图像的处理包括如下步骤：Can also find out from Fig. 1 that the processing of described disaster area map image comprises the following steps:

（1）获得SRTM数字高程地图后，用Global Mapper输出矢量DEM文件；(1) After obtaining the SRTM digital elevation map, use Global Mapper to output the vector DEM file;

（2）用Surfer输出单层等高线图；(2) Use Surfer to output a single-layer contour map;

（3）用Matalab二值化处理得到等高线表示的障碍物图；(3) Use Matalab binarization to obtain the obstacle map represented by contour lines;

（4）用Matalab对障碍物图进行膨胀和腐蚀处理；(4) Use Matalab to expand and corrode the obstacle map;

（5）骨架化特征提取，得到以二值图像表示的救援飞行航迹解空间。(5) Skeletonized feature extraction to obtain the rescue flight track solution space represented by a binary image.

获得SRTM数字高程地图后还需要进行如下操作步骤：After obtaining the SRTM digital elevation map, the following steps are required:

（1）使用地图绘制软件Global Mapper将SRTM格式数据转换为XYZ格式，并保存为等高线地图KML文件；(1) Use the mapping software Global Mapper to convert the SRTM format data into XYZ format, and save it as a contour map KML file;

（2）加载等高线地图KML文件获得灾区数字地图；(2) Load the contour map KML file to obtain the digital map of the disaster area;

（3）利用A*算法在二维平面上即以二值图像表示的航迹解空间搜索得到最短航迹，结合多直升机与救援目标之间的分配结果，形成直升机执行救援任务的应急预案。(3) Use the A* algorithm to search the space of the track solution represented by the binary image on the two-dimensional plane to obtain the shortest track, and combine the allocation results between multiple helicopters and rescue targets to form an emergency plan for helicopters to perform rescue missions.

航迹规划地图采用90m精度的SRTM数字高程数据，数据来源于中国科学院计算机网络信息中心国际科学数据镜像网站(http://datamirror.csdb.cn)。使用地图绘制软件Global Mapper软件将SRTM格式数据转换为XYZ格式，并保存为等高线地图KML文件。The track planning map uses 90m precision SRTM digital elevation data, and the data comes from the International Scientific Data Mirror website of the Computer Network Information Center of the Chinese Academy of Sciences (http://datamirror.csdb.cn). Use the map drawing software Global Mapper software to convert the SRTM format data into XYZ format, and save it as a contour map KML file.

对以等高线表示障碍物的数字地图使用形态数的图像处理方法进行膨胀和腐蚀处理，并使用骨架化的方法提取图像的拓扑结构特征，得到二维平面内的可飞航迹解空间。The image processing method of morphological number is used to dilate and erode the digital map of obstacles represented by contour lines, and the skeletonized method is used to extract the topological structure features of the image, and the solution space of the flight path in the two-dimensional plane is obtained.

运用启发式搜索算法Ａ*算法在航迹解空间中搜索出最短路径。A*算法公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。Use the heuristic search algorithm A* algorithm to search for the shortest path in the track solution space. The A* algorithm formula is expressed as: f(n)=g(n)+h(n), where f(n) is the evaluation function of node n from the initial point to the target point, and g(n) is the value from the initial point to the target point in the state space. The actual cost from the initial node to n nodes, h(n) is the estimated cost of the best path from n to the target node.

然后根据直升机的飞行性能和救援任务的特点，根据直升机飞行高度层将三维空间航迹规划问题分解为多个二维平面航迹规划问题，在各飞行高度层上分别求取二维最优航迹。Then, according to the flight performance of the helicopter and the characteristics of the rescue mission, the three-dimensional space trajectory planning problem is decomposed into several two-dimensional plane trajectory planning problems according to the flight level of the helicopter, and the two-dimensional optimal trajectory planning problem is obtained at each flight level. trace.

参见图2所示，本发明所述方法在计算机系统主流程中的作用。航空应急救援预案的形成需要直升机救援飞行航迹规划的载入以及本发明所述的方法，包括载入灾区等高线数字地图KML文件的获取，灾情设置及救援可行性评估得到可行度矩阵，根据可行度矩阵得到直升机多目标分配方案；航空应急救援预案还包括输出航迹海拔剖面图，测量航路点间的距离和方位角，计算直升机应飞磁航向、飞行时间、剩余燃油里程，根据机型设置直升机性能参数的救援直升机沿航迹飞行，判断直升机之间是否存在冲突，如果回答是，产生冲突警告并调配直升机飞行高度、航向并反馈性调整救援飞行航迹规划；如果回答否，记录飞行过程中的经纬度坐标，调用载有等高线KML文件的Google Earth飞行模拟API演示应急救援预案，做好充分的飞行前准备。Referring to Fig. 2, the function of the method of the present invention in the main flow of the computer system. The formation of the aviation emergency rescue plan requires the loading of the helicopter rescue flight path planning and the method described in the present invention, including loading the acquisition of the KML file of the contour line digital map of the disaster area, disaster setting and rescue feasibility assessment to obtain the feasibility matrix, According to the feasibility matrix, the multi-target allocation scheme of the helicopter is obtained; the aviation emergency rescue plan also includes the output of the altitude profile of the track, the measurement of the distance and azimuth between the waypoints, and the calculation of the helicopter's flying magnetic heading, flight time, and remaining fuel mileage. Rescue helicopters with helicopter performance parameters are set to fly along the track to determine whether there is a conflict between the helicopters. If the answer is yes, a conflict warning will be generated and the helicopter’s flight altitude and heading will be adjusted in feedback to adjust the rescue flight track planning; if the answer is no, record The latitude and longitude coordinates during the flight, call the Google Earth flight simulation API containing the contour line KML file to demonstrate the emergency rescue plan, and make full preparations before the flight.

参见图3所示，将等高线数字地图用二值化图像处理方法进行处理，得到的障碍物如图中封闭等高线所围成的黑色部分；其余白色部分表示安全区域。对于人为设定的禁飞区、限制区以及人工障碍物例如铁塔、输电线路等，可以通过在地图上添加等效的等高线来实现，例如图中的L、S和P区域，该高度上的云、雾等影响飞行的气象条件也可以通过同样的方式在障碍物图中反映出来。As shown in Figure 3, the digital map of contour lines is processed by binary image processing method, and the obtained obstacles are shown in the black part surrounded by closed contour lines; the rest of the white part represents the safe area. For artificially set no-fly zones, restricted areas, and artificial obstacles such as iron towers, power transmission lines, etc., it can be realized by adding equivalent contour lines on the map, such as the L, S, and P areas in the figure. Meteorological conditions affecting flight, such as clouds and fog above, can also be reflected in the obstacle map in the same way.

参见图4所示，救援直升机在山区飞行时，与障碍物之间必须保持侧向安全间隔。因此，选用基于形态学的图像处理膨胀和腐蚀方法对白色安全区域进行压缩，以剔除间隔不满足要求的区域，并采用骨架化的特征提取方法得到二维飞行平面内的可行航路集合如图中细折线所示。Referring to Fig. 4, when the rescue helicopter flies in mountainous areas, it must maintain a lateral safety distance from obstacles. Therefore, the image processing expansion and erosion method based on morphology is used to compress the white safe area to eliminate the areas whose intervals do not meet the requirements, and the skeletonized feature extraction method is used to obtain the set of feasible routes in the two-dimensional flight plane as shown in the figure indicated by the thin line.

参见图5所示，利用启发式搜索算法A*算法在二维平面内寻找最短路径，如图中从星形表示的起点到圆圈表示终点之间的路径，该最短路径就可以作为救援直升机预计飞行轨迹。As shown in Figure 5, the heuristic search algorithm A* algorithm is used to find the shortest path in the two-dimensional plane, as shown in the figure, the path between the starting point represented by the star and the end point represented by the circle, the shortest path can be used as a rescue helicopter to predict flight path.

参见图6所示，该图为汶川地震受灾最严重的区域汶川县的数字高程地图DEM数据，在三维图像显示中标出了救援飞行的起点A和终点B。See Figure 6, which is the DEM data of the digital elevation map of Wenchuan County, the most severely affected area in the Wenchuan Earthquake. The starting point A and the ending point B of the rescue flight are marked in the three-dimensional image display.

参见图7、图8、图9分别是将三维航迹规划转换为多个高度层上的二维航迹规划，其中图7为2100米所在高度层上的二维航迹解空间，图8为3000米所在高度层上的二维航迹解空间，图9是3000米高度层上对应的最短飞行航路。Referring to Fig. 7, Fig. 8, and Fig. 9, the three-dimensional trajectory planning is converted into two-dimensional trajectory planning on multiple altitude layers, wherein Fig. 7 is the two-dimensional trajectory solution space on the altitude layer of 2100 meters, and Fig. 8 is the two-dimensional track solution space on the altitude layer of 3000 meters, and Fig. 9 is the corresponding shortest flight route on the altitude layer of 3000 meters.

从图中可以看出在飞行高度层2100米没有从起点A到终点的可用飞行轨迹解空间，而飞行高度层3000米时的可用飞行轨迹解空间中包含起点到终点的可用飞行轨迹；而图9是对飞行高度层3000米的可用航迹解空间进行骨架化特征提取后得到的救援直升机可用飞行航路。It can be seen from the figure that there is no available flight trajectory solution space from the starting point A to the terminal at the flight level of 2100 meters, while the available flight trajectory solution space at the flight level of 3000 meters contains the available flight trajectory from the starting point to the terminal; 9 is the available flight route of the rescue helicopter obtained after skeletonized feature extraction of the available flight path solution space at a flight level of 3,000 meters.

Claims (4)

1. rescue helicopters multiple goal more than a kind is distributed and path planning method, it is characterized in that, comprises the processing of the feasible degree assessment of air rescue tasks carrying and disaster area map image; Described rescue task is carried out feasible degree assessment and is referred to analyze the feasibility that certain helicopter is implemented certain rescue task, obtains feasible degree matrix; With feasible degree matrix as dematrix X_IjMatrix of coefficients, select Hungary Algorithm for the allocation result between quantity is not identical between rescue helicopters and the impact point task solving multiple helicopters and the rescue target; The processing of described disaster area map image refers to from digital elevation map to extract the individual layer contour map, and this figure is carried out binary image process and obtain the obstructions chart that represents with level line, and wherein black represents barrier, and white expression can supply flight range; Utilize the morphological dilations method to reject dangerous zone in the white flight range, and use the topological structure in corrosion and skeletonization method extraction safe flight zone, thereby obtain the trajectory planning solution space that represents with bianry image; Selecting heuristic Shortest Path Searching Algorithm A* algorithm is that the two dimensional surface search obtains the shortest flight path in the trajectory planning solution space that represents with bianry image; In conjunction with multimachine multiple goal allocation result, form the emergency preplan that helicopter is carried out rescue task; Call Google Earth flight simulation API demonstration emergency management and rescue prediction scheme, do the front preparation of sufficient flight.

2. many rescue helicopters multiple goal according to claim 1 is distributed and path planning method, it is characterized in that, described rescue task is carried out feasible degree and is assessed the assessment that comprises influence factors such as the distance between base and the impact point, sea level elevation, headroom environment, geographical environment, task types, carry out qualitative assessment for the Quantitative Factors employing in the feasible degree assessment influence factor based on the interval quantization disposal route of threshold value, and adopt fuzzy synthetic appraisement method to be converted to qualitative assessment to Qualitative factor; The recycling expert survey obtains the weighted value of influence factor, utilizes the linear weighted function summation to obtain feasible degree value, and this value shows more greatly this disaster relief task of the more suitable execution of this machine; Obtain feasible degree matrix by twice circulation.

3. many rescue helicopters multiple goal according to claim 1 is distributed and path planning method, it is characterized in that, the processing of disaster area map image comprises the steps:

(1) behind the acquisition SRTM digital elevation map, with Global Mapper output vector DEM file;

(2) with Surfer output individual layer contour map;

(3) obtain the obstructions chart that level line represents with the Matalab binary conversion treatment;

(4) with Matalab obstructions chart is carried out dilation and erosion;

(5) skeletonizing feature extraction obtains the trajectory planning space that represents with bianry image.

4. many rescue helicopters multiple goal according to claim 3 is distributed and path planning method, it is characterized in that, also needs to proceed as follows step behind the described acquisition SRTM digital elevation map:

(1) uses mapping software Global mapper that the SRTM formatted data is converted to the XYZ form, and save as contour map KML file;

(2) load contour map KML file and obtain the disaster area numerical map;

(3) utilize the A* algorithm to obtain the shortest flight path in conjunction with the allocation result between multiple helicopters and the rescue target in the two dimensional surface search, form the emergency preplan that helicopter is carried out rescue task.

Images