Automated planning and scheduling: Difference between revisions

Revision as of 16:54, 25 November 2021

Latest revision as of 18:28, 20 July 2025

(22 intermediate revisions by 16 users not shown)

Line 1:

{{Short description|Branch of artificial intelligence}}

{{More footnotes|date=January 2012}}

{{Artificial intelligence|Major goals}}

'''Automated planning and scheduling''', sometimes denoted as simply '''AI planning''',<ref>{{Citation | last1=Ghallab | firstfirst1=Malik | last2=Nau | first2=Dana S. | last3=Traverso | first3=Paolo | title=Automated Planning: Theory and Practice | publisher=[[Morgan Kaufmann]] | year=2004 | url=http://www.laas.fr/planning/ | isbn=1-55860-856-7 | access-date=2008-08-20 | archive-date=2009-08-24 | archive-url=https://web.archive.org/web/20090824103124/http://www.laas.fr/planning/ | url-status=live }}</ref> is a branch of [[artificial intelligence]] that concerns the realization of [[strategy|strategies]] or action sequences, typically for execution by [[intelligent agent]]s, [[autonomous robot]]s and [[unmanned vehicle]]s. Unlike classical [[control system|control]] and [[Statistical classification|classification]] problems, the solutions are complex and must be discovered and optimized in multidimensional space. Planning is also related to [[decision theory]].

In known environments with available models, planning can be done offline. Solutions can be found and evaluated prior to execution. In dynamically unknown environments, the [[strategy]] often needs to be revised online. Models and policies must be adapted. Solutions usually resort to iterative [[trial and error]] processes commonly seen in [[artificial intelligence]]. These include [[dynamic programming]], [[reinforcement learning]] and [[combinatorial optimization]]. Languages used to describe planning and scheduling are often called [[action language]]s.

Line 10 ⟶ 11:

{{More citations needed|section

| name = More citations needed section

| find = {{#if:{{{find|}}}|{{{find|}}}|none}}

|date=February 2021| talk = {{{talk|}}}

| small = {{{small|}}}

}}

Line 46:

* and a single agent.

When full observability is replaced by partial observability, planning corresponds to a [[partially observable Markov decision process]] (POMDP).

If there are more than one agent, we have [[multi-agent planning]], which is closely related to [[game theory]].

Line 54:

{{More citations needed|section

| name = More citations needed section

| find = {{#if:{{{find|}}}|{{{find|}}}|none}}

|date=February 2021| talk = {{{talk|}}}

| small = {{{small|}}}

}}

Line 65 ⟶ 64:

{{More citations needed|section

| name = More citations needed section

| find = {{#if:{{{find|}}}|{{{find|}}}|none}}

|date=February 2021| talk = {{{talk|}}}

| small = {{{small|}}}

}}

The most commonly used languages for representing planning domains and specific planning problems, such as [[Stanford Research Institute Problem Solver|STRIPS]] and [[Planning Domain Definition Language|PDDL]] for Classical Planning, are based on state variables. Each possible state of the world is an assignment of values to the state variables, and actions determine how the values of the state variables change when that action is taken. Since a set of state variables induce a state space that has a size that is exponential in the set, planning, similarly to many other computational problems, suffers from the [[curse of dimensionality]] and the [[combinatorial explosion]].

Line 83 ⟶ 80:

{{See also|Sussman anomaly}}

===Action model learning===

Creating ___domain models is difficult, takes a lot of time, and can easily lead to mistakes. To help with this, several methods have been developed to automatically learn full or partial ___domain models from given observations.

<ref>{{cite conference |author=Callanan, Ethan and De Venezia, Rebecca and Armstrong, Victoria and Paredes, Alison and Chakraborti, Tathagata and Muise, Christian |title=MACQ: A Holistic View of Model Acquisition Techniques |conference=ICAPS Workshop on Knowledge Engineering for Planning and Scheduling (KEPS) |year=2022 |url=https://icaps22.icaps-conference.org/workshops/KEPS/KEPS-22_paper_4962.pdf}}</ref>

<ref>{{cite journal |author=Aineto, Diego and Jiménez Celorrio, Sergio and Onaindia, Eva |title=Learning action models with minimal observability |journal=Artificial Intelligence |volume=275 |pages=104–137 |year=2019 |doi=10.1016/j.artint.2019.05.003 |url=https://doi.org/10.1016/j.artint.2019.05.003|doi-access=free |hdl=10251/144560 |hdl-access=free }}</ref>

<ref>{{cite journal |author=Jiménez, Sergio and de la Rosa, Tomás and Fernández, Susana and Fernández, Fernando and Borrajo, Daniel |title=A review of machine learning for automated planning |journal=The Knowledge Engineering Review |volume=27 |issue=4 |pages=433–467 |year=2012 |doi=10.1017/S026988891200001X |url=https://doi.org/10.1017/S026988891200001X|url-access=subscription }}</ref>

*Read more: [[Action model learning]]

=== Reduction to other problems ===

* reduction to the [[propositional satisfiability]] problem ([[satplan]]).

* reduction to [[Modelmodel checking]] - both are essentially problems of traversing state spaces, and the classical planning problem corresponds to a subclass of model checking problems.

===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 |citeseerx=10.1.1.107.1065 }}</ref>

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.

Temporal planning can also be understood in terms of [[timed automaton|timed automata]].

===Probabilistic planning===

Line 104 ⟶ 108:

===Conditional planning===

Deterministic planning was introduced with the [[Stanford Research Institute Problem Solver|STRIPS]] planning system, which is a hierarchical planner. Action names are ordered in a sequence and this is a plan for the robot. Hierarchical planning can be compared with an automatic generated [[Behavior tree (artificial intelligence, robotics and control)|behavior tree]].<ref>{{cite journal |title=Building a Planner: A Survey of Planning Systems Used in Commercial Video Games |author=Neufeld, Xenija and Mostaghim, Sanaz and Sancho-Pradel, Dario and Brand, Sandy |journal=IEEE Transactions on Games |year=2017 |publisher=IEEE}}</ref> The disadvantage is, that a normal behavior tree is not so expressive like a computer program. That means, the notation of a behavior graph contains action commands, but no [[Loop (computing)|loops]] or if-then-statements. Conditional planning overcomes the bottleneck and introduces an elaborated notation which is similar to a [[control flow]], known from other programming languages like [[Pascal (programming language)|Pascal]]. It is very similar to [[program synthesis]], which means a planner generates sourcecode which can be executed by an interpreter.<ref>{{cite conference |title=Short-term human robot interaction through conditional planning and execution |author=Sanelli, Valerio and Cashmore, Michael and Magazzeni, Daniele and Iocchi, Luca |conference=Proc. of International Conference on Automated Planning and Scheduling (ICAPS) |year=2017 |url=https://www.aaai.org/ocs/index.php/ICAPS/ICAPS17/paper/download/15750/15146 |access-date=2019-08-16 |archive-date=2019-08-16 |archive-url=https://web.archive.org/web/20190816172319/https://www.aaai.org/ocs/index.php/ICAPS/ICAPS17/paper/download/15750/15146 |url-status=live }}</ref>

An early example of a conditional planner is “Warplan-C” which was introduced in the mid 1970s.<ref>{{cite conference |title=Conditional nonlinear planning |author=Peot, Mark A and Smith, David E |conference=Artificial Intelligence Planning Systems |pages=189–197 |year=1992 |publisher=Elsevier|url=https://sites.google.com/site/markpeot2/peot92conditional.pdf}}</ref> What is the difference between a normal sequence and a complicated plan, which contains if-then-statements? It has to do with uncertainty at [[Run time (program lifecycle phase)|runtime]] of a plan. The idea is that a plan can react to [[Soft sensor|sensor signals]] which are unknown for the planner. The planner generates two choices in advance. For example, if an object was detected, then action A is executed, if an object is missing, then action B is executed.<ref>{{cite conference |title=Conditional progressive planning under uncertainty |author=Karlsson, Lars |conference=IJCAI |pages=431–438 |year=2001|url=https://www.researchgate.net/publication/2927504}}</ref> A major advantage of conditional planning is the ability to handle [[Partial-order planning|partial plans]].<ref>{{cite techreporttech report |title=A survey of planning in intelligent agents: from externally motivated to internally motivated systems |author=Liu, Daphne Hao |year=2008 |institution=Technical Report TR-2008-936, Department of Computer Science, University of Rochester |url=http://urresearch.rochester.edu/fileDownloadForInstitutionalItem.action?itemId=5342&itemFileId=8258 |access-date=2019-08-16 |archive-date=2023-03-15 |archive-url=https://web.archive.org/web/20230315180735/https://urresearch.rochester.edu/fileDownloadForInstitutionalItem.action?itemId=5342&itemFileId=8258 |url-status=live }}</ref> An agent is not forced to plan everything from start to finish but can divide the problem into [[Chunking (computational linguistics)|chunks]]. This helps to reduce the state space and solves much more complex problems.

==== ContingentContingency planning ====

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|access-date=2019-07-03|archive-date=2019-07-03|archive-url=https://web.archive.org/web/20190703164319/http://www.aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/download/587/852|url-status=dead}}</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.

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|archive-date=2019-02-12|archive-url=https://web.archive.org/web/20190212011907/http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.3076|url-status=live}}</ref><ref name="rintanen04">{{cite conference| author1 = Jussi Rintanen| title = Complexity of Planning with Partial Observability| publisher =AAAI AAAI| year = 2004| url = http://www.aaai.org/Papers/ICAPS/2004/ICAPS04-041.pdf| conference = Int. Conf. Automated Planning and Scheduling| access-date = 2019-07-03| archive-date = 2020-10-31| archive-url = https://web.archive.org/web/20201031014424/https://www.aaai.org/Papers/ICAPS/2004/ICAPS04-041.pdf| url-status = live}}</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|archive-date=2018-07-17|archive-url=https://web.archive.org/web/20180717154447/https://www.ijcai.org/proceedings/2018/657|url-status=live}}</ref> and 2EXPTIME-complete if the goal is specified with LDLf.

==== 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|access-date=2019-08-16|archive-date=2020-04-27|archive-url=https://web.archive.org/web/20200427045035/https://www.jair.org/index.php/jair/article/download/10618/25394|url-status=live|arxiv=1401.3468}}</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|access-date=2019-08-16|archive-date=2017-07-06|archive-url=https://web.archive.org/web/20170706012917/https://aaai.org/ocs/index.php/ICAPS/ICAPS11/paper/viewFile/2709/3129/|url-status=live}}</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 journalbook |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 |quote=conference: Recent Advances in AI Planning}}</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 ==

Line 122 ⟶ 126:

* [[Action description language]]

* [[Action model learning]]

* [[Actor model]]

* [[Applications of artificial intelligence]]

* [[Constraint satisfaction problem]]

* [[International Conference on Automated Planning and Scheduling]]

* [[Reactive planning]]

* [[Scheduling (computing)]]

Line 130 ⟶ 136:

; Lists

* [[List of SMT solvers]]

* [[List of constraint programming languages]]

* [[List of emerging technologies]]

* [[List of SMT solvers]]

* [[Outline of artificial intelligence]]