原文传递
时间限制下动态路网路径规划算法的研究与实现
| 论文题名： | 时间限制下动态路网路径规划算法的研究与实现 |
| 关键词： | 动态路网;路径规划;时间限制;导航场景 |
| 摘要： | 静态路网无法实时地对交通状态进行表达，传统的路径规划算法也多是基于静态信息进行路径规划，没有利用到实时的交通信息。但是随着信息采集技术的发展，能够很容易获得到实时的交通路况信息，所以在当代导航设备中，更适合使用基于实时交通信息的动态路径规划算法进行导航。另外，由于路网的不断变化，在某些场景下，可用的求解时间非常少，用户对动态路径规划算法有着非常高的实时性要求。算法如何在有限的求解时间内，尽可能地提高求得的路径的质量，是一个很值得研究的问题。 本文的主要工作有: 1，改进的动态路网模型的研究 本文结合以下事实对传统实时路网模型进行改进。1）.用户在一次出行过程中，交叉口的等待时延占总时间20％-40％，不可忽略。2）.传统的路网模型笼统地用一个权值来表示经过一个路段的行驶时间，不便实时信息的收集和计算，且无法直观表现出路段的拥堵程度。本文针对上述两点改进，引入交叉口时延和路阻系数，对动态路网进行更为准确地表达，方便后续的算法研究。 2，对已有的动态路径规划算法进行分析，提出WD*算法 文中对已有的D*Lite、AD*算法进行分析研究，指出它们的算法思想，并结合它们的性质提出WD*算法。并用实验比较它们的导航结果，分析指出，AD*算法会将较多的节点放入下一轮进行搜索，总体上反而增加了求出最优路径的计算量，在实时性要求较高的场景中，WD*算法的导航效果反而总体表现较好。 3，利用WD*算法的性质，提出APWD*算法 WD*算法可以通过改变影响因子∈调整求解时间和路径质量，多核导航设备具有并行计算的能力。结合以上因素，文中提出的APWD*算法并行运行多个影响因子∈不同的WD*算法实例，在限制时间内返回已得路径集合中的最优解，能有效保证每轮搜索的路径质量。实验表明，由于各个算法实例运行时间和返回的路径质量都不同，通过合理地设计各个实例影响因子，算法能很好地适应各种不同实时性要求的导航场景。 |
| 作者： | 程思敏 |
| 专业： | 信息安全 |
| 导师： | 许胤龙;孙广中 |
| 授予学位： | 硕士 |
| 授予学位单位： | 中国科学技术大学 |
| 学位年度： | 2015 |
| 正文语种： | 中文 |
检索历史
应用推荐
