On the Expressive Power of Planning Formalisms in Conjunction with LTL

Authors

  • Songtuan Lin The Australian National University
  • Pascal Bercher The Australian National University

Keywords:

Linear Temporal Logic, STRIPS Planning, HTN Planning

Abstract

Linear Temporal Logic (LTL) has been widely employed in various planning formalisms, e.g., in the STRIPS formalism, in order to specify constraints over state trajectories in a planning problem. In this paper, we investigate the expressive power of two planning formalisms in conjunction with LTL that are most commonly seen in non-hierarchical planning and hierarchical planning respectively, namely the STRIPS formalism and the Hierarchical Task Network (HTN) formalism. We do so by interpreting the set of all solutions to a planning problem as a formal language and comparing it with other formal ones, e.g., star-free languages. Our results provide an in-depth insight into the theoretical properties of the investigated planning formalisms and henceforth explore the common structure shared by solutions to planning problems in certain planning formalisms.

Downloads

Published

2022-06-13

How to Cite

Lin, S., & Bercher, P. (2022). On the Expressive Power of Planning Formalisms in Conjunction with LTL. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 231-240. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19806