Finding a Small, Diverse Subset of the Pareto Solution Set in Bi-Objective Search (Extended Abstract)

Abstract

Bi-objective search requires computing a Pareto solution set which contains a set of paths. In real-world applications, Pareto solution sets may contain several tens or even hundreds of solutions. For a human user trying to commit to just one of these paths, navigating through a large solution set may become overwhelming, which motivates the problem of computing small, good-quality subsets of Pareto frontiers. This document presents two main contributions. First, we provide a simple formalization of good-quality subsets of a Pareto solution set. For this, we use measure of richness which has been employed in the study of Population Dynamics. Second, we propose Chebyshev BOA*, a variant of BOA* to compute good-quality subset approximations.