2019年全国研究生数学建模竞赛华为杯

F题 多约束条件下智能飞行器航迹快速规划

原题再现：

  复杂环境下航迹快速规划是智能飞行器控制的一个重要课题。由于系统结构限制，这类飞行器的定位系统无法对自身进行精准定位，一旦定位误差积累到一定程度可能导致任务失败。因此，在飞行过程中对定位误差进行校正是智能飞行器航迹规划中一项重要任务。本题目研究智能飞行器在系统定位精度限制下的航迹快速规划问题。
  假设飞行器的飞行区域如图1所示，出发点为A点，目的地为B点。其航迹约束如下：
  飞行器在空间飞行过程中需要实时定位，其定位误差包括垂直误差和水平误差。飞行器每飞行1m，垂直误差和水平误差将各增加δ个专用单位,，以下简称单位。到达终点时垂直误差和水平误差均应小于θ个单位，并且为简化问题，假设当垂直误差和水平误差均小于θ个单位时，飞行器仍能够按照规划路径飞行。
  飞行器在飞行过程中需要对定位误差进行校正。飞行区域中存在一些安全位置（称之为校正点）可用于误差校正，当飞行器到达校正点即能够根据该位置的误差校正类型进行误差校正。校正垂直和水平误差的位置可根据地形在航迹规划前确定（如图1为某条航迹的示意图, 黄色的点为水平误差校正点，蓝色的点为垂直误差校正点，出发点为A点，目的地为B点，黑色曲线代表一条航迹）。可校正的飞行区域分布位置依赖于地形，无统一规律。若垂直误差、水平误差都能得到及时校正，则飞行器可以按照预定航线飞行，通过若干个校正点进行误差校正后最终到达目的地。

  在出发地A点，飞行器的垂直和水平误差均为0。
  飞行器在垂直误差校正点进行垂直误差校正后，其垂直误差将变为0，水平误差保持不变。飞行器在水平误差校正点进行水平误差校正后，其水平误差将变为0，垂直误差保持不变。 当飞行器的垂直误差不大于α_1个单位，水平误差不大于α_2个单位时才能进行垂直误差校正。当飞行器的垂直误差不大于β_1个单位，水平误差不大于β_2个单位时才能进行水平误差校正。飞行器在转弯时受到结构和控制系统的限制，无法完成即时转弯(飞行器前进方向无法突然改变)，假设飞行器的最小转弯半径为200m。
  请你们团队为上述智能飞行器建立从A点飞到B点的航迹规划一般模型和算法并完成以下问题：
  问题1. 针对附件1和附件2中的数据分别规划满足条件（1）~（7）时飞行器的航迹，并且综合考虑以下优化目标：（A）航迹长度尽可能小；（B）经过校正区域进行校正的次数尽可能少。并讨论算法的有效性和复杂度。其中附件1数据的参数为：α_1=25，α_2=15，β_1=20，β_2=25，θ=30，δ=0.001附件2中数据的参数为：α_1=20，α_2=10，β_1=15，β_2=20，θ=20，δ=0.001请绘出两个数据集的航迹规划路径，并将结果（即飞行器从起点出发经过的误差校正点编号及校正前误差）依次填入航迹规划结果表，放于正文中，同时将两个数据集的结果填入附件3的Sheet1和Sheet2中。
  问题2. 针对附件1和附件2中的数据（参数与第一问相同）分别规划满足条件（1）~（8）时飞行器的航迹，并且综合考虑以下优化目标：（A）航迹长度尽可能小；（B）经过校正区域进行校正的次数尽可能少。并讨论算法的有效性和复杂度。请绘出两个数据集的航迹规划路径（直线用黑色，圆弧用红色），并将结果（即飞行器从起点出发经过的误差校正点编号及校正前误差）依次填入航迹规划结果表，放于正文中，同时将两个数据集的结果填入附件3的Sheet3和Sheet4中。
  问题3.飞行器的飞行环境可能随时间动态变化，虽然校正点在飞行前已经确定，但飞行器在部分校正点进行误差校正时存在无法达到理想校正的情况（即将某个误差精确校正为0），例如天气等不可控因素导致飞行器到达校正点也无法进行理想的误差校正。现假设飞行器在部分校正点（附件1和附件2中F列标记为“1”的数据）能够成功将某个误差校正为0的概率是80%，如果校正失败，则校正后的剩余误差为min(error，5)个单位（其中error为校正前误差，min为取小函数），并且假设飞行器到达该校正点时即可知道在该点处是否能够校正成功，但不论校正成功与否，均不能改变规划路径。请针对此情况重新规划问题1所要求的航迹，并要求成功到达终点的概率尽可能大。
  请绘出两个数据集的航迹规划路径，并将结果（即飞行器从起点出发经过的误差校正点编号及校正前误差）依次填入航迹规划结果表，放于正文中，同时将两个数据集的结果填入附件3的Sheet5和Sheet6中。
  再次提醒：问题1，问题2和问题3中的结果表格除了需要放在正文中，还需要汇总到附件3的Excel表格文件的6个不同Sheet中，表x的结果放入Sheet x中，最后将汇总的Excel表格命名为：参赛队号-结果表.xlsx，以附件形式提交。

整体求解过程概述(摘要)

  复杂环境下航迹快速规划是智能飞行器控制的一个重要课题。本文分析智能飞行器系统自身结构局限性以及飞行环境导致飞行任务失败等多种原因，建立了多目标规划模型，利用禁忌搜索算法和遗传算法求解出最优的智能飞行器航行轨迹方案。
  针对问题一，在确保智能飞行器能够成功到达目的地的条件下，本文考虑了多种约束条件，建立了多约束条件下航迹长度最小化和误差校正点数最小化的双目标优化模型。模型求解时，首先引入规范函数进行无量纲化处理并通过线性加权法将该模型转化为单目标优化模型，以降低模型复杂度；然后通过约束条件将符合条件的误差校正点根据航迹长度最短原则，使用贪心算法初始化解，再使用禁忌搜索算法，优化初始解，在120次迭代后得到较优解，运行时间为70.64s，改善情况为6.55%。对数据集1求解出的最佳航行轨迹方案为：A→503→69→237→115→338→457→555→436→B，经过误差校正点数 8 个，航迹长度为104898m，比AB直线距离增加了4.41%；对数据集2求解出的最佳航行轨迹方案为：A→163→114→8→309→305→123→45→160→92→93 →61→292→B，经过误差校正点数12个，航迹长度为109342m，比AB直线距离增加了6.11%。该算法时间复杂度为O(n^2)。本文通过深度优先搜索策略进行遍历，验证两组数据最优解的校正点数为8和12，该算法针对两组数据最优解的点数均为最优；同时，两组数据航迹长度比仅比AB直线距离增加4.41%和6.11%，验证了算法的有效性。
  针对问题二，在确保智能飞行器能够成功到达目的地的条件下，需要考虑飞行器转向轨迹。为此本文参考Dubins曲线，分析了飞行器在三维空间中从A点到B点的转向过程，设计了飞行器转向约束，根据优先级尽可能短的航迹长度>尽可能少的误差校正点，在此基础上改进问题一的双目标优化模型，建立了带多约束条件的航迹长度最小化和误差校正点数最小化的双目标优化模型。模型求解时，先引入规范函数进行无量纲化处理并通过线性加权法将该模型转化为单目标优化模型，再使用贪心算法求解初始化解，然后引入了集中和分散机制，提出并使用改进禁忌搜索算法优化初始解，一定程度上解决了禁忌搜索算法在求解优化问题时存在着的停滞现象，进一步提高了禁忌搜索算法的搜索质量和收敛速度，在120次迭代后得到较优解，运行时间为74.41s，改善情况为6.79%。对数据集1求解出的最佳航行轨迹方案为：A→503→69→237→233→598→561→448→485→B，经过误差校正点数8个，航迹长度为104960m，比AB直线距离增加了4.47%，比问题一最优方案距离增加了0.02%；对数据集 2求解出的最佳航行轨迹方案为：A→163→114→8→309→305→123→45→160→92→93→61→292→B，经过误差校正点数 12 个，航迹长度为109411m，比 AB 直线距离增加了 6.18%，比问题一最优方案距离增加了0.06%。该算法时间复杂度低于O(n^2)。本文通过深度优先搜索策略进行遍历，验证两组数据最优解的校正点数为8和12，该算法针对两组数据最优解的点数均为最优；同时，两组数据航迹长度比仅比AB直线距离增加4.47%和6.18%，仅比第一问最优方案增加了0.02%和0.06%，验证了算法的有效性。
  针对问题三，由于无法确保智能飞行器能够成功抵达目的地，因此需尽量降低失败概率，同时使航迹长度尽可能小，经过的校正点个数尽可能少。为此本文考虑了飞行器成功到达目的地的多种约束条件，建立了带多约束条件的失败概率最小化、航迹长度最小化和误差校正点数最小化的多目标优化模型。通过模型求解时，先引入规范函数进行无量纲化处理并通过线性加权法将该模型转化为单目标模型，再使用贪心算法求解初始化解，然后将禁忌搜索算法与遗传算法结合，提出并使用遗传禁忌混合搜索算法优化初始解，在 120次迭代后得到较优解，运行时间为87.86s，改善情况为6.13%。对数据集1求解出的最佳航行轨迹方案为：A→578→417→80→237→607→33→194→450→448→485→302→612→B，经过误差校正点数12个，航迹长度为108439m，比AB直线距离增加了7.93%，成功抵达终点概率100%；对数据集2求解出的最佳航行轨迹方案为：A→169→322→100→137→194→190→296→250→243→73→82→44→211→321→279→301→38→287→99→326→B，经过误差校正点数12个，航迹长度为108439m，比AB直线距离增加了7.93%，成功抵达终点概率100%；对数据集2求解出的最佳航行轨迹方案为：A→169→322→100→137→194→190→296→250→243→73→82→44→211→321→279→301→38→287→99→326→B，经过误差校正点数19个，航迹长度为147271m，比AB直线距离增加了42.91%，成功抵达终点概率65.01%。该算法时间复杂度T(n)=O(n^4/λ)（λ为种群数量）。本文通过深度优先搜索策略进行遍历，验证两组数据最优解的校正点数为12和19，该算法针对两组数据最优解的点数均为最优；同时，两组数据航迹长度比比AB直线距离增加7.93%和42.91%，验证了算法的有效性。

模型假设：

  假设飞行器均按规划好的航线自主飞行，无须人工控制；
  假设飞行器不会出现故障，迫降和损坏等问题；
  假设忽略飞行器起飞和降落过程对飞行路程的影响；
  假设飞行器为质点，忽略飞行器大小。

问题分析(部分)：

  飞行器航线规划问题在很早就被提出并研究，该航线规划相关的文献也较多。大部分都是在缩短总航线的基础上，考虑了飞行质量和飞行安全等一些限制条件；在航线规划的基础上，进一步将飞行器的路线进行平滑和优化。为解决该问题，一般用到的算法有 A*算法、Dijkstra 算法、粒子群算法、遗传算法等[2~5]。这些算法各有优劣，有些传统算法得到的结果精确，但随着模型复杂度和问题规模的增加，算法计算所需时间也更大；一些智能算法计算速度较快，适应性高，但容易陷入局部最优解。针对上述背景下的多约束条件航线规划问题，本文从目标函数的角度入手，分析了各种情况下定位误差实时变化状态并建立了带约束的多目标优化模型；同时，根据问题的限制条件具体分析，考虑了多种约束条件，采用了禁忌搜索算法和遗传算法，针对实际应用对算法进行改进。
  问题一分析
  前提：根据题目所给参数有以下两种场景：针对附件 1，满足垂直校正条件下的最大垂直定位误差α_1=25，最大水平定位误差α_2=25，满足水平校正条件下的最大垂直定位误差β_1=25，最大水平定位误差β_2=25；到达目的地B点时，垂直定位误差和水平定位误差都小于θ=30；单位飞行距离下，垂直定位误差和水平定位误差所增加的单位定位误差ξ=0.001。针对附件 2，满足垂直校正条件下的最大垂直定位误差α_1=20，最大水平定位误差α_2=10；满足水平校正条件下的最大垂直定位误差β_1=15，最大水平定位误差β_2=20；到达目的地B点时，垂直定位误差和水平定位误差都小于θ=20；单位飞行距离下，垂直定位误差和水平定位误差所增加的单位定位误差ξ=0.001。
  条件：根据上述问题背景，按照（1）~（7）限制条件的要求对附件1和附件2所提供的数据分别进行航线规划。
  目标：基于上述前提和条件，在保证最短航线距离的基础上，减少定位误差校正次数，进而建立多目标航迹规划函数。并在该模型下，按照所采用的算法，完成其有效性和复杂度的讨论。
  问题二分析
  前提：与问题一采用同样的参数设置，即同样也考虑以下两种场景：针对附件 1，满足垂直校正条件下的最大垂直定位误差α_1=25，最大水平定位误差α_2=25，满足水平校正条件下的最大垂直定位误差β_1=20，最大水平定位误差β_2=25；到达目的地B点时，垂直定位误差和水平定位误差都小于θ=30；单位飞行距离下，垂直定位误差和水平定位误差所增加的单位定位误差ξ=0.001。针对附件 2，满足垂直校正条件下的最大垂直定位误差α_1=20，最大水平定位误差α_2=10；满足水平校正条件下的最大垂直定位误差β_1=15，最大水平定位误差β_2=20；到达目的地B点时，垂直定位误差和水平定位误差都小于θ=20；单位飞行距离下，垂直定位误差和水平定位误差所增加的单位定位误差ξ=0.001。
  条件：根据问题背景，按照（1）~（8）限制条件的要求对附件1和附件2所提供的数据分别进行航线规划。与问题一不同的是，问题二是在额外考虑限制条件（8）的前提下进行模型的建立。限制条件（8）涉及了三维飞行空间中的转弯问题，由于飞行器转弯的最小半径的限制，所建模型需要在讨论航线方位偏转角的基础上，考虑飞行航线的规划，并包括各种不同情况的转弯情形。与此同时还要满足（1）至（7）限制条件下实时定位误差校正约束。
  目标：基于上述前提和条件，在保证最短航线距离的基础上，减少定位误差校正次数，进而建立多目标航迹规划函数。并在该模型下，按照所采用的算法，完成其有效性和复杂度的讨论。
  问题三分析
  前提：与问题一采用同样的参数设置，即同样也考虑以下两种场景：针对附件 1，满足垂直校正条件下的最大垂直定位误差α_1=25，最大水平定位误差α_2=25，满足水平校正条件下的最大垂直定位误差β_1=20，最大水平定位误差β_2=25；到达目的地B点时，垂直定位误差和水平定位误差都小于θ=30；单位飞行距离下，垂直定位误差和水平定位误差所增加的单位定位误差ξ=0.001。针对附件 2，满足垂直校正条件下的最大垂直定位误差α_1=20，最大水平定位误差α_2=10；满足水平校正条件下的最大垂直定位误差β_1=15，最大水平定位误差β_2=20；到达目的地B点时，垂直定位误差和水平定位误差都小于θ=20；单位飞行距离下，垂直定位误差和水平定位误差所增加的单位定位误差ξ=0.001。与问题一不同的是，航迹规划需要考虑飞行器飞行期间环境因素的变化对定位误差校正点校正概率的影响，在模型的建立中，额外增加校正概率的权重。其中失败校正的概率为20%，若校正失败，则经过该校正点的剩余定位误差为min(error,5)，也就是说经过该校正点后，定位误差取原误差（校正前）和5的较小值。
  条件：根据问题背景，与问题一想相同，按照（1）~（7）限制条件的要求对附件 1和附件2所提供的数据分别进行航线规划。
  目标：基于上述前提和条件，在保证最短航线距离的基础上，减少定位误差校正次数，并且使得所规划的航迹到达目的地的校正成功概率最大化，由此建立多目标航迹规划函数。

论文缩略图(全部)：

全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可

程序代码(部分代码)：

import openpyxl 
import sys 
import random 
random.seed(1) 
sys.setrecursionlimit(100000) 
alpha1=25 
alpha2=15 
beta1=20 
beta2=25 
theta=30 
sigma=0.001 
import os 
data_path = os.path.join('..', '..', '2019 年中国研究生数学建模竞赛 F 题\附件 1：数据集 1-终
稿.xlsx') 
# 打开excel 文件,获取工作簿对象 
wb = openpyxl.load_workbook(data_path) 
# 获取指定的表单 
sheet = wb['data1'] 
point_list = [] 
for row in sheet[3:sheet.max_row]: 
point_list.append([row[1].value, row[2].value, row[3].value, row[4].value, row[5].value]) 
point_num = len(point_list) 
def get_distance(start_index, end_index): 
x1, y1, z1 = point_list[start_index][0:3] 
x2, y2, z2 = point_list[end_index][0:3] 
return ((x1-x2)**2+(y1-y2)**2+(z1-z2)**2)**0.5 
def judge_z(start_index, end_index=point_num-1): 
x1, y1, z1 = point_list[start_index][0:3] 
x2, y2, z2 = point_list[end_index][0:3] 
if abs(z1-z2)>5000: 
return False 
else: 
return True 
def judge(start_index, end_index, horizontal_error,vertical_error): 
end_point_type = point_list[end_index][3] 
distance = get_distance(start_index, end_index) 
 delta_error = distance * sigma 
    end_point_horizontal_error = horizontal_error + delta_error 
    end_point_vertical_error = vertical_error + delta_error 
    if judge_z(start_index): 
        if end_index != point_num - 1:#下一个点不是终点 
            if end_point_type == 0: # 水平 
                if end_point_horizontal_error<=beta2 and end_point_vertical_error<=beta1: 
                    is_pass = True 
                else: 
                    is_pass = False 
            elif end_point_type == 1:#垂直 
                if end_point_horizontal_error<=alpha2 and 
end_point_vertical_error<=alpha1: 
                    is_pass = True 
                else: 
                    is_pass = False 
            else: 
                is_pass = False 
        else:#下一个点是终点 
            if end_point_horizontal_error <= theta and end_point_vertical_error <= theta: 
                is_pass = True 
            else: 
                is_pass = False 
    else: 
        is_pass=False 
    after_end_point_horizontal_error = end_point_horizontal_error 
    after_end_point_vertical_error = end_point_vertical_error 
    if is_pass: 
        if end_point_type == 0: 
            after_end_point_horizontal_error = 0 
            after_end_point_vertical_error = end_point_vertical_error 
        elif end_point_type ==1: 
            after_end_point_horizontal_error = end_point_horizontal_error 
            after_end_point_vertical_error = 0 
    return is_pass, end_point_horizontal_error, end_point_vertical_error, 
after_end_point_horizontal_error, after_end_point_vertical_error 
def rank_distance(point_index_list): 
    ranked_list = sorted(point_index_list, key=lambda index_list: get_distance(index_list[0], 
point_num-1)) 
    return ranked_list 
 
def get_all_distance(index_list): 
    distance = 0 
    for i in range(len(index_list)-1): 
start_index = index_list[i] 
end_index = index_list[i+1] 
distance = distance + get_distance(start_index, end_index) 
return distance 
vis = point_num*[0] 
order = [] 
temp_all_distance = 1000000 
temp_order = [] 
def find_path(start_index=0, horizontal_error=0, vertical_error=0): 
global temp_all_distance 
global order, temp_order 
order.append(start_index) 
candidate_list = [] 
for index in range(point_num): 
if index != start_index: 
is_pass, 
end_point_horizontal_error, 
after_end_point_horizontal_error, after_end_point_vertical_error = judge(start_index, index, 
horizontal_error, vertical_error) 
if 
end_point_vertical_error, 
is_pass and get_distance(start_index, point_num-1) > get_distance(index, 
point_num-1): 
candidate_list.append(index) 
if len(candidate_list) == 0: 
order.pop() 
return 
candidate_list.sort(key=lambda index_list: get_distance(index_list, point_num-1)) 
# random.shuffle(candidate_list) 
if len(candidate_list) >= 5: 
candidate_list = candidate_list[0:5] 
for candidate in candidate_list: 
if candidate == point_num - 1: 
order.append(candidate) 
all_distance = get_all_distance(order) 
if all_distance < temp_all_distance: 
temp_all_distance = all_distance 
temp_order = order.copy() 
print('\n' + 'small', order, all_distance) 
order.pop() 
break 
if len(order) > 13: 
break 
is_pass, 
end_point_horizontal_error, 
end_point_vertical_error, 
after_end_point_horizontal_error, after_end_point_vertical_error = judge( 
start_index, candidate, horizontal_error, vertical_error) 
find_path(candidate, after_end_point_horizontal_error, after_end_point_vertical_error)
order.pop() 
return 
find_path() 
print(temp_order) 

全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可