导 师: 王洪君
学科专业: G11
授予学位: 硕士
作 者: ;
机构地区: 山东大学
摘 要: 随着计算机技术的不断发展,人工智能研究的不断深入,智能机器人的研究工作越来越受到人们的重视。作为智能机器人研究领域的热点,电脑鼠(英文名称为Micro-mouse)实际上是一个由微处理器控制的、集传感与控制于一体的、能够自动穿越迷宫的微型智能移动机器人,它可以在“迷官”中自动记忆和选择路径,寻找出口,最终达到所设定的目的地。电脑鼠融合了机械设计与制造,电机技术及应用、传感与测量技术、电子工程、控制理论、程序设计和人工智能等多方面的专业知识,具有多学科知识融合的特点。因此,电脑鼠对于上述学科的融合、发展和创新具有重要意义。本课题是以上述情况为背景,深入研究了机器人路径规划的相关内容,包括地图已知的路径规划方法,例如:可视图法、自由空间法、拓扑法、栅格法、神经网络法等;以及地图未知的路径规划方法,例如:人工势场法、最优控制法、遗传算法等。木课题根据IEEE电脑鼠竞赛相关规则,并结合机器人路径规划的相关理论,将电脑鼠走迷宫划分为迷宫搜索、迷宫返回和迷宫冲刺三个阶段,并分别进行了详细研究:在迷宫冲刺阶段,本课题重点分析了常用的机器人路径规划方法——A*算法和Flood-Fill算法;在迷宫搜索阶段,本课题提出了基于概率距离的迷宫搜索算法,通过生成静态概率距离图、动态处理所得的迷宫图等步骤,实现了对迷宫的高效搜索,改变了目前常用搜索算法缺乏理论依据的现状;在迷宫返回阶段,本课题提出了基于分区Flood-Fill算法的迷宫返回算法,通过生成分区Flood图,帮助电脑鼠寻找更好的返回路径,以获取更多的迷宫信息。最后,本课题搭建了一套测试平台,将文中提出的算法运用到实际的电脑鼠中,并对算法进行了测试。综上,本课题实现了关于IEEE标准电脑鼠走迷宫的相关算法的设计与实现,并验证了其可行性。
关 键 词: 电脑鼠 迷宫 概率距离算法 分区 算法 路径规划
分 类 号: [TP301.6;TP242.6]
领 域: [自动化与计算机技术] [自动化与计算机技术]