automated planning and scheduling automated planning and scheduling sometimes denoted as simply ai planning 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 planning is also related to decision theory in known environments with available models planning can be done offline solutions can be found and evaluated prior to execution in dynamically unknown environments the strategy often needs to be revised online models and policies must be adapted solutions usually resort to iterative trial and error processes commonly seen in artificial intelligence these include dynamic programming reinforcement learning and combinatorial optimization languages used to describe planning and scheduling are often called action languages overview given a description of the possible initial states of the world a description of the desired goals and a description of a set of possible actions the planning problem is to synthesise a plan that is guaranteed when applied to any of the initial states to generate a state which contains the desired goals such a state is called a goal state the difficulty of planning is dependent on the simplifying assumptions employed several classes of planning problems can be identified depending on the properties the problems have in several dimensions are the actions deterministic or nondeterministic for nondeterministic actions are the associated probabilities available are the state variables discrete or continuous if they are discrete do they have only a finite number of possible values can the current state be observed unambiguously there can be full observability and partial observability how many initial states are there finite or arbitrarily many do actions have a duration can several actions be taken concurrently or is only one action possible at a time is the objective of a plan to reach a designated goal state or to maximize a reward function is there only one agent or are there several agents are the agents cooperative or selfish do all of the agents construct their own plans separately or are the plans constructed centrally for all agents 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 further plans can be defined as sequences of actions because it is always known in advance which actions will be needed with nondeterministic actions or other events outside the control of the agent the possible executions form a tree and plans have to determine the appropriate actions for every node of the tree discretetime markov decision processes mdp are planning problems with durationless actions nondeterministic actions with probabilities full observability maximization of a reward function and a single agent when full observability is replaced by partial observability planning corresponds to partially observable markov decision process pomdp if there are more than one agent we have multiagent planning which is closely related to game theory domain independent planning in ai planning planners typically input a domain model a description of a set of possible actions which model the domain as well as the specific problem to be solved specified by the initial state and goal in contrast to those in which there is no input domain specified such planners are called domain independent to emphasis the fact that they can solve planning problems from a wide range of domains typical examples of domains are block stacking logistics workflow management and robot task planning hence a single domain independent planner can be used to solve planning problems in all these various domains on the other hand a route planner is typical of a domain specific planner planning domain modelling languages the most commonly used languages for representing planning domains and specific planning problems such as strips and pddl for classical planning are based on state variables each possible state of the world is an assignment of values to the state variables and actions determine how the values of the state variables change when that action is taken since a set of state variables induce a state space that has a size that is exponential in the set planning similarly to many other computational problems suffers from the curse of dimensionality and the combinatorial explosion an alternative language for describing planning problems is that of hierarchical task networks 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 algorithms for planning classical planning forward chaining state space search possibly enhanced with heuristics backward chaining search possibly enhanced by the use of state constraints see strips graphplan partialorder planning see also sussman anomaly reduction to other problems reduction to the propositional satisfiability problem satplan reduction to model checking both are essentially problems of traversing state spaces and the classical planning problem corresponds to a subclass of model checking problems temporal planning temporal planning can be solved with methods similar to classical planning the main difference is because of the possibility of several temporally overlapping actions with a duration being taken concurrently that the definition of a state has to include information about the current absolute time and how far the execution of each active action has proceeded further in planning with rational or real time the state space may be infinite unlike in classical planning or planning with integer time temporal planning is closely related to scheduling problems temporal planning can also be understood in terms of timed automata probabilistic planning markov decision process and partially observable markov decision process probabilistic planning can be solved with iterative methods such as value iteration and policy iteration when the state space is sufficiently small 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 preferencebased planning preferencebased planning in preferencebased planning the objective is not only to produce a plan but also to satisfy userspecified preferences a difference to the more common rewardbased planning for example corresponding to mdps preferences dont necessarily have a precise numerical value conditional planning deterministic planning was introduced with the 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 an early example of a conditional planner is warplanc which was introduced in the mid 1970s an agent is not forced to plan everything from start to finish but can divide the problem into chunks this helps to reduce the state space and solves much more complex problems deployment of planning systems the hubble space telescope uses a shortterm system called spss and a longterm planning system called spike artificial intelligence portal robotics portal action description language actor model applications of artificial intelligence constraint satisfaction problem reactive planning scheduling computing strategy game theory lists list of smt solvers list of constraint programming languages list of emerging technologies outline of artificial intelligence vlahavas i planning and scheduling eetn archived from the original on 20131222 international conference on automated planning and scheduling 