Abstract: Aiming at improving efficiency of D*Lite algorithm for path planning of robots, this paper presents three developed cost functions. The characteristics and the construction rules of the cost function are researched and a developed algorithm is proposed based on the Aε algorithm and the restriction of function admissibility. Experimental results show that the developed algorithm can improve the search efficiency and guaranteed the optimality of the result in a certain range.

Key words: evaluation function, D*Lite algorithm, heuristic search, incremental search

摘要： 为提高D*Lite算法在机器人路径规划中的效率，提出3种基于D*Lite算法的估价函数。研究函数的特性及其构造原则，结合Aε*算法的特点，利用估价函数的可纳性约束设计其改进算法。实验结果表明，改进算法能减少扩展节点的数量，提高搜索效率，并保证其解在一定范围内的最优性。

关键词: 估价函数, D*Lite算法, 启发式搜索, 增量搜索

CLC Number: 

• TP301.6