芜湖职业技术学院学报2007年第9卷第2期
机器鼠走迷宫的优化路径算法及实践
邓延安
(芜湖职业技术学院电气系,安徽芜湖,241001)
迷宫问题是计算机数据结构和计算方法经常
涉及的问题,目前最常见的方法有广探法和深探
法 。’
机器鼠走迷宫是机器人比赛的常设项目之一,
要求机器鼠用最短的时间走出迷宫或者用最短路
径走出迷宫。我们提出的用PIcl6F877单片机制作
的机器鼠实现走迷宫的优化路径的一种方案,非常
适合高校进行机器人制作和竞赛 。
1.问题的提出
1.1迷宫的一般形式
迷宫的一般形式有两类,一类是迷宫挡板与外
框都是互联的,即为树形结构,如果把外框作为树
干,那么内部的挡板就是树叉。另一类的迷宫除了与外框互联的挡板外,还有与外框隔离的挡板,也就是说迷宫内部有网孔 。对前一类我们称为树形迷宫,后一类称为网孔形迷宫,显然网孔型迷宫要复杂得多 。图I就是一个树形迷宫 。
1.2迷宫问题
对于树型迷宫,在从入口到出口的路径中,有很多通向死胡同的岔路,只要设计出处理死胡同的方法,就可顺利找出出口 。面对于网孔型迷宫,除了死胡同外,还有可能在迷宫中转圈而无法走出谜宫,因此还要设计出处理网孔的方法。本文主要针对树型迷宫的路径进行讨论 。
对于一个迷宫来说,可能的路径一般不止一条,如何找到最优路径,也是迷宫问题的一个难点 。我们总是希望机器鼠在经过几次试探后能够找出最短的路径。
2.算法设计
无论是树型迷宫还是网孔型迷宫,要找到一条路径并不难 。如果采用“顺墙摸”的办法,肯定可以走出迷宫,但不一定是最短路径 。要找到最短路径,还应进行合理设计。
图1树型迷宫示倒
37
本文采用坐标描述迷宫的位置,如果向右(或左)越过虚线,则x加l(或减1),向上(或下)越过虚线,则y加I(或减I)。为简化问题的分析,假设机器人只能走直线。
2.1死胡同的处理
首先判断哪条路径是死胡同 。当采用顺墙摸时,如果判断出前后两次经过了同一坐标点,那么可以肯定,这两个坐标点之间的路径~定是死胡同路径,该坐标点就是死胡同的入口,第二次行走时,不应再进入,可将这个入口视为有挡板 。图l中的粗虚线示意将死胡同堵死 。
2.2完成“左顺墙”和‘‘右顺墙”
机器人可以通过“左顺墙”和“右顺墙”的办法找到两条路径,显然这两条路径长度是不同的 。图1中的实线箭头表示“左顺墙”的路径,虚线箭头表示“右顺墙”的路径 。
2.3选择最短路径
从图中可见,无论是“左顺墙”还是“右顺墙”,都不是晟短路径,因为通过交替进行“左顺墙”和“右顺墙”还可以找到更短的路径 。如图l中,先“右顺
邓延安:机器鼠走迷宫的优化路径算法投实践
墙”到A,然后“左顺墙”到B,再“右顺墙”通过c走出迷宫 。
3.硬件实现
对于一个不太复杂的迷宫,可以通过单片机完饯硬件电路 。本次设计使用Microchip公司的PIcl6F877A实现。利用该芯片自带的EEPRoM完成对路径的位置的记录和处理
3.1迷宫位置和路径长度的记录
记录并存储迷宫位置和路径长度所需的字长视迷宫的复杂程度而定。对于象图1这样不太复杂的迷宫,用2个字节即可,其中一个字节存储坐标信息(x和Y各用4bit>,另一个字节存储长度信息(6bit)和方向信息(2bit) 。这里,规定方向位为:‘∞’:上;‘‘ol”:右;“11”:下:“l o’’:左 。
为便于记录,约定可以在场地上的每个方格作标记供检测,这与迷宫问题并不矛盾。由于标记线的颜色与场地的颜色不同,可采用红外器件进行检测。通过判断机器鼠行走的方位记录坐标,通过检测标记线记录长度 。
3.2方向信息的处理
根据当前机器鼠的行进方向和碰到档板的情况来进行坐标的记录。如进行“左顺墙”时.当前为向上前进,则碰到档板后应向右前进,方向位应由‘伽”变成‘‘ol”。以此类推,如果碰到档板方向位的变化应是:
厂——————]
∞——+0l——'ll——◆lO
如果走到档板的尽头再折返,则方向位的变化
为;
00己1l o声lo
313剔除死胡同
在先后完成‘‘左顺墙”和“右顺墙”后,根据记录的坐标建立一个线性表 。比较该线性表中各坐标的值,如发现有相同的坐标值,则可以肯定这两个相同的坐标之间的路径是死胡同,从线性表中剔除 。此时就得到了“左顺墙”和“右顺墙”的最短路径。
3.4最短路径的确定
通过图l可见,在进行“左顺墙’啊孙右顺墙”时,有些坐标是共同的,如A点和B点,此时进一步比较这些相同的坐标之间,在‘‘左顺墙”和“右顺墙”两种情况下的长度,选择较短的那一条进而确定是“左顺墙”还是“右顺墙”。
3.5程序流程圈
图2是“左(或右)顺墙算法流程图,图3是路径优化流程图 。
4.结束语
对于不太复杂的树型迷宫。如一个16x16迷宫,PICl6F877单片机可以胜任 。但对于复杂的迷宫,由于存储空间要求较大,需外接E2PROM。如果是网络型迷宫,则算法更为复杂,尚有待进一步研究 。
图2 。(左(或右)顺墙)算法流程图
|莞湖职业技术学院学报2007年第9卷第2期
图3.路径优化流程图
参考文献
文稿责编张学亮
【1】周航慈.单片机程序设计基础.北京:航空航天大学出版社,2003
【2】李学海.PIc单片机实用教程——嵌高篇.北京:航空航天大学出版社,2002
摘要:提出了对树型迷宫的优化路径算法,用坐标法解决了“死胡同”的处理和最短路径的判断与选择问
题,用PIcl6F877单片机完成电路的设计与制作。关键词:迷宫问题:路径优化;PIc单片机 。中图分类号:TP368.1
文献标识码:A
文章编号:1009・1114(2007)02-0037.03
Theop恤nizedAI印rnhmofLabyrin协R嗡IizedbyRobot DENGlhn.曩n
Ah打act:An opt.皿ized algoritI埘0f 1’ree-ly】pe labymIm is pres朗ted,tl他problem of‘‘blind
alleys”柚d
the
judgemem柚d choice
ofthe shonest path am solved
by
thc
coordjn眦m劬od.The
circuit
desi星皿ing柚d
maI【i119
is∞hieved bv廿”PICl6F877.
Key删rd:aIgoritIlln probl锄;pa血optimizillg;Plc
Mcu.
收稿日期:2007.01.17
作者简介:邓延安,1967年出生,舍肥工业大学2005届工学硕士,副教授,工程师.安徽省教育厅立项课题.项目号:2003lu328zc
机器鼠走迷宫的优化路径算法及实践
作者:邓延安, DENG Yan-an
作者单位:芜湖职业技术学院电气系,安徽,芜湖,241001
刊名:
芜湖职业技术学院学报
英文刊名:JOURNAL OF WUHU VOCATIONAL INSTITUTE OF TECHNOLOGY
年,卷(期):2007,9(2)
被引用次数:0次
参考文献(2条)
1.周航慈单片机程序设计基础 2003
2.李学海PIC单片机实用教程--提高篇 2002
相似文献(2条)
1.期刊论文陈永刚.李敏.范庆辉.CHEN Yong-Gang.LI Min.FAN Qing-Hui用粒子群算法求解迷宫问题-河南科技大学学报(自然科学版)2010,31(2)
针对传统算法求解迷宫问题存在效率较低的问题,提出了用粒子群算法求解迷宫问题的方法.重新设计了粒子的编码和定义了粒子的适应度值,成功实现了问题到算法的建模.针对不同类型的迷宫问题进行了实验,结果表明:算法具有较好的性能和效率.
2.期刊论文徐守江迷宫问题的路径优化-电脑知识与技术2009,5(32)
迷宫问题是图形学 、图论和数据结构等领域中的一个经典问题.目前解决迷宫问题的算法主要包括传统算法以及智能算法两大类.如何更好的解决迷宫问题获得最优路径一直是有待解决的问题.首先基于蚁群算法获得导航路径,然后利用粒子群算法优化导航路径获得近似最优化路径.实验仿真表明,利用粒子群算法优化后的路径效果十分令人满意.
本文链接:http://d.g.wanfangdata.com.cn/Periodical_wuhzyjsxyxb200702012.aspx
授权使用:杭州电子科技大学(hzdzkj),授权号:cb9be163-5c4a-4d99-bb83-9e410114faa8
下载时间:2010年12月3日
。
