Jump to content

Draft:Feature Space Search

From Wikipedia, the free encyclopedia

Feature Space Search (FESS) is a novel single-agent search algorithm designed to address limitations of traditional search methods in complex domains. Unlike other search algorithms that use features and combine them into a single value, FESS treats the features as an abstract space (feature space) to be explored. It guides the search process in the domain space through exploration within this feature space, without relying on an evaluation or heuristic function.

Generality

[edit]

FESS is designed as a general approach, offering a potentially more efficient solution for various problems by exploring features independently and providing multi-objective guidance to the search process. This makes it well-suited for challenging problems where finding a solution is a priority, even if not the most optimal one. While initially applied to Sokoban puzzles, its flexibility allows for adaptation to other domains with complex problem-solving requirements.

Development

[edit]

Motivated by the need for better search strategies, the algorithm was presented at the 2020 IEEE Conference on Games (CoG) by Yaron Shoham and Prof. Jonathan Schaeffer.[1]

Performance

[edit]

Empirical evaluations have shown strong performance compared to other search methods in Sokoban puzzles.[2]

FESS Process

[edit]

FESS works by discovering new cells in feature-space until a path is established between the start cell and the target cell. This is done by iterating over the cells and attempting to find unvisited neighbours. Moves are played in the domain space with the aim of discovering new feature-space cells.

[edit]

References

[edit]
  1. ^ Yaron Shoham; Jonathan Shaeffer (2020). The FESS Algorithm: A Feature Based Approach to Single-Agent Search (PDF). 2020 IEEE Conference on Games (CoG). Osaka, Japan: IEEE. doi:10.1109/CoG47356.2020.9231929.
  2. ^ Christopher Olson; Lars Wagner; Alexander Dockhorn (2023). Evolutionary Optimization of Baba Is You Agents (PDF). 2023 IEEE Congress on Evolutionary Computation (CEC). Chicago, USA: IEEE. p. 3. doi:10.1109/CEC53210.2023.10253977.