Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A recursively controlled production system : an implementation of a theory Girard, Jean-Louis 1983

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1983_A6_7 G57.pdf [ 5.15MB ]
Metadata
JSON: 831-1.0051845.json
JSON-LD: 831-1.0051845-ld.json
RDF/XML (Pretty): 831-1.0051845-rdf.xml
RDF/JSON: 831-1.0051845-rdf.json
Turtle: 831-1.0051845-turtle.txt
N-Triples: 831-1.0051845-rdf-ntriples.txt
Original Record: 831-1.0051845-source.json
Full Text
831-1.0051845-fulltext.txt
Citation
831-1.0051845.ris

Full Text

A RECURSIVELY CONTROLLED PRODUCTION SYSTEM: AN IMPLEMENTATION OF A THEORY by JEAN-LOUIS B.Sc.  (Hons.)  University  GIRARD of B r i t i s h  Columbia,  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department  We  o f Computer  Science)  a c c e p t t h i s t h e s i s as conforming to the r e q u i r e d s t a n d a r d .  THE UNIVERSITY OF BRITISH COLUMBIA October,  (c)  Jean-Louis  1983  Girard,  1983  1982  In p r e s e n t i n g requirements  this thesis  fulfilment of the  f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y  of  British  it  freely available  Columbia,  I agree that f o r reference  agree t h a t p e r m i s s i o n for  in partial  scholarly  the Library  shall  and study.  I  f o r extensive  copying or p u b l i c a t i o n  f i n a n c i a l gain  shall  of this  C'.nrn  piA  h  The U n i v e r s i t y o f B r i t i s h 1956 Main Mall V a n c o u v e r , Canada V6T 1Y3  Date  DE-6  (3/81)  (ffrkW  I  <T,  I ti s thesis  n o t be a l l o w e d w i t h o u t my  permission.  of  thesis  p u r p o s e s may be g r a n t e d by t h e h e a d o f my  understood that  Department  further  copying o f t h i s  d e p a r t m e n t o r by h i s o r h e r r e p r e s e n t a t i v e s .  for  make  r  Columbia  I  9 8 ?>  i^nc.p.  written  11  ABSTRACT  Production computational artificial theory.  model  used  practical  to  effect  even  the  interpreter;  t h e power of  an  in  the  the  are  reducing  to consider  at  The  is  technique  production arm  higher  implemented  an  languages,  schemes  choice  of  the  have  level.  Issues  of  in  a  recursively  imbedded sometimes  concerned the  with  s e t of  wire-wrapping  task.  a  rules  metaknowledge discussed. controlled  i s used to a u t o m a t i c a l l y program a  electronic  been  productions.  g e n e r a l i t y and  determines  in  computability  r e c u r s i v e c o n t r o l s t r u c t u r e s are  system which  to accomplish  of  in formal  This thesis i s  system which r e c u r s i v e l y  and  nondeterministic  o f t e n domain d e p e n d e n t and  production  representation  and  nondeterministic  thus,  next  parsing  research,  the model.  the  inherently  p u r p o s e s , a number of  These c o n t r o l t e c h n i q u e s in  are  intelligence  For  proposed  Systems  robot  iii Table  of  Contents  Abstract  i i  Table  of Contents  Table  of F i g u r e s  i  i  i v  1 Introduction  1  1.1 D e f i n i t i o n s  1  1 . 2 Mot i v a t i o n  3  1.3 T h e s i s O v e r v i e w  4  2 Framework  of the F i e l d  2.1 H i s t o r i c a l 2.2 T h e Q u e s t 2.3 T h e s i s  6  Perspective  6  for the Explicit  C o n t r o l of Reasoning  Foundation  11 16  2.4 J u d g e m e n t C r i t e r i a  26  2.5 D o m a i n F r a m e w o r k  27  3 The D e s i g n 3.1  o f RCPS  Representing  3.2 E x t e n d i n g  31 t h e C o n t r o l Language  31  t h e C o n t r o l Language R e p r e s e n t a t i o n  3.3 T h e C o n t r o l L e v e l PS  35  4 RCPS 4.1  34  38 Search  4.2 R u l e  Strategy  Syntax,  4.3 R e p r e s e n t i n g 4.4 T h e R e c u r s i v e  Semantics, State  Reference:  and R e p r e s e n t a t i o n  Information  Virtual  4.5 T h e R C P S R u n - T i m e 4.6 C o n t e n t  38  i n Plans  43  Machine  46  System An E x a m p l e T e r m i n a l  39  49 Session  50  i v 5 R e s u l t s and E v a l u a t i o n 5.1 P r o b l e m 5.2 R u l e s 5.3 A d d i n g  Specification  and E x p e c t e d R e s u l t s  56  f o r an E x h a u s t i v e U n c o n t r o l l e d D e r i v a t i o n a Goal D i r e c t e d  5.4 Augmenting 5.5 R u l e s  56  60  S t r a t e g y v i a Meta R u l e s  the Goal D i r e c t e d  65  Strategy with H e u r i s t i c s  f o r C o n n e c t i n g Many C h a i n s  5.6 P r a g m a t i c  71  Considerations for Solving  a Real Problem  6 Conclusion  .. 74 78  6.1 R e c a p i t u l a t i o n  of the R e s u l t s  6.2 R e l a t e d I s s u e s a n d D i r e c t i o n  78 f o r F u r t h e r Research  .... 80  Bibliography  82  APPENDIX A T r a c e o f t h e C o n t e n t APPENDIX B C i r c u i t  68  Reference  Example  87  Design  APPENDIX C Complete APPENDIX D A u x i l i a r y  89  Set of M u l t i w r a p Rules P r e d i c a t e s f o r Wire-Wrapping  APPENDIX E T r a c e o f Metawrap P r o b l e m  91 Problems  .. 95 97  APPENDIX F U s i n g RCPS on MTS  111  APPENDIX G RCPS I n t e r p r e t e r  112  APPENDIX H U t i l i t i e s  121  f o r RCPS I n t e r p r e t e r  Table  1. D a t a Dependency  Links  of  f o r the Rules of I n f e r e n c e  2. U n c o n t r o l l e d  Derivation  3. I n t r o d u c t o r y  Problem S o l u t i o n  4. E x h a u s t i v e D e d u c t i o n 5. I n t e l l i g e n t 6. R e a l i s t i c  o f an I t e r a t e d Sequence  and R e s u l t i n g  Solution  Problem  Figures  Solution  19 33 60  Solution  64 71 77  1  CHAPTER 1  Introduct ion  "Production Systems a r e a c o n t r o l s t r u c t u r e with promising attributes for building generally intelligent systems with large knowledge b a s e s . " R y c h e n e r , 1977 The for  computer  computational  Neumann  machine  science  community  engines,  a v a r i e t y o f models  and r e c u r s i v e  m o d u l a r and a d d i t i v e n a t u r e , become  a  popular  h a s u s e d , as a f o r m a l  model  function  the for  i n c l u d i n g t h e Von  theory.  production  Because of  system  artificial  basis  (PS)  intelligence  its has  (Al)  research.  1.1 Def i n i t i o n s The  term  "production  denote  a rule-based  consult  [Davis  Birnbaum, of the Each  system.  & King,  Hayes-Roth,  productions knowledge production  postcondition.  system"  76]  has These  used  in  For a t u t o r i a l [Stefik,  & Sacerdoti,  ( r u l e s , or a c t i o n s base,  is  t o PSs Benoit,  A PS c o n s i s t s  of a s e t  synonomously),  and an a l g o r i t h m ,  called  two  a  components  to  Balzer,  a r e used  components,  paper  introduction  Aikins,  82].  this  are  called  the i n t e r p r e t e r .  precondition sometimes 1  and  called  a a  Introduction  2 condition-action  pair  nondeterministic  or  if-then  rule.  a l g o r i t h m , modelled a f t e r  u t i l i z e s these r u l e s  The  [Nilsson,  basic  80], which  i s presented below.  Procedure P S ( S i , S f ) Begin Database = i n i t i a l s t a t e S i U n t i l Database = f i n a l s t a t e Sf Begin C o n s t r u c t from the t o t a l set of r u l e s the a c t i v e set A { Control } C o n s t r u c t the c o n f l i c t s e t , C, from those r u l e s i n A whose p r e c o n d i t i o n holds i n c u r r e n t database { Condition S a t i s f a c t i o n } S e l e c t r u l e R from from c o n f l i c t s e t C { C o n f l i c t Resolution } Database = s t a t e where the p o s t c o n d i t i o n of R holds { Rule A p p l i c a t i o n } End End Given  an  initial  state,  S i , the purpose of the PS i s to apply  r u l e s to S i i n order to achieve the f i n a l such or  a  PS i s o p e r a t i n g  initial backward  and s p e c i f y i n g  goal-driven. simultaneously possibly  using  I f every  is  to  interchanging  by  current  many s u c c e s s o r s , we say the  otherwise i t i s d e p t h - f i r s t .  to  rules  chosen the  the  s t a t e as the i n i t i a l  said  backward rule  applied  By  the f i n a l  as the f i n a l , the PS fashion  We say that  i n a forward manner using forward  i t i s s a i d t o be d a t a - d r i v e n .  conditions  state Sf.  be  rules' and the  operating  or  it  the  is  in a  i s s a i d to be  conflict  state,  search  rules  set i s  resulting  in  breadth-first,  The term "search s t r a t e g y "  i s used  to denote the d i r e c t i o n of search, the manner i n which the space is  searched  conflict  ( i . e . breadth-first  resolution  used  or  [Georgeff,  depth-first), 82],  The 1  and  the  conflict Introduction  3  resolution merit,  some  strategy from  is  A  the  total  PS  procedure  subset  is  the  a  may  of  knowledge  say,  a  sequence of  rules  which  the  can  then  initial  typically  state  particular,  "metaplanning"  predicate  by  order  "plan"  a  set  heuristic  The of  control  active  rules  and  the  its to  the  final  state  which  over  that  state  that  state.  or  The  the final  applying  the  sequence  of  rules  to  stated.  The  sequence  of  rules  is  the  i s concerned  i s used  on  PS  is called a  with  PS  control  implementation own  control  describe  this  "planner".  of  strategies;  a  planner  strategy.  in  which  The  term  by  two  process.  Motivation  The  research  fundamental  In  i n the  plans  based  rules.  select  accomplishes  i t describes  recursively  to  result, either  total  document  applicable  used  obtained  called a  This  1.2  be  selects,  base.  as  satisfies,  state  the  procedure  return,  which  in  c h a r a c t e r i s t i c s of  1)  i t s procedural  2)  its descriptive  the  both  of  context  of  any  is  motivated  automaton  [Mackworth,  83]:  adequacy  PSs,  adequacy. the  goal  of  the  a  has  a  research  is  to  increase  these.  Typically, leads  metaplanning  to  the  although goal,  a  PS  combinatorial  single  inference  number  of 1  path  paths  that are  Introduction  4  considered  before  the  correct  h e u r i s t i c a l l y based procedures  one  is  (e.g.  found.  A  number of  A*) have been developed to  i n c r e a s e the p r o b a b i l i t y of choosing the c o r r e c t path to expand. The approach taken here i s to attempt chosing  a  rule  generated; that at  every  to  the  point  to r e f i n e the  where  numerous  process  of  paths are not  i s , the goal i s to decrease the branching f a c t o r  state.  An  invalid  branch  i s one with a branching  f a c t o r of 0; that i s , the c o n t r o l s t r a t e g y suggests an empty set of  active  rules.  In  effect,  produces h e u r i s t i c a l l y v a l i d  the  technique  branches  as  advocated only  opposed  to  pruning  i n v a l i d ones a f t e r the f a c t , as i n A*. Whereas  heuristics  were  typically  imbedded  i n t e r p r e t e r , or a s p e c i a l e v a l u a t i o n f u n c t i o n , in  a  non-standard  language,  representing control h e u r i s t i c s been  used  These  so  second  d e s c r i b e how  extensively order  rules  in  the  language  i s the same Al  and of  language  in  the  represented choice  for  that  has  - namely, p r o d u c t i o n r u l e s .  are- c a l l e d  metarules  since  they  to use the r u l e s .  1.3 T h e s i s Overview This control  thesis  i n PSs.  Recursively  proposes  a  T h i s language  Controlled  metalanguage f o r reasoning about i s implemented  Production  i n . a PS  called  System (RCPS) which  a  i s then  used i n the domain of r o b o t i c s to judge i t s e f f i c a c y .  1 Introduction  5  Although considered  Chapter  sufficient  which  procedural this  two  used,  provides  has been  PROLOG,  framework  passages  PSs  a  i s not  code. t o the  definition  i s presented which  While paying p a r t i c u l a r  of  and background  taken; i n p a r t i c u l a r ,  in  language  i s  i n the context of PSs,  t h e few b r i e f  a  i n PROLOG,  of  i s the basis to  attention  to the control  a number o f P S s a r e c o n s i d e r e d .  Chapter definitions  three  data The  four  t h e d e s i g n o f RCPS  p r e s e n t s t h e RCPS l a n g u a g e  structures  used  RCPS l a n g u a g e  robotics,  to  descriptive Chapter impact  explicates  i n terms  of the  i n c h a p t e r two.  Chapter and  to clarify  control  research.  knowledge of t h i s  two c o n s i d e r s  depth  Chapter approach  i m p l e m e n t a t i o n , programmed  i n depth, a working  necessary. in  t h e RCPS  judge  and the  algorithms  t o implement i t .  i s used  i n chapter five,  i t s worth  in  terms  of  i n the domain of procedural  and  adequacy. s i x concludes  t h e y may h a v e  by s u m m a r i z i n g  the results  and the  on f u t u r e P S s .  1  Introduction  6  CHAPTER 2  Framework  Throughout controlling Indeed,  the  their  the quest  2.1 H i s t o r i c a l  easily  i s still  Turing  of  PSs,  various  nondeterminacy  methods  have  been  for  proposed.  u n d e r way.  Perspective PSs have  jointly  proved  history  inherent  Historically, attributed  of the F i e l d  t o Markov  [Minsky,  machine  their  (TM)  and Post  67] t h a t and  basis  thus  i n formal [Cutland,  logic 80].  PSs a r e e q u i v a l e n t can  compute  and  are  I t c a n be  i n power  to a  a n y TM c o m p u t a b l e  funct ion.  As d e f i n e d P =  by [ C u t l a n d ,  8 0 ] , a Post  system,  P, i s a  triple:  Q)  ( I , A,  where: I  is a finite  A, a s u b s e t  alphabet  of I * , i s the s e t of axioms  Q i s a s e t of productions g S g S 0  1  1  2  ...  of the form:  gm-1Smgm -> h S i h S i 0  1  1  2  ...  Sinhn  where: g ,...,gm,h ,...,hn 0  0  a subset  of I * a r e f i x e d  2 Framework  strings  of the F i e l d  7 S ...,Sm a r e  arbitrary  1 f  S i t,...,in, A there from for  i  are  a by the  a  Post  Post  i  n  are  arbitrary  strings  whose  subscripts,  1,2,...,m.  from  string exists  S  strings  w  i s generated  p  e Q  of  system  system  P  the  from a form  P and  string  a ->  We  i s denoted  i s the  a by  reflexive  a =>  production  say, co.  is  The  transitive  p i f  computed  solution  set  c l o s u r e of  =>  thus: S(P)  =  { u> | a  e A,  Markov's notion differs  production  2)  there  may  3)  an  Markov  (i.e. 2) apply 3)  the  how  the  the  first  the  similar  to  Post's  and  has  the in Q  form  be  S,gS  2  ->  s i n g l e d out  i s given  to  S,!^  as  uniquely  being" t e r m i n a l determine  the  applied.  applies  one  productions  production  i n the  fixed  in  Q  sequentially  a p p l i e s , then  use  the  top  most  one  way,  order)  a p p l i e s to a  leftmost  string  i n more t h a n  string  h a l t s when e i t h e r  production  strategy  in Q  following strategy:  algorithm  left-to-right  is  i t should  i f a production i t to  computable  strategy  i f more t h a n  terminal This  to  u>]  productions  algorithm  according 1)  be  explicit and  a =>*  f o l l o w i n g ways:  every  rule  e L*,  of  1)  next A  i n the  w  no  production  a p p l i e s , or  a  is applied.  is  sometimes  called  the  top-to-bottom  strategy. 2  Framework  of  the  Field  8 C o n s i d e r , as an example, taken from [Galer & the  following  Markov  symbols  a,  /3 / L,  70],  e Z*.  a l g o r i t h m to reverse a s t r i n g  p e r i o d i s used to denote t e r m i n a l p r o d u c t i o n s . auxiliary  Perlis,  For X,  The  e  Y  I,  c a l l e d markers or t o k e n s , and the  n u l l s t r i n g A, the f o l l o w i n g set of p r o d u c t i o n s  accomplish  the  said function. Q1 Q2 Q3 Q4 Q5 Q6 The  -> /3 (3a -> 0 0X -> X/3 0 "> A. aXY -> YaX A -> a aa  order  of  flexibility  the  productions  in the c o n t r o l  &  Perlis,  crucial  appended  in  labelling  70] as an a l t e r n a t i v e  to  production  Q.  If  it,  the only  technique  presented  control strategy. which  by Each  denotes  some  a p r o d u c t i o n i s a p p l i c a b l e . and a l a b e l  then  transfer  to  the  I*.  -> A aXY -> YaX A -> a a -> A  (Q4) (Q2) (QI) (Q4)  c l a i m that t h i s a l g o r i t h m i s p r o c e d u r a l l y more adequate  If Q6 were the f i r s t would never t e r m i n a t e . 1  The  is  reverse  We  name.  control  l a b e l l e d p r o d u c t i o n s from [Tremblay & Sorenson, 76] w i l l  aa  label  of  set of  Q1: Q2: Q3: Q4:  that  the  is  following  a string e  bearing  is  1  p r o d u c t i o n may have a l a b e l appended to i t production  and  structure .  Consider the f o l l o w i n g [Galer  is  p r o d u c t i o n , for  instance,  the  than  algorithm  2 Framework of the  Field  9  the  first.  tests to  This  for  reverse  in  the  claim  rule applicability a string  second.  least  part  productions however, control this to  does  strategy  an  easily  claim,  be  procedural  By  the  can  the  gradation  order  power  of  ((Q2) ; +  power.  s e t of  strategy;  automaton  s e t ,the  often  in  leads more  i s e s p e c i a l l y true  control  argument  As  allowing  specification  concerning  this  i s  latter  The  control scan  questions  and the  resulting  by a t y p e  (type  The  3  strategy  i s  This  as first  set i n the  control  strategy  3) e x p r e s s i o n  (Q1;  f o r the second  algorithm  expression;  Kleene  used  of the  the production  were a s s e r t e d .  by t h e r e g u l a r  (Q4)*)*.  invite  The Chomsky h i e r a r c h y  i s to repeatedly  be r e p r e s e n t e d Q3)*;  first  i n the second  of t h e c o n t r o l component  the productions  be r e p r e s e n t e d  also  The  expressed  control  increase  of the  needed  algorithm i s  explicitly  (by  57  algorithm  and manipulable.  Q 3 ; Q4; Q5; Q 6 ) * . . T h e c o n t r o l s t r a t e g y can  this  c o n t r o l s t r a t e g i e s we  i tcontrols.  algorithm that  This  that  [Kowalski, 79a].  o f t h e PS  Markov  stated  adequacy  excellent  defining various  regarding power  an  that  the  more a d e q u a t e  specified).  For  consult  convey  fact  18 t e s t s a r e  strategy.  i s more u n d e r s t a n d a b l e  in  the  i n the f i r s t  only  we h a v e  i s explicitly  when t h e d e s c r i p t i v e a d e q u a c y increased.  3, w h i l e  control  a descriptively  to  a r e needed  since  the  not  increase  knowledge  adequate  i t  from  i s further claimed  of)  since  case,  of l e n g t h It  more d e s c r i p t i v e l y (at  i s substantiated  "+"  in  2 Framework  namely, the  Q2;  (Q1;  previous  of the F i e l d  10 expression failure  i s  latter power can  ensures the  control  t h a t Q2 sole  means by w h i c h  be c o m p u t e d  its  70];that  the computational  various  control  languages.  One  productions  via  may  such of  suggest  THTBF  specifying differ only  which  and  we may h a v e  gained  power  the  has been  computational constructs  z  Another  The  computational functions  may  (or  have.  are  can only  in  t o attempt  main  they to  allowing the  given.  i s irrelevant. to  of The  control Although  explicitly  computational  level,  nor i n  advantage  to  i s i n t h e p r o c e d u r a l adequacy.  by  allows  number  by t h e s e  by h a v i n g  base  constructs  a  order  are  attempt  production  t h e p r o d u c t i o n s , no  at the control The  as  control  be e f f e c t e d  adequacy  [Hewitt, 72].  the theorem  next  are  programming  a l g o r i t h m , which  by  of a s s e r t i o n  descriptive  model.  the  with  they  production  method,  Markov  attempted  Markov  level  theorems  These  per production,  gained  high  i s Micro-Planner  suggest  the labelled  the order  order  2  and  rudimentary,  t h e name o f t h e n e x t  of productions  constructs  are  As an a l t e r n a t i v e  from  one s u g g e s t i o n  express  language  clause,  slightly  sequencing  remove)  f o r many v e r y  p r o p e r t i e s i t must  suggestions  Q3 c a n b e t r i g g e r e d .  models of Post  Micro-Planner  a THUSE c l a u s e .  filter,  since i t s  i s , a l l TM c o m p u t a b l e  strategies  the foundation  called)  once  b u t no m o r e .  nevertheless  The  at least  s t r a t e g y does not add ( o r  [Galer & P e r l i s ,  Although  i s triggered  the  these  Intuitively,  overall control there i s  i s SNOBOL. 2 Framework  of the F i e l d  11  considerable  evidence that h e u r i s t i c a l l y  h e l p the o v e r a l l performance of the under  the  caveat  that  the  system;  effort  suggestion i s l e s s than the e f f o r t  v a l i d suggestions w i l l however,  needed  this  is  to  compute  the  to e x h a u s t i v e l y  attempt  all  the p r o d u c t i o n s .  2.2 The Quest for the E x p l i c i t Such  a  variety  of  C o n t r o l of  methods  have  Reasoning been  proposed for  the  comparison  is  c o n t r o l of reasoning that some common ground f o r needed.  Since  relative  criteria  criterion  i s proposed.  to  the  every  amount  specified  and  of its  technique  for  has i t s own j u s t i f i c a t i o n  judgement,  a  more  global,  and  theoretic  The techniques are c a t e g o r i z e d a c c o r d i n g  explic i t ease  control  of a c c e s s .  knowledge  that  can  There are b a s i c a l l y  be  three  categor i e s . 1) The  control  and can be accessed example strategy. 2) The  of  this  strategy only  is by  imbedded in the r u l e modifying  strategy  is  the  the  interpreter  interpreter.  original  Markov  An  control  This is c a l l e d "hard-coded". control  strategy  is  available  as  a  program  object.  For example, the l a b e l l e d Markov a l g o r i t h m  explicit  s p e c i f i c a t i o n of the next r u l e to attempt and i s  level  allows  the  called  "softly-coded". 3) The this  control  strategy  i s completely s e p a r a t e .  f l e x i b l e control strategy  Examples of  have not yet been c o n s i d e r e d 2 Framework of the  and Field  12 is  called  "separately-coded".  Most strategy  of the e a r l y category.  heuristic between  GPS  evaluation the  a  difference.  Given  strategy  a  the  rule  table  single  rule,  to  with  recursing  on  difference  i s used;  difficult control of  look  the  thus,  than  any  structure  goal  i s a  from  the  from  a  the  for  that  only  smallest.  fails,  from  the  table  then  are  current  never  flexibility  (i.e.  When  sorted  of the d i f f e r e n c e s  i n p a r t i c u l a r , the rules  rule.  i s attempted.  subgoals  The  function,  to  scheme,  a  of  (state-state)  largest  table  a that  method  the associated  difference  the strategy  i s the ordering  and  evaluation  indexing  only  ancestor.  as  a  distance  state,  used  i n the table  insures  both  the  particular  typically  subgoals,  difference  the t a b l e ) ;  with  the next  requires  approximate  table  up  control  s p e c i f i e d as the s t r a t e g y  r e t r i e v e d by t h i s  associated  descending  The  69]  the  t o be  are ordered,  thus  to  and  rule  i n the hard-coded  & Newell,  a difference  is  The d i f f e r e n c e s If  state  the interpreter.  associating  the  [Ernst  function,  current  difference-operator controls  PSs a r e c l a s s e d  by more  in  the  (i.e.  rows  columns) are  not  ordered.  STRIPS is  a PS  [Fikes  based  control of  STRIPS  to  solve  on  schemes  & Nilsson, GPS  goals  [Fikes,  evolved  - a l l o f them h a r d  i s backward the  which  71]  Hart,  through  coded.  and d e p t h - f i r s t .  The  in left-to-right  order  The  & Nilsson, many  different  search  strategy  overall strategy by c h o o s i n g  2 Framework  72]  is  a  rule,  of the  Field  13 indexed the  by g o a l ,  fewest  to  preconditions in  the order  is  through  goals  solves  preconditions  backtracking  subgoals  which  any  that  specified.  The o n l y  ordering  be  linearly  [Tate,  75].  a r e NOAH  NOAH p r o d u c e s  non-linear  then  linearized  plans  i n non-linear  goals  by  priority by  deciding  accessible classify this  have  sometimes  Lesser,  known  effected ofthe that  as goals  may  of a network Warplan  through  goal  [Warren, 7 4 ] , which i s produces  the plan  called  until  a  control  structure  of a rule or goal.  the  80],  uses  heuristic  i n the conflict  i s chosen  an agenda, h a s been  first.  as a program  a  set.  The  I f these level  and thus  i ti s  heavily  criticized  function  action  object,  we  with were could  i n Hearsay I I Agenda  [Davis,  2 Framework  of  to assign  priorities  hard-coded. (e.g.  for  Hearsay I I ,  scheduler,  systems as s o f t l y - c o d e d ; however,  been  be  for solving  critics.  as  & Reddy,  as  the rules,  i s not the case  systems  can  the assumption  proposals  by b a c k t r a c k i n g  The  recursively solved  not warranted  i n t h e form  scheduling  priority  these  plans  researchers  to the rules  from  i s  failure.  and t h e o r d e r i n g  In general,  with  interact.  the  variables,  highest  of  rule  the option of  [ S a c e r d o t i , 77] and Warplan  order  many  upon  priorities  case  the goal  solved  queue,  [Erman, Hayes-Roth,  the  of  The  with  control that  s p e c i a l purpose  no l o n g e r  suggested  first,  in  Two c l a s s i c  interactions  five  remain  goal.  of t h e a p p l i c a b l e r u l e a r e then  the  can  A  i s attempted  i n the preconditions.  interact  the  the current  based  80a])  as  of the F i e l d  1 4 being  opaque.  The  Al  programming  [Roussel,  7 5 ] , used  The  strategy  search  failure-driven  to  language  PROLOG  implement  RCPS,  backtracking. left-to-right.  softly-coded  PS  can  predicate Consider SPY  i s  3  the flow Example  <<<<-  used the  to  only  also  restrict flexibility  discussed  with  control  automatic  strategy  PROLOG h a s b e e n c a t e g o r i z e d  the predicate  t h e f o l l o w i n g example  predicate ,  trace /* */ P Q Q R  be  since  The  first  70]  i s a s o f t l y - c o d e d PS.  i s backward and d e p t h - f i r s t  top-to-bottom  level,  [Colmerauer,  i s as  a  ", a v a i l a b l e a t t h e o b j e c t alternative  rules.  i n the control presented  in the last  structure.  by [ B y r d ,  reference,  This  80], A  i s used t o  of c o n t r o l . PROLOG r u l e s , f a c t s ,  and goal  Q & R. S. T. A & B.  S. A. <-P. Entering P Entering Q Entering S Exiting S Exiting Q Entering R Entering A Exiting A Entering B Failed B Redo A  The SPY p r e d i c a t e , i m p l e m e n t e d t h e U.B.C. MTS/G s y s t e m , i n f i l e 3  by t h e a u t h o r , JGIR:SPY.  i s a v a i l a b l e on  2 Framework  of the F i e l d  15 Failed A Failed R Redo Q Redo S Failed S Entering T Failed T Failed Q Failed P  ?  to,  The  rules  are  ordered  available conflict and  1)  for  the  of  the  i t s use  choice  the  order  i s used  cut  has  have  PROLOG  may  asserted. to  prune  already  been  backtrack  The  cut,  the  spun a  proposed  "/",  remaining controversy  [Clocksin  &  of  others  a  rule:  once  a  can  be  rejected.  used  to  implement  rule  i s known t o  negation  as  be  failure  78] a  generate  backtracking)  practical  and  c o n s i d e r a t i o n s , the of  rules  abbreviated  above and (confirm  RCPS.  1)  CR  2)  CF  (cut-fail)  3)  GT  (generate-test)  simple  test:  cutting  i n m u l t i answer  implementation  A  the  level,  combination:  Terminate  (i.e.  use  to  set, which  81].  Cut-fail  3)  For  rules  c o r r e c t one,  [Clark,  program  The  Confirming  2)  conflict  according  the  set.  certain  Mellish,  the  at  i n the  I t s use  cut  out  further  answers  problems. i s used  extensively in  i s documented  according  to  the the  thus:  rule)  means of  achieving a separate  control  2 Framework  component of  the  is  Field  16 suggested Melle, A  by O n c o c i n  & Jacobs,  control  block,  description control  of  blocks  interpreter) invoked blocks next  2.3  associated how  data,  80a],  [Georgeff, Sussman, A  while  82].  reasoning, Steele,  problem  solver  system.  Every  RCPS the  A  the  Campbell,  protocol  Van  management.  a goal,  serves  as a high  level  i s  be a c c o m p l i s h e d .  These  to from  the  relevant control  rules  data,  (and the  the rules  block.  guide  separately  a minor  These  t o be  control  the interpreter.  coded c o n t r o l  Sussman,  definition work role  AMORD,  also  type  of  order  a variable.  of  The  strategies.  The  the  have i n  The a c t u a l  syntax. AMORD  Doyle,  Steele,  first.  explicit  control  by [de K l e e r ,  structure  of the  i n the rules an  of the  explicit  the rules.  by t h e f o l l o w i n g  logic  i s by  presented  control  of  used  be p r e s e n t e d  for  flow  on a s y s t e m by  control  represented must  The  [de K l e e r ,  and w i l l  represented  a r e t o be e l u c i d a t e d  works. i s based  h a s been  77].  deduced  by  system  i s explicitly fact  major  interpreter  rule-based  called  link  first  on t w o  third  ideas  denote  task  oncology  as s c r i p t s which  the  77] plays  dependency  with  or another  i s founded  softly-coded  Doyle,  for  Bishoff,  Foundation  within  [Davis,  Scott,  separately  presents other  thesis  control  the  specify  a r e regarded  Thesis  a system  a r e coded  on t h i s  The  of  81],  and  section  [Shortliffe,  These  example which  T h e "*" p r e f i x constructs 2 Framework  data basic uses a  i s used t o  will  n o t be  of the Field  17 considered.  Consider  the  following  facts  and  rules  of  inference.  2 Framework  of  the  Field  18  H U M A N ( * X ) -> F A L L I B L E ( * X ) HUMAN(TURING) A B  A -> B A  A & B  B  An  exhaustive  pertinent  uncontrolled  to the  HUMAN(TURING) the  derivation  (such  produces a wealth  of  the  goal  of f a c t s not  FALLIBLE(TURING)  a s : HUMAN(TURING) & HUMAN(TURING));  rules of inference  need  search  f o r i t h a s been  c a n be r e s t r i c t e d  to apply  only  however, when  shown by a u g m e n t i n g t h e p r e c o n d i t i o n ,  SHOW(A & B ) A B  SHOW(B) A -> B A  A & B  B  Subgoals are generated  by t h e f o l l o w i n g  SHOW(A & B )  SHOW(A & B ) A  SHOW(A)  SHOW(B)  &  a  thus:  rules:  SHOW(B) A -> B SHOW(A) If  we  are  again  given  the i n i t i a l  SHOW(FALLIBLE(TURING) & HUMAN(TURING)) only  f a c t s as w e l l as t h e f a c t to  show  interest,  the  f a c t s now g e n e r a t e d a r e :  SHOW(FALLIBLE(TURING)) SHOW(HUMAN(TURING)) FALLIBLE(TURING) FALLIBLE(TURING) Since  the goal  every  r u l e h a s been  & HUMAN(TURING)  has e f f e c t i v e l y restricted  been  asserted  to fire  only  as a fact to solve  2 Framework  a  and s i n ^ e goal  or  of the F i e l d  19 subgoal,-  there  directed". are  The  dependent  dependencies, facts.  is  little  problem on  Since  with  the  explicit a  doubt this  is  i n terms of  the  facts  derived main  facts.  Figure  We  Figure  r u l e s of  B  see,  t r u e and  \  are  no  other  that  1 shows t h e  To  conclusions  separate  asserted only  facts,  longer  these  with  if  the  affects  dependency  the  it  has  control  the  links  over  t r u t h of  the  f o r the  two  / \  /L  ft I  for there  few  "The problem a l w a y s s u c h an  are  believed  SHOV/(ft L B )  B  example, is  SHow(fl)  SWOW(B)  1. D a t a D e p e n d e n c y L i n k s  a  is  inference.  "SHOW(A & B ) " . there  of  d e r i v a t i o n i s goal  assertions.  , justifications fact  the  approach  control  well-founded-support derivation  that  "A  no  i s true  dependency  Although points  & B"  f o r the  of  these  because the  techniques  similarity  of generating easy t a s k .  on  . non  Rules  worth  of  Inference  "A"  and  control  are  not  interacting  i n RCPS,  The  subgoals  2 Framework  of  are  assertion  used  noting.  "B"  the  basic  is  not  Field  20 concept  i s  their  the explicit  introduction,  distinguished, RCPS c a n a l s o facts; level  thus,  are  the data  explicitly  to  the explicit the  control  does  A general  applicable it  will  notion  PS  to  level;  of t h i s  the  in  exhaustively  nondeterminism  or  and need n o t  i n RCPS  refers  the  that  i sfor the  the  resulting  control  about c o n t r o l  level  over t h e  facts.  i s proposed  the techniques are source,  of PSs .  saturation;  6  reasoning  that  a space the  of  of the derived  f o r the explicit  search  level  versa and  mechanism and knowledge  i n the context  simply  truth  i t i sclaimed  control  t o the object  AMORD,  the truth  t o any computational  of i n e v i t a b l e  but not vice  i s , the justification  f o rreasoning  80a]. Although  i s needed.  object  distinguished  the  longer  on  i sthat  returned  by  of the object  "justification"  not  as  link  t h e scope  scope  Since, no  inference  metalevel  that  and  framework  motivation  the  do  i swithin  dependency  not a f f e c t  be d i s c u s s e d  The  and  The term  Therefore,  5  [Davis,  control  inference  conclusion .  by  at  restated.  control  of  derivation  The e f f e c t  are  dependency  dependencies a r e s t i l l  be  from  assert  facts.  facts  data  the deduction  available  of control  control  explicit  explicitly  deduction.  facts  the  the  however,  assertion  large  about  control i s  i s , the inability  either  due t o t h e  number  of  of a  inherent  rules.  The  T h i s i s , i n some w a y s , c o m p l e t e l y o r t h o g o n a l t o AMORD. T h e work r e p o r t e d i s from t h e development of the rule-based system Teiresias [Davis, 79] and thus much o f t h e o r i g i n a l d i s c u s s i o n i s i n terms of r u l e s and m e t a r u l e s . 5  6  2 Framework  of t h e F i e l d  21 solution  offered  applicable  rules  generally  known  technique  general  on  the  the  index  for  as  conflict  scheme u s e d  this  the current here  search  strategy i s depth-first according  control  strategies  as  metarules,  purpose  inference  engine  of  level  object  the  set  retrieve  order a  set.  are  rules.  The  i s  the rules.  not  and  the  conflict  set  t o be s o l v e d  highly  A system  according  like  order  which  are interpreted rules,  order  the goal  rules  rules,  sets.  The  interpreter,  unwinds with  (partially)  ordered  by  highest to refine  shortened  of  known The  t h e . same  i s to refine  the set  retrieves proceeds t o  order  set  the next  the net e f f e c t  and/or  are  the goal.  and then  of  Since the  The s p e c i f i c a t i o n  associated with  level  GPS,  strategy  the  also  associated with  The p r o c e s s  by s e c o n d  on  to the difference  The s e a r c h  solve.  by  dependent  i t i s dependent  backwards,  they  notion,  new,  In operation, the interpreter  b y t h e common  potentially  i s .  specifically,  i s accomplished  as the o b j e c t  any h i g h e r  interpreted,  to the goal  metarules,  of r u l e s  the s e t of  f o r the e x p o s i t i o n of the ideas.  which  of these  i s  fledged problem  s t a t e and the g o a l .  i s  indexed  task  i t s operators  MYCIN  refine  i t . Though t h i s  The t e c h n i q u e  to access  indexes  to  7  s t r a t e g y ; more  used  is  resolution ,  a full  inference system.  instance,  problem  by o r d e r i n g o r p r u n i n g  i s considered  search  between  this  f o r accomplishing  refinement a  to  of  is  lower  producing  s e t of object  The term "conflict resolution" often means t h e i r r e v o c a b l e c h o o s i n g of a s i n g l e r u l e ( s e e [McDermott & Forgy, 7 8 ] ) ; thus, i n t h i s c a s e we may p r e f e r " c o n f l i c t refinement". 7  2 Framework of t h e F i e l d  22 level  r u l e s which a r e then  simple,  the  explicit  provides  a uniform  interpretation. dependency as  is  in  to  effect,  the  separate  problem  of  from  before  checking  system CPS  i s  ( C P S ) as a four = ( I , D,  h,  and  control thus  the  next.  effecting  of the search  over  first  procedural s t r a t e g y and  the production  retrieved,  even  before  criteria  between  set  as  i t  i s  i s In  checked  i t i s checked f o r  control  information  and thus  there  them.  the c o n t r o l over  for applicability  formally,  for  t h a t , u n l i k e AMORD,  s e t of a p p l i c a b l e  More  appealing  of  of a  sequences of p r o d u c t i o n s .  the a p p l i c a b i l i t y  system,  The n o t i o n  82] i s c o n s i d e r e d  allowable  distinguishing  Davis'  not  a theory  language  Notice  unlike  total  the  control  applicability. is  i s  a c o n t r o l language  specify  ideas.  of  the c o n f l i c t s e t .  when a p r o d u c t i o n  against  appealing  i s independent  on r e f i n i n g  i s  v i a metarules,  s t r a t e g y and t h e d e f i n i t i o n  82] presents  Abstractly, used  are  by [ G e o r g e f f ,  PSs which  not based  t h e scheme  r e p r e s e n t a t i o n a n d common m e a n s  however,  provided  [Georgeff, control  knowledge  on t h e s e a r c h  alternative  Although  r e p r e s e n t a t i o n of c o n t r o l ,  These  refinement,  interpreted.  Also  notice  the rules i s opposed  to  i s no that,  accomplished  refining  the  rules.  Georgeff tuple,  defines  a controlled  production  thus:  C)  where:  2 Framework  of the F i e l d  23 I  i s a s e t of production  D  i s a set of data  h  names  bases  (states)  i s an i n t e r p r e t a t i o n w h i c h  a pair  assigns  t o each  element  of Z  (q, r)  where:  C A state S =  q  i s a total  r  i s a binary  i s a control o f a CPS  predicate  on D  (condition)  r e l a t i o n on D  language  i s defined  over  Z  t o be a  (action) (i.e.  a subset  of Z * ) .  pair:  ( u , x)  where: u  i s a prefix  x  e D.  Inductively, (u,  x,),  and  only  a state  denoted  (up, x )  ( u , x , ) ->  in C  i s d i r e c t l y computed  2  i f q(x,) i s true  reflexive S(CPS,  o f some w o r d  (up, x  2  ) , where  and ( x , , x )  e  2  t r a n s i t i v e closure  o f ->.  u e Z* a n d p r.  The s o l u t i o n  s , g ) = {x : ( s , x ) e R ( C P S )  from a  state e Z, i f  L e t ->* b e set  the  i s :  and g ( x ) i s true}  where: s  e D i s the i n i t i a l  state  g  i s a predicate  D  R(CPS) For  over  = { ( x , y ) : x ->*  example,  for  start  (goal) y} symbol  S  and  the  following  product ions: Q 1 : S -> Q 2 : A ->  ABC aA 2 Framework  of the F i e l d  24 Q3: Q4: Q5: Q6: Q7: the  B C A B C  solution  S(PS) If  -> bB -> c C -> a -> b -> c set i s :  = {a**l,  we d e f i n e  Q7,  b**m, c * * n :  the control  the solution  general,  languages  1, m > 1, n > 1}.  l a n g u a g e C = Q1;  ( Q 2 ; Q 3 ; Q 4 ) * Q5;  Q6;  set i s :  S(CPS) = {a**n, In  1 >  b**n,  context generate  c**n  free  : n > 1}.  rewriting  a l l  systems with  recursively  regular  enumerable  control languages  [Salomaa, 7 7 ] . In with  operation,  a stage  that  function  of  language  need  at  t h e moment  used  determines  the  specified  when t h e n e x t  i n RCPS t o g e n e r a t e  knowledge,  Thus, i n .the  representation  It  i s  be  refine  effected.  form  interesting  £*, a CPS the  i s needed.  language  i s  a  control  be  generated  The  automaton  the  specification forms  as  PS  of an  being control  implicit  language.  the orthogonality  Trivially,  i s reduced  plausible  The  b u t may  metarules,  t o note  of D a v i s .  set of productions  explicitly  explicit of  o f a PS i s a u g m e n t e d  language.  production  of the c o n t r o l  scheme a n d t h a t language  control  the control  the  cycle  the active  n o t be s p e c i f i e d  controlled.  not  the recognize-act  t o a PS.  knowledge  The u s e o f G e o r g e f f ' s  i f  we  of Georgeff's  l e t the Similarly,  source,  no  i f we  control  scheme t o d e t e r m i n e 2 Framework  control do i s  the active  of the F i e l d  25 production scheme t o In note  refine  comparing  Davis'  may  search.  of  s e t , the  also reorder  i t .  independent  i s of  i s the  condition  satisfaction,  comparison  of  the  criteria  i s wasted  cannot  unless  be  the  based  on  entire  set  checked.  however,  i f  the  rule  after  the  active  Georgeff's conditions  An ability is,  the  scheme and  important  ability  to  rules  This  latter  set  has  be  reduced  can  line  suggest  of a  method  strategy, in a  is  the  by  sequence  be  of  after  for  this  of  for the  accessed i s only  the set  the  active rules  and  rule  effective,  i s not  Davis'  redundantly In  under  effect, the  above  RCPS.  v i a the of  point  applicable  Georgeff's  thought  in  satisfiability  determined. to  rule  set  needed  of  criteria  used  the  reducing the  the  depth-first  every  prune  technique  been  of  general  is available  i t  set  applicability  technique  set  we  rules  determination  complete  characteristic  to define a  I f we  i f  Davis'  of  Thus,  compute  the  of  can  i s the  hand,  the  applicability  checked  perhaps  other  a  search  however,  to  set  would apply  entire  required  the  seek  advantageous  set.  rules;  (except  the  consequence.  the  of  applicability.  prunes  the  search  the  the  effort  On  of  use  achieving control,  I f we  of  i s only  little  pruning  implies  set  methods of  a breadth-first  order  comparison).  two  rules  the  i n s u r i n g .for  simply  comparison  mutual  after  preclude  technique  the  Since  set  these  achieving control  reordering  the  this  that Georgeff's  while of  s e t , however, does not  technique  control  rules.  is  the  words;  that  Davis  2 Framework  of  said the  that Field  26 such  a  capability  i s  not  p r o v i d e d by h i s t e c h n i q u e a n d i s a  limitation.  2.4  Judgement  PSs  Criteria  The  criterion  i s  the  penetrance directed  used  t o judge  penetrance  factor  towards  factor  measures  [Nilsson,  the  the goal.  t h e p r o c e d u r a l adequacy  degree  80].  to  Algebraically,  of  Intuitively,  which  a  search  i t i s defined  the the i s  t o be:  P = L / T where: L  i s the length  T  i s the t o t a l  Although  of the path  i t does  may  rate  not,  the degree  however,  effort  needed  to accomplish this  offered  by RCPS  i s from  by  PS a r e c o u n t e d  the  this  effort  control rules,  level  so  expands  as part  criteria  easily  guidance. level  o f T,  the entire remains  The p e n e t r a n c e ,  the results  The  a control  the  since  they  reflect  generated rating  I f , f o r example,  to determine  same  the  Since the guidance  PS, t h e s t a t e s  as  i s used  the  the  the correct uncontrolled  i n chapter  five  to  cannot  be  i n t h e domain.  f o r judging the descriptive  defined  a search i s  t h u s more a c c u r a t e l y  tree  as d e f i n e d ,  o f u s i n g RCPS  t o which  accurately  to accomplish the goal.  the penetrance  version. judge  needed  to the goal  number o f n o d e s g e n e r a t e d d u r i n g t h e s e a r c h .  the penetrance  goal-directed,  found  adequacy  a r e o f a more s u b j e c t i v e 2 Framework  nature.  of the F i e l d '  27 Since can  the control be  described;  characteristic the  only  which  user  presented  hence,  which  in  the  ease  of  prose  of chapter  form  listed  in  computable  strategy  description  i s the  Since the author  far, a subjective  knowledge  are also  by a PS, e v e r y  i s t o be r a t e d .  thus  t h e domain  criteria  i s effected  account  has  been  of t h e ease  with  f o u r was c o d e d  chapter  t h e r e so that  five.  i n RCPS  Some  readers  can  i s  subjective form  their  own o p i n i o n s .  2.5 D o m a i n  RCPS if  Framework  i s a planner  applied  The  and  robot  electronic The  which  will  Unimation].  the  r e t u r n s a sequence  to the current state,  machine  [Condec,  which  execute  circuit  these  The c l a s s  arm,  for  will  this  result  i n the goal  actions  of problems thesis,  of a c t i o n s  i s a PUMA  which state.  r o b o t arm  t o be s o l v e d by RCPS  i s the wire-wrapping of  boards.  wire-wrapping  domain  h a s been chosen  forthe  following  reasons. 1) M a n u a l 2) is  The  wire-wrapping  programming  t e d i o u s and e r r o r 3)  The  4)  The  of n o n - i n t e l l i g e n t  product  modification,  intelligence  technological  limits  prone.  wire-wrapping  machines  prone.  resulting  prototyping,  i s tedious and error  should  be  useful  for  circuit  and p r o d u c t i o n . required  and thus  i s  just  p r o v i d e s a good  within test  2 Framework  current  f o r RCPS. of the F i e l d  28 The  problem  connected. action's  The  that  physically the  consists  robot  solution will  to  specifying  a  the  i s the  problem  accomplish  accomplish arm  of  the  is fitted  these  connections,  with a wire  number  of  sequence  connections. as  pins  wrap t o o l .  of  In  specified  by  The  to  be  robot  order the  tool  to  plan,  has  two  funct ions: 1)  wrap the  2)  cut  In the to  wire  the  the  the  i s not  next  by  cut.  with  language  the  arm  is similar  interrupts,  iteration,  which  solve  the  machine.  task  one  The  as  task  and  solve  that  communicate.  f a r as be  languages  goal.  and  in  for  are a  machine  The  have used  Using  this the  RCPS  from  automatic  must  commanding  by  without  to  particular  programmer  the  a  The  to accomplish  the  arm  asking  goal  pin  conditionals,  algorithm before  robot we  language  structures.  accomplished  the  one  [Condec, U n i m a t i o n ] .  Indeed,  the  to accomplish  particular  VAL  from  pins i f  typically  The  control  problem.  tool  robots,  other  Intuitively, arm  and  consecutive  arm.  facilities  spec i f i c a t i o n . robot  the  robot  t o command t h e  to  of  has  program  the  the  is called  It  solve the  moving  to computer  i s able  problem  of  by  automatically  and  pin  w r a p a number  o t h e r s may  BASIC.  steps  current  computers  resembles  language,  can  The  like  which  communicate VAL  tool  i s accomplished  Machines, language  the  wire.  particular, wire  around  is  a  system  to  problem of  specifying  RCPS how  programming  2 Framework  of  the  the  to of  Field  29 conditionals  and  loops  sequential  plans.  An  Waldinger,  80].  automatically example, the  Most  proposed [Week, 81].  then  term  robot  motion  and  Matsumoto,  of  of  robots  repeat is  the  robot  81]  this  refers a  using  new  from  the  plans  parts.  manually  languages &  have  been  Pagello,  81]  the  &  The  In most  proximity sensors Gorman  the  &  ability  sensors  Takagi,  process  operation.  to  by  of  robot cases,  or,  Shulman,  often accomplished have  which  either  sequence.  [Masaki,  does not  For  a PS  to  are  plans.  Ueno, T s u j i k a d o  taught  i s most  are  &  more 81].  low  level  reason  with  [Futami,  Kijura  &  81].  order  open  [Abe,  through  servoed  fedback  present  Lorenzin  in robotics,  robot  that  machines  number o f  [Bison,  Zuehlke,  few  sequential  81]  simply  [Manna  today A  than  i s o f f e r e d by  to produce mechanical  "taught".  feedback  information  In  cuts  s m a l l a r r a y cameras  negative  execute  & Latombe,  robots  the to  the  simply  "taught",  expected  hardware the  &  guiding  recently, The  are  Eversheim The  the  or  to program  manually is  machine  industrial  programmed  example  Typically,  [Descotte  of  t a s k much more d i f f i c u l t  excellent  programmed  GARI  sequence  is a  to  loops  discussion,  the  1)  realize  2)  find  3)  learn  and  the  realize must  a  be  closed.  automaton current  pose  general  self-sufficient In  automaton,  terms  of  the  a  number previous  must: state  i t s own  of  the  world  problems  knowledge. 2 Framework  of  the  Field  30 The the  practice world  using vision  is  laboratory  a  cart  to  plan  has  proposed  of  of  a  popular  [Moravec,  experimental  f o r example,  a  of  series  a demonstration  [Freita,  Healy  range,  very  by  a  long  automonous behaviour a c h i e v i n g the  81].  Although  delays and  thus  above  in the  three  The  uses  space still  state  A  vision  study  (largest  radio  communications demonstration  system control  require i s an  group  satellite  exploration in  of  Stanford Al  stereo  obstacles.  mission to Titan  general-purpose  & Long,  current  area.  81],  route through  Saturn)  towards  to p e r c e i v e the  some  experiment  characteristics.  2 Framework  of  the  Field  31  CHAPTER  The  Design  3  o f RCPS  " V e r i l y , a s much knowledge i s needed to effectively use a fact as there i s i n the fact. " De K l e e r , D o y l e , S t e e l e , & S u s s m a n , 1977 This  chapter  controlled theory  p r o d u c t i o n system  of  effecting  proposes  control control  in  put forth i s  then  the  design  terms  of  of the  a  definition  by [ G e o r g e f f , 8 2 ] .  generalized  recursively  without  and  The t h e o r y o f changing  the  fundamental d e f i n i t i o n .  3.1  Representing the Control  Language  " A n d we h a v e now m o v e d down another level, to the interpreter of the interpreter-writing language of the representation language." H a y e s , 1977 Recall, terms  c h a p t e r two,  of a control  control sequence in  from  language  specifies  of' r u l e s  t h e sequence  language  over  every  i s called  the  definition  the rule  ( i . e . the last rule  rule  word  t o be  control  names o f t h e P S .  allowable  the c o n t r o l  of  while  sequence. the l a s t  applied)  i s  3 The D e s i g n  in The A rule  called  o f RCPS  32  the a  suffix.  language  There are which  "generate" the  total  we  shall  method. set  essentially  In  call  the  are  compared  match  the  current  rules  applied  so  far) u n t i l  generate  method  suffix  as  the  one  used  by  rule  n a m e s , we  control a  finds  next  word  shall  c o n t r o l language PLAN(R1;  The to  R2;  algorithm match  side)  of  plan upon  one  level  the  always has  this  current  r u l e s , Q1, holds  and  between  Q1  and  applied;  that  be  on  the  and  is  latter  sequence  of  found.  a  the  is  the  sequence  suffix We  The  returns  method  i s but the  words  of  can  of the  represent  thus:  set  these  returns of  rules  rules  the  simply (i.e.  next  attempts left-hand  rule  i s simply  a  to  PS  be  with  a  inference.  concept plan,  to  an  and  thus  Q2  the  precondition  the  until  i s , we  deal  example  Q3.  some p r e c o n d i t i o n .  alternate  control  NEXT_RULE(R).  of  Q2,  from  "next-rule".  success and  r u l e s chosen  rule  while  rules,  with  algorithm  of  and  can  of  operate  three  r u l e Q3  set  the  the  (i.e.  This  such  and  c o n t r o l word and  "plan",  would  Consider  The  called a  extending  simply  i t a  method  the  c o n t r o l word  which  r u l e and  Before  the  implementing  the  of  path  consider.  ->  the  suffix  matching  ; Rn)  current  maximum d e p t h  a  ...  This  Q2  by  the  applied.  than  call be  method,  a matching  Since  shall  the  ways of "accept"  inference  rule to  RCPS.  the  accept to  which  two  want  The  with of  more i t s use  is  given.  precondition  r u l e s can  always  The  solution  the  precondition  to  metafacts  effect  3 The  be  of  applied.  sought of  is Q3  sequencing  Design  Q1  of  to  holds and  RCPS  33 iteration.  A  u n t i l an e d i t forward  concrete  example  condition is  breadth-first  f i g u r e 2, assuming two  is  to input and echo a v a l u e  satisfied.  search  If  would  rules, problem  it  i s not e a s i l y  is also descriptively is  to  a  produce  the d e d u c t i o n  in  of an I t e r a t e d  T h i s s o l u t i o n i s not only p r o c e d u r a l l y strategy  uncontrolled,  iterations.  F i g u r e 2. U n c o n t r o l l e d D e r i v a t i o n  control  left  Sequence  inadequate b u t ,  since  e x p r e s s i b l e in the o b j e c t inadequate.  The remedy to  the  level this  d e f i n e the f o l l o w i n g c o n t r o l language where " * "  denotes any p l a n . 3 The Design of RCPS  34  -•PLAN ( * ) -> N E X T _ R U L E (Q1 ) P L A N ( * ; Q1) -> N E X T _ R U L E ( Q 2 ) P L A N ( * ; Q2) -> N E X T _ R U L E ( Q 3 ) P L A N ( * ; Q2) -> N E X T _ R U L E ( Q 1 ) This  strategy  expression control  can  be  (Q1; Q 2 ) * ;  Q3.  PS i s t o a t t e m p t  backtracking  t o the next  apply,  deduction  both  the  have  first  expressed  i f  scheduling  i t  rule  produced  are  the Control currently  reason  other metafacts  why  the  warrranted.  level  metafacts  1) d o m a i n  Since  Also,  be a u g m e n t e d  the c o n t r o l  2)  current  of  does  The l a s t Q3  the  specified,  suggested  the rule  domain  PS  to  generate  plan metafact; cannot  there  be  i s  two  not rules  attempted  i s c o n t i n u e d by  a  control  however,  why  one l e v e l  with the metafacts.  i s no  providing  they  the c o n t r o l  level  of  inference  The a u g m e n t a t i o n  i s c o n s i d e r e d i n the next  are categorized  language  there  introduced  i s no r e a s o n  t o more t h a n  be a b l e t o r e a s o n  The  rule  3)  Language R e p r e s e n t a t i o n  able  on  thus  i n the order  i s linear. thus  (type  strategy  does not h o l d , t h e i t e r a t i o n  depending  PS c a n n o t  regular  control  rules  i f the  the  Q1.  3.2 E x t e n d i n g  are  the  t h e above  t h e same p r e c o n d i t i o n  and  We  If  by  and of  section.  into:  independent dependent.  domain  dependent  metafacts  cannot  be  generalized,  3 The D e s i g n  a  o f RCPS  35 facility user. PLAN  must We  be  are  i s but  provided  concerned  one.  description  of  the  the  following  1)  the  sequence of  2)  the  complete  3)  every  The  set  of  the  rules  name>) a n d  by  we  rules  set of  state  c u r r e n t , and  p r o v i d i n g access  by  obtained  v i a i t s name w h i c h  from  PLAN m e t a f a c t  state  dependent  3.3  name.  is accessible.  The  and  thus  far  without  proof,  description:  (i.e.  PLAN)  and  the  database;  metafacts to  of  the  the  rule  the  content  i s p r o v i d e d as the  i s considered  particular,  to this i n the  form  database of  a  every  which  is  can  be  Similarly, object  information next  RULE(<rule  rule  metafact.  RULE m e t a f a c t ,  access  in  final.  Thus,  The  Control Level  a  where  instantaneous  claim,  such  so  of  the  i s p r o v i d e d by  indexed  the  provide  the  metafacts  complete We  by  rules  level  rule  a  PS.  applied  specification  independent  want  object level  metafacts  object  initial,  w i t h domain  Ideally,  that  the  to allow their  is  level system  chapter.  PS  "We n e e d t o be a b l e t o describe processing s t r a t e g i e s i n a l a n g u a g e a t l e a s t as r i c h as that in which we describe the external domain, and f o r good e n g i n e e r i n g , i t s h o u l d be t h e same l a n g u a g e . " Hayes, 1977 Rather level hence  PS  than  i s used  the  having to  a  separate  recursively  name R C P S .  With  such  control  plan a  level  i t s own  PS,  control  s c h e m e , we  are  3 The  not  the  object  strategy, limited  Design  of  to  RCPS  36 a  single  level  following 1) t h e 2)  conditions recursive  the  into  of c o n t r o l .  manner  the current  4)  the boundary  and  thus w i l l  however,  we  recursive  subordinate result  to reduce which  the  the  procedure  the  used  presented  in  in a position  stops  at the bottom on  i s amalgamated  problem  recursion  are dependent  be are  on  a  condition  conditions  any  specified:  which  level  the condition  be  with  call in  3)  These  must  As  of  the p a r t i c u l a r  detail  in  to consider  the  the  recursion.  implementation next  chapter;  them a t t h e  intuitive  level. The and as  language  RCPS  states.  The  final opposed  implement  to the host RCPS)  instantaneous state  condition  of  expanded.  S i n c e we  the  (i.e.  of  The  condition  The  The  thus w i l l  which  the current  coded  i n RCPS,  state level  PS  and  and  to this  the  the  the final  particular level. rule,  the  the  plan  is  problem  terminate.  recursion  problem.  to  is  current  to the goal,  eventually  used  given  at the current  closer  the  initial  of c h o s i n g the next  checked rule  given  language  solution  to consider  is  plan  is actually  the current  the problem  on  a  initial  sought.  a r e one  r e d u c e d and  to solve  the  rule  rule  been  knowledge  language  rule  When R C P S s o l v e s  has  call  where  i s the next  to return  recursive  description  i s the next  RCPS g o a l  i s used  stops i s the Thus,  3 The  the  lack  of  recursion  Design  of  RCPS  37 bottoms-out  when n o r u l e  Since the  next  c a n be a p p l i e d  the recursion  rule  stops  to consider,  rule  nondeterministically.  order  of choice Since  rules  metaplanning  For example,  particular case,  The  level  may  will  simply  to  about  i s t o chose  chose  a  from and t h e  by t h e u s e r . time  a  be s u g g e s t e d  k n o w l e d g e may but  state.  i s no k n o w l e d g e  condition  rules  i s done e v e r y  circumstance a rule  there  the boundary  be s p e c i f i e d  at a particular  depths.  latter  must  when  t o an i n i t i a l  not  exist  rule by p l a n s  t o suggest  i n another  be c h o s e n  i s  needed,  of varying a rule  and thus,  in a  in this  nondeterministically.  3 The D e s i g n  o f RCPS  38  CHAPTER  4  RCPS  "Would you tell me, please, w h i c h way I o u g h t t o go f r o m h e r e ? " , s a i d A l i c e . "That depends a dood deal on w h e r e y o u want t o go", s a i d t h e C a t . Lewis C a r o l l The  RCPS  structures, of  be  4.1  i n terms  i s presented  the design  language,  design,  in. t h i s  a r e dependent  of s p e c i f i c  algorithms  chapter.  Although  on t h e c h o i c e  of (host)  the d i s c u s s i o n i s general  the  details  implementing  enough  t h a t any language can  "Examine your guess. suspicion, or guess, without examination i neradicable."  Don't l e t your or conjecture grow t i l l i t becomes  used.  Search  Strategy  Polya, Since strategy, chosen is  and data  the d e f i n i t i o n  we a r e n o t l i m i t e d  i s forward  solution  does  not rely  on t h e c h o i c e .  and b r e a d t h - f i r s t .  more a p p e a l i n g  optimal  of c o n t r o l  A  i f one e x i s t s .  on t h e s e a r c h  The s e a r c h  breadth-first  s i n c e we a r e g u a r a n t e e d  that  A depth-first  1945.  i twill search,  strategy strategy find the on  the  4 RCPS  39 other  hand,  detecting  may  the  undecidable. no  its  the  search  problem  The they  Ironically,  i s appealing  to which a s o l u t i o n  conflict  resolution  has the e f f e c t  cycling. finite  universe  4.2 R u l e  Semantics,  RCPS r e c o g n i z e s rule  2)  problem  The  plan  i s  a  as  there  goal-directed  context  i s simple.  since  Rules  from  than  nature  of t h e  i t i s  exactly  are restricted i f  the  preventing  preventing  i s presented  Syntax,  1)  of  in  i s sought.  of, at least,  The p r o b l e m  that,  & Morris, 81];  uninformed  do n o t add ( o r remove) knowledge  This  3)  in this  in  [Kibler  less  the  no hope o f  i s appealing  goals  i s much  with  proves  cycles  characteristic  interacting  branch 79b]  detecting  generally the search  counterpart.  forward  of  The f o r w a r d with  an i n f i n i t e [Kowalski,  problem  problem  however,  into  i t s predicament.  general,  is  plunge  cycles  current  a single  state.  rule  from  altogether  in  a  by [ R o s e n s c h e i n , 8 1 ] .  and  Representation  three constructs:  statements statements  metafacts. following  Definite  Clause  o f .RCPS a n d c a n a l s o s e r v e a variable  a n d an a t o m i c  the  particular  PROLOG they  formula  implementation; have  (DCG) d e f i n e s  as a s y n t a c t i c  of  generality,  Grammar  been  checker.  the syntax The  syntax  i s n e c e s s a r i l y dependent thus,  defined  in  for  the  terms  of  sake  on of  system 4  RCPS  40 predicates. /* */ /* */ RCPS RCPS RCPS  D e f i n i t e Clause  Grammar  f o r RCPS  statements  Non-Terminals  PROBLEM RULE METAFACT  => P R O B L E M . => R U L E . => M E T A F A C T . => G I V E N & i m p l i e s & l e f t _ e n c l o s u r e & PLAN_VARIABLE & r i g h t _ e n c l o s u r e & GOAL. => P R E C O N D I T I O N Sc i m p l i e s & l e f t _ e n c l o s u r e Sc A C T I O N S< r i g h t _ e n c l o s u r e & POSTCONDITION. => i m p l i e s Si l e f t _ e n c l o s u r e S< m e t a f a c t s S< r i g h t _ e n c l o s u r e S< GIVEN.  GIVEN GOAL POSTCONDITION PRECONDITION PRECONDITION PLAN V A R I A B L E PLAN VARIABLE ACTION  => => => => => => => =>  CONJUNCT. CONJUNCT. CONJUNCT. CONJUNCT. CONJUNCT Sc o r S< P R E C O N D I T I O N . var. P L A N Sc s e q u e n c e Sc v a r . atomic.  CONJUNCT CONJUNCT PLAN PLAN  => => => =>  SIGNED ATOMIC. S I G N E D ATOMIC Sc a n d Sc CONJUNCT. ACTION. A C T I O N Sc s e q u e n c e S< P L A N .  S I G N E D ATOMIC = > a t o m i c . S I G N E D _ A T O M I C = > S I G N Sc a t o m i c . SIGN SIGN SIGN SIGN SIGN  = > NOT. => i n d i rect i o n . = > NOT Sc i n d i r e c t i o n . = > NOT Sc i n d i r e c t i o n Sc NOT. = > i n d i r e c t i o n Sc NOT.  NOT NOT  => not. => not  /* Terminals */ implies => left enclosure =>  Sc  NOT.  '->'.NIL. '{'.NIL. 4  RCPS  41 right_enclosure metafacts or sequence and not indirection /*  => => => => => => =>  }'.NIL. 'METAFACTS'.NIL. |'.NIL. ;'.NIL. &'.NIL. -'.NIL. !'.NIL.  System Dependent  V  Terminals  var(*S0.*S1,*S1) <-STRING(*S0,'*'.*). atomic(*S0.*S1,*S1 ) <-( A T O M ( * S 0 ) | S K E L ( * S 0 ) & -STRING(*S0,'*'.*).  The  following  )  a r e examples of r u l e  and  problem  statements  respectively. O N T A B L E ( * X ) & C L E A R ( * X ) & HANDEMPTY -> { P I C K U P ( * X ) } H O L D I N G ( * X ) & -•ONTABLE (*X) & --CLEAR (*X)  & -HANDEMPTY.  ONTABLE(A) & ONTABLE(B) & ON(C,A) & C L E A R ( C ) & C L E A R ( B ) & HANDEMPTY -> { * } O N ( A , B ) & O N ( B , C ) .  The of  following  the rule if  r e a d i n g c a n be u s e d  t o express  the  semantics  statement:  <precondition>  h o l d s , then  after  <action>,  <postcondition>  holds. The  problem  if  <given>  plan) The  statement  does  holds,  then  t h e <goal>  hold.  only difference  statement  has a s i m i l a r  between  has a v a r i a b l e  reading:  after  what  sequence  these  statements  where t h e a c t i o n  of actions ( i . e .  i s that  would  be  the problem (actually, 4 RCPS  42 for  convenience,  precondition). after  the  weakest  This  the  has  truth  has  important  very  only  contains  action.  are  "|"  the  operator as  indirection Notice,  indirection  is  that  i n the  failure'  operator, the  allowed.  This  the  host  language.  access  to  the  host  f r o m w i t h i n any  operator  i s most  Similarly, The  This  useful  action  that  are  plays  The  two  unary.  the  after  mention  algorithm  the  that  true  a c t i o n must  in  (thus  next  for  section.  The  "&"  and  "and"  and  "or".  which  is  accomplished  effecting but  i s very  only  one  is  used  effect  construct at for  goal  used  the  and  has  the  a c t i o n frames are  facts of  facts  frame  operator  to  only  The  a  i s simple  syntax,  i s ,  78].  i t is considered  connective  operand  indirection  [Reiter,  that  connectives  "!",  rule.  assumption"  the  [ C l a r k , 78]  the  world  considered  "not"  of  the  "closed  postcondition.  logical  plan  Everything  The  operators  the  facts.  as  list  the  a l l true  to hold.  rules  argument  to  in  precondition is  mentioned.  t o deduce  is  The  assumption  bindings.  i s the  from  of  need  i n the  binary  instantiated  weakest; be  disjuncts  for applicability  this  need  feat  simply  be  term  the  facts  included this  'negation  RCPS.  The  rules'  a l s o two  are  unary  The  will  have  statement.  to  role  the  argument  There  via  the  Hence, the  accomplishing  the  false.  a d e e p b i n d i n g manner  every  also  consists  changed  a  the  the  is similarly  of  in  of  given  consists  which  variable  given  been  postcondition whose  may  c o n d i t i o n t h a t must h o l d  i s considered  (CWA)  rule  execution  Similarly, else  a  of  any  accessing  The  a  CWA).  useful in level  of  to pass i t s providing level.  The  procedures 4  RCPS  43 written  in  the  host  metafacts  construct  metafacts  accessible  except  object).  the  The  rules  are  database.  The  convenience  of  is  presented  assertions the  are  one  for  of  next  every  the  type  are  the  assertion  i s present.  Representing  "What  done  than  i n most  PSs,  intensionally instantiated  store (eg.  in action.  Since  chosen on  for  them.  The  rule  contains exactly  second  of  name ( i . e . the  one  entire  of  that  i s ,  postcondition.  The  the  type;  these.  second  type  of  Plans  even  the  the  by.the  the  state  Intuitively, the  relational  fool  knows" Homer,  Iliad  information extensionally  STRIPS),  plans.  a  level  types  the  in  every  two  where o n l y  i s past,  state  the in  Information  is  dependent  are  i s always  case  in  The  algorithm  of a s s e r t i o n  of  I/O).  when t h i s  There  indexed  formula  degenerate  State  Rather  both  There  (i.e.  operate  i n more d e t a i l  assertions  atomic  levels  which  and  domain  assertions  section.  rule.  a number o f every  specify  representation  rule,  first  arithmetic  a l l control  i s considered  The  to  algorithms  metafacts  4.3  at  particular  for  precondition  used  (like  r e p r e s e n t e d as  i n the  action).  There  is  the  representation  language  action  as  is  information i s stored consider  c o n t a i n s , by  a  single  definition,  4  RCPS  44  every and  argument  in  i n s t a n t i a t e the  necessary  to  simply  the  action.  facts  from  the  postcondition  store  a  a l l , the The  plan  postcondition,  a  regression  [Waldinger,  77].  exploited  by  74]  dual  purpose  [Warren, of  This  a  storing  the  i n s t a n t i a t i o n s to  state . 8  maintenance considered  The means of  This  systems as  the  actual  and,  using  algorithm (TMS)  sole  the  not  postconditions  but  the  a  impressively  plan  of  of  i s known a s  is  Thus, a  truth  serves  actions  the  which  algorithm,  of  determine  the  of  in  forms  degenerate  the 79]  [Doyle,  justification  the  i t  access is  actions),  sequence  to  regression  t r u t h maintenance  communicating  Thus,  algorithm  the  in  that  state  of  in Warplan.  result  used  which determines  sequence  representing  be  assertions.  instantiated  algorithm  (i.e.  i t can  for  truth  where the  algorithm  and  case  the  the  of  truth  action  t r u t h of  PROLOG c o d e  facts  the  fact.  i s presented  syntax  of  is  the  as  a  rule  assertions. /*  V  Truth  Maintenance  System  T R U E ( { * A C T S } * F A C T & * R E S T ) /* <-/ /* CR */ & TRUE({*ACTS}*FACT) & TRUE({*ACTS}*REST).  Conjunctions  */  T R U E ( { * A C T S } * F A C T | * R E S T ) /* <- / /* CR */ & ( TRUE({*ACTS}*FACT) | TRUE({*ACTS}*REST)).  Disjunctions  */  A fact i s true only r e l a t i v e to an interpretation. In this case, the postcondition a s s e r t i o n s form the i n t e r p r e t a t i o n to the a c t i o n ; that i s , changing the a s s e r t i o n s changes the truth of the f a c t s . 8  4  RCPS  45 TRUE( {* ACTS j " * F A C T ) <-/ /* CR */ & -TRUE({*ACTS}*FACT).  /* N e g a t i o n  TRUE({*}!*FACT) <-/ /* CR */ & *FACT.  /* I n d i r e c t i o n  TRUE({*REST;*ACT}*FACT) <-({*ACT}*FACT)7.  /* A t o m i c f a c t made t r u e /* l a s t a c t i o n i n p l a n  by  */ */  TRUE({*REST;*ACT}*FACT) <-/ /* CR */ & TRUE((*REST}*FACT) &NOT(({*ACT}-*FACT)?).  /* A t o m i c f a c t made t r u e b y /* some o t h e r a c t i o n i n p l a n  */ */  TRUE({*ACT}*FACT) <-/ /* CR */ & ((*ACT}*FACT)?.  /* A t o m i c f a c t made t r u e b y * / /* l a s t ( o n l y ) a c t i o n i n p l a n * /  TRUE(<*ACT>*FACT) <-(<*ACT>*FACT)?.  /* U s e d  1  Since be  a plan  represented  fact,  represents  */  */  to retrieve  precondition  */  a s t a t e , the e n t i r e s t a t e space can  by a number o f p l a n s .  A plan  i s represented  as a  thus:  PLAN(<ACTI0N1>; <ACTI0N2>;  ... < A C T I O N n > ,  <DEPTH>)  where: ACTIONi DEPTH  i s t h e number o f a c t i o n s - 1  (i.e.  The  plans  i s an a c t i o n  the depth  are asserted,  of the branch  within  a  i n the deduction  given  depth,  in  tree).  the  order  generated.  4 RCPS  46 4.4 T h e R e c u r s i v e We  a r e now  introduced  in  TMS,  extensively associate  the  a  separate  sequence store 1)  2)  previous  as described the  facts  RCPS  with  memory  of  terms  ideas  of  the  that  effect,  the  consistent.  i s  used  t h e TMS c a n forms  a  c a n be r e g a r d e d  as  TMS  i t  i s  T h e TMS  to  keep  a  i s used t o  information:  c o n d i t i o n s as described  i n the previous  *PRECONDITION)  ASSERT({*ACTION}  *POSTCONDITION)  section:  names:  ASSERT({RULES} 3)  In  instantiation  The p u r p o s e  the  section,  Recall  ASSERT(<*ACTION>  the rule  in  previous  action.  detail  chapter.  interpreter.  partitions  the following the rules'  the  where e v e r y  such  in  chapter  of t h i s  in  some  partition. of  to present  and a l g o r i t h m s  by  partitioned  Machine  in a position  representations The  Virtual  the state  RULE(*ACTION))  space:  ASSERT({LEVEL(*LEVEL)}  PLAN(*PLAN, *DEPTH))  where: *LEVEL  i s 0 f o r the object  every 4)  the given  facts  problem  level,  while  and incremented  for  metalevel of a problem  ASSERT({LEVEL(*LEVEL)} Every  level  has a separate  the entire  at a particular  level:  *GIVEN). or l o c a l  set of rules  partition,  d e f i n e d by t h e  i s g l o b a l t o every  problem; 4  RCPS  47  in p a r t i c u l a r ,  r u l e s are not d i s t i n g u i s h e d by o r d e r .  Reconsider  the  conditions  for  s e c t i o n 3 . 3 . The RCPS r e c u r s i v e c a l l  recursivity i s the  introduced in  following  problem  statement. ( LEVEL(*LEVEL) & PLAN(*PLAN) & *G & DEPTH(*DEPTH) -> {METAFACTS;RULES;*MP} NEXT_RULE(*ACT) ) The l o c a l given f a c t s to the problem of f i n d i n g  the  next  rule  are: 1) the metalevel  number which we are reasoning about  2) the p l a n , which i s used f o r : 1)  the sequence of a c t i o n s a p p l i e d so f a r  2) the  s t a t e i n f o r m a t i o n a c c e s s i b l e by an i n d i r e c t i o n  to  the TMS 3) the c u r r e n t l y  unsolved goals  4) the depth of i n f e r e n c e  (a  convenience).  The g l o b a l f a c t s to the problem, represented by the p a r t i a l  plan  METAFACTS; RULES, are any domain dependent metafacts d e c l a r e d by the  user  using the METAFACT statement and the r u l e names.  content of the r u l e s database.  It  i s a c c e s s i b l e by an i n d i r e c t i o n to the  is this  set of l o c a l and g l o b a l f a c t s  the instantaneous d e s c r i p t i o n of the solved,  returns  plan.  If  plan,  the  a  metaplan  and  PS.  i s true  TMS  that  forms  problem,  when  the a c t i o n suggested by  the p r e c o n d i t i o n of t h i s a c t i o n action  This  The  in the  this  current  i s used to expand the plan thus reducing the 4 RCPS  48 problem;  otherwise,  reconsidered. problem  cannot  statement  The machine. It call  is  If be  the a  problem  rule solved  of  cannot and  finding  be  the  found, top  a  rule  the object  level  RCPS  i s level  problem  fails.  PROLOG  code  I t i s called expected  to follow with  to return  the predicate  SOLVE  i s the core  the goal, the plan  o f t h e RCPS  the l e v e l ,  on s u c c e s s .  i s considered  and the  virtual depth.  The d e c i s i o n t o  later.  /* Main p r o d u c t i o n system l o g i c */ SOLVE(*GOAL,*LEVEL,*PLAN,*DEPTH) /* I f the goal i s < - T R U E ( { L E V E L ( * L E V E L ) } P L A N ( * P L A N , * D E P T H ) ) /* t r u e a t t h e & TRUE({* PLAN}*GOAL). /* c u r r e n t d e p t h /* a n d l e v e l , /* r e t u r n p l a n . SOLVE(*GOAL,*LEVEL,*PLAN;*ACT,*DEPTH) /* Create given of <-ADD1(*DEPTH,*NEXT) /* c u r r e n t p l a n a n d & T R U E ( { L E V E L ( * L E V E L ) } P L A N ( * P L A N , * D E P T H ) ) /* u n s o l v e d g o a l s a t & GOAL_ASSERTION(*GOAL,*PLAN,*G) /* c u r r e n t l e v e l f o r & ( L E V E L ( * L E V E L ) & P L A N ( * PLAN) /* r e c u r s i v e c o n t r o l & *G & D E P T H ( * D E P T H ) /* c a l l . -> {METAFACTS;RULES;*MP} NEXT_RULE(*ACT) ) & TRACE3(*PLAN;*ACT,*MP,*DEPTH,*LEVEL) & TRUE(<*ACT>*PRECONDITION) /* Does c o n d i t i o n & (TRUE({*PLAN}*PRECONDITION) /* o f s u g g e s t e d r u l e | (TRACE6(*ACT,*LEVEL) & F A I L ) ) /* h o l d ? & TRACE4(*PRECONDITION,*ACT,*LEVEL) & CONFLICT_RESOLUTION(*ACT,*PLAN,*LEVEL) /* Does i t pass c o n & TRACE5(*LEVEL) /* f l i c t r e s o l u t i o n ? S= A S S E R T ( { L E V E L ( * L E V E L ) } P L A N ( * P L A N ; * A C T , * N E X T ) ) & FAIL. /* A p p l y i t by /* e x p a n d i n g p l a n . SOLVE(*GOAL,*LEVEL,*PLAN,*DEPTH) /* Flush previous < - F L U S H ( ( { L E V E L ( * L E V E L ) } P L A N ( * , * D E P T H ) ) ? ) /* l e v e l . & ADD1(*DEPTH,*NEXT) /* C o n s i d e r n e x t l e v e l & TRUE({LEVEL(*LEVEL)}PLAN(*,*NEXT)) /* I s there a path t o & SOLVE(*GOAL,*LEVEL,*PLAN,*NEXT). /* c o n s i d e r ? Increase /* d e p t h o f i n f e r e n c e  4  RCPS  49 Once  a n RCPS p r o b l e m  state  asserted  control  with  decide  whether  call the /*  SOLVE, goal  into  number  there  or choose  i s to find  i s parsed  t h e TMS,  the level  Condition  V  statement  and t h e  the predicate and g o a l  as  a rule  i f there  the next  section  rule),  concludes  i t srun-time  t h e RCPS  2) p r o v i d e  It  or else  must thus  (providing  i t fails.  /* /* /* /* /*  /* r e c u r s i v e l y . /* I f no k n o w l e d g e , /* c h o o s e a c t i o n s i n /* o r d e r a s s e r t e d i n /* m e t a f a c t s .  system.  The p u r p o s e  of this  briefly  top-level  i s to:  language  echos  4) c o l l e c t  unneeded  5) p r o v i d e  various  terminals  I f t h e r e i s some r u l e whose p r e c o n d i t i o n h a s some p o s i t i v e a t o m i c and i s c u r r e n t l y true then, solve goal  t h e d e s c r i p t i o n o f RCPS by  error detection  3) p r e t t y p r i n t  The  argument.  System  o f PROLOG p r e d i c a t e s  1) p a r s e  i s given  for recursivity  4.5 T h e R C P S R u n - T i m e  set  below  i s no k n o w l e d g e  PLAN(*LEVEL,NEXT_RULE(*ACT),CHOOSE(*ACT)) <-TRUE({METAFACTS}CHOOSE(*ACT)).  considering  initial  i s a p p l i c a b l e c o n t r o l knowledge and  PLAN(*LEVEL,*GOAL,*PLAN) <-TRUE({RULES}RULE(*ACT)) & TRUE(<*ACT>*PRECONDITION) & ANY_POS(*PRECONDITION) & TRUE({LEVEL(*LEVEL)}PLAN(*GIVEN,0)) & TRUE({*GIVEN}*PRECONDITION) & / /* GT & CR * / & SOLVE(*GOAL,*LEVEL,*PLAN,0).  This  PLAN  given  and  and  results  garbage trace  recovery  from  t h e TMS  options.  o f t h e R C P S DCG,  presented  in  section  4.2,  4  RCPS  50  are  declared  as  PROLOG  operators.  Thus, RCPS statements  c o n s i d e r e d PROLOG goals and can be parsed by Error  traps  have  been  declared  along  the  with  host  are  PROLOG.  suitable  error  messages. The t r a c e options are an e s s e n t i a l part provide  great  how the  knowledge  insights  insight  which  RCPS  as  they  on the behaviour of the i n t e r p r e t e r  is  can,  of  used.  Their  hopefully,  use  be  typically  coded  and  leads  to  as RCPS knowledge.  There are four o p t i o n s : 1) no t r a c e 2) c h e c k p o i n t : w r i t e s the plan restart  after  i s by g i v i n g t h i s as a p a r t i a l  3) a l l  successes: this  every  n  expansions  plan  i s the most u s e f u l and i s the one  used  in the appendices 4) e v e r y t h i n g :  every plan attempted.  The use of RCPS i s f u r t h e r presented in appendix F.  4.6 Content Reference:  An Example Terminal Session  Consider the f o l l o w i n g set of true true true true  -> -> -> ->  { { { {  A B C D  } } } }  a. b. c. d.  These r u l e s s t a t e rule  (whose  rules.  name  a p p l i e d to that  that is  state  whenever  " t r u e " holds  enclosed  in  braces  resulting  in  a  state  in  a  thus "{ where  state, }") the  the  can be post 4 RCPS  51  condition The  holds.  problems  following true  we  wish  to  solve  with  these  rules  have  the  holds  and  form.  ->  {*}  *GOAL  where: *GOAL  This  goal  statement  requests a,  i s one o f a , b, c , o r d  the plan  b, c , o r d.  sequence rules  of  that  CHOOSE  specify  be  even.  If  an o r d e r .  the goal. may  particular  Consider  being  strategy in  be  strategy  we  the goal  i s t o only  state  i s the  we w o u l d  like the  of  t o compute,  the  we may  rules  were  indeed  want  distribution schedule to  may  not  the rule  which  implementing  this  t h e r u l e b y name d e p e n d i n g  on t h e  goal.  NEXT_RULE(A).  of changing,  for  instance,  say, the alphabetically consistent  t o , f o r e x a m p l e , A -> b , B -> a , too  could  the order  approximation  t o schedule  the consequences  (or,  currently  preconditions  Or, again,  A first  GOAL(a) -> { S C H E D U L E ( A ) }  goal  the  "true"  r e s u l t i n the s o l u t i o n of the goals  metafacts  A better  strategy  to  that  d i f f e r e n t and d i f f i c u l t  to  names  will  The s i m p l e s t  attempted.  mutually  solves  expresses  brittle  and  specific,  the  mapping  . . . ) .  The  must be c h a n g e d  rule  of action strategy,  accordingly. 4  RCPS  52 The  strategy  the  rule  for  the  considered  whose p o s t c o n d i t i o n process  appropriately, "<-"  <-  of  session  i s the goal  inspecting  "content  i s t h e RCPS  ***  i n the terminal  the  reference"  below  sought.  content  The t e r m  of  [Davis,  schedules  a  used  rule i s ,  8 0 b ] . The symbol  prompt.  Recursively  Controlled Production  / * C h a n g i n g t h e RCPS s o u r c e */ SOURCE(content).  System  to f i l e  Version  "content"  1.1 * * *  t o input  rules  true  -> { A } a. true ->  { B } b.  true ->  { C } c.  true ->  { D } d.  <-  /*  Oops, T e s t i n g  error  recovery  */ GOAL(*G) & ! ( ( { * R } * G ) ? ) -> (STRATEGY*R)} NEXT  RULE(*R).  I <-  <-  <<<SYNTAX>>> T r y again /* A content r e f e r e n c e s t r a t e g y */ OK_TO_USE_STRATEGY & GOAL(*G) & ! ( ( { ( * R } * G ) ) ?) -> .{ STRATEGY (*R) } NEXT_RULE(*R). LEVEL(0) -> { CHECK_LEVEL } OK TO USE STRATEGY.  4 RCPS  53  <-  /*  The  V  metastrategy  ->  {METAFACTS} C H O O S E ( S T R A T E G Y ( * R ) ) .  <-  ->  {METAFACTS}  <-  /*  CHOOSE(CHECK_LEVEL).  Problem  V  ( t r u e -> {*} c ) & W R I T E ( ' T h i s T h i s i s a PROLOG g o a l . true ->  { LEVEL(0) C } c &  WRITE(This <-  i s a PROLOG  goal').  ;  i s a PROLOG  goal).  STOP.  The  trace  successes),  produced  by  this  session,  using  option  3 ( a l l  i s the following.  Given Facts true Goal c  t o be  Solved  Meta Plan CHOOSE(CHECK_LEVEL) Suggests Expansion LEVEL(1) ; CHECKJLEVEL Precondition LEVEL(0) Plan  o f CHECK_LEVEL  holds  Expanded  Meta Plan CHOOSE(STRATEGY(* 1)) Suggests Expansion LEVEL(1) ; CHECK_LEVEL ;  4  RCPS  54 S T R A T E G Y ( * 1) P r e c o n d i t i o n of STRATEGY(C) OK_TO_USE_STRATEGY & GOAL(c) & ! ( ( { ( C } c ) ) ?) Plan  holds  Expanded  Meta P l a n CHOOSE(CHECK_LEVEL) Suggests Expansion LEVEL(1) ; CHECK_LEVEL ; CHECK_LEVEL Precondition LEVEL(0) Conflict  o f CHECK_LEVEL  Resolution  holds  Restricts  Rule  CHECK_LEVEL  Meta Plan LEVEL(1) ; CHECK_LEVEL ; STRATEGY(C) Suggests Expansion LEVEL(0) ; C Precondition true Plan  of C  holds  Expanded  Solution t o Problem true -> { L E V E L ( 0 ) C } c.  Although single  rule,  the  ;  control  i t i s specified  metareasoning.  strategy using  can  two as a  be s p e c i f i e d simple  using  example  a of  As an example o f : 4 RCPS  55  1)  using the same knowledge at d i f f e r e n t  2) more than one l e v e l  levels  of c o n t r o l ,  c o n s i d e r the f o l l o w i n g r u l e : LEVEL(*L) & !LE(*L,2) & GOAL(*G) & !(({*R}*G)?) & -> {STRATEGY(*R)} NEXT RULE(*R). This itself  content  reference  as the object  level  rule  is  strategy.  used as a s t r a t e g y The t r a c e  to invoke  produced  using  o p t i o n 3 i s i n appendix A.  4 RCPS  56  CHAPTER  Results  This  chapter  and E v a l u a t i o n  conveys  the  automatically  program  when e x e c u t e d  by t h e arm, w i l l  problem. the  chapter  expected  considers  progressively increasingly  results  t h e PUMA r o b o t  The s p e c i f i c a t i o n  results  5  solve  of the  refined. difficult  rules These  The  first.  sets  RCPS  generated  the specified  whose  problems  using  wire-wrapping  are considered  a set of  arm.  of  wire-wrapping problems  the  results  and  of the  component  of r u l e s a r e used  and  plan,  The r e m a i n d e r control  to  i s  to solve  are  then  compared.  5.1  Problem The  wire-wrapping  statement. of  the  result  S p e c i f i c a t i o n and Expected  The b o a r d  statement  converted  language,  RCPS  the goal  i s  a  a hypothetical which  will  i s  specified  list  are the  i s a plan  valid  program.  VAL  of a host  (pre/post)processor,  which  language,  written  i n the preparation  can  we  The be  will  i n the host  o f t h e RCPS  5 Results  goal  "given"  i s the "goal".  statement  sublanguage  aid  a s o n e RCPS  specifications  the connection  to a syntactically  Since consider  and socket  while  of executing  problem  Results  goal  and E v a l u a t i o n  57  statement basic the  and  resulting  steps.  RCPS g o a l  The  VAL  first  i s the  statement;  the  statement  by  final  step  t r a n s l a t e s the  valid  VAL  at  least  on  connection every  the  list.  pin,  the  package) header topology can  be  of  few  every  is specified.  From  calculated.  characterized  by  circuit  consists first  of  the  prompt  conjunctive circuit  Every of  and  for  the  g o a l , as  would  well  In  of  with  construct  the  the  consist  a  the  pin  location  of  DIP  (dual the of  in-line physical  every  pin  then  be  (aside  from  location  a of  the  "goal"  preprocessor  would  and list  circuit  given.  of  c o n s i s t of  the  list  accumulate  the  be  pins, while  The  and  to  summary, of  goal  pins  location  consists  creates the  component must  connection  Prompting  then  pins.  list.  as  should the  c h i p or  the  of  three  syntactically  knowledge about  i t s number  pin  a  s p e c i f y the  circuit  "given"  pin connection  components.  preprocessor RCPS g o a l  component  IC  of  should  to  components,  i t s number  s t a r t - u p f a c t s , ) the  every  having  of  circuit  to  "given"  "goal"  which  interpreter;  plan  the  step  has  execution  location  the  than  location  the  easily  and  Rather  i s the  resulting  absolute  board,  processor  RCPS l a n g u a g e  Intuitively,  physical  This  preprocessing  second  imbedded  program.  the  connected  the  program.  An  construct of  the  a l l  the  components,  the  example  of  an  statement i s :  5 Results  and  Evaluation  58  SYMBOLIC O R I G I N ( o r i g i n ) & LOCATIONlSTARTIC,0:0) & LOCATION(IC,1000: 1000) & NO_PINS(STARTIC,0) & N O _ P I N S ( l C , 1 4) & WRAPPED(STARTIC:0) & ABOVE(STARTIC:0) -> { *P } CONNECT(IC:2,IC:1) & CONNECT(IC:3,IC:1). Given to  such  a goal  construct  statement,  a plan  which  RCPS u s e s  the rules,  defined  i s bound t o t h e v a r i a b l e  *P.  LEVEL(0) ; SET(origin) ; SIGNAL(2,STARTIC:0) ; SHI F T ( I C : 1 , 1 0 2 5 : 1 0 3 8 , M O V I N G _ T O _ S T A R T _ C H A I N ( I C : 1 ) ) APPRO(IC:1,STARTIC:0,MOVING_TO_START_CHAIN(IC:1)) MOVES(IC:1,MOVING_TO_START_CHAIN(lC:1)) ; SIGNAL(1,IC:1,MOVING_TO_START_CHAIN(IC:1)) ; DEPARTS(IC:1) ; SET(origin) ; SHIFT(IC:2,1050:1038,SOLVING GOAL(IC:3,IC:1)) ; APPRO(IC:2,IC:1,SOLVING G O A L l l C : 3 , I C : 1 ) ) ; MOVES(IC:2,SOLVING_GOALTlC:3,IC:1)) ; SIGNAL(1,IC:2,SOLVING_GOAL(IC:3,IC:1)) ; DEPARTS(IC:2) ; SET(origin) ; SHIFT(IC:3,1075:1038,SOLVING GOAL(IC:2,IC:1)) ; APPR0(IC:3,IC:2,S0LVING GOALTlC:2,IC:1)) ; MOVES(IC:3,SOLVING_GOALTlC:2,IC:1)) ; SIGNAL(1,IC:3,S0LVING_G0AL(IC:2,IC:1)).  This  plan  can then  be p o s t p r o c e s s e d  resulting  later,  ; ;  i n the following  VAL p r o g r a m . REMARK REMARK FRAME REMARK SET REMARK SIGNAL REMARK  Define t h e board r e f e r e n c e frame. T h e s e VAL l o c a t i o n s a r e p r e s u m e d t o be d e f i n e d . BOARD = O R I G I N , X, Y, Start of connection P I N = ORIGIN T e r m i n a t e t h i s c h a i n by c u t t i n g w i r e a t p i n 0 o f STARTIC 2 S h i f t o r i g i n t o p i n 1 of IC t o s t a r t chain 5 Results  and E v a l u a t i o n  59 SHIFT REMARK APPRO REMARK MOVES REMARK SIGNAL REMARK DEPARTS REMARK SET REMARK REMARK SHIFT REMARK APPRO REMARK MOVES REMARK REMARK SIGNAL REMARK DEPARTS REMARK SET REMARK REMARK SHIFT REMARK APPRO REMARK MOVES REMARK REMARK SIGNAL RETURN The  plan  allow  P I N BY 1 0 2 . 5 , 1 0 3 . 8 A p p r o a c h p i n 1 o f I C f r o m p i n 0 o f STARTIC P I N , 20 I n s e r t t o o l on p i n 1 o f I C PIN Wrap p i n 1 o f IC a c c o m p l i s h i n g s t a r t o f c h a i n 1 Leave p i n 1 of IC 20 Start of connection P I N = ORIGIN S h i f t o r i g i n t o p i n 2 of IC t o accomplish c o n n e c t i o n between p i n 2 o f IC and p i n 1 o f IC P I N BY 1 0 5 . 0 , 1 0 3 . 8 Approach p i n 2 of IC from p i n 1 of IC P I N , 20 I n s e r t t o o l on p i n 2 o f I C PIN Wrap p i n 2 o f IC a c c o m p l i s h i n g c o n n e c t i o n between p i n 3 o f IC and p i n 1 o f IC 1 Leave p i n 2 o f IC 20 Start of connection P I N = ORIGIN S h i f t o r i g i n t o p i n 3 of IC t o accomplish c o n n e c t i o n between p i n 3 o f IC and p i n 1 o f IC P I N BY 1 0 7 . 5 , 1 0 3 . 8 Approach p i n 3 of IC from p i n 2 of IC P I N , 20 I n s e r t t o o l on p i n 3 o f I C PIN Wrap p i n 3 o f I C a c c o m p l i s h i n g c o n n e c t i o n between p i n 2 o f IC and p i n 1 o f IC 1 0 contains  the postprocessor  .serving  problems  specification a  (explicit  and i m p l i c i t )  information to  t o i n c l u d e comments i n t h e VAL code  thus  a s an e x p l a n a t i o n .  The  of  enough  to  and s o l u t i o n  be  considered  ina pictorial  present format.  diagram of the p i n l o c a t i o n s and r e s u l t i n g  the I t  problem consists  paths taken t o  5 R e s u l t s and E v a l u a t i o n  60  accomplish are  the  drawn  to  the  they  connections.  as  connections  dotted connections  resultant). are  The  Since  numbered.  The  both  specified  ( u n l e s s they  are  problem  goal  a l l identical  s e t s of c o n n e c t i o n s  previous  as  are  i s presented  ordered, by  figure  3.  o STARTIC  Figure  5.2  Rules The  presented  f o r an  3.  I n t r o d u c t o r y Problem S o l u t i o n  Exhaustive  Uncontrolled Derivation  s e t of  rules  modeling  and  first  used  nondeterministically).  little  m o d i f i c a t i o n , i n a l l the domain  model  wire-wrapping  without  chosen  The  the  These  a  control  rules  will  domain  are  strategy ( i . e . be  used,  with  f o l l o w i n g problems.  i s simple  and  makes use  of  the f o l l o w i n g  facts: 1)  the  2)  whether  pin 3)  symbolic  VAL  name of  the  circuit  board  i s set  origin  the  only  program v a r i a b l e  to the  the  tool  i s a t or a b o v e a p i n 5 R e s u l t s and  origin  or  a  location whether  Evaluation  61 4) whether a p i n i s wrapped or not 5) the given f a c t s ; namely, the l o c a t i o n and number of pins of each  component  6) a u x i l i a r y The  auxiliary  predicates. predicates  are  procedures  language and accessed v i a the i n d i r e c t i o n used  to c a l c u l a t e the p i n r e l o c a t i o n  from the component The h e a v i l y are  presented  reference  The  i n the host  operator.  shift  (i.e.  They  are  Displacement)  location.  commented r u l e s , i n the next.  written  casual  form  reader may  of  paraphrases,  read the comments  only. /*  */ /*  V  This set of r u l e s , c a l l e d 'WRAP', i s the main set of l o g i c r u l e s which can be used without a c o n t r o l s t r a t e g y ( i . e . chosen nondeterministically). T h i s same set can be used with other control strategies. The program v a r i a b l e can be set to the o r i g i n whenever the s t a r t token i s t r u e . The s t a r t token i s an example of how c o n t r o l knowledge can be imbedded i n the l o g i c r u l e s and i s a c t u a l l y needed i f we do not want a m e t a l e v e l .  SYMBOLIC_ORIGIN(*NAME) & START TOKEN -> TSET(*NAME)} VAR_SET_TO_ORIGIN & -VAR_SET_TO_PIN_LOCATION(*) & -START_TOKEN. /*  V  If the program v a r i a b l e i s set to the o r i g i n , choose a component and an unwrapped p i n and s h i f t the o r i g i n a c c o r d i n g to the l o c a t i o n of the component and the p i n number. The program v a r i a b l e i s now set to the unwrapped pin l o c a t i o n .  VAR_SET_TO_ORIGIN & LOCATION(*IC,*ICLOC) & NO_PINS(*IC,*N) & !BETWEEN(*PIN,1,*N) & -WRAPPED(*IC:*PIN) & 5 R e s u l t s and  Evaluation  62  !REFERENCE_PIN_SHIFT(*PIN,*N,*DISP) & !RELOCATE(*ICLOC,*DISP,*PINLOC) -> ( S H I F T ( * I C : * P I N , * P I N L O C ) } VAR_SET_TO_PIN_LOCATION(*IC:*PIN) -VAR_SET_TO_ORIGI N. /*  V  &  I f t h e p r o g r a m v a r i a b l e i s s e t t o t h e n e x t unwrapped p i n l o c a t i o n and t h e t o o l i s n e i t h e r a t o r above i t , t h e n i t can be a p p r o a c h e d l e a v i n g t h e p r e v i o u s p i n b e h i n d .  VAR SET_TO_PIN_LOCATION(*IC:*PIN) & -ATl*IC:*PIN) & -ABOVE(*IC:*PIN) & -WRAPPED(*IC:*PIN) & ABOVE(*OLDIC:*OLDPIN) -> (APPRO(*IC:*PIN,*OLDIC:*OLDPIN)} ABOVE(*IC:*PIN) & -ABOVE(*OLDIC:*OLDPIN). /*  V  I f above an unwrapped p i n , t h e n moving t o i t w i l l t h e t o o l t o be a t i t .  cause  ABOVE(*IC:*PIN) & -WRAPPED(*IC:*PIN) -> {MOVES(*IC:*PIN)} AT(*IC:*PIN) & -ABOVE(*IC:*PIN). /* I f a t an unwrapped p i n , t h e n w r a p p i n g i t w i l l c a u s e a c o n n e c t i o n between i t a n d any o t h e r wrapped p i n .  V  AT(*IC2:*PIN2) & -WRAPPED(*IC2:*PIN2) & WRAPPED(*IC1:*PIN1) -> {SIGNAL(1,*IC1:*PIN1,*IC2:*PIN2)} WRAPPED(*IC2:*PIN2) & CONNECT(*IC1:*PIN1,*IC2:*PIN2). /*  V  I f a t a wrapped p i n , d e p a r t i n g w i l l c a u s e t h e t o o l t o be above i t and n o t a t i t . T h i s t e r m i n a t e s a c o n n e c t i o n a n d t h u s t h e s t a r t t o k e n c a n be a s s e r t e d t o s t a r t t h e n e x t .  WRAPPED(*IC:*PIN) & AT(*IC:*PIN) -> {DEPARTS(*IC:*PIN)} ABOVE(*IC:*PIN) & -AT(*IC:*PIN) & START TOKEN. /*  Order  that  the rules  should  be n o n d e t e r m i n i s t i c a l l y  chosen.  5 R e s u l t s and E v a l u a t i o n  63  */ -> {METAFACTS}CHOOSE(SET(*)). -> {METAFACTS}CHOOSE(SHIFT(*,*)). ->  {METAFACTS}CHOOSE(APPRO(*,*)).  ->  {METAFACTS}CHOOSE(MOVES(*)).  ->  {METAFACTS}CHOOSE(SIGNAL(*,*,*)) .  ->  {METAFACTS}CHOOSE(DEPARTS(*)).  Notice only  that since a rule a single  chained  does n o t e x i s t  connection  for  cutting  c a n be a c c o m p l i s h e d  the  wire,  with  these  rules. A control Since,  in  s t r a t e g y must a l w a y s be s p e c i f i e d  this  case,  nondeterministically, attempted  via  advocated  here,  rules  in  serving  the  we  we s t a t e CHOOSE  a control  order  to  problem  at  a l l tractable.  sequencing such  focussed strategy driven. applied  some  (for this  between a forward toward  in  77]  the  Most p l a n n e r s  order  In a d d i t i o n t o  i n order  accomplished  goal d i r e c t e d  simply  form  some form o f t o make t h e  discusses  how  v i a working  memory.  derivation  i s not  have a backward because they  strategy, this to  be  t o the t h e s i s  s t r a t e g y i s used,  [Rychener,  a goal d i r e c t e d  exhaustively  sequencing.  strategy,  should  introduced i n the l o g i c  example o n l y )  is  search  the g o a l .  and a r e t h u s Without  rules  rules.  t o be c h o s e n  they  Contrary  has been  a s an example o f how t h i s needed  that  metafact.  effect  is  want t h e r u l e s  the order  token  control  With  simply  f o r RCPS  search  are goal  s e t of r u l e s i s  a l l combinations  of  5 R e s u l t s and E v a l u a t i o n  64  connections.  A  simple  sections,  problem,  i s shown  produced. argument  Some o f t h e s e  In  solve the intended  which w i l l  in figure  this  will  be r e c o n s i d e r e d  4 along  diagram,  the  t o SIGNAL.  with  the  goal.  i n subsequent  deduction  p r e v i o u s p i n i s used  tree as t h e  ser  *  SH  =  SHIFT  A  =  /WROflCH  M  z  Moves  s  D  • '  DEPARTS  STAftTJCC  Figure  4. E x h a u s t i v e  Deduction  and R e s u l t i n g S o l u t i o n  5 R e s u l t s and E v a l u a t i o n  65 The  penetrance P = L / T =  5.3 A d d i n g  f o r t h i s problem,  a Goal Directed  Strategy  the uncontrolled  in  uninformed  manner a s c a n be seen  penetrance  factor.  the  section  cited  in  has the f o l l o w i n g  1)  The d e r i v a t i o n  2)  A l l rule  explicit  2,  i s :  control  tokens  solves  so i n a very  from  the  the  problem  inefficient  derivation  will  be a d d e d  the previous  tree  i n order  section.  and and  strategy, to  The  solve control  characteristics.  i s goal  sequencing,  Rules  t h i s set of rules, a c o n t r o l  o f RCPS m e t a r u l e s ,  deficiencies  strategy  5.2, i t does  Using  v i a Meta  set of rules  specified  t h e form  i n chapter  1 7 / 133.  Although  in  as defined  directed. whether  previously  or i m p l i c i t l y  accomplished  by g o a l s ,  by  i s explicitly  stated. Before presented  further and  explanation,  their  these  incorporation  control into  rules  the  logic  are rules  discussed. /*  */ /*  T h i s s e t of r u l e s , c a l l e d 'metawrap', i s a c o n t r o l strategy f o r t h e s e t o f l o g i c r u l e s i n 'wrap'. The s t r a t e g y i s t o solve t h e goals e x a c t l y as s p e c i f i e d . I f reasoning about start a connection.  object  l e v e l w h i c h h a s no p l a n ,  then  */ LEVEL(0) & DEPTH(0) -> { S T A R T _ C O N N E C T I O N } NEXT_RULE(SET(*)). /*  If just  terminated  a connection,  then  start  . 5 Results  t h e next one. and  Evaluation  66  */ PLAN(*;DEPARTS(*)) -> { C H A I N } NEXT_RULE(SET(*)). /*  V  I f just s t a r t i n g a connection , then pick a goal which r e q u i r e s t h e c u r r e n t p i n t o be c o n n e c t e d t o a n o t h e r a n d calculate i t sshifted location.  PLAN(*P;SET(*)) & GOAL(CONNECT(*IC1:*PIN1,*IC2:*PIN2)) & !TRUE({*P}ABOVE(*IC1:*PIN1) & WRAPPED(*IC1:*PIN1)) -> {SEQUENCE 1 ( * I C 2 : * P I N 2 ) } NEXT_RULE(SHIFT(*IC2:*PIN2,*)). /*  V  it  After s h i f t i n g the variable c a n be a p p r o a c h e d .  to the l o c a t i o n  of the p i n ,  PLAN(*;SHIFT(*IC:*PIN,*)) -> {SEQUENCE2(*IC:*PIN)} NEXT_RULE(APPRO(*IC:*PIN,*)). /*  After  V  approaching  a p i n , the t o o l  c a n be moved t o  it.  PLAN(*;APPRO(*IC:*PIN,*)) -> {SEQUENCE3(*IC:*PIN)} NEXT_RULE(MOVES(*IC:*PIN)). /*  */  A f t e r moving t o a p i n , wrapping between i t and t h e p r e v i o u s p i n .  i t will  cause a  connection  PLAN(*;MOVES(*IC2:*PIN2)) & GOAL(CONNECT(*IC1:*PIN1,*IC2:*PIN2)) -> { S E Q U E N C E 4 ( * I C 1 : * P I N 1 , * I C 2 : * P I N 2 ) } NEXT_RULE(SIGNAL(1,*IC1:*PIN1,*IC2:*PIN2)). /*  V  After  wrapping  a p i n the t o o l  can  depart.  PLAN(*;SIGNAL(1,*,*IC:*PIN)) -> {SEQUENCE5(*IC:*PIN)} NEXT R U L E ( D E P A R T S ( * I C : * P I N ) ) .  Since  this  nondeterministic these  rules.  control  control  strategy  replaces  strategy,  we  t h e CHOOSE m e t a f a c t s  Since  strategy,  these we  replace  control  specify  rules the  must  order  the  previous  now  have  of  choosing  5 Results  and  their  with own them.  Evaluation  67  Although  we  metarules being is  still are  applicable strategy  look  for  ever  attempted.  and  t h e one a p p l i c a b l e  necessarily  We  by  say  Note  sequencing  ensuring  subroutine beginning  that  since  of the next the  control to start thus  last  metarule  the interpreter  control logic  to  strategy  derivation  may  i s  i s not  have more  strategy  scheduling  of  than  of the c o n t r o l  effecting  the  operator  object  plan;  that  i n a state  t h e means  used  i s actually  metarules This  from  specified  determine  i s  build,  routine  accomplished  in effect,  i s "called"  the  goal.  which  a fundamental  been to the  . This  ensures  as g o a l a r e accomplished Notice the  the rules  t o communicate h i g h  a  at the  The a r g u m e n t s  the  truth  use  level  assumption  of  of f a c t s  i s , i n general, to determine  about  i s i t s  a c o n n e c t i o n has  an i t e r a t i o n .  subroutine.  to  rule  i n t h e PLAN m e t a f a c t  a c o n n e c t i o n and a f t e r  indirection level  applicable  structure.  the connections  only  This  a  control  sequencing  that  9  one  thenondeterministic  one m e t a r u l e  action  are obtained directly  is  the rules  o n l y t h e one m e t a r u l e i s  such  the  than  only  requires  metarule,  subroutine  facts  though  the top level  also,  The f i v e  accomplished  of  case,  fewer  i s nondeterministic.  predecessor.  the  even  that  that  deterministic  instantiation;  The  particular thus  typically,  a given metastate  (of the metarules)  deterministic.  strategy  nondeterminism, in  In t h i s  9  control  some  applicable  controlled .  ever  one  have  the  are reasoning. facts  behind  to  a  by the  i n the truth This lower  the theory.  5 R e s u l t s and E v a l u a t i o n  68 metalevel.  Conversely,  means f o r c o m m u n i c a t i n g higher  levels.  reinstantiated is,  the  thus  If the  accessed  at  previous  metarule  this  Without  simply  as m e t a f a c t .  again  by  the  the  goal  rule.  of  is  That and  generality,  allocated  slots  needed,  it  i n the can  i n s p e c t i n g the o b j e c t  This technique  of  had  17 /  t o be  34; fired  A partial  i s used  in  be  level  the  next  allows  in  that  the  Although  the  toward  general,  rules  same  to schedule  RCPS t r a c e of  rule  i t and  this  to accomplish  solution  i s , for every  the  Goal  no  but  on  the  other  deduction  Directed Strategy with  previous  the  control  g o a l , the  the  with path,  stray  a one  rule  i s included in  previous  strategy  e x a c t l y the g o a l s  intelligently  specify  problem  the g o a l s .  independent  of  i s not solves  specified The  Heuristics  strategy  solution  accomplishing  the  the  E.  the  attention  strategy  resulting  Augmenting  solve  is  have  its justification loss  in specially  justification  that  another  to scope,  yet  information to  reason,  needed by  due  held  the m e t a l e v e l  problem  fired.  appendix  In  be  control  penetrance  5.4  lost,  strategic  does not  metarules.  This  is  for  rededuced.  can  actions.  of  has  be  justifications  set  level  when i t i s a g a i n  must  plan provided  s e t of m e t a r u l e s  lower  Notice,  subroutine  it  this  and  ideal  t h e manner  has very the  thus  case  focussed  intelligent. problem the  user  by must  would o p t i m a l l y  i n which t h e  5 R e s u l t s and  goal  is  Evaluation  69 posed. or This  Such a s t r a t e g y  completeness strategy  augmenting arguments /*  V /*  and  i s presented  thus  i s better  i s incorporated  the precondition to the subroutine  into  without called the  proof  a heuristic  previous  of the metarule  of  which  for accomplishing  a  soundness strategy.  metarules  by  determines  the  connection.  This set of r u l e s , c a l l e d 'equivwrap', i s a c o n t r o l s t r a t e g y f o r t h e s e t of l o g i c r u l e s i n 'wrap'. The s t r a t e g y i s t o connect to the closest equivalent p i n . Equivalent pins are t h e o n e s w h i c h w i l l be c o n n e c t e d t o g e t h e r . I f reasoning about object start a connection.  level  which  h a s no p l a n ,  then  */ LEVEL(0) & DEPTH(0) -> { S T A R T _ C O N N E C T I O N } NEXT_RULE(SET(*)). /* I f just terminated V PLAN(*;DEPARTS(*)) -> { C H A I N } NEXT_RULE(SET(*)). /*  a connection,  then  start  the next  one.  I f j u s t s t a r t i n g a connection , then pick a goal which r e q u i r e s t h e c u r r e n t p i n t o be c o n n e c t e d t o a n o t h e r a n d c a l c u l a t e the s h i f t e d l o c a t i o n of the c l o s e s t e q u i v a l e n t pin.  */  PLAN(*P;SET(*)) & !TRUE({*P}ABOVE(*IC1:*PIN1) & WRAPPED(*IC1:*PIN1)) & EQUIV P I N ( * I C 1 : * P I N 1 , * I C 3 : * P I N 3 ) & !TRUEl{*P}WRAPPED(*IC3:*PIN3)) & ( (GOAL(CONNECT(*IC3:*PIN3,*IC2:*PIN2)) & !EQUAL(*JUSTIFI CATION,SOLVING_GOAL(*IC3:*PIN3,*IC2:*PIN2))) | (GOAL(CONNECT(*IC2:*PIN2,*IC3:*PIN3)) & !EQUAL(*JUSTIFICATION,SOLVING_GOAL(*IC2:*PIN2,*IC3:*PIN3)) ) ) & EQUIV P I N ( * I C 2 : * P I N 2 , * I C 4 : * P I N 4 ) & !TRUET{*P}-WRAPPED(*IC4:*PIN4)) & -( EQUIV P I N ( * I C 2 : * P I N 2 , * I C 5 : * P I N 5 ) & !TRUET{*P}-WRAPPED(*IC5:*PIN5)) & !CLOSER(*P,*IC3:*PIN3,*IC5:*PIN5,*IC4:*PIN4) ) -> { S E Q U E N C E 1 ( * I C 4 : * P I N 4 , * J U S T I F I C A T I O N ) } NEXT_RULE(SHI F T ( * I C 4 : * P I N 4 , * , * J U S T I F I C A T I O N ) ) . /*  After  shifting  the v a r i a b l e  to the l o c a t i o n 5 Results  of the p i n , and  Evaluation  70 it  c a n be a p p r o a c h e d .  V PLAN(*;SHI F T ( * I C : * P I N , * , * J U S T I F I C A T I O N ) ) -> (SEQUENCE2(*IC:*PIN,JUSTIFICATION)} NEXT_RULE(APPRO(* I C : * P I N , * : * , * J U S T I F I C A T I O N ) ) . /* A f t e r a p p r o a c h i n g a p i n , t h e t o o l c a n be m o v e d t o i t . */ PLAN(*;APPRO(*IC:*PIN,*:*,*JUSTIFICATION)) -> (SEQUENCE3(*IC:*PIN,*JUSTIFICATION)} NEXT_RULE(MOVES(*IC:*PIN,*JUSTIFICATION)). /*  After between  moving i t and  to a p i n , wrapping i t w i l l the previous p i n .  cause a  connection  */ PLAN(*;MOVES(*IC:*PIN,*JUSTIFICATION)) -> {SEQUENCE4(*IC:*PIN,JUSTIFICATION)} NEXT_RULE(SIGNAL(1,*IC:*PIN,*JUSTIFICATION)). /* A f t e r wrapping a p i n the t o o l can depart. V PLAN(*;SIGNAL(1,*IC:*PIN,*JUSTIFICATION)) -> {SEQUENCE5(*IC:*PIN)} NEXT R U L E ( D E P A R T S ( * I C : * P I N ) ) .  Notice  that  "equivalent" goal reason  now  becomes  in  connected  pins  the  specification.  of  slot  slots  justified  as a  The  These by  level  would simply  some o t h e r  specified in a goal. justification;  must  be  metafacts  this  way).  the wrapping of a p i n  metafacts  the preprocessor.  without  cause  p a r t i c u l a r p i n not  equivalent  i n the object  the rules  extra  that  goal.  t o be  may  to another  important  for connecting  automatically  rules  (but c l o s e r )  mentioned  extra  the  Note  particular  which assert  be that  does  the  5 Results  even  problem asserted  not p r e c l u d e  of  a  a l l the  the addition  strategy;  truth  a  easily  remain u n i n s t a n t i a t e d Also,  i s , as  necessarily  s p e c i f i e d as  can  actions  that  This  that  of  an  the  use  i s ,  the  i f not used (or facts  and  is  not  Evaluation  71  dependent the  on t h e s e  parsing  If  we  figure  of n a t u r a l language  again  sections,  justifications.  the  pose  i s presented  the problem  solution  i s  to  control  [McCord, 8 2 ] ,  in  the  previous  more a p p r o p r i a t e l y a s shown i n  5.  Figure  Rules  We  have  straightforward  1) a r u l e 2) a  The  rules  ic:3  for  extension  Solution  Chains  rules  which  accomplishing  of  the  simply many  previous.  chain  chains  Two  more  pins are  a  object  a r e needed: for cutting  rule  connection  Many  so f a r c o n s i d e r e d The  rules  rc.2.  5. I n t e l l i g e n t  f o r Connecting  together.  level  by  considered  now  *c*.i  5.5  The u s e o f s l o t s  for  (i.e.  strategy  the wire  wrapping  the f i r s t  for  a  pin  without  p i n i n a new  dealing  with  accomplishing  a  chain).  these  new  rules  i s  as  follows.  5 Results and E v a l u a t i o n  72 1) C u t is  i f the current  chain  c a n n o t be  continued ( i . e .  completed). 2)  next /*  the wire  If a chain  has  just  terminated,  start  the next  chain  at the  closest pin. T h i s s e t of r u l e s , c a l l e d 'multiwrap*, i s a c o n t r o l s t r a t e g y f o r t h e s e t of l o g i c r u l e s i n 'wrap'. The strategy i s to connect to the c l o s e s t e q u i v a l e n t p i n a n d c u t t h e w i r e when t h e c h a i n i n g i s c o m p l e t e . The n e x t c h a i n i s s t a r t e d a t t h e c l o s e s t p i n .  */ /*  I f reasoning about start a connection.  object  level  which has  no  plan,  then  V LEVEL(0) & DEPTH(0) -> { S T A R T _ C O N N E C T I O N } NEXT_RULE(SET(*)). /* I f just terminated */ PLAN(*;DEPARTS(*)) -> { C H A I N } NEXT_RULE(SET(*)). /*  a connection,  After completing a connection, t h a t n e e d s t o be w r a p p e d .  then  shift  start  the next  to the c l o s e s t  one.  pin  */ PLAN(*P;SIGNAL(2,*IC1:*PIN1)) & (GOAL(CONNECT(*IC:*PIN,*)) | GOAL(CONNECT(*,*IC:*PIN))) & -•( (GOAL (CONNECT ( * I C 2 : * P I N2 , * ) ) | GOAL (CONNECT (*,* I C 2 : * P I N2 ) ) ) & !CLOSER(*P,*IC1:*PIN1,*IC2:*PIN2,*IC:*PIN)) & -!TRUE({LEVEL(1)}PLAN(*;START_NEXT_CHAIN(*),1)) -> (START_NEXT_CHAIN(*IC:*PIN)} NEXT_RULE(SHIFT(*IC:*PIN,*, MOVING_TO_START_CHAIN(*IC:*PIN))). /*  I f j u s t s t a r t i n g a c o n n e c t i o n , then p i c k a g o a l which r e q u i r e s t h e c u r r e n t p i n t o be c o n n e c t e d t o a n o t h e r a n d c a l c u l a t e the s h i f t e d l o c a t i o n of the c l o s e s t e q u i v a l e n t pin.  */ PLAN(*P;SET(*)) & !TRUE({*P}ABOVE(*IC1:*PIN1) & WRAPPED(*IC1:*PIN1)) & EQUIV_PIN(*IC1:*PIN1,*'IC3 :*PIN3) & !TRUE({*P}WRAPPED(*IC3:*PIN3)) & ( (GOAL(CONNECT(*IC3:*PIN3,*IC2:*PIN2)) & !EQUAL(*JUSTIFICATION,SOLVING GOAL(*IC3:*PIN3,*IC2:*PIN2))) 5 R e s u l t s and  Evaluation  73 |  (GOAL(CONNECT(*IC2:*PIN2,*IC3:*PIN3)) & !EQUAL(*JUSTIFI CATION,SOLVING_GOAL(*IC2:*PIN2,*IC3:*PIN3)))) EQUIV P I N ( * I C 2 : * P I N 2 , * I C 4 : * P I N 4 ) & !TRUEl{*P}--WRAPPED(*IC4:*PIN4) ) & -•(EQUIV P I N ( * I C 2 : * P I N 2 , * I C 5 : * P I N 5 ) & !TRUET{*PJ-WRAPPED(*IC5:*PIN5))  &  &  !CLOSER(*P,*IC3:*PIN3,*IC5:*PIN5,*IC4:*PIN4)) ->  {SEQUENCE 1 (*IC4:*PIN4,JUSTIFICATION)}  NEXT_RULE(SHIFT(*IC4:*PIN4,*,*JUSTIFICATION)). /*  I f ready to s t a r t a connection chain t o , then cut the wire.  and  there  i s no  V PLAN(*P;SET(*)) & !TRUE({*P}AB0VE(*IC1:*PIN1) & WRAPPED(*IC1:*PIN1)) -(EQUIV_PIN(*IC1:*PIN1,*IC3:*PIN3) & G0AL(C0NNECT(*IC3:*PIN3,*))) -> {END_CHAIN(*IC1:*PIN1)} NEXT_RULE(SIGNAL(2,*IC1:*PIN1)). /* it  After s h i f t i n g the v a r i a b l e c a n be a p p r o a c h e d .  to the l o c a t i o n  pin to  &  of  the p i n ,  V PLAN(*;SHI FT(*IC:*PIN,*,*JUSTIFICATION)) -> { S E Q U E N C E 2 ( * I C : * P I N , * J U S T I F I C A T I O N ) } NEXT_RULE(APPRO(*IC:*PIN,*:*,*JUSTIFICATION)). /* A f t e r a p p r o a c h i n g a p i n , t h e t o o l c a n be m o v e d V PLAN(*;APPRO(*IC:*PIN,*:*,*JUSTIFICATION)) -> { S E Q U E N C E 3 ( * I C : * P I N , J U S T I F I C A T I O N ) } NEXT_RULE(MOVES(*IC:*PIN,JUSTIFICATION)). /*  After between  moving i t and  to a p i n , wrapping i t w i l l the previous p i n .  to i t .  cause a  connection  V PLAN(*;MOVES(*IC:*PIN,*JUSTIFICATION)) -> {SEQUENCE4(*IC:*PIN,*JUSTIFICATI0N)} NEXT_RULE(SIGNAL(1,*IC:*PIN,*JUSTIFICATION)). /* A f t e r wrapping a p i n the t o o l can d e p a r t . */ PLAN(*;SIGNAL(1,*IC:*PIN,*JUSTIFICATION)) -> { S E Q U E N C E 5 ( * I C : * P I N ) } This  set of  section the  next  5.1  rules and  section  was  used  i t s skeleton to solve  a  to solve logic larger  the  and  introductory  control  practical  will  be  problem.  5 Results  and  problem i n used  in  Notice  in  Evaluation  74 figure  3 that, given  STARTIC,  5.6  i t proceeds  Pragmatic The  compared  the to  planning  of  declaring  programming  languages.  sequence  costly. for  the  sequence  The  The  into  r u l e s are  strategy  modified  notion  to  for  had  just  closest pin  to  a control strategy a  fixed  Thus,  of  a  the form  VAL  based  on  and  the  faster  the  wrapping  next  in  replanning  i s introduced resulting then  costly  as  conventional  wrap s u b r o u t i n e  The  chain.  Problem  is relatively  planning  which are  is  of  overly  which  plan  the  stands  i s thus  m a c r o e x p a n d e d by  a the  instructions. the  choosing  tradeoff a  Real  as  wrap sequence.  the  start  strategy  wrap macro  actions  terminated  for Solving a  rules that  wrap  postprocessor The  of  particular of  the  Considerations  to  fixed  tool  slight  ones  the  from  next  increase  planning  the pin  in  for  considerably  /*  T h i s s e t of r u l e s , c a l l e d ' l a r g e w r a p ' , large wire-wrapping problems.  1 0  previous  section.  in a chain  robot  arm  has  been  thrashing  . i s used  for solving  */ /*  */  I f a c h a i n c a n n o t be c o n t i n u e d ( i . e . i s c o m p l e t e d ) , p i c k a p i n on t h e c u r r e n t c o m p o n e n t i f p o s s i b l e .  PLAN(*P) & !TRUE({*P}ABOVE(*IC1:*PIN1) & WRAPPED(*IC1:*PIN1)) -(EQUIV_PIN(*IC1:*PIN1,*IC3:*PIN3) & GOAL(CONNECT(*IC3:*PIN3,*))) &  then  &  The strategy for choosing the closest pin, which requires computing the distance t o e v e r y o t h e r p i n , c a n be s u b s t i t u t e d s i m p l y by r e p l a c i n g t h e o n e m e t a r u l e . Other s t r a t e g i e s include the combination of choosing the current component e l s e the c l o s e s t p i n or a n o t h e r i s c h o o s i n g the c l o s e s t component. 1 0  5 Results  and  Evaluation  75 (  (!EQUAL(*IC,*IC1) & (GOAL(CONNECT(*IC:*PIN,*)) | G O A L ( C O N N E C T ( * , * I C : * P I N ) ) ) ) | GOAL(CONNECT(*IC:*PIN,*)) ) & -!TRUE({LEVEL(1)}PLAN(*;START_NEXT_CHAIN(*,*),1)) -> {START_NEXT_CHAIN(*IC:*PIN,*IC1:*PIN1)} N E X T _ R U L E ( W R A P ( * I C : * P I N , * I C 1 : * P I N 1 , * , MOVING_TO_START_CHAIN(*IC:*PIN))).  /*  I f just starting a connection , then p i c k a goal which r e q u i r e s t h e c u r r e n t p i n t o be c o n n e c t e d t o a n o t h e r a n d c a l c u l a t e the s h i f t e d l o c a t i o n of the c l o s e s t equivalent pin.  V PLAN(*P) & !TRUE({*P}ABOVE(*IC1:*PIN1) & WRAPPED(*IC1:*PIN1)) & EQUIV P I N ( * I C 1 : * P I N 1 , * I C 3 : * P I N 3 ) & !TRUEl{*P}WRAPPED(*IC3:*PIN3)) & ( '(GOAL ( C O N N E C T ( * I C 3 : * P I N 3 , * I C 2 : * P I N 2 ) ) & !EQUAL(*JUSTIFICATION,SOLVING_GOAL(*IC3:*PIN3,*IC2:*PIN2))) | (GOAL(CONNECT(*IC2:*PIN2,*IC3:*PIN3)) & !EQUAL(*JUSTIFI CATION,SOLVING_GOAL(*IC2:*PIN2,*IC3:*PIN3))) EQUIV P I N ( * I C 2 : * P I N 2 , * I C 4 : * P I N 4 ) & !TRUE"C{*P}-WRAPPED(*IC4:*PIN4) ) & -(EQUIV P I N ( * I C 2 : * P I N 2 , * I C 5 : * P I N 5 ) & !TRUET{*P}-WRAPPED(*IC5:*PIN5)) & ! C L O S E R ( * P , * I C 3 : * P I N 3 , * I C 5 : * P I N 5 , * I C 4 : * P I N 4 ) ) -> {MAKE_CONNECTION(*IC4:*PIN4,*IC1:*PIN1,*JUSTIFICATION)} N E X T _ R U L E ( W R A P ( * I C 4 : * P I N 4 , * I C 1 : * P I N 1 , * , * J U S T I F I C A T I O N ) ) .  /* V -> ->  Order  that  the rules  should  be n o n d e t e r m i n i s t i c a l l y  )  chosen.  {METAFACTS}CHOOSE(START_NEXT_CHAIN(*,*)). {METAFACTS}CHOOSE(MAKE_CONNECTION(*,*,*)).  /* Macro r u l e t o wrap t h e beginning p i n i n a V LOCATION(*IC,*ICLOC) & NO_PINS(*IC,*N) & !BETWEEN(*PIN,1,*N) & -WRAPPED(*IC:*PIN) & !REFERENCE_PIN_SHIFT(*PIN,*N,*DISP) & !RELOCATE(*ICLOC,*DISP,*PINLOC) & ABOVE(*OLDIC:*OLDPIN) -> { W R A P ( * I C : * P I N , * O L D I C : * O L D P I N , * P I N L O C ,  chain.  SOLVING_GOAL(*IC1:*PIN1,*IC2:*PIN2))}  -ABOVE(*OLDIC:*OLDPIN) ABOVE(*IC:*PIN) & WRAPPED(*IC:*PIN) &  &  5  Results  and Evaluation  &  76 CONNECT(*IC1:*PIN1,*IC2:*PIN2).  /* Macro r u l e t o wrap a p i n i n t h e c u r r e n t V LOCATION(*IC,*ICLOC) & NO_PINS(*IC,*N) & !BETWEEN(*PIN,1,*N) & -WRAPPED(*IC:*PIN) & !REFERENCE_PIN_SHIFT(*PIN,*N,*DISP) & !RELOCATE(*ICLOC,*DISP,*PINLOC) & ABOVE(*OLDIC:*OLDPIN) -> { W R A P ( * I C : * P I N , * O L D I C : * O L D P I N , * P I N L O C , MOVING_TO_START_CHAIN(*))} -ABOVE(*OLDIC:*OLDPIN) & ABOVE(*IC:*PIN) & WRAPPED(*IC:*PIN).  The  small  extended areas the  range  position  [Peterson,  given  summary,  the pins  another  on  connections the  sensor  circuit that  diagram  problem  i s  consists  chosen  works  7 8 ] . The p r o b l e m  schematic  sixteen  All  but r e a l i s t i c  measuring  t o b e made  connections  shown on t h e d i a g r a m .  i n high  included of  in  three  three  specified  The s o l u t i o n  noise  obtained  appendix  are laid  chains  i s an  ambient  out  There of  In  one o f  one  above  are nineteen three  a t random and they  o f f e r e d i s shown  from  B.  components,  50mm x 100mm.  including are  as a problem  specification  and two o f f o u r t e e n , w h i c h a board  chain.  in  pins. arenot figure  6.  5 Results  and E v a l u a t i o n  77  Figure  6.  Realistic  Problem  5  Solution  Results  and  Evaluation  78  CHAPTER 6  Conclusion  This  thesis  has  proposed  a  particular  r e p r e s e n t i n g and using metaknowledge in PSs. can  reason  about  philosophically  its  justifies  R e c a p i t u l a t i o n of the  6.1  own  language  In  reasoning.  effect, This  for RCPS  chapter  these means.  Results  The main c l a i m s of the previous chapter and of t h i s  thesis  are the f o l l o w i n g . 1) Metaknowledge i n c r e a s e s the even  when  considering  the  penetrance effort  towards  required  the to  goal  do  the  metareasoning. 2) Metaknowledge  increases  by r e q u i r i n g e f f e c t i v e These  justifications  r e s u l t s are i n t u i t i v e l y  a facility  for s p e c i f y i n g and  they  very  are  the  problem.  The f i r s t  control Indeed,  monotonically.  f o r the i n f e r e n c e s t e p s .  s a t i s f y i n g since we are p r o v i d i n g using  more  knowledge;  however,  strong c l a i m s that need f u r t h e r and more general  justifications. that  the i n t e l l i g e n c e of the deduction  c l a i m i s made  problem it  This  is  less  i s assumed that is  the  under  complex the  the  assumption  than  the  complexity  object  decreases  case f o r some c l a s s of problems. 6 Conclusion  79  The r e c u r s i v e class  of  technique advocated provides a paradigm  problems.  In  force  Someone who s o l v e s a  cannot be c o n s i d e r e d more i n t e l l i g e n t  who s o l v e s the same problem with v a l i d inference results  even  though  pertaining  to  this  the authors o p i n i o n , the second c l a i m  does not depend on the f i r s t . brute  for  the  latter  the  RCPS  problem  by  than someone  justifications  for  the  r e q u i r e d more e f f o r t .  The  implementation  the  and  d e s c r i p t i v e adequacy of the RCPS language i s c o n s i d e r e d n e x t ; particular,  we are not concerned, at t h i s p o i n t , with the domain  which has been chosen to e l u c i d a t e The  in  RCPS  implementation  is  a  results.  robust,  additive  and modular, but the c o n t r o l and the amount of c o n t r o l  is a l s o .  The e f f e c t  with  various  implementation  of such modularity Thus,  logic has  and also  of  the  purpose  Not only i s  modification.  specification  general  planner.  of  the  these  logic  i s f l e x i b i l i t y and  system  provides  ease  RCPS i s very u s e f u l f o r experimenting control proven  components.  itself  The  efficient  the  usual  facilities  RCPS  in space and  time even though the host PROLOG used i s i n t e r p r e t i v e . run-time  rules  The RCPS  offered  by  standard programming languages. Rating the power however, in terms 1)  of  some c r i t e r i a  expression  are g i v e n .  in  RCPS  One can judge  is  subjective;  expressibility  of:  the c o n c i s e n e s s of the code  2) the r e a d a b i l i t y  of the code 6 Conclusion  80 3)  the  inherent principle  Typically, vice  languages  versa.  For  language  like  on  other  that  the RCPS  is  strategy, one  APL  level  of  action  both  they  inference; that  have  a  easily  behind  intuitive,  the  is  difficult  components. simply  by  This  to the  Related  Al;  primary  language has  to  think  however,  slow  stumbling  block  least  at  Direction  been and  are  separate  can  regarded  since  Although support  and  is  that  control  languages  is  in  the  statement  is  as  a  fault  with  80a].  Research  active  i s b e i n g made  is  lack  a  the  and  beginning,  [Davis,  i s an  of  one  readable  sequence  progress the  than  statements  for Further  still  only  that  i n most  language  and  shows  logic  the  be  the  claim  introductory  prose.  separate  the  control  well-founded  ordering  characteristic  has  in  COBOL, We  i s longer  rules  a  wire-wrapping  however,  statements  I n RCPS, a  I s s u e s and  The  at  in  of  of  of  and  author,  concise.  The  4.6,  has  found,  implicitly  level  given).  RCPS.  the  The  metaplan  paraphrased  conciseness  Metareasoning in  of  sequencing  desired.  required.  6.2  The  done  sequence  respect  the  author  o n l y one  of  readable.  readable.  i s , no  readability  easily  f a r from  in section  limitation  been  but  for  opinion  i s not  the  example  language.  the  and  has  (excluding  i s not  in  i s readable  example,  principal  it  example,  concise  the  conciseness  i s c o n c i s e but  content-reference this  tradeoff  hand,  for  behind  research  i n the theory  area  area.  The  about  the  6 Conclusion  81  process about be  the  posed  The the  of  reasoning.  language and  the  plans  and  location  errors.  A  as  as  simple  Such  a  that  the  a metalanguage  reasoning  before  i s needed  theoretic  to  talk  arguments  can  solved.  presented  PUMA r o b o t  sensing  of  Indeed,  arm.  Since  servo of  touch  planner robot  the  paper  arm,  capabilities,  the  truly  in this  pin to  adaptive sensors, would  could  be  generate  adapt  been e x e c u t e d  presented,  does not  i m p r e c i s i o n i n the  wrapped  system and  as  have not  would  may  cause  arm  have and/or  positioning  include sensors,  a conditional  planning  perhaps system.  programs w i t h c o n d i t i o n a l s  itself  to  the  on  environment  such being  sensed.  6  Conclusion  82 BIBLIOGRAPHY Abe, R., S. Ueno, S. T s u j i k a d o , a n d H. Takagi, "The Programming Language for Welding Robots", Symposium on I n d u s t r i a l Robots, Japan I n d u s t r i a l Robot A s s o c i a t i o n , 1981. B i s o n , P., G. L o r e n z i n , a n d E. P a g e l l o , "The F o r m a l D e f i n i t i o n of VML and a P r o p o s e d P o r t a b l e I m p l e m e n t a t i o n " , Symposium on I n d u s t r i a l Robots, Japan I n d u s t r i a l Robot A s s o c i a t i o n , 1981. B y r d , L . , " U n d e r s t a n d i n g t h e C o n t r o l F l o w o f PROLOG Programs", Department of A r t i f i c i a l I n t e l l i g e n c e , U n i v e r s i t y of Edinburgh, S c o t l a n d , 1980. C l a r k , K. S., "Negation G a l a i r e and Minker (eds.), Clocksin, W. Springer-Verlag  as F a i l u r e " , Logic and P l e n u m , New Y o r k , 1 9 7 8 .  Databases,  F. a n d C. S. M e l l i s h , P r o g r a m m i n g i n PROLOG, B e r l i n H e i d e l b e r g , New YorV, 1981 C58-78).  C o l m e r a u e r , A., " L e s S y s t e m e s - q o u u n F o r m a l i s m e pour Analyser et Synthetiser des Phrases sur Ordinateurs", Internal p u b l i c a t i o n number 4 3 , D e p a r t e m e n t d ' I n f o r m a t i q u e , U n i v e r s i t e de M o n t r e a l , September, 1970. Condec Unimation R o b o t i c s , "Puma R o b o t M a n u a l 3 9 8 H " , I n c o r p o r a t e d , S h e l t e r R o c k L a n e , D a n b u r y CT. 06810. Cutland, Function  Unimation  N. J . ,Computabi1ity: An Introduction to Recursive Theory. C a m b r i d g e U n i v e r s i t y P r e s s , 1980 " ( C h a p t e r 3) .  Davis, R. and J . K i n g , "An O v e r v i e w o f P r o d u c t i o n M a c h i n e I n t e l l i g e n c e , E l c o c k , E . W. and M i c h i e , D. W i l e y , New Y o r k , 1 9 7 6 ( 3 0 0 - 3 3 2 ) .  Systems" (ed.),  D a v i s , R., a n d B. G. Buchanan, "Meta L e v e l Knowledge: O v e r v i e w and A p p l i c a t i o n s " , P r o c e e d i n g s o f t h e 5 t h I J C A I - 7 7 , Cambridge, MA, 1 9 7 7 ( 9 2 0 - 9 2 7 ) . Davis, R. , "Interactive Transfer of E x p e r t i s e : New I n f e r e n c e R u l e s " , Artificial Intelligence, H o l l a n d P u b l i s h i n g Company, 1979 ( 1 2 1 - 1 5 7 ) . Davis, R. , " M e t a R u l e s : R e a s o n i n g March 1980a. Davis, R., "Content Reference: Artificial Intelligence, 15(3), Company, 1980b.  about  Control",  A c q u i s i t i o n of 12(2), North A l memo # 5 7 6 ,  Reasoning about Rules", North Holland Publishing  Bibliography  83  De K l e e r , J . , J . Doyle, G. L. Steele J r . , a n d G. J. Sussman, "AMORD: E x p l i c i t C o n t r o l o f R e a s o n i n g " , S I G P L A N / S I G A R T 1 2 ( 8 ) , A u g u s t 1977 ( 1 1 6 - 1 2 5 ) . D e s c o t t e , Y. a n d J . - C . Latombe, "GARI: A P r o b l e m Solver that Plans how t o Machine Mechanical P a r t s " , Proceedings of t h e7 t h I J C A I - 8 1 , V a n c o u v e r , B . C . , 1981 ( 7 6 6 - 7 7 2 ) . D o y l e J . , "A T r u t h M a i n t e n a n c e S y s t e m " , A r t i f i c i a l Intelligence, 1 2 ( 3 ) , N o r t h H o l l a n d P u b l i s h i n g Company, 1979 ( 2 3 1 - 2 7 2 ) . Erman, Hearsay Resolve  L . , F. Hayes-Roth, V. Lesser, a n d D. R e d d y , "The I I Speech Understnading System: I n t e g r a t i n g Knowledge t o U n c e r t a i n t y " , C o m p u t i n g S u r v e y s , ACM 1 2 ( 2 ) , 1 9 8 0 .  Ernst, G. and P r o b l e m  W. a n d A. N e w e l l , GPS: A Case S t u d y i n G e n e r a l i t y S o l v i n g , Academic P r e s s I n c o r p o r a t e d , 1969.  F i k e s , R. E. a n d N. J . N i l s s o n , " S T R I P S : A New Approach to the Application o f Theorem Proving t o Problem Solving", A r t i f i c i a l I n t e l l i g e n c e , 2, N o r t h Holland Publishing Company, 1 971 . Fikes, R. E . , P. E. H a r t , a n d N. J . N i l s s o n , "Some New D i r e c t i o n s i n Robot Problem Solving" Machine Intelligence 1_, M e l t z e r a n d M i c h i e ( e d . ) , J o h n W i l e y a n d S o n s , 1972 ( 4 0 5 - 4 3 0 ) . Freitas J r . , R. A., T. J . H e a l y , a n d J . E. Long, Automaton f o r Space M i s s i o n " , P r o c e e d i n g s of t h e 7 t h V a n c o u v e r , B . C . , 1981 ( 8 0 3 - 8 0 7 ) .  "Advanced IJCAI-81,  Futami, S., N. K i j u r a , a n d I . M a t s u m o t o , "A C o n t r o l A l g o r i t h m f o r T r a c i n g and V i s u a l S e r v o i n g by I n d u s t r i a l R o b o t s " , Symposium on I n d u s t r i a l R o b o t s , J a p a n I n d u s t r i a l R o b o t A s s o c i a t i o n , 1 9 8 1 . Galer, B. A. a n d A. J. Perlis, A View of Programming Languages, Addison-Wesley P u b l i s h i n g Company, 1970. Georgeff, Systems", (328-334).  M. P., "A Framework f o r Control i n Production Proceedings o f t h e 6 t h I J C A I - 7 9 , T o k y o , J a p a n , 1979  G e o r g e f f , M. P., " P r o c e d u r a l C o n t r o l Artificial Intelligence, 18(2), C o m p a n y , M a r c h 1982 ( 1 7 5 - 2 0 1 ) .  i n Production North Holland  H a y e s , P., " T h e F r a m e Problem and Related Problems Artificial a n d Human T h i n k i n g , E l i t h a n A., a n d J o n e s J o s s e y - B a s s 1973. Hayes,  P.,  "In  Defense  of  Logic",  Proceedings  of  Systems", Publishing  in A l " , D., ( e d . )  the 5th  Bibliography  84 IJCAI-77,  C a m b r i d g e , MA,  1977  (559-565).  Hayes, P., "The Logic of Frames", Frame Concept i o n s Understanding, M e l z i n g D., ( e d . ) , de G r u y t e r , 1979.  and  Text  Hewitt, C, "Description and Theoretical Analysis (Using Schemata) of Planner: A Language f o r Proving Theorems and Manipulating Models i n a Robot", Massachusetts Institute of Technology, Cambridge Massachusetts, A p r i l 1972. Kowalski, R., t h e ACM, 2 2 ( 7 ) , K o w a l s k i , R., Inc., 1979b.  "Algorithm = Logic 1979a ( 4 2 4 - 4 3 6 ) .  Logic  + C o n t r o l " , Communications of  f o r Problem S o l v i n g , Elsevier  North  Holland  Mackworth, A., "Recovering the Meaning of Diagrams and S k e t c h e s " , G r a p h i c s I n t e r f a c e ' 8 3 , E d m o n t o n , A l b e r t a , May 1983. M a n n a , Z. a n d R. Waldinger, "A D e d u c t i v e A p p r o a c h to Program Synthesis", ACM Transactions on Programming Languages and S y s t e m s , 2 ( 1 ) , 1980. M a s a k i , I . , R. G o r m a n , a n d B. Shulman, "Arc Welding Robot w i t h Vision" Symposium on I n d u s t r i a l R o b o t s , J a p a n I n d u s t r i a l R o b o t A s s o c i a t i o n , 1981. M c C o r d , M., " U s i n g S l o t s a n d Modifiers i n Logic N a t u r a l Language", A r t i f i c i a l I n t e l l i g e n c e , 18(3), P u b l i s h i n g C o m p a n y , May 1982 ( 3 2 7 - 3 6 7 ) .  Grammar for North Holland  McDermott, J . , and C. Forgy, "Production System Conflict Resolution Strategies", Pattern P i rected Inference Systems, Watermann and H a y e s - R o t h ( e d . ) , Academic Press, London, 1978 (177-199) . Minsky, Cliffs,  M. , C o m p u t a t i o n : F i n i t e a n d N. J . , P r e n t i c e H a l l , 1967  Moore, R. Proceedings  Inf inite (Chapter  Machines, Englewood 12).  C. , "Reasoning about Knowledge o f t h e 5 t h I J C A I - 7 7 , C a m b r i d g e , MA,  Nilsson, N. J . , Pr inc i p l e s P a l o A l t o , 1980 ( 2 1 , 9 1 - 9 4 ) . 0 Duda, R., and J. G. S y s t e m s come o f A g e " , B Y T E ,  of A r t i f i c i a l  and Action", 1977 ( 2 2 3 - 2 2 7 ) .  Intelligence,  Tioga,  Gaschnig, "Knowledge-Based 6 ( 9 ) , Mc G r a w H i l l , 1981.  Peterson, D., "Circuit Ideas", Fairchild Semiconductor Progress, 6 ( 4 ) , 1 9 7 8 ( 1 2 ) .  Journal  Expert  of  Bibliography  85 Reiter, Galaire  R., "On C l o s e d W o r l d D a t a B a s e s " , L o g i c and M i n k e r ( e d . ) , Plenum P r e s s , 1978.  and Data  Bases,  Roussel, P h . , "PROLOG, M a n u e l d ' U t i 1 i s a t i o n " , I n t e r n a l R e p o r t , G r o u p e d ' I n t e l l i g e n c e A r t i f i c i e l l e , UER de Luminy, Universite d ' A i x - M a r s e i l l e , September 1975. Rosenschein, Proceedings (331-337).  S. J . , "Plan Synthesis: A L o g i c a l Perspective", of the 7th IJCAI-81, Vancouver, B.C., 1981  Rychener, M. D., Production System 1977 (37-44).  "Control Requirements f o r the Design of A r c h i t e c t u r e s " , SIGPLAN/SIGART Newsletter,  Sacerdoti, E. D., A Structure E l s e v i e r , New Y o r k , 1 9 7 7 . S a l o m a a , A., F o r m a l  for  Languages, Academic  Plans  Press,  and  Behaviour,  New Y o r k , 1 9 7 7 .  S h o r t l i f f e , E. H., A. C. Scott, M. B. Bishop, A. B. Campbell, W. Van M e l l e , a n d D. J a c o b s , "ONCOCIN: A n e x p e r t System f o r O n c o l o g y P r o t o c o l Management", P r o c e e d i n g s o f t h e 7 t h I J C A I - 8 1 , V a n c o u v e r , B.C., 1981 ( 8 7 6 - 8 8 1 ) . Stefik, M., "Planning with R e p o r t STAN-CS-80-784, J a n u a r y Stefik, M., Intelligence,  "Planning 16(2), North  Constraints", 1980.  and Holland  Stanford  Technical  Meta-Planning", Artificial P u b l i s h i n g Company, 1 9 8 1 .  Stefik, M., R. Balzer, J. Benoit, L. Birnhaum, F. Hayes-Roth, and E Sacerdoti, "The O r g a n i z a t i o n of Expert Systems, A Tutorial", Artificial Intelligence, 18(2), North H o l l a n d P u b l i s h i n g Company, M a r c h 1982, ( 1 3 5 - 1 7 3 ) . T r e m b l a y , J . P. A n d P. G. S o r e n s o n , An I n t r o d u c t i o n t o S t r u c t u r e s w i t h A p p l i c a t i o n s , McGraw H i l l , 1976 (60) . Tate, A., " I n t e r a c t i n g G o a l s a n d T h e r e U s e " , P r o c e e d i n g s 5 t h I J C A I - 7 5 , T b i l i s i , G e o r g i a , U.S.S.R., 1 9 7 5 . W a l d i n g e r , R., " A c h i e v i n g Intelligence 8, Elcock (94-136).  of the  S e v e r a l Goals Simultaneously", Machine a n d M i c h i e ( e d . ) , E l l i s H o r w o o d , 1977  W a r r e n , D. memo no. J u n e 1974.  H. D., "WARPLAN: A S y s t e m 76, Dept. O f Comp. Logic,  W a r r e n , D.  H.  D.,  Data  f o r Generating Plans", U n i v e r s i t y of Edinburgh,  "WARPLAN", U n i v e r s i t y  of  British  Columbia  Bibliography  86 implementat ion. Waterman, Inference  D. A., a n d F., H a y e s - R o t h , ( e d . ) Pattern Systems, Academic P r e s s , London, 1978.  Directed  W e e k , M., W. E v e r s h e i m , a n d D. Z u e h l k e , "Robex An Off-line Programming System for Industrial Robots", Symposium on I n d u s t r i a l Robots, Japan I n d u s t r i a l Robot A s s o c i a t i o n , 1981. W i l e n s k y , R., "Meta-Planning: R e p r e s e n t i n g and Using Knowledge About Planning in Problem Solving and Natural Language Understanding", Cognitive Science, 5(3), Ablex Publishing C o r p o r a t i o n , J u l y - S e p t e m b e r , 1981, (197-234). Zisman, M. D., "Use of Production Systems for Modelling Asynchronous Concurrent Processes", Pattern Directed Inference Systems, Waterman and H a y e s - R o t h ( e d . ) , Academic P r e s s , London, 1978 (53-68).  Bibliography  87  APPENDIX A  Trace  of the Content  PROLOG/MTS 0 . 0 END OF F I L E READ FROM  Reference  Example  content  Given Facts true Goal c  t o be S o l v e d  Meta P l a n CHOOSE(STRATEGY(* 1)) Suggests Expansion LEVEL(3) ; STRATEGY(* 1 ) P r e c o n d i t i o n o f STRATEGY(STRATEGY(*1)) h o l d s LEVEL(2) & !LE(2,2) & G O A L ( N E X T _ R U L E ( * 1 )) & ! (({(STRATEGY(* 1)}NEXT_RULE(* 1))) ?) Plan  Expanded  Meta Plan LEVEL(3) ; STRATEGY(STRATEGY(* 1)) Suggests Expansion LEVEL(2) ; S T R A T E G Y ( * 1) P r e c o n d i t i o n o f STRATEGY(STRATEGY(*1)) LEVEL( 1 ) & !LE(1,2) & G O A L ( N E X T _ R U L E ( * 1)) & ! ( ( { ( S T R A T E G Y ( * 1 )}NEXT_RULE(* 1 ))) A Trace  of the Content  holds  ?) Reference  Example  88  Plan  Expanded  Meta Plan LEVEL(2) ; STRATEGY(STRATEGY(* 1)) Suggests Expansion LEVEL(1) ; S T R A T E G Y ( * 1) P r e c o n d i t i o n of STRATEGY(C) LEVEL(0) & !LE(0,2) & GOAL(c) & ! ( ( { ( C } c ) ) ?) Plan  holds  Expanded  Meta P l a n LEVEL(1) ; STRATEGY(C) Suggests Expansion LEVEL(0) ; C Precondition true Plan  of C  holds  Expanded  S o l u t i o n to Problem true -> { L E V E L ( 0 ) C } c. E X I T PROLOG/MTS 0.0  ;  A Trace of  the Content Reference  Example  89  APPENDIX B  Circuit  The  schematic  [Peterson,  78],  placement circuit actual  on  diagram is  the DIPs  layout  of the p r o x i m i t y s e n s o r , d e s i g n e d  shown and  i s depicted  Design  below the  RCPS  in figure  along  with  problem 6 which  the  component  statement. i s drawn  by  two  The times  size.  v/  cc  — NO  oerecT  V & = OBJECT DETECTED 0  RI C|= f  - IO  K  o.OI^F  *5  kH*  B Circuit  Design  DIP  6p. 3o  *0 1  o  I  DJPZ  yyyNjBk-o ' °  4-  90  C5  I ^ L Q I Z  -vW ^ *4 2  SYMB0LIC_0RIGIN(or1g1n) & L0CATI0N(STARTIC,O:O) & NO_PINS(STARTIC,0) & WRAPPED(STARTIC:0) & ABOVE(STARTIC:0) & L0CATI0N(SIGNAL,250:980) & L0CATI0N(GND1,325:940) & L0CATI0N(UA758,150:820) & L0CATI0N(VCC1.175:700) & LOCATI0N(GND2,325:62O) & L0CATI0N(DIP1,150:500) & L0CATI0N(VCC2,175:380) & L0CATI0N(GND3,325:3OO) & L0CATI0N(DIP2,150:180) & L0CATI0N(VCC3,175:60) & N0_PINS(DIP1,14) & N0_PINS(DIP2,14) & N0_PINS(UA758,16) & N0_PINS(VCC1,0) & N0_PINS(VCC2.0) & N0_PINS(VCC3,0) & N0_PINS(GND1,0) & N0_PINS(GND2,0) & N0_PINS(GND3,O) & NO_PINS(SIGNAL,0) -> {*> C0NNECT(DIP1:1,UA758:1) & C0NNECT(DIP1:2,UA758:12) & C0NNECT(DIP1:3,UA758:10) & C0NNECT(DIP1:4,UA758:14) & C0NNECT(DIP1:5,UA758:7) & C0NNECT(DIP1:7,GND2:0) & C0NNECT(DIP1:8,UA758:15) & C0NNECT(DIP1:10,VCC2:0) & C0NNECT(DIP1:11,UA758:13) & C0NNECT(DIP1:12,UA758:9) & C0NNECT(DIP1:13,UA758:2) & C0NNECT(DIP1:14,GND2:0) & C0NNECT(UA758:8,GND1:0) & CONNECT(UA758:16,VCC1:0) & C0NNECT(UA758:11,DIP2:4) & C0NNECT(DIP2:1.UA758:1) & C0NNECT(DIP2:7,GND3:O) & C0NNECT(0IP2:14,VCC3:0) & C0NNECT(SIGNAL:0,UA758:7).  B Circuit  Design  91  APPENDIX  Complete  /*  C  Set of Multiwrap  Rules  T h i s s e t of r u l e s , c a l l e d 'multiwrap', i s a c o n t r o l s t r a t e g y f o r t h e s e t o f l o g i c r u l e s i n 'wrap'. The strategy i s t o connect to the c l o s e s t equivalent p i n a n d c u t t h e w i r e when t h e c h a i n i n g i s c o m p l e t e . The next c h a i n i s s t a r t e d a t t h e c l o s e s t p i n .  */ /*  I f reasoning about object start a connection.  level  w h i c h h a s no p l a n ,  then  V LEVEL(0) & DEPTH(0) -> { S T A R T _ C O N N E C T I O N } NEXT_RULE(SET(*)).  /* I f just terminated */ PLAN(*;DEPARTS(*)) -> {CHAIN} NEXT_RULE(SET(*)). /*  a connection,  After completing a connection, t h a t n e e d s t o be w r a p p e d .  then  shift  start  the next  one.  to the c l o s e s t p i n  V PLAN(*P;SIGNAL(2,*IC1:*PIN1)) & (GOAL(CONNECT(*IC:*PIN,*)) | GOAL(CONNECT(*,*IC:*PIN))) & -((G0AL(C0NNECT(*IC2:*PIN2,*)) | GOAL(CONNECT(*,*IC2:*PIN2))) !CLOSER(*P,*IC1:*PIN1,*IC2:*PIN2,*IC:*PIN)) & -•! T R U E ( { L E V E L ( 1 ) } P L A N ( * ; S T A R T _ N E X T _ C H A I N ( * ) , 1 ) ) -> {START_NEXT_CHAIN(*IC:*PIN)} NEXT_RULE(SHI F T ( * I C : * P I N , * , MOVING_TO_START_CHAIN(*IC:*PIN))). /* .  &  I f just s t a r t i n g a connection , then p i c k a goal which r e q u i r e s t h e c u r r e n t p i n t o be c o n n e c t e d t o a n o t h e r a n d c a l c u l a t e the s h i f t e d l o c a t i o n of the c l o s e s t e q u i v a l e n t pin.  */ PLAN(*P;SET(*)) & !TRUE({*P}AB0VE(*IC1:*PIN1) & WRAPPED(*IC1:*PIN1)) C Complete  &  Set of M u l t i w r a p  Rules  92 E Q U I V _ P I N ( * I C 1 : * P I N 1 , * I C 3 : * P I N 3 ) !TRUE({*P}WRAPPED(*IC3:*PIN3)) & ( (GOAL(CONNECT(*IC3:*PIN3,*IC2: !EQUAL(JUSTIFICATION,SOLVING | (GOAL(CONNECT(*IC2:*PIN2,*IC3:*  & *PIN2)) & _GOAL(*IC3:*PIN3,*IC2:*PIN2))) PIN3)) &  !EQUAL(*JUSTIFICATION,SOLVING_GOAL(*IC2:*PIN2,*IC3:*PIN3)))) EQUIV P I N ( * I C 2 : * P I N 2 , * I C 4 : * P I N 4 ) & ( * I C 4 : * P I N 4 ) ) & -(EQUIV P I N ( * I C 2 : * P I N 2 , * I C 5 : * P I N 5 ) & !TRUET{*P}-WRAPPED(*IC5:*PIN5)) & ! C L O S E R ( * P , * I C 3 : * P I N 3 , * I C 5 : * P I N 5 , * I C 4 : * P I N 4 ) ) -> {SEQUENCE 1(*IC4:*PIN4,*JUSTIFICATION)}  &  ^Pus-el*?}-WRAPPED  NEXT_RULE(SHIFT(*IC4:*PIN4,*,*JUSTIFICATION)).  /*  I f ready t o s t a r t a connection chain t o , then cut the wire.  V PLAN(*P;SET(*))  and  there  i s no p i n t o  &  !TRUE({*P}ABOVE(*IC1:*PIN1) & WRAPPED(*IC1:*PIN1)) - ( E Q U I V _ P I N ( * I C 1 : * P I N 1 , * I C 3 : * P I N 3 ) & GOAL(CONNECT(*IC3:*PIN3,*))) -> {END_CHAIN(*IC1:*PIN1)} NEXT_RULE(SIGNAL(2,*IC1:*PIN1)).  /* it  After s h i f t i n g the v a r i a b l e c a n be a p p r o a c h e d .  to the l o c a t i o n  &  of the p i n ,  V P L A N ( * ; S H I F T ( * I C : * P I N , * , J U S T I F I C A T I O N ) ) -> {SEQUENCE2(*IC:*PIN,JUSTIFICATION)} NEXT_RULE(APPRO(*IC:*PIN,*:*,JUSTIFICATION)).  /* V  After  approaching  a p i n , the t o o l  c a n be m o v e d  to i t .  P L A N ( * ; A P P R O ( * I C : * P I N , * : * , J U S T I F I C A T I O N ) ) -> {SEQUENCE3(*IC:*PIN,JUSTIFICATION)} N E X T _ R U L E ( M O V E S ( * I C : * P I N , J U S T I F I C A T I O N ) ) .  /*  After between  moving t o a p i n , wrapping i t and the p r e v i o u s p i n .  i t will  cause  a  connection  V P L A N ( * ; MOVES ( * I C : *PI N ,J U S T I FI C A T I ON ) ) -> {SEQUENCE4(*IC:*PIN,JUSTIFICATION)} N E X T _ R U L E ( S I G N A L ( 1 ,* IC:*PIN,JUSTIFICATION)).  /* V  After  wrapping  a p i n the t o o l  can  depart.  PLAN(*;SIGNAL(1,*IC:*PIN,JUSTIFICATION)) -> (SEQUENCE5(*IC:*PIN)} NEXT RULE(DEPARTS(*IC:*PIN)).  C  Complete  Set of Multiwrap  Rules  93 /* */ ->  Order  that  the rules  should  be n o n d e t e r m i n i s t i c a l l y  chosen.  {METAFACTS}CHOOSE(START_CONNECTION).  ->  {METAFACTS}CHOOSE(CHAIN).  ->  {METAFACTS}CHOOSE(SEQUENCE 1 ( * , * ) ) .  -> { M E T A F A C T S } C H O O S E ( S E Q U E N C E 2 ( * , * ) ) . -> { M E T A F A C T S } C H O O S E ( S E Q U E N C E 3 ( * , * ) ) . ->  {METAFACTS}CHOOSE(SEQUENCE4(*,*)) .  ->  {METAFACTS}CHOOSE(SEQUENCE5(*)).  -> { M E T A F A C T S } C H O O S E ( E N D _ C H A I N ( * ) ) . ->  {METAFACTS}CHOOSE(START  /*  The p r o g r a m v a r i a b l e the r u l e i s f i r e d .  */  NEXT  CHAIN(*)).  i s set to the o r i g i n  whenever  SYMBOLIC_ORIGIN(*NAME) -> { S E T ( * N A M E ) } VAR_SET_TO_ORIGIN & - V A R _ S E T _ T O _ P I N _ L O C A T I ON ( * ) . /*  */  I f the program v a r i a b l e i s s e t t o the o r i g i n , choose a component and an unwrapped p i n and s h i f t t h e o r i g i n a c c o r d i n g t o t h e l o c a t i o n of t h e component and t h e p i n number. T h e p r o g r a m v a r i a b l e i s now s e t t o t h e u n w r a p p e d pin location.  VAR_SET_TO_ORIGIN & LOCATION(*IC,*ICLOC) & NO_PINS(*IC,*N) & !BETWEEN(*PIN,1,*N) & -WRAPPED(*IC:*PIN) & !REFERENCE_PIN_SHIFT(*PIN,*N,*DISP) & !RELOCATE(*ICLOC,*DISP,*PINLOC) -> {SHI F T ( * I C : * P I N , * P I N L O C , * J U S T I F I C A T I O N ) } VAR_SET_TO_PIN_LOCATION(*IC:*PIN) & -VAR_SET_TO_ORIGIN. /*  */  I f t h e program v a r i a b l e i s s e t t o the next unwrapped p i n l o c a t i o n and t h e t o o l i s n e i t h e r a t or above i t , then i t c a n be a p p r o a c h e d l e a v i n g t h e p r e v i o u s p i n b e h i n d .  VAR_SET_TO_PIN_LOCATION(*IC:*PIN)  &  C Complete  Set of M u l t i w r a p  Rules  94 -AT(*IC:*PIN) & -ABOVE(*IC:*PIN) & -WRAPPED(*IC:*PIN) & ABOVE(*OLDIC:*OLDPIN) -> {APPRO(*IC:*PIN,*OLDIC:*OLDPIN,*JUSTIFICATION)} ABOVE(*IC:*PIN) & -ABOVE(*OLDIC:*OLDPIN). /*  I f above an unwrapped p i n , t h e n moving t o i t w i l l t h e t o o l t o be a t i t .  cause  V ABOVE(*IC:*PIN) & -WRAPPED(*IC:*PIN) -> { M O V E S ( * I C : * P I N , J U S T I F I C A T I O N ) } AT(*IC:*PIN) & -ABOVE(*IC:*PIN). /*  I f a t an unwrapped p i n , t h e n w r a p p i n g i t w i l l c a u s e a c o n n e c t i o n between i t and any o t h e r wrapped p i n .  V AT(*IC:*PIN) -> { S I G N A L ( 1 , * I C : * P I N , S O L V I N G _ G O A L ( * I C 1 : * P I N 1 , * I C 2 : * P I N 2 ) ) } WRAPPED(*IC:*PIN) & CONNECT(*IC1:*PIN1,*IC2:*PIN2). /* I f a t a p i n , w r a p p i n g i t w i l l c a u s e i t t o be wrapped. */ AT(*IC:*PIN) -> {SIGNAL(1,*IC:*PIN,MOVING_TO_START_CHAIN(*IC:*PIN))} WRAPPED(*IC:*PIN). /* The w i r e may be c u t whenever */ ABOVE(*IC:*PIN) -> {SIGNAL(2,*IC:*PIN)} END_CHAIN(*IC:*PIN). /*  the tool  i s above a p i n .  I f a t a wrapped p i n , d e p a r t i n g w i l l c a u s e t h e t o o l t o be above i t and n o t a t i t . T h i s t e r m i n a t e s a c o n n e c t i o n and t h u s t h e s t a r t t o k e n c a n be a s s e r t e d t o s t a r t t h e n e x t .  */ WRAPPED(*IC:*PIN) & AT(*IC:*PIN) -> {DEPARTS(*IC:*PIN)} ABOVE(*IC:*PIN) & -AT(*IC:*PIN).  C Complete Set of M u l t i w r a p  Rules  95  APPENDIX D  Auxiliary  Predicates  f o r Wire-Wrapping  Problems  0P(:,RL 80). f  BETWEEN(0,*,0) <"/. BETWEEN(*I,*LOW,*HIGH) <-INTEGER(*I) & LE(*LOW,*I) & GE(*HIGH,*I). INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER INTEGER  1) . 2) . 3) . 4) . 5) . 6) . 7) .  8) .  9) . 10) 11 ) 12) 13) 14) 15) 16)  REFERENCE_PIN_SHIFT(*PIN,*N,*DX:38) <-QUOT(*N,2,*HALF) & LE(*PIN,*HALF) & / & PROD(*PIN,25,*DX). REFERENCE_PIN_SHIFT(*PIN,*N,*DX:'-38') <-DIFF(*N,*PIN,*T1) & ADD 1 (*T1 , * T 2 ) D Auxiliary  Predicates  f o r Wire-Wrapping  Problems  96 &  PR0D(*T2,25,*DX).  RELOCATE(*OLDX:*OLDY,*DX:*DY,*NEWX:*NEWY) <-ADD(*OLDX,*DX,*NEWX) & ADD(*OLDY,*DY,*NEWY). CLOSER(*PLAN,*IC1:*PIN1,*IC2:*PIN2,*IC3:*PIN3) <-LOCATE(*PLAN,*IC1:*PIN1,*PINLOC1) & LOCATE(*PLAN,*IC2:*PIN2,*PINLOC2) & LOCATE(*PLAN,*IC3:*PIN3,*PINLOC3) & DISTANCE_SQUARED(*PINLOC1,*PINLOC2,*DIST1) & DISTANCE_SQUARED(*PINLOC1,*PINLOC3,*DIST2) & LT(*DIST1,*DIST2).  LOCATE(*PLAN,*IC:*PIN,*PINLOC) <-TRUE((*PLAN}LOCATION(*IC,*ICLOC) & NO_PINS(*IC,*N)) & REFERENCE_PIN_SHIFT(*PIN,*N,*DISP) & RELOCATE(*ICLOC,*DISP,*PINLOC). DlSTANCE SQUARED(*X1:*Y1,*X2:*Y2,*DIST) <-DIFFl*X1,*X2,*X) & DIFF(*Y1,*Y2,*Y) & PROD(*X,*X,*XX) & PROD(*Y,*Y,*YY) & ADD(*XX,*YY,*DIST).  D Auxiliary  Predicates  f o r Wire-Wrapping  Problems  97  APPENDIX  Trace  PROLOG/MTS 0 . 2 END OF F I L E READ FROM  of Metawrap  E  Problem  metawrap  Given Facts SYMBOLIC O R I G I N ( o r i g i n ) & LOCATIONlSTARTIC,0:0) & LOCATION(IC,1000: 1 0 0 0 ) & NO_PINS(STARTIC,0) & NO_PINS(lC,14) & WRAPPED(STARTIC:0) & ABOVE(STARTIC:0) G o a l t o be S o l v e d CONNECT(STARTIC:0,IC:2) CONNECT(IC:2,IC:1) & CONNECT(IC:1,IC:3)  &  Meta P l a n CHOOSE(START_CONNECTION) Suggests Expansion LEVEL(1) ; START_CONNECTION P r e c o n d i t i o n o f START_CONNECTION LEVEL(0) & DEPTH(0) Plan  holds  Expanded  Meta P l a n LEVEL(1) ; START_CONNECTION Suggests Expansion LEVEL(0) ; SET(*1) E Trace  of Metawrap  Problem  98  Precondition of SET(origin) SYMBOLIC_ORIGIN(origin) Plan  holds  Expanded Meta Plan C H O O S E ( S E Q U E N C E 1 (* 1 ) ) Suggests Expansion LEVEL(1) ; SEQUENCE 1 (* 1 ) P r e c o n d i t i o n o f SEQUENCE 1 ( I C : 2 ) h o l d s PLAN(LEVEL(0);SET(origin)) & GOAL(CONNECT(STARTIC:0,IC:2)) & !TRUE({(LEVEL(0)}ABOVE(STARTIC:0)&WRAPPED(STARTIC:0))) Plan  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE 1 ( I C : 2 ) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,*1) P r e c o n d i t i o n of SHIFT(IC:2,1050:1038) holds VAR_SET_TO_ORIGIN & L0CATI0N(IC,1000:1000) & NO_PINS(lC,14) & !BETWEEN(2,1,14) & -WRAPPED(IC:2) & !REFERENCE_PIN_SHIFT(2,14,50:38) & !RELOCATE(1000:1000,50:38,1050:1038) :  Plan  Expanded Meta Plan CHOOSE(SEQUENCE2(* 1 )) Suggests Expansion LEVEL(1) ; SEQUENCE2(*1) Precondition  o f SEQUENCE2(IC:2) h o l d s E Trace of Metawrap  Problem  99 PLAN(LEVEL(0);SET(origin);SHI FT(IC:2,1050:1038)) Plan  Expanded  Meta Plan LEVEL(1) ; SEQUENCE2(IC:2) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038)  ;  APPR0(IC:2,*1 ) P r e c o n d i t i o n of APPRO(IC:2,STARTIC:0) VAR S E T _ T 0 _ P I N _ L 0 C A T I 0 N ( I C : 2 ) & -•ATTlC:2) & -AB0VE(IC:2) & -•WRAPPED(IC:2) & ABOVE(STARTIC:0) Plan  holds  Expanded Meta Plan CHOOSE(SEQUENCE3(*1)) Suggests Expansion LEVEL(1) ; SEQUENCE3(*1) Precondition Plan  of SEQUENCE3(IC:2)  holds  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE3(IC:2) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) APPRO(IC:2,STARTIC:0)  ; ;  MOVES(IC:2) P r e c o n d i t i o n of MOVES(IC:2) ABOVE(IC:2) &  holds  E Trace  of Metawrap  Problem  100  -WRAPPED(IC:2) Plan  Expanded Meta Plan C H O O S E ( S E Q U E N C E 4 ( * 1 ,*2) ) Suggests Expansion LEVEL(1) ; SEQUENCE4(*1,*2) Precondition  Plan  of SEQUENCE4(STARTIC:0,IC:2) h o l d s  Expanded  Meta P l a n LEVEL(1) ; S E Q U E N C E 4 ( S T A R T I C : 0 ,1C: 2 ) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) APPRO(IC:2,STARTIC:0) MOVES(IC:2) ;  ; ;  SIGNAL(1,STARTIC:0,1C:2) P r e c o n d i t i o n of SIGNAL(1,STARTIC:0,IC:2) h o l d s AT(IC:2) & "•WRAPPED ( I C : 2 ) & WRAPPED(STARTIC:0) Plan  Expanded Meta P l a n CHOOSE(SEQUENCE5(* 1 )) Suggests Expansion LEVEL(1) ; SEQUENCE5(*1) Precondition  Plan Meta  of SEQUENCE5(IC:2)  holds  Expanded  Plan E Trace  of Metawrap  Problem  101 LEVEL(1 ) ; SEQUENCE5(IC:2) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; APPRO(IC:2,STARTIC:0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2)  ;  DEPARTS(IC:2) P r e c o n d i t i o n of DEPARTS(IC:2) WRAPPED(IC:2) & AT(IC:2) Plan  holds  Expanded Meta P l a n CHOOSE(CHAIN) Suggests Expansion LEVEL(1) ; CHAIN Precondition Plan  o f CHAIN  holds  Expanded  Meta P l a n LEVEL(1) CHAIN  ;  Suggests Expansion LEVEL(0) ; SET(origin) ; .. S H I F T ( I C : 2 , 1 0 5 0 : 1 0 3 8 ) ; APPRO(IC:2,STARTIC:0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) DEPARTS(IC:2) ;  ;  SET(*1 ) P r e c o n d i t i o n of SET(origin) SYMBOLIC_ORIGlN(origin) Plan  holds  Expanded E Trace  of Metawrap  Problem  1 02  Meta P l a n C H O O S E ( S E Q U E N C E 1 (* 1 ) ) Suggests Expansion LEVEL(1) ; SEQUENCE 1 ( * 1 ) Precondition  o f SEQUENCE 1 ( I C : 1 )  holds  • ••  Plan  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE 1 ( I C : 1 ) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; APPRO(IC:2,STARTIC:0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) ; DEPARTS(IC:2) ; SET(origin) ; S H I F T d C : 1 ,* 1 ) P r e c o n d i t i o n o f S H I F T d C : 1 , 1 025: 1 038) VAR_SET_TO_ORIGIN & LOCATION(IC,1000:1000) & NO_PINS(lC,14) & !BETWEEN(1,1,14) & -•WRAPPED ( I C : 1 ) & !REFERENCE_PIN_SHIFT(1,14,25:38) & !RELOCATE(1000:1000,25:38,1025:1038) Plan  holds  Expanded Meta P l a n CHOOSE(SEQUENCE2(* 1 )) Suggests Expansion LEVEL(1) ; S E Q U E N C E 2 ( * 1) Precondition  of SEQUENCE2(IC:1)  holds  • ••  E Trace  of Metawrap  Problem  1 03  Plan  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE2(IC:1) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; APPRO(IC:2,STARTIC:0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,1C:2) ; DEPARTS(IC:2) ; SET(origin) ; S H I F T d C : 1 , 1 025: 1 038) ; A P P R O d C : 1 ,*1 ) P r e c o n d i t i o n of APPRO(IC:1,IC:2) h o l d s VAR S E T _ T O _ P I N _ L O C A T I O N ( l C : 1 ) & -AT"ClC:l) & -ABOVE(IC:1) & -WRAPPED(IC:1) & ABOVE(IC:2) Plan  Expanded Meta P l a n CHOOSE(SEQUENCE3(*1)) Suggests Expansion LEVEL(1) ; SEQUENCE3(*1) Precondition Plan  of SEQUENCE3(IC:1)  holds  Expanded  Meta Plan LEVEL(1) ; SEQUENCE3(IC:1) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; A P P R O d C : 2, S T A R T I C : 0) ; E Trace  of Metawrap  Problem  1 04 MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) DEPARTS(IC:2) ; SET(origin) ; SHIFT(IC:1,1025:1038) ; A P P R O d C : 1 ,IC:2)  ;  ;  MOVES(IC: 1 ) P r e c o n d i t i o n of M0VES(IC:1) AB0VE(IC:1) & -WRAPPED d C : 1 ) Plan  holds  Expanded Meta Plan CHOOSE(SEQUENCE4(*1,*2)) Suggests Expansion LEVEL(1) ; S E Q U E N C E 4 ( * 1 , *2) Precondition Plan  of SEQUENCE4(IC:2,IC:1)  holds  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE4(IC:2,IC:1) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; A P P R O d C : 2, S T A R T I C : 0) ; M0VES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) DEPARTS(IC:2) ; SET(origin) ; S H I F T d C : 1 , 1 025: 1 038) ; APPROdC: 1 , IC:2) ; MOVES(IC:1) ;  ; .  .  SIGNAL ( 1 ,I*C:2,IC: 1 ) P r e c o n d i t i o n of SIGNAL(1,IC:2,IC:1) AT(IC:1) & -WRAPPED(IC:1) & WRAPPED(IC:2)  holds  E Trace  of Metawrap  Problem  105  Plan  Expanded Meta Plan CHOOSE(SEQUENCE5(* 1 )) Suggests Expansion LEVEL(1) ; SEQUENCE5(*1) Precondition  Plan  of SEQUENCE5(IC:1)  holds  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE5(IC:1) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; A P P R O d C : 2, S T A R T I C : 0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) DEPARTS(IC:2) ; SET(origin) ; S H I F T d C : 1 , 1025: 1038) ; APPRO(IC:1,IC:2) ; MOVES(IC:1) ; SIGNAL(1,IC:2,IC:1) ;  ;  DEPARTS(IC:1) P r e c o n d i t i o n of DEPARTS(IC:1) WRAPPED(IC:1) & AT(IC:1) Plan  holds  Expanded Meta Plan CHOOSE(CHAIN) Suggests Expansion LEVEL(1) ; CHAIN Precondition  o f CHAIN  holds E Trace  of Metawrap  Problem  106  Plan  Expanded  Meta P l a n LEVEL(1) CHAIN  ;  Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; A P P R O d C : 2, S T A R T I C : 0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) DEPARTS(IC:2) ; SET(origin) ; S H I F T d C : 1 ,1025: 1038) ; APPRO(IC:1,IC:2) ; M0VES(IC:1) ; SIGNAL(1,IC:2,IC:1) ; DEPARTS(IC:1) ;  ;  SET(*1) P r e c o n d i t i o n of SET(origin) SYMBOLIC_ORIGIN(or i g i n ) Plan  holds  Expanded Meta P l a n CHOOSE(SEQUENCE 1 ( * 1 ) ) Suggests Expansion LEVEL(1) ; SEQUENCE 1 (* 1 ) Precondition Plan  o f SEQUENCE 1 ( I C : 3 )  holds  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE 1 ( I C : 3 ) Suggests Expansion LEVEL(0) ; SET(origin) ; S H I F T ( I C : 2 , 1 0 5 0 : 1038)  ; E Trace of Metawrap  Problem  1 07 APPRO(IC:2,STARTIC:0) ; M0VES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) ; DEPARTS(IC:2) ; SET(origin) ; SHIFT(IC:1,1025:1038) ; APPRO(IC:1,IC:2) ; MOVES(IC: 1 ) ; SIGNAL(1,IC:2,IC:1) ; DEPARTS(IC:1 ) ; SET(origin) ; SHIFT(IC:3,*1 ) P r e c o n d i t i o n of SHIFT(IC:3,1075:1038) holds VAR_SET_TO_ORIGIN & LOCATION(lC,1000:1000) & NO_PINS(lC,14) & !BETWEEN(3,1,14) & -WRAPPED(IC:3) & !REFERENCE_PIN_SHIFT(3,14,75:38) & !RELOCATE(1000:1000,75:38,1075:1038) Plan  Expanded Meta P l a n CHOOSE(SEQUENCE2(*1)) Suggests Expansion LEVEL(1) ; SEQUENCE2(*1) Precondition Plan  of SEQUENCE2(IC:3)  holds  Expanded  Meta Plan LEVEL(1) ; SEQUENCE2(IC:3) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; A P P R O d C : 2,STARTIC:0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) ; DEPARTS(IC:2) ; SET(origin) ; E Trace  of Metawrap  Problem  108 S H I F T d C : 1 , 1 0 2 5 : 1 038) ; APPRO(IC:1,IC:2) ; MOVES(IC:1) ; SIGNAL(1,IC:2,IC:1) ; DEPARTS(IC:1) ; SET(origin) ; SHIFT(IC:3,1075:1038) ; APPRO(IC:3,*1  )  P r e c o n d i t i o n of APPROdC: 3 , IC: 1) holds VAR S E T _ T O _ P I N _ L O C A T I O N ( l C : 3 ) & -AT"CIC:3)  &  -ABOVE(lC:3) & -WRAPPED(IC:3) & ABOVE(IC:1) Plan  Expanded Meta P l a n CHOOSE(SEQUENCE3(* 1)) Suggests Expansion LEVEL(1) ; SEQUENCE3(*1 ) Precondition Plan  of SEQUENCE3(IC:3) h o l d s  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE3(IC:3) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; A P P R O d C : 2,STARTIC:0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) DEPARTS(IC:2) ; SET(origin) ; S H I F T d C : 1 , 1 0 2 5 : 1 038) ; A P P R O d C : 1 , I C : 2) ; MOVES(IC:1) ; SIGNAL(1,IC:2,IC:1) ; DEPARTS(IC:1) ; SET(origin) ;  ;  E Trace  of Metawrap  Problem  109 SHIFT(IC:3,1075:1038) APPRO(IC:3,IC:1) ;  ;  MOVES(IC:3) P r e c o n d i t i o n of MOVES(IC:3) AB0VE(IC:3) & -WRAPPED(IC:3) Plan  holds  Expanded Meta Plan C H O O S E ( S E Q U E N C E 4 ( * 1,*2) ) Suggests Expansion LEVEL(1) ; SEQUENCE4(*1,*2) Precondition Plan  of SEQUENCE4(IC:1,IC:3)  holds  Expanded  Meta P l a n LEVEL(1) ; SEQUENCE4(IC:1,IC:3) Suggests Expansion LEVEL(0) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; A P P R O d C : 2, S T A R T I C : 0) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) DEPARTS(IC:2) ; SET(origin) ; S H I F T d C : 1 , 1025: 1038) ; A P P R O d C : 1 , I C : 2) ; M0VES(IC:1) ; SIGNAL(1,IC:2,IC:1) ; DEPARTS(IC:1) ; SET(origin) ; SHIFT(IC:3,1075:1038) ; APPRO(IC:3,IC:1) ; MOVES(IC:3) ;  ;  SIGNAL(1,IC:1,IC:3) P r e c o n d i t i o n of SIGNAL(1,IC:1,IC:3) AT(IC:3) &  holds  E Trace  of Metawrap  Problem  11 0 -WRAPPED(IC:3) WRAPPED(IC: 1) Plan  &  Expanded  S o l u t i o n t o Problem SYMBOLIC O R I G I N ( o r i g i n ) & LOCATIONlSTARTIC,0:0) & LOCATION(IC,1000:1000) & NO_PINS(STARTIC,0) & NO_PINS(lC,14) & WRAPPED(STARTIC:0) & ABOVE(STARTIC:0) -> { L E V E L ( 0 ) ; SET(origin) ; SHIFT(IC:2,1050:1038) ; A P P R O d C : 2, S T A R T I C : 0 ) ; MOVES(IC:2) ; SIGNAL(1,STARTIC:0,IC:2) ; DEPARTS(IC:2) ; SET(origin) ; S H I F T d C : 1 ,1025: 1038) ; A P P R O d C : 1 , I C : 2) ; MOVES(IC:1) ; SIGNAL(1,IC:2,IC:1) ; DEPARTS(IC:1) ; SET(origin) ; S H I F T d C : 3, 1 0 7 5 : 1 0 3 8 ) ; APPRO(IC:3,IC:1) ; MOVES(IC:3) ; SIGNAL(1,IC:1,IC:3) } CONNECT(STARTIC:0,IC:2) & CONNECT(IC:2,IC:1) & CONNECT(IC:1,IC:3). END OF F I L E READ FROM m e t a g o a l E X I T PROLOG/MTS 0.2  E Trace  o f Metawrap  Problem  111  APPENDIX F  Using  R C P S o n MTS  $ S E T ECHO =OFF $COMMENT The f o l l o w i n g f i l e i s u s e d t o b o o t RCPS. $COMMENT There a r e always three f i l e s t o l o a d : $COMMENT 1) R C P S i n t e r p r e t e r $COMMENT 2) u t i l i t y library $COMMENT 3) t r a c e p a c k a g e . $COMMENT The d e f a u l t t r a c e o p t i o n i s 3 a n d t h e t r a c e $COMMENT i s o u t p u t t o SERCOM w h i c h d e f a u l t s t o t h e $COMMENT t e m p o r a r y f i l e -TRACE. The n o r m a l i n t e r p r e t e r $COMMENT I/O i s t h r o u g h SCARDS a n d S P R I N T . $COMMENT $empty - tr a c e $RUN PLOG : p r o l o g s c a r d s = * s o u r c e * s e r c o m = - t r a c e t = 3 p a r = w s = 5 0 $ C O N T I N U E WITH J G I R : r c p s RETURN $ C O N T I N U E WITH J G I R : u t i l s . r c p s RETURN $ C O N T I N U E WITH J G I R : t r a c e . r c p s ( 1 0 3 ) RETURN <-RCPS.  F  U s i n g R C P S o n MTS  112  APPENDIX G  RCPS  /*  Recursively  Interpreter  Controlled Production  System  Version  1.1  This program i s subject t o c o p y r i g h t : The U n i v e r s i t y o f B r i t i s h C o l u m b i a ( c ) J e a n - L o u i s GIRARD J u l y , 1983.  */ /* D e c l a r e PROLOG c o n t r o l */ CONTROL(ATTN, O N ) . /* A t t e n t i o n s a r e t r a p p e d . */ CONTROL(CC, O N ) . /* F i r s t c h a r a c t e r i s c a r r i a g e c o n t r o l . * / C O N T R O L ( N O A X , O F F ) . /* Do n o t p r i n t w a r n i n g o f m i s s i n g a x i o m s . * / /* V /*  */  Operator  The o p e r a t o r s a n d t h i s RCPS l a n g u a g e s y n t a x .  OP( ' - >', 0 P ( ' - >', OP({, OPO, OP(<, OP(>, OP( ; , 0P(?, OP( ! ,  /* */  declarations  RL, PREFIX, PREFIX, RL, PREFIX, RL, LR, SUFFIX, PREFIX,  Error  parsing  precedence defines the  12) 20) 15) 15) 15) 15) 80) 60) 85)  t r a p and  /* Look up g o a l V ERROR <-ANCESTOR(*X,2) & MSG(*X).  that  failed  and c a l l  associated  message.  G RCPS  Interpreter  1 13 /*  Syntax e r r o r i f reading thus, retry input.  from master  source;  */ MSG(READ(*,'*MSOURCE* ' ) ) <-/ /* CR * / & PRINTC «<SYNTAX»> T r y again ' .SKIP(2) ) &RETRY(SOURCE('*MSOURCE*')). /* S y n t a x e r r o r f r o m a s o u r c e f i l e c a n n o t be r e t r i e d . */ MSG(READ(*,*I)) <-/ /* CR * / & PRINTC «<SYNTAX»> on ' . * I . ' ~ A b o r t i n g ' . SKI P ( 2 ) ) & RETRY(SOURCE('*MSOURCE*')). /* General error recovery. */ MSG(*X) < - P R I N T ( ' *** ERROR * * * o c c u r e d & RETRY(SOURCE(*)).  while  deriving  '.*X.SKIP(2))  /* Read-Eval-Print loop V /* Boot message V RCPS <-PRINT('0*** R e c u r s i v e l y C o n t r o l l e d P r o d u c t i o n . ' V e r s i o n 1.1 ***' .SKIP(2)) & SOURCE. /*  Read r e c o r d from i n p u t r e c o r d , and s e l f loop.  unit,  eval  record,  System  pretty  print  V SOURCE <-SOURCE('*MSOURCE*'). SOURCE(*LOGUNIT) <-PRINT('&<-','*MSINK*') & READ O N C E ( * G O A L , * L O G U N I T ) & EVALl*GOAL) & ECHO(*GOAL) & PRINT('.','*MSINK*') & RETRY(SOURCE(*)).  /*  E v a l u a t e argument (i.e. CALL).  using  PROLOG  metavariable  facility  V G RCPS I n t e r p r e t e r  1 14 EVAL(*X) <-*X & /. /* GT  & CR  */  /* S u c c e e d a t SOURCE */ EVAL(SOURCE(*X)) <-/. /* CR * /  EOF.  /* Print goal failed. V EVAL(*X) <-ECHO(*X) & PRINTC FAILED!'.SKIP(2)*MSINK*') & RETRY(SOURCE(*)). /* Pretty print Routines V /* These r o u t i n e s a r e u s e d by t h e t r a c e V ECHO(*X&*Y) <-/ /* CR * / & ECHO(*X) & P R I N T C &'.SKIP(O),'*MSINK*') & ECHO(*Y).  package.  ECHO(*RULE) <-EQUAL(*RULE,*->{*}*) & / /* CR * / & PRINT(SKIP(1),'*MSINK*') & FLUSH(SYMBOL COUNTERC*',*)) & GROUND(*RULE! & PPRULE(*RULE,'*MSINK*' ). ECHO(*X) <-PRINT(SKIP(1).TAB(7).*X.SKIP(0),'*MSINK*'). PPRULE(*X->{*REST;*FIRST}*Y,*OUTUNIT) <-/ /* CR * / & PPCONJUNCT(TAB(7),*X,*OUTUNIT) & PRINT(SKIP(1).TAB(9).'-> { '.SKIP(0),*OUTUNIT) &PPPLAN(TAB(14),*REST;*FIRST,*OUTUNIT) & P R I N T C }',*OUTUNIT) & PPCONJUNCT(TAB(18),*Y,*OUTUNIT). PPRULE(*X->{*ONLY}*Y,*OUTUNIT) <-PPCONJUNCT(TAB(7),*X,*OUTUNIT) & P R I N T ( S K I P ( 1 ) . T A B ( 9 ) . ' - > { '.*ONLY.' & PPCONJUNCT(TAB(18),*Y,*OUTUNIT).  }',*OUTUNIT)  G RCPS  Interpreter  11 5  PPCONJUNCT(*INDENT,*FIRST & *REST,*OUTUNIT) <-/ /* CR * / & PRINT(*INDENT.*FIRST.' &',*OUTUNIT) Sc PPCONJUNCT(*INDENT,*REST,*OUTUNIT). PPCONJUNCT(*INDENT,*ONLY,*OUTUNIT) <-PRINT(*INDENT.*ONLY.SKIP(0),*OUTUNIT). PPPLAN(*INDENT,*REST ; *FIRST,*OUTUNIT) <-/ /* CR * / & PPPLAN(*INDENT,*REST,*OUTUNIT) & PPPLAN1(*INDENT,*FIRST,*OUTUNIT). PPPLAN(*INDENT,*ONLY,*OUTUNIT) <-PRINT(*ONLY.SKIP(0),*OUTUNIT). PPPLAN1(*INDENT,*REST ; *FIRST,*OUTUNIT) <-/ /* CR * / & PRINTC ;'.SKIP(1).*INDENT.SKIP(0),*OUTUNIT) & PPPLAN(*INDENT,*REST ; *FIRST,*OUTUNIT). PPPLAN1(*INDENT,*ONLY,*OUTUNIT) <-PRINT(' ;',SKIP(1).*INDENT.*ONLY.SKIP(0),*OUTUNIT). /* I n t e r p r e t object language V /* RCPS p r o b l e m s t a t e m e n t w i t h o u t p a r t i a l p l a n */ *GIVEN->{*PLAN}*GOAL <-VAR(*PLAN) Sc / /* CR * / & NEXT_LEVEL(*GIVEN,*LEVEL) & TRACE 1 (*LEVEL,*GIVEN,*GOAL) Sc A S S E R T ( { L E V E L ( * L E V E L ) } * G I V E N & P L A N ( L E V E L ( * L E V E L ) , 0 ) ) & PLAN(*LEVEL,*GOAL,*PLAN) & TRACE2(*LEVEL,*GIVEN->{*PLAN}*GOAL). /* RCPS p r o b l e m s t a t e m e n t w i t h p a r t i a l p l a n - i n i t i a l */ *GIVEN->{*REST;*PLAN}*GOAL <-VAR(*PLAN) Sc U S E _ L E V E L ( * R E S T , * L E V E L ) St / /* CR * / & FLUSH(({LEVEL(*LEVEL)}PLAN(*,*))?) Sc TRACE 1 (*LEVEL,*GIVEN, *GOAL) Sc ASSERT ( {LEVEL ( *LEVEL ) } *GI VENScPLAN ( *REST , 0 ) )  call  G RCPS I n t e r p r e t e r  1 16 & PLAN(*LEVEL,*GOAL,*COMPLETE_PLAN) & EXTRACT_PARTIAL_PLAN(*COMPLETE_PLAN,*REST,*PLAN) Sc T R A C E 2 ( * L E V E L , * G I V E N - > { * P L A N } * G 0 A L ) . /* RCPS p r o b l e m s t a t e m e n t w i t h p a r t i a l p l a n - r e c u r s i v e c a l l */ *GIVEN->{*REST;*PLAN}*GOAL <-VAR(*PLAN) Sc / / * CR * / Sc NEXT_LEVEL ( *GI VEN , *LEVEL ) Sc TRACE 1 ( * L E V E L , * G I V E N , *GOAL) Sc ASSERT ( { LEVEL (* LEVEL) } *GI VENScPLAN ( * R E S T ; LEVEL ( *LEVEL) , 0) ) Sc PLAN ( * LEVEL , *GOAL , *COMPLETE_PLAN) Sc EXTRACT_PARTI AL_PLAN ( *COMPLETE_PLAN , *REST, *PLAN) Sc T R A C E 2 ( * L E V E L , * G I V E N - > { * P L A N } * G O A L ) . /* RCPS r u l e s t a t e m e n t */ *ANT->{*ACT}*CON <-ASSERT({RULES}RULE(*ACT)) S< ASSERT (<*ACT>*ANT) Sc ASSERT( (*ACT}*CON) . /*  */  RCPS m e t a f a c t s  statement  ->{*ACT}*FACT  <-ASSERT((*ACT}*FACT).  /* Increment metalevel number. V N E X T L E V E L ( L E V E L (*CURRENT) Sc * , * L E V E L ) <-7 /* CR * / Sc ADD 1 ( *CURRENT , * L E V E L ) Sc F L U S H ( ( { L E V E L ( * L E V E L ) } * ) ? ) . NEXT_LEVEL(*,0) <-FLUSH(({LEVEL(0)}*)?). /* R e t r i e v e l e v e l number f r o m p l a n . */ USE_LEVEL(*;LEVEL(*LEVEL),*LEVEL) <-/. /* CR * / USE_LEVEL(LEVEL(*LEVEL),*LEVEL) <-/. /* CR * / USE_LEVEL(*REST;*FIRST,*LEVEL) <-USE_LEVEL(*REST,*LEVEL).  G RCPS  Interpreter  117  /* E x t r a c t p a r t i a l p l a n from t o t a l and remainder. */ EXTRACT PARTIAL_PLAN(CHOOSE(*ACT),*REST,CHOOSE(*ACT)) <-/. 7* CR * / EXTRACT_PARTIAL_PLAN(*COMPLETE_PLAN,*REST,*PLAN) <-EXTRACT_PARTIAL_PLAN 1 (*COMPLETE_PLAN,*REST,*PLAN). EXTRACT  PARTIAL_PLAN1(*START;*LAST,*START,*LAST) CR * /  <-/. 7*  EXTRACT_PARTIAL_PLAN1(*COMPLETE;*LAST,*START,*REST;*LAST) <-/ /* CR * / &  EXTRACT_PARTIAL_PLAN1(*COMPLETE,*START,*REST).  EXTRACT_PARTIAL_PLAN1(*ONLY,*,*ONLY). /* V i r t u a l Machine V /* Condition for recursivity V PLAN(*LEVEL,*GOAL,*PLAN) <-TRUE({RULES}RULE(*ACT)) & TRUE(<*ACT>*PRECONDITION) & ANY_POS(*PRECONDITION) & TRUE({LEVEL(*LEVEL)}PLAN(*GIVEN,0)) & TRUE({*GIVEN}*PRECONDITION) & / /* GT & CR */ & SOLVE(*GOAL,*LEVEL,*PLAN,0).  /* I f t h e r e i s some r u l e /* w h o s e p r e c o n d i t i o n h a s /* some p o s i t i v e a t o m i c /* a n d i s c u r r e n t l y t r u e /* t h e n , s o l v e g o a l /* r e c u r s i v e l y .  PLAN(*LEVEL,NEXT_RULE(*ACT),CHOOSE(*ACT)) <-TRUE({METAFACTS}CHOOSE(*ACT)).  /* Succeeds i f formula V ANY_POS(*X) <-->NO P O S ( * X ) .  h a s some p o s i t i v e  /* I f no k n o w l e d g e , /* c h o o s e a c t i o n s i n /* o r d e r a s s e r t e d i n /* metafacts. atomic.  NO_POS(*FIRST & *REST) <-/ /* CR * / & NOT_POS(*FIRST) & NO_POS(*REST). NO  POS(*ONLY) G RCPS  Interpreter  1 18 <-NOT P O S ( * O N L Y ) . NOT_POS(-*) <-/. /* CR NOT  */  POS(!*).  /* Main p r o d u c t i o n system logic V SOLVE(*GOAL,*LEVEL,*PLAN,*DEPTH) /* < - T R U E ( { L E V E L ( * L E V E L ) } P L A N ( * P L A N , * D E P T H ) ) /* & TRUE({* PLAN}*GOAL). /* /* /*  I f the goal i s true at the current depth and l e v e l , return plan.  SOLVE(*GOAL,*LEVEL,*PLAN;*ACT,*DEPTH) /* Create given of <-ADD1(*DEPTH,*NEXT) /* c u r r e n t p l a n a n d & T R U E ( { L E V E L ( * L E V E L ) } P L A N ( * P L A N , * D E P T H ) ) /* u n s o l v e d g o a l s a t & GOAL_ASSERTION(*GOAL,*PLAN,*G) /* c u r r e n t l e v e l f o r & ( LEVEL(*LEVEL) & PLAN(*PLAN) /* r e c u r s i v e c o n t r o l & *G & D E P T H ( * D E P T H ) /* c a l l . -> {METAFACTS;RULES;*MP} NEXT_RULE(*ACT) ) & TRACE3(*PLAN;*ACT,*MP,*DEPTH,*LEVEL) & TRUE(<*ACT>*PRECONDITION) /* Does c o n d i t i o n & (TRUE({*PLAN}*PRECONDITION) /* o f s u g g e s t e d r u l e | ( T R A C E 6 ( *ACT , * L E V E L ) & F A I L ) ) /*. h o l d ? & TRACE4(*PRECONDITION,*ACT,*LEVEL) & CONFLICT_RESOLUTION(*ACT,*PLAN,*LEVEL) /* Does i t p a s s c o n & TRACE5(*LEVEL) /* f l i c t resolution? & ASSERT({LEVEL(*LEVEL)}PLAN(*PLAN;*ACT,*NEXT)) & FAIL. /* A p p l y i t by /* e x p a n d i n g p l a n . SOLVE(*GOAL,*LEVEL,*PLAN,*DEPTH) /* FLush p r e v i o u s < - F L U S H ( ( { L E V E L ( * L E V E L ) } P L A N ( * , * D E P T H ) ) ? ) /* l e v e l . & ADD 1 ( * D E P T H , * N E X T ) /* C o n s i d e r n e x t l e v e l & TRUE({LEVEL(*LEVEL)}PLAN(*,*NEXT)) /* Is there a path to & SOLVE(*GOAL,*LEVEL,*PLAN,*NEXT). /* c o n s i d e r ? I n c r e a s e /* d e p t h o f i n f e r e n c e /* Return a s s e r t i o n of a l l untrue g o a l s . */ G O A L _ A S S E R T I ON ( *G&*RESTGOAL , * P L A N , * R E S U L T ) <--TRUE({*PLAN}*G) & / /* CR */ & GOAL A S S E R T I O N 1 ( * R E S T G O A L , * P L A N , G O A L ( * G ) , * R E S U L T ) . G RCPS  Interpreter  11 9 GOAL  <-7 &  ASSERTION(*G&*RESTGOAL,*PLAN,*RESULT) /* CR */ GOAL_ASSERTION(*RESTGOAL,*PLAN,*RESULT).  GOAL_ASSERTION(*G,*PLAN,GOAL(*G)) <--TRUE({*PLAN}*G). GOAL_ASSERTION 1 (*G&*RESTGOAL,*PLAN,*TMP,*RESULT) <--TRUE((*PLAN}*G) & / /* CR * / & G O A L _ A S S E R T I ON 1 ( * R E S T G O A L , * P L A N , GOAL ( *G) 6t*TMP, * R E S U L T ) . GOAL  <-7 &  ASSERTION1(*G&*RESTGOAL,*PLAN,*TMP,*RESULT) /* CR */ GOAL_ASSERTION1(*RESTGOAL,*PLAN,*TMP,*RESULT).  GOAL_ASSERTION1(*G,*PLAN,*TMP,GOAL(*G)&*TMP) <--TRUE({*PLAN}*G) & /. /* CR * / GOAL A S S E R T I O N 1 ( * , * , * R E S U L T , * R E S U L T ) . CONFLICT_RESOLUTION(*ACT,*PLAN,*) <-((*ACT}*FACT)? & -"TRUE( { * P L A N } * F A C T ) & /. /* GT & CR */ CONFLICT_RESOLUTION(*ACT,*PLAN,*LEVEL) <-TRACE7(*ACT,*LEVEL) & FAIL. /* T r u t h Maintenance System V T R U E ( { * A C T S } * F A C T & * R E S T ) /* C o n j u n c t i o n s <-/ /* CR * / & TRUE({*ACTS}*FACT) & TRUE({*ACTS}*REST). T R U E ( { * A C T S } * F A C T | * R E S T ) /* D i s j u n c t i o n s <- / /* CR * / & ( TRUE({*ACTS}*FACT) | TRUE({*ACTS}*REST)). TRUE ( { * A C T S } * F A C T ) <-/ /* CR */ & -TRUE((*ACTS}*FACT). _,  TRUE({*}!*FACT)  /* Negation  */  */  */  /* I n d i r e c t i o n  */ G RCPS  Interpreter  1 20 <-/ /* CR & *FACT.  */  TRUE({*REST;*ACT}*FACT) <-({*ACT}*FACT)?.  /* /*  A t o m i c f a c t made t r u e last action i n plan  by  */ */  TRUE({*REST;*ACT}*FACT) <-/ /* CR * / & TRUE({*REST}*FACT) & NOT(({*ACT}-*FACT)?).  /* /*  A t o m i c f a c t made t r u e b y some o t h e r a c t i o n i n p l a n  */ */  TRUE((*ACT}*FACT) <-/ /* CR * / & ({*ACT}*FACT)?.  /* /*  A t o m i c f a c t made t r u e b y * / last (only) action i n plan*/  TRUE(<*ACT>*FACT) <-(<*ACT>*FACT)?.  /*  Used  ASSERT({*ACT}*FIRST&*REST) <-/ /* CR * / & ASSERT({*ACT}*FIRST) & ASSERT((*ACT}*REST).  /*  Conjunction  */  ASSERT(*FACT) <-NOTINDB((*FACT)?) & / /* CR * / & ADDAX((*FACT)?).  /*  Atomic f a c t  */  to retrieve precondition  */  ASSERT(*FACT). NOTINDB(({*PROBLEM}PLAN(*PLAN,*LEVEL))?) <-/ /* CR * / & -(({*PROBLEM}PLAN(*PLAN,*LEVEL))?). /*  NOTINDB(*FACT) <-AX(*FACT,*AX) & GROUND(*AX) . & EQUAL(*FACT,*AX) & /. */ /*  GT  & CR  */  NOTINDB(*).  G RCPS  Interpreter  121  APPENDIX H  Utilities  /* Ground Argument */ NOT(*X)  f o r RCPS  before  Interpreter  CWA  <-GROUND(*X)  & *X & / / * NF & FAIL.  */  NOT(*X).  /* W i l l r e t u r n i t ' s argument V GROUND(*X) <-VAR(*X) & / / * CR * / & GENSYM('*',*X).  with  a l l variables  GENSYMed  GROUND(*X) <-CONS(*.*ARGS *X) & GROUNDARGS(*ARGS). r  GROUNDARGS(NIL) <-/. / * CR * / GROUNDARGS(*FIRST.*REST) <-GROUND(*FIRST) & GROUNDARGS(*REST).  /* Generate a unique symbol and r e t u r n */ GENSYM(*NAME,*UNIQUE) <-NEXT SYMBOL(*NAME,*NEW)  bound  t o argument  Sc ADD 1 T*NEW, * N E X T ) & &  UPDATE(SYMBOL_COUNTER(*NAME,*NEW), SYMBOL_COUNTER(*NAME,*NEXT)) CONCATENATE(*NAME,*NEW,*UNIQUE). H Utilities  f o r RCPS  Interpreter  1 22  NEXT_SYMBOL(*NAME,*NEW) <-SYMBOL_COUNTER(*NAME,*NEW) & /. /* CR * / NEXT_SYMBOL(*NAME,1) <-ADDAX(SYMBOL C O U N T E R ( * N A M E , 1 ) ) . /* C o n c a t e n a t e two f i r s t s t r i n g s a n d r e t u r n V CONCATENATE(*ID 1 ,*ID2,*ID1ID2) <-STRING(*ID1,*ID1LIST) & STRING(*ID2,*ID2LIST) & COMBINE(*ID1LIST,*ID2LIST,*ID1ID2LIST) & STRING(*ID1ID2,*ID1ID2LIST).  in third  COMBINE(*FIRST.NIL,*X,*FIRST.*X) <-/. /* CR * / COMBINE(*FIRST.*REST,*X,*Y) < - C O M B I N E ( * R E S T , * X , * Z) & COMBINE(*FIRST.NIL,*Z,*Y). /* Adds 1 t o f i r s t */ ADD1(*X,*Y) <-SUM(*X,1,*Y). /* S u b t r a c t s 1 from */ SUB 1 (*X,*Y) <-DIFF(*X,1,*Y).  argument  first  and return  argument  /* P r i n t l i s t of s t r i n g s , skipping V PRINT(*L) <-PRINT(*L,'*SINK*').  i n second  and r e t u r n  lines  i n second  as s p e c i f i e d  PRINT(*VAR,*OUTUNIT) <-VAR(*VAR) & / /* CR * / & WRITECH(*VAR,*OUTUNIT) & NEWLINE(*OUTUNIT).  H Utilities  f o r RCPS  Interpreter  123 PRINT(*VAR.*REST,*OUTUNIT) <-VAR(*VAR) & / /* CR * / & WRITECH(*VAR,*OUTUNIT) & PRINT(*REST,*OUTUNIT). PRINT(SKIP(*S).*REST,*OUTUNIT) <-/ /* CR * / & SKIP(*S,*OUTUNIT) & PRINT(*REST,*OUTUNIT). PRINT(TAB(*N).*REST,*OUTUNIT) <-/ /* CR * / & TAB(*N,*OUTUNIT) & PRINT(*REST,*OUTUNIT). PRINT(*FIRST.*REST,*OUTUNIT) <-/ /* CR * / & WRITECH(*FIRST,*OUTUNIT) & PRINT(*REST,*OUTUNIT). PRINT(SKIP(*S),*OUTUNIT) <-/ /* CR * / & SKIP(*S,*OUTUNIT). PRINT(TAB(*N),*OUTUNIT) <-/ /* CR */ & TAB(*N,*OUTUNIT) & NEWLINE(*OUTUNIT). PRINT(*ONLY,*OUTUNIT) <-WRITECH(*ONLY,*OUTUNIT) & NEWLINE(*OUTUNIT). SKIP(0,*) <-/. /* CR  */  SKIP(*S,*OUTUNIT) <-NEWLINE(*OUTUNIT) & SUB 1 (*S,*T) & SKIP(*T,*OUTUNIT). TAB(0,*) <-/. /* CR  */  TAB(*N,*OUTUNIT) <-WRITECH(' ',*OUTUNIT) & SUB 1 (*N,*T) & TAB(*T,*OUTUNIT). H Utilities  f o r RCPS  Interpreter  1 24  /*  V  Clear  database of a l laxioms  that  match  FLUSH(*X) <-AX(*X,*X) & DELAX(*X) & FAIL. FLUSH(*). EQUAL(*X,*X). UPDATE(*X,*Y) <-DELAX(*X) & ADDAX(*Y). REPEAT. REPEAT <-REPEAT. /*  Reads  that  don't  leave  choice  points  */ READCH_ONCE(*X,*0) <-READCH(*X,*0) & /. /* GT * / READ_ONCE(*X,*0) <-READ(*X,*0) & /. /* GT * / /*  V  Prompts  a n d s u c c e e d s on an a f f i r m a t i v e  answer  YESNO <-READ_ONCE( *R, '*MSOURCE* ' ) & AFFIRMATIVE(*R) & /. /* GT * / AFFIRMATIVE(yes). AFFIRMATIVE(YES). AFFIRMATIVE(Yes). AFFIRMATIVE(Y). AFFIRMATIVE(y). H Utilities  f o r RCPS  Interpreter  1 25  AFFIRMATIVE(OK). AFFIRMATIVE(ok).  /* */  Circumvents  a p r o b l e m w i t h MTS PROLOG  A D D ( * X , * Y , * Z )  <-DIFF(0,*Y,*Y1) Sc  D I F F ( * X , * Y 1 , * Z ) .  SPY(*P) <-GEN_SPY_AX(*P,*A) Sc (AX(*P,*A) Sc PRINT(' T h e r e i s a l r e a d y a spy p o i n t on '.*P,SERCOM) | (ADDAX(*A,1) Sc P R I N T C Spy p o i n t e s t a b l i s h e d on ' . *P, SERCOM))) & /• NOSPY(*P) <-GEN_SPY_AX(*P,*A) Sc (DELAX ( *A) Sc PRINT(' Spy p o i n t removed f r o m '.*P,SERCOM) | PRINT(' T h e r e i s no s p y p o i n t on '.*P,SERCOM)) & /• GEN SPY A X ( * P , * P < - " ' A N C E S T O R ( B U G ( * , * ) , 4 ) Sc/ScBUG ( *P , * I ) ) . BUG(*P,*I ) <-INDENT(*l) Sc STRING(*S, *I ) Sc P R I N T ( * S . ' E n t e r i n g '.*P,SERCOM) S< (*P | ( P R I N T ( * S . ' F a i l e d '.*P,SERCOM) S< F A I L ) ) Sc ( P R I N T ( * S . ' E x i t i n g '.*P,SERCOM) | (PRINT(*S.'Redo '.*P,SERCOM) S< F A I L ) ) . INDENT(' ' .*I ) <-ANCESTOR(BUG(*,*I),*X) Sc GT(*X,2) & /. INDENT( ' ' . N I L ) .  H Utilities  f o r RCPS  Interpreter  126 MAP(*P,*F.*R)  <-/ & & &  CONS(*P.*-F.NIL,*X) *X MAP(*P,*R).  MAP(*P,*0) <-CONS(*P.*O.NIL,*X) & *X.  sig  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051845/manifest

Comment

Related Items