The SOS Algorithm

SOS is an algorithm which automatically designs finite state machines (FSM) capable of solving a given task. The interpretability of FSM makes SOS particularly suitable for problems involving the design of controllers. SOS uses a variation of reinforcement learning applied to FSM and an island-based genetic algorithm.


  • Wiering and Schmidhuber Maze [ avi ]
  • The Santa Fe Trail (learning) [ avi ]
  • The Santa Fe Trail [ avi ]

B. Mesot, E. Sanchez, C-A. Pena, and A. Perez-Uribe. SOS++: Finding smart behaviours using learning and evolution. In Proceedings of the 8th International Conference on Artificial Life, pages 264–273, 2002. [ bib ] [ pdf ]

E. Sanchez, A. Perez-Uribe, and B. Mesot. Solving partially observable problems by evolution and learning of finite state machines. In Proceedings of the 4th International Conference on Evolvable Systems, 2001. [ bib ] [ pdf ]