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

徐小小 周啟銀 婁成龍 夏 宇

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

0 引言

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

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

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

1 貪心算法和動態規劃法

貪心算法是將一個問題分成多個子問題，自頂向下以循環遞歸的方式快速地進行貪心選擇，從而求出子問題的最優解，進而簡化數學模型的規模[6]，并把迭代求解出的局部問題最優解集合為整個問題的最終解[7]。貪心算法常運用于子問題具有最優解的問題中，其算法流程為建立能描述問題的數學模型、把問題分成多個子問題、對子問題進行求解、獲得子問題的最優解以及將集合子問題的最優解作為整個問題的解。……