Towards a Unified View of AI Planning and Reactive Synthesis

Authors

  • 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.

Downloads

Published

2021-05-25

How to Cite

Camacho, A., Bienvenu, M., & McIlraith, S. A. (2021). Towards a Unified View of AI Planning and Reactive Synthesis. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 58-67. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/3460