密宫机器人算法研究及其实现.doc

目  录
摘 要 I
关键词 I
Abstract I
Key words II
1  前言 1
1.1  机器人的历史 1
1.2  密宫机器人的研究背景 2
1.3  密宫机器人的设计思路 3
2 密宫研究 4
2.1  密宫设计的矩阵表示 4
2.2  密宫设计的拓扑研究 7
2.3  密宫模型探究 9
3  算法研究 10
3.1 搜索算法概览 10
3.1.1  广度优先搜索 11
3.1.2  深度优先搜索 12
3.2  路径优化算法 14
3.2.1  Dijkstra算法 14
3.2.2  A*搜寻算法 15
3.2.3  遗传算法 16
3.2.4  蚁群算法 18
3.3  小车处于密宫环境下的分析 20
3.3.1  靠右算法和靠左算法 20
3.3.2  直线优先算法 24
3.3.3  带记忆功能的算法 24
3.3.4  结合坐标定位的算法 25
4  密宫机器人的硬件实现 26
4.1  密宫机器人的机械结构 27
4.1.1  行走方式分析 27
4.1.2  动力系统选择 28
4.1.3  防撞论证 30
4.2  密宫机器人的电路实现 33
4.2.1  系统主控部分 34
4.2.2  电机驱动 36
4.2.3  障碍物状态识别装置 38
4.3  实物照片及效果展示 41
4.3.1  各角度实物照片 41
4.3.2  机器人行进图 42
5  密宫机器人的程序流程图 46
5.1  主流程图 46
5.2  子程序流程图 48
5.2.1  电机控制流程图 48
5.2.2  路径纠正流程图 49
6.  系统调试 50
7.  总结 51
参考文献 53
致  谢 54
附录 55
附录A  控制程序 55

密宫机器人算法研究及其实现

摘 要
　　　本文重点描述机器人在自动穿越密宫时遇到的算法问题，并对算法在实践中的应用进行论证，强调了机器人在行动过程中判别的自动化、智能化过程。算法的论证是基于密宫图形的拓扑学描述，而机器人相应的行动规则则基于密宫的矩阵分析。本文还就机器人的机械结构和电路设计方案进行阐述，对机器人在密宫中掉头转弯等动作可能出现的碰到墙壁的状况进行了分析并提出相应解决办法，通过制作基于单片机的轮式机器人并使用靠右算法实现了机器人在密宫中的探索。

关键词
　　　密宫；拓扑；算法；人工智能 ;机器人

Algorithm and Its Implementation of The Maze Robot

Abstract
　　　The design based on the analysis of maze algorithms and development, design and manufacture of robot, this thesis realizes the hardware design and software design of wheeled robot based on MCU. This text discusses how to transform the question of the maze into a question pursued, and how to utilize the algorithm pursued to solve the problem of the maze. Maze problem is a classical problem in graphtheory and other fields, the paper described the feasibility of themode is proved by mathematical modeling and qualitative analysis.This paper is about maze the matrix analysis, and the topological description of maze. The article also gave the solution when robot arrond the corner of  the robot's mechanical structure and circuit design on the status of the robot.

Key words
 Maze ; Topology ; Algorithm ;Artificial Intelligence;Robot