Content deleted Content added
Changing short description from "branch of artificial intelligence that concerns realization of strategies action sequences" to "Branch of artificial intelligence" (Shortdesc helper) |
Tag: Reverted |
||
Line 114:
Michael L. Littman showed in 1998 that with branching actions, the planning problem becomes [[EXPTIME]]-complete.<ref>{{cite conference|first1=Michael L.|last1=Littman|title=Probabilistic Propositional Planning: Representations and Complexity|conference=Fourteenth National Conference on Artificial Intelligence|publisher=MIT Press|year=1997|url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.3076|access-date=2019-02-10|pages=748–754}}</ref><ref name="rintanen04">{{cite conference| author1 = Jussi Rintanen| title = Complexity of Planning with Partial Observability| publisher=AAAI | year =2004|url=http://www.aaai.org/Papers/ICAPS/2004/ICAPS04-041.pdf|conference=Int. Conf. Automated Planning and Scheduling}}</ref> A particular case of contiguous planning is represented by FOND problems - for "fully-observable and non-deterministic". If the goal is specified in LTLf (linear time logic on finite trace) then the problem is always EXPTIME-complete<ref>{{cite conference|first1=Giuseppe |last1=De Giacomo|first2=Sasha|last2=Rubin|title=Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals|year=2018|conference=IJCAI|url=https://www.ijcai.org/proceedings/2018/657|access-date=2018-07-17}}</ref> and 2EXPTIME-complete if the goal is specified with LDLf.
==== Conformant planning : - (ALGORITHM) ====
Conformant planning is when the agent is uncertain about the state of the system, and it cannot make any observations. The agent then has beliefs about the real world, but cannot verify them with sensing actions, for instance. These problems are solved by techniques similar to those of classical planning,<ref>{{Cite journal|title=Compiling uncertainty away in conformant planning problems with bounded width|journal=Journal of Artificial Intelligence Research|last=Palacios|first=Hector|volume=35|pages=623–675|last2=Geffner|first2=Hector|year=2009|url=https://www.jair.org/index.php/jair/article/download/10618/25394|doi=10.1613/jair.2708|doi-access=free}}</ref><ref>{{Cite conference|title=Effective heuristics and belief tracking for planning with incomplete information|conference=Twenty-First International Conference on Automated Planning and Scheduling (ICAPS)|last=Albore|first=Alexandre|last2=Ramírez|first2=Miquel|year=2011|last3=Geffner|first3=Hector|url=https://www.aaai.org/ocs/index.php/ICAPS/ICAPS11/paper/viewFile/2709/3129}}</ref> but where the state space is exponential in the size of the problem, because of the uncertainty about the current state. A solution for a conformant planning problem is a sequence of actions. Haslum and Jonsson have demonstrated that the problem of conformant planning is [[EXPSPACE]]-complete,<ref>{{cite journal|first1=Patrik|last1=Haslum|first2=Peter|last2=Jonsson|title=Some Results on the Complexity of Planning with Incomplete Information|journal=Recent Advances in AI Planning|volume=1809|series=Lecture Notes in Computer Science|publisher=Springer Berlin Heidelberg|year=2000|isbn=9783540446576|doi=10.1007/10720246_24|pages=308–318}}</ref> and 2EXPTIME-complete when the initial situation is uncertain, and there is non-determinism in the actions outcomes.<ref name="rintanen04"/>
| |||