[發明專利]一種基于萬有引力搜索的無人機航路規劃方法

無效

• 申請號: 201110349670.0
• 申請日: 2011-11-07
• 公開（公告）號: CN102506863A
• 公開（公告）日: 2012-06-20
• 發明（設計）人: 段海濱;李沛;羅琪楠
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G01C21/24
• 分類號: G01C21/24
• 代理公司: 北京慧泉知識產權代理有限公司 11232
• 代理人: 王順榮;唐愛華

(一)技術領域

本發明提出了一種基于萬有引力搜索的無人機航路規劃方法，屬于機器人技術領域。

(二)背景技術

無人機(Unmanned?Aerial?Vehicle)是一種有動力、可控制、能攜帶多種任務設備、執行多種作戰任務并能重復使用的無人戰術飛行器。由于其零傷亡風險和高機動性等優勢引起了各國軍方的高度重視。而航路規劃(Path?Planning)作為無人機任務規劃系統的關鍵組成部分，其目標是在適當的時間內計算、選擇最優或次優的飛行航路，對合理分配無人機的作戰資源，實現無人機的最大作戰效能起著至關重要的作用。目前，國內外在航路規劃技術方面的研究正進一步向智能化、實時性、可實現性方向發展，但基本上還處于初始研究階段。萬有引力搜索算法(Gravitational?Search?Algorithm，GSA)是一種源于對物理學中的萬有引力進行模擬的新的優化搜索技術，是一種元啟發式算法。它通過群體中各粒子之間的萬有引力相互作用產生的群體智能指導優化搜索。

本發明針對無人機航路規劃的特點，基于萬有引力搜索算法解決了無人機航路規劃問題。與傳統的航路規劃方法相比，該發明所提出的方法具有較好的實時性和快速性，所搜索到的航路更逼近實際的無人機最優航路。該方法是解決復雜動態環境下無人機航路規劃的有效技術途徑，同時，本發明也可應用于復雜環境下的機器人路徑規劃、城市交通車輛路徑規劃等技術領域。

目前，常用的無人機航路規劃算法有可行性方向算法、A*算法、遺傳算法等。

可行性方向算法是由梯度法演化而來的，與一般梯度搜索尋優法一樣，通過不斷改變控制量，直到性能指標最優。其獨到之處在于，它先找到控制變量的最佳允許方向，然后再沿該方向改變控制量。因此，該方法在調節控制變量使性能指標變小的同時，還能滿足約束條件。可行性方向算法的局限性在于收斂速度慢，而且可能得到一個局部最優解而非全局最優解。基于梯度法的所有方法收斂速度都具有較大的不確定性，其收斂速度受地形輪廓影響較大。

遺傳算法提供了一種求解復雜化問題的通用框架，而且它對問題的具體細節要求不高，對問題的類有很強的魯棒性。然而將遺傳算法用在航路規劃中可能相對而言比較費時，一般不適合用來進行實時規劃，但是目前的計算體系是串行的，而遺傳算法具有隱含的并行性，這使其有很大的發展潛力。該算法的缺點是：遺傳因子以及控制參數難于選擇，算法有時還可能出現過早收斂和停滯現象。

A*算法通過啟發信息引導搜索，達到減小搜索范圍、提高計算速度的目的。啟發信息一般取從搜索空間中某個中間節點到目標節點的最優代價的估計值。利用該啟發信息引導搜索將可以產生最優解。因此啟發信息的選取至關重要，若太簡單，則展開的中間節點數會增多：若太復雜，則計算估計值花費的時間也增多，因此應折衷考慮。目前較好的啟發函數要靠試湊的方法獲得，使得算法應用受到很大的限制。A*算法最大的缺點是搜索空間需求太大，計算時間長。

因此，目前這些方法均沒能有效地從實際意義上解決無人機的航路規劃問題。

萬有引力搜索算法是一種新興的啟發式仿生智能優化算法，目前人們對萬有引力搜索算法的研究雖然剛剛起步，但是已經取得了很多突破性進展，從而使這種新興的仿生優化算法展現出勃勃生機和廣闊的發展前景。不同于其它仿生智能算法，萬有引力搜索過程中所體現出的并行性、協同性、自組織性、動態性、強魯棒性等特點與復雜戰場環境的許多要求是相符的，因此萬有引力搜索算法可用于解決無人機的自適應航路規劃問題。但是基本萬有引力搜索算法存在著搜索時間長、容易陷于局部最優解等缺點，因此在應用萬有引力搜索算法解決無人機航路規劃問題時必須對其進行改進。基于此，本發明提出了一種改進的萬有引力搜索算法模型，并將其成功應用于解決復雜動態環境下的無人機航路規劃問題。

(三)發明內容

1、發明目的：

本發明的目的是提供了一種基于萬有引力搜索的無人機航路規劃方法，它是一種在適當的時間內為無人機計算出最優的或者是次優的飛行航路的方法。此方法也可移植于其它可以簡化為D維函數優化的問題。

2、技術方案：

該方法利用改進后的萬有引力搜索方法對無人機在戰場威脅環境下的航路進行優化，從而使無人機能突破敵方威脅環境，并且在完成任務目標的同時自我生存。該方法充分利用了粒子群優化(Particle?swarm?optimization，PSO)的記憶和群體信息共享的特征，以及萬有引力搜索智能優化收斂速度快，優化效果好的特點。