Search-based planning systems are often evaluated under the two assumptions of producing a single plan while minimizing a single quality metric.  In this context, a planner is preferred if its search produces a better quality plan with the same (or fewer) computational resources.  The dominant paradigm of search in planning is constructive best first search (i.e., A*), and the quality-efficiency focus has naturally led to search techniques that iteratively improve the next generation of planners to find the best (optimal) solution ever faster.

Our focus problem -- a personalized security agent for home computer users -- challenges the evaluation assumptions of these search-based planning systems.  The security application requires a planner that searches for plan sets that are evaluated with more than one quality metric.  These assumptions extend planner evaluation in two ways.  The requirement of multiple metrics refines the quality dimension.  The requirement of producing plan sets introduces a new evaluation dimension, namely diversity, which is often measured as a distance between the actions of plans (i.e., distance is the cardinality of the set difference or the set intersection between the actions of two plans). Recent work has extended planning systems to produce diverse plan sets, and a common approach for driving diversity in search is to combine the quality and diversity metrics in a single, weighted objective function.  While these approaches can improve the diversity of the final plan sets, relatively little is understood about the interplay of diversity, quality, and efficiency with respect to search behavior.

This talk reviews our study so far into the interplay of diversity, quality, and efficiency for search-based planning.  We examine the security application, several benchmark tasks, plus a synthetic task that allows us to control metric interaction.  Using several evaluation metrics from the literature as well as some new metrics of our own creation, we show that combining the diversity metric with the quality metric(s) in a weighted objective function leads to high diversity that often sacrifices efficiency and quality.  Our key contribution is discovering that parsimony -- preferring shorter plans while maximizing diversity -- is essential to achieving diverse plan sets that maintain reasonable quality.

Our findings synthesize the recent literature on generating diverse plans. Since each application has differing concerns with respect to quality and diversity, our results emphasize that the objectives of the application should direct both the choice of the algorithm and the choice of the search control mechanisms.  We show that targeted changes to the A* algorithm improve search for several applications including security. Finally, we show that understanding the interplay of diversity, quality, and efficiency can lead to improved algorithm design for specific applications.