[發明專利]一種無人機基站選址與巡邏路徑優化方法及裝置

有效

• 申請號: 201710497121.5
• 申請日: 2017-06-26
• 公開（公告）號: CN107239078B
• 公開（公告）日: 2020-03-27
• 發明（設計）人: 劉忠;劉瑤;石建邁;陳超;羅志浩;張家銘;王玥;周天任
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G05D1/10
• 分類號: G05D1/10;H04B7/185;H04W16/18
• 代理公司: 北京卓嵐智財知識產權代理事務所(特殊普通合伙) 11624
• 代理人: 任漱晨

1.一種無人機基站選址與巡邏路徑優化方法，其特征在于，所述方法包括：

根據無人機偵察的目標點和基站的歐式距離對目標點進行分配，而后按照臨近點搜索規劃無人機路徑，以無人機續航時間約束限定無人機巡邏路徑，并限定每個基站配置無人機數量的上下限，得到無人機基站選址與巡邏路徑的初始方案；

對所述初始方案進行鄰域調整，獲得無人機基站選址與巡邏路徑鄰域調整后的新方案；

計算所述無人機基站選址與巡邏路徑的新方案的總費用；

若判定所述新方案總費用比原方案總費用減少，則保存新方案，并在新方案基礎上進行下一步迭代，否則舍棄；

所述根據無人機偵察的目標點和基站的歐式距離對目標點進行分配，而后按照臨近點搜索規劃無人機路徑，限定了每個基站配屬無人機數量的上下限，得到無人機基站選址與巡邏路徑的初始方案，包括：

Step1：已知偵查目標點和基站候選點位置后，根據歐式距離，偵查目標點分配給距其最近的基站候選點；

Step2：按照基站點分配到的目標點數量，對基站進行排序；

Step3：從分配到的目標點數量最多的候選基站開始，判斷該基站派出的無人機是否超過基站內的無人機上限數，若沒有，執行Step4，否則轉Step5；

Step4：從距基站最近的目標點開始巡邏，采用就近原則，每次尋找下一個距離當前目標點最近的待巡邏的點，并判斷無人機能否訪問完下一個目標點后再返回原基站；若可以，則該架無人機繼續偵查下一個目標點，若無法完成，則直接返回基站，轉Step3；

Step5：當基站派出無人機的數量達到基站能夠配屬的上限后，判斷基站是否還存在未偵查的目標點；若沒有，則將該基站設為已開始，并移出候選基站，轉Step3，對下一個候選基站進行路徑分配；若有，則把未完成的偵查點進行第二次分配，分配給剩余候選基站中距離最近的，而后轉Step3，繼續之后候選基站的路徑規劃，直至完成所有基站的路徑規劃；

Step6：檢測基站無人機配置數量，如果無人機配置數量最少的達到基站配置數量的下限，則結束，給出初始方案；如果沒有達到，則進行如下操作：

Step6.1：如果該基站只有一個相鄰基站，并且相鄰基站無人機配置數量少于上限，則關閉該基站，將其目標分配給相鄰的基站，應用Step4的臨近搜索算法重新構建無人機巡邏路徑，若應用基站配置上限數量的無人機能夠完成所有目標的巡邏，則轉Step6，若不能完成所有目標的巡邏，則轉Step6.3；

Step6.2：如果該基站有兩個相鄰的基站，則關閉該基站，將其目標先分配給無人機數量較少的相鄰基站，應用Step4的臨近搜索算法重新構建無人機巡邏路徑，若應用基站配置上限數量的無人機能夠完成所有目標的偵察，則轉Step6，否則將該相鄰基站的無人機配置到上限數量，并將剩余不能訪問的目標分配給第二個相鄰基站，應用Step4的臨近搜索算法重新計算第二個相鄰基站的無人機巡邏路徑，若第二個相鄰基站應用配置上限數量的無人機能夠完成所有目標的巡邏，則轉Step6，否則轉Step6.3；

Step6.3：為無人機數量少于下限的基站增加1架無人機，該無人機按照最近原則順序訪問相鄰基站中無人機數量較多的一個基站分配的目標點，構建該無人機的最大訪問回路，依次為該基站增加無人機，直到達到無人機下限數量要求，然后對該相鄰基站剩余的目標點應用Step4的臨近搜索算法重新構建無人機巡邏路徑，轉Step6；

Step7：若Step6循環次數超過候選基站總數，則停止算法，給出基站選址和無人機巡邏路徑的初始方案。

2.如權利要求1所述無人機基站選址與巡邏路徑優化方法，其特征在于，對所述初始方案進行鄰域調整時調用如下元操作：

關閉基站操作：關閉基站并重新分配相應目標點，使控制基站的無人機完全利用，以降低巡邏費用。

3.如權利要求1所述無人機基站選址與巡邏路徑優化方法，其特征在于，對所述初始方案進行鄰域調整時調用如下元操作：

交換目標點操作：在單架無人機的巡邏路徑內隨機交換兩個目標點的順序，主要對無人機路徑內部的飛行路線交叉或重疊現象進行改進優化。