Automated planning and scheduling: Difference between revisions

Revision as of 07:47, 14 May 2020

Revision as of 22:21, 19 October 2020

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]], thatwhich 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> 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 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.