Brothers in Arms? On AI Planning and Cellular Automata

摘要: AI Planning is concerned with the selection of actions towards achieving a goal. Research on cellular automata (CA) question how global behaviours arise from local updating rules relating cell to its direct neighbours. While these two areas are disparate at first glance, we herein identify problem that interesting both: How reach fixed point in an asynchronous CA where cells updated one-by-one? Considering particular rule, encode this into PDDL and show resulting benchmark challenge for Planning. For example, our experiments determine that, very atypically, optimal SAT-based planner outperforms state-of-the-art satisficing heuristic search planners. This points severe weakness current heuristics because, as prove herein, plans can always be constructed time linear size automaton. Our proof starts high-level argument then relies using flexible case enumeration within localised parts ar gument. Besides formal result itself, establishes new technique CAs thus demonstrates potential benefit research crossing fields mutual.