基于网格的电脑鼠迷宫路径搜索和障碍规避算法研究

摘要

电脑鼠作为具有较强计算和控制功能、能够自动完成迷宫穿越的自主式移动机器人，融合了机械电子、自动控制、软件工程和人工智能等多学科领域的知识，具有交叉学科融合的特点。依照国际电脑鼠比赛的规则，电脑鼠需要在迷宫中，应用自身的能力对周边环境进行探查，自主判断、选择相应的动作（前进、转弯等），以及对迷宫信息进行记忆和分析，作出路径选择，寻找可行路径并最终达到初始设定的目的地，实现预期的功能。这对于人工智能、自动控制等领域的研究具有非常重要的意义。
　　 本文的研究内容主要有以下三个方面:
　　 1)从控制策略层面对电脑鼠迷宫行走所应用的技术进行了研究。电脑鼠的行走速度控制中加减速资料表的建立;传感器的距离测量原理以及传感器资料的收集存储;电脑鼠前进中转弯的弯道控制方法。
　　 2)对电脑鼠在迷宫中行走进行了路径规划和障碍规避的研究，包括算法设计及实现。
　　 3)通过四个实验对本文提出的算法进行了分析验证，前三个实验结果以及分析表明，本文提出的迷宫遍历算法的设计是有效的，该算法能够在给定的迷宫中找到最佳的解决方案。第四个实验表明该算法对某一个特定的情况也有可能找不到解决方案。下一步工作的重点我们将围绕这个问题进行展开。在性能分析部分，通过实验得到的数据表明该算法在遍历的时间和单元格的数量上有一定的优势。

目录

声明

摘要

第1章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．3 本论文的主要研究内容

1．4 论文研究内容安排

1．5 本章小结

第2章 电脑鼠硬件设计

2．1 电脑鼠的外形设计

2．2 电源的选择

2．3 障碍检测原理和检测方法选择

2．3．1 检测原理及方案的比较与选择

2．3．2 传感器检测电路

2．4 人机交互界面电路设计

2．5 电脑鼠控制器设计

2．5．1 LPC2138最小系统设计

2．5．2 JTAG接口电路

2．5．3 复位电路

2．5．4 最小系统及各引脚分配

2．6 本章小结

第3章 电脑鼠的实时控制与驱动研究

3．1 电脑鼠实时速度控制

3．2 电脑鼠走直线控制

3．2．1 电脑鼠的位置修正

3．2．2 电脑鼠迷宫中距离检测原理

3．2．3 传感器控制信号存储设计

3．3 电脑鼠弯道控制

3．4 电脑鼠电机驱动与控制设计与实现

3．4．1 电机的比较与方案选择

3．4．2 电机驱动的比较与选择

3．4．3 步进电机的控制策略与选择

3．5 本章小结

第4章 路径规划策略和障碍规避算法

4．1 算法简介

4．2 关键词

4．3 路径规划和障碍避免实现

4．3．1 导航

4．3．2 障碍数据库的建立

4．3．3 中间目标形成

4．3．4 黑名单和回溯

4．3．5 障碍规避策略

4．4 算法设计

4．4．1 主算法设计

4．4．2 路径规划程序设计

4．4．3 X方向的路径规划设计

4．4．4 Y方向的路径规划设计

4．4．5 障碍规避程序设计

4．4．6 中间目标的形成

4．4．7 回溯算法设计

4．5 本章小结

第5章 实验结果和性能分析

5．1 右手策略失效时采用较低优先级左手策略求解实验

5．2 左手策略具有更优解时右手策略路径求解实验

5．3 迷宫遍历求解实验

5．4 基于黑名单的回溯无解实验

5．5 性能比较分析

5．6 本章小结

总结和展望

参考文献

附录A 攻读学位期间所发表的学术论文目录

致谢