Detail

Graph Search Algorithms with One and Multiple Objectives

The shortest path problem is a classical combinatorial optimization problem with many applications in Operations Research. The development of Artificial Intelligence, and specially the Heuristic Search Hypothesis (1975) by Allen Newell and Herbert Simon, gave graph search algorithms a central role in general problem solving. In consequence, Artificial Intelligence research has favoured significant advances in the development of efficient graph search algorithms.

Multiobjective decision making is an important alternative to classical optimization. Real world decision problems often involve a trade-off between multiple, conflicting, and non-commesurate objectives. The multiobjective search problem can be described as an extension of the shortest path problem where arc costs become vectors. However, this is a genuinely different problem since vector costs induce only a partial order relation, and requires the development of specific search algorithms.

In this talk we shall first review state-of-the-art heuristic graph search algorithms developed by the AI community and give a general picture of their performance. We shall then consider the extension of these algorithms to the multiobjective decision framework, and discuss their applications and limitations.