jagomart
digital resources
picture1_Design Patterns Pdf 182768 | Ws98 03 011


 127x       Filetype PDF       File size 0.84 MB       Source: www.aaai.org


File: Design Patterns Pdf 182768 | Ws98 03 011
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 ...

icon picture PDF Filetype PDF | Posted on 31 Jan 2023 | 2 years ago
Partial capture of text on file.
                 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
The words contained in this file might help you see if this file matches what you are looking for:

...From aaai technical report ws compilation copyright www org all rights reserved design patterns for planning systems qiang yang and philip w l fong edward kim school of computing science simon fraser university burnaby bc canada va s qyang cs sfu ca abstract want to demonstrate how can be em in this work we are interested building a software ployed structure search based planner so engineering discipline system our that the complexity constructing ai objective is enable become more managed second discuss role played configurable modular with help object li by pattern catalog during process de braries capturing well designed experiences com signing evolving framework re mon it hoped port allowed us flex thus constructed will ibly configure different applica reusable modifiable also effort tions follows closely current trend contribute movement towards industrially making bvb applicable supply dynamic bhb subfield rigorous dis first introduce concept pat cipline than just smart algorithm...

no reviews yet
Please Login to review.