动态不确定环境下多目标路径规划方法  

Multiobjective Path Planning under Dynamic Uncertain Environment

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

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

出　　处：《计算机学报》2011年第5期836-846,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(60773097;60873044;60873148;60973089);符号计算与知识工程教育部重点实验室开放基金项目(93K-17-2009-K02;93K-17-2009-K06);吉林大学研究生创新基金(20111060)资助~~

摘　　要：提出一种在动态不确定环境下求解多目标问题时快速调整移动路径的方法.首先提出采用逆向多目标启发式搜索进行全局规划,求解问题的最优路径集合;然后提出动态多目标路径规划方法,先根据当前观测进行全局规划,在移动过程中探测到不一致的环境信息时,通过对先前搜索中部分信息的重用,在全局规划的基础上进行增量重规划,调整当前状态与目标状态之间的移动路径.研究结果表明:采用增量重规划的求解方法通过搜索信息的重用提高求解效率,能够有效地处理动态不确定环境下的多目标路径规划问题.In this paper,a method for adjusting the executing path of multiobjective path planning problems under dynamic uncertain environments is proposed.The backward multiobjective heuristic search algorithm is proposed firstly which starts the search process from the goal state to the start state to solve the given multiobjective problem.Then the dynamic multiobjective path planning algorithm is proposed.The algorithm performs global planning according to initial observations to the state space.Incremental replanning process is performed immediately when changes of environment are detected during the moving process.The replanning process can execute incrementally based on the global planning process to revise the path between any current state and the goal state efficiently by reusing parts of the saved information of the previous search.The experiment results show that the dynamic multiobjective path planning algorithm adopting an incremental replanning can solve multiobjective path planning problems under dynamic uncertain environments efficiently by reusing the information of previous search.

关 键 词：多目标路径规划 动态不确定环境 启发式搜索 全局规划 增量重规划 

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