Filetype PDF | Posted on 31 Jan 2023 | 2 years ago
Authentication
digital resources
134x Filetype PDF File size 0.84 MB Source: www.aaai.org
From: AAAI Technical Report WS-98-03. Compilation copyright © 1998, AAAI (www.aaai.org). All rights reserved.
Design Patterns for Planning Systems
Qiang Yang and Philip W. L. Fong and Edward Kim
School of Computing Science
Simon Fraser University
Burnaby, BC Canada V5A 1S6
qyang@cs.sfu.ca
Abstract want to demonstrate how design patterns can be em-
In this work, we are interested in building a software ployed to structure a search-based planner design, so
engineering discipline for planning system design. Our that the complexity of constructing AI software can be
objective is to enable planning systems to become more managed. Second, we want to discuss the role played
configurable and modular, with the help of object li- by a design pattern catalog during our process of de-
braries capturing well designed experiences and a com- signing and evolving the framework. We want to re-
mon planner-design pattern catalog. It is hoped that port how the design pattern catalog allowed us to flex-
the planning systems thus constructed will be more ibly configure planning systems for different applica-
reusable and modifiable. It is also hoped that this effort tions. Our work follows closely the current trend in AI
will contribute to the movement towards industrially Planning in making the systems more modular (BVB96;
applicable planning systems, to supply this dynamic BHB97).
subfield of AI with a rigorous software engineering dis- We will first introduce the concept of design pat-
cipline than just smart algorithms for plan generation. terns. We then discuss planning as search (section),
To this end, we focus on an object oriented design and the need to reuse past planning frameworks (sec-
methodology to planning. We focus on a collection tion ). We will show several design patterns useful for
of design patterns for modularizing different search- modular planner design applied to our planner frame-
related parts of a typical planning system. We illus- work. We report the issues involved in each decision,
trate our concept using the C++ language, although the solution we adopted, the alternatives we considered,
our experience apply equally well to all object oriented and in what manner the design pattern catalog helped
languages. This work is represents our continuing re- us in coming up with the solution. We summarize our
search in knowledge acquisition and maintenance effort
in planning systems design. experience in section .
Introduction Design Patterns
This paper summarizes our experience in applying de- Design pattern is a recent movement in software engi-
sign patterns to develop intelligent planning systems neering. The basic concept is to reuse design knowledge.
based on heuristic search. Over the past few years, we Design pattern is a genre by which standard, expert-
have built a number of artificial intelligence (AI) plan- tested solution to canonical design problems is rigor-
ners, schedulers, and other kinds of problem solvers ously is documented. The term design pattern could
in languages including Common Lisp, C, and C++. also refer to the solution itself. Such design patterns
As experience cumulates, we intended to design an usually solve a design problem by imposing new orga-
object-oriented framework for building intelligent prob- nization in the software, and layout a particular pro-
lem solvers. Our hope is that the framework allows var- tocol in which individual computational entities should
ious reusable AI techniques to be mixed and matched in interact. By conforming to such restriction, the target
a highly flexible manner. The effort resulted in a C++ program would become more maintainable. For exam-
framework called Plan++. Our recent implementation ple, iterators "provide a way to access the element of
of AI planners, as well as our current focus in text-based an aggregate object sequentially without exposing its
planning systems, are all done on top of this framework. underlying representation." Iterators can be found in
nearly all object-oriented container class library. It de-
In this paper, we report how the design pattern cat- fines a protocol by which client subprograms can access
alog (GHJV94) has shaped the way we design our plan- the internal of an aggregate object.
ning system’s framework. As a starting point, we will Design patterns can be shown informally as boxes
concentrate on search aspects of planning algorithms, with connections between them. A popular notation is
leaving the rest of the planning framework as a part of an class/object diagram known as the OMT diagram
our future work. Our interest here is twofold. First, we (Object Modeling Technique). Figure 1 (a) shows
104
Concrete Class Name if it finds one of the goal nodes. A typical search routine
AbstractClaasNarne
Abstract Operationl0 Operation0 looks like the following:
Type AbstraetOperation20 Type Operation20 plan(init-plan, operators, goal-condition):
instanceVariablel mark init-plan as "generated";
Type instanceVariable2 while (not all generated nodes are expanded) do
(a) select a node n that is generated but not expanded;
(part-of relationship) (a solid circle means more than one) if (n satisfies the goM-condition) then return
~
generate all or some of the successor nodes n of n;
I
mark all n as "generated";
~ (class Inheritance) mark n as "expanded";
end while;
return "failure";
(creation relationship) end Search.
(acquaintance relationship, that is, Intuitively, a plan node is "generated" the first time
LineShape keeps a reference to Color) it is visited. A node is "expanded" if all its neighboring
(b) nodes are "generated". The efficiency of a search is
Figure 1: Introduction to OMT diagram partly determined by the order in which the state space
is traversed, which, in turn, is determined by the order
in which nodes are selected for expansion, the definition
OMT notation for abstract and concrete classes. A class of the operator, and the representation of the states.
is denoted by a box in the figure. The key operations The efficiency is also defined by how and in which order
of the class appear below the class name. Any instance a successor node is generated; in partial order planning,
variables appear below the operations. a node is generated by resolving threats and achieving
Figure 1 (b) shows various relationships between open-preconditions. In HTN planning, a node can also
classes. The OMT notation for class inheritance is a be generated by reducing a non-primitive task by a task
triangle connecting a subclass (LineShape) to its parent network. In case based planning a variety of repair
class (Shape). The rest of the notations are explained operations can be used to generate successor nodes.
in the figure. In short, OMT is a convenient way of Throughout the paper, we will use a sample AI plan-
communicating good design experiences in object ori- ning domain to illustrate the effect of applying the de-
ented design, showing relationships between classes and sign patterns. An instance of the water-jug planning
objects. problem is often described as follows:
A collection of well-used design patterns forms a de- "You have two jugs { A, B}, jug A holds m litres
sign pattern catalog. Such catalogs are widely available (L) of water, jug B holds n L of water. You are
on the Internet and in various book formats. Work in allowed to do three things with the jugs: fill up a
design pattern mining from large-scale software code is jug, empty a jug, or pour the content of a jug to
also starting to generate important results. another (until one of them is either full or empty).
Find a sequence of steps which will result in a jug
Planning as Search holding kL of water."
A significant number of AI and combinatorial opti- For example, in a sequel of the movie Die Hard, the
mization problems are instances of heuristic state-space protagonists are given two jugs of capacity 3L and 5L,
search (Pea84). A state space is a set of states plus a set and they are asked to measure out exactly 1L from the
of operators. Planning is no different. In planning one two jugs. Here a state can be represented by a vector
can differentiate between state-based search (BK95) (p, q), where p and q are the amount of water in jug
and plan-space search (Wel94; Yan97). In both frame- and B respectively. The operators are fillJug0, emp-
works, one define a search engine and a processing mod- tyJug0, and pourContentsOfJugIntoOtherJug0; thus,
ule for generating a set of successor nodes from a given the neighbourhood of a node in the state-space is gen-
current node. Both styles of planning are instances of erated by the execution of all possible operators from
a state-space search. this state; then the goal states are all (p, q) so that one
In a state-space search framework, an operator is a ofporqis 1.
transformation that generates one or more states given Reusability in Planner Design
the input of a state. A state space, therefore, implicitly Reuse is a unique challenge in search-based applications
defines a graph in which nodes are states, and edges because of several reasons:
are operator applications. A state space search is basi-
cally a graph searching problem such that nodes in the 1. Frequent shift of representation. The efficiency and
underlying graphs are generated incrementally as the quality of search depends largely on the representa-
search proceeds. The goal of a search is a set of states tion of state space. Designers building search appli-
with some interesting properties. A search is successful cation must experiment with multiple representation
105
before an appropriate one is found. A reusable search ¯ Different domain have different ways of specifying
engine should anticipate such frequent shift of repre- and verifying a goal. As we move from one domain to
sentation. another, or as the representation of states changes, a
2. High demand for flexible composition. Almost no sin- goal will be represented differently, and the algorithm
gle AI technique can be claimed as being omnipotent. used for checking a goal will be different.
Most of the techniques are heuristic in the sense that ¯ Different domains have different state space topolo-
it works well in some domain, but not in other do- gies. In particular, the representation of operators
mains. Most of the time, more than one search tech- determines how the successors are generated.
nique has to be combined to yield satisfactory per- In fact, even if we stay in one domain, and fix the rep-
formance. Reuse, therefore, means not so much as resentation of states, both the goal verification and suc-
the direct recycling of a predetermined set of search cessor generation mechanisms may still vary:
techniques, but instead the ability for future users to ¯ As the application mature, one might want to search
pick and choose various techniques that fits their do- for goals that previous goal specification method fails
main, and to compose these techniques together in a to represent.
flexible manner.
3. Obscurity of module boundary. AI techniques are ¯ One might discover that the reformulation of the
very difficult to modularized. There are implicit search problem by altering the topology of the search
interaction and hidden dependency among various space might speed-up the search procedure. This can
components of the system. It takes a very in depth be achieved by providing multiple successor genera-
understanding of these techniques in order for the tion strategies and allowing users of the application
system architect to cleanly isolate the components. to configure the system with one of the alternative
The goal of developing the Plan++ framework is to strategies. A real-life example is the SNLP planner
provide an architecture in which individual search tech- (MR91) and its variants with various threat removal
niques can be mixed and matched in a flexible manner, strategies (PS93). All SNLP-based planners search in
so that search technologies can be readily applied to a the same plan space. The implementation of states
wide range of application domains. and goal verification mechanism are therefore fixed.
However, the successor generation mechanism is dif-
Encapsulating the Variation of State ferent for different threat-removal strategies.
Representation To summarize, we are dealing with the following issues:
Variations in State Representation ¯ The generic search procedure is more or less stan-
The core search facilities is provided by a search engine dard. Its behavior varies when we have a different
object. Users construct a search engine object by sup- mechanism for verifying goals and generating succes-
plying their problem description, and subsequent invo- sors. We want to provide a way for the users of our
cation of a member function will return solution search framework to configure the search engine with the
path to the users. appropriate behavior.
template ¯ We anticipate that both the goal verification and suc-
class Search { cessor generation mechanisms will evolve as the users
public : attempt to build increasingly sophisticated problem
¯ .. ¯ solvers. We want to provide an architecture that sup-
Search(const State~ start_state, ....) ports the enhancement and adaptation of the search
SearchPath findSolution() engine.
// Get solution. Return search path. ¯ The goal verification and successor generation mech-
anisms access the state objects, which the search en-
}; gine should assume zero knowledge if flexibility is
Now, within the :findSolution() member function to be achieved. We want to completely insulate the
implement the generic search algorithm in section . It search engine from any access of the state objects.
is clear that the implementation of findSolutton() To resolve the above issues, we adopted a design that
needs a way to test if a state object satisfy the goal we later recognized to be an incarnation of the Strategy
(goal verification mechanism), and a way to generate pattern.
the neighbouring states (successor generation mecha-
nism). We want to give the users of Plan++ the free- Goal Verifier
dom to represent their states in a way that best fits their The Strategy pattern is applied to encapsulate the goal
application domain. As such, the search engine should verification mechanism. We define a goal verifier class
assume minimal knowledge about the implementation Goal, which is a parameterized abstract base
of the state objects. However, both the goal verification class.
and the successor generation mechanisms are dependent
on the search domain and its representation: template
105
~ata> Search
¯ sucg~so~3cnem~r_
expand(State) ~ findSolutlonO; (3- - -
bool satisfied(State) I findSolution0; O- I A [
A succcssorOcncrater_->cxpand(statc)
1 I
DomainSpecifieGoal I ~2 4 expand(State)DomainSpecificSuccc,ssor I 1[¢xpsnd(State) [ DomatnSpeclficSuccess~r2
boo sat sfied(State) I bool satisfied(State)
Figure 2: Goal Figure 3: Successor
class JugGoal : Goal {
class Goal { public :
public : JugGoal(int target_volume) : t_(target_volume)
. .. bool satisfied(const JugState is)
virtual bool satisfied(coast State~ state) // Check if any of the jug in state js
= O; // holds target_ litre of liquid.
} /* satisfied */
}; /* Goal */ private :
We then introduce into the search engine a pointer int t_ ;
that refers to the above abstract base class. }; /* JugGoal */
template Now, suppose we decide to use another goal condition
class Search { for our planner, and want to search for states so that
public : the volume of both jugs are specified. For example, we
Search(const State~ start_state, want jug A to hold 1L and jug B to hold 2L. To allow
Goal* goal, such goal to be specified, we define a second goal verifier
class for the jug domain.
.... ); class JugGoal2 : Goal {
SearchPath findSolution() public :
// Get next solution JugGoal2(int tl, int t2)
private : tl_(tl), t2_(t2)
Goal *goal_ ; bool satisfied(const JugState is)
// Pointer to goal object // Determine if both jugs in js
//satisfy the goal condition.
}; /* Search */ } /* satisfied */
When the findSolution() function needs to check private :
if a state statisfies the goal of the search, it delegates int ti_, t2_;
the responsibility to the object referenced by goal_. }; /* JugGoal2 */
Notice that the change of the definition of a goal in
template the water-jug domain does not require any modification
SearchPath of the search engine.
Search : : ~indSolution() We can also easily modify the goal condition for it
° ... to serve a partial-order planner. In this case the class
if (goal_->satisfied(state)) JugState encodes all necessary elements of a partial
order plan, including steps, variables, initial and goal
... ° steps, causal links, threats and open preconditions.
} /* findSolution */ class JugGoal3 : Goal {
With the above design, even if we change the goal public :
verification mechanism, the search engine does not need JugGoal3() : {
to be changed. All that is required is that the users bool satisfied(JugState partial_order_plan)
configure the search engine with a different concrete // return True when
goal verifier object. The design is summarized in figure // (1) no open preconditions exist and
2. // (2) no (negative) threats exist
We illustrate the implication of this design using the // for all causal links
water-jug example domain. Suppose the states in this } /* satisfied */
domain are encapsulated in the class JugState. The }; /* JugGoal3 */
goal of the water-jug problem is to reach a state in Successor Generator
which one of the jugs holds a specific volume of liquid. The Strategy pattern can be applied to isolate the vari-
To implement such goal verifier, we define a concrete
subclass of Goal. ation of the successor generation mechanism in a simi-
107
no reviews yet
Please Login to review.
