An Approach Combining Incremental Search and Heuristic Search for Solving Multiobjective Problems

Multiobjective problems are much more difficult to solve than single objective problems because of the multiple conflicting objectives. Heuristic search is an efficient approach for solving multiobjective shortest paths problems. However, many real problems change their state spaces with different situations. Incremental search which reuses information from previous searches can be used to find solutions in dynamic situations. In this paper, an approach combining incremental search and heuristic search for solving multiobjective problems is proposed, and a multiobjective incremental heuristic search system based on path expansion in the search process is designed and implemented. When the edge costs of a graph change or nodes are added or deleted in the state space, the system does not solve the new problem from scratch, but updates the scene of the search immediately, reuses parts of the information of the previous search and then starts a new search process from the scene after the update process, thus the efficiency of replanning is improved. The gridworld benchmark problem is used for testing and the experimental results show that the approach combining incremental search and heuristic search can solve a series of similar multiobjective shortest path problems very efficiently when the state space changes continuously.