Automated planning and scheduling

Automated planning and scheduling, sometimes denoted as simply AI planning,[1] is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles.

Unlike classical control and classification problems, the solutions are complex and must be discovered and optimized in multidimensional space.

Solutions usually resort to iterative trial and error processes commonly seen in artificial intelligence.

Typical examples of domains are block-stacking, logistics, workflow management, and robot task planning.

Temporal planning is closely related to scheduling problems when uncertainty is involved and can also be understood in terms of timed automata.

With partial observability, probabilistic planning is similarly solved with iterative methods, but using a representation of the value functions defined for the space of beliefs instead of states.

A difference to the more common reward-based planning, for example corresponding to MDPs, preferences don't necessarily have a precise numerical value.

That means, the notation of a behavior graph contains action commands, but no 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.

It is very similar to program synthesis, which means a planner generates sourcecode which can be executed by an interpreter.

Michael L. Littman showed in 1998 that with branching actions, the planning problem becomes EXPTIME-complete.

[9][10] A particular case of contiguous planning is represented by FOND problems - for "fully-observable and non-deterministic".

Haslum and Jonsson have demonstrated that the problem of conformant planning is EXPSPACE-complete,[14] and 2EXPTIME-complete when the initial situation is uncertain, and there is non-determinism in the actions outcomes.