Hierarchical Plan-Based Control in Open-Ended Environments: Considering Knowledge Acquisition Opportunities - Agents and Artificial Intelligence - page 27

knowledge acquisition scheme kas is called possibly-acquirable iff all ( l,ks )

∈ kas are

possibly-acquirable.

Let D be the set of domain models, TL be the set of task lists, P be the set of plans and

KAS ∈D×TL×P×KAS

a planning state . A planning state is called final if the task list is empty and called
intermediate if the task list is not empty. ps D denotes the domain model, ps t the task
list, ps p the plan and ps kas the knowledge acquisition scheme of a planning state ps .
The term planning step is used in this work as an abstraction of (HTN) methods and
planning operators. A planning step

be the set of knowledge acquisition schemes. We call ps

s is represented by a 4-tuple ( s task , s cond , s eff ,

s cost ) . s task is an atomic formula that describes for which task s is relevant, s cond

is a statement that constitutes the precondition of s , s eff is the effect of s ,and s cost

represents the expected cost of the plan that results from the application of s .

PS . Thus,
a planning step maps the current planning state to a resulting planning state. In this
sense operators map the current planning state to a resulting state by removing the next
task from the task list, adding a ground instance of this task to the plan and updating
the domain model according to the effects of the operator. In contrast, HTN methods
transform the current planning state by replacing an active task by a number of subtasks.
Furthermore, we define the concept of a possibly-applicable planning step introduced
in Section 2.1 as follows:

Let PS be the set of planning states. s eff is a function s eff : PS →

Definition 3 (Possibly-applicable). A planning step is called possibly-applicable

w.r.t. a domain model D M and a knowledge acquisition scheme kas iff kas is possibly-
acquirable and a knowledge acquisition scheme for

s

s cond .

A possibly-applicable planning step can only be applied after necessary information
has been acquired by the execution of corresponding knowledge acquisition tasks. For
example, consider the second method instance of the situation illustrated by Fig. 1. This
method instance can only be applied if the robot has perceived that door2 is open. The
fact that possibly-applicable planning step instances require the execution of additional
tasks (i.e., knowledge acquisition tasks) needs to be considered by the expected cost.
The cost of a possibly-applicable planning step is defined as the sum of the cost for
the step if it is applicable and the expected cost of all necessary knowledge acquisition
tasks.
For example, let us assume that the cost of the plan that results from applying the
method for move to(Room) is always 100. Moreover, let us assume that the cost of
performing the task det(open(door2), ∅ , ∅ ,percept) is 50 (see Fig. 2) and the
cost of performing the task det(connect(lab,X,kitchen),
[connect(lab,door1,kitchen), connect(lab, door2,kitchen)],
open(X), percept) is 300. In this situation the cost of method instance 1 is 100,
the cost of method instance 2 is 100 + 50 = 150 , and the cost of method instance 3 is
100 + 50 + 300 = 450 . Thus, in this case the applicable instance has the less expected
cost. However, this does not always have to be the case.