World Library  
Flag as Inappropriate
Email this Article

Automated planning and scheduling

Article Id: WHEBN0001505641
Reproduction Date:

Title: Automated planning and scheduling  
Author: World Heritage Encyclopedia
Language: English
Subject: Artificial intelligence, History of artificial intelligence, Process ontology, Nils John Nilsson, Artificial intelligence, situated approach
Collection: Automated Planning and Scheduling
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Automated planning and scheduling

Automated planning and scheduling, in the relevant literature often denoted as simply 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.

Contents

  • Overview 1
  • Planning languages 2
    • Preference-based planning 2.1
  • Algorithms for planning 3
    • Classical planning 3.1
    • Reduction to other problems 3.2
    • Temporal planning 3.3
    • Probabilistic planning 3.4
  • Deployment of planning systems 4
  • See also 5
  • References 6
  • Further reading 7
  • External links 8

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? 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.

Discrete-time 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 multi-agent planning, which is closely related to game theory.

Planning languages

The most commonly used languages for representing 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 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 preferences. A difference to the more common reward-based planning, for example corresponding to MDPs, preferences don't necessarily have a precise numerical value.

Algorithms for planning

Classical planning

Reduction to other 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 Telescope uses a short-term system called SPSS and a long-term planning system called Spike.

See also

Lists

References

Further reading

External links

  • International Conference on Automated Planning and Scheduling
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.