The FESS Algorithm: A Feature Based Approach to Single-Agent Search

摘要

This paper introduces the Feature Space Search algorithm (FESS) that projects a single-agent application search space onto an abstract space that is defined by features of the domain. FESS works in this smaller space by directing the search from the projected initial state towards the projected final state. A state transition in the feature space maps to one or (usually) many moves in the domain space. Each of these transitions leads to a change in one or more features, with the FESS algorithm favoring transitions that make progress towards the projected final state. Each feature can be thought of as being a heuristic, and FESS is providing multi-objective guidance from the feature space to the search in the application domain.FESS is demonstrated using the challenging single-agent problem of Sokoban. For over twenty years, numerous approaches have been used to try solving the 90 problems in the standard benchmark test suite. FESS, using a set of domain-specific features, is the first program that solves all 90 problems. Further, although the experimental standard is to allocate 10 minutes of solving time per problem (900 minutes), the FESS approach solves the entire test set in less than 4 minutes.