劉曉羽 徐斌

摘要：針對移動(dòng)機(jī)器人礦井巷道環(huán)境，柵格法離散物理環(huán)境后，提出利用細(xì)胞自動(dòng)機(jī)算法建模，進(jìn)行路徑規(guī)劃的方法。算法將機(jī)器人工作空間定義為一組離散的細(xì)胞狀態(tài)，通過控制演化的規(guī)則和記錄演化進(jìn)程中的路徑信息，搜索巷道上任意兩節(jié)點(diǎn)之間的最優(yōu)路徑。仿真實(shí)驗(yàn)說明該方法的有效性。

關(guān)鍵詞：移動(dòng)機(jī)器人；細(xì)胞建模；路徑規(guī)劃

一、引言

隨著煤礦井下礦難事故頻有發(fā)生，安全可靠的井下搜救與環(huán)境監(jiān)測移動(dòng)機(jī)器人是非常必要的。由于井下巷道地形復(fù)雜，災(zāi)后環(huán)境不確定性增加，要求搜救機(jī)器人有較強(qiáng)的自主路徑規(guī)劃能力。傳統(tǒng)上，常用拓?fù)浣Y(jié)構(gòu)將空間分區(qū)的拓?fù)涞貓D表述環(huán)境[1]， 幾何方法表述環(huán)境地圖，多種方法混合使用[3]，取得良好效果。由于井下工作背景復(fù)雜程度提高，環(huán)境信息冗雜，使得建模過程和數(shù)據(jù)處理變得復(fù)雜，容易丟失環(huán)境細(xì)節(jié)，影響機(jī)器人路徑規(guī)劃的實(shí)時(shí)性和準(zhǔn)確性。

本文提出了一種基于細(xì)胞自動(dòng)機(jī)的方法，通過柵格環(huán)境場景，將離散化的每個(gè)單元看作細(xì)胞賦以狀態(tài)值，即把移動(dòng)機(jī)器人物理工作環(huán)境離散為抽象的細(xì)胞狀態(tài)空間。運(yùn)行自動(dòng)機(jī)演化規(guī)則，遍歷運(yùn)行全局區(qū)域，通過遞歸搜索得到機(jī)器人在巷道中的最優(yōu)路徑。仿真實(shí)驗(yàn)結(jié)果，驗(yàn)證了算法的有效性。

二、巷道工作空間建模

移動(dòng)機(jī)器人的工作環(huán)境，是具體連續(xù)的場景，機(jī)器人在規(guī)劃路徑時(shí)，需要將物理環(huán)境處理成抽象的模型，以提取環(huán)境信息，確定障礙物的特征和位置關(guān)系，以及自身的定位。本文使用柵格法建模工作空間，使連續(xù)復(fù)雜的環(huán)境抽象為柵格元素，建立數(shù)字地圖。地圖中，離散化的移動(dòng)機(jī)器人運(yùn)動(dòng)軌跡，為控制機(jī)器人行走與轉(zhuǎn)向提供明確信息。由于柵格地圖是一種對真實(shí)場景的近似，柵格大小決定了信息提取的誤差多少，因此，柵格建模時(shí)，應(yīng)考慮機(jī)器人自身體積大小。

以柵格所表征的信息不同，整個(gè)工作區(qū)域可分為兩類，即自由運(yùn)動(dòng)區(qū)域和障礙物區(qū)域。若柵格為障礙物所占據(jù)，則標(biāo)記固定數(shù)值；若為移動(dòng)機(jī)器人可遍歷空間，則定為自由運(yùn)動(dòng)區(qū)域。場景信息抽象為數(shù)字地圖，便可轉(zhuǎn)化為細(xì)胞狀態(tài)空間，賦予細(xì)胞狀態(tài)值，利用自動(dòng)機(jī)演化規(guī)則，優(yōu)化自由運(yùn)動(dòng)區(qū)域的移動(dòng)軌跡，搜索出最優(yōu)或次優(yōu)的移動(dòng)機(jī)器人路徑。

三、基于細(xì)胞自動(dòng)機(jī)的路徑規(guī)劃方法

（一）、細(xì)胞自動(dòng)機(jī)算法描述

細(xì)胞自動(dòng)機(jī)是在一個(gè)由有限狀態(tài)的細(xì)胞組成的離散細(xì)胞空間上，依照規(guī)定的局部演化規(guī)則，在離散的時(shí)間上進(jìn)行演化的動(dòng)力學(xué)系統(tǒng)。柵格中每個(gè)單元都可以看做一個(gè)細(xì)胞，于時(shí)間和空間上離散。設(shè)定模型為一個(gè)五元組：

其中，為離散時(shí)間，為模型中的最基本單元，即細(xì)胞；模型中全體細(xì)胞空間稱為；是中心細(xì)胞周圍鄰域內(nèi)的細(xì)胞，根據(jù)實(shí)現(xiàn)目標(biāo)不同，可選擇不同鄰域；為模型的演化規(guī)則，決定中心細(xì)胞與鄰居細(xì)胞之間的演變過程。

柵格化的移動(dòng)機(jī)器人空間中，每個(gè)柵格均看作細(xì)胞，即第行，第列的細(xì)胞，細(xì)胞在每一時(shí)刻有唯一狀態(tài)值。所有可能的細(xì)胞狀態(tài)，必須為有限個(gè)。當(dāng)某一演化規(guī)則作用時(shí)，工作區(qū)域內(nèi)所有細(xì)胞均按演變規(guī)則，更新自身狀態(tài)。而細(xì)胞空間初始狀態(tài)，由機(jī)器人獲知的環(huán)境信息決定。通過傳感器更新自動(dòng)機(jī)的輸入，不斷迭代所有細(xì)胞狀態(tài)，演化環(huán)境變化。

由描述對象決定，本文細(xì)胞初始狀態(tài)有四種不同狀態(tài)，即細(xì)胞在某一時(shí)刻，。當(dāng)細(xì)胞為機(jī)器人自由運(yùn)動(dòng)區(qū)域，狀態(tài)值為0；當(dāng)細(xì)胞所在區(qū)域有物體存在，機(jī)器人不能經(jīng)過，狀態(tài)值為1；當(dāng)初始時(shí)，細(xì)胞區(qū)域有機(jī)器人占據(jù)，狀態(tài)值為3；當(dāng)細(xì)胞區(qū)域?yàn)橐苿?dòng)機(jī)器人目標(biāo)位置，狀態(tài)值為2.

當(dāng)前細(xì)胞組中，中心細(xì)胞與鄰居細(xì)胞之間的狀態(tài)關(guān)系，決定了移動(dòng)機(jī)器人的行走方向。原則上機(jī)器人可以向任意方向移動(dòng)，實(shí)際模型中機(jī)器人受自身配置傳感器的限制，鄰居模型通常采用八個(gè)方向的摩爾鄰居，和四個(gè)方向的馮諾依曼（）鄰居。限于計(jì)算復(fù)雜度的考量，本文采用馮諾依曼模型。

移動(dòng)機(jī)器人路徑規(guī)劃可采用動(dòng)態(tài)規(guī)劃方法，即由目標(biāo)終點(diǎn)開始，逆序遞歸，回溯到起始位置的演化思路。細(xì)胞自動(dòng)機(jī)的演化規(guī)則，依據(jù)實(shí)現(xiàn)目標(biāo)不同，制定方法各異。演化規(guī)則為：

rule0：if ，then

rule1：if ，

then

其中是中心細(xì)胞在t時(shí)刻的狀態(tài)，是中心細(xì)胞的鄰域細(xì)胞組。

（二）、自動(dòng)機(jī)路徑規(guī)劃算法

移動(dòng)機(jī)器人的過程，是在細(xì)胞空間中，以諾依曼型鄰域演化狀態(tài)空間，逆序遞歸搜索路徑的過程。為了記錄搜索軌跡，并找到路徑，我們建立表和表，分別記錄存放待擴(kuò)展的細(xì)胞和已演化的細(xì)胞，并設(shè)置指針。演化算法步驟如下：

將起始細(xì)胞 放入表

若表為空，則失敗退出

取表中第一個(gè)細(xì)胞，生成型鄰域細(xì)胞，并放入子節(jié)點(diǎn)集合中

對中的每一個(gè)細(xì)胞，計(jì)算狀態(tài)值 ，并設(shè)置指向的指針

若目標(biāo)細(xì)胞 ，則轉(zhuǎn)向

將成員放入表中， 移入表，并在表中刪除，轉(zhuǎn)向

由目標(biāo)細(xì)胞，逆序回溯起始細(xì)胞，輸出路徑，退出。

四、仿真實(shí)驗(yàn)及分析

在仿真實(shí)驗(yàn)中，用柵格法對復(fù)雜的礦井環(huán)境進(jìn)行離散化。將柵格賦值，得到細(xì)胞空間的初始狀態(tài)。障礙物占據(jù)的區(qū)域標(biāo)記為黑色，白色細(xì)胞空間為礦井巷道，移動(dòng)機(jī)器人實(shí)現(xiàn)的目標(biāo)是從工作空間中任一可行位置，移動(dòng)距離最短且無碰撞，安全到達(dá)目標(biāo)終點(diǎn)，環(huán)境仿真如圖1所示。場景在仿真的離散細(xì)胞空間，任意設(shè)定移動(dòng)機(jī)器人的合理起始位置和目標(biāo)位置，以機(jī)器人為中心細(xì)胞的二維空間內(nèi)正交分布四個(gè)運(yùn)動(dòng)方向，路徑規(guī)劃效果如圖1所示。

2 場景防撞路徑規(guī)劃

實(shí)驗(yàn)結(jié)果顯示，算法找到一條最優(yōu)路徑。但井下環(huán)境復(fù)雜，移動(dòng)機(jī)器人自身存在體積，緊貼障礙物的移動(dòng)路徑，可能導(dǎo)致機(jī)器人某一部分與障礙物碰撞。因此，算法中應(yīng)對障礙物邊緣進(jìn)行檢測，認(rèn)為障礙物邊沿生長一定禁行區(qū)域，使其與機(jī)器人之間始終保持一定的安全距離。在相同工作環(huán)境下，考慮障礙物生長后的搜索路徑如圖2所示。與圖1相比，仿真結(jié)果中的路徑找到了次優(yōu)路徑，并具有安全性。

五、結(jié) 論

算法本文研究了柵格建模和細(xì)胞自動(dòng)機(jī)算法在煤礦井下路徑規(guī)劃中的應(yīng)用。環(huán)境信息有細(xì)胞空間狀態(tài)值表示，通過不同鄰域細(xì)胞的遞歸演化，實(shí)現(xiàn)井下巷道移動(dòng)機(jī)器人的路徑規(guī)劃。為適應(yīng)環(huán)境，增加規(guī)劃路徑的安全性，在避障中加入障礙物生長因素，降低碰撞風(fēng)險(xiǎn)。仿真實(shí)驗(yàn)證明了此算法在復(fù)雜井下環(huán)境中，有效規(guī)劃出最優(yōu)或次優(yōu)路徑，利于動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)。

參考文獻(xiàn)：

[1] Choi G.J， Ahn D S. Map Building and Localization on Autonomous Mobile Using Graph and Fuzzy Inference System[C].IEEE：2004：2419-2424

[2] 莊嚴(yán)， 徐曉東， 王偉. 移動(dòng)機(jī)器人幾何-拓?fù)浠旌系貓D的構(gòu)建及自定位研究[J]. 控制與決策，2005，20（7）： 815-818