基于改進D*算法的巡檢機器人路徑規劃

秦 旭，黃曉華，馬東明，翁亞華

(南京理工大學機械工程學院，南京 210014)

0 引言

巡檢機器人需要在工作場景中規劃出一條從初始位置到目標位置的路徑[1-2]，該路徑應滿足路程短、效率高、安全性好等一系列要求，并且必須能夠避開沿途的靜態和隨機動態障礙物[3]，路徑規劃的好壞直接決定了巡檢任務是否能夠順利完成。因此，路徑規劃對于巡檢機器人的任務完成起到舉足輕重的作用。

目前較為常用的路徑規劃算法有Dijkstra算法、A*算法。Dijkstra算法可以在實際環境中搜索一個節點到其他任意節點的最短路徑[4]，屬于貪心算法的一種；A*算法是在Dijkstra算法基礎上進行改進，融合了貪心思想和啟發思想，使用啟發信息來引導搜索方向，故又稱啟發式算法[5]，并可以添加安全約束[6]。然而，Dijkstra算法與A*算法在遇到動態障礙物時，只能進行重復規劃，效率較低；而在巡檢機器人實際工作過程中，可能會出現動態障礙，于是就產生了D*算法[7]，D*算法又稱動態A*(dynamic A*)算法，與A*算法類似，不同在于是從終點到起點進行反向搜索。

但是D*算法也存在著一些問題，D*算法以長度優先，并且向周圍8個子節點進行擴展搜索，生成的路徑會產生一些不必要的轉彎，會增加巡檢機器人的功耗和時間；長度優先的準則也導致生成的路徑某些時候會從兩個障礙物之間穿過，并未考慮到機器人本身的外形尺寸[8]。對此，許多學者對D*算法也做出了一些改進，張賀等[9]基于動態窗口法，將 A*算法與D*算法結合，最大程度確保了路徑精度。……