Partial-order planning
Encyclopedia
Partial-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 inspired by the least commitment strategy. In many cases, there are many possible plans for a problem which only differs in the order of the actions. Many traditional automated planners are searching for plans in the full search space containing all possible orders. Despite the smaller search space for partial-order planning, it can also have advantages to leave the option about the order of the actions open for later.
If you want to keep the possible orders of the actions as open as possible, you want to have the set of order conditions as small as possible.
A plan is a solution if the set of open preconditions is empty.
or program
which will construct a plan and searches for a solution. The input is the problem description, consisting of descriptions of the initial state, the goal and possible actions.
The problem can be interpreted as a search problem
where the set of possible partial-order plans is the search space. The initial state would be the plan with the open preconditions equal to the goal conditions. The final state would be any plan with no open preconditions, i.e. a solution.
Partial plan
In formal AI planning, a partial plan is a plan which specifies all actions that need to be taken, but does not specify an exact order for the actions as the order does not matter...
is a set of all needed actions and order conditions for the actions where needed.
The approach is inspired by the least commitment strategy. In many cases, there are many possible plans for a problem which only differs in the order of the actions. Many traditional automated planners are searching for plans in the full search space containing all possible orders. Despite the smaller search space for partial-order planning, it can also have advantages to leave the option about the order of the actions open for later.
Partial-order plan
A partial-order plan consists of four components:- A set of actions.
- A partial order for the actions. It specifies the conditions about the order of some actions.
- A set of causal links. It describes what action meet what preconditions of other actions.
- A set of open preconditions, i.e. those preconditions which are not fulfilled by any action in the partial-order plan.
If you want to keep the possible orders of the actions as open as possible, you want to have the set of order conditions as small as possible.
A plan is a solution if the set of open preconditions is empty.
Partial-order planner
A partial-order planner is an algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
or program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
which will construct a plan and searches for a solution. The input is the problem description, consisting of descriptions of the initial state, the goal and possible actions.
The problem can be interpreted as a search problem
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
where the set of possible partial-order plans is the search space. The initial state would be the plan with the open preconditions equal to the goal conditions. The final state would be any plan with no open preconditions, i.e. a solution.