OWA-based Search in State Space Graphs with Multiple Cost Functions

Lucie Galand, Olivier Spanjaard

This paper is devoted to the determination of well-balanced solutions in search problems involving multiple cost functions. After indicating various contexts in which the ordered weighted averaging operator (with decreasing weights) is natural to express the preferences between solutions, we propose a search algorithm to determine the OWA-optimal solution. More precisely, we show how to embed the search for a best solution into the search for the set of Pareto solutions. We provide a sophisticated heuristic evaluation function dedicated to OWA-optimization, and we prove its admissibility. Finally, the numerical performance of our method are presented and discussed.

Subjects: 15. Problem Solving; 15.7 Search

Submitted: Feb 10, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.