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

Improvement of Hierarchical Path Planning Algorithm in Embedded Environment

作　　者：苗洋[1] 陈奇[1] 

机构地区：[1]浙江大学计算机科学与技术学院,杭州310027

出　　处：《计算机工程》2010年第14期243-245,共3页Computer Engineering

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

关 键 词：嵌入式系统 分层路径规划算法 DIJKSTRA算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]