Planning for Multiple Preferences versus Planning with No Preference

Abstract EN

Many planning applications must address conflicting plan objectives, such as cost, duration, and resource consumption, and decision makers want to know the possible tradeoffs.

Traditionally, such problems are solved by invoking a single-objective algorithm (such as A*) on multiple, alternative preferences of the objectives to identify nondominated plans.

The less-popular alternative is to delay such reasoning and directly optimize multiple plan objectives with a search algorithm like multiobjective A* (MOA*).

The relative performance of these two approaches hinges upon the number of f-values computed for individual search nodes.

A* may revisit a node several times and compute a different f-value each time.

MOA* visits each node once and may compute some number of f-values (each estimating the value of a different nondominated solution constructed from the node).

While A* does not share f-values between searches for different solutions, MOA* can sometimes find multiple solutions while computing a single f-value per node.

The results of extensive empirical comparison show that (i) the performance of multiple invocations of a single-objective A* versus a single invocation of MOA* is often worse in time and quality and (ii) that techniques for balancing per node cost and exploration are promising.