# Synthesis of Procedural Models for Deterministic Transition Systems

arXiv: https://arxiv.org/abs/2307.14368 · HTML: https://mlsanity.com/paper/2307.14368/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 58 references that are in the map.
- First posted on arXiv 25 Jul 2023.

## Builds on (most cited first, 11 of 11)

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Understanding the Power and Limitations of Teaching with Imperfect Knowledge](https://mlsanity.com/paper/2003.09712/) (2020)
- [Learning First-Order Representations for Planning from Black-Box States: New Results](https://mlsanity.com/paper/2105.10830/) (2021)
- [Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2103.14434/) (2021)
- [Safe Learning of Lifted Action Models](https://mlsanity.com/paper/2107.04169/) (2021)
- [Learning Partially Observable Deterministic Action Models](https://mlsanity.com/paper/1401.3437/) (2014)
- [Scaling-up Generalized Planning as Heuristic Search with Landmarks](https://mlsanity.com/paper/2205.04850/) (2022)
- [STRIPS Action Discovery](https://mlsanity.com/paper/2001.11457/) (2020)
- [Target Languages (vs. Inductive Biases) for Learning to Act and Plan](https://mlsanity.com/paper/2109.07195/) (2021)
- [Online Action Recognition](https://mlsanity.com/paper/2012.07464/) (2020)
- [Computing Programs for Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2205.06259/) (2022)

## Abstract (arXiv)

This paper introduces a general approach for synthesizing procedural models of the state-transitions of a given discrete system. The approach is general in that it accepts different target languages for modeling the state-transitions of a discrete system; different model acquisition tasks with different target languages, such as the synthesis of STRIPS action models, or the update rule of a cellular automaton, fit as particular instances of our general approach. We follow an inductive approach to synthesis meaning that a set of examples of state-transitions, represented as (pre-state, action, post-state) tuples, are given as input. The goal is to synthesize a structured program that, when executed on a given pre-state, outputs its associated post-state. Our synthesis method implements a combinatorial search in the space of well-structured terminating programs that can be built using a Random-Access Machine (RAM), with a minimalist instruction set, and a finite amount of memory. The combinatorial search is guided with functions that asses the complexity of the candidate programs, as well as their fitness to the given input set of examples.