Information Technology Reference
In-Depth Information
planning operator instances are considered. In other words, one can also benefit from
the proposed approach in situations where it is possible to generate a complete plan
without acquiring additional information.
2.2
Open-Ended Domain Model
A planner that wants to consider possibly-applicable HTN methods or planning oper-
ators needs to be able to reason about extensions of its domain model. Most existing
automated planning systems are unable to do that, since their underlying domain model
is based on the assumption that all information is available at the beginning of the plan-
ning process [9]. In contrast, the proposed HTN planning system
ACogPlan
is based on
the open-ended domain model
ACogDM
. ACogDM enables the planner to reason about
relevant extensions of its domain model. The key concepts of ACogDM are described
briefly in this section.
A planner should only consider domain model extensions that are
possible
and
rele-
vant
with respect to the overall task. However, how can a planner infer what is relevant
and possible? The domain information encoded in HTN methods can nicely be ex-
ploited in order to infer which information is relevant. A relevant method or planning
operator can actually be applied if and only if its precondition
p
holds (i.e., an instance
pσ
3
is derivable) with respect to the given domain model. Therefore, we define the set
of
relevant preconditions
with respect to a given
planning context
(i.e., a domain model
and a task list) to be the set of all preconditions of relevant methods or planning opera-
tors. An HTN planner cannot—except backtracking—continue the planning process in
situations where no relevant precondition is derivable with respect to the domain model
at hand. Introducing the notion of a relevant precondition is a first step to determine
relevant extensions of a domain model, since only domain model extensions that make
the derivation of an additional instance of a relevant precondition possible constitute
an additional way to continue the planning process. All other possible extensions are
irrelevant, because they do not imply additional planning alternatives. In other words,
if it is possible to acquire additional information which implies the existence of a new
instance of a relevant precondition, then the planning process can be continued in an
alternative manner. As already pointed out, this is particularly relevant for situations in
which it would otherwise be impossible to find any plan at all.
In order to formalize this we introduce the following concepts: a
possibly-derivable
statement
(e.g., a precondition) and an
open-ended literal
.Let
L
x
be a set of literals and
p
be a precondition.
p
is called
possibly-derivable
w.r.t.
L
x
iff the existence of a new
instance
lσ
for all
l ∈ L
x
implies the existence of a new instance
pσ
of
p
. Obviously
this definition is only useful if the existence of an additional instance for each
l ∈ L
x
is possible. A literal for which the existence of non-derivable instances is possible is
called
open-ended
. Based on that, one can say that a possibly-derivable precondition
constitutes the partition of a precondition into a derivable and an open-ended part (i.e.,
a set of open-ended literals).
For example, consider the situation illustrated by Fig. 1. In this example there are three
different situations in which the precondition of the HTN method is possibly-derivable.
3
In the context of this work
σ
denotes a substitution.
