The Optimality of Satisficing Solutions
This work critiques a foundational assumption in heuristic search theory, potentially influencing algorithm design for AI and optimization problems.
The paper challenges the assumption that single-agent heuristic search must guarantee shortest-path (p-optimal) solutions, arguing that satisficing solutions can be optimal under different quality metrics.
This paper addresses a prevailing assumption in single-agent heuristic search theory- that problem-solving algorithms should guarantee shortest-path solutions, which are typically called optimal. Optimality implies a metric for judging solution quality, where the optimal solution is the solution with the highest quality. When path-length is the metric, we will distinguish such solutions as p-optimal.