|
Introductory Talk
ICKEPS
Home
|
ModPlan - Modern Action Planning
Operator Dependency
There are two main optimization metrics in planning, the
plan length (number of
actions) and its makespan (minimum parallel execution time).
To express parallel plans, a
mutex relation of operators, which
in the case of metric planning,
naturally extends to the standard mutex relation for STRIPS:
- The precondition list of one operator
has a non-empty intersection with the add
or delete lists of the other one.
- The head of a numerical modifier of one
operator is contained in some condition of the other one.
- The head of the numerical modifier of one operator is
contained in the body of the modifier of the other one.
For temporal planning with start, invariant and
end conditions or effects, we have eight different
mutexes, i.e. start-start, start-invariant, start-end,
invariant-start, invariant-end, end-start, end-invariant and end-end.
If there is more than one conflict for one operator pair, we have to
compute the maximum value derived for the individual conflicts.
The semantics of operator duration in PDDL2.1 demands a slack
of epsilon time steps between any two happenings that are
dependent. The default for epsilon is 0.01. The idea is
that if a proposition
or a numerical quantity is accessed by different actions,
some time for resolving has to pass.
Optimizing of plans without precedence ordering
is involved, since computing
the makespan for a set of operators is
NP-complete.
Knowledge Acquisition
However, given a sequence of operators in a plan, a precedence
ordering among them, an
optimal parallel plan that respects the given timing constraints, is
polynomially solvable. With PERT scheduling
such a plan
can be computed in optimal time.
The approach extends to
timed initial literals and action execution time windows.
Knowledge Engineering
Operator dependency induces a partial ordering in a sequence of
actions. In order to derive posterior schedules of sequential plans
in temporal planning, pairwise dependencies are precomputed and made
visible and accessible to the domain expert with each computed plan.
He may add or delete precedence constraints before scheduling is
performed.
|
|