基于多標(biāo)號(hào)修正法的快速最短路算法在智能飛行器航跡快速規(guī)劃問(wèn)題中的應(yīng)用

秦子柔

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

1 概述

近年來(lái)，隨著國(guó)民經(jīng)濟(jì)的提高以及科學(xué)技術(shù)尤其是人工智能的飛速發(fā)展，無(wú)人機(jī)已經(jīng)成為我國(guó)物資運(yùn)輸，環(huán)境監(jiān)控，軍事偵察，資源勘探等領(lǐng)域不可或缺的一部分。由于信號(hào)傳輸延時(shí)，實(shí)現(xiàn)無(wú)人機(jī)的自動(dòng)導(dǎo)航日顯重要。然而由于系統(tǒng)結(jié)構(gòu)及環(huán)境多變導(dǎo)致定位系統(tǒng)無(wú)法對(duì)自身進(jìn)行精準(zhǔn)定位，常常導(dǎo)致任務(wù)失敗。在2018 年5 月的西安無(wú)人機(jī)表演中，就有無(wú)人機(jī)因?yàn)榄h(huán)境干擾而無(wú)法對(duì)自身定位從而打亂編隊(duì)并引起墜機(jī)的先例。

由于無(wú)人機(jī)發(fā)展的重要性與需求，近幾年有大量學(xué)者從事了無(wú)人機(jī)自動(dòng)導(dǎo)航的研究。與他們的方法相比，此文提出了無(wú)人機(jī)航跡規(guī)劃的一般模型和算法，有實(shí)時(shí)性高，計(jì)算量小的優(yōu)勢(shì)。

2 問(wèn)題背景及模型建立

2.1 背景描述

假設(shè)飛行器的飛行區(qū)域業(yè)已確定，如圖1 所示，出發(fā)點(diǎn)為A點(diǎn)，目的地為B 點(diǎn)。其航跡約束要求如2019 年全國(guó)研究生數(shù)學(xué)建模競(jìng)賽F 題。

圖1 飛行器飛行環(huán)境

2.2 模型建立

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

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

2.2.2 帶轉(zhuǎn)彎約束的航跡規(guī)劃方案

使用軌跡示意圖來(lái)展示模型中兩點(diǎn)之間飛行器的運(yùn)動(dòng)軌跡。

圖2 點(diǎn)間運(yùn)動(dòng)幾何分析圖

轉(zhuǎn)彎角度是轉(zhuǎn)彎起始點(diǎn)和轉(zhuǎn)彎結(jié)束點(diǎn)之間的連線和原航向間所成的夾角，用β 表示。轉(zhuǎn)彎半徑指以原航向與新航向?yàn)橥馇芯€形成的圓的半徑大小，用r1 表示。假設(shè)飛行器行駛的第一段圓弧路段是以最小轉(zhuǎn)彎半徑行駛。行駛一段距離之后，飛行器將會(huì)進(jìn)入另一個(gè)與此最小半徑圓相切，同時(shí)與速度方向上節(jié)點(diǎn)相切的圓的第二段圓弧路段，從而假設(shè)了合理的飛行軌跡。如上圖所示，紅色的兩段圓弧為所走軌跡。當(dāng)飛行器從出發(fā)點(diǎn)A出發(fā)時(shí)，假設(shè)它走直線到達(dá)第一個(gè)校正點(diǎn)。

排除掉一些無(wú)法飛達(dá)的節(jié)點(diǎn)，飛行器飛行軌跡空間長(zhǎng)度的模型計(jì)算公式如下。

用式(5)獲得兩點(diǎn)之間的兩段弧長(zhǎng)運(yùn)動(dòng)軌跡總長(zhǎng)。

2.2.3 校正點(diǎn)存在失效概率的多目標(biāo)航跡規(guī)劃模型

對(duì)于給定的可行航跡，飛行器能夠成功到達(dá)終點(diǎn)的概率符合一種馬爾可夫鏈狀態(tài)空間概率分布?？紤]校正點(diǎn)處校正最壞的狀況來(lái)找到某個(gè)路徑的成功概率的下界，來(lái)最大化到達(dá)終點(diǎn)的概率。所有可能失效的校正點(diǎn)都按失效處理。

增加一個(gè)子優(yōu)化目標(biāo)作為模型約束：

其含義是對(duì)于終點(diǎn)B，盡量使得有流量進(jìn)入，即飛行器成功到達(dá)終點(diǎn)B。

同時(shí)需要的流量守恒約束式為：

其中I 為飛行器終止的節(jié)點(diǎn)。飛行器成功到達(dá)B 點(diǎn)，則I=B。

通過(guò)修改約束式來(lái)考慮校正點(diǎn)處校正失效。

整理得校正點(diǎn)存在失效概率的多目標(biāo)航跡規(guī)劃模型：

3 實(shí)驗(yàn)仿真

3.1 考慮飛行器轉(zhuǎn)彎半徑約束:

在最短航跡方案和最少檢查次數(shù)的方案中，航跡大多數(shù)情況下會(huì)輪流經(jīng)過(guò)垂直/水平校正點(diǎn)來(lái)校正誤差。兩條航跡總體方向始終朝向終點(diǎn)B，最少校正次數(shù)方案的航跡會(huì)增加路程長(zhǎng)度而減少一次校正次數(shù)，不分伯仲。

3.2 校正點(diǎn)存在失效概率的多目標(biāo)航跡規(guī)：

最短航跡方案總航跡長(zhǎng)度104827.3772m，經(jīng)過(guò)10 個(gè)校正點(diǎn)；最少校正次數(shù)方案總航跡長(zhǎng)度104864.3839m，經(jīng)過(guò)9 個(gè)校正點(diǎn)。兩種方案航跡總長(zhǎng)相差37m，無(wú)論從航跡總長(zhǎng)度以及校正次數(shù)來(lái)看都較接近。

圖3 數(shù)據(jù)集1 航跡圖

圖4 數(shù)據(jù)集2 軌跡圖

數(shù)據(jù)集2 航跡規(guī)劃耗時(shí)281ms, 最優(yōu)航跡既是路徑最短，且校正次數(shù)最少。與數(shù)據(jù)集1 相比，數(shù)據(jù)集2 可供選擇的校正點(diǎn)較少。

3.3 模型的敏感性分析

隨著轉(zhuǎn)彎半徑變化，計(jì)算得到的航跡長(zhǎng)度、校正次數(shù)均發(fā)生變化，但整體變化不大。數(shù)據(jù)集2 的計(jì)算耗時(shí)均遠(yuǎn)小于數(shù)據(jù)集1。從兩個(gè)數(shù)據(jù)集內(nèi)部橫向比較來(lái)看，轉(zhuǎn)彎半徑變化對(duì)其求解耗時(shí)影響很小。隨著轉(zhuǎn)彎縮小，兩個(gè)數(shù)據(jù)集求解耗時(shí)并無(wú)一致性變化。

4 結(jié)論

本文提出了解決飛行器由于自身定位系統(tǒng)受到限制和誤差校正點(diǎn)可能失效情況下最優(yōu)航跡規(guī)劃的方法。通過(guò)運(yùn)用基于多標(biāo)號(hào)修正法的快速最短路算法，建立了帶轉(zhuǎn)彎約束的雙目標(biāo)航跡規(guī)劃模型，使用多標(biāo)號(hào)修正法的快速最短路算法求解。算法不依賴于模型的表達(dá)式；對(duì)于存在多個(gè)目標(biāo)的情況，不需要人為的給定目標(biāo)間的權(quán)重，因?yàn)樗惴軌蛱峁┧械呐晾弁凶顑?yōu)解。

對(duì)于點(diǎn)與點(diǎn)之間的飛行軌跡的雙圓弧假設(shè)，具有創(chuàng)新性和實(shí)際操作價(jià)值，對(duì)飛行器空間軌跡控制提供參考。通過(guò)敏感性分析，發(fā)現(xiàn)模型、算法求解速度保持穩(wěn)定，因此適用于飛行器的快速航跡規(guī)劃。