Automated planning and scheduling


Automated planning and scheduling

Automated planning and scheduling 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.

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

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 or PDDL. The planner produces a sequence of actions that lead from the initial state to a state meeting the goal. 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.

The difficulty of planning is dependent on the simplifying assumptions employed, such as atomic time, deterministic time, and complete observability. Classical planners, which make all of these assumptions, have been studied most fully. Some popular techniques include forward chaining and backward chaining state space search, possibly enhanced by the use of relationships among conditions (see graphplan) or heuristics synthesized from the problem, search through plan space, and translation to propositional satisfiability (satplan).

Dropping the assumption of determinism and adopting a probabilistic model of uncertainty leads to the problem of policy generation for a Markov decision process (MDP) or (in the general case) partially observable Markov decision process (POMDP).

Preference-based planning

In preference-based planning, the objective is not only to produce a plan but also to satisfy user-specified preferences.

Conditional Planning

Conditional planning operates on an IF (condition) THEN (action) ELSE (action) model. The branching model does not have to be binary. Conditional planners examine the current model and then determine the action to take based on that. This process allows the planning algorithm to examine all possible contingencies and then perform the best action possible given the current status. Conditional planning is, however, limited in that if the number of conditions is sufficiently large the problem can quickly become intractable. In addition, conditional planners are limited in that they can only act upon the specifically enumerated conditions.

Continuous Planning

Continuous planning operates by performing some number of actions, examining the current status of the world, and then re-evaluating it's goals. Continuous planners are allowed to revise their goals in order to satisfy current needs in the process of reaching their ultimate goal. For instance, a continuous planning algorithm may decide that in order to reach its goal, it must first plan for the completion of a sub-goal. This planning process allows continuous planners to operate autonomously as they are built on an open-world assumption.

Examples

See also

References

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Planning — 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 …   Wikipedia

  • Scheduling (computing) — This article is about processes assignment in operating systems. For other uses, see Scheduling (disambiguation). Scheduling is a key concept in computer multitasking, multiprocessing operating system and real time operating system designs.… …   Wikipedia

  • Planning Domain Definition Language — The Planning Domain Definition Language (PDDL) is an attempt to standardize planning domain and problem description languages. It was developed mainly to make the 1998/2000 International Planning Competitions possible. It was first developed by… …   Wikipedia

  • Automated Tissue Image Systems — (ATIS) are computer controlled automatic test equipment (ATE) systems classified as medical device and used as pathology laboratory tools (tissue based cancer diagnostics) to characterize a stained tissue sample embedded on a bar coded glass… …   Wikipedia

  • 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 (and for) multiple agents. It can involve agents planning for a common… …   Wikipedia

  • Dynamic Analysis and Replanning Tool — The Dynamic Analysis and Replanning Tool, commonly abbreviated to DART, is an artificial intelligence program[1] used by the U.S. military to optimize and schedule the transportation of supplies or personnel and solve other logistical problems.… …   Wikipedia

  • Crew scheduling — is the process of assigning crews to operate transportation systems, such as rail lines or aircraft. Contents 1 Complex 2 4 Parts 3 Real Time 4 Disruptions …   Wikipedia

  • Reactive planning — Dynamic planning redirects here. For the anime studio, see Dynamic Planning. In artificial intelligence, reactive planning denotes a group of techniques for action selection by autonomous agents. These techniques differ from classical planning in …   Wikipedia

  • Noninterleaved planning — A noninterleaved planner is a planner that, when given two subgoals G1 and G2, produces either a plan for G1 concatenated with a plan for G2, or vice versa. Sources Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern… …   Wikipedia

  • Operational Test and Evaluation Force — (OPTEVFOR) seal Active December, 1947 – Present Country …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.