Faster and Better Simple Temporal Problems

Authors

  • Dario Ostuni University of Verona, Italy
  • Alice Raffaele University of Trento, Italy
  • Romeo Rizzi University of Verona, Italy
  • Matteo Zavatteri University of Verona, Italy

Keywords:

Temporal Planning, Scheduling, Satisfiability, Satisfiability Modulo Theories

Abstract

In this paper we give a structural characterization and extend the tractability frontier of the Simple Temporal Problem (STP) by defining the class of the Extended Simple Temporal Problem (ESTP), which augments STP with strict inequalities and monotone Boolean formulae on inequations (i.e., formulae involving the operations of conjunction, disjunction and parenthesization). A polynomial-time algorithm is provided to solve ESTP, faster than previous state-of-the-art algorithms for other extensions of STP that had been considered in the literature, all encompassed by ESTP. We show the practical competitiveness of our approach through a proof-of-concept implementation and an experimental evaluation involving also state-of-the-art SMT solvers.

Downloads

Published

2021-05-18

How to Cite

Ostuni, D., Raffaele, A., Rizzi, R., & Zavatteri, M. (2021). Faster and Better Simple Temporal Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11913-11920. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17415

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling