一种电脑鼠走迷宫算法的设计与实现

《一种电脑鼠走迷宫算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第27卷第12期计算机应用与软件Vol.27No．122010年12月ComputerApplicationsandSoftwareDec．2010一种电脑鼠走迷宫算法的设计与实现王凤林王宜怀(苏州大学计算机科学与技术学院江苏苏州215006)摘要电脑鼠是一个自主移动机器人系统。电脑鼠的任务是到达迷宫中心的目标区域。电脑鼠在不知道迷宫的布局情况下，必须自己找出到达目标的最优路径。整个过程是一种自主搜索的过程。研究和实现了基于位差值的搜索算法和基于等高图的最优路径算法，并作出改进提高机器人完成任务的

2、能力。关键词迷宫搜索算法电脑鼠机器人位差值等高图最优路径DESIGNINGANDIMPLEMENTINGAMAZESOLVINGALGORITHMFORMICROMOUSEWangFenglinWangYihuai(SchoolofComputerScienceandTechnology，SoochowUniversity，Suzhou215006，Jiangsu，China)AbstractMicromouseisactuallyanautonomousmobilerobot(AMR)．Them

3、icromousefindstheoptimalpathtogettothedestinationar-eawhichislocatedinthecenteroflabyrinthwithoutanyinformationofthelayout．Thewholeprocessisanautomaticsearchprocess．Inthispaperwestudiedandrealisedthepotentialvalue-basedpathsearchingalgorithmandcontour

4、map-basedoptimalpathalgorithm，andalsomadetheimprovementontheabilityofmicromouse’stasksaccomplishment．KeywordsMazesolvingalgorithmMicromouserobotPotentialvalueContourmapOptimalpath电脑鼠必须自成独立系统。电脑鼠的长和宽限定在25cm0引言×25cm。对电脑鼠的高度没有限制。1．2竞赛的规则所谓“电脑鼠”(micromous

5、e)，是使用嵌入式微控制器、传感电脑鼠的基本功能是从起点开始走到终点所花费的时间称器和机电运动部件构成的一种智能行走装置的俗称，它可以在为“运行时间”。电脑鼠从第一次激活到运行开始所花费的时“迷宫”中自动记忆和选择路径，寻找出口，最终达到所设的目间称为“迷宫时间”。电脑鼠在比赛时手动辅助的动作称为“碰［1，2］的地。［1－3］触”。电脑鼠搜索路径应该是在没有人工干预的情况下自主完成电脑鼠的得分通过计算每次运行的“排障时间”来衡量，即的，也就是说，需要运用搜索算法使电脑鼠自主行走。搜索算法将迷宫时间

6、加上一次运行时间的1/30。如果被碰触过，那再减的主要目的是，根据电脑鼠当前的位置确定下一步，以迅速到达去10秒，这样得到的就是排障时间。电脑鼠在迷宫中停留或运迷宫的中心并返回，同时利用搜索迷宫时得到的隔墙信息找出行的总时间不可超过15分钟，在限时内允许运行多次。从起点到终点并返回的最优路径。1．3电脑鼠走迷宫的流程描述1电脑鼠走迷宫的规则与流程电脑鼠上电后，首先进行探测和记忆，这次运行被称为“试跑”。在试跑时，需要按照一定的算法得到隔墙信息，并到达终点，即迷宫搜索算法;在搜索结束后根据搜索所获得

7、的隔墙信1．1迷宫、电脑鼠的规格息，按照最优路径算法确定最佳路径，并以最快的速度到达目的迷宫由256个方块(单元)组成，每个方块的大小为18厘米地，这次运行被称为“冲刺”。冲刺后还可以继续多次试跑和见方，排成16行×16列。迷宫的隔墙板沿方块的四周布设，形冲刺。成迷宫通道。如图1所示。2迷宫搜索算法当电脑鼠移动时，电脑鼠要知道自己所处的位置，因此首先需要定义电脑鼠的坐标和方向，然后设计基于位差值的搜索收稿日期:2009－04－05。王凤林，硕士生，主研领域:嵌入式系统图1全迷宫结构应用，网络技术。

8、第12期王凤林等:一种电脑鼠走迷宫算法的设计与实现271［4］算法。达某个格子后，该格子的count变量需要加1。该变量在搜索算2．1迷宫坐标和方向法中选择路径时要用到。当电脑鼠处于某个格子时，需要完成下面的操作:为了让电脑鼠记住所走过的各个迷宫格的信息，需要使用①检测是否到达过该格子。坐标对256个迷宫进行编号。②通过传感器计算该格子可走的方向。规定以电脑鼠放到起点时的方向为参照，此时电脑鼠的正③根据该格子可走的方向数，选择下一步走的方向。前方为Y轴正方向。迷宫格与坐标的对应关系