[發明專利]一種基于拓撲地圖和沖突消除策略的多無人車尋路方法

有效

• 申請號: 202010041160.6
• 申請日: 2020-01-15
• 公開（公告）號: CN111238519B
• 公開（公告）日: 2022-05-03
• 發明（設計）人: 蔡奕僑;張凱凱;鄒燁;傅順開;張惠臻;田暉
• 申請（專利權）人: 華僑大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 廈門市首創君合專利事務所有限公司 35204
• 代理人: 張松亭

本發明公開了一種基于拓撲地圖和沖突消除策略的多無人車尋路方法，本發明的技術方案包含三個要點：第一，引入拓撲地圖作為無人車調度環境，來減少多無人車路徑規劃的計算量；第二，通過將拓撲地圖轉化成加權有向圖來生成精準調度方案，再對精準調度方案進行RVIZ仿真，證明算法的有效性；第三，提出兩種沖突消除方法，即：中間點沖突消除法和相鄰點沖突消除法，并根據動作計劃中沖突結點的屬性，選擇沖突消除方法，來消除沖突，從而快速生成無沖突的路徑計劃。本發明通過RVIZ對聯合計劃進行仿真實驗，驗證了提出的方法在真實環境下是有效性的。

技術領域

本發明涉及一種多主體尋路方法，具體是一種基于拓撲地圖和沖突消除策略的多無人車尋路方法。

背景技術

近年來，無人駕駛的研究發展迅速，其涉及機器人、計算機科學和工程學等多個領域。多無人車路徑規劃問題是多主體尋路問題(Multi-Agent Pathfinding，MAPF)在無人駕駛領域的延伸。MAPF被定義為：存在多個主體，它們具有不同的目標點，為這些主體尋找無沖突路徑計劃的問題。MAPF問題為無人車路徑規劃提供理論基礎，解決MAPF問題的算法通過改進可以用于解決無人車路徑規劃問題。

目前最受歡迎的解決MAPF的算法是基于沖突的搜索算法(Conflict-BasedSearch，CBS)。CBS是一個面向MAPF問題的求解算法，它通過運行兩級搜索算法(高級搜索和低級搜索)，來保證算法的完整性和最優性。以前絕大數工作針對網格地圖，并假設主體的動作具有統一的持續時間，如：CBS算法等；也有少部分只針對網格地圖，不作假設，如：CCBS(CBS with Continuous Times)算法等。CCBS也可用于拓撲地圖上的MAPF問題中。在無人車路徑規劃問題中，采用網格地圖進行路徑規劃，計算量大，很難在短時間內獲得合理的解決方案；拓撲地圖以其數據量少，處理方便的優點，被用來作為無人車路徑規劃的環境。將CCBS算法用于拓撲地圖上的多無人車路徑規劃問題，不僅能夠生成高質量的解決方案，而且能夠極大地減少計算時間。但是實際使用過程中，會出現不能及時提供無沖突路徑計劃的現象。此現象不僅降低了無人車的工作效率，而且降低了用戶體驗。為消除此現象，本發明提出基于拓撲地圖和沖突消除策略的多無人車尋路算法。此算法將根據當前路況及時地提供無人車的路徑計劃，來準確高效地指導無人車的路線調度。

發明內容

本發明提出了一種基于拓撲地圖和沖突消除策略的多無人車尋路方法。此方法將根據當前路況及時地提供無人車的路徑計劃，來準確高效地指導無人車的路線調度。其原理為：開始時，將真實世界的拓撲地圖處理成加權有向圖，以便實現無人車的精準路徑規劃，再調用CCBS算法生成無人車的動作計劃；若一定時間內找不到無沖突的動作計劃，就調用沖突消除策略來消除沖突，從而加速無沖突動作計劃的查找。具體地：一開始，將真實世界的拓撲地圖處理為加權有向圖，并輸入每輛無人車的起點和終點，再調用提出的算法生成合理的解，其過程如下。根據無人車在加權有向圖中的起點與終點，調用CCBS算法生成無人車的動作計劃；然后判斷生成的動作計劃是否有沖突，若沒有沖突，就保存此動作計劃到合理的解中；若存在沖突，就檢查當前動作計劃中是否存在多個無人車同時經過的結點，若存在此類結點，調用“中間點沖突消除法”選擇此位置之前的結點作為臨時終點；若不存在此類結點，調用“相鄰點沖突消除法”選擇當前位置相鄰的未使用的結點作為臨時終點，重復這個過程，直到無人車到達輸入的終點。最后，返回合理的解。本發明提出的基于拓撲地圖和沖突消除策略的多無人車尋路算法的步驟為：

1)根據真實的地形獲取相應的拓撲地圖的數據，拓撲地圖的數據包含：node(x，y)，track(startNode，endNode，weight)，topoMap(tracks，nodes)；其中，node表示拓撲地圖中結點，track表示拓撲地圖的邊，其由開始頂點(startNode)、結束頂點(endNode)和權重(weight)組成，topoMap表示整個拓撲地圖，由邊集(tracks)和頂點集(nodes)構成；