We speak of "contingent planning" when the environment is observable through sensors, which can be 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.
MichaeMichael 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.
