Automated planning and scheduling: Difference between revisions

Revision as of 04:50, 13 August 2023

Latest revision as of 18:28, 20 July 2025

(10 intermediate revisions by 7 users not shown)

Line 11:

{{More citations needed|section

| name = More citations needed section

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

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

| small = {{{small|}}}

}}

Line 55 ⟶ 54:

{{More citations needed|section

| name = More citations needed section

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

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

| small = {{{small|}}}

}}

Line 66 ⟶ 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 84 ⟶ 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===

Line 113 ⟶ 118:

==== 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|last1=Palacios|first1=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)|last1=Albore|first1=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 121 ⟶ 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 129 ⟶ 136:

; Lists

* [[List of SMT solvers]]

* [[List of constraint programming languages]]

* [[List of emerging technologies]]

* [[List of SMT solvers]]

* [[Outline of artificial intelligence]]