基于栅格法的汽车路径规划

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 引言
• 1.2 相关研究现状综述
• 1.2.1 环境建模的方法
• 1.2.2 路径搜索的方法
• 1.3 主要研究内容及论文组织结构
• 2 环境建模
• 2.1 栅格法
• 2.2 建模思路及实现
• 2.2.1 建模思路
• 2.2.2 具体实现
• 2.3 线路拟合和平滑化处理
• 2.3.1 ALA 路径
• 2.3.2 实现方案
• 2.4 本章小结
• 3 基于栅格的搜索方法
• 3.1 广度优先算法实现
• 3.1.1 搜索思路
• 3.1.2 广度优先算法
• 3.1.3 哈希表
• 3.2 Dijkstra 算法实现
• 3.2.1 搜索思路
• 3.2.2 Dijkstra 算法
• 3.2.3 程序设计
• 3.3 算法比较
• 3.4 本章小结
• 4 调运辅助决策系统研制方案与实现
• 4.1 开发方案
• 4.2 系统界面及功能
• 4.3 本章小结
• 5 总结与展望
• 致谢
• 参考文献