Probabilistic Focal Search Accelerates Bounded-Suboptimal Search

Summary

Bounded-suboptimal search aims to find a solution no worse than a chosen factor w from optimal while limiting search effort. The paper identifies a limitation in Focal Search: its deterministic policy can expand many nodes without increasing the minimum f value, delaying the admission of useful nodes into FOCAL. Probabilistic Focal Search (PFS) follows the usual Focal Search choice with probability p, and otherwise expands a minimum-f node from OPEN to advance the lower bound. The authors evaluate PFS against Focal Search on N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem, and test an anytime version, Anytime Probabilistic Focal Search (APFS), on the Generalized Covering TSP. The largest improvements appear on long f-minimum plateaus that delay FOCAL admission, where PFS can reduce node expansions by about 90% or more on examples including N-Puzzle and TSP. Gains are smaller on Pancake Sorting, where deterministic search already advances efficiently. The same scheduling idea is also applied to Dynamic Potential Search as Probabilistic Dynamic Potential Search, with results depending on the domain and bound.