基于貪心算法的自動路徑規劃送藥小車

徐小小 周啟銀 婁成龍 夏 宇

（貴州師范大學物理與電子科學學院，貴州 貴陽 550025）

0 引言

隨著無人駕駛技術的不斷創新發展，小車自動規劃路徑成為當今社會的熱點。為了實現醫院無接觸配送藥品，該文進行了以無人小車為主的精細化、智慧化送藥服務[1]的研究。

黃匯華等[2]采用K210、OpenMV 和STM32 共同組成的智能送藥小車能按規定的路線完成送藥任務，但是在送藥之前需要布置小車軌道。閉世管等[3]基于MSP-423E401Y 單片機、LV8548MC 芯片、OpenMV 識別模塊和NRF24L01 通信模塊實現不同藥房的送藥、取藥功能。萬瑞豐[4]基于OpenArt和TC377 設計的送藥小車雖然降低了小車送藥的操作復雜度，但是在尋跡過程中的識別受光線的影響較大。肖光亞[5]基于Arduino 的智能送藥小車通過識別地面的安置路線自動避障，以實現往返送藥的功能。

在總結國內學者對智能送藥小車相關研究的基礎上，針對送藥小車在二維平面下如何規劃出最優路徑，以提高送藥效率，該文提出了一種基于貪心算法的改進RRT 算法。該算法可以建立醫院內部的坐標圖，并在獲取目標位置的坐標點后，根據醫院內部各個部門的坐標位置動態規劃出1 條最優的路徑。

1 貪心算法和動態規劃法

貪心算法是將一個問題分成多個子問題，自頂向下以循環遞歸的方式快速地進行貪心選擇，從而求出子問題的最優解，進而簡化數學模型的規模[6]，并把迭代求解出的局部問題最優解集合為整個問題的最終解[7]。貪心算法常運用于子問題具有最優解的問題中，其算法流程為建立能描述問題的數學模型、把問題分成多個子問題、對子問題進行求解、獲得子問題的最優解以及將集合子問題的最優解作為整個問題的解。問題的求解關鍵是貪心策略，當選擇貪心策略時須注意策略應具有無后效性，即當前狀態與前一個狀態沒有統計學意義，單獨節點的問題單獨求解，第一次選擇不需要前一個時刻子問題的解。無后效性是貪心算法區別于動態規劃法的本質特點。

動態規劃法是自底向上地求解子問題的解，這是一種與前一個狀態有關聯的求解方法，當第一次選擇時，需要求解前一個時刻子問題的解，只有求解出前一個時刻子問題的解才能求解下一個子問題。該算法具有重疊子問題的性質，在循環遞歸時會解決相同的問題，但是不會一直生成新的子問題。

2 貪心算法

2.1 貪心算法的基本步驟

貪心算法的求解過程為讀入問題、制定貪心策略、問題排序以及處理問題[8]。貪心算法從問題的初始解出發，不斷向目標點逼近，每步都是不可回溯的決策，根據貪心選擇的性質，歸并一系列的局部最優解，以得到所求問題的解。該算法的核心思想是待求解問題的最優解依賴于子問題的最優解。該思想縮小了解決問題需要考慮的范圍，將全局變成局部，有利于降低算法的復雜度。

2.2 貪心算法的適用性

貪心算法具有最優子結構的性質，即整體的解取決于局部子問題的解。該特性使貪心算法的適用范圍受到限制，即只有局部子問題最優解能決定全局最優解的情況才適用貪心算法。貪心算法的可信度可以通過數學方法證明，通過該算法能夠得到解決整個問題趨于最優的解。

2.3 貪心算法實例——Prim 算法、Kruskal 算法

Prim 算法和Kruskal 算法是貪心算法中常用的算法，2 種算法的運行機制不同，因此其執行過程也存在差異，但這2 種算法都是求連通網的最小生成樹，可以將每條邊線逐步添加到沒有任何邊線的狀態的樹中。

2.3.1 Prim 算法

文獻[9]中，該算法是從任一根節點出發，利用貪心算法把離頂點最近的頂點添加到生成樹，不斷擴大所含頂點的個數，當最后一個節點被添加到生成樹時結束。與Kruskal 算法相比，該算法不受網絡圖稠密的影響。Prim 算法隨機選取1 個頂點，在圖1 中選取A為初始根節點，計算其與無向圖中的其他節點的距離，選取最小的邊添加到生成樹，循環上述流程，將節點添加到生成樹，直到終點被添加到生成樹。Prim 算法在無向圖中的執行過程如圖1 所示。由圖1 可知，Prim 算法得到的最小生成樹是權值最小、有n個頂點且有n-1 條邊的帶權無向完全圖。該算法是對所有節點進行直接搜索的，涉及多次迭代。

圖1 Prim 算法執行圖

圖1 以A點為起點，利用Prim 算法得到的最小生成樹的每條邊上的數值為兩點之間的權重，算法通過判斷權重生成“ABDGEC”的擴展樹，其中不包括F點，比較連接F點的權重可以得到G指向F的擴展樹。

2.3.2 Kruskal 算法

Kruskal 算法可以選擇任意的起點，主要應用在互斥集合數據結構中。該算法的貪心策略是將所有節點與當前節點的權值進行比較，第一條邊是最小權值的邊線，再在其余邊線中任意選取一條邊線放在已有的邊線中，按照此方法循環取出邊線，最后得到最小生成樹。

Kruskal 算法執行圖如圖 2 所示，選擇D點作為起點，對邊線的權值進行排序，將權值最小的邊線添加到最小生成樹。橙色的粗線代表被添加到生成樹的邊線，即將圖2 中DGEC先放入生成樹，再將A、F的邊線進行排序，把B到A、D到F加入樹中。該算法當將邊線添加到最小生成樹時還須注意其是否會與生成樹中其他邊線產生回路，并將會產生回路的邊線刪除。要判斷是否產生回路，需要對生成樹進行深度優先搜索，判斷逆向邊是否存在。按照上述方式將所有的邊線添加到生成樹。

圖2 Kruskal 算法執行圖

由上述原理介紹可知，網絡圖邊線數量對Kruskal 算法的影響較大。

對比Kruskal 算法與Prim 算法建立生成樹的方法可知，Kruskal 算法是先對權重進行排序，選取最小的權重添加到生成樹；Prim 算法則是直接對其他的節點進行循環查找，搜索權值最小的節點放入最小生成樹。因此當邊線繁雜時選用Prim算法，如果考慮時間復雜度，那么Kruskal 算法的效率比Prim算法效率高。

3 二維坐標系下貪心算法結合動態規劃規劃最優路徑

3.1 RRT 算法

RRT 算法是基于隨機采樣的快速擴展樹，通過與障礙物產生碰撞檢測是否將該節點添加到擴展樹，多次循環檢測直到到達目標點，再從目標點回溯到起始點，就可以找到路徑。與Dijkstra 算法、粒子群優化算法和人工勢場法相比，該算法的搜索能力強、參數少且搜索路徑的速度快，適用于高維復雜環境下的路徑優化。在擴展生成樹的過程中，擴展的節點是隨機采樣的，因此其搜索的路徑只能找到兩點之間的路徑，并不能得到最優路徑并且冗余節點的計算量大、規劃時間響應時間太長，容易導致路徑規劃失敗。

3.2 貪心算法融合改進的RRT 算法規劃流程

為了解決傳統的RRT 算法帶來的路徑規劃非最優、搜索速度慢的問題，該文引入貪心算法中的Kruskal 算法選擇每個子問題的最優解并舍棄其他解，以減少冗余點的計算量。RRT算法路徑規劃的優化主要進行以下5 個步驟：1）隨機樹初始化。2）進行隨機采樣。3）擴展節點。4）終點停止擴展。5）處理冗余點。

3.2.1 隨機樹初始化

當該算法在讀取坐標系時，以當前位置為快速擴展樹的搜索起點，以接收到的目的地坐標點為快速擴展樹的終點。隨機樹的初始化包括根節點和帶閾值的終點。

3.2.2 進行隨機采樣

隨機樹的擴展采用隨機采樣檢測節點是否存在碰撞，從而判斷該點是否存在障礙物。利用歐氏距離計算空間中兩點的距離，二維環境下的歐氏距離、三維坐標系上的歐式距離如公式（1）、公式（2）所示。

式中：（x1，y1）為直線一側端點的坐標點；（x2，y2）為直線另一側端點的坐標點；z1、z2為2 個點在z坐標軸上的坐標。

可以將公式（2）推廣到三維坐標中，還可以將公式（1）推廣到n維坐標系上。在對計算的距離進行排序后，選擇距離最短的節點進行碰撞檢測（判斷2 個節點之間是否存在障礙物）。如果無障礙物發生碰撞，那么將該節點添加到快速擴展樹；如果該節點發生碰撞事件，算法判斷該點存在障礙物，那么重新生成隨機點，再循環檢測歐氏距離的計算和判斷。

3.2.3 擴展節點

節點的擴展須基于上一步驟檢測碰撞事件，將沒有發生碰撞事件的節點添加到隨機樹，以擴展隨機樹。

3.2.4 終點停止擴展

隨機樹初始化時需要設置一個帶閾值的終點。當擴展樹的節點與終點的歐式距離小于設置的閾值時，程序判斷該節點是終點，停止隨機樹的擴展。完成上述步驟后就可以得到1條從起點到終點的路徑。

3.2.5 處理冗余點

冗余點刪除前后對比圖如圖3 所示。由圖3 可以得到冗余點處理表，見表 1。

圖3 冗余點刪除前后對比

圖4 二維環境路徑優化對比圖

貪心算法結合改進的RRT 算法在二維環境下的路徑優化對比圖如圖 4 所示。

4 結語

針對傳統送藥小車按軌道尋徑存在靈活性差、工作效率低和適用范圍容易被限制等問題，該文提出將Kruskal 算法與RRT 算法結合，建立醫院內部的坐標圖，自動規劃最優路徑，以完成送藥任務。該算法使送藥小車能夠靈活選擇醫院的各個位置，不再局限于只在軌道上運動，且該算法不用識別地面上的軌道，外界的亮度就無法對其產生影響。利用貪心算法提取最優解，可以減少路徑冗余點的計算量，結合改進的RRT 算法能夠快速找到最優路徑，提高送藥小車的工作效率。但是該文研究算法的試驗背景是在道路上沒有行人的場所，如果要將該算法投入使用，還需要實現送藥小車的實時避障功能。將最優路徑算法結合實時避障算法，最終使送藥小車能夠靈活避開行人，快速完成送藥任務。

表1 冗余點處理表