基于多標號修正法的快速最短路算法在智能飛行器航跡快速規劃問題中的應用

秦子柔

（上海交通大學船舶海洋與建筑工程學院，上海200240）

1 概述

近年來，隨著國民經濟的提高以及科學技術尤其是人工智能的飛速發展，無人機已經成為我國物資運輸，環境監控，軍事偵察，資源勘探等領域不可或缺的一部分。由于信號傳輸延時，實現無人機的自動導航日顯重要。然而由于系統結構及環境多變導致定位系統無法對自身進行精準定位，常常導致任務失敗。在2018 年5 月的西安無人機表演中，就有無人機因為環境干擾而無法對自身定位從而打亂編隊并引起墜機的先例。

由于無人機發展的重要性與需求，近幾年有大量學者從事了無人機自動導航的研究。與他們的方法相比，此文提出了無人機航跡規劃的一般模型和算法，有實時性高，計算量小的優勢。

2 問題背景及模型建立

2.1 背景描述

假設飛行器的飛行區域業已確定，如圖1 所示，出發點為A點，目的地為B 點。其航跡約束要求如2019 年全國研究生數學建模競賽F 題。

圖1 飛行器飛行環境

2.2 模型建立

2.2.1 僅考慮誤差積累上限的航跡規劃方案

在任意一個誤差校正點處，如飛行器滿足誤差校正要求，則其水平誤差或者垂直誤差立即被校正。將校正點、出發點A 和終點B 及它們之間的空間路段抽象成簡單無向完全圖，它們之間的距離用dij表示為目標函數：對一條路段ij，如被選擇作為航跡中的路段，則xij=1；否則為0。因此目標函數的第一部分表示的是規劃航跡的總長度。如飛行器在此處進行了誤差校正，則u1i=0 或u0i=0；否則u1i=1 且u01=1，因此第二部分表示規劃航跡中校正的次數。對兩部分分別賦予w1和w2的非負參數權重。在建立流量守恒約束、飛行誤差控制約束后，建得飛行器誤差校正約束。

2.2.2 帶轉彎約束的航跡規劃方案

使用軌跡示意圖來展示模型中兩點之間飛行器的運動軌跡。

圖2 點間運動幾何分析圖

轉彎角度是轉彎起始點和轉彎結束點之間的連線和原航向間所成的夾角，用β 表示。轉彎半徑指以原航向與新航向為外切線形成的圓的半徑大小，用r1 表示。假設飛行器行駛的第一段圓弧路段是以最小轉彎半徑行駛。行駛一段距離之后，飛行器將會進入另一個與此最小半徑圓相切，同時與速度方向上節點相切的圓的第二段圓弧路段，從而假設了合理的飛行軌跡。如上圖所示，紅色的兩段圓弧為所走軌跡。當飛行器從出發點A出發時，假設它走直線到達第一個校正點。

排除掉一些無法飛達的節點，飛行器飛行軌跡空間長度的模型計算公式如下。

用式(5)獲得兩點之間的兩段弧長運動軌跡總長。

2.2.3 校正點存在失效概率的多目標航跡規劃模型

對于給定的可行航跡，飛行器能夠成功到達終點的概率符合一種馬爾可夫鏈狀態空間概率分布。考慮校正點處校正最壞的狀況來找到某個路徑的成功概率的下界，來最大化到達終點的概率。所有可能失效的校正點都按失效處理。

增加一個子優化目標作為模型約束：

其含義是對于終點B，盡量使得有流量進入，即飛行器成功到達終點B。

同時需要的流量守恒約束式為：

其中I 為飛行器終止的節點。飛行器成功到達B 點，則I=B。

通過修改約束式來考慮校正點處校正失效。

整理得校正點存在失效概率的多目標航跡規劃模型：

3 實驗仿真

3.1 考慮飛行器轉彎半徑約束:

在最短航跡方案和最少檢查次數的方案中，航跡大多數情況下會輪流經過垂直/水平校正點來校正誤差。兩條航跡總體方向始終朝向終點B，最少校正次數方案的航跡會增加路程長度而減少一次校正次數，不分伯仲。

3.2 校正點存在失效概率的多目標航跡規：

最短航跡方案總航跡長度104827.3772m，經過10 個校正點；最少校正次數方案總航跡長度104864.3839m，經過9 個校正點。兩種方案航跡總長相差37m，無論從航跡總長度以及校正次數來看都較接近。

圖3 數據集1 航跡圖

圖4 數據集2 軌跡圖

數據集2 航跡規劃耗時281ms, 最優航跡既是路徑最短，且校正次數最少。與數據集1 相比，數據集2 可供選擇的校正點較少。

3.3 模型的敏感性分析

隨著轉彎半徑變化，計算得到的航跡長度、校正次數均發生變化，但整體變化不大。數據集2 的計算耗時均遠小于數據集1。從兩個數據集內部橫向比較來看，轉彎半徑變化對其求解耗時影響很小。隨著轉彎縮小，兩個數據集求解耗時并無一致性變化。

4 結論

本文提出了解決飛行器由于自身定位系統受到限制和誤差校正點可能失效情況下最優航跡規劃的方法。通過運用基于多標號修正法的快速最短路算法，建立了帶轉彎約束的雙目標航跡規劃模型，使用多標號修正法的快速最短路算法求解。算法不依賴于模型的表達式；對于存在多個目標的情況，不需要人為的給定目標間的權重，因為算法能夠提供所有的帕累托最優解。

對于點與點之間的飛行軌跡的雙圓弧假設，具有創新性和實際操作價值，對飛行器空間軌跡控制提供參考。通過敏感性分析，發現模型、算法求解速度保持穩定，因此適用于飛行器的快速航跡規劃。