一种实时多目标路径规划方法  

Real-time Multiobjective Path Planning

作　　者：魏唯[1,2] 欧阳丹彤[1,2] 吕帅[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012

出　　处：《计算机科学》2010年第7期236-239,269,共5页Computer Science

基　　金：国家自然科学基金(60973089;60773097;60873044;60873148);教育部博士点基金(20060183044);吉林省科技发展计划项目基金(20060532;20080107)资助

摘　　要：提出一种利用实时搜索思想的多目标路径规划方法。首先设计并实现局部路径规划算法,在有限的局部空间内执行启发式搜索,求解所有局部非支配路径;在此基础上,提出实时多目标路径规划方法,设计并实现相应的启发式搜索算法,在线交替执行局部搜索过程、学习过程与移动过程,分别用于求解局部空间内的最优移动路径,完成状态的转移和更新状态的启发信息,最终到达目标状态。研究表明,实时多目标启发式搜索算法通过限制局部搜索空间,避免了大量不必要的计算,提高了搜索效率,能够高效地求解多目标路径规划问题。A method adopting the idea of real-time search for solving multiobjective path planning problems was proposed, a local path planning algorithm was designed and implemented which executes a heuristic search within a limited local space to get all of the local non-dominated paths. After that, the method of real-time multiobjective path planning was proposed and the corresponding heuristic search algorithm was designed and implemented. The algorithm executes path planning process, learning process and moving process online by turns to get the set of local optimal paths, trans- fers the current state in the local space and updates heuristic information of the local states respectively until reaching the goal state successfully. Test results show that the algorithm can solve multiobjective path planning problems efficiently by limiting local search space which can avoid lots of unnecessary computing work and thus improve the search efficiency.

关 键 词：多目标路径规划 实时搜索 局部空间 启发式搜索 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]