基于现实迷宫地形的电脑鼠设计.pdf

第 卷第 期大学物理实验.年 月 .收稿日期:基金项目:教育部高等学校电子信息类专业教学指导委员会教改项目()江苏省高等教育教改研究课题重点项目()南京邮电大学教育科学“十三五”规划重点课题()南京邮电大学大学生创新创业训练计划项目()通讯联系人文章编号:()基于现实迷宫地形的电脑鼠设计吴润强庹忠曜刘文杰项璟晨孙科学(.南京邮电大学 电子与光学工程学院、柔性电子(未来技术)学院江苏 南京.南京邮电大学 自动化学院、人工智能学院江苏 南京.南京邮电大学 通信与信息工程学院江苏 南京)摘要:针对现阶段电脑鼠计算量庞大且不适用于现实迷宫地形的问题设计出一款可在现实迷宫地形下自动寻找出口的电脑鼠 该电脑鼠基于超声波测距与传统迷宫算法原理适用于岔路数量与道路宽度不定、多死路弯道并且相对较大的迷宫地形具有适应性强、计算量小、兼容性和可塑性强等优点对于现实迷宫地形下的自动应用具有一定研究价值关键词:电脑鼠超声波测距迷宫算法自动应用中图分类号:.文献标志码:./.大学物理实验投稿网址:/.随着当今社会的进一步智能化智能小车这一领域得到巨大的发展但是其中对于智能小车走迷宫的研究却大多只是偏重电脑鼠的路径记忆与快速寻找出路的算法之中 此类电脑鼠往往需要先通过轨道循迹或障碍接触对可以行走的路径进行遍历不仅其中有关路径记忆的庞大数据占用了大量的 对较为复杂的功能增添带来困难而且其道路感知方式、车辆行驶方法和迷宫算法等通常仅适用于 比赛等道路笔直宽度一致、至多三分岔口并且整体较小的理想迷宫环境 面对岔路数量与道路宽度不定、多死路弯道并且相对较大的现实迷宫地形智能小车的功能应用大多都是通过手动控制其中对于现实迷宫地形的无记忆路径寻找更是处于一片相对空白的区域基于以上因素特设计出一款适用于现实迷宫环境的电脑鼠 该电脑鼠以超声波测距为基础对当前的道路状况与前方可转弯的路口可能进行判断保证电脑鼠始终保持在道路中间行驶并基于现有的电脑鼠智能算法进行改进提出三类较为可行的路径寻找算法并根据其适用情况进行比较分析 在保证其能成功在现实中的迷宫环境中找寻出路的前提下减少没必要的路径遍历与路径记忆步骤进而降低自身寻路运算占用 整体设计.设计思想在复杂的现实道路中阻碍电脑鼠前进的障碍物并非 比赛中呈直线平行分布的情况(见图)并且电脑鼠相邻两边的障碍物距离也可能随着电脑鼠的前进而不断变化具象化的现实道路(见图)图 理想的迷宫地形图图 实际的迷宫地形图为方便电脑鼠行驶可将弯曲且宽度不一的现实道路进行均匀微分(图)由于所分段后的路程长度相对实际情况下两边障碍物之间的距离较小故而可对所分得的每一路段近似认为障碍物呈现笔直排布 电脑鼠在每个微分路段上的中线上直线行驶则可完成弯曲道路上的正常行驶图 实际道路的合理化超声波探测可对探测头与现实生活中的障碍物之间的距离进行测量故而可以通过超声波测距测量电脑鼠距离周围障碍物的距离值判断其所处地形在所划分的每一个路段中保持道路中间行驶并判断该路段是否有交叉路口具体流程图如图 图 系统流程图基于所提出的三类迷宫算法此电脑鼠便可在迷宫地形的死路与多岔路口中做出相应选择从而寻得出口.结构设计本电脑鼠采用三轮式驱动由电机控制两前驱动进行前进与转向后万向轮无驱使动力仅由电脑鼠运动带动用以辅助电脑鼠进行转弯三轮式驱动结构如图 图 三轮式驱动结构由转向舵机与超声波测量模块共同组成测距结构其中超声波模块进行超声波的释放与接受从而计算电脑鼠与障碍物之间的距离值而转向舵机带动超声波进行转向从而得出电脑鼠与四周障碍物之间的距离值测距结构如图 所示图 测距结构.电路设计此电脑鼠对于自身寻路所占用的代码量与计算量较少故适用于市面上的多类开发板 目前智能小车常与物联网开发相结合故以基于此电脑鼠的后续物联网开发为例基于 开发板设计的电路图如图 所示电池组电源经过 芯片的电流稳压处理后分别对发光二极管、开发板等元器件进行供电其中发光二极管起指示灯作用若电路导通则二极管发光开发板通过 引脚与转向舵机的数据引脚相连控制转向舵机的旋转角度通过、引脚与超声波模块的 引脚与 引脚分 第 期吴润强等:基于现实迷宫地形的电脑鼠设计别相连根据传递的数据进行超声波测距经过 驱动芯片的数据处理对左右电机的转速、方向等进行控制从而完成电脑鼠的前进、转弯等功能图 电路图 超声波探测.测距与判断原理假设超声波的传播速度为 超声波探头的位置可近似代表电脑鼠所在的位置则根据超声波测距的原理可由超声波释放与接受的间隔时间 得到电脑鼠与障碍物之间的距离/.()为读取电脑鼠与周围障碍物的距离需测量多组 值而当同时使用多组超声波探头时彼此产生的余波可能会干扰距离的测量结果同时考虑到性价性与普适性等现实因素特采用转向舵机带动超声波探头测距在进行探测时以电脑鼠的前进方向作为基准线根据现实环境中可能存在的路口宽度以固定的旋转间隔角度 分别将舵机向左向、右旋转得到每一个角度所对应的障碍物到电脑鼠的距离进而根据其旋转角度计算其对应的横向距离与纵向距离距离计算方案如图 所示图 测距计算方案障碍物距离电脑鼠的横向距离为 与旋转角的正弦值之积纵向距离为 与旋转角的余弦值之积 同时当路口的宽度不小于相邻两个探测点的纵向距离之差时超声波即可探测到该路口内的障碍物情况此时可认为该路口在超声波的探测范围之内当舵机旋转角度 越小其可探测到的路口宽度越小测量也越精准 而当 过小时其计算的数据量较大复杂度较高当 过大时其精确大 学 物 理 实 验 年度较低可能漏过宽度较小的路口在实际情况下可转弯路口的实际宽度与当前所行驶的道路宽度可大致认为相差不大且所分段的道路长度对于二者而言相对较小故而可认为路口的道路宽度大于分段的道路长度则 取 是一个较为合理的值不妨以 作为旋转间隔角度进行研究将基准线的探测距离记为 在基准线上以 为间隔向左进行三次探测其探测距离记为 、在基准线上以 为间隔向右进行三次探测其探测距离记为 、则根据以上的研究有以下公式:()()().().中线距离求解基于前面对于实际道路的合理化在前方道路左侧无路口时应该近似相等同理当右侧无路口时应该近似相等对于近似相等的 与 即可求得电脑鼠距离左侧与右侧道路的平均值 与:()/()()/()将公式()、()带入公式()中有 ()/()/()将公式()、()带入公式()中有 ()/()/()基于公式()、()即可确定中线位置与电脑鼠位置从而实现中线判断与中线对齐功能.路口判断路口判断分为转弯路口判断与死路判断两部分超声波测距所得到的数据则为其判断依据超声波探测到小车前方道路出现路口时所得到的 与 中的某个或多个值会变得极大当 中出现不合理的极大值时可认为左侧有可通过的路口同理当 中出现不合理的极大值时可认为右侧有可通过的路口 此时便可根据迷宫算法执行转弯路口判断功能同时对于不合理的极大值进行去除将剩余的 与 带入公式()、()中仍可进行中线判断与中线对齐当一般当电脑鼠当前道路无障碍时可视为一个极大值故而当 与 均为合理值且与 相差不大时便可认为当前方向已经无路可走需要执行车辆掉头功能.路口判断为保证电脑鼠在每一微分段落均能对齐中线行驶并进行路口判断电脑鼠每达到一个微分段落便需要进行一次超声波探测电脑鼠在微分段落中以速度 进行匀速直线运动在超声波探测的间隔时间 里电脑鼠运动的距离恰好为微分段落的长度:.()电脑鼠的驱动源自电机对于驱动轮的带动而电机的驱动频率 与驱动轮周长 决定车辆的运动速度:()驱动轮周长可通过方便测量的驱动轮直径 进行求解:.()由公式()()解得超声波探测时间公式如下:()其中驱动轮直径 应为一个定值 的取值受 与 的比值成正比在电脑鼠的现实应用中可根据道路的弯曲复杂程度合理地取 的值并且通过公式()对电脑鼠的运动速率进一步优化 电脑鼠驱动.中线判断与中线对齐中线判断即根据超声波探测所得到的 与判断出道路的中心直线记此线为中线 基于超声波探头位于电脑鼠最中部并且可用于其近似代表电脑鼠位置的理论当超声波探头沿着中线前进时可认为电脑鼠沿着中线前进此时电脑鼠距离左右的障碍物均足够远可保证其在行驶过程中不会与障碍物相撞中线对齐即根据、与已知的两驱动轮间距 计算出相关数据判断出小车位于中线的左侧还是右侧 其中以小车位于中线右侧为例先保持左驱动轮不动右驱动轮向前行驶一定时间使车辆左进行偏转再保持右驱动轮不动驱动左驱动轮使车辆向右偏转相同角度从而使得车辆 第 期吴润强等:基于现实迷宫地形的电脑鼠设计中心恰好对齐中线位置如图 图 中线对齐示意图.理论分析中线对齐过程右驱动轮先从 点行驶到点然后左驱动轮从 点行驶到 点此时左右驱动轮与障碍物之间的距离、应处于一个合理值且恰好相等:()同时 距离左侧障碍物之间的距离 与 距离右侧障碍物之间的距离 也可求解:/()/()根据电脑鼠位于中线右侧的假设 则电脑鼠位于中线右侧先停止左电机转动使右电机工作 时间再同理停止右电机转动使左电机工作 时间最后使两电机保持额定功率正常运转若 则电脑鼠位于中线左侧先停止右电机转动使左电机工作 时间再同理停止左电机转动使右电机工作 时间最后使两电机保持额定功率正常运转若 则电脑鼠正好处于中线两电机功率保持一致正常运转即可.转弯判断与车辆转向转弯判断与车辆转向均是基于超声波探测与迷宫算法下进行完成的其具体流程图如图 所示图 转弯判断流程图根据超声波测量的路口情况进行迷宫算法判断若并不需要转弯则保持正常行驶反之则将舵机转向需要转弯的方向通过不断地超声波测距根据是否有极大值的出现判断其是否到达路口以图 的情况为例电脑鼠前往右侧的路口则将转向舵机向右旋转 同时车辆保持匀速前进在前进的过程中不断进行超声波测距而当车辆行驶至图中路口时其测量的数据便存在了极大值 此时小车停止运动对路口再次进行超声波测量根据路口判断原理分析该路口是否为死路为死路则将舵机转回前进方向正常行驶不为死路则停止右电机转动单独工作左电机 时间使小车向右旋转 进入新路口行驶根据此时情况将 公式()计算可得:.()对于大多数迷宫而言车辆转向所需要的时间为一个定值大 学 物 理 实 验 年.车辆掉头在智能小车的避障研究中若前方道路为死路则直接向后行驶或以一个轮胎为圆点旋转 进行掉头 这不仅不适用我们的设计方案同时面对狭窄的现实道路时也可能会出现车辆的掉头而导致车辆与障碍物相碰如图 所示图 掉头碰撞示意图为使电脑鼠可以在道路宽度小于 的狭窄情况进行掉头基于上述的中线对齐、车辆转向理论与公式()对掉头驱动进行改进其运动情况如图 图 车辆掉头示意图当电脑鼠所前进的方向 为死路时可先使其以 为圆心关闭左电机单独工作右电机 时间驱动右车轮从 到达 同理以 为圆心关闭右电机单独工作左电机 时间驱动左车轮从 到达 此时的前进方向便从方向 改为了方向 且电脑鼠在转向过程中不会与障碍物发生碰撞完成转向后依然对齐中线行驶在保证安全行驶的同时节省了二次中线对齐的时间损耗 迷宫算法.随机算法在现实环境下的寻路过程与目前电脑鼠所研究的迷宫遍历大致相同但在实际生活中知晓迷宫地形的大致分布与全地形探索迷宫不太现实故而向心算法等常用的算法不具备太多的普适性但是在所能前进的方向里随机选择一个方向前行的随机算法对于现实生活中的绝大多数迷宫地形仍然适用 假设当电脑鼠从入口进入迷宫地形之后在入口摆上障碍物使得电脑鼠无法从入口出来那么从理论上而言电脑鼠终将在不断地尝试中到达迷宫终点优点:普适性强几乎适应一切迷宫地形缺点:时间耗费较大且有可能从入口驶出出于以上优缺点的考虑该算法比较适用于地下溶洞、动物洞穴等未知地形的迷宫环境在不偏重其进出迷宫的时间间隔的前提下携带附加设备对迷宫内环境进行研究.偏好算法此算法基于优先向前法则、左手法则和右手法则的基础上进行总结与修改:当电脑鼠前进道路中出现多方向优先向前法优先选择直行然后考虑向左或向右行驶而左(右)手法则优先选择向左(右)转其次是向前行驶最后向右(左)行驶原三种算法仅针对当前道路中最多只存在三个可行的方向并且其左右路口的方向又过于理想 在现实中的路口可能呈非理想状态的树状分布如图 此时的原有算法便存在一定的局限性图 树状分布道路故根据现实情况改善优先向前法则为直行偏 第 期吴润强等:基于现实迷宫地形的电脑鼠设计好算法改善左手法则与右手法则为两端偏好算法.直行偏好算法基于该算法理论当小车前进方向无障碍物时则不考虑其如今行驶道路两边的可行路口一直保证直行状态当 并非极大值时则分别对小车左右两边的障碍物进行超声波测距:若 与 均为合理值则可认为当前所处道路为死路执行掉头功能若在 于 的测量中仅出现一个极大值则仅有该方向存在可转向路口对其方向执行转弯功能若在测量中出现多个极大值且极大值之间相差较大则可认为测量值最大的方向为出口的可能性最大向该方向执行转弯功能出于之前对于实际应用情况的假设我们无须进行迷宫地形的遍历同时对已经行走的路程并无记忆储存在执行该算法时会不可避免地重复之前的路程而陷入的“”型死锁之中如图 图 “”型死锁图当电脑鼠沿直线到达点 时前方的障碍物阻碍电脑鼠继续前进故根据左右两边探测距离前往距离较远的 点 到达 点后因为死路情况而掉头经过 点到达 点同理因为 点的死锁情况掉头之后使得电脑鼠在 点与 点进行往复运动造成死锁情况优点:算法简便时间耗费较小缺点:存在“”型死锁而迷宫有较大的可能存在该“”型结构故而直行偏好算法的适用度较低仅可用于无“”型结构的迷宫地形.两端偏好算法首先确定一个偏好方向(左或右本文以左进行举例)根据超声波探测判断前方可前行道路的数量若探测到的数据均为合理值则前方无可前行的道路此时执行掉头功能若探测的数据仅存在一个极大值则前方仅有一个可前行的道路向该方向进行转弯功能若探测的数据存在多个极大值则前方道路树状分布多个可前行的道路此时其测量的数据编号选择最靠近左边的道路进行转弯前行根据此算法可在大部分现实迷宫地形中较为快速地到达终点但对于特殊迷宫其出口位于迷宫中央则电脑鼠便有可能从入口驶出和始终找不到出口如图 所示图 特殊迷宫地图电脑鼠从入口 处进入根据偏好方向向左前行到 点再根据仅存的前进方向前进到 点同理电脑鼠向 方向前进路过出口 点时由于出口方向相对在右不符合偏好方向而继续前往 点之后电脑鼠经过 点再次到达入口 点根据偏好向左的算法其会从 点驶出 若假设当电脑鼠进入迷宫后将入口堵住则电脑鼠会在 四点进行反复循环而不会从 点离开迷宫优点:适用于大部分迷宫地形逻辑清晰且时间耗费较少缺点:对于出口位于迷宫中间的特殊迷宫地形不太适用该算法适用于现实生活中出口不位于迷宫中间的迷宫地形可用于现实中树状分布乃至于网状分布的迷宫地形进行出口寻找.沿壁算法该算法是在两端偏好的算法上进行的进一步修改同两端偏好算法确定偏好方向根据超声波探测与中线对齐原理始终与左侧的障碍物保持一定的距离 此时我们可以将电脑鼠视为沿着左侧的障碍物行驶根据左手法则可同两端偏好算法般从出口驶出沿壁算法与两端偏好算法相比有优缺点如下优点:只需考虑沿壁一侧的距离把控减少了大 学 物 理 实 验 年舵机旋转测距与多路口判断等工作量缺点:无法保证车辆居中行驶车辆可能会因距离的把控不当而与另一侧的障碍物相互碰撞在迷宫地形各分叉道路宽度相差不大时可使用沿壁算法缩短车辆的行驶时间而当迷宫中存在个别较为狭窄的道路时可选择两端偏好算法保证车辆的安全行驶 结 语该电脑鼠通过超声波测距收集路况信息判断微分道路中线位置与前方路况保证居中安全行驶的同时根据迷宫算法进行路口转弯 其设计方案与算法思想均只涉及简单的临时数据处理运算量小、兼容性与可塑性强适用于岔路、死路数目不定、分布不均道路弯曲且宽度不定的多类现实迷宫地形可为该地形下的自动应用提供一定研究基础参考文献:赵欣哲杨培培刘文凯.超声波小车自动测距变速系统.大学物理实验():刘伟童慧芬郑森伟等.基于激光探测的智能小车系统设计.大学物理实验():.李伟管鱼龙谢浩等.基于微分变换法的变截面梁振动研究及有限元数值模拟.大学物理实验():.李劲松.超声波传感实验教学设计研究.大学物理实验():.陈水桥方文萱李宝学等.基于 平台的数字化差动光通量法测量带材微位移的设计与实现.大学物理实验():.薛啸天宋文韬崔淦维等.超声波声速测量实验的拓展.大学物理实验():.赵欣哲杨培培刘文凯.超声波小车自动测距变速系统.大学物理实验():.梁金泽程琳.基于红外线传感器的智能测距圆规的设计开发.大学物理实验():.王辉廖峰林.智能小车循迹与避障的仿真与实现.成都 大 学 学 报(自 然 科 学 版)():.贺少波孙克辉.基于向心法则的电脑鼠走迷宫算法设计与优化.计算机系统应用():.侯爽.基于环格模型的电脑鼠走迷宫算法研究与实现.北京:北京工业大学.李玉祺.不确定条件下的城市道路交通网络设计与交通需求管理研究.武汉:中国地质大学.王康吴文明刘利刚.三维迷宫的设计与建模.浙江大学学报(理学版)():.王俊莹.山地城市道路交通网络韧性研究 .重庆:重庆交通大学.(.().):.:第 期吴润强等:基于现实迷宫地形的电脑鼠设计