Brothers in Arms? On AI Planning and Cellular Automata

Joerg Hoffmann 1 Nazim Fatès 1 Hector Palacios 2
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : AI Planning is concerned with the selection of actions towards achieving a goal. Research on cellular automata (CA) is concerned with the question how global behaviours arise from local updating rules relating a cell to its direct neighbours. While these two areas are disparate at first glance, we herein identify a problem that is interesting to both: How to reach a fixed point in an asynchronous CA where cells are updated one-by-one? Considering a particular local updating rule, we encode this problem into PDDL and show that the resulting benchmark is an interesting challenge for AI Planning. For example, our experiments determine that, very atypically, an optimal SAT-based planner outperforms state-of-the-art satisficing heuristic search planners. This points to a severe weakness of current heuristics because, as we prove herein, plans for this problem can always be constructed in time linear in the size of the automaton. Our proof of this starts from a high-level argument and then relies on using a planner for flexible case enumeration within localised parts of the argument. Besides the formal result itself, this establishes a new proof technique for CAs and thus demonstrates that the potential benefit of research crossing the two fields is mutual.
Type de document :
Communication dans un congrès
19th European Conference on Artificial Intelligence (ECAI'10), Aug 2010, Lisbon, Portugal. 2010
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
Contributeur : Joerg Hoffmann <>
Soumis le : vendredi 12 novembre 2010 - 17:59:10
Dernière modification le : mercredi 24 octobre 2018 - 15:24:04
Document(s) archivé(s) le : jeudi 30 juin 2011 - 12:59:20


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00491114, version 1



Joerg Hoffmann, Nazim Fatès, Hector Palacios. Brothers in Arms? On AI Planning and Cellular Automata. 19th European Conference on Artificial Intelligence (ECAI'10), Aug 2010, Lisbon, Portugal. 2010. 〈inria-00491114〉



Consultations de la notice


Téléchargements de fichiers