移動機器人養老服務路徑規劃的粒子群算法研究

陳曦斌，焦明海，劉昊汧，程亦然，張　浩

（1. 東北大學機械工程與自動化學院，遼寧 沈陽　110819；2. 東北大學計算機科學與工程學院，遼寧 沈陽　110819；3. 東北大學信息與工程學院，遼寧 沈陽　110819）

0　引言

隨著經濟社會的發展，中國人口老齡化規模越來越大，養老是中國未來社會發展的嚴重社會問題，也是一個重要的經濟和政治問題。中國已經進入社會稟賦的深度，“老前富”和稟賦困境的現實顯露出來。在當前的環境中，養老社區中的導向機器人的重要性是不言而喻的[1]。隨著近年來人工智能技術的應用，中國政府作為工業和信息化部，發展和改革委員會，財政部聯合發布了“機器人產業發展規劃（2016-2020年）”[2]。根據該計劃文件，機器人應用將在5年內投入服務行業。但事實上，中國老人導向機器人的研發并不理想。

機器人路徑規劃是根據給定的需求指令從起點到目標點選擇一條路徑，避開環境障礙物條件，并將位置從開始位置逐步移動到目標位置，以使機器人可以穿越所有障礙物安全和沒有碰撞。這是移動機器人研究領域的熱點問題[3]。移動機器人路徑規劃研究方便老年人社區護理服務。

移動機器人的路徑規劃可以根據機器人為路徑感知而采取的工作空間環境信息劃分為全局路徑規劃和局部路徑規劃。對于機器人移動路徑規劃優化，主要的傳統路徑規劃算法是人工勢場[4]，視覺反饋[5]和模塊化可重構[6]方法。這些算法可以在不同程度上得到改進以獲得良好的結果，但是這些算法具有其自身的限制。為了獲得機器人規劃的最優路徑，人工智能算法[7,8]被應用于移動機器人的路徑規劃優化。研究成為人工智能解決移動機器人路徑規劃問題的熱點問題。

對于人工智能算法的研究，群體智能算法是近年來機器人移動路徑規劃優化的熱點。但移動機器人運動精度和全局路徑規劃的瓶頸問題也有待解決。自主無人機的發展是自動路徑規劃的能力。遺傳算法（GA）和粒子群優化算法（PSO）相結合，以解決問題的復雜性和計算可行和準最佳軌跡[9]。文獻[10]提出了在已知的靜態粗糙地形環境下運行的類似汽車的移動機器人的路徑規劃算法，該算法找到了具有最小長度和地形粗糙度的無碰撞和可行路徑。提出了基于二進制編碼的靜態和動態環境下移動機器人導航（MRN）二進制編碼遺傳算法的新變體，以軌跡理論為最優控制器，建立了SLI（Sylvester Law of Inertia）矩陣模型。另外還提出了另一種三層結構分層全局路徑規劃方法，用于移動機器人在雜亂環境中的應用。討論了基于動態分布粒子群優化算法的最優路徑規劃算法，并考慮了使用兩個局部最優檢測器的無碰撞最優路徑。并將人工蜂群算法作為局部搜索過程和進化規劃算法相結合，對一組局部過程找到的可行路徑進行優化。

1　養老機器人移動機器人路徑規劃優化問題

1.1　機器人工作空間的網格圖模型

移動機器人可以幫助老年人在老年社區中完成引導、提醒、陪伴、安慰等生活事物工作。但移動機器人從起點移動到目標點時必須首先避開障礙物，機器人的工作空間可視化為網格圖模型，如圖1所示。

圖1　移動機器人工作空間的網格圖模型Fig.1　Grid graph model of working space of mobile robot

基于以下假設描述網格圖模型：

a）機器人工作環境被定義為包括分類網格塊的二維網格圖;

b）在機器人工作環境中，分布著許多靜態障礙物。障礙物的高度被忽略。每個障礙物可以在網格圖中占據一個或多個網格塊。

c）機器人被表示為沒有質量或尺寸的粒子，稱為粒子機器人。

d）粒子機器人每次移動一個網格步，當機器人從開始點移動到目標點時，網格移動步驟不能重復。

e）粒子機器人必須避開工作空間的障礙物。

圖1顯示移動機器人根據一百個網格塊之一從起點移動到目標點。二維網格圖空間被標記為從左側塊到右側塊的排序號碼，從底部到上一塊，從1到100排序?；疑W格塊是粒子機器人避免移動的障礙。

定義1移動機器人工作空間被描述為一個二維地圖，它被劃分為行網格塊和列網格塊。網格塊的數量描述如下。

參數R是機器人移動每個步長的大小。Nx和Ny分別是工作空間圖的長度和寬度。Xmax和Ymax分別是最大長度和最大寬度。R，Xmax，Ymax的參數設置為1,10,10。因此，10*10尺寸的機器人工作空間圖被劃分為100個網格塊尺寸。排序后的數字在圖1中標出。

1.2　路徑規劃優化模型

機器人路徑規劃優化的目標不僅是尋找機器人從網格圖中的起點到目標點的最短路徑，而且還避免與障礙物塊的碰撞。移動機器人路徑規劃的研究被認為是一個約束優化問題。并建立了優化目標函數和約束條件的路徑規劃優化模型。優化目標為最小路徑代價，約束條件有效避免路徑規劃中的障礙。

為了解決優化問題，約束條件被轉化為優化目標函數，其被定義為最小沖突懲罰函數。然后給出該模型作為兩個優化目標函數，其中包括最小路徑成本和最小碰撞懲罰。對老年服務而言，老年社區的障礙問題對老年人來說是一段非常危險的時期，這些障礙包括水泥墻，帶刺植物軀干，臺階等等。因此碰撞處罰也被定義為碰撞系數，表示移動機器人應遠離障礙物的危險等級。

移動機器人在網格圖中移動的路徑規劃優化模型如下：

優化函數 fpath是包含網格圖中機器人每走一步的路徑的總距離。如下所示：

Di是機器人第 i步的路徑距離，其被描述為每個網格長度，并且n是網格塊的總數。優化函數fpunish定義如下：

Hik是由機器人步進網格塊i碰撞的障礙塊k的懲罰系數。參數n是網格塊的總數，m是障礙塊的總數。考慮到求解問題的一致性，將多目標優化模型合并為單目標優化問題。如下所示：

粒子群優化算法有效解決了單一優化問題，參數α和β是經驗系數，滿足α+β= 1。

1.3　人工勢場法

采用人工勢場法進行路徑探測，避開障礙物，根據目標點包含引力場和排斥場。在虛擬勢場中，機器人移動點與目標點之間的距離越大，勢能越大。距離目標點越近，勢能越小，到達目標點時勢能為零。機器人移動點與障礙物之間的距離越近，排斥力越大。

引力勢場函數定義如下：

Ugra是引力勢場函數。k是重力場常數參數，其值大于零。X是當前機器人位置點向量。而Xg是目標位置矢量。

排斥勢場函數定義如下：

Urep是排斥勢場函數。λ是一個排斥場常數參數，其值大于零。參數ρ是機器人位置與障礙物之間的距離。ρ0是障礙物的最大影響范圍。機器人在吸引和排斥方面互動，向前移動到目標點。

2　解決路徑規劃問題的粒子群優化算法

2.1　粒子群優化算法

粒子群優化算法是人工智能搜索思想的有效解決方法。粒子在目標搜索空間尋找最優解。粒子群優化算法表述為：假設搜索空間為d維，種群中有Np個粒，那么群體中的粒子 i在第 t代的位置表示為一個d維矢量。粒子的速度定義為位置的改變，用矢量 V表示。粒子i的速度和位置更新公式為：

式中，t為粒子更新迭代次數。在第t代，粒子i在 d維空間中所經歷過的“最好”位置記作；粒子群中“最好”的粒子位置為慣性系數；cl和 c2為加速系數；r1和r2為區間[0, l]服從均勻分布的兩個獨立隨機數。參數w、cl、c2的取值依賴于問題。

2.2　編碼和解碼方法

a）粒子編碼：網格圖大小是解空間，如圖1中的10*10大小。從左到右，然后從下到上，排序后的數在每個網格塊中標記為索引。因此每個粒子都有一個選定的m維解。考慮障礙塊是無意義的解決方案，真正的解決方案大小是m = Dtotal-Dobstacle，Dtotal是總的網格塊大小，Dobstacle是障礙網格塊大小。粒子編碼的問題是如何為移動移動步驟選擇網格塊。作為粒子編碼方法的新思想是給每個有效網格塊的概率為xij（j = 1,2,…,m）變量。根據網格圖大小將概率范圍設置為靈活變量值，并且不一定是0和1的區間。

b）粒子解碼：對于編碼方法來說是相反的，其重點在于根據給定的更新概率選擇最優網格塊作為移動機器人移動步驟。粒子解碼的重要主題是網格塊選擇。從網格圖中，如圖1所示，每個網格塊具有不同的相鄰網格塊，因此可選的相鄰網格塊在網格圖中定義。例如，圖1中左下方的網格塊是移動機器人移動步驟的起點，標記為數字“1”。然后，起點的相鄰網格塊應該是三個可選的網格塊，標記為數字‘2’，‘11’，‘12’。經過優化迭代過程后，起始位置的鄰居網格塊具有各自的概率值，最大鄰居塊被選為移動機器人的移動步驟。對于粒子解碼解決方案，屏障網格塊將被忽略。并且自由網格塊具有最大八個相鄰網格塊，諸如具有標記為數字“4”，“5”，“6”，“14”，“16”，“24”的相鄰網格塊的空閑塊編號“15”，“25”，“26”。對于網格圖的移動路徑，該塊不被重復選擇。

3　實驗和性能分析

3.1　實驗設計

實驗平臺是專為硬件和軟件環境而設計的。 硬件是老年服務移動機器人的原型，它可以沿著室內和老年社區的優化路徑隨著三個輪子移動。 該軟件是具有路徑規劃管理和決策系統的控制模塊。

該實驗僅針對粒子優化算法求解的網格圖模式而設計。模型的細節設置如下。

表1　模型設置Tab.1　Model setting

該算法在 windows操作系統或 linux操作系統上實現。 上述系統的實驗描述如下：CPU為Core i5 3.3 GHz，內存大小為8 G，仿真環境為Visual C++。

3.2　實驗結果

考慮避免碰撞的最佳移動機器人移動路徑如圖2所示。

圖2　最佳移動機器人移動路徑Fig.2　The best mobile moving path of mobile robot

所有移動步驟都組成移動機器人路徑。考慮避免碰撞的最佳路徑是一種折中結果，其不僅包括最短路徑優化，而且還避免了危險障礙。老年人社區中的機器人是一種重要的輔助手段，可以幫助老年人緩慢行走，避開危險物體。因此，盡管是最短的優化路徑，但與障礙塊側面接觸一樣，不滿足最佳路徑決策。

當目標位置發生變化時，粒子群優化算法也被有效地應用于求解所提出的網格圖模型。例如，當目標位置被改變為索引號69的網格塊時，該算法被實施以根據所存儲的全局路徑規劃來選擇最佳 路徑。

3.3　實驗性能分析

實驗針對移動機器人運動路徑問題求解，提出粒子群優化算法（PSO），蟻群算法（AC）和遺傳算法（GA）的性能對比。運行時間不同優化算法的實驗結果如表2所示。

從網格圖模型優化中的路徑規劃實驗結果來看，粒子群算法克服了其他有效的人工智能算法。

該算法也可以在算法運行過程中執行相同的迭代次數。這三種算法在相同的標準實驗環境下進行1000次迭代運行。

表2　算法的優化結果Tab.2　Optimized results of algorithm

4　結論

老年群體中移動導向機器人的路徑規劃問題是一個多重障礙和約束的復雜優化問題。為了更好地滿足老年人的導游路徑要求，如何選擇最短路徑和無碰撞成為提出路徑規劃問題的最重要的解決方案。提出了移動機器人運動路徑規劃模型，用于輔助老年人走出房間，走出房間引導。還提出了粒子群優化算法來解決路徑規劃問題。該模型被定義為10*10大小的網格圖，包括兩個障礙物。并提出了人工勢場法來加速路徑優化過程。該實驗旨在驗證所提出的求解算法的性能。結果表明，粒子群優化算法對老年社區老年服務移動機器人移動路徑規劃問題是有效和高效的。