2018 · 41 citations · 21 references
ComputingComputer ScienceAlgorithmsOptimizationTheory Of ComputationAlgorithm AnalysisHeuristic SearchSearching AlgorithmsA* SearchAnytime Heuristic SearchBounded SearchDeliberationReuseState Space Search
Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a "good" solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.
21
Conflict-based search for optimal multi-agent pathfinding
Guni Sharon, Roni Stern, Ariel Felner et al. · Artificial Intelligence · 2014 · 1.2K citations
Blai Bonet, Héctor Geffner · Artificial Intelligence · 2001 · 961 citations · Full text
Heuristic search viewed as path finding in a graph
Ira Pohl · Artificial Intelligence · 1970 · 423 citations