Content deleted Content added
Montgolfière (talk | contribs) Added {{Artificial intelligence}} sidebar |
adding links to references using Google Scholar |
||
Line 81:
===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]], that 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}}</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> Until now, the question was not answered what the difference is 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/profile/Lars_Karlsson3/publication/2927504_Conditional_Progressive_Planning_under_Uncertainty/links/0fcfd50ffdee0e75ad000000/Conditional-Progressive-Planning-under-Uncertainty.pdf}}</ref> A major advantage of conditional planning is the ability to handle [[Partial-order planning|partial plans]].<ref>{{cite techreport |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}}</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.
==== Contingent planning ====
Line 91:
==== 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|last=Palacios|first=Hector|volume=35|pages=623-675|last2=Geffner|first2=Hector|year=2009|url=https://www.jair.org/index.php/jair/article/download/10618/25394}}</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)|last=Albore|first=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|series=Lecture Notes in Computer Science|publisher=Springer Berlin Heidelberg|year=2000|isbn=9783540446576|doi=10.1007/10720246_24|url=https://link.springer.com/chapter/10.1007/10720246_24|access-date=2019-02-10|pages=308–318}}</ref>, and 2EXPTIME-complete when the initial situation is uncertain, and there is non-deternimism in the actions outcomes<ref name="rintanen04"/>.
== Deployment of planning systems ==
| |||