智能小车走迷宫算法的设计与研究

王蒙+朱冬旭+李治

【摘 要】智能小车是一种集感知、判断、行走功能于一体的微型机器人，能够自动寻找最佳路径并且达到目的地。对智能车搜索和冲刺迷宫提出了一种算法。智能小车可根据行走的路线和拐弯的情况进行变速调节，提高了智能车的行进速度以及灵活性。利用已经搜索到信息的耦合关系，对算法提出改进，缩短了智能小车搜索的时间。

【关键词】智能小车；算法；迷宫；探索策略

中图分类号： TP242 文献标识码： A 文章编號： 2095-2457（2017）23-0017-002

【Abstract】Intelligent car is a micro robot with the functions of perception，judgment and walking.It can automatically find the best path and achieve the destination.An algorithm for intelligent vehicle search and sprint maze is proposed. Smart car according to the routes and turns of speed regulation，improve the speed and flexibility of intelligent vehicle By using the coupling relation of searching the information，the algorithm is improved，and the time of searching the intelligent car is shortened.

【Key words】Smart car；Algorithm；Maze；Exploration strategy

0 背景

智能机器人的需求越来越大，应用领域日益广泛，大到宇宙探索、深海研究、军事等领域，小到工厂企业、家庭等都对智能机器人提出了很高的要求。智能机器人的路径研究成为热点。

智能机器人的路径研究，放到迷宫中进行探索，能更好地适应自主寻找目标。迷宫的生成通过仿真模拟实现，由隔墙板沿方块的四周布设，形成迷宫通道。智能小车的包括电源模块、微处理器模块、传感器模块、电机模块、驱动模块。小车的整体设计方案如图1所示。

智能小车是由一个微处理器控制的，集感知、判断、行走功能与一体，能够自主寻找最佳路径并达到目的地的微型机器人，可以在迷宫中感知并记忆迷宫地图，通过一定的算法，寻找一条最佳路径，以最快的速度达到目的地。

1 走迷宫算法

1.1 性能指标

智能小车的基本功能是从起点走到终点，这个过程称为一次运行，所花费的时间称为运行时间。从智能小车的第一次激活到每次运行开始，这期间所花费的时间称为迷宫时间。智能小车走迷宫的性能主要从速度、求解迷宫的效率和小车的可靠性来评判。

智能小车在在有限的时间或探测次数下，采用部分迷宫探索策略，只探测迷宫的一部分，从中找出最佳路径。如果小车根据设定的算法行进，最终选择出一条最优的路径，称为相对最优路径。迷宫中实际存在的最优路径称为绝对最优路径。

如果进入迷宫是为了进行探索和记忆，则这次运行称为“试跑”。如果进入迷宫是根据先前的记忆和经验，按照智能算法确定最佳路径，并以最快的速度达到终点，则这次运行称为“冲刺”。

1.2 探测策略

智能小车在迷宫内行走，如果最终无路可走，则该路径称为“死路”；如果存在2个或2个以上的方向可以行走，称为“交叉”。遇有交叉时，在行走方向的选择上可以有如下几种选择法则：

右手法则：以右边为优先前进的方向，其次是直线方向、左边方向。

左手法则：以左边为优先前进的方向，其次是直线方向、右边方向。

中左法则：以直线为优先前进的方向，其次是左边方向、右边方向，同理还有中右法则。

乱数法则：取随机值作为前进方向。

中心法则：由于终点设在迷宫中心，遇到交叉时取指向迷宫中心的方向为优先选择的方向。

1.3 标记

为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。迷宫共有16×16个单元，可采用二维坐标的方式进行标记，即用每个单元的XY坐标表示。此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位和相对方位两种方式。

绝对方位：这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别表示“东”﹑“西”﹑“南”和“北”四个方向。以1表示允许行进（无墙壁），0表示不允许行进（有墙壁）。

相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实现标记，分别表示“前”“左”“右”， 以1表示允许（无墙壁），0表示不允许（有墙壁）。

绝对方式利用具体的坐标来记忆，具有唯一性，能够减少处理器的运算，但没有考虑小车的具体指向。相对方式根据小车具体的指向来确定，容易造成混淆，增加记忆的数据。

1.4 试跑

试跑是获得迷宫地图的唯一方法，在规则允许的情况下，应尽可能多的获取迷宫信息，为最后的冲刺做准备。在试跑过程中除了要对经过的单元进行线路标记外，还要选择一种合理的探测策略。

1.5 阻隔

根据小车试跑的数据，可以将小车遇到死路的路径进行分析，将其前一个遇到交叉的路口进行阻隔，当小车再次遇到此交叉时，不会再次寻找此路径，缩短探索时间。

1.6 最佳路径的选择

智能小车要在最短的时间完成冲刺，路径的选择至关重要。选择步数少的路径是确定最佳路径的条件之一，但不是唯一条件。考虑智能小车在拐弯时同样需要时间，所以要将拐弯次数加权后再加到步数中，以确定加权步数。endprint

加权步数=步数+拐弯次数×拐弯权重

拐弯次数：一个90度的拐弯算一次，一个180度的拐弯算两次。

小车采用变速的行走方式，如果连续3个数据均为直行方向则确定小车为提速行进的状态，如果不符合确定小车为普通速度行进。因此，小车的拐弯次数所占比重较大，经过试验权值设在1～1.3之间为宜。如图2所示为模拟智能小车的轨迹图。

2 搜索算法的改进

迷宫搜索的目标是尽量用短的时间搜索出尽量多的信息。前面的搜索路径只是根据已有的试跑数据来选择最佳路径，忽略了数据之间的相关性，不能充分利用智能小车搜索来的信息。提出在已有支路的的算法基础上对搜索路径进行优化。通过上面的研究提出一种将中心法则与洪水推演法相结合，具有预推演功能的迷宫搜索算法，该算法从剔除无效搜索路径和增加有效信息两个角度，减小智能车的搜索时间，对墙面信息进行扩展。

2.1 扩展搜索信息

智能小车的行走路径依照前面的算法只有根据当前传感器传来的数据对小车的行走进行判断，而没有注意对已探索的数据之间的耦合性进行研究。根据已有的数据进行扩展，减少探索次数，缩短探索时间。

一、开辟两个二维数组Realstep[x][y]、Exstep[x][y]。这两个二维数组分别存放实际走过的路径和扩展后的路径。迷宫的规格为256（16×16），则坐标[x][y]为16×16个单元，其中x为横坐标，y为纵坐标。每个数据的bit7代表是否真实检测，如bit7为0则代表此数据为真实路径，bit7为1则代表此数据为扩展路径。bit3～bit0代表“左”“下”“右”“上”方向，0代表该方向无路，1代表该方向有路。如0x05H表示这条数据为真实探索的数据，并且在上和下两个方向均无墙壁，左和右两个方向均有墙壁。

二、对两个二位数组进行初始化。Realstep[x][y]存储的信息為实际行走信息，在激活之前，假定迷宫内部没有墙壁，初始化为0x00H。Exstep[x][y]存放扩展信息。当x=0时，迷宫的最下面一排没有“下”方向，bit2=0；当x=15时，迷宫的最上面一排没有“上”方向，bit0=0。同理，当y=0时，bit3=0，y=15时，bit1=0。

三、对数组内部进行扩展。将Realstep[x][y]、Exstep[x][y]中的数据进行实时更新。Realstep[x][y]中的数据完全根据智能小车探索的数据进行更新，Exstep[x][y]不仅将Realstep[x][y]内部信息全部复制到数组中，还需要对其中的数据进行扩展。如（3，3）点的数据为0x05H，则（2，3）右边为0，（3，4）左边为0，（2，3）和（4，3）为上下均可以行进。

2.2 剔除死路交叉

根据扩展的路径进行分析，可以判断在遇到交叉时会有死路的选择，不必进行真实的路径探索，而直接将其阻隔，减少搜索的时间。由于剔除的路径都是经过实际路径过滤必定不能达到的路径，所以会保留可能到达终点的所有信息。这一动作增加了微处理器的运行时间，但其数量级很小，且对于减少机械运行时间来说效果甚佳。

3 实验数据与分析

在相同的环境和小车状况下，选择8幅不同的迷宫，使小车进行搜索和冲刺，得到数据如表1。

根据数据得知，改进后的算法在搜索时间上均大大缩短，其中缩短时间最大的为第7组迷宫，缩短了38.75%，冲刺时间基本没有变化。可见采用改进后的算法大大减少了搜索所需要的时间。

4 结论

智能小车在直线行进时提速拐弯时普速，实现了速度的调节，使行进更灵活快速。最重要的是在优化算法方面，通过对已知数据耦合性关系的推演改进，大大缩短了搜索迷宫的时间，提高了搜索的效率。

【参考文献】

[1]周毅.基于智能算法的机器人路径方法研究[D].北京： 北京工业大学，2009：1-15.

[2]尹伟峰.智能车设计及其追踪系统研究[D].江苏：南京理工大学，2010.

[3]王斌，张卫钢.基于IEEE标准的电脑鼠走迷宫的智能算法研究[J].电子设计工程，2011，19（12）：42-45.

[4]吴哲辉，崔焕庆，马炳先.算法设计方法[M].机械工业出版社，2008.endprint