Revision as of 10:39, 30 November 2019 edit Citation bot (talk \| contribs) Bots 5,868,353 edits m Alter: template type, url. Add: year, volume, doi. Removed URL that duplicated unique identifier. Removed parameters. Some additions/deletions were actually parameter name changes.\| You can use this bot yourself. Report bugs here.\| Activated by User:Nemo bis \| via #UCB_webform ← Previous edit		Revision as of 12:02, 9 January 2020 edit undo 195.192.250.118 (talk) →Contingent planning: typo: "can be at faulty" -> "can be faulty" Next edit →
Line 86: ==== Contingent planning ==== We speak of "contingent planning" when the environment is observable through sensors, which can be at faulty. It is thus a situation where the planning agent acts under incomplete information. For a contingent planning problem, a plan is no longer a sequence of actions but a [[decision tree]] because each step of the plan is represented by a set of states rather than a single perfectly observable state, as in the case of classical planning.<ref>{{Cite conference\|conference=International Joint Conference of Artificial Intelligence (IJCAI)\|year=2009\|author1= Alexandre Albore\| author2 = Hector Palacios\| author3 = Hector Geffner\| title =A Translation-Based Approach to Contingent Planning\| publisher=AAAI\|___location =Pasadena, CA\|url=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/download/587/852}}</ref> The selected actions depend on the state of the system. For example, if it rains, the agent chooses to take the umbrella, and if it doesn't, they may choose not to take it. Mikael 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.

Automated planning and scheduling: Difference between revisions