Automated planning and scheduling
Encyclopedia
Automated planning and scheduling is a branch of artificial intelligence
that concerns the realization of strategies
or action sequences, typically for execution by intelligent agent
s, autonomous robot
s 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 language
s.
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.
The simplest possible planning problem, known as the Classical Planning Problem, is determined by a unique known initial state, durationless 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.
Planning with nondeterministic durationless actions with probabilities, full observability, maximization of a reward function, and a single agent corresponds to discrete-time Markov decision process
es (MDP).
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 multi-agent planning
, which is closely related to game theory
.
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 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 also the description of task networks.
s. A difference to the more common reward-based planning, for example corresponding to MDPs, preferences don't necessarily have a precise numerical value.
In general, classical planning can be solved by methods for Model checking
because both are essentially problems of traversing state spaces, and the classical planning problem corresponds to a subclass of model checking problems.
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 can 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.
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
that concerns the realization of strategies
Strategy
Strategy, a word of military origin, refers to a plan of action designed to achieve a particular goal. In military usage strategy is distinct from tactics, which are concerned with the conduct of an engagement, while strategy is concerned with how different engagements are linked...
or action sequences, typically for execution by intelligent agent
Intelligent agent
In artificial intelligence, an intelligent agent is an autonomous entity which observes through sensors and acts upon an environment using actuators and directs its activity towards achieving goals . Intelligent agents may also learn or use knowledge to achieve their goals...
s, autonomous robot
Autonomous robot
Autonomous robots are robots that can perform desired tasks in unstructured environments without continuous human guidance. Many kinds of robots have some degree of autonomy. Different robots can be autonomous in different ways...
s and unmanned vehicles
Unmanned aerial vehicle
An unmanned aerial vehicle , also known as a unmanned aircraft system , remotely piloted aircraft or unmanned aircraft, is a machine which functions either by the remote control of a navigator or pilot or autonomously, that is, as a self-directing entity...
. Unlike classical control
Control system
A control system is a device, or set of devices to manage, command, direct or regulate the behavior of other devices or system.There are two common classes of control systems, with many variations and combinations: logic or sequential controls, and feedback or linear controls...
and classification
Classifier
Classifier may refer to:*Classifier *Classifier *Classifier *Hierarchical classifier*Linear classifier...
problems, the solutions are complex and must be discovered and optimized in multidimensional space. Planning is also related to decision theory
Decision theory
Decision theory in economics, psychology, philosophy, mathematics, and statistics is concerned with identifying the values, uncertainties and other issues relevant in a given decision, its rationality, and the resulting optimal decision...
.
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
Strategy
Strategy, a word of military origin, refers to a plan of action designed to achieve a particular goal. In military usage strategy is distinct from tactics, which are concerned with the conduct of an engagement, while strategy is concerned with how different engagements are linked...
often needs to be revised online. Models and policies must be adapted. Solutions usually resort to iterative trial and error
Trial and error
Trial and error, or trial by error, is a general method of problem solving, fixing things, or for obtaining knowledge."Learning doesn't happen from failure itself but rather from analyzing the failure, making a change, and then trying again."...
processes commonly seen in artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
. These include dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
, reinforcement learning
Reinforcement learning
Inspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
and combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
. Languages used to describe planning and scheduling are often called action language
Action language
In computer science, an action language is a language for specifying state transition systems, and is commonly used to create formal models of the effects of actions on the world...
s.
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 find a plan that is guaranteed (from any of the initial states) to generate a sequence of actions that leads to one of the goal states.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? This is the question between full observability and partial observability.
- How many initial states are there, one 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 there 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 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.
Planning with nondeterministic durationless actions with probabilities, full observability, maximization of a reward function, and a single agent corresponds to discrete-time Markov decision process
Markov decision process
Markov decision processes , named after Andrey Markov, provide a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly under the control of a decision maker. MDPs are useful for studying a wide range of optimization problems solved via...
es (MDP).
When full observability is replaced by partial observability, planning corresponds to partially observable Markov decision process
Partially observable Markov decision process
A Partially Observable Markov Decision Process is a generalization of a Markov Decision Process. A POMDP models an agent decision process in which it is assumed that the system dynamics are determined by an MDP, but the agent cannot directly observe the underlying state...
(POMDP).
If there are more than one agent, we have multi-agent planning
Multi-agent planning
In computer science multi-agent planning involves coordinating the resources and activities of multiple "agents".NASA says, "multiagent planning is concerned with planning by multiple agents...
, which is closely related to game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
.
Planning languages
The most commonly used languages for representing planning problems, such as STRIPSSTRIPS
In artificial intelligence, STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this planner...
and PDDL
Planning Domain Definition Language
The Planning Domain Definition Language is an attempt to standardize planning domain and problem description languages. It was developed mainly to make the 1998/2000 International Planning Competitions possible....
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
Curse of dimensionality
The curse of dimensionality refers to various phenomena that arise when analyzing and organizing high-dimensional spaces that do not occur in low-dimensional settings such as the physical space commonly modeled with just three dimensions.There are multiple phenomena referred to by this name in...
and the combinatorial explosion
Combinatorial explosion
In administration and computing, a combinatorial explosion is the rapidly accelerating increase in lines of communication as organizations are added in a process...
.
An alternative language for describing planning problems is that of hierarchical task network
Hierarchical task network
In artificial intelligence, the hierarchical task network, or HTN, is an approach to automated planning in which the dependency among actions can be given in the form of networks....
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 also the description of task networks.
Preference-based planning
In preference-based planning, the objective is not only to produce a plan but also to satisfy user-specified preferencePreference
-Definitions in different disciplines:The term “preferences” is used in a variety of related, but not identical, ways in the scientific literature. This makes it necessary to make explicit the sense in which the term is used in different social sciences....
s. A difference to the more common reward-based planning, for example corresponding to MDPs, preferences don't necessarily have a precise numerical value.
Classical planning
The most popular approaches to solving the classical planning problem are- forward chainingForward chainingForward chaining is one of the two main methods of reasoning when using inference rules and can be described logically as repeated application of modus ponens. Forward chaining is a popular implementation strategy for expert systems, business and production rule systems...
state space searchState space searchState space search is a process used in the field of computer science, including artificial intelligence , in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property....
, possibly enhanced with heuristics, - backward chainingBackward chainingBackward chaining is an inference method that can be described as working backward from the goal...
search, possibly enhanced by the use of state constraints (see graphplanGraphplanGraphplan is an algorithm for automated planning developed by Avrim Blum and Merrick Furst in 1995. Graphplan takes as input a planning problem expressed in STRIPS and produces, if one is possible, a sequence of operations for reaching a goal state...
), - partial-order planningPartial-order planningPartial-order planning is an approach to automated planning. The basic idea is to leave the decision about the order of the actions as open as possible. Given a problem description, a partial-order plan is a set of all needed actions and order conditions for the actions where needed.The approach is...
, - reduction to the propositional satisfiability problem (satplanSatplanSatplan is a method for automated planning. It converts the planning problem instance into an instance of the Boolean satisfiability problem, which is then solved using a method for establishing satisfiability such as the DPLL algorithm or WalkSAT.Given a problem instance in planning, with a given...
).
In general, classical planning can be solved by methods for Model checking
Model checking
In computer science, model checking refers to the following problem:Given a model of a system, test automatically whether this model meets a given specification....
because 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 can be understood in terms of timed automata.
Probabilistic planning
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.
Deployment of planning systems
- The Hubble Space TelescopeHubble Space TelescopeThe Hubble Space Telescope is a space telescope that was carried into orbit by a Space Shuttle in 1990 and remains in operation. A 2.4 meter aperture telescope in low Earth orbit, Hubble's four main instruments observe in the near ultraviolet, visible, and near infrared...
uses a short-term system called SPSS and a long-term planning system called Spike.
See also
- Actor modelActor modelIn computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
- Action description languageAction description languageIn artificial intelligence, Action description language is an automated planning and scheduling system in particular for robots. It is considered an advancement of STRIPS. Pednault proposed this language in 1987...
- PlanningPlanningPlanning in organizations and public policy is both the organizational process of creating and maintaining a plan; and the psychological process of thinking about the activities required to create a desired goal on some scale. As such, it is a fundamental property of intelligent behavior...
- Reactive planningReactive planningIn artificial intelligence, reactive planning denotes a group of techniques for action selection by autonomous agents. These techniques differ from classical planning in two aspects. First, they operate in a timely fashion and hence can cope with highly dynamic and unpredictable environments....
- SchedulingScheduling (computing)In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
- Strategy (game theory)Strategy (game theory)In game theory, a player's strategy in a game is a complete plan of action for whatever situation might arise; this fully determines the player's behaviour...