数事热术与点
算法分析
机器人走迷宫问题的算法设计与模拟实现
郝慎学
(山东英才学院山东济南250104)
摘要：文中实现了机器人走速宫问题的计算机模拟，给出了网格状速宫的合理数据结构表示，并给出了机器人走速宫过程中行进方向的探测方法，设计了合理的数据结构及算法记录机器人行走的露径，给出了机器人图溯算法和行进控制算法，文中并实现了根据机器人探测得到的建宫情况计算得到从起点到终点的最短路径，最终模拟实现机器人在速宫范围内自主寻导找从起点到终点的最超路径，
关键调：机器人速宫问题四潮方向探测
中图分类号：TP301.6
文献标识码：A
文章编号：1007-9416(2011)10-0113-02
Algorithm Designing and Simulation for
MazeRealizedbyRobot
Hao Shenxue
(ShanDong Yingcai University Jinan 250104)
Abstract:The maze realized hy robot is simulation in program. The data structure is described in this paper, and the direction detected method is ako described. The path that rohot through hy is saved, the lhack tracing algorithm and the move up control method are illuminated in this paper. The path from start=point to endpoint is fotind, the shortest path in the detected grids by robot is aso can be found.
Key words:robot maze hack tracing direction detected
1、引言
随着机器人技术的发展，智能移动机器人在未知环境内、自主探测、动态决策与规划行进路径的研究成为--个重要分支。机器人走速宫是在没有外界干预情况下，通过机器人自带传感器探测速宫环境，进而决定行进路线，从而实现从递宫起点到终点的导路过程。机器人走递宫也是机器人比赛的常设项目之一。本文旨在利用计算机编程模拟实现机器人走递宫问题，给出机器人走递宫算法设计思路和实现过程，并通过合理数据结构和算法的设计提高机器人迷宫导路效率。
迷宫问题是数据结构中的-一个经典问题，通常有广度优先探测法和深度优先探测法，可利用栈和队列实现求解过程。机器人走迷宫问题中首先需要解决机器人功能设计，本文假定机器人已具备前进、左侧转向90度，探测前方障碍物，以及探测机器人所在网格是否改变等功能。本文主要描述机器人自主导路算法过程及相关数据结构设计。
2、数据结构设计
Public Type GridType
1向
4尚
3 图1
2尚
ID As Integer i .jAs Integer
ajdGrid (1 To 4) As Integer Visited As Boolean
Dstate (1 To 4) As Integer
Ddelected (1 To 4) As Booiean End Type
图2
我们将迷宫抽象成·-个n×n的网格，并对每个网格从左到右，每个两格具有4个方向，分别定义为1方向，2方向.3方间，4方向，如图1所示。并规定机器人行进过程中不停探测前方是否有障碍物，同时探测时按左侧规则，进人新网格后优先探测当前方向的左侧方向。探测过程中记录每个网格的四个方向上的状态：通路、不通或未
知，分别用1、0、一1表示，探测得到不同状态后记人当前网格的四个方尚上的状态数组Dstate(1to4)。同时利用网格的Ddetected(1to4) 数组记录当前网格的四个方向是否已被探测过。若某网格四个方向全部探测过则利用Visited标志位表示该网格已访间。为了寻找到从起点到终点的最佳路径，我们利用网格的ajdGrid(1To4)数组记录当前网格在1、2、3、4四个方向上的邻接网格序号，由此最后可在机器人已探测过的网格中利用Dijkstra算法找到最佳路径，并为计算方使由1，记录网格所在速宫中行号、列号。类型定义如图2所示。并机器人探索过程中设置一个回溯网格栈记录机器人经过的递宫网格序号及方向，此方向是从一个遂宫网格到下一个递宫网格经过的方向。设置一个方间队列记录机器人在某网格内探测方向的顺序。设置一个回潮路径数组记录需要回溯时从回溯起点到回潮终点的述
宫网格序号及方向。 3、算法设计
本文主要描述机器人走述宫问题的算法过程，假定机器人已具备相关行进，探测，转向以及相关数据设置功能。机器人开始寻路之前需预设递网格宽度W，迷宫网格行列数。假设机器人所在迷宫起点网格行号列号为starti和startj。
3.1网格序号计算方法
根据机器人年某方向工的前进距离网格宽度W以及起点网格的行号和列号可计算得到新宫网格的行列号和。计算方法如
1方向.上前进w距离then
i=starti-!
2方向.上前进w距离then
j = startj +1
If3方向上前进w距离then
i = starti +1
f4方向上前进w路离then
j= startj-1
3.2机器人自主寻路算法
假设机器人所在速宫起点网格序号为StartGridID，并假设机器人初始前进方向为D方向，并引入回溯标志BacktrackingFlag，初值为False。算法描述过程如下：
Step1：机器人在D方向上前进。
Step2：检测机器人所在迷宫网格是否为终点网格，若是则算法
113