Theoretical Study on Multi-objective Heuristic Search

Shawn Skyler, Shahaf S. Shperberg, Dor Atzmon, Ariel Felner, Oren Salzman, Shao-Hung Chan, Han Zhang, Sven Koenig, William Yeoh, Carlos Hernández UlloaIJCAI 2024 · OpenReview

Abstract This paper provides a theoretical study on Multi-Objective Heuristic Search (MOS). We first classify states in the state space into must-expand, maybe-expand, and never-expand states and then transfer these definitions to nodes in the search tree. We then formalize a framework that generalizes A* to Multi-Objective Search. We study different ways to order nodes under this framework and their relation to traditional tie-breaking policies and provide theoretical findings. Finally, we study and empirically compare different ordering functions.

Introduction

In classical Single-Objective Search (SOS), algorithms like A are well-understood, with clear definitions of which states must be expanded to guarantee optimality. However, Multi-Objective Search (MOS) is significantly more complex. In MOS, there is rarely a single "best" path; instead, the goal is to find the Pareto-optimal frontier (POF)*—a set of paths where no path is strictly better than another across all objectives (e.g., balancing time, fuel, and distance).

While various MOS algorithms exist, the field has lacked a comprehensive theory explaining why certain nodes must be expanded and how different "Ordering Functions"—the logic used to pick the next node from a priority queue—affect performance. This research bridges the gap between SOS theory and the vector-based reality of MOS.

State and Node Classification

A key contribution of this work is the extension of the "must-expand" theory to the multi-objective domain. The researchers classify states and nodes into four distinct zones based on their cost vectors relative to the optimal solutions:

  • Zone A (Optimality): States that must be expanded to find optimal solutions.
  • Zone B (Completeness): States that must be expanded to prove that no other optimal solutions exist.
  • Zone C (Maybe): States that might be expanded depending on the specific tie-breaking policy.
  • Zone D (Never): States that can be safely ignored as they cannot lead to an optimal solution.
Classification of states and nodes into zones A, B, C, and D based on their cost vectors relative to the Pareto-optimal frontier.

The MOS-A* Framework and Ordering Functions

The researchers formalize a framework called MOS-A, which generalizes standard A to handle vector costs. A central component of this framework is the Ordering Function (OF), which determines the order in which undominated nodes are processed. Because objectives like "cost" and "time" often have different scales, the authors utilize a linear normalization process to map all costs to a [0, 1] range for fair comparison.

Visualization of normalization and different ordering functions (Lex, Avg, Min, Max) and how they prioritize the search through the objective space.

The study analyzes several common ordering functions:

  • Lexicographical (Lex): Prioritizes objectives in a fixed, hierarchical order.
  • Average (Avg): Minimizes the weighted sum of all objectives.
  • Min/Max: Focuses on the smallest or largest individual objective values respectively.

Key Theoretical and Empirical Insights

One of the most significant theoretical findings is the Invariance of Ordering: the choice of Ordering Function does not change the final set of nodes that must be expanded. If the tie-breaking is consistent, the total "work" remains the same regardless of whether one uses Lexicographical or Average ordering.

However, the Tie-Breaking (TB) policy can change the number of expansions. Finding a solution earlier via a superior tie-breaker allows the algorithm to prune other branches more aggressively. This leads to differences in "anytime" performance:

  • Lexicographical (Lex) is the fastest at finding the first solution, often requiring only 10-17% of total expansions, but it is the slowest to discover the full frontier.
  • Min Ordering emerged as a powerful anytime strategy, sometimes discovering the entire Pareto-optimal frontier after only 43% of the total required expansions.
  • Phase Distribution: The "Mid phase"—the time between finding the first and last solution—is the most computationally expensive, accounting for 80-90% of expansions as the number of objectives increases.

Conclusion and Future Work

This study provides a rigorous foundation for MOS, highlighting that while ordering functions don't change the total expansion set, they are critical for anytime performance. Future work may explore "state-based" information sharing to reduce redundant expansions and investigate how multi-valued heuristics interact with these state classifications.

Summary updated

Abstract

This paper provides a theoretical study on Multi-Objective Heuristic Search. We first classify states in the state space into must-expand, maybe-expand, and never-expand states and then transfer these definitions to nodes in the search tree. We then formalize a framework that generalizes A* to Multi-Objective Search. We study different ways to order nodes under this framework and their relation to traditional tie-breaking policies and provide theoretical findings. Finally, we study and empirically compare different ordering functions.
BibTeX
@inproceedings{skyler2024theoretical,
  author = {Shawn Skyler and Shahaf S. Shperberg and Dor Atzmon and Ariel Felner and Oren Salzman and Shao-Hung Chan and Han Zhang and Sven Koenig and William Yeoh and Carlos Hernández Ulloa},
  title = {{Theoretical Study on Multi-objective Heuristic Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=tvZjoBNrpm},
}
Figure