摘 要

本文以综合比赛项目——机器人游中国为背景对循迹小车的路径规划问题进行设计。在比赛所给的地图的基础上，分析了地图的建模方法，运用拓扑法建立地图的模型，以简化路径规划问题，提高规划效率，并在MATLAB平台上进行仿真。此外，采用Dijkstra算法搜索地图上两点之间的最短路径，同时设计循迹小车路径规划算法。最后，开发循迹小车控制程序，控制小车按照规划好的路径完成比赛。

关键词：循迹小车；竞赛；拓扑地图；路径规划

Abstract

This paper designs the path planning problem of the tracing car with the background of the comprehensive competition project - robot tour China. On the basis of the map given by the competition, the modeling method of the map is analyzed, and the model of the map is established by using the topology method to simplify the path planning problem, improve the planning efficiency and simulate the MATLAB platform. In addition, the Dijkstra algorithm is used to search the shortest path between two points on the map, and the path planning algorithm is designed. Finally, the development of tracking car control procedures, control the car in accordance with the planned path to complete the game.

Key Words：Tracking car; competition; topology map; path planning

目 录

第1章 绪论 6

第1章 绪论 6

1.1 研究的背景和意义 6

1.2 路径规划国内外研究现状 6

1.2.1 全局路径规划 6

1.2.2 局部路径规划 7

1.3 论文的研究内容和结构 7

第2章 规划地图的拓扑建模 9

2.1 可视图法 9

2.1.1 可视图法原理 9

2.1.2 可视图法缺陷 9

2.2 拓扑法地图建模 9

2.2.1 拓扑法地图建模的原理 9

2.2.2地图特征分析 10

2.2.3 拓扑法地图建模的实施过程 10

2.2.4 拓扑法地图建模实验 14

第3章 机器人游中国的路径规划方法 16

3.1 比赛规则分析 16

3.2 路径规划问题分析 16

3.2 路径规划算法 17

3.2.1 算法基本思路 17

3.2.2 景点路径代价表的制订 17

3.2.3 小车路径规划算法步骤 20

第4章 循迹小车控制程序设计 21

4.1 循迹小车简介 21

4.2 小车循线算法 22

4.3 小车转弯策略 23

4.4 小车路径规划控制程序设计 23

4.5 小车路径规划控制程序实验 25

第5章 总结与展望 26

参考文献 27

致谢 28

第1章 绪论

1.1 研究的背景和意义

最初在研究移动机器人避障控制就开始了路径规划问题的研究。经过多年研究发展和技术积累，路径规划技术日趋成熟，同时路径规划技术的应用领域也越来越多，路径规划技术也逐步延伸到其他领域中。

路径规划技术应用领域十分广泛，如扫地机器人的规划清扫、无人机的自主驾驶、汽车导航、虚拟装配、智能交通、物流运输等领域都和路径规划密不可分。随着路径规划技术的研究与发展，路径规划技术在日常生活及生产中愈发起到不可或缺的作用。

在路径规划推动社会发展的同时，人们对路径规划的关注度也日趋上升。许多关于路径规划的比赛相继举办。机器人游中国是中国教育机器人大赛设立的趣味比赛项目之一，其主题就是规划循迹小车的行走路径，减少其完成比赛的时间。

在这个科技日新月异、竞争日益激烈的社会中，很多时候需要最优路线、最短时间来获得最高效益。如车辆路径问题，从某个地点出发，途中经过某些地点，最后到达终点，从众多路线中寻找出一条最优的路线能够节省大量时间，减少成本，提高效益。

1.2 路径规划国内外研究现状

路径规划就是在一个存在诸多限制的有界空间内，满足限定条件情况下，从环境中寻找一条从起点到目标终点的最优或次优的路线方案。目前路径规划主要集中在机器人在初始位置和目标位置两点之间的最优路径搜索，而对于多目标点的路径规划研究比较少。路径规划主要分为两种类型：全局路径规划和局部路径规划。

1.2.1 全局路径规划

全局路径规划是对环境信息已完全知道的路径规划问，其方法主要有：栅格法、结构空间法和拓扑法。

栅格法多采用二维笛卡尔矩阵栅格表示工作环境，它是对规划空间进行单元分割，将空间用大小相等的二值栅格单元表示，栅格值为1表示该方格已经被占用，对于空闲的栅格则赋予值0，这样栅格大小的选取是影响规划算法性能的一个重要的因素。栅格越小，由栅格地图所表示的环境信息将会非常清晰，但由于需要存储较多的信息，会增大存储开销，极大减低了规划速度，实时性得不到保证。一般，栅格法用于对工作环境的建模，在在规划路径时需要结合其他算法。

结构空间的实质是一种数据结构。结构空间法的一般步骤为：首先建立结构空间，构造自由空间；其次确定单元连通性，将自由空间表示为连通图；然后建立搜索树，确定搜索策略；最后进行路径优化。结构空间表示法有许多，其中具有代表性的是Voronoi图法和四叉树及其拓展算法。

拓扑法是用图形来表现机器人工作环境中事物及他们之间的联系。通常，环境中的事物用节点来表示，用这些节点之间连线形成的边来展示事物之间的联系。这些节点与边结合在一起形成一张拓扑图。拓扑图中的边则表示不同节点之间的通道。拓扑结构不需要直接测量环境信息，一般作为环境模型建立方法使用。

1.2.2 局部路径规划

局部路径规划的主要方法有:人工势场法、模糊逻辑算法和遗传算法。

人工势场法的基本思想是:将环境空间看作为虚拟的势力场，运动物体看作在其中运动，目标点对运动物体产生吸引力，障碍物对运动物体产生排斥力，引力与斥力共同作用控制物体运动，两个作用力的合力的极小值可以做为物体运动路径。由于人工势场法在数学描述上简洁，此方法仍然在很多地方被应用。它的局限性主要表现在：当目标附近有障碍物时，规划对象将永远无法达不了目的地，而且当规划对象受到的引力和斥力的合力为很小时，规划对象会表现的很迟钝。

模糊逻辑法的基础是模糊逻辑算法，他是利用传感器实时采集规划空间内物体的位置和运动信息，对采集到的信息进行模糊化处理，通过比对自身的知识库和规则库进行模糊推理，然后通过解模糊得到物体运动速度变化和转角变化，从而控制物体达到目标位置。该方法适合用在环境空间实时变化路径规划。