移動機器人養(yǎng)老服務路徑規(guī)劃的粒子群算法研究

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

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

0　引言

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

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

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

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

1　養(yǎng)老機器人移動機器人路徑規(guī)劃優(yōu)化問題

1.1　機器人工作空間的網(wǎng)格圖模型

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

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

基于以下假設描述網(wǎng)格圖模型：

a）機器人工作環(huán)境被定義為包括分類網(wǎng)格塊的二維網(wǎng)格圖;

b）在機器人工作環(huán)境中，分布著許多靜態(tài)障礙物。障礙物的高度被忽略。每個障礙物可以在網(wǎng)格圖中占據(jù)一個或多個網(wǎng)格塊。

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

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

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

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

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

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

1.2　路徑規(guī)劃優(yōu)化模型

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

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

移動機器人在網(wǎng)格圖中移動的路徑規(guī)劃優(yōu)化模型如下：

優(yōu)化函數(shù) fpath是包含網(wǎng)格圖中機器人每走一步的路徑的總距離。如下所示：

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

Hik是由機器人步進網(wǎng)格塊i碰撞的障礙塊k的懲罰系數(shù)。參數(shù)n是網(wǎng)格塊的總數(shù)，m是障礙塊的總數(shù)?？紤]到求解問題的一致性，將多目標優(yōu)化模型合并為單目標優(yōu)化問題。如下所示：

粒子群優(yōu)化算法有效解決了單一優(yōu)化問題，參數(shù)α和β是經(jīng)驗系數(shù)，滿足α+β= 1。

1.3　人工勢場法

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

引力勢場函數(shù)定義如下：

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

排斥勢場函數(shù)定義如下：

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

2　解決路徑規(guī)劃問題的粒子群優(yōu)化算法

2.1　粒子群優(yōu)化算法

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

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

2.2　編碼和解碼方法

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

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

3　實驗和性能分析

3.1　實驗設計

實驗平臺是專為硬件和軟件環(huán)境而設計的。 硬件是老年服務移動機器人的原型，它可以沿著室內(nèi)和老年社區(qū)的優(yōu)化路徑隨著三個輪子移動。 該軟件是具有路徑規(guī)劃管理和決策系統(tǒng)的控制模塊。

該實驗僅針對粒子優(yōu)化算法求解的網(wǎng)格圖模式而設計。模型的細節(jié)設置如下。

表1　模型設置Tab.1　Model setting

該算法在 windows操作系統(tǒng)或 linux操作系統(tǒng)上實現(xiàn)。 上述系統(tǒng)的實驗描述如下：CPU為Core i5 3.3 GHz，內(nèi)存大小為8 G，仿真環(huán)境為Visual C++。

3.2　實驗結(jié)果

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

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

所有移動步驟都組成移動機器人路徑?？紤]避免碰撞的最佳路徑是一種折中結(jié)果，其不僅包括最短路徑優(yōu)化，而且還避免了危險障礙。老年人社區(qū)中的機器人是一種重要的輔助手段，可以幫助老年人緩慢行走，避開危險物體。因此，盡管是最短的優(yōu)化路徑，但與障礙塊側(cè)面接觸一樣，不滿足最佳路徑?jīng)Q策。

當目標位置發(fā)生變化時，粒子群優(yōu)化算法也被有效地應用于求解所提出的網(wǎng)格圖模型。例如，當目標位置被改變?yōu)樗饕?9的網(wǎng)格塊時，該算法被實施以根據(jù)所存儲的全局路徑規(guī)劃來選擇最佳 路徑。

3.3　實驗性能分析

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

從網(wǎng)格圖模型優(yōu)化中的路徑規(guī)劃實驗結(jié)果來看，粒子群算法克服了其他有效的人工智能算法。

該算法也可以在算法運行過程中執(zhí)行相同的迭代次數(shù)。這三種算法在相同的標準實驗環(huán)境下進行1000次迭代運行。

表2　算法的優(yōu)化結(jié)果Tab.2　Optimized results of algorithm

4　結(jié)論

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