Suppose that there is a collection of cost functions, each of which evaluates an action. This leads to a generalization of Formulation 9.1 to multiobjective optimization.
A version of this problem was considered in Section 7.7.2, which involved the optimal coordination of multiple robots. Two actions, and , are called equivalent if . An action is said to dominate an action if they are not equivalent and for all such that . This defines a partial ordering, , on the set of actions. Note that many actions may be incomparable. An action is called Pareto optimal if it is not dominated by any others. This means that it is minimal with respect to the partial ordering.
Based on this simple example, the notion of Pareto optimality seems mostly aimed at discarding dominated actions. Although there may be multiple Pareto-optimal solutions, it at least narrows down to a collection of the best alternatives.
The two criteria for a driver are 1) the time to cross the state, and
2) the amount of money spent on tickets. It is assumed that you will
be caught violating the speed limit. The goal is to minimize both.
What are the resulting Pareto-optimal driving speeds? Compare driving
56 mph to driving 57 mph. Both cost the same amount of money, but
driving 57 mph takes less time. Therefore, 57 mph dominates 56 mph.
In fact, 65 mph dominates all speeds down to 56 mph because the cost
is the same, and it reduces the time the most. Based on this
argument, the Pareto-optimal driving speeds are 55, 65, 75, 85, and
100. It is up to the individual drivers to decide on the particular
best action for them; however, it is clear that no speeds outside of
the Pareto-optimal set are sensible.
The following example illustrates the main frustration with Pareto optimality. Removing nondominated solutions may not be useful enough. In come cases, there may even be a continuum of Pareto-optimal solutions. Therefore, the Pareto-optimal concept is not always useful. Its value depends on the particular application.
Steven M LaValle 2012-04-20