硕士论文-基于栅格法的汽车路径规划.pdf

华中科技大学硕士学位论文
摘要
路径规划是指移动机器人按照某一种性能指标(例如距离、时间、能量等) 搜索
出一条从起始状态到目标状态的最优或次优路径。本文以某汽车调运辅助决策系统
为实际背景,研究了机器人路径规划技术在工程实践中的应用问题。
本项目的目的是针对典型的汽车布列模式和典型的调运任务提供一定数量的优
选的调运路线,并对可行路线进行排序。其主要难点在于系统的环境建模问题,以
及在线路搜索中必须保证一定的实时性要求。
本文首先从环境建模方法和路径搜索方法两方面介绍了目前路径规划技术的研
究现状,并给出了本文的主要研究内容和全文的组织结构。
其次,结合本项目的特点,在系统环境建模中提出改进的栅格法,并提出使用
ALA 的方法进行栅格之间的线路拟合和平滑化处理工作的思路。
第三,提出了两种基于改进的栅格法的路径搜索方法。第一种方法是以广度优
先算法为基础的全局搜索方法,在该方法中,主要采取哈希表进行判重,大大提高
了搜索速度。本文主要研究了建立哈希表的具体方法,并提出了两种方法来处理哈
希冲突问题。另一种方法是以 Dijkstra 算法为基础的近似搜索方法,该方法可以在保
证线路具有一定性能的前提下实现较快的搜索速度。本文针对两种搜索方法均给出
了具体的编程实现,并根据多种不同的布列图使用上述两种方法计算出汽车移动的
路径,从运算速度和运算结果两方面对这两种方法进行了比较。
最后,简要介绍了汽车调运辅助决策软件的开发方案、功能以及部分界面。

关键词:路径规划栅格法广度优先算法 Dijkstra算法哈希表
I
华中科技大学硕士学位论文
Abstract
The path planning is that a mobile robot searches an optimal path or a sub-optimal
path from the initial state to the target state in accordance with a performance index (such
as distance, time, energy, etc.). In this thesis, taking automobile allocation and
transportation assistant decision-making system as background , we discuss the path
planning application in engineering.
The objectives of this project are providing a certain number of optimized path for
some typical distributed maps and some typical tasks and sorting possible path. The main
difficulties are environmental modeling for system and the requirement of meeting
real-time in path search.
Firstly, this thesis introduces the current research status about path planning from the
environmental modeling and path search, and gives the main contents and the
organizational structure.
Secondly, combining with characteristics of the project, we propose improved grid
method for environmental modeling. And we propose to use the ALA method for fitting
and smoothing lines between grids.
Thirdly, we propose two search methods based on improved grid method. One global
search algorithm takes breadth-first search algorithm as base. We use hash table to prevent
the duplic