[發明專利]一種在復雜地圖下改進Visual Graph的方法

有效

• 申請號: 201611144910.2
• 申請日: 2016-12-13
• 公開（公告）號: CN106708043B
• 公開（公告）日: 2019-08-06
• 發明（設計）人: 陳智鑫;林夢香
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G05D1/02
• 分類號: G05D1/02;G06Q10/04
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 楊學明;顧煒

本發明公開了一種在復雜地圖下改進Visual Graph的方法，使之不僅適用于凸多邊形障礙物的地圖，也適用于一般的復雜地形的SLAM地圖。Visual Graph是1979年提出的路徑規劃算法，模擬了光線沿直線傳播這一特性，將起點和終點與凸多邊形障礙物的角點連接，構成路徑，但也僅限于凸多邊形障礙物。本發明沿用主要思路，即光沿直線傳播，從路徑的起點和終點發射光線，經過障礙物的反射，最終以光路為載體獲得一條連接起點和終點的路徑，實現路徑規劃的功能，而不是簡單使用障礙物頂點連線作為載體，這樣也就不僅限于凸多邊形的障礙物，對一般復雜地形都適用。

技術領域

本發明涉及智能機器人運動規劃領域內的一種路徑規劃算法，具體是一種針對地形復雜的地圖下Visual Graph算法的改進，使其不僅可以應用在凸多邊形障礙物的地圖下，也可以運用在復雜的地圖下。

背景技術

當下能夠自主導航避障的機器人系統研究異?；馃?，而且也已經有許多產品應用于實踐。如餐館的服務機器人，就擁有障礙物識別，路徑規劃的能力；又如家庭掃地機器人，也擁有在開闊空間內規劃自身運動路徑的能力。在公共運輸方面，無人機快遞投遞的應用已經開展的如火如荼，在快遞投遞上也必須用到路徑規劃，以使無人機能夠在避開障礙物的前提下以最短的路徑到達目的地并完成投遞。

路徑規劃即是指機器人決策如何從地圖的某一點運動到另一點的能力。首先要求機器人能夠獲得當前環境的地圖信息，并能定位當前自身的位置，隨后才可以進行路徑規劃，定位和建圖的算法目前最實用的就是SLAM算法。目前有許多路徑規劃算法，如RRT、PRM等。

Visual Graph也是常用的路徑規劃算法，但是其應用對地圖有嚴格的限制，要求地圖的障礙物要是凸多邊形，并且各個障礙物的頂點坐標已知，隨后連接各個障礙物的頂點，并以這些連線為載體，生成路徑。但是在實際應用場景中，地形是十分復雜的，地圖中的障礙物形狀是不規則的，而且其頂點坐標也是未知的，因此要直接利用Visual Graph算法是不可行的。現行的解決該問題的方法為，首先對地圖進行預處理，使用形態學方法，如分水嶺算法、特征匹配算法等，可以提取地圖中的特征點或者障礙物的邊界，獲得障礙物的大致形狀，并以直線連接各個特征點，將障礙物轉化為一個凸多邊形，再應用Visual Graph算法。這種方法的計算量不小，涉及的額外算法多，效率很難估算，而且在其將障礙物轉化到凸多邊形時，會對障礙物的邊緣進行一定程度的膨脹或腐蝕，可能造成地圖中原本不是障礙物的區域成為障礙物，原本是障礙物的區域成為可通過，可能使得最終得到的路徑非法。

發明內容

本發明的技術解決問題：克服了原始Visual Graph對地圖的硬性要求，提出一種在復雜地圖下改進Visual Graph的方法，使其不再僅限于凸多邊形障礙物的地圖，在復雜的SLAM地圖下也可以運行，并且無需對地圖做預處理，節點的密度參數也很容易調整，以生成精確的路徑。

本發明的技術解決方案：一種在復雜地圖下改進Visual Graph的方法，其特征在于：能夠使Visual Graph不僅僅應用于凸多邊形障礙物的地圖，對一般的SLAM地圖也可以適用，其步驟如下：

步驟1：對地圖進行轉化，將灰度圖或者SLAM所構建的地圖二值化處理，得到轉化后的地圖，此過程稱為地圖二值化過程；

步驟2：針對轉化后的地圖，給定起點和終點，將起點和終點儲存在一個順序表中，并從起點和終點開始發射光線，開始建立光路圖，此過程稱為初始化過程；

步驟3：當光線碰觸障礙物時，記錄該碰撞點的坐標，并與順序表中已有的節點求取距離，若距離小于一個閾值則舍棄該點，否則保留，該過程稱為節點儲存判定過程；

步驟4：從保留的節點開始，重新發射光線，并重復步驟3的過程，此過程稱為重復光線發射過程；

步驟5：當所有光線碰撞障礙物都無法生成新的節點時，判斷建圖結束；