Learning-Based Bounded Synthesis for Semi-MDPs With LTL Specifications
Open Access
- 25 April 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Letters
- Vol. 6, 2557-2562
Abstract
This letter proposes a learning-based bounded synthesis for a semi-Markov decision process (SMDP) with a linear temporal logic (LTL) specification. In the product of the SMDP and the deterministic K-co-Büchi automaton (dKcBA) converted from the LTL specification, we learn both the winning region of satisfying the LTL specification and the dynamics therein based on reinforcement learning and Bayesian inference. Then, we synthesize an optimal policy satisfying the following two conditions. (1) It maximizes the probability of reaching the wining region. (2) It minimizes a long-term risk for the dwell time within the winning region. The minimization of the long-term risk is done based on the estimated dynamics and a value iteration. We show that, if the discount factor is sufficiently close to one, the synthesized policy converges to the optimal policy as the number of the data obtained by the exploration goes to the infinity.Keywords
All Related Versions
Funding Information
- Japan Science and Technology Agency (JST)-ERATO HASUO Project, Japan (JPMJER1603)
- JST CREST, Japan (JPMJCR2012)
This publication has 8 references indexed in Scilit:
- Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning2020
- Reinforcement Learning of Control Policy for Linear Temporal Logic Specifications Using Limit-Deterministic Generalized Büchi AutomataIEEE Control Systems Letters, 2020
- A formal methods approach to interpretable reinforcement learning for robotic planningScience Robotics, 2019
- Omega-Regular Objectives in Model-Free Reinforcement Learning2019
- Reinforcement learning with temporal logic rewards2017
- A learning based approach to control synthesis of Markov decision processes for linear temporal logic specifications2014
- Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints2014
- Antichains and compositional algorithms for LTL synthesisFormal Methods in System Design, 2011