一种基于动态规划的飞行冲突解脱方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109979248A(43)申请公布日2019.07.05(21)申请号201910339191.7(22)申请日2019.04.25(71)申请人浙江工业大学地址310014浙江省杭州市下城区潮王路18号(72)发明人陈伟锋车国庆张贵军(74)专利代理机构杭州求是专利事务所有限公司33200代理人邱启旺(51)Int.Cl.G08G5/00(2006.01)权利要求书3页说明书8页附图2页(54)发明名称一种基于动态规划的飞行冲突解脱方法(57)摘要本发明公开了一种基于动态规划的飞行冲突解脱方法，首先，将飞行冲突解脱问题的整个过程，按不同飞机状态的改变划分成与飞机架数相同的阶段，以便按已划分阶段的次序去求每个阶段的解，使用不同的状态变量来表示每个阶段开始时全体飞机所处的飞行状态，每架飞机采取改变航向角的策略，来避免冲突的发生；然后，按照已划分的次序保持其余的飞机航向角不变，对相应阶段的飞机求出最优的航向角，然后交替地固定，以迭代地形式反复进行，完成两轮迭代；最后，引入混合整数线性规划，在上一步结果的基础上进行求解。本发明能大大降低了不必要的搜索范围，方法不复杂，提供了一种搜索速度非常迅速，且结果可靠的飞行冲突解脱方法。CN109979248ACN109979248A权利要求书1/3页1.一种基于动态规划的飞行冲突解脱方法，其特征在于：所述飞行冲突解脱方法包括以下步骤：(1)将飞行冲突解脱问题的整个过程，按不同的飞机进行编号，划分成与飞机架数相同的阶段；使用不同的状态变量来表示每个阶段开始时全体飞机所处的飞行状态；每架飞机采取改变航向角的策略，来避免冲突的发生；(2)按照已划分的阶段，采用逐步求解的方式求出各个阶段的解，完成整个阶段的求解后；再次按已划分阶段的次序进行第二轮求解，将第一轮求得的解进行优化；(3)引入一个混合整数线性规划(MILP)问题，每架飞机采取航向角和速率同时改变的策略来避免冲突；对该MILP问题进行求解，完成飞行冲突解脱。2.根据权利要求1所述的飞行冲突解脱方法，其特征在于，所述步骤1具体为：将每架飞机看为二维平面上的圆并进行编号，每个编号对应一个阶段，以便逐次按阶段求解每个阶段的解；每个阶段的状态变量包含飞机的初始位置坐标(x0,y0)、终点位置坐标(xi,yi)、飞行速率v，由初始位置和终点位置按三角函数关系求得原始航向角采用航向角的改变来实现冲突解脱，左右最大可偏转角不大于3.根据权利要求1所述的飞行冲突解脱方法，其特征在于，所述步骤2通过以下子步骤来实现：(2.1)将航向角等分为n份，由第一架飞机开始，仅当前求解的阶段的航向角可变，保持其余飞机的航向角不变，对n个等分的航向角使用阶段指标sk来衡量，并引入二元变量gk来判断每个航向角是否可行，通过两架飞机的最小距离是否大于最小安全准则来判别是否存在冲突，将阶段指标和二元变量的和的最小值作为目标值，求出一个可以解决最多冲突对数的航向角作为第一架飞机新的航向角，其中sk和gk为：分别为新的航向角和原始航向角；(2.2)按照次序为每个阶段的飞机都找到一个新的航向角；(2.3)完成整个阶段后，将求解出的航向角作为新的航向角，重复步骤(2.1)和步骤(2.2)，进行第二轮求解，将第一轮求得的解进行优化。4.根据权利要求1所述的飞行冲突解脱方法，其特征在于，所述步骤3通过以下子步骤来实现：(3.1)关于混合整数线性规划问题，每架飞机采取航向角和速率同时改变的策略来避免冲突，将飞机看作为二维平面上的圆，航向角的左右最大偏转不大于速率的改变满足圆速率的94％-103％。只需要保证两架飞机的相对速度与水平线的夹角，大于两架飞机两条公切线与水平线的夹角中较大的那个，或小于公切线与水平线夹角中较小的那个，就可以保证冲突解脱。目标函数为最小的航向角和速率的改变。引入一系列的二元变量β*来实现航向角的离散化，每一个β对应一个角度，只需要让每一架飞机对应的一系列二元变量中2CN109979248A权利要求书2/3页有且仅有一个为1，其对应的航向角就是新的航向角。并引入另外一个二元变量b和两个非负的连续变量c和k，将形如c·b的非线性化部分线性化，具体如下：M为大于c的常数；(3.2)对航向角和速率的搜索域进行定义，航向角的左右最大可偏转角应不大于步骤(2.3)优化后的航向角的改变量的绝对值，速率的改变量仍满足圆速率的94％-103％，目标函数仍为最小的航向角和速率的改变；(3.3)在定义好的搜索域内对该混合整数线性规划问题进行求解，将解出的新的速率和航向角作为最终的速率和航向角，完成飞行冲突解脱。5.根据权利要求1所述的飞行冲突解脱方法，其特征在于，所述混合整数线性规划问题MILP为：s.t.3CN