0．引言
        路径规划是移动机器人控制的关键，关系到机器人的执行效率，而迷宫机器人的路径规 划一直是控制领域和计算机领域的研究热点问题。相对于未知的迷宫环境，迷宫机器人大多 都利用自带的传感器设备如摄像头来获取迷宫的信息。本文针对迷宫的特殊环境，用上位机 的视觉系统采集迷宫图像，通过设置色标的方法，结合改进A*搜索算法实现了迷宫机器人 的路径规划。
        迷宫机器人系统采用CCD 摄像头来感知和识别整个迷宫系统。采集的迷宫和机器人位置 信息通过上位机进行图像处理。迷宫机器人和上位机通过无线装置传递实时信息。其中迷宫 环境是由人为设定的某种迷宫栅格的形式；迷宫机器人则采用色标进行颜色辨别。迷宫机器 人系统如图1 所示：
        

        1．图像处理
        1.1 色标和颜色空间的确定
        迷宫机器人系统的路径搜索是基于视觉处理的搜索算法，其搜索路径的前提是系统所获 取的图像，因而色标的选取和颜色空间的确定对后续的图像处理与识别有很大的影响。 机器人的色标有各种不同的方案，但是实际系统中应该采用尽量醒目，相互之间广义距 离尽量大的颜色作为不同的色标。迷宫机器人系统采用红色，蓝色，绿色，黑色CONTROL ENGINEERING China版权所有，白色分别 表示车头，车尾，目标，迷宫墙和可以行走的路径。
        YUV 颜色空间由于可以减少数据储存空间和数据传输带宽，非常适合迷宫机器人系统的 图像处理运算。YUV 是PAL 和SECAM 模拟彩色电视制式采用的颜色空间www.cechina.cn，Y 表示亮度， U，V 用来表示色差，U，V 是构成彩色的两个分量。RGB 与YUV 之间的转换关系如下：

        1.2 图像阀值分割及栅格化
        区域阀值分割方法[1]是通过设定不同的特征阀值，把图像象素点分为若干类。例如设原 始图像为g(x, y)，按照一定的准则，在g(x, y)中找到特征值T，将图像分割成两个部分：

        在图像分割的过程中，应用最大类间方差可以有效的降低图像处理的复杂度。其实现是 将直方图在某一阀值处分割成两组，当被分成的两组的方差为最大时，得到阀值。因为方差 是灰度分布均匀性的一种量度，方差值越大，说明构成图像的两部分差别越大，当部分目标 错分为背景或部分背景错分为目标都会导致两部分差别变小，因此使间类方差最大的分割意 味着错分概率最小。
        图像的灰度级范围是 0,1,2,…...L-1，设灰度级i 的象素点个数为mi，图像的象素点总数为：

        则灰度级 i 出现的概率pi 定义为：

        阀值 t 把图像的象素分为C0=(0, 1, …., t)和C1=(t+1, t+2, ….., L-1)两类（分别表示门标和背 景）。C0 和C1 类出现概率及均值分别为：

        其中：

        C0 和C1 类的方差：

        类间方差为：

        类内方差为：

        总体方差为：

        通过引入关于 t 的等价判决准则函数：

        并求取函数的最大值就能得到最优阀值：

        2．路径规划算法
        A*算法[2][3]是人工智能中一种有效的启发式算法。用一个估价函数f(n)=g(n)+h(n)来估计 从起始点S经节点n 到目标点G的代价，其中g(n)表示从起始点到节点n的代价，g(n)是一 个确定值控制工程网版权所有，h(n)代表从节点n 到目标点G 的代价估值，g(n)和h(n)的数学表达式可以根据 实际情况而定。
        h(n)采用欧拉距离计算节点n和目标点之间的距离，因节点n和目标点之间一般会存在障 碍物，这样h(n)可能会比实际值h*(n)小很多，反而会走一些不必要的节点，为了减小这种 现象发生的概率，本文使用A*算法逆向搜寻最优路径。由于迷宫的特殊环境，为了提高搜 索效率，在保证算法可接纳性定理的条件下，对估价函数进行了加权处理：

        算法描述如下：
        (1) 初始化，将所有节点的估价置0，将障碍物所在节点的估价置最大值M；
        (2) 创建待处理节点列表OpenList，并把目标节点放入OpenList中；
        (3) 重复如下过程，直到OpenList为空：
        a．取出OpenList中估价值最小的节点作为待处理节点CurNode
        b．通过计算CurNode的状态空间中每一个有效成员的估价值更新其状态空间，并将 更新后的节点放入到待处理列表OpenList中。判断一个成员是否有效必须同时满足3 个条件：节点不是障碍物；节点还没有被估过价；节点不是目标点。
        (4) 根据估计值提取路径
        整个算法主要包含比较、估价和排序三个过程，可以通过适当的优化手段进一步减小计 算量，降低系统资源消耗。比较的过程体现为逻辑运算，其消耗资源很小。估价的过程可以 通过判断父亲节点和子节点的相对位置完成，以便减少运算量。排序过程可以通过创建一个 有序列表(OpenList)完成。即在节点插入待处理列表时，就按照估价值从小到大的顺序插入， 保证列表始终处于排序状态。这样做既方便了运算，也提高了搜索速度。
        3．算法仿真
        在主频1.8GHZ，内存为1GB 的PC 机上,作者分别对20*20、30*30 和50*50 的迷宫机器
        人系统进行了仿真实验，如下图所示：

        从仿真结果可以看出基于机器视觉的A*算法能在满足迷宫机器人实时性的前提下寻找 出较优的路径。但是随着迷宫地图的增大，算法的搜索路径的时间也在逐步增加，如何在大 地图中提高迷宫机器人路径规划的实时性，是作者下一步的工作重点。
        4．结论
        本文作者的创新观点：提出了一种机器视觉和逆向 A*算法相结合的法，该方法实现简 单，实时性较好，能解决复杂的未知环境下迷宫机器人路径规划问题。
        参考文献：
        [1] 何超，熊蓉，戴连奎.足球机器人视觉图像的快速识别[J].中国图像图形学报,2003， 8A(3):271-275.
        [2] R.Dechter and J.Pearl. Generalized best-first search strategies and the optimality of A*.JACM,32(3):505-536.1985.
        [3] R.E.Korf. Real-time heuristic search. Artificial Intelligence, 42(3):189-211, 1990.
        [4] 张海涛，程荫杭CONTROL ENGINEERING China版权所有，基于A_算法的全局路径搜索[J]微计算机信息,2007,6-2：238-239.
        作者简介：周毅（1982-），男（汉族），湖南汉寿人，北京工业大学电子信息与控制工程学 院，硕士，主要从事机器人路径规划方向的研究。
        Biography: Zhou Yi(1982-), Male(Han), HuNan Province, Beijing University of TechnologyCONTROL ENGINEERING China版权所有, Master, Major in Path planning for robot.
        作者简介：崔刚（1971-），男（汉族），河北人，北京工业大学电子信息与控制工程学院副 教授，硕士生导师，主要从事人工智能和智能控制方向研究。
        Biography: Cui Gang(1971-), Male(Han), HeBei Province, Beijing University of TechnologyCONTROL ENGINEERING China版权所有, Professor, Major in artificial intelligence and control