摘 要

汽车作为人们衣食住行中行的主要载体之一，其地位的重要性不言而喻。现如今，中国经济不断增长，国内汽车保有量不断增加，交通拥堵十分严重，交通事故频发，现有的交通状况对人们的驾驶技术要求愈发提高。现有的交通资源与人们的交通需求之间的矛盾亟待解决。智能交通系统(Intelligent Transportation Systems，ITS)应运而生，无人驾驶车辆又是智能交通系统的重要组成部分，目前不仅仅各大汽车厂商投入大量资金和人员研发相关技术，互联网和移动通信公司也争相进入这一领域。

无人驾驶车辆将是汽车行业发展的必然趋势，无人驾驶车辆是一个复杂的智能系统，涉及到的内容主要包括体系结构、环境感知、定位导航、路径规划、运动控制和一体化设计六个方面。本文的主要研究方向是无人驾驶车辆智能系统中的路径规划技术。无人驾驶车辆路径规划技术是指在一定的环境模型基础上，给定无人驾驶车辆起始点和目标点后，按照某种技术指标规划车一条无碰撞的有效路径。路径规划主要包括建立环境地图和调用搜索算法在环境地图中搜索出一条有效路径。查阅文献时发现基于随机采样的非完备性路径规划算法能够避免对位形空间进行确定性计算，可以解决其他算法中在高维空间中存在的计算复杂和储存量巨大的问题，具有较大研究价值。本文的主要内容是研究基于随机采样的路径规划技术。

本文首先对课题的背景和研究意义进行了分析，同时阐述了国内外无人驾驶车辆路径规划技术研究现状，主要是对路径规划技术中的两个关键问题即环境建模和路径搜索策略的研究现状进行介绍。其次对基于随机采样的非完备性路径规划算法中的相关基础理论知识进行了说明，为后续分析提供理论支撑。然后本文以快速扩展随机树算法(RRT)为例,分析了该算法中关键函数并给出了相应的函数伪代码，同时也分析了基于RRT改进的RRT^*算法，给出了相关函数的伪代码。再者本文利用Matlab软件编写了相应程序，实现了基于RRT算法的路径规划仿真，对RRT算法中的关键参数即拓展步长和目标偏置概率p进行了分析，同时也对基于RRT改进的RRT^*算法进行了对比分析。最后，对本文的工作进行了总结，提出了本文未解决的问题及对以后的工作进行了展望。

关键词：无人驾驶车辆 路径规划技术 随机采样 快速扩展随机树 Matlab软件

ABSTRACT

As one of the main carriers for people in China, the importance of their status is self-evident. In recent years, China’s economy has grown continuously. The number of cars in China keeps increasing, traffic congestion is very serious, traffic accidents happens frequently, and the current traffic conditions have increased people’s driving technical requirement. The contradiction between the existing transportation resources and people's transportation demand needs to be solved. Intelligent Transportation Systems (ITS) come into being. Pilotless automobiles are an important part of intelligent transportation systems. At present, not only major automobile manufacturers have invested large sums of money and personnel in related technologies, but also Internet and mobile communications companies enter this field.

Pilotless automobiles will be an inevitable trend in the development of the automotive industry. Pilotless automobiles are a complex intelligent system, which mainly includes architecture, environment awareness, positioning navigation, path planning, motion control and integrated design. The main research direction of this paper is the path planning technology of the intelligent vehicle system for unmanned vehicles. The path planning technology of unmanned vehicles is based on a certain environmental model. After a starting point and a target point of a driverless vehicle are given, a certain collision-free effective path is planned according to a certain technical index. Path planning mainly includes establishing an environment map and invoking a search algorithm to find out an effective path in the environment map. When reviewing the literature, it is found that the incomplete path planning algorithm based on random sampling can avoid deterministic calculation of the configuration space, and can solve the problem of computation complexity and huge storage capacity in high-dimensional space of other algorithms. The main content of this paper is to study path planning technology based on random sampling.

Firstly, this paper analyzes the background and research significance of the project. At the same time, it expatiates on the status quo of research on path planning technology of unmanned vehicles at home and abroad. It is mainly about two key issues in path planning technology, namely, environment modeling and path search strategy. And it’s status quo is introduced. Secondly, the relevant basic theoretical knowledge in the incomplete path planning algorithm based on random sampling is explained to provide theoretical support for the subsequent analysis. Then, this paper uses Rapidly-exploring Random Tree algorithm (RRT) as an example, analyzes the key functions of the algorithm and gives the corresponding function pseudo-code. At the same time, it also analyzes the improved RRT* algorithm based on RRT and gives the pseudo-functions of related functions. In addition, this paper uses Matlab software to write the corresponding program, realizes the path planning simulation based on the RRT algorithm, analyzes the key parameters in the RRT algorithm, namely, the extended step length ∆q and the target bias probability p. At the same time, it also makes a comparative analysis of the improved RRT* algorithm based on RRT. Finally, the paper summarizes the work of this article, and proposes unsolved problems in this paper and looks forward to the future work.

Keywords: Pilotless automobiles; path planning; random sampling; Rapidly-exploring Random Tree; Matlab software.

目录

摘要 I

ABSTRACT II

第一章．绪论 1

1.1课题背景及研究意义 1

1.2 国内外研究现状分析 2

1.2.1 环境地图建模研究现状 3

1.2.2 路径搜索算法研究现状 4

1.3本文的主要研究内容 6

1.4论文的组织结构 6

第二章.基于采样的路径规划算法理论研究 7

2.1 图论及位形空间(Configuration-Space) 7

2.2.1 图论简介 7

2.1.2 位形空间(Configuration-Space) 7

2.1.3 度量函数 8

2.2 基于采样的路径规划算法的一般原理 8

2.2.1 问题说明 8

2.2.2 算法的一般步骤 10

2.3 采样策略 10

2.3.1 随机性与完备性概念 10

2.3.2 随机采样策略 11

2.4碰撞检测 12

2.4.1 碰撞检测核心思想及类型 12

2.4.2 检验步长的确定 12

2.5 路径平滑优化处理 13

2.6 本章小结 14

第三章.实例分析-以快速扩展随机树(RRT)算法为例 15

3.1引言 15

3.2 基于RRT算法路径规划原理 15

3.2.1路径规划流程图 15

3.2.2 RRT算法原理 15

3.3 RRT算法中的关键函数 17

3.3.1 RRT算法中的Sample函数 17

3.3.2 RRT算法中的Nearest函数 18

3.3.3 RRT算法中的Steer函数 20

3.4 RRT^*算法概述 21

3.4.1 RRT^*算法与RRT算法的区别与改进 21

3.4.2 RRT^*算法原理 21

3.5 RRT^*算法中Min函数和Reconnect函数分析 23

3.5.1 Min函数 23

3.5.2 Reconnect函数 24