一种基于智能方法井下路径规划研究

刘晓羽 徐斌

摘要：针对移动机器人矿井巷道环境，栅格法离散物理环境后，提出利用细胞自动机算法建模，进行路径规划的方法。算法将机器人工作空间定义为一组离散的细胞状态，通过控制演化的规则和记录演化进程中的路径信息，搜索巷道上任意两节点之间的最优路径。仿真实验说明该方法的有效性。

关键词：移动机器人；细胞建模；路径规划

一、引言

随着煤矿井下矿难事故频有发生，安全可靠的井下搜救与环境监测移动机器人是非常必要的。由于井下巷道地形复杂，灾后环境不确定性增加，要求搜救机器人有较强的自主路径规划能力。传统上，常用拓扑结构将空间分区的拓扑地图表述环境[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