Automata-Theoretic Approach to Planning for Temporally Extended Goals
作者： Giuseppe De Giacomo , Moshe Y. Vardi
DOI: 10.1007/10720246_18
关键词: Büchi automaton 、 Worst-case complexity 、 Computer science 、 Observable 、 Dynamical system 、 Complete information 、 Transition system 、 Automaton 、 Theoretical computer science 、 Algorithm
摘要: We study an automata-theoretic approach to planning for temporally extended goals. Specifically, we devise techniques based on nonemptiness of Buchi automata infinite words, synthesize sequential and conditional plans in a generalized setting which have that: goals are general temporal properties desired execution; dynamic systems represented by finite transition systems; incomplete information the initial situation is allowed; states only partially observable. prove that proposed optimal wrt worst case complexity problem. Thanks scalability algorithms, presented here promise be applicable fairly large systems, notwithstanding intrinsic
springer.com
core.ac.uk
uniroma1.it 参考文章(44)
Edwin P. D. Pednault, ADL: exploring the middle ground between STRIPS and the situation calculus principles of knowledge representation and reasoning. pp. 324- 332 ,(1989)
Christer Bäckström, Equivalence and Tractability Results for SAS+ Planning. principles of knowledge representation and reasoning. pp. 126- 137 ,(1992)
F. Kabanza, R. St-Denis, M. Barbeau, Synthesizing plant controllers using real-time goals international joint conference on artificial intelligence. pp. 791- 798 ,(1995)
Blai Bonet, High-Level Planning and Control with Incomplete Information Using POMDP's ,(1998)
Mark Drummond, Situated control rules principles of knowledge representation and reasoning. pp. 103- 113 ,(1989)
Orna Kupfermant, Moshe Y. Vardit, Synthesis with Incomplete Informatio Springer, Dordrecht. pp. 109- 127 ,(2000) , 10.1007/978-94-015-9586-5_6
Daniel S. Weld, Keith Golden, Representing sensing actions: the middle ground revisited principles of knowledge representation and reasoning. pp. 174- 185 ,(1996)
Oren Etzioni, Daniel S. Weld, Denise Draper, Steve Hanks, Mike Williamson, Neal Lesh, An Approach to Planning with Incomplete Information. principles of knowledge representation and reasoning. pp. 115- 125 ,(1992)
Sérgio Vale Aguiar Campos, Kenneth L. McMillan, Edmund M. Clarke, Vassili Hartonas-Garmhausen, Symbolic Model Checking ,(1993)
Moshe Y. Vardi, An automata-theoretic approach to linear temporal logic Proceedings of the VIII Banff Higher order workshop conference on Logics for concurrency : structure versus automata: structure versus automata. pp. 238- 266 ,(1996) , 10.1007/3-540-60915-6_6