迷宫机器人的回溯深度优先算法应用(图文)

1、迷宫机器人的回溯深度优先算法应用(图文)    论文导读：迷宫问题经典的算法是深度优先算法和广度优先算法，深度优先算法是从迷宫的入口出发，顺着某一方向向前探索，若能走通，则继续前进，否则沿原路退回（回溯)，换一个方向再继续探索，直到所有可能的通路都探索到为止，深度优先算法可以在未知迷宫中找到一条可行但不一定是最优的通路。考虑到实际物理系统内存容量和运算速度的限制以及以上算法的优缺点，带回溯的深度优先算法具有占用内存空间少，对处理器的速度要求不高，不需要知道迷宫内部的具体结构的特点，因此适合于机器人在未知迷宫中进行路径搜索。 关键词：迷宫问题，机器人，深度

2、优先    0 引言 迷宫最短路径问题是一个典型的搜索、遍历问题，目前很多学者提出了一些新的迷宫路径求解算法如如遗传算法1、脉冲耦合神经网络2 、蚁群算法3、反应扩散搜索4等，在迷宫最优路径仿真搜索方面做出了一定的成绩，但上述算法需要进行大规模的运算，对处理器的要求很高，因此只能应用于仿真层次，对于实际的物理系统来说实现起来是有困难的。 迷宫问题经典的算法是深度优先算法和广度优先算法，深度优先算法是从迷宫的入口出发，顺着某一方向向前探索，若能走通，则继续前进，否则沿原路退回（回溯)，换一个方向再继续探索，直到所有可能的通路都探索到为止，深度优先算法可以在

3、未知迷宫中找到一条可行但不一定是最优的通路。广度优先搜索是从入口出发，离开入口后依次搜索与当前位置相邻的单元格，然后分别从这些相邻单元格出发依次访问它们的邻接格，依次类推直到找到迷宫出口，算法可以找到迷宫的最优路径，但探索点会随着探索的深入急剧增加，需要大量的内存空间用来保存探索过程的记录。 考虑到实际物理系统内存容量和运算速度的限制以及以上算法的优缺点，带回溯的深度优先算法具有占用内存空间少，对处理器的速度要求不高，不需要知道迷宫内部的具体结构的特点，因此适合于机器人在未知迷宫中进行路径搜索。免费论文参考网。 1迷宫机器人结构描述 智能移动机器人技术是机器人研究领域的一个重要分支，智能移动机

4、器人是指机器人在完全未知的环境中，实时自主运动，是集环境感知、动态决策与规划、行为控制与执行等功能于一体的具有高度自动化程度的智能化装置。因此走迷宫机器人是在没有人工干预的情况下，通过机器人自身的传感器系统感知迷宫环境，并根据不同的迷宫环境做出不同的决策并驱动执行装置执行相应的动作来完成走迷宫的过程的一种机器人。免费论文参考网。 1.1机械结构描述 机器人的移动方式有很多种，但大致可分为车轮式 和足步式两种，车轮移动方式的大部分技术比较成熟， 控制也比较容易，而足步行走方式的控制要困难得多， 因此本文的迷宫机器人采用轮式移动机构，其机械结构如图1所示：它有三个车轮，其中前轮为从动轮，为万向自由

5、轮，后两轮为相互独立的驱动轮，固定不可转向，并且每个轮子都有独立的电气驱动模块和变速机构，车身的方向和速度依靠改变两轮的速度来实现。 1.2传感器系统 环境感知能力是移动机器人除了移动之外最为基本的一种能力，感知能力的高低直接决定了一个机器人的智能性高低，它的作用是建立合理的机器人感觉系统，以便机器人能够建立起完整的信息获取渠道。机器人要具备智能行为就必需依靠传感器不断感知外界环境，从而做出相应的决策行为。目前传感器的种类繁多，功能越来越丰富，像超声波传感器、红外传感器、光电传感等。传感器系统是机器人很重要的 部分，选择机器人传感器完全取决于机器人的工作需要和应用特点，因此迷宫机器人具有如下传

6、感器系统：其传感器系统包括3个红外传感器和2两个光电传感器，3三个红外传感器位于机器人的左前右方（如图1中箭头3所示），探测距离是6cm，分别对机器人左前右三个方向的迷宫墙壁进行探测，以便机器人建立起迷宫障碍物的完整信息，光电传感器1用来检测是否进入一个新的迷宫格中，而传感器2主要用来和1配合以识别机器人是否到达终点。 1.3 控制系统 控制系统主要包括单片机及其外围电路以及电机驱动模块、串行通讯模块等，单片机采用了ATMEL公司的ATmega16微控制器，在16MHZ频率下速度为16MIPS的8位RISC结构单片机，其内含硬件乘法器和16K的flash，支持ISP编程，运算速度比普通的单片机

7、要快的多，因此可以满足系统的需要。 2 迷宫问题描述 迷宫问题是图形学、图论和数据结构等领域中广为人知的一个经典问题，我们把迷宫简化成如右图2所示：图中1表示障碍物，0表示通路，机器人从入口处进入，从出口出来就算成功的走出迷宫。 3算法仿真试验 3.1算法描述如下： ：初始化，随机生成符合要求的m行n列的迷宫maze（m，n），通过调整迷宫数组中0和1的个数比调节迷 宫的可行通路数量，0越多，则迷宫的可行路径就越多，就越容 易找到出口。设定方向数组dir：规定搜索迷宫只能向上下左右四个方向搜索，对于正方形迷宫，设边长为1个单位，因此可以设定方向数组dir（4，2）=1 0;0 1;0 -1;-

8、1 0。行进经过结点记录数组jiedian（i，j）用来记录机器人探索过的每个结点，如果机器人走过结点（i，j），则jiedian（i，j）=1，否则为0。走过路径记录数组way用来记录机器人行走过程的可行路径信息。 ：机器人开始行走，从当前结点开始向三个方向搜索，如果没有障碍物（即该方向的迷宫壁为0）且不是终点并且没有走过（即jiedian（i，j）=0），则把该结点记录到jiedian中。 ：如果只有一个结点符合要求，则以该结点为起点继续过程，同时把该结点记录到way中，如果有两个或两个以上的结点，则从中随机选择一个结点为起点继续过程，并把该结点记录到way中。免费论文参考网。 ：如果三个

9、方向都有障碍物，则机器人进行回溯，退回上一个结点，选择排除已经探索方向的其它方向继续搜索，如果没有可通路径则继续回溯直到回到起点，转到，否则转到继续搜索直到找到终点，转。 ：给出没有可行路径信息。 ：输出可行路径。 3.2实验结果过程及结果： 为了验证算法的有效性，我们随机生成一个22*22规模的迷宫，应用深度优先算法进行迷宫路径搜索，其仿真结果如3图所示：图中o表示迷宫的0，表示迷宫中的1，左上角为迷宫的入口，右下角为迷宫的出口，深色部分表示算法找到的可行迷宫路径，从图3中可以看到：深度优先算法可以在迷宫中找到一条可行路径。 4 物理系统实现： 图 3 深度优先算法找到的路径示意图机器人路径

10、规划问题可以分为两种，一种是基于环境先验完全信息的全局路径规划，另一种是基于传感器信息的局部路径规划，后者环境是未知或者部分未知的。基于实际物理系统的特点，我们把该算法应用到我们研制的迷宫机器人上，在不影响算法正确性的情况下，我们采用图4所示的简化迷宫进行实验：带箭头的白线是机器人实际所走路线图，可以看到机器人从入口出发，按照带回溯的深度优先算法行走，经过一定的时间后能够顺利的找到出口，完成了在未知迷宫中的行走过程，实验证明了算法的有效性。 5结论： 迷宫问题是一个经典的遍历问题，求解算法很多，但对于实际的物理系统，考虑到其运算速度和内存大小的局限，运用深度优先算法进行迷宫路径的搜索是可行的，从仿真实验和物理实验都可以看出，深度优先算法是有效的。 参考文献： 1 SU S,Tsuchiya K. Learning of a maze using a genetic algorithmc. IndustrialElectronics, Control and Instrumentation 1993, Proceedings of the IECON