作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (14): 243-245. doi: 10.3969/j.issn.1000-3428.2010.14.088

• 开发研究与设计技术 • 上一篇    下一篇

嵌入式环境中分层路径规划算法的改进

苗 洋,陈 奇   

  1. (浙江大学计算机科学与技术学院,杭州 310027)
  • 出版日期:2010-07-20 发布日期:2010-07-20
  • 作者简介:苗 洋(1985-),男,硕士研究生,主研方向:地理信息系统,导航系统;陈 奇,副教授

Improvement of Hierarchical Path Planning Algorithm in Embedded Environment

MIAO Yang, CHEN Qi   

  1. (College of Computer Science and Technology, Zhejiang University, Hangzhou 310027)
  • Online:2010-07-20 Published:2010-07-20

摘要: 针对分层路径规划算法对上下层道路的对应关系存储耗费大量存储空间的问题,提出一种适合嵌入式环境的改进分层算法。通过在各个层次内部引入道路等级信息提高计算速度,在运算过程中动态切换搜索层次和等级达到减少分层数和数据量的目的。对比实验表明,改进算法在扩展节点数和路径规划时间方面均优于其他3种算法,且能满足嵌入式环境中高效路径规划的需求。

关键词: 嵌入式系统, 分层路径规划算法, Dijkstra算法

Abstract: Aiming at the problem that hierarchical path planning algorithm always has to store the correspondence between roads of different hierarchies which makes the storage efficiency critical, this paper proposes an improved hierarchical path planning algorithm which is suitable for embedded system. This algorithm enhances computing speed by importing road class information into every road hierarchy, and dynamically switches searching hierarchy and class to reduce hierarchy number and the amount of data. Comparison experiment shows the improved algorithm has better performance than other three kinds of algorithms on the aspects of extended node number and path planning time, and it can satisfy the need of efficient path planning in embedded system.

Key words: embedded system, hierarchical path planning algorithm, Dijkstra algorithm

中图分类号: