Automated planning and scheduling: Difference between revisions

Revision as of 10:44, 27 March 2022

Revision as of 14:52, 10 November 2022

Line 91:

===Temporal planning===

Temporal planning can be solved with methods similar to classical planning. The main difference is, because of the possibility of several, temporally overlapping actions with a duration being taken concurrently, that the definition of a state has to include information about the current absolute time and how far the execution of each active action has proceeded. Further, in planning with rational or real time, the state space may be infinite, unlike in classical planning or planning with integer time. Temporal planning is closely related to [[scheduling]] problems when uncertainty is involved and can also be understood in terms of [[timed automaton|timed automata]]. The Simple Temporal Network with Uncertainty (STNU) is a scheduling problem which involves controllable actions, uncertain events and temporal constraints. Dynamic Controllability for such problems is a type of scheduling which requires a temporal planning strategy to activate controllable actions reactively as uncertain events are observed so that all constraints are guaranteed to be satisfied. <ref>{{cite journal |last1=Vidal |first1=Thierry |title=Handling contingency in temporal constraint networks: from consistency to controllabilities |journal=Journal of Experimental & Theoretical Artificial Intelligence |date=January 1999 |volume=11 |issue=1 |page=23--45 |doi=10.1080/095281399146607 |url=https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.1065&rep=rep1&type=pdf }}</ref>

===Probabilistic planning===

Line 113:

==== Conformant planning ====

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|lastlast1=Palacios|firstfirst1=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)|lastlast1=Albore|firstfirst1=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"/>

== Deployment of planning systems ==