Hybrid Compositional Reasoning for Reactive Synthesis from Finite-Horizon Specifications

Authors

  • Suguman Bansal Rice University
  • Yong Li Chinese Academy of Sciences
  • Lucas Tabajara Rice University
  • Moshe Vardi Rice University

DOI:

https://doi.org/10.1609/aaai.v34i06.6528

Abstract

LTLf synthesis is the automated construction of a reactive system from a high-level description, expressed in LTLf, of its finite-horizon behavior. So far, the conversion of LTLf formulas to deterministic finite-state automata (DFAs) has been identified as the primary bottleneck to the scalabity of synthesis. Recent investigations have also shown that the size of the DFA state space plays a critical role in synthesis as well.

Therefore, effective resolution of the bottleneck for synthesis requires the conversion to be time and memory performant, and prevent state-space explosion. Current conversion approaches, however, which are based either on explicit-state representation or symbolic-state representation, fail to address these necessities adequately at scale: Explicit-state approaches generate minimal DFA but are slow due to expensive DFA minimization. Symbolic-state representations can be succinct, but due to the lack of DFA minimization they generate such large state spaces that even their symbolic representations cannot compensate for the blow-up.

This work proposes a hybrid representation approach for the conversion. Our approach utilizes both explicit and symbolic representations of the state-space, and effectively leverages their complementary strengths. In doing so, we offer an LTLf to DFA conversion technique that addresses all three necessities, hence resolving the bottleneck. A comprehensive empirical evaluation on conversion and synthesis benchmarks supports the merits of our hybrid approach.

Downloads

Published

2020-04-03

How to Cite

Bansal, S., Li, Y., Tabajara, L., & Vardi, M. (2020). Hybrid Compositional Reasoning for Reactive Synthesis from Finite-Horizon Specifications. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 9766-9774. https://doi.org/10.1609/aaai.v34i06.6528

Issue

Section

AAAI Technical Track: Planning, Routing, and Scheduling