Ideal Point Guided Iterative Deepening

摘要

Many real world search problems involve different objectives, usually in conflict. In these cases the cost of a transition is given by a cost vector. This paper presents IPID, a new exact algorithm based on iterative deepening, that finds the set of all Pareto-optimal paths for a search problem in a graph with vectorial costs. Formal proofs of the admissibility of IPID are presented, as well as the results of some empirical comparisons between IPID and other approaches based on iterative deepening. Empirical results show that IPID is usually faster than those approaches.