Cargando…
A learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition
The traditional synthesis problem is usually solved by constructing a system that fulfills given specifications. The system is constantly interacting with the environment and is opposed to the environment. The problem can be further regarded as solving a two-player game (the system and its environme...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
PeerJ Inc.
2022
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9455281/ https://www.ncbi.nlm.nih.gov/pubmed/36091983 http://dx.doi.org/10.7717/peerj-cs.1094 |
_version_ | 1784785548395675648 |
---|---|
author | Zhao, Wei Liu, Zhiming |
author_facet | Zhao, Wei Liu, Zhiming |
author_sort | Zhao, Wei |
collection | PubMed |
description | The traditional synthesis problem is usually solved by constructing a system that fulfills given specifications. The system is constantly interacting with the environment and is opposed to the environment. The problem can be further regarded as solving a two-player game (the system and its environment). Meanwhile, stochastic games are often used to model reactive processes. With the development of the intelligent industry, these theories are extensively used in robot patrolling, intelligent logistics, and intelligent transportation. However, it is still challenging to find a practically feasible synthesis algorithm and generate the optimal system according to the existing research. Thus, it is desirable to design an incentive mechanism to motivate the system to fulfill given specifications. This work studies the learning-based approach for strategy synthesis of reward asynchronous probabilistic games against linear temporal logic (LTL) specifications in a probabilistic environment. An asynchronous reward mechanism is proposed to motivate players to gain maximized rewards by their positions and choose actions. Based on this mechanism, the techniques of the learning theory can be applied to transform the synthesis problem into the problem of computing the expected rewards. Then, it is proven that the reinforcement learning algorithm provides the optimal strategies that maximize the expected cumulative reward of the satisfaction of an LTL specification asymptotically. Finally, our techniques are implemented, and their effectiveness is illustrated by two case studies of robot patrolling and autonomous driving. |
format | Online Article Text |
id | pubmed-9455281 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2022 |
publisher | PeerJ Inc. |
record_format | MEDLINE/PubMed |
spelling | pubmed-94552812022-09-09 A learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition Zhao, Wei Liu, Zhiming PeerJ Comput Sci Data Mining and Machine Learning The traditional synthesis problem is usually solved by constructing a system that fulfills given specifications. The system is constantly interacting with the environment and is opposed to the environment. The problem can be further regarded as solving a two-player game (the system and its environment). Meanwhile, stochastic games are often used to model reactive processes. With the development of the intelligent industry, these theories are extensively used in robot patrolling, intelligent logistics, and intelligent transportation. However, it is still challenging to find a practically feasible synthesis algorithm and generate the optimal system according to the existing research. Thus, it is desirable to design an incentive mechanism to motivate the system to fulfill given specifications. This work studies the learning-based approach for strategy synthesis of reward asynchronous probabilistic games against linear temporal logic (LTL) specifications in a probabilistic environment. An asynchronous reward mechanism is proposed to motivate players to gain maximized rewards by their positions and choose actions. Based on this mechanism, the techniques of the learning theory can be applied to transform the synthesis problem into the problem of computing the expected rewards. Then, it is proven that the reinforcement learning algorithm provides the optimal strategies that maximize the expected cumulative reward of the satisfaction of an LTL specification asymptotically. Finally, our techniques are implemented, and their effectiveness is illustrated by two case studies of robot patrolling and autonomous driving. PeerJ Inc. 2022-09-05 /pmc/articles/PMC9455281/ /pubmed/36091983 http://dx.doi.org/10.7717/peerj-cs.1094 Text en © 2022 Zhao and Liu https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, reproduction and adaptation in any medium and for any purpose provided that it is properly attributed. For attribution, the original author(s), title, publication source (PeerJ Computer Science) and either DOI or URL of the article must be cited. |
spellingShingle | Data Mining and Machine Learning Zhao, Wei Liu, Zhiming A learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition |
title | A learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition |
title_full | A learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition |
title_fullStr | A learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition |
title_full_unstemmed | A learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition |
title_short | A learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition |
title_sort | learning-based synthesis approach of reward asynchronous probabilistic games against the linear temporal logic winning condition |
topic | Data Mining and Machine Learning |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9455281/ https://www.ncbi.nlm.nih.gov/pubmed/36091983 http://dx.doi.org/10.7717/peerj-cs.1094 |
work_keys_str_mv | AT zhaowei alearningbasedsynthesisapproachofrewardasynchronousprobabilisticgamesagainstthelineartemporallogicwinningcondition AT liuzhiming alearningbasedsynthesisapproachofrewardasynchronousprobabilisticgamesagainstthelineartemporallogicwinningcondition AT zhaowei learningbasedsynthesisapproachofrewardasynchronousprobabilisticgamesagainstthelineartemporallogicwinningcondition AT liuzhiming learningbasedsynthesisapproachofrewardasynchronousprobabilisticgamesagainstthelineartemporallogicwinningcondition |