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

摘要

提出一种在动态不确定环境下求解多目标问题时快速调整移动路径的方法.首先提出采用逆向多目标启发式搜索进行全局规划,求解问题的最优路径集合;然后提出动态多目标路径规划方法,先根据当前观测进行全局规划,在移动过程中探测到不一致的环境信息时,通过对先前搜索中部分信息的重用,在全局规划的基础上进行增量重规划,调整当前状态与目标状态之间的移动路径.研究结果表明:采用增量重规划的求解方法通过搜索信息的重用提高求解效率,能够有效地处理动态不确定环境下的多目标路径规划问题.%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 multiohjective 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.