摘要
提出一种在动态不确定环境下求解多目标问题时快速调整移动路径的方法.首先提出采用逆向多目标启发式搜索进行全局规划,求解问题的最优路径集合;然后提出动态多目标路径规划方法,先根据当前观测进行全局规划,在移动过程中探测到不一致的环境信息时,通过对先前搜索中部分信息的重用,在全局规划的基础上进行增量重规划,调整当前状态与目标状态之间的移动路径.研究结果表明:采用增量重规划的求解方法通过搜索信息的重用提高求解效率,能够有效地处理动态不确定环境下的多目标路径规划问题.
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.
出处
《计算机学报》
EI
CSCD
北大核心
2011年第5期836-846,共11页
Chinese Journal of Computers
基金
国家自然科学基金(60773097
60873044
60873148
60973089)
符号计算与知识工程教育部重点实验室开放基金项目(93K-17-2009-K02
93K-17-2009-K06)
吉林大学研究生创新基金(20111060)资助~~
关键词
多目标路径规划
动态不确定环境
启发式搜索
全局规划
增量重规划
multiobjective path planning
dynamic uncertain environment
heuristic search
global planning
incremental replanning
