一種基于智能方法井下路徑規劃研究

劉曉羽 徐斌

摘要：針對移動機器人礦井巷道環境，柵格法離散物理環境后，提出利用細胞自動機算法建模，進行路徑規劃的方法。算法將機器人工作空間定義為一組離散的細胞狀態，通過控制演化的規則和記錄演化進程中的路徑信息，搜索巷道上任意兩節點之間的最優路徑。仿真實驗說明該方法的有效性。

關鍵詞：移動機器人；細胞建模；路徑規劃

一、引言

隨著煤礦井下礦難事故頻有發生，安全可靠的井下搜救與環境監測移動機器人是非常必要的。由于井下巷道地形復雜，災后環境不確定性增加，要求搜救機器人有較強的自主路徑規劃能力。傳統上，常用拓撲結構將空間分區的拓撲地圖表述環境[1]， 幾何方法表述環境地圖，多種方法混合使用[3]，取得良好效果。由于井下工作背景復雜程度提高，環境信息冗雜，使得建模過程和數據處理變得復雜，容易丟失環境細節，影響機器人路徑規劃的實時性和準確性。

本文提出了一種基于細胞自動機的方法，通過柵格環境場景，將離散化的每個單元看作細胞賦以狀態值，即把移動機器人物理工作環境離散為抽象的細胞狀態空間。運行自動機演化規則，遍歷運行全局區域，通過遞歸搜索得到機器人在巷道中的最優路徑。仿真實驗結果，驗證了算法的有效性。

二、巷道工作空間建模

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

以柵格所表征的信息不同，整個工作區域可分為兩類，即自由運動區域和障礙物區域。若柵格為障礙物所占據，則標記固定數值；若為移動機器人可遍歷空間，則定為自由運動區域。場景信息抽象為數字地圖，便可轉化為細胞狀態空間，賦予細胞狀態值，利用自動機演化規則，優化自由運動區域的移動軌跡，搜索出最優或次優的移動機器人路徑。

三、基于細胞自動機的路徑規劃方法

（一）、細胞自動機算法描述

細胞自動機是在一個由有限狀態的細胞組成的離散細胞空間上，依照規定的局部演化規則，在離散的時間上進行演化的動力學系統。柵格中每個單元都可以看做一個細胞，于時間和空間上離散。設定模型為一個五元組：

其中，為離散時間，為模型中的最基本單元，即細胞；模型中全體細胞空間稱為；是中心細胞周圍鄰域內的細胞，根據實現目標不同，可選擇不同鄰域；為模型的演化規則，決定中心細胞與鄰居細胞之間的演變過程。

柵格化的移動機器人空間中，每個柵格均看作細胞，即第行，第列的細胞，細胞在每一時刻有唯一狀態值。所有可能的細胞狀態，必須為有限個。當某一演化規則作用時，工作區域內所有細胞均按演變規則，更新自身狀態。而細胞空間初始狀態，由機器人獲知的環境信息決定。通過傳感器更新自動機的輸入，不斷迭代所有細胞狀態，演化環境變化。

由描述對象決定，本文細胞初始狀態有四種不同狀態，即細胞在某一時刻，。當細胞為機器人自由運動區域，狀態值為0；當細胞所在區域有物體存在，機器人不能經過，狀態值為1；當初始時，細胞區域有機器人占據，狀態值為3；當細胞區域為移動機器人目標位置，狀態值為2.

當前細胞組中，中心細胞與鄰居細胞之間的狀態關系，決定了移動機器人的行走方向。原則上機器人可以向任意方向移動，實際模型中機器人受自身配置傳感器的限制，鄰居模型通常采用八個方向的摩爾鄰居，和四個方向的馮諾依曼（）鄰居。限于計算復雜度的考量，本文采用馮諾依曼模型。

移動機器人路徑規劃可采用動態規劃方法，即由目標終點開始，逆序遞歸，回溯到起始位置的演化思路。細胞自動機的演化規則，依據實現目標不同，制定方法各異。演化規則為：

rule0：if ，then

rule1：if ，

then

其中是中心細胞在t時刻的狀態，是中心細胞的鄰域細胞組。

（二）、自動機路徑規劃算法

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

將起始細胞 放入表

若表為空，則失敗退出

取表中第一個細胞，生成型鄰域細胞，并放入子節點集合中

對中的每一個細胞，計算狀態值 ，并設置指向的指針

若目標細胞 ，則轉向

將成員放入表中， 移入表，并在表中刪除，轉向

由目標細胞，逆序回溯起始細胞，輸出路徑，退出。

四、仿真實驗及分析

在仿真實驗中，用柵格法對復雜的礦井環境進行離散化。將柵格賦值，得到細胞空間的初始狀態。障礙物占據的區域標記為黑色，白色細胞空間為礦井巷道，移動機器人實現的目標是從工作空間中任一可行位置，移動距離最短且無碰撞，安全到達目標終點，環境仿真如圖1所示。場景在仿真的離散細胞空間，任意設定移動機器人的合理起始位置和目標位置，以機器人為中心細胞的二維空間內正交分布四個運動方向，路徑規劃效果如圖1所示。

2 場景防撞路徑規劃

實驗結果顯示，算法找到一條最優路徑。但井下環境復雜，移動機器人自身存在體積，緊貼障礙物的移動路徑，可能導致機器人某一部分與障礙物碰撞。因此，算法中應對障礙物邊緣進行檢測，認為障礙物邊沿生長一定禁行區域，使其與機器人之間始終保持一定的安全距離。在相同工作環境下，考慮障礙物生長后的搜索路徑如圖2所示。與圖1相比，仿真結果中的路徑找到了次優路徑，并具有安全性。

五、結 論

算法本文研究了柵格建模和細胞自動機算法在煤礦井下路徑規劃中的應用。環境信息有細胞空間狀態值表示，通過不同鄰域細胞的遞歸演化，實現井下巷道移動機器人的路徑規劃。為適應環境，增加規劃路徑的安全性，在避障中加入障礙物生長因素，降低碰撞風險。仿真實驗證明了此算法在復雜井下環境中，有效規劃出最優或次優路徑，利于動態規劃的實現。

參考文獻：

[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] 莊嚴， 徐曉東， 王偉. 移動機器人幾何-拓撲混合地圖的構建及自定位研究[J]. 控制與決策，2005，20（7）： 815-818