Search for Compromise Solutions in Multiobjective State Space Graphs
Galand, Lucie; Perny, Patrice (2006), Search for Compromise Solutions in Multiobjective State Space Graphs, in Traverso, Paolo, Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), IOS Press : Tokyo, p. 93-97
TypeCommunication / Conférence
Book titleProceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006)
Book authorTraverso, Paolo
MetadataShow full item record
Abstract (EN)The aim of this paper is to introduce and solve new search problems in multiobjective state space graphs. Although most of the studies concentrate on the determination of the entire set of Pareto optimal solution paths, the size of which can be, in worst case, exponential in the number of nodes, we consider here more specialized problems where the search is focused on Pareto solutions achieving a well-balanced compromise between the conflicting objectives. After introducing a formal definition of the compromise search problem, we discuss computational issues and the complexity of the problem. Then, we introduce two algorithms to find the best compromise solution-paths in a state space graph. Finally, we report various numerical tests showing that, as far as compromise search is concerned, both algorithms are very efficient (compared to MOA*) but they present contrasted advantages discussed in the conclusion.
Subjects / Keywordsspace graphs; algorithms
Showing items related by title and author.
Bidirectional versus Unidirectional Heuristic Search for Multiojective Optimization in State Space Graphs Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013) Communication / Conférence