Content deleted Content added
Disambiguated: STRIPS → Stanford Research Institute Problem Solver (3) |
m Cleaned up using AutoEd |
||
Line 19:
The simplest possible planning problem, known as the Classical Planning Problem, is determined by:
* a unique known initial state,
* durationless actions,
* deterministic actions,
* which can be taken only one at a time,
* and a single agent.
Since the initial state is known unambiguously, and all actions are deterministic, the state of the world after any sequence of actions can be accurately predicted, and the question of observability is irrelevant for classical planning.
Line 32:
Discrete-time [[Markov decision process]]es (MDP) are planning problems with:
* durationless actions,
* nondeterministic actions with probabilities,
* full observability,
* maximization of a reward function,
* and a single agent.
Line 51:
An alternative language for describing planning problems is that of [[hierarchical task network]]s, in which a set of tasks is given, and each task can be either realized by a primitive action or decomposed into a set of other tasks. This does not necessarily involve state variables, although in more realistic applications state variables simplify the description of task networks.
==
===Classical planning===
Line 80:
===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 [[
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}}</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}}</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}}</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.
Line 103:
* [[Outline of artificial intelligence]]
==
{{reflist}}
==Further reading==
* {{cite web|url=http://www.eetn.gr/index.php/eetn-publications/ai-research-in-greece/planning-and-scheduling |last=Vlahavas |first=I |title=Planning and Scheduling |journal=EETN |deadurl=yes |archiveurl=https://web.archive.org/web/20131222165824/http://www.eetn.gr/index.php/eetn-publications/ai-research-in-greece/planning-and-scheduling |archivedate=2013-12-22 |df= }}
== External links ==
| |||