Must-Expand Nodes in Multi-Objective Search [Extended Abstract]


  • Shawn Skyler Ben-Gurion University
  • Shahaf Shperberg Ben-Gurion University
  • Dor Atzmon Royal Holloway, University of London
  • Ariel Felner Ben-Gurion University
  • Oren Salzman Technion - Israel Institute of Technology
  • Shao-Hung Chan University of Southern California
  • Han Zhang University of Southern California
  • Sven Koenig University of Southern California
  • William Yeoh Washington University in St. Louis
  • Carlos Hernández Ulloa Universidad San Sebastián



Analysis Of Search Algorithms, Problem Solving Using Search


This extended abstract presents a theoretical analysis of node expansions in Multi-Objective Search. We define three categories of nodes, Must-Expand Nodes, Maybe-Expand Nodes, and Never-Expand Nodes. Our analysis establishes that regardless of the Ordering Function or Multi-Objective Search algorithm used, any Multi-Objective Search algorithm must expand all Must-Expand Nodes, some or none of Maybe-Expand Nodes, and none of Never-Expand Nodes. In addition, we conduct experimental evaluations of various Ordering Functions, revealing that they all expand the same number of nodes and compare their efficiency at finding solutions at various stages of the search.