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

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

（1. 東北大學(xué)機(jī)械工程與自動(dòng)化學(xué)院，遼寧 沈陽(yáng)　110819；2. 東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧 沈陽(yáng)　110819；3. 東北大學(xué)信息與工程學(xué)院，遼寧 沈陽(yáng)　110819）

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

d）粒子機(jī)器人每次移動(dòng)一個(gè)網(wǎng)格步，當(dāng)機(jī)器人從開(kāi)始點(diǎn)移動(dòng)到目標(biāo)點(diǎn)時(shí)，網(wǎng)格移動(dòng)步驟不能重復(fù)。

e）粒子機(jī)器人必須避開(kāi)工作空間的障礙物。

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

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

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

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

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

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

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

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

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

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

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

1.3　人工勢(shì)場(chǎng)法

采用人工勢(shì)場(chǎng)法進(jìn)行路徑探測(cè)，避開(kāi)障礙物，根據(jù)目標(biāo)點(diǎn)包含引力場(chǎng)和排斥場(chǎng)。在虛擬勢(shì)場(chǎng)中，機(jī)器人移動(dòng)點(diǎn)與目標(biāo)點(diǎn)之間的距離越大，勢(shì)能越大。距離目標(biāo)點(diǎn)越近，勢(shì)能越小，到達(dá)目標(biāo)點(diǎn)時(shí)勢(shì)能為零。機(jī)器人移動(dòng)點(diǎn)與障礙物之間的距離越近，排斥力越大。

引力勢(shì)場(chǎng)函數(shù)定義如下：

Ugra是引力勢(shì)場(chǎng)函數(shù)。k是重力場(chǎng)常數(shù)參數(shù)，其值大于零。X是當(dāng)前機(jī)器人位置點(diǎn)向量。而Xg是目標(biāo)位置矢量。

排斥勢(shì)場(chǎng)函數(shù)定義如下：

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

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

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

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

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

2.2　編碼和解碼方法

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

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

3　實(shí)驗(yàn)和性能分析

3.1　實(shí)驗(yàn)設(shè)計(jì)

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

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

表1　模型設(shè)置Tab.1　Model setting

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

3.2　實(shí)驗(yàn)結(jié)果

考慮避免碰撞的最佳移動(dòng)機(jī)器人移動(dòng)路徑如圖2所示。

圖2　最佳移動(dòng)機(jī)器人移動(dòng)路徑Fig.2　The best mobile moving path of mobile robot

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

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

3.3　實(shí)驗(yàn)性能分析

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

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

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

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

4　結(jié)論

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