教学型智能移动机器人在“走迷宫”竞赛中的应用

龙威林

(天津现代职业技术学院，天津 300350)

教学型智能移动机器人在“走迷宫”竞赛中的应用

龙威林

(天津现代职业技术学院，天津 300350)

将教学型智能移动机器人成功的应用在电脑鼠走迷宫竞赛当中，与实际教学联系的更加紧密。对电脑鼠走迷宫竞赛中的实际问题，如运动姿态的控制进行了研究，并对几种经典的路径规划和优化算法进行了研究。本文研制的教学型智能移动机器人不仅具有性能稳定、实时性好等特点，此外，在设计上考虑全面，结合了多学科的知识技术，能够实现模块化扩展，也尽可能的降低了成本，便于高校相关专业学生实践学习和竞赛培训使用。

教学型智能移动机器人；嵌入式硬件平台；嵌入式软件平台；电脑鼠走迷宫竞赛；路径规划

1 “走迷宫”竞赛背景

1.1 竞赛起源与发展

“走迷宫”的小型智能移动机器人，又根据外形被形象的称为“电脑鼠”，是设计一个小型移动机器人，在“迷宫”中从起点出发，自行选择路径到达终点，并自动记忆迷宫的信息，寻找路径的最优化，以实现最快的穿过迷宫。这个竞赛是由国际电工电子工程学会发起的，无论是大中专院校的在校学生，还是社会上的工程技术人员、科学工作者和电脑鼠爱好者，均可参加。

“电脑鼠”的这个概念，最早是在1977年、由IEEE Spectrum杂志提出的。1979年，第一届电脑鼠走迷宫大赛举行。

1980年，在伦敦举办了欧洲电脑鼠比赛。同年11月日本举办了首场日本电脑鼠竞赛。

1985年8月，在日本筑波举办了首场国际范围内的电脑鼠竞赛。参赛者来自欧洲各国、美国以及日本。比赛无论是规模还是技术水平都达到了空前的高度。

1987年10月，新加坡举行了第一届新加坡电脑鼠比赛。

1991年，世界锦标赛在香港举行，香港世锦赛同样得到了来自全世界电脑鼠爱好者的关注，参赛国家、参赛人数创下新高。

电脑鼠竞赛被引入到我国大陆还比较晚，直到2007年才举办了大陆第一次地区性的电脑鼠竞赛，之后，电脑鼠竞赛逐渐在大陆普及，成为了一项全国高校普遍关注的重要竞赛。

1.2 竞赛规则

迷宫通常是由16×16个﹑18cm×18cm大小的正方形单元组成。起始点通常设在迷宫四个角落中的一个。起始点只允许有一个出口，比如如果电脑鼠只能从北边的方向进入到迷宫内部的话，那么西、南两方向就必须都具有阻隔用的墙壁。终点设在迷宫中央，只留一个入口。具体结构如图1所示。

图1 电脑鼠迷宫实物图

2 运动姿态控制

电脑鼠依靠控制左右两个步进电机、传感器测距以及合适的算法，来实现避障、动作调整和方向控制。电脑鼠稳定运行的前提下，可全面搜索整个迷宫，绘制并存储迷宫信息，再通过微控制器进行计算，来找到最短的目标路径。

2.1 电脑鼠底层驱动程序设计

电脑鼠作为一个智能机器人，灵活程度和智能程度不仅仅依赖于硬件设计，还要依赖于良好的软件性能。电脑鼠程序设计结构分为底层驱动程序和顶层算法程序。前者主要用来实现电脑鼠的移动和检测功能等，比如测量移动的距离、向左或向右转九十度、转向、迷宫环境信息检测，等等。

2.1.1 两相四线制步进电机驱动时序

驱动步进电机的时序主要有单拍驱动、整步驱动、半步驱动。

2.1.2 步进电机的加减速控制

通常，我们通过控制换相的时间间隔，从而对电机的速度进行控制。利用定时器来控制速度的电机，我们可以通过定时器装载值的改变，来控制电机的速度。步进电机接收步进脉冲信号和方向电平信号，脉冲信号的到来将使电机旋转一个步距角，接收到的脉冲信号频率越高，转动的速度越快。

实验表明，脉冲信号频率过高的话，电机将不能同步的运行，产生失步，半步驱动能够改善这一现象。加减速实时算法主要是使用定时器中断。电机转过的步数通常可由n表示(ω为电机的加速度)：

(4-1)

这样，电机转过n步所花的时间为：

(4-2)

2.2 电脑鼠运动状态的控制

电脑鼠移动过程中，两个电机性能不尽相同，与车身的连接也可能不太相同，这些因素都会造成对电脑鼠移动过程精度的影响。因此，这些随机问题难以计算和预测，也不容易解决。对电脑鼠的运动状态进行控制，是研究中的重点和难点。本设计通过调整电脑鼠左、右、左前、右前、前方五个方向上的红外传感器，以及设定阈值的方法来解决。假设，左和右两个传感器的阈值设为4cm，左前和右前设为6cm。电脑鼠移动中，如果偏向某一侧，那必有一个方向上与墙壁的距离会小于设定值。此时，电机控制程序发出中断信号，系统将修正左右电机步数，直到距离超过设定值，说明电脑鼠回到路径正中。

2.2.1 电脑鼠转弯

电脑鼠的转弯角度有直角和水平两种。直角转弯又包括行进中转弯和原地转弯。行进中转弯更快捷，转弯半径相对也更小。但控制上相对要困难一些。所以，前进中的转弯技术是非常重要的。

目前采用的转弯办法是，两侧的电机分别在运动的状态当中处于加速和减速的状态，调整步数后同时向前转动。转弯后，再使电机加速，恢复前进，这种转弯也叫漂移转弯。这种转弯办法更节省时间。

2.2.2 使用传感器获取信息进行姿势修正

由于两轮的摩擦、初始位置等因素，如果电脑鼠要在迷宫中直线移动，需要不断的调整姿势，以免与墙壁发生碰撞。本设计的机器人以5个IRM8601S的红外传感器作为“眼睛”。W1至W5用来调节红外强度，也就是调节传感器的检测范围，RF1至RF5为红外发射装置，W1与RF1构成红外发射电路，发射端口与微控制器相连。这五组传感器中，RF1、RF3、RF5都与PE0端口相连，RF2和RF4则与PB0相连。红外接收端U1到U5的输出信号分别与微控制器的PB1到PB5端口相连。通过调节电阻W1改变驱动电流，从而改变“眼睛”的“视力”。

在迷宫移动过程中，电脑鼠的理想姿势中位于两侧墙壁的中心线上，前进的方向与墙壁平等。这种状态下最不容易碰撞墙壁。根据这五个传感器的安装位置可分为两组，U1、U3、U5一组，检测左、前、右三个方向的墙壁信息，U2和U4一组，主要用来调整电脑鼠的姿势。

图2则是几种不佳的姿势。图2 a中，前进方向偏离，如果不及时调整，就会与左侧墙壁发生碰撞。图2 b中，虽然电脑鼠是平行与墙壁的，但由于车身过于靠近左侧，也需要调整。图2 c中，电脑鼠前进中偏移且接近左侧，这种情况目前是不需要修正，因为按照这个趋势下一时刻它会移动到中间。

a

b

c

图3示意的是电脑鼠在路径左侧发生偏移的调整方法。同理，可以调整在右侧发生偏移的情况。用传感器检测位置偏差的方法如下。图2和3中，都显示有一段箭头，这是传感器U2的检测示意。箭头长度代表U2所能够检测的距离。

可以看出，在图2 c中，传感器U2探测不到墙壁，也就是说不需要调整。在图2 a和b中，传感器能够检测到墙壁，这就意味着需要调整。当电脑鼠接近右侧墙壁的时候，调整方法相同，只是此时检测到墙壁的传感器是U4。如图3所示，假设只有左侧一侧存在墙壁，调整方法与图2的调整方法完全相同。

a

b

c

如图4所示，此时电脑鼠向右侧偏差，但因为右侧没有墙壁，只能用U1传感器，检测到左侧有墙壁而且与墙壁的距离过远时，机器人就应该向左侧靠近作为调整。

同理，可以调整只有右侧有墙壁的情况。如图5所示，当电脑鼠处于如图所示的位置时，U2和U4都检测到前方的墙壁，就会带来错误的判断。所以，当前方有墙壁时，应不处理U2和U4的检测结果。

图4 电脑鼠右侧位置偏差示意图

图5 前方存在墙壁示意图

综合上面的几种情况可以看出，如果发现左侧的信号强于右侧，应当向右转向，反之则应该向左转。在设计中，如何在调整中合理的控制向左和向右转的速度，是一个核心的问题。理想情况下，调整后的电脑鼠迅速回到正常位置上，而且震幅轻微。为了实现这个理想情况，可以采用数字PID算法，比例控制具有快速调整现状的功能，使调整更加灵敏快速。积分控制则可以利用历史状态进行调整，提高系统的稳定程度。微分控制则可以系统未来状态来进行调整，可以改善系统的动态特性。

3 路径规划算法

机器人的路径规划是指根据机器人的作业要求，在有障碍的环境中，按照一定的标准，对末端执行器在工作过程中的状态进行设计，使其能够按照要求寻找一条从起始点到目标点的无碰撞最优路径。电脑鼠的路径规划问题是移动机器人规划的分支，为了研究需要，把电脑鼠的路径规划问题扩展到移动机器人领域。

3.1 传统迷宫搜寻法则

传统迷宫搜索算法主要有右手法则、左手法则、中左法则、中右法则、乱数法则、向心法则。以右手法则和左手法则为例具体解释一下算法：

3.1.1 右手法则

机器人前进时，如果前方存在两条及以上的支路时，需要决定选择哪个方向转弯。选择不同的转弯的方向将产生不同的运行路径。可以使机器人的选择顺序为，右转、向前、左转，这种策略就称为右手法则。示意图如图6所示。图中坐标(0，0)为起始点，虚线为机器人的运动路径，很明显，每次机器人遇到支路时，都优先右转，不能右转的情况下会直行，只有既不能右转也不能直行的情况下才会左转。

通过图6中几个关键点，来分析和解释一下右手法则。坐标(0，4)处，机器人既可以右转也可以前进，按照右手法则，机器人选择了右转；坐标(2，0)处，既可以左转也可以右转，按照右手法则，机器人选择了右转；坐标(4，0)处，既可以前进也可以左转，按照右手法则选择了前进。

3.1.2 左手法则

左手法则与右手法律完全对应，机器人优先考虑顺序为，左转、前进、右转。如图7所示。同样从(0，0)出发，虚线为机器人的运动路径。不同的是，机器人遇到支路时，都会优先左转，不能左转时继续前进，既不能左转又不能前进时才向右转弯。

同样，选择图7中几个关键点进行分析和解释。坐标(2，6)处，可以选择左转或右转，依据左手法则选择左转；坐标(1，8)处，可以选择前进或右转，依据左手法则选择前进；坐标(2，F)处，机器人可以选择右转或前进，但前进失败后，最终选择右转。

3.2 基于等高图最优路径的优化算法

3.2.1 等高图最优路径算法

假设机器人对迷宫进行了全遍历，或是只遍历了包含起始位置和终点的一部分，记录下了已经遍历的迷宫信息，则可以利用等高图算法寻找到最优路径。

以4×4的小迷宫为例来制作等高图的步骤如图8至图15：

图8 等高图步骤一

图9 等高图步骤二

图10 等高图步骤三

图11 等高图步骤四

图12 等高图步骤五

图13 等高图步骤六

图14 等高图步骤七

图15 等高图步骤八

按照这种方法遍历整个迷宫，得到等高图。等高图中单元中的数字即为步数，如坐标(2，3)距离起点有6步，坐标(1，2)则距离起点有4步。

蓝色和黄色两条线条标示了从起始位置到终点的两条路径，蓝色路径需要10步，黄色路径仅需要8步。所以在不考虑转弯次数的情况下，很明显，黄色路径是最优解。

3.2.2 转弯加权的等高图最优路径算法

不过在现实中，电脑鼠转弯需要花费的时间很难忽略不计，如图16，虽然坐标(3，3)和坐标(3，1)的等高数均为7，但可以肯定的是，电脑鼠从起始位置到(3，3)要比到(3，1)的时间更短。所以，我们必须给转弯次数加权。权值设为1的话，图16经过加权后转变为图17。在设计中，权值是根据电脑鼠的实际转弯情况来决定的，为了方便研究，在本文里设为1。

图16 等高图最终的示意图

图17 转弯加权后的等高图

3.3 几种算法的比较

传统迷宫搜索算法的优点是算法简单、易于实现，在运行前不需要进行迷宫遍历；缺点是迷宫搜寻效率不高。等高图最优路径算法的优点是迷宫搜索效率较高，适用于冲刺环节；缺点是在运行前，需要遍历迷宫，得到所有迷宫信息。转弯加权的等高图最优路径算法的优点是算法考虑了电脑鼠在转弯时的速度损失问题，尽可能的减少了电脑鼠的转弯次数，迷宫的搜寻效率进一步提高；缺点是由于采用了加权算法，算法的复杂度进一步提高。

4 总结与展望

教学型智能机器人在“电脑鼠走迷宫”竞赛中的应用，对“走迷宫”竞赛的背景、意义、规则作了详细的介绍，如何控制电脑鼠在竞赛场地中运动姿态，实现快速的转弯和路径规划也作了详细了分析。基于教学型机器人平台CPU的选择以及算法的难易程度，在电脑鼠的路径规划算法多采用转弯加权的等高图最优路径算法。考虑了电脑鼠在转弯时的速度损失问题，尽可能的减少了电脑鼠的转弯次数，进一步提高了迷宫的搜寻效率。

进一步研究工作的展望：

电脑鼠是否能够快速准确高效的走出迷宫很大程度上取决于采取的路径规划算法，本文对几种先进的算法进行了研究，但由于时间限制，并没有将这些算法全部运用在实际的系统当中。未来将会将这些算法进行实际的应用，在实践中比较各种算法的优缺点，找出最适合的算法，并加以改进。

在研究过程中，发现模糊PID算法对于电脑鼠的电机控制比常规的PID算法收到的控制效果更好。但模糊PID控制算法中，函数中的参数选择很重要，由于时间限制也没有对此进入深入的研究。未来将会把模糊PID算法引入到电脑鼠当中，并通过实验尽可能的实现控制效果的最优。

[1]Brunette E S, Flemmer R C, Flemmer C I. A review of artificial intelligence. 4thInternationalConferenceonAutonomousRobotsandAgents, 2009, 385～392.

[2]Kibler S G, Hauer A e , Giessel D S, et al.IEEEMicromouseformechatronicsresearchandeducation.IEEEInternationalConferenceonMechatronics, 2011: 887～892.

[3]Ning Chen, Hwang Chung, Young K. Kwon. Integration of Micromouse Project with Undergraduate Curriculum: A Large-Scale Student Participation Approach.IEEETransactiononEducation, 1995, 38(2):136～144.

[4]Maaret H, Barret C. Sensor-based navigation of a mobile robot in an indoor environment.RoboticsandAutonomousSystems, 2003, 38:1～18.

[5]孙舟, 雷斌. 电脑鼠走迷宫转弯算法的改进与实现[J].电子元器件应用, 2011, 13(1).

[6]柳长安, 鄢小虎, 刘春阳等. 基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5).

[7]Ching-Chih Tsai, Shu-Min Shish, Hsu-Chih Huang, et al. Autonomous navigation of an indoor tour guide robot.IEEEWorkshoponAdvancedroboticsandItsSocialImpacts, 2008, 23-25:1～6.

[8]张立毅, 费腾, 刘婷等. 基于混沌蚁群算法的应急物流路径优化算法[J].中国民航大学学报, 2011, 29(03).

[9]倪世宏, 秦军立, 苏晨. 一种求解连续空间优化问题的动态蚁群算法[J].电光与控制, 2009, 16(12).

The application of Instructional Intelligent Mobile Robots in Micromouse Contest

LONG Wei-lin

(TianjinModernVocationalTechnologyCollege,Tianjin, 300350)

Successful application of the instructional intelligent mobile robots in Micromouse Contest is more closely associated with practical teaching. This paper studies the actual issues during Micromouse Contest, such as control of moving postures, and also studies several classical route planning and optimization algorithms. The instructional intelligent mobile robot developed in this paper has stable and good performance. Besides, the robot design is considered comprehensively, combines multi-disciplinary knowledge and technologies, can realize modular expansion, and also reduces the cost as much as possible. It helps college students in related majors in experiential learning and contest training.

instructional intelligent mobile robot; embedded hardware platform; embedded software platform; Micromouse Contest; route planning

2015-07-02

龙威林(1981-)，男，湖南人，天津现代职业技术学院讲师，研究方向：机器人和无人机。

JP249

A

1673-582X(2015)08-0055-07