Towards a Unified View of AI Planning and Reactive Synthesis

  • Alberto Camacho University of Toronto
  • Meghyn Bienvenu CNRS University of Bordeaux
  • Sheila A. McIlraith University of Toronto

Abstract

Automated planning and reactive synthesis are well-established techniques for sequential decision making. In this paper we examine a collection of AI planning problems with temporally extended goals, specified in Linear Temporal Logic (LTL). We characterize these so-called LTL planning problems as two-player games and thereby establish their correspondence to reactive synthesis problems. This unifying view furthers our understanding of the relationship between plan and program synthesis, establishing complexity results for LTL planning tasks. Building on this correspondence, we identify restricted fragments of LTL for which plan synthesis can be realized more efficiently.

Published
2019-07-06