Research On Multiobjective Path Planning Methods Under Uncertain Environment

Path planning is an important branch of Artificial Intelligence research. Optimal path planning should find a best path according to some criterion from a given start state and a given goal state in the state space of the problem. The optimal path can be found by carrying out a complete global planning process if the environment information is static and fully known. However, in many situations the environment can not been totally known beforehand, the real situation may be detected different with the initial observation when moving on the path, then the moving path has to be recomputed several times before reaching the goal state according to the current detected environment information. Incremental search and real-time search are two very effective methods for solving uncertain environment. The basic idea of incremental search is not solving the changed problem from scratch but making some modifications to information from the previous search and improving the replanning efficiency by reusing part of the information. The real-time method does not start moving to the goal state after searching the whole state space off line but adopts a decomposing idea and executes path planning process, learning process and moving process online by turns to get the set of local optimal paths, transfer the current state in the local space and update heuristic information of the local states respectively until reaching the goal state successfully.The task of solving optimization problem is to find the optimal solution that satisfies one or multiple objectives. If only one object is considered, it is a single objective optimization problem. If more than one object needs to be considered simultaneously in a path planning problem, it is a multiobjective path planning problem. Solving a multiobjective problem is quite different with the single object condition because of the conflict among these objects. Since one solution may be good for some object but bad for others, there usually exists a set of optimal solutions which are not comparable instead of one best solution. The set of optimal solutions between the start state and the goal state need to be recomputed as soon as possible which is required to decide a new moving path when some inconsistent information is detected. Thus solving multiobjective path planning problems under uncertain environment are much more difficult.Analyzing the character of multiobjective problems, in this paper we do some deep research on multiobjective path planning methods based on heuristic search under uncertain environment. Multiobjective heuristic search expands a path each time and use heuristic information leading the search process to improve efficiency. A method based on incremental search is proposed first. The method performs global planning according to observations to get the set of optimal paths between the start state and the goal state. Local replanning process is performed immediately when changes of environment are detected such as change of transition cost and condition of dynamic obstacles. The replanning process can execute the backward heuristic search incrementally based on the global planning process to get the set of optimal paths between any current state and the goal state efficiently by reusing parts of the saved information of the previous search. In the backward search process, pm is a path from the goal state to the current state Sm, gm and hm of pm's evaluation function fm=gm+hm represent Sm's goal distance and evaluation of the optimal cost from Sm to the start state. Since the global planning process records all paths between each state to the goal state, the local replanning process only need to update the changed information and then performs backward multiobjective heuristic search from the goal state to the changed state again. Thus, the incremental replanning search can avoid a lot of repeated computing work caused by solving the changed problem from scratch. The Grid World benchmark problem is used for experiment. The test has four parts. Since the most common situation in real problem is considering two criterions simultaneously, the first three parts use path problems with two objects to test the condition when the dynamic obstacles change during the moving process, the transition costs of states change and compare of blind search and heuristic search respectively. The fourth part tests path problems with more than two objects and analyzes the algorithm's ability to solve kinds of path planning problems with different objects.Many real problems have strict real-time constraint, especially for some large size problem, it is inefficient to solve the whole problem in one search process. Real-time method can produce a partial execution steps in a limit time. In this paper, a method adopting the idea of real-time search for solving multiobjective path planning problems is proposed and the corresponding heuristic search algorithm is designed and implemented. The algorithm does not execute the moving process after exploring the whole state space with heuristic search off line but executes path planning process, learning process and moving process online by turns. The path planning process performs heuristic search within the local space around the current state and start to move immediately after the beginning of the path are computed. The moving process does the state transition in the local space to get closer to the goal state; meanwhile the learning process updates heuristic information of the local states constantly. The planning process is called again after the moving process is completed to compute the next part of moving path until reaching the goal state successfully. Solving multiobjective path planning problem requires finding all the non-dominated paths and thus the quantity of computation is huge. The algorithm divides the whole solving process into several independent local solving processes and only finds all the non-dominated in local space. Since the size of local state space is usually small and independent of the size of whole space, local space search process can been completed in a short time with greatly reduced computation which satisfies the real-time constraint and the local moving path is optimal. The beginning of the moving path can been computed in a quite short time, especially when a lot of uncertain information exist in the environment, choosing a small local space can detect the environment tentatively and avoid unnecessary computation caused by exploring the whole space completely. The richer heuristic information updated by on-line learning process can improve the efficiency of next search process which make the solving process more intelligent and the algorithm's ability more enhanced. Global moving path is concatenated of all the local paths computed by each local search process, the algorithm can ensure every local path is optimal in the related local search , but the additive global path can not been ensured globally non-dominated. Thus the real-time search algorithm trades solving efficiency with sacrificing of optimization. The Grid World benchmark problem is used for experiment. The test has two parts. The first part uses path planning problems with two object for instance to test the affection to search time and path cost with different search depth; the second part tests path problems with more than two objects and analyzes the algorithm's ability to solve kinds of path planning problems with different objects. The 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.