Automated planning

Automated planning is a subfield of Artificial Intelligence concerned with developing computer algorithms to generate plans, typically for execution by a robot or other agent. A typical planner takes three inputs: a description of the initial state of the world, a description of the desired goal, and a set of possible actions (all encoded in a formal language such as STRIPS ). The difficulty of planning is dependent on the simplifying assumptions employed, e.g. atomic time, deterministic time, complete observability, etc.

Classical planners make all these assumptions and have been studied most fully. Some popular techniques include: forward-chaing state-space search, backward-chaining state-space search, search through plan space, graphplan, and compilation to propositional satisfiability.

If the assumption of determinism is dropped and a probabalistic model of uncertainty is adopted, then this leads to the problem of policy generation for a Markov decision problem (MDP) or (in the general case) partially-observable Markov decision problem (POMDP ).