LTLf and LDLf Synthesis under Partial Observability
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1044-1049.
Abstract
In this paper, we study synthesis under partial observability for logical specifications over finite traces expressed in LTLf/LDLf. This form of synthesis can be seen as a generalization of planning under partial observability in nondeterministic domains, which is known to be 2EXPTIME-complete. We start by showing that the usual belief-state construction used in planning under partial observability works also for general LTLf/LDLf synthesis, though with a jump in computational complexity from 2EXPTIME to 3EXPTIME. Then we show that the belief-state construction can be avoided in favor of a direct automata construction which exploits projection to hide unobservable propositions. This allow us to prove that the problem remains 2EXPTIME-complete. The new synthesis technique proposed is effective and readily implementable.
@inproceedings{ijcai2016p152,
title = {LTLf and LDLf Synthesis under Partial Observability},
author = {De Giacomo, Giuseppe and Vardi, Moshe Y.},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {1044--1049},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/152},
}
TY - CPAPER TI - LTLf and LDLf Synthesis under Partial Observability AU - De Giacomo, Giuseppe AU - Vardi, Moshe Y. T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 1044 EP - 1049 UR - https://ijcai.org/proceedings/2016/152 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
