UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Robot simulation studies Rowat, Peter Forbes 1972

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

Item Metadata

Download

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

Full Text

(i) !  Robot  Simulation  Studies  b.Y  Peter  F*  Howat,  B.A.,Cantab.,1963.  A thesis the  submitted  in  requirements  Master  in  the  for  of  accept  this  thesis  required  THE  UNIVERSITY  the  OF  MARCH  fulfilment degree  of  of  Science  department  Computer  We  partial  of  Science.  as  conforming tc  standard  BRITISH 1972.  COLUMBIA  the  In presenting this thesis i n p a r t i a l fulfilment of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library shall make i t freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the Head of my Department or by his representatives.  It i s understood that copying or publication  of this thesis for financial gain shall not be allowed without my written permission.  Department The University of B r i t i s h Columbia Vancouver 8, Canada  Date  X  (ii)  For  t h o s e who s u s t a i n e d in time of need:  me  EJ, N i c k o , Mickey, Mike, A l i s t a i r , and t h e w i l d mountainous p l a c e s .  "The  best-laid  schemes  o' m i c e a n * men Gang a f t a g l e } " Robert  Burns.  (iii)  Abstract  The  history  o f t h e r o b o t as a concept  indicated,  and  the  discussed.  The  problem  approached  by t a k i n g  a  t o move a r o u n d  manner.  execution  the  problem  dealt  which fixed  of plans  a  fact  i s  to robotology  robot-controller  programs  with  to  i s  enable  i n a reasonably  representation  are dealt  of exploration  approach  a  c o m p u t e r - s i m u l a t e d , model o f  i t s environment of concept  as  i n this  i s encountered  the  intelligent  and the c r e a t i o n  simple  s y s t e m , and  but not s a t i s f a c t o r i l y  with..  The  robots'  squares  a  surrounding  belonging  square,  can  sense  The boundary  the  the l a b e l s  house.  After  an  which  environment  called produces  (i.e.  initial i s  as  the  views  t h e maximal  and  drop  i s thus a of  exploration  the basic  a  of  sequence  within  subrectangles  An  edge-  algorithm  subrectangles  rooms, p a s s a g e s , doorways) f o r moving  itself  to the floor-plan  t h e s e t of maximal  T o make p l a n s  i n  of the eight  move,  the ring-representaticn.  representation.  robot  environment  c a n be compared  of t h e environment  and t u r n s ,  robot f i r s t  of a t y p i c a l  grid  to the boundary, t o  objects, or t o holes, while  p o l y g o n , which  representation  described  as  of a rectangular  s q u a r e s , can t u r n , and can p i c k u p ,  one-level  lengths  consists  labelled  single  movable o b j e c t s . rectanguloid  environment are  o r movable  occupies  the  designing  a simplified,  The p r o b l e m s  and  is  of  linguistic  r o b o t i n an e n v i r o n m e n t , and w r i t i n g  robot  a  current  and  from  of  the ring  the environment, as t h e  vertices  (iv)  of a graph, wherein two v e r t i c e s are connected by an edge i f and only  i f the corresponding  maximal subrectangles overlap, and  then uses a path-finding algorithm t o f i n d a  path  between  two  v e r t i c e s of the graph. This path c o n s t i t u t e s a "plan of a c t i o n " . Whenever  an i s o l a t e d  object  or hole i s found, i t s r i n g -  representation i s generated and i t s set of maximal subrectangles produced. Thus the shapes environment  of objects  and holes  can be compared i n various ways. In p a r t i c u l a r , an  algorithm i s described which compares the shape object  w i t h i n the  with  that  of a  movable  of a hole to a s c e r t a i n i f the movable object  could be moved to f i t i n s i d e  the hole  without  "physically"  moving the object. . BOSS  , an i n t e r a c t i v e computer program which simulates the  robot-environment model, i s described. A command language allows the user to s p e c i f y tasks f o r the robot  at various  conceptual  levels. Several robot might  problems are l i s t e d concerning explore,  represent,  and make  the ways i n which a plans  about, i t s  environment, most of which are amenable to d i r e c t attack i n t h i s s i m p l i f i e d model. F i n a l l y , t h e o r e t i c a l questions concerning twodimensional rectanguloid shapes are r a i s e d .  (v)  Table  of contents  Introduction Chapter  1  1 - P r e a m b l e on r o b o t i c s and a r t i f i c i a l  intelligence  1.1  History of the robot  1.2  Robots i n f a c t  4  1.3  An e s s a y  6  Chapter  concept  2  on r o b o t r e s e a r c h  1.3.1  Importance to a r t i f i c i a l  1.3.2  Philosophy  1.3.3  Goals  2 - Design  intelligence  6 7 11  of the simulated  robot  2.1  B a s i c approach  13  2.2  The s i m u l a t e d w o r l d  16  2.3  Robbie's  17  model o f t h e w o r l d  2.3.1  The r i n g  r e p r e s e n t a t i o n of o b j e c t s  17  2.3.2  M a x i m a l s u b r e c t a n g l e s : t h e a l g o r i t h m DECOMP  19  2.3.3  Containment:the  22  2.3.4  P l a n s : t h e i r c o n s t r u c t i o n and e x e c u t i o n  2.4  Exploration  2.5  Summary o f R o b b i e ' s  Chapter 3.1  3.2 Chapter  a l g o r i t h m CONTAIN  25 29  world  31  3 - ROSS: a r o b o t s i m u l a t i o n s y s t e m How t o u s e  33  3.1.1  General  3.1.2  Commands  35  3.1.3  Summary o f ROSS commands  50  3.1.4  Sample o u t p u t  52  Implementation 4 - Conclusion  description  33  63  (vi)  4.1  Summary  65  4.2  Directions  for  further  work  65  4.2.1  Preamble  66  4.2.2  Design  66  4.2.3  ROSS  70  Bibliography  71  Appendices A  Detailed  B  Plans  and  description models o f  of the  the  algorithm  world  DECOMP  77 83  (vii)  list  of  figures  following  page  16  Figure  1  Figure  2  16  Figure  3  18  Figure  4  18  Figure  5  18  Figure  6  19  Figure  7  19  Figure  8  19  Figure  9  21  Figure  10  22  Figure  11  23  Figure  12  25  Figure  13  25  Figure  14  26  Figure  15  26  Figure  16  28  Figure  17  77  Figure  18  78  Figure  19  78  (viii)  3±i.§t o f  Zi£§i  snapshots  episode  Snap  #4  Snap  #6  S na. p  following  page  53 53  #13  54  Snap  #23  54  Snap  #27  54  Snap  #30  54  Snap  #32  56  Snap  #34  57  Second Snap  #8  episode 58  (ix)  I his  am  greatly  excellent I  thank  financial their  I' itself,  for  executed  also i t was  the  FORMAT  program  the  extensively  for  Only t h r o u g h  my  supervisor,  for  Council  for providing  me  was  preparation,  through  in  used  to  to t h i s  described was  the  and  here,  alter  t h a n k s go inspiring  t h e s i s here  to me now.  360/67 c o m p u t e r  in  and  and  format,  and  System  thesis  prepared  revise  deepest  i s this  with  67-7642.  controlled  supporting her  thesis  essential  thesis  Above a l l , my life,  Rosenberg,  a c k n o w l e d g e UBC's IBM  programs  which  Research  while the  67-5552 and  through  was  National  support  must  to Dr.  guidance. the  grants  indebted  two  i t was  typed.  and  the  the  text.  Nona,  MTS  my  ways. the  Bill  medium Webb's  file  editor  partner  in a multitude  It  of  in  ways.  Robot Simulation Studies  1  IB i n d u c t i o n  This t h e s i s i s an attempt at formulating logical  a  solving  the  problems involved i n the design of a robot, or i n other  words we try to face the question "How of  and  robot?".  the  brain  Our approach i s to simulate an extremely  simple  robot-environment system by means cf programs  of  do you design  a  computer,  and  develop  the  simplest  sort which w i l l enable the robot to  execute elementary  tasks i n  i t s environment  i n t e l l i g e n t manner. I t may the  engineering  in  such  reasonably  well be the case that i n a r e a l robot  problems of f a b r i c a t i o n and c o n t r o l w i l l cause  f u r t h e r l o g i c a l problems to a r i s e , but since we foresee  a  problems  short  are  unable  to  of b u i l d i n g a p h y s i c a l robot, we  ignore t h i s p o s s i b i l i t y . The f i r s t three chapters can each independently.  Chapter  1  is  a  be  brief  read but  r o b o t i c s and a r t i f i c i a l i n t e l l i g e n c e . Chapter design  of  a  simulated  robot,  computer  program  which  implements  or  less  general survey of 2  i t s simulated  robot's conceptual world, while chapter 3  more  considers  the  world, and the  describes  a  running  the design of chapter 2. A  b r i e f summary i n chapter 4 i s followed by  a  list  of  brought to l i g h t by the work described i n chapters 2 and  problems 3.  Robot  Simulation  Chapter  P r e a m b l e on  1.1  History of  The times.  concept  most  pregnant  fantasies  together Western  but  language  by  by  word  theory  occur  in  Vulcan  to  obtain  was  technology  abysm  Babbage,  ...  also  of  of  the and  time,  [and]  with  t r a c e the the  introduced  to  R.  1920.  U.  R»  fiction  required  i n the  places  in  the  tc  i n Greek  forged  armour  and  of  of  Swiss  English  "Robotics"  writing  build  scientific  a  joins  history  automata  [As]  robots,  literature.  mythology.  Book X V I I I , T h e t i s v i s i t s  divinely  one  an  technology  ...  i n his science  several  ancient  deserves  between  and  dark  Droz [ C h ]  appears  since  China,India,Persia,Egypt,  in his play  e x a m p l e , i n Homer's I l i a d , god  with  us  "automaton  science  concerned  now  with  continuity  Homer  "robot"  and  concept  [Co,p.7],  i n the  and  intelligence  been  birth  Asimov  "robotology"  has  works of  mainly  Isaac  robot  modern  their  K a r e l Capek  the  Robots  of  Chapuis  The  coined denote  says  links  are  artificial  robot  imaginative  clock-makers.  although  had  the  2  J  is]...some  concepts  Europe."  robots,  Cohen  which  the  a  [There  which  continuity  to  of  I n d e e d , as  encyclopaedia.  was  r o b o t i c s and  Studies  the  for  For  smithher  son,  Robot Simulation Studies  Achilles,  The lame V u l c a n  3  comes o u t t o meet T h e t i s , "beside  while  their lord, [ mov *d n i m b l y Pages i n f i n e - w r o u g h t g o l d , i n form l i k e unto l i v i n g maidens; Which have w i t h i n t h e i r h e a r t a mind, a v o i c e w i t h i n t h e i r bosom. And s t r e n g t h ; a n d c a n n y s e r v i c e know by g i f t s o f g o d s i m m o r t a l . These d i d t h e i r t a s k s f u l f i l , , . . " [ T r a n s l a t i o n b y W.J.Newman.] In  short,  they  were  robots.  A most s t r i k i n g  tale  makes  i t clear  idea  o f a man-made r o b o t  involve  t h a t even  inanimate  European  middle  clay  o r wooden images  plot  created this, had  1. 2. 3.  into  them  any r o b o t  i n China. animate  [Ne1,p„53]  century  Many C h i n e s e [G,Sh,L]1.  stories  tale  destroyed  and  up  of robots  their  which  to  In  the to  involved  1940, t h e  was: r o b o t s  creator.  science fiction  injuring  myths  springing  were  In reaction to  i n which  the robots  t h e "Three Laws o f R o b o t i c s " , which  from  B.C. t h e  animate.  Frankenstein,  to write  Needham  as the third  o f t h e Golem  f o ra science f i c t i o n  began  by Joseph  o f a man-made i m a g e  becoming  Mary S h e l l e y ' s  Asimov  prevent  was k n o w n  i n view  and s u b s e q u e n t l y  built  as e a r l y  ages, the idea  was w e l l - k n o w n ,  usual  recounted  o b j e c t s becoming  life  Since  and around  a human b e i n g . T h e s e  were  to  laws a r e :  A r o b o t may n o t i n j u r e a human b e i n g , o r , t h r o u g h inaction, a l l o w a human b e i n g t o come t o h a r m . A r o b o t m u s t o b e y t h e o r d e r s g i v e n i t by h u m a n b e i n g s e x c e p t , where s u c h o r d e r s would c o n f l i c t w i t h t h e F i r s t Law. A r o b o t m u s t p r o t e c t i t s own existence as long as such p r o t e c t i o n d o e s n o t c o n f l i c t w i t h t h e F i r s t c r S e c o n d Law,.  With  these  as  a basis,  Asimov  has w r i t t e n  many a t a l e o f  *. I cannot r e f r a i n from m e n t i o n i n g t h e s t r a n g e tale from Liao dynasty [A.D. 900-1169], wherein [ G , L ] " a n i m a g e o f a d e a d man may b e c o m e t h i s man h i m s e l f , so c o m p l e t e l y even t h a t he c a n f e c u n d a t e h i s l i v i n g widow" .  the  Robot S i m u l a t i o n  robots. the  I t i s interesting  Three Laws, robots  benevolent contrast  to note  in  creatures  to the malevolent  science  as  i n  robots  the  returned  myths  to  of  being  cf antiquity, i n  of Frankenstein  and  pre-1940  Robots i n f a c t  It built.  will  always  There  be d i f f i c u l t  have been  statues  a hidden  the  a g e s [ C h , C o ] ; and a l t h o u g h  projects ever  existence  has e x i s t e d , or  mechanical  maze  Thomas  Ross  Walter  ([W], 1953).  mechanical are  with  the  reasonably  which  been  could  built  (1938), R.A.Wallace  Grey  exploratory  Each of  tortoise  behaviour  Walter's  machine  behaviour,  environment toys  genus robcto)  real  compares  i t could  have  aspects  The  move a n d t a l k  by  models  now  [ P o 1, N i 1, H , Su ] , n o r e a l  tortoises  a  ingenious  there  robot  robots  be s a i d  means  through  several robot  was  robot  e x i s t s , or of  science  t h a t " i t was a  man".  solve  means.  which  of which  Mechanical  certain  could  p r i e s t , p u p p e t s , a n d many  in  fiction  t o s a y when t h e f i r s t  that  of  not  fiction  the introduction  fiction.  1.2  its  t h a t , with  science  just  4  Studies  and s e l f -  wander  b y many  arcund  people;  (1952), Claude was b u i l t could  to  no f u r t h e r ,  and  or  include  demonstrate  that  by  mechanical  for  instance,  interaction  and m u t u a l - r e c o g n i t i o n .  were d e v e l o p e d  these  be r e a l i z e d  and n e g a t i v e  floor  S h a n n o n , and G r e y  demonstrated,  positive  a  However,  the  with these  species  (of  on t h e s c e n e  were  died out.  members o f t h e n e x t machines  at  species  a l l : they  to appear were  computer  simulations  !  Robot S i m u l a t i o n  Friedman  [Fr1,Fr2],  simulation sensory  psychologist,  of i n s t i n c t i v e  and motor  population purpose  a  of organisms of  behaviour  systems.  Uhr  explicating  the  around  capabilities.  Doran [D1,D2] s i m u l a t e d some  rudimentary  elementary  p l a n n i n g and g e n e r a l i s a t i o n .  closest  is  i t intended  rather  the  Nilsson  simulation  might  called  "Shakey"  software  to  h a s been  use  in  University  the  built  robot  system  that  [ A i ] . The p a p e r s  International  that  the  capable  system  i n  an  a  of  i s the case  simulation,  heuristic  hardware  a t S,. R . I . ,  with  [ K ] , Edinburgh  [ F e 2 , Mc 1 ,Mc3 , S c ] ,  recognition  Doran's  [ N i l ]carried  mobile  but  processes are  effective  robot  cut a very  simple  real  robot  robots. A mobile although  at  robot  currently i t s  Joint  presented Conference  simple  [Pc1,Po2],  A combined  uses  surroundings  of a mechanical  r e c e p t o r s that can manipulate  Japan  i n  ( S.R.I ) .  [ B a 2 ] . Systems c o n s i s t i n g  tactile  pattern  r e c o n s t r u c t e d [ F i 1 , F i 2 , M u 1 , M u 2 , N i 1 , N i 2 , R 1 ] . At  a stationary  or  Italy  be c o m b i n e d  Institute  come  i s being  Edinburgh used  we  of  was a l s o  as a p r e l i m i n a r y t o b u i l d i n g  Stanford Research  Finally  and  o f what  and Raphael  a  with the  own. F o r i n s t a n c e , i n n e i t h e r  an i n v e s t i g a t i o n they  simulated  need-satisfaction  t h a t t h e work be a s e r i o u s r o b o t  n e e d e d , a n d how  robot  t o my  with  a r a t i n i t s surroundings  pleasure-seeking,  i n spirit  i t i s  controller.  and  intelligence  rat  computer  an e n v i r o n m e n t  formation,  simulated  one  was  [U ]  inter-relationships  hypothesis  displayed  a  an a u t o m a t o n  Kochen  recognition,  which  described  involving  and  wandering  5  Studies  hand  has plus  objects  been visual  are  i n  M.I.T., and S t a n f o r d  visual-tactile  pattern  a mechanical  arm i s p r o p o s e d i n  i n  8  Session  on A r t i f i c i a l  cf  the  Second  Intelligence [Se]  Robot S i m u l a t i o n  give the  a good  description of the current  general  navigate the  across  way,  while  current  and  push  various  centers  system  to  to solve  [E,Po2]  recognition  of everyday  polyhedra, attempts  at the assembling  Why  i s  intelligence problems  ?  problem-solving, retrieval, another,  problem  on r o b o t  with  each  puzzle.  research i n  hand-eye  (-touch)  i t s constituent the  parts.  problem  However, t h e a r t o f to nice  of visual  clean  simple  a n d i t may b e t h a t t h e  intelligence  important  to  from  uniform  manner,  dealing  with  other.  For  difficult,  artificial  i n any w o r k i n g  i n isolation  pattern-recognition,  problems  manipulate  research  research  t h e programs  i n  are premature.  language understanding,  several  from  a  could  position,  can  Insanity"  state [Ba1],  i n a reasonably  minimum,  communicate  whole  F o r one t h i n g , b e c a u s e  now b e c o n s i d e r e d  system  using  engine.  previously considered  very  of  to a r t i f i c i a l  robot  to a specified  [Po2] considers  i s i n a primitive  Importance  object  o b j e c t s , as opposed  An e s s a y  1.3.1  can  i s that  idea of  "objects  problems c u r r e n t l y guiding  model a i r c r a f t  1.3  plane-faced  the "Instant  Popplestone  a  (197 1 ) . Some  f o l l o w s : "Shakey"  hand-eye  assemble a complex  example,  several  a specified  assembling  the  having  o f t h e paradigm  work  o f performance  University  w e l l enough  One  For  a floor  the Stanford  blocks  level  6  Studies  each  many  other  must  so  that,  separate  instance,  etc., are a l l  storage  required.  artificial,  at  problems  programs  information  or very  robot  for and For  to deal  Robot S i m u l a t i o n  with  in  isolation  must  be  squarely  problem  of building  { this  also  problem  o f a u n i v e r s a l and b e s t  the  problem  also  an a d e q u a t e  assists  greatly  namely, r e a l  because  inputs  of  from  uncertainties  and c o n c u r r e n t  the  formal  precise  theorem  provers.  organising  a  complex  robot  every  research  problem  relevant  to  there  t a c k l e d by w o r k e r s  robot  all  intelligence.  1.3.2  ) ,the  world,  with  further  research  the  for  a l l their  instance,  i n  problem  of  sheer  ...  The  i sthe  importance  i n [R2 ] . S i n c e  i n artificial  c a n be  used;  problems, as opposed t o  used,  i s  being  i s  virtually  intelligence  robot,  we s h o u l d  considered  to  i s note  include  Philosophy.  In science to  machine  research  o f the data  of the ultimate  that, conversely, of a r t i f i c i a l  the  understanding  on e v e r y t h i n g . " [ F e 1 ] ,  design  include the  ; "The main p r i n c i p l e  i s expounded  the  nature  external  system  into  p l a n s . Robot  ill-defined  Finally,  These  r e p r e s e n t a t i o n o f knowledge, and  representations  dependence o f e v e r y t h i n g of  i n language  the  the  faced.  world-model  o f c r e a t i n g and e x e c u t i n g  valuable  7  Studies  robot  research,  despite  which  the efforts  which  behaviour.  The u s e f u l n e s s behaviour  behaviour  of other  as  c o n s i s t s of running  i n  either similar  of the idea with  human  a  theoretical  HewittfHe] a  i m p l e m e n t s o n e s ' i d e a , and o b s e r v i n g  resultant  Just  be c a l l e d  of Hayes[Ha1],  make i t s o , a n e x p e r i m e n t  robot)  cannot  i s judged  and  others  program  (or  the resultant  by c o m p a r i n g t h e  behaviour  or  with  the  programs, i f any.  artificial  intelligence  as a whole, t h e r e a r e  Robot S i m u l a t i o n  three  common  briefly, brain as  approaches  one  human  to the setting  i s to t r y to simulate  and body, a n o t h e r  developed  i n various  physiology  robot  approach  Warren  However, i n view  expect  hardware  robot  a  attack  direct  used  i n my  attitudes. recently the  p r o j e c t s have  the t h i r d ,  reduced  t o some  approach  taken  direct,  taken  n on- U n g u i s t i c  i s the approach  I have  Note  there  that and  t o propose a t h e s i s : that  I  do  following  observations,  t o which  language  making  a r e two o p p o s i n g attitude,  most  and t h e o t h e r i s  stated  by  everything this  i s  Sloman must  indeed  be  the  P r o j e c t [ F i 2 ].  reasoning.  were  A l l other  approach, of  explicitly  maintain  of l i n g u i s t i c  There  the third  formalism,  by t h e S . R . I .  .  concepts. o f how t h e  approach.  and Hayes[Mc2],  existence  1)  this  or l i n g u i s t i c  attitude  Hayes  logical  However, I wish  on t h e  physiological  physiological  approach,  by M c C a r t h y  and  the  of understanding  with  One i s t h e f o r m a l i s t i c  McCarthy  attack  about  robot.  non-formal, i n t u i t i v e  [Si].  i s to forget  takes  on t h e p r o b l e m s , and t h a t  expounded  psychology  b y D o r a n [ D ] h a s a b i b l i o g r a p h y ) , we  successes  simulated  Within  lack  Very  o f t h e human  human  a n d make a d i r e c t  Mcculloch's  of the current  great  experiments.  the physiology  project [Su]  functions {the review  cannot  up o f  t h e o r i e s , and a t h i r d  and psychology  using  8  i s to t r y to simulate  p r o b l e m s . T h e NASA  brain  Studies  intelligent  n o t deny  The t h e s i s  I hope  beings  was u s e d , a n d t h e r e  reasoning  are  the importance or i s  the reader  long many  i s basically,  based will  before  on  the  assent.  any  intelligent  Robot  creatures  that  language. For are  2)  A  human do  cannot  speak  yet.  experience: t o go  i s  used  things), ideas.  According  to  many g i f t e d intuitive  to  a  program "We  (dolphins  not  store  plan  though  reason v e r b a l l y for a  f o r communicating for  "The  reasoning  are  stems  only  way  i s i n language. That  we  our g o a l s ,  perform."  do  even  i t  when  newspaper,  ideas  (amongst  about  or  for  mental processes of apparently  from  f o r the Advice Taker  system  that  actions,  approach  which  believe that  fact  situation, can  horses  human  highly  non-linguistic.  s t a t e s [ Mc4,p.406 ] :  the  to  months can c l e a r l y  mathematicians  proposal  (...)  18  Hadamard[Hd ] , t h e  and  abstractions  we  not  linguistic  influential  on  similar  furniture.  creating  states:  and  to the corner  moving  Language  The  of only  intelligent  when  other  5)  language  dogs  some  planning  4)  instance,  infant  Everyday  or  p o s s e s s no  9  Studies  too c o n t r o v e r s i a l ) .  and  3)  Simulation  and  program,  we  know  i s why  in  we  represent  i n language  the e f f e c t s of v a r i o u s  he  expressing  have  depends  highly  which  of  reasons verbally." Later  human i n t e l l i g e n c e  can  McCarthy's  decided  [p.410]  he  essentially  f a c t s about actions  that  our we  Robot  I  do  not  wish  to  Advice  Taker  program  which  one,  Carl  m o d e l s and  merely to  of  wish  My fact not  first  that  has  we  out  closely  in  to  express  As shall  to  McCarthy  that  we  that our  done  sericusly. computer,  ( In  obsessive ].  papers  we  go  into  However, i f  i t of  concern  reason  is that with  many p r o j e c t s  of  are  of  are  our  here, airy at  why  with  go  form  and  in  of  Minsky  formalism  in  way  Take  to c l a i m  that using  reasoning  etc)  a  at a l l  them.  read,  The does  c r e a t i n g and  to  I  devoted  known; and  non-linguistic  should  elegant,  approach.  cf  f a r as  symbol  implementation a l l  be  them i n a  so  variety i t  projects.  abstractions  "syntactic  a  most  ncn-sequitur.  manipulation  simply  the  abstractions verbally  formal,  are  a  intuitive  words, the  manipulating  should  difficult  symbol  there  for  expressions  would  to r e s o r t to  ideas  the  amongst  like  represent  form  Strachey's  their  in fact  intelligence  mathematicians  highest  their  our  verbal  definitions,  formalisation  [Hn2  by  for formalism, not  is  more a t t e n t i o n  to express  or  mathematicians have  themselves.  robots,  artificial that  from  able  i s the  (eguations,  to  reads  are  why  godfather  guote  related  is  proposal;  approaches.  reasoning  that  10  even i n t r o s p e c t i v e ,  manner  mathematics  McCarthy's  the  mathematicians, for instance. I the  Studies  PLANNER language}" He]  to-day's  necessarily imply  linguistic  been  theorems  to point  intuitive,  denigrate  Hewitt's  proving  significant  Simulation  why  methods  to  express  manipulations  used  sugaring".)  reasons, net  of should  an be  be  which taken  I too  approach regarded  inveighs i n computer  by as  against science  a an in  Robot S i m u l a t i o n  Perhaps approach  the  and  the  dichotomy  opposing  conflict  between  the  corresponding  first  thinkers  Grey  to  an  significant  alpha  In  the  examining  comparable  the  engender  a P  - the  rhythm minds  two  extreme  extreme  -  the  rhythm  One  example  non-visual,  activity  -  and  might even  and  logical second  p.185  no f f ].  Hadaraard  found  a  intuitive  types  of  will  p e r s o n a l i t y types  a  types:  the  [W,  speculate  research  of  t h i n k e r s with  (H f o r m i n u s )  logical  linguistic  personality  highly visual  to robot  robot  i s an  mathematicians,  between  approaches  two  activity  of  formal,  approach  type  alpha  the  that,  one  correspondingly  !  Goals.  One a  alone and  to  m i n d [ Hd , p . 10 6 ] .  two  1.3.3  as  Walters'  type  dichotomy  mathematical day,  M  between  intuitive  with persistent  corresponding  Studies  goal  tool  of  robot  for testing,  intellectual  language  The  goal  of  of  multitude  uses,  of  robot  competent  initial  uses  are  planetary  e.g.  prevent  i t this  of  the  future  robot  developing  various  stand-  instance,  the will  jobs  horrific be  becoming  the  per  mechanical  written  survive,  warfare;  use  and  research  as  for  i s also  refining,  programs. For  dangerous, or  There  i s the  pattern  recognizers  translators.  construction  obvious  research  about for  in  men.  situations  of  responsibility perhaps  of  These  that  exploration,  reality,  i s  in science  jobs  prospect  se  the of by  will  fiction.  man  finds  where deep  course  man  the  have The  a  most  boring  and  could  not  ocean e x p l o r a t i o n . use robot  of  robots  in  researchers  incorporating  to  some  Robot S i m u l a t i o n  form  of  Asimov's  Three  Laws,  Studies  or  by  12  using  a  self-destruct  mechanism.  The be  social  carefully  i m p l i c a t i o n s of  considered  by  intelligent  machines,  future r o b o t o l o g i s t s , are  which  must  explored  by  G r e g o r y f Gr ] .  Supposing man,  in  merely  a  what  light  machine, or  This  immediately  not  comment.  this  robot  incompatible  -  should will  raises Just  question  research  as  will yet  succeeds we  i t be  view a  in building  these  " f r e e and  purposeful  free-will  question,  for  man[Ne2],  the  co-existent.  be  found  mechanical  creations? Will  the  doubtless  a  two to  cn  views be  which  i t  be  being"? I  shall  expressed  in  essentially  Robot S i m u l a t i o n  Chapter  Desicm  fly method was,  whole that  and i s , t h a t  techniques bring  and  to light  2  o f t h e s i m u l a t e d •. r o b o t  approach  works  13  Studies  has  been  on an ad h o c b a s i s :  a n d , when i n d o u b t , u s e t h e s i m p l e s t . we ideas  might  derive  useful  i n the design  some p r o b l e m s  from  worthy  of  this  The  hope  approach  of a real  attack  use any  i n  some  robot,  and  their  own  right.  I  have  d e l i b e r a t e l y avoided  linguistic  or  formal  preamble,section to  avoid  plagued my  the  natural  approaches,  1.3.2. A l s o rather  system  i t  manner. However  robot  "frame"  i t would  possible  problem]"R3 ] ,  which has  p r o j e c t s , or at l e a s t  I must s a y h e r e  that  chance  to rear  so t h e frame  i nthe  be  and  elementary things,  be d e a l t  that with  R o b b i e c a n do even  i n i n a only  problem  hasn't  had a  a  environment - f o r  i t s head.  2.1  Basic  Suppose  that  arise  pretty  might  any c f t h e w e l l - k n o w n  f o r reasons explicated  I hoped  unnatural  some o f t h e e x t a n t  resulting  utilizing  we  are  approach  introduced  to  new  Robot  Simulation  example, a l a r g e one-floor consider  the  1  : explore  Task  2 : find  and  our  : move  a  form  way  efficient 3  h o u s e , or  a  university  campus  -  and  following tasks.  Task  Task  Studies  an  from  internal  one  point  model of  the  to another,  environment.  in a  reasonably  manner.  large object  ( e.g.  a  t a b l e ) from  one  point  to  another.  These that "How  tasks  we do  can we  very  simple  carry  them  out  carry  processing  the  are  out  Before  a robot  tasks  mentioned  "How?", f o r e a c h  The this;  can  of  us  a  to  carry  above  as  p o s s i b l e , but  simple  We as  answer  to carry the  hopefully, "world  and  model"  might of  that  terms to g i v e  i s capable  must f i r s t  But of  an  of  answer  simple i f asked  the  data  answer.  carrying  the  the  work  reported  out  question  of  thesis  is  idealized,  what t h e  in this  model of a  robot  model s h o u l d  be  with  data  s t r u c t u r e s and  proceed  from  there,  above of  building  r e q u i r e d . When o u r three  "How gleaned  real  above t a s k s  robot  ?"  tasks  then  for  each  seme might  insight take.  of into As  make  procedures more  will  be  as  complex  robot  them.  able  is to  Also,  what f o r m  extra  an  simple  don't  model  we  in  enable i t  k e p t as  the  as  robot  r e q u i r e s to  that  have a  the  simple  start  question we  (in  pressed  t a s k s . The  procedures out  we  see  so  p o s s i b l e and  structures able  not  shall  hard  simple,  l e t us  sense.  tasks?"  built  behind  take  the  be  above,  e n v i r o n m e n t , and out  are  unconsciously.  so  them.  basic idea  let  almost  these  r e q u i r e d ) , we  f o r humans, i n f a c t  the  motivation  Robot  for  setting  mind  played  contains, of  up p r o c e d u r e s  the following  games  fixed  by  apart  movable  then,  f o r each  move  that  children:  robot,  i s obviously  consider  shapes. Let the robot  objects which  through  to the which  number  wander  around and  holes.  { i f any ) f i t i n t o into  the environment  related  i n  equal  and  i t knows f i t s  keep  o b j e c t s , a number  an  objects  we  an e n v i r o n m e n t  fixed  s h a p e s , and  the movable  object  15  f o r the  game w h i c h  of various  which  object  Studies  i t s w a l l s and ether  and d e s c r i b e  decide  that  from  of various  must  and d a t a  simple young  objects  holes  discover  Simulation  which a  Then  i t  h o l e s , and  certain  and i n t o  of  hole,  the hole, i f  i s possible.  Only they  tasks  are.  1 and 2 a r e d e a l t  I  have  definite  1  and  2  with  ideas  i n the system, simple  about  task  3 but they  as  are not  implemented.  Tasks environment move f r o m its  place  environment  In that  the robot  environment choice  looks  must  move f r o m  like  these  for simplicity,  b)  f o r usefulness  tasks  the  represented  a)  :  to  explore  place  to place,  some  conception  an  whereas t o of  what  beforehand.  should  of representation  linked  i t must have  with  i s : "How be  closely  to place  connection  arises  are  i n  we h a v e  i n connection  , t h e most  robot's  basic  question  perceptions  of i t s  i t s memory ? " . C o n c e r n i n g o u r been  guided  by a  with  the tasks  desire  being  attempted,  and c)  that  the representation  square  with  sides  be  of length  independent  of  2 i s represented  size  (  ±.e'. a  i n t h e same  way  as  a  square  complexity. that, a  usage "it"  with  sides  { See f i g u r e  we mean  follows  we  everywhere  f o r "he" o r  of  Robbie  lives  refer  no  or less  o r "him";  those  each  type  of  square  of n i s s e t t o 28, but  way d e p e n d s o n t h i s  the  The l e t t e r s  t h e f o l l o w i n g meanings :  t h e square t h e square boundary  i  i s  or part  a  barrier: of a fixed  o f a movable  'H'  the square  forms  part  of a  hole.  one  square,  instant  position  Robbie  occupies  ( x , y ) , and i s i n one o f  east,  and  or west.  an  n-by-n  a  letter, of  Robbie  t o work  four  An e n v i r o n m e n t  and o r i e n t a t i o n i s c a l l e d  part  of  the  object.  part  south,  this  performance  forms  forms  coordinates  the  i s vacant.  the square  any  to  with  we c a n g i v e  'M*  At  than  n u m b e r . The l a r g e r t h e g r i d ,  in.  have  :  i s marked  the environments  'B'  to  f o r "Robbie"  world  more i n t e r e s t i n g  )  complex  worId  the  ' ' ( blank  feeling  who o b j e c t  s u b s t i t u t e "the robot"  where  the value  i n  intuitive  anthroporaorphically  i n a chess-board  sguares  Currently  the  i s simpler  The s i m u l a t e d  grid  100 ) b u t d e p e n d e n t o n  "him".  2.2  Robbie  16  1. )  robot as "Robbie"  must  Studies  of length  By " c o m p l e x i t y ' *  what  simulated  Simulation  f o r i n s t a n c e , a square  "W".  In  Bobot  plus  object.  specified  orientations, Robbie  a configuration  in a ( see  by  north, specific figure  2 ) .  He  has  t h e f o l l o w i n g a c t i o n s . He c a n move o n e s q u a r e  at a  I n t u i t i v e l y , the square i s l e s s complex than the  "W".  F i g u r e 1.  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B' B  B  B  B  B B B B B  B B B  B  B B B  B B B  B  B B B  B  B B B  B  B B B  B  B B B  a  B B B B B B  B B B B B  1"  |H H H  H  H  B  H  B  B  B B B  B B B B B B  B B B B B  B  B  B  B  B  B  B B B B  B B B B  An example o f a c o n f i g u r a t i o n : Robbie i n an environment. The arrow designates h i s p o s i t i o n and o r i e n t a t i o n . The shaded squares are a l l t h a t he can "see". There i s a f i x e d o b j e c t marked w i t h B's, a hole marked w i t h H's, and the M*s mark a movable o b j e c t that c o u l d be moved to f i t i n t o the h o l e .  Figure 2 .  Robot S i m u l a t i o n  time or  i n the d i r e c t i o n through  sensory  180 d e g r e e s  of  the  occupy blank In  general  he  i s facing  object,  become  goes  with  the  a rigid  turn.  As  sguares may  body  no c o l l i s i o n  OBJA.  b o d y a n d he may  OBJA  Thereupon walk  2.3  In  the  independence objects, as  a  holes  cyclic  the proposed  o b j e c t . I f such a s i t was  i s taken  of  i s , to objects  the execution  picked  may  of a  overlap the  and moved, cease  a  before  of a c o l l i s i o n  R o b b i e a n d OBJA  OBJA  Robbie  t o be a  rigid  model o f t h e  worlds  to manipulate  it._  r e p r e s e n t a t i o n of o b j e c t s .  light of  movable  turns,  between  m a n o e u v r e s , OBJA  has been  h i s way.  whole  cr  or other  no a c c o u n t  r e p r e s e n t a t i o n , and a l g o r i t h m s  The r i n g  step  occurs  wall  blocks  away.  Sobbie^s  2.3.1  a  The d e f i n i t i o n  of Robbie's  only  i s a p a r t . He a n d OBJA  i s s w e p t o u t b y OBJA d u r i n g  a result  h i m . He c a n  the  the c o n f i g u r a t i o n remains  or turn.  the  h i s way. I f , h o w e v e r ,  up  square  : i f he t a k e s  of a hole. After  drop  that  sense  «B' o r 'H»  pick  right His  only  surrounding  or square.  can  he c a n  unnatural, i n that which  he  square  o f which  left  o n t h e same  'M' a l s o b l o c k s  then  step  :  marked  o f OBJA a n d some  occurs  the area  limited  A square  him, provided  rather  remaining  squares  17  and c a n t u r n  marked  say,  attempted  date, in  a n 'M'  position  collision  are  sguares.  OBJA  while  eight  a square  then  final  he i s f a c i n g ,  capabilities  contents  Studies  of  size  the , we  requirements  chose t o represent  i n t h e e n v i r o n m e n t , and the list  of  o f t h e edges and c o r n e r s  simplicity objects,  environment that  occur  and  movable itself, when  one  Robot  goes round the  the  o b j e c t . The  computer  gives ) at  the  is  length  i t s end.  Simulation  as of  fin  natural  a  an  "ring"  edge  example  and  Studies  way  of  represent  linked  the  i s given  to  type  18  nodes  of  (left  walks  encountering round  generates simple  the  the  to  similarity see  that  rotated  ( i s one  -  i . e . do  corners,  lengths  may  similar the  internal  where  not?  the  ring  to  the  -  an  in his  object,  to  of  descriptions  of  two  inside  other. so  figure 5  ring"  of  the  This  of  an  tried  is  whether  did  devised involves a  not a  by  as  i t ,  of  we  as  the  as  the  ),  other?  same of  but  "up  edges  the  edge  to  note  is  and  Stark  very [No],  format f o r  the  mentioned  in  brain.  game  could  seem  the  here  a  one  other?  used  decide, one  found i t (can  number  Noton  i n the  given be  the  moved  feasible  decomposition deeper  about  interesting  object  to  t o be  must a g r e e  perception, object  and  (both  same  types  ). It  left,  c o n t r a c t i o n of  object-to-hole  objects,  which  top  Robbie  the  f o r congruence  the  proposed  an  also  we  have  to  seem  for corner-congruence  visual  we  or  the  Using  l i e e x a c t l y on  corner  with  keeping  devise.  expansion  right  environment,  would  objects  the  "feature  2.1,  representation  two  both  representation  descriptions,  could  representation  context  the  the  they  see  In connection section  object  one  compare  f i g u r e 4 ) , and  to corners" and  of  a d e s c r i p t i o n as  t r a n s l a t e d and  for  in  edge  an  above d e s c r i p t i o n . T h i s  straightforward be  such  or  node  3.  Definition: this ring of nodes i s ri_nc[ r e p r e s e n t a t i o n o f a n o b j e c t .  On  within  where e a c h  turn  in figure  this  of  a n a l y s i s of  to  ring f i t  using  ring  the  ring  the  shape  of  6  7  8  9  X ' 9 -10 •11  -12 -13  T h i s "L" - shaped o b j e c t has t h e the r i n g - r e p r e s e n t a t i o n diagrammed below.  name = OBJECT 3 # edges = 6 top l e f t hand c o r n e r  length=4  length=2  turn = L  turn = R  y  (9»5)  length=3 turn = L  s  length=2 turn = L  Figure 3  Similar objects.  F i g u r e 4.  Corner - congruent objects.  F i g u r e 5.  Robert S i m u l a t i o n  the  object  fact  this  Robbie  (or of t h e boundary decomposition  i s endowed  with,  19  Studies  of the environment i t s e l f  i s basic so i s  ) . In  t o most o f t h e p r o c e d u r e s  of  central  importance  that  to  this  thesis.  2.3.2  Maximal  In simplest decide is  i n which  kind  Given  of object.  i f one c a n f i t i n s i d e  to  a rectangular place.  complicated  a "U" a r e  figure as  the other  overlapping  decomposed  should  i n figure  7 should  need  be  rectangles.  into  i s the  i ti s t r i v i a l  ; also,  natural suggestion,  .  a rectangle  two r e c t a n g l e s ,  supposing t o move  decomposed  from a more  into  into  are a l l the "biggest11  a  F o r e x a m p l e , an " L " rectangles  as  s o o b v i o u s hew a n o b j e c t  be decomposed  to  Robbie  then, i s that  overlapping  6. However i t i s n o t q u i t e  What we an  we o p e r a t e ,  or environment  of  DECOMP  environment, i ti s t r i v i a l  The  object  conglomeration and  the algorithm  the environment  inside  place  subrectangles:  i n such  rectangles.  rectangles  contained  i n  object.  Definition : a jaximal_subrectang_le of an o b j e c t 0 i s a r e c t a n g l e R contained in 0 such that each side o f R has a s u b i n t e r v a l i n common w i t h a n e d g e o f 0 . Our  representation  representation abbreviated decomposed  ring,  "MRT"s into  of  ring  object  contains,  the l i s t  of a l l i t s maximal  ) .  instance  For  the collection  DECOMP i s a b a s i c the  an  o f MRTs i n f i g u r e  procedure  representation  of  the object  an  i n our system object  into  besides  the  subrectangles i n figure  (  7 i s  8.  which  decomposes  a list  of a l li t s  Decomposition o f simple shapes i n t o o v e r l a p p i n g r e c t a n g l e s .  F i g u r e 6.  20  1  T  r  T  1  r  1  19  top l e f t hand corner  17 , 18R  O B J A  £  T  16  Q  r  H  15  13  M  12  1  1  ± 8  11  I  -7  9  G  J  j 6  r  i  I  10  K  I t i s not immediately obvious how t o break the shape o f OBJA i n t o o v e r l a p p i n g r e c t a n g l e s ( but see f i g u r e 8 ) . T h e - d i g i t s by each edge g i v e the edge-number. F i g u r e 7.  '  '  •  Conceptual decomposition of the shape of OBJA (figure 7) into the MRTs  R1 , R2, ... , R9. F i g u r e 8.  Robot S i m u l a t i o n  MRTs. I n a s e n s e  one c a n s a y t h a t  its  MRTs.  constituent  independent follows  interest,  i s a brief  Since full  Dl.  [ Initialize  DLL  Take  the f i r s t  DL2.  Take  the next  DB1.  Take is  a  bottom DB2.  Take  Take from  edge the  defined Take B. DT.  i n appendix  with  bottom  first  with  i t s left  go b a c k  right right  R  lies  the  side  edge R a f t e r  side  edge  be  stop  side  edge e x i s t s , top edges left  edge  a t o r below  are defined  DR2.  be  order  and  which  possible  defined  to  by L and i t s  B which  such  i s accessible to  defined  go b a c k  L  exists  side  from  L and  the  right  t o DB2.  l i e between  i n ring  t h e bottom  a  by R. Go t o DT.  i saccessible  which  draw  by L , i t s b o t t o m  order,  and  which  b y L a n d R. I f o n e  ends  of both  whose l e f t ,  by L , B , a n d R  Otherwise,  L . I f no  possible  defined  R which  no i n s c r i b e d r e c t a n g l e  to  edges,  L i n ring  the horizontal interval defined  back  A. What  t o DL2.  i s , i t would  i t s left  edge  sides  of  list.  edge B a c c e s s i b l e from  right  through those  right  be  b y B . Go t o D R 1 .  exists,  and  MRT  i s , i t would  by B , and i t s r i g h t  these  may  CECOMP  edge B a f t e r  L, that  defined  I f no s u c h  then  a r e given  used  into  e d g e L a n d go t o D B 1 .  bottom  Check  of  algorithm  an o b j e c t  list.  the next  overlap  "parses"  e d g e L . I f no m o r e l e f t  L and B , t h a t  rectangle  DR2.  left  rectangle  the next  bottom DR1.  left  first  side  details  algorithm  a c c e s s i b l e from  draw  the  ] . S e t up t h e empty  t h e MRT the  DECOMP  20  description of the procedure.  The  return  Studies  L a n d R,  bottom, and  respectively ;  l e t T be t h e l o w e s t  go  o f thet o p  Robot Simulation Studies  edges checked bottom,  right,  respectively list  It  i n  figure  7. T h i s  the  figure  9  that  only  a r e needed  we  the  have  another  as  hole  i n the environment.  rotation, into Example  each  Robbie,  under  a  o f the maximal  and  we  consider  we  ask Robbie  somewhere i n R5. maximal  Suppose  subrectangles  in  particular  it  i s a fairly  following  OBJB  o f OEJA o f  and  ask  "Can  OEJB ? " . ( T h i n k  o f OBJB  ) I t i s sufficient  in this  certain  translation  subrectangles  simple  plan  ii)  move  an  t o move f r o m  also  task  that  R1  and  t o R5  fits  environment  for  R3  point knows  with  i n R2 t o how  each  the  other,  o v e r l a p s R5. Then  come  up  with  the  :  t h e 1-by-2 i n t e r s e c t i o n  through  a  he  R3 a n d R3  f o r him t o  onto  o f R2 a n d R3  t h e 1-by-2 i n t e r s e c t i o n  o f R3  R5  move t o t h e r e q u i r e d  However, f o r c e r t a i n subrectangles  as  R1 t o R5 i n t e r s e c t  of action  move o n t o  and  OBJA  t h a t R2 o v e r l a p s  i)  Example  subrectangles  OBJB.  2. Suppose  iii)  to f i t inside  that,  maximal  object  b e moved  know  : a d d i t t o t h e MRT  guestions.  OBJA  to  left,  by L , B, R and T  i n the decomposition  object  case  whose  t o DR2.  i s true, f o r certain  1. S u p p o s e  a  rectangle  i s a maximal subrectangle  be o b j e c t e d  shown  Then  and t o p s i d e s a r e d e f i n e d  and go back  may  Example  through.  21  other  o f OBJA  1. S u p p o s e  O B J B b e moved  position  questions  i n R5.  the l i s t  o f a l l the maximal  i s needed.  we h a v e  another  to f i t inside  object OBJA  O E J B a n d we  ask  "Can  ? " . I f OBJB c o n s i s t s o f a  T h i s c o l l e c t i o n o f MRTs, which covers OBJA o f f i g u r e 7, s u f f i c e s f o r some, but not a l l , q u e s t i o n s concerning the shape o f OBJA.  F i g u r e 9.  Robot Simulation  single list not  Studies  22  1-by-8 r e c t a n g l e , s a y , i t i s q u i t e o b v i o u s f r o m t h e in  f i g u r e 8 t h a t t h e answer i s " y e s " ,  a t a l l obvious from t h e l i s t  Example 2. Suppose we a g a i n Robbie, but t h i s  consider  whereas i t i s  i n f i g u r e 9.  OBJA a s an e n v i r o n m e n t  for  t i m e t h e r e i s a movable o b j e c t c o n s i s t i n g  o f a 1-by-3 r e c t a n g l e p o s i t i o n e d somewhere i n R1. Then a s k "Can  R o b b i e move t h e 1-by-3 r e c t a n g l e t o t h e b o t t o m  hand  corner  possible, to  of  the  environment  ( i . e . o f R5 ) ?". I t i s  with a s u i t a b l e perusal of the l i s t  i n f i g u r e 8,  a n s w e r " y e s " and i n a d d i t i o n s a y how t c c a r r y  task;  but  figure  9.  Conseguently,  this  we r e t a i n  w o u l d be v e r y  hard  the complete l i s t  right-  t o do from  out the  the l i s t i n  o f MRTs o f an o b j e c t .  { The above e x a m p l e s s u g g e s t t h a t we s h o u l d  use  two  lists  o f MRTs o f an o b j e c t . covering  list  :  those  MRTs w h i c h a r e e s s e n t i a l t o c o v e r t h e  object. figure  (There  i s no way t o c o v e r  7 without  OBJA o f  i n c l u d i n g t h e MRTs R 1 , R2,  ... R5. ) The  secondary l i s t  : a l l o f t h e MRTs n o t i n t h e c o v e r i n g  However, we have n o t i m p l e m e n t e d t h i s . Figure into  MRTs  we i g n o r e  2.3.3  }  10 g i v e s e x a m p l e s o f s h a p e s f o r w h i c h i s clearly  these  not the best  decomposition  a p p r o a c h , b u t f o r t h e moment  complications.  Containment : the a l g o r i t h m  list.  CONTAIN  Examples of shapes for which representation by straight-forward decomposition into MRTs i s clearly not the best approach.  Figure  10.  Robot S i m u l a t i o n  Having maximal  the decomposition  subrectangles,  concerning inside  described  Studies  two o b j e c t s  23  o f an  we a r e now r e a d y  object  t o answer  O B J A a n d O B J B , " C a n OBJA  into i t s  the question,  b e moved  to  f i t  O B J B ?•».  We f i r s t  have t o f i n d  the "super-rectangle"  c f each  object.  D e f i n i t i o n : the §u_per-rectancjle c f an object i s the smallest rectangle which contains that object. The between  partial rectangles  classify and  the  arrange  relation. have  i n  same  would  at  the  top covering  one  c f which  of  figure  positions 6,  Now  every form  i n this  the  lattice  containment  3-by-4,  i n a diamond  on  individual  r o t a t i o n s . For  3-by-9,  shaped  lattice  be  at  7-by-5,  lattice  rectangles  would  with  rectangle 3-by-9 and  the  bottom,  r e c t a n g l e s . The t o p p o s i t i o n s  to {equivalence could  may  structure i s actually  c o n s i s t i n g o f t h e } 7-by-9  MET  We  dimensions  o f an o b j e c t  i s i n v a r i a n t under  and 7-by-5  other  lattice.  o f MRTs r a t h e r t h a n  rectangle  correspond  a  the  parts  lattice  of containment  to their by  t h e two i n c o m p a r a b l e  t h e 3-by-9  7  1-by-12,  class  t h e 3-by-4  of t h e l a t t i c e  given  o f dimensions  be a r r a n g e d  ( t h eequivalence  by  classes  o f an o b j e c t  the  covered  the  as  according  lattice  dimensions  rectangles  7-by-5, while  represented  object  the  on e q u i v a l e n c e  7-by-9  by t h e r e l a t i o n  s e v e r a l MRTs i n d i f f e r e n t  MRTs. The l a t t i c e  and  i s naturally  them  example, four  given  MRTs o f e a c h  Since  the  imposed  ordering  classes  o f } MRTs  f i t . A s an e x a m p l e , t h e shown  correspond  i n  figure  into MRTs  11. The t o p  t o MRTs o f d i m e n s i o n s 3 - b y -  7-by-2.  we o u t l i n e t h e  algorithm  CONTAIN  f o r answering  the  7-by-r12  (super-rectangle  o f OBJA)  3-by-6 (R5)  1-by-12 (R9)  7-by-2 (R8)  >by-5 (R2)  1-by-9 (R7)  5-by-1 (R6)  3-by-4 (R3.R4)  3-by-3 (R1)  The l a t t i c e  formed  by  t h e MRTs o f  OBJA  of figure  7. Figure 11  Robot S i m u l a t i o n  question  of  objects  OBJA  decomposed into or  containment.  into  into  obstructions  i t  such  figure  would  where  t o CONTAIN  each  o f MRTs,  24  input  c o n s i s t s o f two  object  i s either  and t r a n s l a t i o n  OBJB  (ignoring  the complications  objects, walls,  a r g u m e n t s t o CONTAIN  be a c c o m p a n i e d  8 and t h e l a t t i c e  organised  etc.).  required  Can t h e  For  instance,  were t h e OBJA o f f i g u r e  by t h e l i s t  o f 9 MRTs i n d i c a t e d i n  shown i n f i g u r e 11.  super-rectangle  super-rectangle  CT2.  of  of  OBJB,  OBJA  and y - d i m e n s i o n s o f OBJA b o t h  to  the x- and y - d i m e n s i o n s  If  n o t , answer  If  OBJB  i s  f i t inside  or i n o t h e r  x-  less  the  words a r e the than  or  equal  c f OBJB ?  "no" and s t o p . a  single  rectangle,  answer  " y e s " and  stop. CT3.  CT4.  Can t h e s u p e r - r e c t a n g l e top  MRTs o f OBJB  not,  and OBJA  stop  ; otherwise  Can e a c h top  o f OBJA  f i t into  ? I f s o , answer  i s a single  < Now  we  relative every  one o f  the  " y e s " and s t o p . I f  r e c t a n g l e , answer  "no" and  proceed.  o f t h e t o p MRTs o f OBJA f i t i n t o  MRTs o f OBJB  ? I f n o t , answer know  that,  one o f t h e  "no" and s t o p .  disregarding  the  p o s i t i o n s o f t h e MRTs o f CBJA,  MRT o f  somewhere. >  OBJA  can  to  of p o s s i b l e  lJhe_al2ori^m_C08TAIN CT1.  been  a s t r a i g h t "no",  the r o t a t i o n  as other  has  and t h e component MRTs  with  one o f t h e i n p u t  7,  The i n p u t  s t r u c t u r e . The o u t p u t  "yes" together OBJA  OBJB  a list  a lattice  move  if  and  Studies  f i t into  OBJB  Robot S i m u l a t i o n  CT5.  Take how  each  MRTs the CT6.  number  For each  pick  of different  OBJB,take  check  i f a l l the remaining  "no"  and  Figure answer  answer  "yes"  force"  size  considerably objects  algorithm  o f OBJA r e q u i r e d  stop  ;  are  and  indeed  translation i s  otherwise,  i n which  CT6  works r e a s o n a b l y  and c o m p l e x i t y  answer  must be  invoked  the  compared in  two  and i m p r o v e m e n t s c o u l d  searching  by making  well for  to  objects  of shape. However, i t i s a  t o the problem  MRTs, a s i l l u s t r a t e d utilizing  can f i t  correctly.  reduced  being  f o r which  A*  MRTs o f OBJA  s h o w s two c a s e s  solution  instance,  ways i n w h i c h  and  into  minimum.  o f OEJB. I f a s u i t a b l e  " y e s " o r "no"  of s i m i l a r  f i t i t  A* o f OBJA  the t r a n s l a t i o n  count  stop.  12  The above  to  ways i s a  of the different  a n MRT  i n t u r n and  are  a n MET  into  found,  For  ways t h e r e  o f OBJB, then  inside  -  o f t h e t o p MRTs c f O B J A  many d i f f e r e n t  25  Studies  reguired  use  of  the f o l l o w i n g obvious  13. fact  CT5  connectedness  c o n s i s t of long figure  i n  "brute  be  made.  could when  be the  sequences o f connected  This  about  would  be  done  by  connectivity :  If MRTs A1 a n d A2 a r e c o n n e c t e d i n O E J A , a n d A1 c a n f i t i n t o MRT B1 o f O B J B , t h e n A2 c a n o n l y f i t into B1 o r some MRT o f O B J B t h a t i s d i r e c t l y c o n n e c t e d t o B1.  2.3.4  Plans:  The required  plans  their  c o n s t r u c t i o n and  dealt with  f o r Robbie  execution.  i n t h e system  t o move f r o m  place  so f a r a r e m e r e l y  to place  i n a  those  reasonably  ]  OBJA  OBJB  CONTAIN (OBJA,OBJB) doesn't answer "no" u n t i l  OBJA  CT6«  U  L_ OBJB  CONTAIM (OBJA.OBJB) doesn't answer "yes" u n t i l CT6.  The containment question : two pairs of arguments for the algorithm CONTAIN for which step CT6 must be invoked to answer correctly.  Figure 1 2.  OBJA  OBJB  An example o f a p a i r o f o b j e c t s f o r which COI.TALN(OBJA,OBJB) performs p a r t i c u l a r l y badly.  F i g u r e 13.  Robot  efficient  manner  are  small  are  limited,  the  fixed  i n that  executing  We  Robbie  and e x e c u t i o n  models of the world  We  take  insert "IRT" at  between ) which  graph  whose  links  i n  how  M RT 1  from plan  intersection  to  and  illustrates  The  MRTs  they  an  into  a chain  i t i s  o f MRTs  from  must  be  found  other  nodes a r e c o l o u r e d  are  by  i s found,  link  reach  may  Robbie  initially.  reach  in figure overlap  the  as a  overlap  path-finding links  no s u c h  from  chain  A. F i g u r e  position  described  HERE  i s  i t constitutes a  to reach  be  THERE. C o l o u r  B  and  abbreviated  overlap  A t o B ; otherwise, to  as  and t h e node  wavefront  of  15.  B.  follows. t o which a  HEBE r e d a n d T H E R E b l u e . A  }  and s e t  a n d he m u s t  uses a  connected  i n the graph  path  B.  MRTs a n d w i t h  MAKPLAN  a chain  algorithm  plans  i n s e r t e d , may b e v i e w e d  the construction of a plan  node  {  Now s u p p o s e  into  program  impossible  path-finding  MRTs  "overlap"  rectangle"  overlap.  rectangles  i n the  between  i s p o s s i b l e , as i l l u s t r a t e d  MRT5.. I f s u c h  the starting  objects  f u r t h e r i n appendix  i n the environment,  The  of a c t i o n f o r going  exists  Call  MRTs.  to find  M RT1  o r movable  v e r t i c e s a r e MRTs a n d w h o s e e d g e s  between  algorithm  with  [The r e l a t i o n  T h e e n v i r o n m e n t , when d e c o m p o s e d and  satisfactorily  model of t h e world  an " i n t e r s e c t i o n  B i n MRT5 i f t h a t  links  plans  fixed  even  obstacles  these  o f the environment  of overlapping them  A  large  i s considered  specifies  position  position 14.  pair  yet deal  of plans.  the decomposition  f o r every  of  where t h e o n l y  of writing  use o f Robbie's  and  up  cannot  26  plan.  make e x t e n s i v e  construction  At t h e time  occurrence a  Studies  w i t h i n an e n v i r o n m e n t  objects.  unexpected  while  Simulation  red  No  nodes  Decomposition o f E i n t o MRTs p l u s o v e r l a p l i n k s and i n t e r v e n i n g i n t e r s e c t i o n r e c t a n g l e s (shaded).  F i g u r e 14.  MRT4  HST2  MET 5 MRT1  The graph form o f environment E.  S t a r t i n MRT1 Hove through MRT1 i n t o IRT1 Move through MRT3 i n t o 1RT4 Move through MRT4 i n t o IRT5 Ends i n MRT5. P r i n t e d output o f the p a t h - f i n d i n g program MAKPLAN.  MRT1  MRT3  IRT1  MRT4  IRT4  MRT5  o  IRT5  The c h a i n o f p o i n t e r s produced by MAKPLAN.  F i g u r e 15.  Robot  expands i n s t e p s from in  s t e p s from  nodes blue  whose  Simulation  HERE  and a w a v e f r o n t  shortest  path  consists  back  t o HERE  n . A node r e t a i n s  to  and b l u e  i t . The  red  When t h e w a v e f r o n t s  THERE, and t h i s  that simple  this  of b l u e nodes  i s  matter  produced  of minimal  t o modify  first  has been  length,  the algorithm  assigned  from  HERE  algorithm.  and t h a t  to obtain  back t o  i n alternate  found  by t h e  o fa l l  n , andt h e path  w a v e f r c n t s a r e expanded  i s the path  a path  shortest  the colour  meet, a path  expands  consists  i s of length  o f a l l n o d e s whose  THERE i s o f l e n g t h  to  27  THERE. A t s t e p n t h e r e d w a v e f r o n t  wavefront  steps.  Studies  Note  i t would  a l l  be a  paths  from  HERE r e d a n d t h e n o d e  THERE  HERE t o T H E R E .  The PF1.  [Initialize.] blue.  PF2.  S e t up t h e l i s t and t h e l i s t  [Expand  RWAVE. ]  initialize list,  PF2.1  C o l o u r t h e node  alone,  link  a l g o r i t h m PF_.  BWAVE c o n s i s t i n g  Set  up  the  each  to P. Three  node cases  I f Q i s neither the l i s t  Q that  of  the  node  HERE  o f THERE a l o n e .  temporary  i t t o be e m p t y . F o r e a c h  take  to  RWAVE c o n s i s t i n g  list  node P  i n  i s connected  RWAVEt a n d the  RWAVE  b y an o v e r l a p  arise.  red nor blue  then  colour  RWAVE#, a n d s e t a p o i n t e r  Q r e d , add Q  from  Q back  to  P. PF2.2  If  Q  i s  coloured  already  r e d then  a t an e a r l i e r  do n o t h i n g - e i t h e r  stage or i si t s e l f  Q was  a member o f  RWAVE. PF2.3  I f Q i salready  b l u e t h e n a c o n n e c t i o n h a s been  between a r e d path path  emanating  from  emanating  from  THERE. Reverse  HERE  and  a  the pointers  found blue along  Robot S i m u l a t i o n  the  r e d path  directed and When  [Expand  PF3.1  PF3.2  o f nodes from  nodes  reset  BWAVE.]  initialize  link  chain  a l lthe  list,  and s e t a p o i n t e r from  P t o Q, s o t h a t a  HERE t o T H E R E  remains,  stop.  considered, PF3.  28  Studies  P  RWAVE Set  i n  the  RWAVE  t o t h e new l i s t up  the  each  node  t o P. Three cases  Q that  list  node P  i sconnected  BWAVE  overlap  arise.  Q  to  BWAVE#, a n d s e t a p o i n t e r  to  P.  coloured  the  by an  r e d nor blue  I f Q i salready  been  BWAVE* a n d  i n  I f Q i sneither the l i s t  have  RWAVE#.  temporary  i t t o be e m p t y . F o r e a c h  take  list  blue  then  a t an e a r l i e r  then  colour  do n o t h i n g  stage  Q blue,  add  from  Q  back  Q  was  - either  or i si t s e l f  a member o f  B WAVE. PF3.3  I f  Q i salready  red then  between a r e d path path the  emanating r e d path  directed and When  emanating  from  HERE  from THERE. R e v e r s e  and s e ta p o i n t e r  chain  o f nodes  and  found  a  blue  the pointers  along  from  from  has been  Q t o P , so that  HERE t o THERE  a  remains,  stop.  a l lt h e  considered, PFU.  a connection  nodes  reset  P  i n  the  BWAVE  BWAVE t o t h e new l i s t  [No  path  exists.]  I f either  list  i s empty, stop  and r e p o r t  list  been  BWAVE*.  t h e RWAVE failure.  have  list  o r t h e BWAVE  Otherwise  go  back  to PF2. The  algorithm  written  quite  i s illustrated independently  i n figure of  Eohl  ,  16.. T h e a l g o r i t h m who  discusses  was path  0  ©  i s a node t h a t has been coloured r e d . i s a node t h a t has been coloured b l u e .  The e n c i r c l e d groups o f nodes o f the graph a r e t h e s u c c e s s i v e wavefronts as found by the a l g o r i t h m PF. The t a b l e below g i v e s the order i n which t h e wavefronts a r e found.  Successive RWAVEfronts  Successive BWAVEfronts  The path Nl , N3, N6, N11 , N H from HERE t o THERE i s found when advancing the BWAVEfront f o r t h e second time.  Example t o i l l u s t r a t e t h e a c t i o n o f t h e a l g o r i t h m PF on a graph.  Figure 16.  Robot  problems in  i n depth  similar  A  and d e s c r i b e s  language  plan  produced  and  calls  TURN,  a similar  by  MAKPLAN  of a  plan  o n MOVE, MOVE c a l l s and  the effects  i s  where  typical  l e g i s "move t h r o u g h  in  charge  current  of  position  One  the  a  plan  different  not  forms STEP  difficulties dealing  can f a i l  fails  unexpected  i f STEP  at  fails  avoiding  control  program.  at  level,  this  fails,  o b j e c t , and takes  TURN. EXPLAN  attempts  only  fails,  when L I N E A R  2.4  Robbie  and r e p o r t s  by t h e  the  plan,  ; i t i s  LINEAR  from  i s  Robbie's  position.  i n  any  system  for  This  At t h e lowest l e v e l  takes  i n our  i nf r o n t o f Robbie i s i sholding this  action  with  i nfailing  and r e p o r t s  we  to  MOVE..  i sdue t o an  calls  to  after  failure  s o p h i s t i c a t e d system  an o b j e c t .  back  assumes t h e f a i l u r e  avoiding  action,  re-planning  on STEP  IRT4"  the unexpected.  t h e sguare when  of  possible  inherent with  leg  obstacles.  destination  i f MOVE p e r s i s t s  I n a more  calls  MRT3 i n t o  as  levels.  because  v a c a n t . TURN c a n f a i l  MOVE  linearly  at different  LINEAR c a n f a i l  and  as  i s  o f each  any unexpected  to a specified  of  executing  system,  moving  organised.  o f S T E P a n d TURN a r e d e f i n e d  i s i n charge  of avoiding  by t h e p r o g r a m  cn L I N E A R , LINEAR  MOVE  i n charge  algorithm  hierarchically  reality.  also  path-finding  i s executed  simulated a  29  Studies  [Pb,p. 1 5 ] .  E X P L A N . The e x e c u t i o n EXPLAN  Simulation  STEP  several  back would  to the have,  by MAKPLAN.  Ex£loration  So generate  f a r we  have nowhere i n d i c a t e d e i t h e r  the r i n g - d e s c r i p t i o n of h i s environment  how R o b b i e i n  the  i s to first  Robot  place,  or  generate  how  this  he m i g h t  ring-description. line  FOLLOW  causes  using  a  of  would  along  and  'B' s q u a r e  FIND  and t h e n  which  following of  what  not f i t with  sets  o f fto explore clear  h i sprevious this  object  procedure  360 d e g r e e s ,  to generate the ringunintelligent  Robbie  has a square probes  he e n c o u n t e r s an o b j e c t  the  through  t h e environment  He m a k e s r a n d o m  o f fi n a  has not been  lines.  the  Robbie  Then  RINGS  i sa rather  approach,  generating  sends  i s found.  procedures called  notion  empty.  i s quite  object  i n originally  procedure  one p o s s i b l e , w h i c h  whenever  30  an i s o l a t e d  t o f o l l o w t h e boundary  the  does  he  a  better  preconceived  otherwise  find  a cheat  a s he g o e s . T h i s  A  simplest  The  Robbie  proceed. be  allow  until  set  description  first  Studies  objects' ring-description.  We e f f e c t i v e l y  straight  Simulation  leeks  with  like  wall  i n various  ( or wall or  and i s  directions,  hole  )  that  of t h e environment  fits  into  a  - the  by f o l l o w i n g i t s b o u n d a r y  how t h e new o b j e c t  to  implemented,  starts  boundary  conception  way  he  until  h i s model o f t h e  environment.  To  find  isolated  objects  MRT  of h i s environment. F i r s t  he  uses  time  square the  of  the  he u s e s  object  does  he g o e s  t h e p r o c e d u r e EXPLORE  of writing,  centre  Robbie  the f o l l o w i n g f o r each  to i t , using  t o explore  i t . EXPLORE  extremely crude: i tmerely MRT, a n d i f b y c h a n c e  sends  this  square  was a  part.  the  then  i s , atthe  Robbie  he e n c o u n t e r s a  t h e p r o c e d u r e FOLLOW t o f o l l o w  o f which  PLANS,  to the  non-blank  boundary  of  Robot Simulation 2.5  Studies  Summary of Rpbbie_^s world On  the l e v e l  of d i r e c t  contact with the outside  Robbie knows h i s p o s i t i o n and o r i e n t a t i o n eight squares surrounding  and can "see"  data  the  him, and possesses a pickup arm which,  when " a c t i v e " , "holds" a movable object i n the outside The  world,  structures  world.  used i n Robbie's conceptual model of  the world are extremely simple, at the top l e v e l  he  has two  pointers and four stacks of o b j e c t s . One p o i n t e r , c a l l e d "home", points  to the header  of the r i n g  representation  environment. The other p o i n t e r , c a l l e d "currentnsrt",  of h i s  points  to  the MRT of the environment i n which'he i s c u r r e n t l y l o c a t e d . The stacks  are used  f o r the four d i f f e r e n t kinds cf objects that  Robbie may f i n d i n h i s environment objects,  holes,  : fixed  objects,  moveable  and anything else that doesn't f i t i n t o one of  the f i r s t three categories. The header of the r i n g representation of the. environment or of any object contains s e v e r a l p o i n t e r s . r i n g representation  Pour  point  into the  (having four instead of one merely speeds up  questions of congruence, corner-congruence, and s i m i l a r i t y ) , one points  to the l i s t of MRTs of the object, and cne points to the  l a t t i c e s t r u c t u r e associated with the MRTs of that pointer  to the l a t t i c e  structure  object.  The  i s n u l l unless the object  becomes involved i n a containment guestion, because only then i s i t necessary to construct the l a t t i c e . at a lower l e v e l , the overlapping MRTs of the environment are  linked  together  with  overlap pointers, and each MRT of a  Robot  pair  of overlapping  rectangle  The the  of  will  and  is  of  on  object then  used  These  model  the  EXPLAN  t o compare  isolated  :  the  a  ring  MAKPLAN  model  r e g a r d e d as  programs  of  being  and  the  intertwined.  when  Robbie  the l a t t i c e FOLLOW  and  EX PLAN uses  , and the  i s then executed , C_CONGRU ENT  the shapes  SETOLAP c o n s t r u c t s  of the environment  MAKPLAN  CONGRUENT  be  representation  representation.  boundary  which  objects.  should  o f MRTs. FIND and  program,  .  intersection  o f h i s e n v i r o n m e n t . DECOMP p r o d u c e s  a ring  follow  a plan  to the  they act are i n e x t r i c a b l y  constructs  i t s list  construct by  his  which  from  used  pointer  manipulate Robbie's  p o i n t e r s . LATCONS c o n s t r u c t s  PLANS i n c o r p o r a t e s often  and  listed.  the boundary  o f MRTs f r o m  overlap  be  simply  following  list  which b u i l d  parcel  RINGS  MRTs p o s s e s s e s a  now  representations  32  Studies  pair.  programs  world  part  that  Simulation  of  two  structure first  c r o f an  i s perhaps overlap  , SIMILAR  objects.  and  EXPLORE  an and  object.  the  pointers  in hierarchical  the  of  find  a  most to  fashion  CONTAIN  are  finds  new  Robot  Chapter  ROSS  :a r o b o t  3.1  How  3.1.1  General  ROSS robot  i s  environment. to  turn,  a  higher  a  level  "Robbie",  and  neighbours.  has the b a s i c  abilities  of  movable  a  ROSS  terminal with a typewriter  s t e p s and  consists  at  of  a  as belonging t o  to h o l e s , o r to other christened  man o c c u p y i n g  labels  of  a  single  h i seight  nearest  be compared  through  of  objects,  The r o b o t i t s e l f ,  might a l s o  eyesight wandering  course  objects,  the  type  about t h e environment i n  o f as a b l i n d  sense  simulates a  to take  are labelled  "oddities".  be c o n c e i v e d to  which  rectangular,  and drop  sguares  o r movable  His situation  the  program  manner. The e n v i r o n m e n t  i n which  to fixed  able  man w i t h g o o d  computer  computer  two-dimensional,  are called  may  system  t o use  i tcan e x p l o r e and walk  grid  which  In  a  intelligent  boundary,  square  simulation  and t o p i c k u p , m a n i p u l a t e ,  rectangular  things  i n  The r o b o t  reasonably  the  3  description  an i n t e r a c t i v e  living  33  Simulation Studies  a dense  episode, keyboard  with  that of  a  forest.  the and  user CRT  sits  at a  display  Robot S i m u l a t i o n  screen.  He  execute  them  the  issues by  ROSS  means o f  action  34  commands  snapshots which  and  watches  periodically  Robbie  appear  on  screen. A  snapshot  single  a  picture  appear  (senses,  world  trail  and  a l l  MRT  respectively, at this  the  he  fixed  i n  thinks  objects,  his  MRT  Robbie's  there  this  environment with  i s a  that  Robbie  within  his  environment,  allow  him  addition  to count  and  then  relate  position  counts columns  The  could  user  (x,y), from  can  can  and  also  dots  turns,  from  can  as I do,  position  the  as  also  position  this  his  the  contact  that,  then  i f we i s  no  absolute the  origin  In r e f e r r i n g  top  of the  view  should  out  knew  to this.  section  direct I  to or  across  to h i s absolute  didn't  positions  hall,  the d e t a i l s  drawn  immediately point  of,  known  is in  a l t h o u g h he  take h i s i n i t i a l  issue  room,  "senses".  to refer  and  numbers holes  not; h i s only  F o r , i f he  to  the  definition  of  his  x counts rows left  or model of  the  any  state i f  t h e e n v i r o n m e n t and  i s allowed  h i s steps  he  the  the user that  a l lh i s subsequent as  and  the  holding  movable o b j e c t s , and  of  to h i s knowledge.  position  he's  i s through  mention  i s  state,  i n ,  physical  he  a  and,  m o t i o n s . Below  h i s mental  whole, Robbie  the environment  what  with  position  Robbie's  and  "curtain"  i s t o remind as a  of  environment;  the picture  screen:  present  i s , roughly,  2.3.2. Between state  of  the environment  h i s recent  details  details  of  Robbie's  orientation  t i m e ) . An  passageway  a picture  of dots recording  a few  (what  of  marking  position,  anything)  him  consists  " 3 " character  usually,  a  Studies  down  and  to y  right.  a c o m p a r a t i v e command a s k i n g  Robbie  Robot  to  compare  In are  t h e s h a p e s o f two known  addition  executed  commands  to  Definition:  are  a  episode,  or perhaps  the  executed  physical state at a r e used  world.  production  i n one o f f o u r  a  by  ways.  commands  the  consists  supporting  of  particular  system.  an e n v i r o n m e n t instant.  plus  The  global  t o s e t up c o n f i g u r a t i o n s , t o t e r m i n a t e  a ROSS  t o wipe o u t a l l o f Bobbie's  current  of snapshots  printouts of various  and t o o b t a i n  I f no c o n f i g u r a t i o n i s s p e c i f i e d  a s s u m e s by d e f a u l t t h e t r i v i a l empty  square  configuration with  Robbie  to  model of  the user  single  which  a r e t h e g l o b a l and d i s p l a y  The d i s p l a y commands a l l o w  information.  large  objects  himself, there  configuration  commands  35  Studies  t h e a c t i o n and comparative  by R o b b i e  which  Robbie's  Simulation  control  the other  by t h e u s e r , consisting  ROSS of  i n the middle,  a  facing  north.  A complete ROSS  record  (snapshots  excluded),  written  i n a debugging  during  or  later,  every  in  after  This  snapshot  various can  be  between other  t h e user  and  information, i s  viewed  at  To a i d i n r e v i e w i n g  i s numbered and a r e f e r e n c e  to  any an i t  time  episode placed  file.  Commands  The character this  file.  and  a ROSS e p i s o d e .  t h e debugging  3.1,2  of the conversation  word  correctly.  first  word  position suffice No  of  a  of a line,  command  must  and t h e f i r s t  f o r ROSS t o i n t e r p r e t  blank  should  appear  begin three  the r e s t  between  a  i n the f i r s t characters  of  o f t h e command colon  and  a  Robot  following the  word.  I f part  non-underlined  interpret  The  t h e word  Simulation  o f a word  part  may  36  Studies  be  or phrase  i s underlined  omitted:  ROSS  will  then s t i l l  correctly.  commands a r e d e s c r i b e d  i n four  groups:  Global Action Comparative Display  Global  .  Commands  FIXED  An user of  interactive  to specify  the f o l l o w i n g  procedure  the fixed  i s entered  part  fixed-format  which  prompts t h e  o f t h e e n v i r o n m e n t by  means  sub-commands.  CHARS=ch Causes a l l sguares and  COL  single  sub-commands  character  i n subsequent  t o be l a b e l l e d  *ch', until  sub-command  i s received.  sub-command  the character  character  i s  character. Example:  specified  referred  with the  another  I n absence  as  CHARS  o f a CHARS  'B' i s a s s u m e d . to  ROW  the  This f i l l  Robot  Simulation  Studies  37  CHARS=H  BOS=x10x2,COL=y*Uy2 Labels  squares with  illustrated are  two  leading  the  f i l l  character,  i n t h e examples. Here digit  zero,  integers,  x 1 , x2,y1,y2  possibly  and £ i s r e p l a c e d  as  by  with  a  either  or '-». Examples: ROW=02- 12,COL = 0 5 - 1 7 Causes  a l ls q u a r e s i n the r e c t a n g l e  by, and i n c l u d i n g , to  17  to  be  delimited  r o w s 2 t o 12 a n d c o l u m n s  labelled  with  squares  at  the current  5 f i l l  character. ROW=0 2&12,COL=0 5&17 Causes  the four  (2,17),  (12,5),  the  character.  f i l l  (12,17)  positions  (2,5),  t o be l a b e l l e d  with  ROH=02S12 COl=0 5-17 f  Labels  the squares  inclusive  i n  from  rows  2  positions and  12  5  with  to the  17 f i l l  character.  POSITION=x,y Places  Robbie i n square  (x,y).  ORIENTATION=d Causes  Robbie t o face  north,  east,  south,  or  Robot  west  Simulation  according  Studies  as  38  the d i g i t  d i s 0 , 1 , 2 . , or 3  respectively.  MARKER=m Causes  Robbie's motions  t o be r e c o r d e d  s n a p s h o t s by t h e c h a r a c t e r  i n the  ' m»,  Example: M&RKER=.  FIN  STOP  Both c a u s e c o n t r o l t o r e t u r n  t o the user.  MOBILE An user  interactive  specifications.  self-explanatory;  conform or  which  prompts t h e  to s p e c i f y the mobile o b j e c t s i n the environment  free-format is  procedure i s entered  In terminal  f o r batch  usage  t o t h e f o l l o w i n g grammar.  phrase  separate  enclosed  by  the i n p u t c a r d s  ::= m o b j l i s t  mobjlist  ::= m o b j s p e c  mobjspec  ::= t l h c  terminator  | mobjlist  rectlist  ::= " x , y " ::= r e c t  rect  «'xoff,yoff,xdim,ydim"  ::=  xdim,ydim  | rectlist  ::- p o s i t i v e  mobjspec  terminator  rectlist  rect  integer  must  characters  marks must a p p e a r on a  card.  raobileobjects  tlhc  mode t b i s p r o c e d u r e  A sequence o f  quotation  with  Robot Simulation Studies  x,y,xoff,yoff terminator  In  ::- i n t e g e r  ::=  " F I N " | "STOP"  the above, "x,y" gives  left-hand  corner  of  "xoff,yoff,xdim,ydim" dimensions currently it's  example  specifies  mobile that  a  i s t o be p a r t  of  quadrant  a  object;  f  U-shaped  28-by-28  t h e MOBILE  3f  object  (xoff,yoff)  object  environment,  object  from  i n  i n the north  the  command.  2  16,18 0,0,4,2  3^2^2/2 0,4,4,2 FIN FIN  Terminates  execution  o f ROSS  Terminates  execution  and s i g n s  south  the following  FIN  STOP  and  of the mobile  0,0,2,6 f  top  with  5,5  2 2  the  rectangle  of  t o s p e c i f y a T-shaped  and a  might f o l l o w  new  position  corner.  west guadrant of  the  d e f i n e d , a t an o f f s e t  top left-hand  For  a  xdim-by-ydim being  39  .  SIGNCFF the user o f f .  east cards  Robot s i m u l a t i o n  MTS  Interrupts execution can  be  restarted with  printed  c o p y on t h e  40  Studies  and r e t u r n s  control to  a $RESTABT, T h i s  lineprinter  of  MTS.  ROSS  i s u s e f u l to get a  the  recent  terminal  display.  SET  STEPS=  stepbd  SET  TURNS=  turnbd  These  commands  turns  that  They  c a n be r e g a r d e d  if  one  user  Robbie  may  set  the  take  maximum  i n the course  as the f u e l  new  values  cf  one  allowance.  of these bounds i s exceeded  to enter  number o f s t e p s  ROSS  and  episode.  At a t e r m i n a l ,  will  prompt  the  f o r them.  RESET Causes may  a l l knowledge about the environment  have g a i n e d  through  previous  explorations  to  that  Robbie  be  wiped  out.  Action  commands  These  come i n t h r e e  Level  1  Consists  levels.  of  t h e most  DROP, S T E P , T U R N , F A C E ,  Level  2  Consists  Level  .3  Of  most  basic  commands:  LINEAR.  o f t h e commands F I N D ,  interest,  PICKUP,  this  FOLLOW.  consists  of  the  Robot S i m u l a t i o n  Studies  c o m m a n d s HOME, WALK,  EXPLORE.  I  Level  PICKUP Causes  Robbie  facing,  i f any; otherwise  array "see"  MSENSE under  enables being in  held  the the  movable  command  if  fails.  that The  on t h e s n a p s h o t s a l l o w s  whatever  movable  object  MSENSE  falling  into  i s undefined  he i s h o l d i n g holes.  - denoted  he i s 3-by-3  appears  Robbie  to drop  a n y . MSENSE b e c o m e s  STEP  Causes facing, is  Robbie  provided  holding  the  him t o  and  thus  When n o o b j e c t i s by t h e  signs  step  collision  one s t e p  the square object,  c a n be t a k e n ; between  :rotation  he was  holding,  also,  i n the d i r e c t i o n  i n front  o f him i s b l a n k .  MSENSE i s u s e d  to t e l l  the step  fail  the object  being  the environment.  Is e q u i v a l e n t  object  undefined.  to take  a movable  whatever  STEP :n  TURN  object  which  him t o avoid  Causes  in  pickup  the snapshots.  DROP  a  to  t o n STEP commands.  might held  he  I f he whether  because  and o t h e r  i s  of  objects  Robot S i m u l a t i o n  Causes degrees If  held  to  turn  left,  according as <rotaticn>  Robbie  command  FACE  Robbie  Studies  i s  may  with  right,  or through  i s LEFT, RIGHT,  currently  holding  through  a collision  fail  42  a  or  movable of  the  180  ABOUT.  object object  this being  the environment.  :direction Causes according Just  Robbie  to  as < d i r e c t i o n >  a s f o r t h e TURN  face  north,  south,  i s NORTH, SOUTH,  command, t h i s  e a s t , o r west  EAST,  or  WEST.  can f a i l .  Example: FACE  :WEST  LINEAR :x,y Causes Robbie from of out  h i s present  steps what  position  and t u r n s . h i s next  may f a i l  through  and  actions.  turn  t o move i n a n a p p r o x i m a t e l y  As each  t o ( x , y ) by e x e c u t i n g square  move s h o u l d  failure  straight  i s reached,  b e . Of c o u r s e ,  line  a  sequence  he  figures  this  command  o f any one o f t h e c o n s t i t u e n t s t e p  Example: LINEAR :3,21  Level  2  FIND : » c h ' Causes Robbie character  to search  'ch* i n a random  f o r a square manner.  labelled  with  the  Robot  Simulation  Studies  Example : FIND  :'H' C a u s e s R o b b i e  FOLLOW  : ' c h ' hand  issued  Robbie  t o note  currently  facing  a  sequence o f  point  regained,  proceeds.  He k e e p s  after  i s facing  hisstarting  continuous i s  hole.  immediately  : ' c h ' c o m m a n d , when R o b b i e  Causes is  fora  [STACK]  Usually FIND  to search  square 'ch'  a  until ring  or l e f t  i s not i n i t i a l l y  starting  point. This  movable  object  a n 'M' s q u a r e  FOLLOW  :'H»  is  object  because  convention is  done  of  edges  If the  given  will  form  as  <hand>  i f  either  back  i s no to the  i f , f o r instance,  with  a hole,  Robbie  a was  o b j e c t , a n d t h e command  an  enclosure  used,  but  order.  command  i f  :'ch» LEFT s h o u l d  in anti-clockwise  a  i s issued: be  the  command  they form be u s e d .  shape  This  i s ,  H o w e v e r , no  the clockwise  an  by  harm ring  reversed.  STACK a p p e a r s  form  fails  leading  of  the option  starting  or i f there  ring-description  automatically  'ch' squares  be  FOLLOW  i f t h e wrong  i f he  issued.  should  then  the  be t h e c a s e  o f t h e movable  the 'ch' squares  isolated  squares  edge-contact  LEFT were  F O L L O W : ' c h ' RIGHT  "ch' square,  'ch'  would  had  facing  If  of  the  according  he  sequence  square.  d e s c r i p t i o n as he  R I G H T o r L E F T r e s p e c t i v e l y . T h e command  continuous  'ch'  ' c h ' ,to f o l l o w a  is  facing a  successful  p o s i t i o n and t h e n ,  squares  to the right  a  labelled  generating  a  an i s o l a t e d  then  i f i t turns  object,  out that  the object's  ring  Robot  description is,  i sstacked  i t i splaced  hole  stack  otherwise  Simulation  according  on t h e f i x e d  according  i ti splaced  Studies  44  to theobject's  object,  movable  as thecharacter on t h e o d d i t y  type.  That  object,  or  ' c h ' i s B , M, o r H;  stack.  Example:  FOLLOW  :'H' LEFT  STACK  Level 3  HOME [ NEW  ]  This  i susually  observable  thef i r s t  action  action  i s equivalent  F I N D : ' B 1 , FOLLOW: ' B ' R I G H T , w i t h object  so  enclosure, pair  of  failure found  followed i t s ring  to the pair  isolated  description i s  o f some s o r t o c c u r s  i f the  instead and  i srepeated  or t h e boundary  o f commands  that  object  stacked  o f an  the  until  same  either  i s successfully  and f o l l o w e d .  the  g e n e r a t e s t h e MRTs o f t h e e n v i r o n m e n t  currentmrt  pointer  t o thef i r s t  contains  Robbie. Also, theintersection  between  overlapping  environment SET  issued. I t s  the proviso  commands r e - i s s u e d . T h i s  Then R o b b i e sets  i s an  command  will  MRTs  are  be d i s p l a y e d  found.  unless  MRT f o u n d  rectangles The  MRTs  suppressed  and which  (IRTs ) of the  through  PR co and. commands a r e i s s u e d , t h e s e c o n d I fI N T t w om mHOME  one  a will  Robot S i m u l a t i o n  be  i n t e r p r e t e d a s an e r r o r a n d w i l l  option one  NEW  appears. This  episode,  change  :MRT  the  environment, plans  Robbie  be i g n o r e d i fduring  commands  f o r moving  about  unless  the  the course of  are  a n d we w a n t R o b b i e  to create  i .  He w i l l  a  single isolated  avoiding  issued  to  t o be a b l e t o  i n t h e new e n v i r o n m e n t .  anything  terminal  and execute a plan  successfully sidestep  unpredictable.  non-blank larger  The p l a n  display  command. A t r a c e  WALK  45  i Causes  the  i s useful  new F I X E D o r M O B I L E  make c o r r e c t  WALK  Studies  debugging  an o b s t a c l e  s q u a r e , whereas  a r e net zero, created  screen  will  unless  of the execution  to reach  MRT  consisting  of  h i s chances o f  but small be  and r a t h e r  printed  on  the  s u p p r e s s e d b y a SET P R I N T of the  plan  appears  i n  file.  : x,y If  (x,y) l i e s  command the  WALK :MRT  first  command  i n  MRT  i followed  i  , this  i sequivalent  b y t h e command L I N E A R  to the  :x,y i f  i s successful.  EXPLORE Causes objects that  Robbie  that  i s  non-blank  might  not  part  character  to  explore  be p r e s e n t .  h i s current Whenever  o f t h e boundary 'ch* ,  what  MRT  a sguare  f o r any i s  but i s labelled  essentiallly  found with  happens  a  i s  Robot S i m u l a t i o n  that  EXPLORE  the action  : MRT  FOLLOWch'  Studies  LEFT  46  STACK  i s taken.  i  This  i sequivalent  to the pair  EXPLORE  where  failure  of  original  E X P L O R E command  the  o f commands WALK  WALK:MRT  coir ma nd  i ,  causes the  to f a i l .  EXPLORE : x , y This two  i s equivalent  alternative  Robbie the  explores  updated  t o t h e command  actions.  o f 'ch' squares  the  FOLLOW^ch'  action  returned  (x,y),  MRT. I f i t f a i l s  consisting  followed  I f t h e WALK command s u c c e e d s  t h e MRT c o n t a i n i n g  current  WALK:x,y  LEFT  encountered STACK  then  or i n other  because  by  words  o f an o b s t a c l e  o n t h e way t o  i s executed  and  (x,y), control  t o the user.  EXPLORE : A L L Equivalent  to  issuing  commands, one f o r each  EXPLORE  :ROOMS { o r : S P A C E S This  MRTs  i ssimilar  with  position explored.  a  seguence  of  o f t h e MRTs i n t h e e n v i r o n m e n t .  }  t o EXPLORE:ALL, e x c e p t  dimensions  i n the lattice  EXPLORE:MRT i  at least of  MRTs  4-by-4 of  that  only  those  and occupying a t o p  the  environment  are  Robot S i m u l a t i o n  The  IS?  comparative  obspec  comparator  obspec  ::=  CONGRENT TO  ::= o b t y p e  : obno  obtype  ::= O B J E C T  | MOBILE  obno  ::=  | SIMILAR  | BOLE  | OtDITY  integer  I S ? command  causes t h e shapes  environment  to  congruence,  similarity,  simple  ] C_CONGRUENT TO  | CONTAINABLE I N  obspec  The  47  command  comparator  TO  Studies  be  compared  for  of two o b j e c t s congruence,  i n the corner-  o r c o n t a i n m e n t . The r e s p o n s e i sa  "yes" or "no".  Examples: Suppose t h a t  Robbie  knows o f two f i x e d  OBJECT  2 S OBJECT  OBJECT  5, two h o l e s  object  whose s q u a r e s a r e l a b e l l e d  8. Then  3 , two m o v a b l e o b j e c t s called  the following  IS?  0BJECT:2  CONGRUENT  IS?  M0BILE:4  SIMILAR  IS?  MOBILE:4  C_CONGRUENT  IS?  MOBILE  OBJECT  are valid  with  Qs a n d c a l l e d  comparative  TO ODDITY :8  However, t h e next  OBJECT  OBJECT  H0LE:6  : 5 CONTAINABLE  called  called  6 &  TO M O B I L E :4  TO  objects  I N HOLE : 7  conrcand would  fail.  7,  and  commands.  4 S one  OBJECT  Robot  IS?  Simulation  M O B I L E : 5 CONGRUENT TO HOLE In  the  case  Studies  : 8  o f I S ? .... C O N T A I N A B L E I N . . .  details  of the l a t t i c e  of  objects  being  are produced,  SET  48  compared  MRTs  constructed unless  commands,  for  the  suppressed  two by a  command.  JLispifLI commands  DISPLAY Causes  a  snapshot  of the current  c o n f i g u r a t i o n t o be  displayed.  SET  ACTDSW  SET  INTDSW  SET  DEBUGSW  SET  PRINTSW  There  control,  switches  For  switches  the production  after ( INTDSW  completion  every  of snapshots  ROSS  after  completion  action i s to  the  o f an a c t i o n could  production  that  was c a l l e d  be s e t s o t h a t  a snapshot  of  would  of an  produce  a  display  snapshots internally.  every  appear.  that  (ACTDSW)  a c t i o n command. The i n t e r n a l  ) control  action occurred  within  The a c t i o n d i s p l a y s w i t c h e s  i n s t a n c e , t h e INTDSW  LINEAR  of  command. The d e f a u l t s y s t e m  snapshot  after  banks  ROSS'S o u t p u t .  control  action  are four  time  This  a  could  Robot S i m u l a t i o n  be  u s e f u l f o r watching Robbie's  WALK  command, f o r e x a m p l e .  produce  no s n a p s h o t  The  debug, s w i t c h e s  debugging  The  after  information  £rint  an a c t i o n  overlapping  of  an I S ? . . .  CONTAINABLE  action  a  i s to  internally.  MRTs,  o f MRTs  i sf o ra l lthe print  changed  by a SET PRINTSW  of the l i s t  intersection  the plans  produced f o r  produced  switches  of  the  . . . . command,  default  settings,  executing  file.  or c f an o b j e c t ,  WALK c o m m a n d , t h e l a t t i c e  switch  i scalled  control the printing  a  A s e t command  while  The d e f a u l t system  on t h e debugging  switches  between  progress  ( DEBUGSW ) c o n t r o l t h e p r i n t i n g o f  MRTs o f t h e e n v i r o n m e n t rectangles  49  Studies  and  i n the course so  on.  t o be o n . They  The  may be  command.  m u s t be f o l l o w e d  by a s e q u e n c e  a n d must be t e r m i n a t e d  of on/off  by a "STOP"  card.  Examples: SET  ACTDSW  STEPS-OFF L I N E A R=OF F WALK=ON STOP Subsequently, LINEAR  SET  INTDSW  L I N EAR=ON STOP  no  snapshot  command, b u t w i l l  appear  will after  appear a WALK  after  a STEP o r  command.  Robot  Subsequently, internally  a  Simulation  each  snapshot  time  50  Studies  the action  will  appear  LINEAR  i s  invoked  on c o m p l e t i o n  of the  action.  SET  DEBUG SW  FOLLCW=OFF EXPLOR E=0 EF STOP Suppresses the  SET  the printing  FOLLOW a n d E X P L O R E  c f debugging  information  from  procedures.  PROTSW  PLANS=0FF LATTICE=0N STOP Suppresses in  the course  printout  the printing  of any p l a n s t h a t  m i g h t be  made  o f a WALK o r E X P L O R E c o m m a n d , a n d e n s u r e s t h e  o f any l a t t i c e  constructed i n the course  o f an I S ?  command.  PRINT  STACK Causes four  3.1.3  Global  the  s t a c k s t o be  names  printed.  Summary o f ROSS  commands  of  commands  the objects  on e a c h  of  Robbie's  Robot S i m u l a t i o n  FIXED  Must  be f o l l o w e d  51  Studies  by a s e q u e n c e o f  fixed  format  sub-  commands, MOBILE  Must  be  followe  specifications. MTS RESET SET  STEPS=  stepbd  SET  TURNS=  turnbd  SIGNOFF STOP  Action  commandsx  level  J  commands, l e v e l  2  PICKUP DROP STEP [ : n ] TURN  :rotation  FACE  :direction  LINEAR :x,y  Action FIND  :'c h '  FOLLOW  :'ch« hand  Action  commands^, l e v e l  HOME [ N E W ]  [STACK]  3  by  a  sequence  of  mobile  object  Robot  WALK  52  Studies  rwmode wmode  EXPLORE  MRT  i  | x,y  MRT  i | x , y | A L L | ROOMS  :emode emode  Comparative IS?  Simulation  obspec  ^is£i9Ll  | SPACES  coinmand comparator  obspec  commands  CIS FLAY SET  ACTDSW  SET  INTDSW  SET  DEBUGSW  SET  PRINTSW  Set  commands m u s t be f o l l o w e d  settings PRINT  with  of  .switch  "STOP".  STACKS  3.1.4  Sample  The episodes. added  terminated  by a s e q u e n c e  following  pages  The b i g g e s t  later  prefixed  output  with  are  contain  omissions  enclosed  the sign  ">".  by  condensed  are-marked "$"  versions with  signs.  o f t w o ROSS  "...".  User  Comments  commands a r e  Robot  In  the f i r s t  direct  control  carries  out  second  a  answers of  Note world  learns  by  objects,  *WELCOME TO >SET  1","M0BJ  a  movable  objects  I n the and  2",  Robbie  "OBJECT  ... are to  ROSS: RECORD OF  holes  EPISODE  AT  under  the  ROME c o m m a n d ,  command. I n Through  and two  explore  one  hole,  IS?  19  22  names  used  the movable  04:55 P.M.  the  objects  ... are  his explorations  or o d d i t i e s  by  f o r the  encountered.  JAN.  20,  ENTERED  SNAP #  $ mobj  3 $  4  >TURN:ABOUT >STEP  :6  SNAP*  6  >DROP >FACE:WEST  $ t h e n e x t few  in  names  :SOUTH  >PICKUP  and  questions,  :19,22  * LINEAR  the  out.  "OBJECT 2 " ,  i n the course of  movable o b j e c t s ,  last  printed  1",  a  EXPLORE  different.  procedures to refer whereas  around  then, after by  is slightly of four  53  STEPS=1000  > L I N EAR  >FACE  followed  MRTs a r e c o n s t r u c t e d  simulation  generated  and  s i x IS? questions.  t h a t "MOBJ  Studies  moves o b j e c t s  user,  WALK command  environment,  fixed  the  the environment  lattices  the  episode Robbie of  commands R o b b i e then  Simulation  commands manoeuvre  robbie  1972  ROBOT PICKUP  SIMULATION  STUDIES  OK  SN AP#  4  1 B B B B B B B B B B B B B B B B B B B B B B B B B B B B  2 3 4 5 6 7 8 9 1011121314 1516171819202122232425262728 B B B B B B B 3 B B E B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B E E B B B B B B B B B B B B B B B B B B B B B B B B B B B B E B B B M M M M M M M M B B M M M W E M M M M M B B B M M M M H H B B B H E M M M B B H H H H a B M M M E B H H H H H E $ i n o b j 4$ B B B B B B B B B B B B B B E B B B B B E B B B B B B • B B B B B B B B B B B B <* B B B a M M M M M M M B B B B B M M M M M M M B B B M M M M M M M E B B B M B B M E B B M B B B E $mobj 3$ B B B B B B B B B B B B B B B B B B B B B E B B B B B B B B  Y  1 2 3 4 5 6 7 8 9 10 1 1 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 X  M M M| 3 I  M SEN SE  #FIXED #MO VA B L E  SENSE  POSITION: (19,22) O R I E N T A T I O N : SOUTH HOLDING: MOBJ 3 CURRENT MRT: U N D E F I N E D O B J E C T S KNOWN: 0 O B J E C T S KNOWN: 0 WHOLES KNOWN: 0  ROBOT 5 TH S T E P 1 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 B 9 B 10 B 1 1B 12 B 13 B 14 B 15 B 16 B 17 B 18 B 19 B 20 B 21 B 22 B 23 B 24 B 25 B 26 B 27 B 28 B  SIMULATION  STUDIES SNAP#  6  10111213141516171819202122232425262728 B B E B B B B B B B B B B B B B B B B B B B E B B B B E B B E B E B B E B B B B B B B B B B B B B B B B B B B B E B B M M M M B M M M M B B M E B B M M M M H H M B B B M M M M M M M H B M B B M M M M M M M H B M B B M M M M M" M M H B 5) B B B B « B E E B B B B * B E B • E B B B * B B E B B B B B B B B B B B B B B B E B E B B B B B B B B B B B B B B B B E B E B B E  Y  BAD 2 3 4 5 6 7 8 9 B B B B B B B B B  B B B B  B B E B B B  E B E B  B B  M M M M M M M M M M M M M M B B B B B B B B B B B B E B B B B B B B B B B B  B B  B  B B B  B B  X  |  H H |  | M M M |  I I  a I  I I  I  MSENSE  a  ] I  SENSE  ( 1 5 , 22) POSITION: O R I E N T A T I O N : NORTH 3 H O L D I N G : MOBJ C U R R E N T MRT: U N D E F I N E D 0 # F I X E D O B J E C T S KNOWN: 0 #MO V A B L E O B J E C T S KNOWN: 0 #HOLES KNOWN:  Robot  Simulation  ready >STEP  54  Studies  t o pick  up mobj 3 a g a i n .  $  :6  >PICKUP >TURN  :LEFT  SNAP*  13  >DRCP  $ mobj 3 $  >LINFA R : 19,15  $  the next robbie  half-dozen  ready  commands m a n o e u v r e  t o pick  up m o b j  4. $  $ mobj 4 5  >PICKUP >TU RN  :L EFT  SNAP#  23  >DROP  $ the next  f e w c o m m a n d s move  to  a different  it  up a g a i n .  part  o f mobj  robbie  around  4 to pick  $  >PICKUP SNAP#  27 $ user  issued  doorway  c o m m a n d s t o move m o b j 4  $  S N A P ! 30  >H OM E * FIND('B')  ENTERED  * FOLLOW{'B', 1 , ) ENTERED RING5:0BJECT  1  $ the ring  representation  environment #EDGES=  20  follows  of t h e $  thro  ROBOT TORN  LEFT 1 1 B 2 B 3 B  4  SNAP*  2 3 4 B B B  5 B  6 B  7 8 9 10111213141516171819202122232425262728 B B B B B B B B B B B B B B B. B B B B E B E  B  B  B B  B E  B  B  B B  B B  B B  B B  B B  E B  M M  W M  E B  E B  B B  M  M  M  M M  M M M  B B  B  B B B B B B B  B  M M  B B  B B B B B B B B  B B B B B B  B E B B B E  B B  STUDIES  BAD  5 6 B 7 B 8 B 9 B 10 B 1 1 B 12 B 13 B 14 B 15 B 16 B  17 18 19 20 21 22 23 24 25 26 27 28  SIMULATION  B  B B B  B  B  B  B B  B B  B  B  B E B  B  B B B  B  M  M  B B B  B B B  B  B  B B B  B  B  E  B B  B B  B B  B B  B B B B B  B  B  M  M  M M  M M  M  M  M M  M M  .  a  M M M M  B B  B  B  B  B  B  B  B  B  B  B  B  M M M M M  M  M  H M  H H  M M  M M M M  M M  H H  B B B E B E B B  B  B E B E B B B B B B B B B B  M  M M  B B B B B B B E B B  B  B  B  B  |M  M  M|  I  a  I  B  SENSE  KNOWN: KNOWN: KNOWN:  (13,18) EAST MOBJ 3 UNDEFINED 0 0 0  B  B E  B  B B  POSITION: ORIENTATION: HOLDING: C U R R E N T MRT: OBJECTS OBJECTS #HOLES  E  B B  B B  M SENSE  #FIXED #MO V A B L E  B  B  B  B  B  E  B  13  ROBOT TURN  LEFT  1 2  STUDIES  OK  1 2 B B  B 3 B 4 B 5 B 6 B 7 B 8 B 9 B 10 B 1 1 B 12 B 13 B 14 B 15 B 16 B 17 B 18 B 19 B 20 B 21 B 22 B 23 B 24 B 25 B 26 B 27 B 28 B  SIMULATION  3 4 5 6 7 8 9 B B B B B B B B  B B  B B  B B  B B  E B  B B B B  M M  M M  M M  M M M  M M M  B B  B B B  B B B  B B B  B B B  B E B  B E B  B B B  B B B  B  B  B  B  B  B  B  B  SNAP*  23  10111213141516171819202122232425262728 B B B E B B B B B B B B B B B B B B B E B B • • E • B * • B B B B B B B B E B B B B B B B B • B B B B B B B B B B B B B B B E • • B B M M M B B B * M M M M B • B B H B B M M M M a M M B B H H B H H H H H M B B B M E B H H H H H E B B B m B B B M E B B m m M B B B B B M E B B M M M M M M M B • • M M M M M M M B B • B B B M M M M M M M B B B E B B B B B B B B B B B E B B B B B E B B B B B B B B B B B B E B B B  Y  X  M  3  MSENSE  #FIXED #MOVABLE  SENSE  POSITION: (12,10) ORIEN1 ATIGN: EAST H O L D I N G : MOBJ 4 C U R R E N T MRT: UNDEFINED O B J E C T S KNOWN: 0 O B J E C T S KNOWN: 0 t H O L E S KNOWN: 0  ROBOT PICKUP  SIMULATION  STUDIES  OK  1 2 3 •4  5 6 7 8 9 10 1 1 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  1 B B B B B B B B B B B B B B B B B B B B B B B B B B B B  SNAP# 2 3 4 5 B B B B  B B B B B B  B B  6 7 8 9 1011 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 52 6 2 7 2 8 B B B B B B E B B B B B B B B B B B B B B B B B B B . » B B • B * • B B B B B B B B B B B E E B B B B . . B B B B B B B . B B B B B B B B B B B B B B • • B B B • B B B B B E . s B B H H B B B H H B H H H H H BB H H E H H B BB B BB B B B B B B B B B E E B B B B B B B B B B B B B E M , B B B B B E B B B B B E B B B B B B B B B B B E B B B B B B B B B B B B B B B B B E B B E B B B B B  M MM MM . M M M MM M  M M MMM M M MMM MM . MM M M  B B B B B B B B B B B B  M M MM MMM . . MM M MM MMM . . M MMM M MM M m  m  B B  B  B  X  |M M I  MSENSE  3  SENSE  POSITION: (11,11) O R I E N T A T I O N : SOUTH HOLDING: MOBJ 4 C U R R E N T MRT: U N D E F I N E D  #FIXED  OBJECTS  KNOWS:  0  •MOVABLE  OBJECTS ftHOLES  KNOWN: KNOWN:  0 0  27  ROBOT 3  SIMULATION  STUDIES  S T E P OK  1 2 3 4 5 6 7 8 9 10 1 1 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  SNAP*  1 B B B B B B B B B B B B B B B B B B B B B B B B B B  2 3 4 5 6 7 8 9 1011121314 1516171819202122232425262728 B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B • B * • • B B B B B E E B B B B B B E B B E B E B B B . B B B B B B B E B B B * B B B B B B B B B B B B B B B B E B B M M M B M 'M M M M B B M M M M B M M M M M B B M M M M H H B M M R H B B B B B H H H R H B E B H B H B H B B B B B B B B B B B B B B B M E B B B B E E B B B B B' M B B B B B B B B B B B B M E » B B M M M M M M M B • M M M M M M M E B B • B B M M M M M M M B M S -a • B B E M M M B B B B B B B B B B B E B B B B B B B B B B B B B B B B B B B B B B B B B B E B E B B B m  m  X  IM M I  MSENSE  #FIXED #MO VABLE  a  SENSE  P O S I T I O N : ( 2 2 , 8) O R I E S T A T I G N : WEST HOLDING: MOBJ 4 CURRENT MRT: U N D E F I N E D O B J E C T S KNOWN: 0 O B J E C T S KNOWN: 0 #HOL ES KNOWN: 0  30 Y  Robot S i m u l a t i o n  TLHC  HEAD  0  HAS COORDS  0  P O I N T S TO  R I N G OF EDGES EDGE  2  EDGE  55  Studies  2  11  FOLLOWS  11  STEPS=  4  T0RN=  -1  EDGE 12  STEPS=  9  TUBN=  1  •» • »  * THE  RING R E P . OF "HOME" I S C A L L E D O B J E C T 1  MRTS OF O B J E C T MRT  1  FOLLOW.. TOP,X=  2;  6  L E F T , Y=15 ;  RIGHT , Y = 1 7 ;  M ST 5  L EFT,Y= 1 5 ;  BOTTOM, X = 2 8 ;  RIGHT,Y=28;  LEFT,Y= 2;  BOTTOM,X=  RIGHT,Y=28;  TOP,X=  8;  • • •  MRT  1  END OF  MRTS.  OUTOLAP:OVERLAPS MRTL1ST  6;  BETWEEN  MRTS OF  OBJECT 1  FOLLOWS  MRT 6 OVERLAPS  MRT 1  WITH  INTERSECTION IRT 2  OVERLAPS  MRT 5  WITH  INTERSECTION IRT 1  MRT  WITH  INTERSECTION IRT 1  MRT 5 OVERLAPS  6  TOP,X=  2;  Robot  Simulation  Studies  56  MRT 1 OVERLAPS  MRT  2  WITH  INTERSECTION  IRT 5  OVERLAPS  MRT  6  WITH  INTERSECTION  IRT 2  IRTSTACK  FOLLOWS  IRT  5  L E F T , Y= 9;  BOTTOM, X =  4;  R I G H T , Y= 11 ;  1  L E F T , Y =13 ;  BOTTOM,X=26;  RIGHT,Y=15;  TOP,X= 0;  • •• IRT  OUTOLAP:END SNAP#  32  >WALK  TO  :MRT  5  WALKA:SEARCHING DETAILS STARTS  FOR  OF  1  THROUGH  MOVE THROUGH ENDS  •  MRT  LINEAR  THRO  1  INTO  IRT 2  MRT  INTO  IRT 1  6  3  DETAILS STARTS  INTO  IRT 2  INTO  I ET 1  15 E N T E R E D THRO  :MRT  EXPLORE{-1,  MRT 1 IRT 2  EXPLAN--MOVING  >EXPLORE  MRT 1  IN MRT 5  EXPLAN:MOVING MOVE:  5  PLAN:  I N MRT  MOVE  MRT  MRT  6  3  3) :S EARCHIN G FOR OF  PLAN:  IN MRT  5  MRT  3  TOP,X= 6;  ROBOT HOME:SETTLED  1 2 3 4 5 6 7 8 9 10  SIMULATION  STUDIES  IN OK  SNAP# 3 2  1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728 B B B B B B B B B B . B B B B B B B B B B B B B B . B B B B B . . . . . . . . . . . . . . . . . . . . . . . . . . E B . B . B B . B . E B . . . . . . . . . . . . 3 . . . . . . . . B B B B B B E E B B B . . B B . . . B B B B B B B B B B B E B B B B B E E B B B . . B B . . B B B B B B B B B B B B B B B B B . . B B . . B B . . B B .  MMM M M M M M M M M M 1 1 B . MMMMM . B B . MMMM H H . B 1 2 B . MM . B B . H H . B  13 B . , 14 B . 15B 1 6 B B B B B B B B 1 7 B B B B B B E B 1 8 B B B B B B B B 19B  20 B . 21 B . 22 B 23 B 24 B 25 B 26 B 27 B 2 8 B  . . . . .  . B B . . B B . . . . B B . B B . . B B . B B . . B B . B B . . B B . . . . . B B .  H H H H H . B H H H H H . B . B M . B M . B M .. B . B  MMMMMMM . B B . MMMMMMM . B B . MMMMMMM  M. . . . . . . . . .  B B B B B B B B B B B B B B B B B B B  MMM  B B B B B B B  . . . . .  . . . . . . B B B B B B B B B B B  B  X  %  % %\  |  B|  % 3 %|  I  n) B |  |  |  % % %\  MSENSE POSITION: ORIENTATION: HOLDING: CURRENT MRT: # F I X E D O B J E C T S KNOWN: • M O V A B L E O B J E C T S KNOWN: #HOLES KNOWN:  . E . B  SENSE ( 5,13) EAST NOTHING MRT 1 0 0 0  E B E B E B E  Y  . B  Robot  Simulation  Studies  MOVE THROUGH MRT 5  INT0 IRT 1  MOVE THROUGH MRT 6  INTO IRT 2  MOVE THROUGH MRT 1  INTO  MOVE THROUGH MRT 2  INTO IRT 4  IRT 5  ENDS IN MRT 3  EXPLAN:MOVING  THRO MRT 5  MOVE: MRT 5  IRT  * LINEAR  INTO 1ST 1  1  17 15 ENTERED  • -» *  *  *  • •*  LINEAR  12  7 ENTERED  * FOLLOW('M•,- 1 , ) ENTERED  RING5:OBJECT 2 #EDGES = TLHC -»  6  0  HAS COORDS  0  POINTS TO  10  4  *  HEAD  EDGE 24  * » *  • • •  RING OF EDGES FOLLOWS EDGE 24  STEPS=  2  TURN=  * XPLMRT : FOUND" M" OBJECT *  EXPLORE(-1, 3):XPLMRT  SNAP* 34  FAILED  -1  ROBOT EXPLORE  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  MRT 1 B B B B B B B B B B B B B B B B B B B B B B B B B B B B  SIMULATION  STUDIES  3 BAD  SNAP* 34  2 3 4 5 6 7 8 9 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 B B B B E B B B B B B B B B B B B B B B B B B E B B B B a B B • B B • B B B B B B B B B B B B B B B B B B B B B B B B B B B B E B B B B • B B • B B B E B B B B B B B B B B B M M M B B B * B B B M M M M • M M M M M • M M M M B E E B •B • M M M M M H H B M M a * B B • • , H H H H H B m B B * B B B H H H H H B B B „ B B M B B B B B B B B B B M B B B B B B B B B B E B • • • M B B B B B B B B B B B B B B M M M M M M M E B M M M M M M M B B M M M M M M M B B B B B B M E B E M M M B B B B B B B B B B B B B B 3 E B B B B B B B B B B B B B B B B B B B B B B B  .  m  m  m  m  X  \% % %\ | % 2 %| \% % %]  MSENSE  |M |MS |  SENSE  POSITION: ( 1 2 , 9) O R I E N T A T I O N : NORTH HOLDING: NOTHING CURRENT MRT: MRT 3 # F I X E D O B J E C T S KNOWN: 0 #MO V A B L E O B J E C T S KNOWN: 1 #H01ES KNOWN: 0  Y  Robot S i m u l a t i o n  Studies  58  >STOF * ACTS  FINISHED  T=2.19  DR=0  The  $ cputime  second  episode  •WELCOME TO R O S S :  used  by e p i s o d e  >EXPLORE  RECORD OF E P I S O D E AT  0 4 : 4 1 P.M.  2  :MRT  3  * X PLM RT: FO UN D"M" O B J E C T RING5:OBJECT >EXPLORE *  3  :MRT  5  XPLM RT:FO UN D"K"OBJECT  RING5:OBJECT 4 >EXPLORE *  XPLMRT:FOUND"M"OBJ ECT  RING5:OBJECT  5  >EXPLORE *  XPLMRT:FOUND"H"OBJECT  RING5:OBJECT SNAP#  6  8  >IS? MOBILE:2 CONGR O B J E C T 0 STEPS  CONGRUENT TO 2  OBJECT  F A I L E D AT  3  EDGE 24  MOBILE:3 :ENTERED EDGE 3 0  * *»  * NO,MOBILE  2.19  seconds  $  follows.  >EXFLORE RING5:OBJECT  was  2 I S ' N T CONGRUENT TO  MOBILE  3  J A N . 2 9 , 1972  ROBOT EXPLORE M R T 5 1 1 . 2 B 3 B 4 B 5 B 6 B 7 B 8B 9B  SIMULATION  STUDIES  BAD  SNAP*  8  2 3 4 5 6 7 8 9 10111213141516171819202122232425262728 B B B B B E B B B B B B B B B B B B B E B B E B B B B B B E B B B E B B B B B B B B B E E B B B B B B B B B B B B B B B B E B B B B B B B B B B B B B B B B B B B B . . . . . . . . . B B B . M M M B  Y  10B  M M M M M  B B  M M M M  11  M M M M M  B B  M M M M  B  12 B 13 B  MM  .  3  .  B  . H H . B  B B $cbject 5$  H H . B  B B  . H H H H H H .  B  14 B 15 B  B B B B  . H H H H H H . . . . . . . . .  B B  1 6 B B B B B E E B B B  B B  1 7 B B B B B B B B B B 1 8 B B B B E E E B B B  E B B B  19  Sobject  3$  .  B  2 0 B 21  B  22 B  23 B 24 B  25 B  M M M  $ c b j e c t 6$ B  B B  M M M M M M M  B  B B  M M M M M M M  B  B B  M M M M M M M  B B  M  B B  M M M  B B  S o b j e c t 2$.  E E  B  B  Sobject 4 $  B B  E B  E  26 B B B B 27 B B B E 2 8 B B B B B B B B B B B B B B B B B B B B B B B B B B B B X  \%  % %\  MSENSE  |  |  SENSE  POSITION: (10,26) O R I E N T A T I O N : WEST H O L D I N G : NOTHING CURRENT MRT: MRT 5 # F I X E D O B J E C T S KNOWN: 0 # M 0 V A EL E O B J E C T S KNOWN: 4 #HOLES KNOWN: 1  Robot Simulation Studies  59  >IS? M0BILE:2 SIMILAR TO MOBILE:3 OBJECT 3  SIMILAR OBJECT 2  : ENTERED EDGE  0 TURNS FAILED AT EDGE 24 1 STEPS NOT PROP. AT EDGE 22  * NC,MOBI.LE  30  EDGE 31  2 IS' NT SIMILAR TO  MOBILE  3  >IS? MOBILE:2 SIMILAR TO HOLE:6 SIMILAR OBJECT 2  OBJECT 6  :ENTERED  1 TURNS FAILED AT EDGE 21  EDGE 51  •• •  * LAST ALLOCATION OF MOV_PAR FOLLOWS: * TURN  LEFT, MOVE 10 STEPS UP  *YES,MOBILE  2  IS  , AND 17 STEPS RIGHT.  SIMILAR TO  HOLE  6  >IS? MOBILE:3 C_CON TO HOLE:6 C_CONGR OBJECT 3  OBJECT 6  0 TURNS FAILED AT EDGE 30  CENTERED EDGE 51  * LAST ALLOCATION OF MOV_PAR FOLLOWS: * TURN  LEFT, MOVE  *YES,MOBILE  3  IS  0 STEPS DOWN, AND 15 STEPS RIGHT. C_CONGRUENT TO HOLE  6  >IS? MOBILE:3 CONTAINABLE IN MOBILE:4 CONTAIN OBJECT 3  OBJECT 4  :ENTERED  CONTAIN OBJECT 3  OBJECT 4  :CONSTRUCTING MRTLIST FOR OBJECT 4  MRTS OF OBJECT 4  FOLLOW.  Robot S i m u l a t i o n  LEFT,Y=16;  BOTTOM,X=22;  RIGHT,1=23;  T0P,X=19;  »JT11  LEFT,Y=19;  BOTTOM,X=22;  RIGHT,Y=20;  TOP,X=16;  MRTS.  CONTAIN  OBJECT 3  LATCONS  ENTERED  OBJECT  L A T T I C E OF O B J E C T  BNODE 8  4  4  :CONSTRUCTING  LATTICE  FOR  FOLLOWS  $ BNODES a r e e q u i v a l e n c e  BN0DE 7 BNODE  60  MRT12  ENjD OF  *  Studies  classes  o f MRTs $  DETAILS  ENODE 8 XDIM=  6  EQUIVCT= HAS THE  YDIM =  1  1 FOLLOWING  MRTS  MRT 11 HAS  NO  SUCCESSORS  BNODE 7 XDIH=  3  EQUIVCT= HAS  THE  YDIM =  7  1 FOLLOWING  MRTS  MRT 12 HAS  NO  •CONTAIN *  SUCCESSORS  OBJECT 3  OBJECT  4  L A S T A L L O C A T I O N OF MOV_PAR  * TURN -NONE, MOVE •YES,MOBILE  >IS?  MOBILE:5  3  IS  :SUCCESS  CONTAINED  IN  CT3  FOLLOWS:  9 S T E P S DOWN, AND  CONTAINABLE  AT S T E P  IN  HOLE:6  12 S T E P S  MOBILE  4  RIGHT.  OBJECT 4  Robot Simulation Studies  61  CONTAIN O B J E C T 5  OBJECT 6  :ENTERED  CONTAIN O B J E C T 5  OBJECT 6  -.CONSTRUCTING M R T L I S T FOR O B J E C T 5  MRTS OF OBJECT 5  FOLLOW.  MRT15  L EFT,Y=17  BOTTOM,X =12  RIGHT , Y = 2 1 ;  MRT14  L E F T , Y=19  BOTTOM,X=10  RIGHT,1=22;  TOP,X=  9;  MRT13  L E F T , Y=19  BOTTOM/X= 12  RIGHT,Y= 2 1 ;  TOP,X=  9;  TOP,X=10;  END OF MRTS. CONTAIN O B J E C T 5 LATCCNS  OBJECT 6  :CONSTRUCTING L A T T I C E FOR O B J E C T 5  ENTERED  * L A T T I C E OF OBJECT 5  FOLLOWS  $ the top equivalence c l a s s e s i n  BNODE12  the l a t t i c e $  BNODE10 BNO.DE D E T A I L S BNODE12 XDIM=  3  EQUIVCT=  Y DIM=  2  1  HAS T H E FOLLOWING  MRTS  MRT 1 3 HAS  NO  SUCCESSORS  BNODE10 XDIM= EQUIVCT=  2  YDIM=  n  1  HAS THE FOLLOWING  MRTS  MRT 15 HAS THESE IMMEDIATE SUCCESSORS BNODE11  Robot Simulation  Studies  62  BNODE11 XDIM=  1  EQUIVCT=  Y DIM=  3  1  HAS THE FOLLOWING MRTS MRT 14 HAS NO SUCCESSORS *  •  *  THETA OF BNODE 12  IS  2  THETA OF BNODE10  IS  3  THE BEST BNODE OF A IS BNODE12 * STEP CT5:MRT13  OBJECT 6  :FAIL AT STEP CT6  5 IS * NT CONTAINED IN  HOLE  >PRINT STACK PRINTOUT OF STACKS FOLLOWS END OF STACK  $ no fixed objects known  OBJECT 5 OBJECT 4 OBJECT 3 OBJECT 2 END OF STACK  $ four movable objects $  OBJECT 6 END OF STACK  $ one hole $  END OF STACK  $ no oddity $  * END OF PR STACK  2  IS BEST- FITS INTO OBJECT 6  •CONTAIN OBJECT 5 * NO,MOBILE  WITH THETA=  6  IN  2 WAYS.  Robot Simulation Studies  3.2  63  l!£l£IL§J]£i^tion L o g i c a l l y , the system c o n s i s t s o f : The simulated world.  The simulated robot, Robbie.  Robbie's model of h i s world. To make i t i n t o a "camera"  usable  system,  there  i s , firstly,  a  to provide snapshots of the world, and to give output  showing how Robbie uses h i s model of the world,  and secondly  there i s a command i n t e r p r e t e r to accept the user's commands and pass the  them  onto  routines  Robbie (action and comparative commands) or t o  which  administer  the simulated  world  (global  commands), or to the camera (display commands). The  system  consists  About 4,700 PL/1 statements occupies  50  pages  of over 25 PL/1 e x t e r n a l procedures. are involved.  When  loaded,  ROSS  of core. This f i g u r e grows r a p i d l y when any  l i s t - p r o c e s s i n g i s done. For instance, by the end of the  first  episode l i s t e d i n s e c t i o n 3.1.4 an extra 16 pages had been used. This  figure  would  be  considerably  reduced i f a) PL/1's AREA  v a r i a b l e s had been used to keep a l l the space a l l o c a t i o n s i n one place, and b) garbage c o l l e c t i o n was places.  I t takes  about  36  seconds  done  at the appropriate  of  CPU-time to load the  program, most of which i s spent cn the PL/1  library.  However,  a f t e r l i n k e d i t i n g with the PL/1 l i b r a r y the load time i s reduced to 5 seconds. The s i n g l e d e c l a r a t i o n of most i n t e r e s t i s that of  Robot  an  MRT,  concept DCL  which  i n  Simulation  ROSS  of a rectangular  i s  the  64  Studies  programmed  equivalent  ofthe  room.  1 MRT B A S E D (MRTPTR) , 2 MRTNAME CHAR (10) , (2 Y L , 2 X B , 2 Y R , 2 X T ) F I X E D B I N ( 1 6 , 0 ) , /*BOUNDING (2 L E L I S T , 2 /*  LELIST SIDE  /*  BELIST,2  SIMLY  RE L I S T , 2  P O I N T S TO L I S T  TELIST)  PTR,  OF L E F T EDGES WH. D E F I N E  FOR B E L I S T , R E L I S T , T E L I S T * /  MRTLINK  P T R , /*FOR  M A I N T A I N I N G MRT  2  LATLINK  P T R , /*FOR  USE I N L A T T I C E * /  2  MLAP P T R , /*HEAD S L I S T INTERSECT TRACEBACK P T R ,  OF L A P N O D E S G I V I N G  /*FOR T R A C I N G  IRTBACK P T R ,  STACK*/  OVERLAP 5  PTES*/  IN 2  LEFT  OF MRT*/  2  2  LINES*/  PATHS FROM  P L A C E TO  PLACE  ENVIRON*/  /*FOR  LOCATING  CORRECT  I R T , WEEN  USING  TRACEBACK*/ 2  WAVEPTF P T R ,  2  COLOUR  The  last  /*FOR  FIXED BIN ( 1 6 , 0 ) ;  four  entries  path-finding  algorithm  removed  an i m p r o v e d  easy  t o store  The of  with  /*FOR C O L O U R I N G MRTS * /  a r e used  in a rather version  i n PLANS clumsy  o f PLANS  tc  implement  f a s h i o n . They ( i t would  the  could  be  also  be  then  o l d plans).  first  CPU t i m e ,  L I N K I N G W AVEFRONT * /  episode  recorded  so t h e execution  i n 3.1.4 t o o k  time  only  2.19 s e c o n d s  o f ROSS i s n e g l i g i b l e .  Robot S i m u l a t i o n  Chaster  Studies  65  4  Conclusion  4. 1  S uroma r %  We  have  system.  The  designed robot  and implemented  can e x p l o r e  m a n n e r , a n d c a n make e l e m e n t a r y place.  The  robot  about,  and  can  unstructured simulation problems: of  plans.  our  method  to  concept We  to  have  i n a very  move  to  from  h i s world.  this  with  t h e problem  i t needs  more i n t e l l i g e n t  chapters.  two  to  t o move i n  an  of our basic  and e x e c u t i o n  of e x p l o r a t i o n , but  improvement. I n any attempts we w i l l  problems, as d e t a i l e d  be d i s c u s s e d  world  with  simple  place  In the course  dealt simplemindedly  encountered  simulation  model o f h i s w o r l d  information  Dil^ctions  will  plans  robot  r e p r e s e n t a t i o n , and t h e c r e a t i o n  of dealing  '  preceeding  new  s t u d i e s we h a v e  make t h e r o b o t  These  add  i t s environment  an e l e m e n t a r y  way a s he e x p l o r e s  some i m p o r t a n t  4.2  uses  a simple  below  f o r further  i n three  find  ourselves  i n section  facing  4.2.2..  work  p a r t s , one f o r e a c h  of the  Robot  4.2.1  Firstly,  i t i s clear  of  robot  the  references instance,  given I  intelligence, works  on  that a  concept  in  1.1  know o f  Secondly,  66  no  study  be  a  of  concerning i t might  important  mind, body  the  the  i n a paper  arguments  from  Golem  the  M.  modern  none o f  the  treatment.  For  study  to  some o f  artificial  the  classical  possible sources  world  of  ideas  into  machines.  The  Young [ Y ] , which  t r a c e s the  most  workers  entitled  automata  legends.  p s y c h o l o g i c a l and  environment,  of  written;  approaches  useful to  Robert  century  and  t o be  [ H u , K a , L c ] as  philosophical,  nineteenth  Hayes,  by  history  comprehensive  the  i n c o r p o r a t i n g knowledge of study  definitive  is s t i l l  provide  epistemology  scholarly  of  Studies  Preamble  and  for  Simulation  physiological  concerning may  also  the  be  a  useful  "Robotclogic"[Ha1],  philosophical  relations  uses  logic  ideas among source.  results  and  and  analytical  philosophy.  Thirdly, between  the  I  discussion  intuitive  intelligence also,  the  could  think,  be  and  be  concerning  linguistic  greatly  apparent  approaches  expanded;  fundamental  the  to  the  the  to  conflict artificial  issues raised  problem  of  would  language  understanding.  4.2.2  Design  In surface building  the of an  work  some o f  reported the  intelligent  here  we  have  problems i n v o l v e d robot.  I shall  merely  in either  list  scratched simulating  w h a t seem  to  me  the or to  Robot  be  the  most  There should  the  pressing  problems.  are  of  two  robot  introduced  to  is  to  the  resulting  make  a  have, new  second  exploring object  in  its  improve  efficiency  How a one  simple part  of  its its  when  overlaps  is:  How  the  descriptions  to  robot  and  this  was When  "expectations"  behave, the  surroundings,  the  be  it  to  should  utilized?  abilities, place  how  has  should  first  behaviour  section  robot  how  from  when  robots'  made i n  planning  walking  What  information  as  plan  its  actions  a rectangle  of  another?  world  in  the  when  2-by-6  rectangle  different  2.4  .  A The  discovered use  and  this  new  thus  to  place?  How  in  of  such  the  least)  to  move  2-by-6,  from  should  middle ?  The  known  the  an  plus  by  Winston[Wi]  might  be  useful  object  in  a  robot  action, of  a  basic  environment  movino. is  MRTs (at  wants  dimensions  middle is  when i t  the  used  there the  new  to  represent  Suppose  at  it  environment  three  Subtle  of  this.  its  is:  Supposing its  67  prgblems  such  the  and  doorway,  the  object,  represent instance  jnoving  is  first  surroundings,  improve  should  bits  problem  Studies  should  into  concerning  to  Easj  The  how  probes  information its  and  piece-meal  suggestion  new  these.  environment?  random  vague  a  Simulation  for  doorway question  objects?  Some  of  here.  problems an  lengths  'L'-shaped of  the  arms  of  the  'L'  room are  with  one  greater  than  Robot  the  width  one  another  the  room.  another then  by  the  way  But  s i d e s of t h e  i f the as  probably  the r o b o t  problem  will  probably  "birth"  with  procedures  for  procedures  programmed speculate  problem  A to  was  our  has  the  offset arms o f  of  from  one  the  the  doorway  sliding  block  'L*, in  a  puzzle.  been s o l v e d , t h e to be  robot  of  moving  within  rather  basic learn  spaces  'subtle'  easy,  using  these  i t will  Analysis,  is:  the concept Larry  How and at  words have be  (MRT), w i t h  space,  and  another  in a  place within a  procedures  Consequently  by  t o one  concepts  in other  considered  have "endowed" i t from  such  to  question  or  like  one  place  and  we  a r e c t a n g u l a r space  these  from  built-in,  anything  of  through  t u r n out  concept  that concepts  evolution. learn  of  moving  environment.  doorway a r e  out  formatjLon  for relating  for  be moved  with  techniques.  design the  s i d e s are f l u s h  problem?  moving p r o b l e m  the  68  'L' c o u l d  words, a s i m p l e  easy  In  two  width  moved  the  Concept  Nature,  be  solve this  known p r o b l e m - s o l v i n g  useful  t h a t the  much as t h e  f a s h i o n . In other  Once moving  t h e r e i s no  at l e a s t  should  Studies  t h e doorway. Then i f t h e  'L' can  •subtle' How  of  Simulation  hard  to  could  with  been  a  manner  robot  level  a  d e s c r i p t i o n ^ and  9.%. J E ^ c t a n c j u l o i d s h a p e s  comparison  in  through  robot  of a maximal s u b r e c t a n g l e . Travis[Tr],  be  I would are,  "learnt"  design  the  nOn-trivial  procedures? this  the  to This  Robot S i m u l a t i o n  Analyze will and  be  be  useful  bottom  between a  starting  shape  of  this I  be  provided better  operation  of  algorithm  CONTAIN  c r u d e , be  improved?  efficiencies  of  complexity comparison operation?  for  shapes  for of  sense,  which  The  top  "approximation" thesis[Wi]  might  raises  proves be  two  shapes  for  parses  an  subrectangles  a  this,  shapes  is is  a  mathematical  or  else  for  otherwise,  can  a  2.3.3,  The  would  seem  which a  on  the  very  of  algorithm the  "complexity" to  a good  containment  present of  compare i t  "complexities"  (rectanguloid)  a  i s clearly  algorithms  give  be  the  CONTAIN  indeed,  to Can  efficiency  the  problem:  containment,  i n many c o n t e x t s .  CONTAIN bound  kind  devised?  compared;  two-dimensional  or  Can  dependent  the  analyzes  task.  or  different  simplest  the  dimensions.  being  the  ( s e c t i o n 2.3.2)  More g e n e r a l l y , d e v i s e  measure and/or This  which  DECOMP  in section  i s highly  shapes  comparands.  ways  that  which  given  rectanguloid  to  of  i t s maximal  comparing  more  CONTAIN a l g o r i t h m  necessary  notion  two-dimensional operation  or  in  about i t s world.  certain  into  algorithm  rectanguloid  three  10  Again, Winston's  suspect  analysis  for  a  algorithm  sort  algorithm  fundamental  require  in a  s h a p e , any  good  whether  i n reasoning  are,  reasonably  substantially  in figure  point.  insignificant.  The  those  shapes.  rectangles  rectanguloid  arbitrary not  to a robot  rectanguloid  good  as  examples c l e a r l y  Since of  shapes such  69  Studies  will of  definition  shapes.  a fundamentally  Is  the the be the of the  complex  Robot S i m u l a t i o n  Studies  70  Generalizations Finally generalize  t h e r e a r e a whole h o s t the  system.  a l l o w s more g e n e r a l rectangular  world  shapes than r e c t a n g u l a r polygons;  the  which  extend t h e  robot  truly  autonomous  by  form  including  s u c h a s h u n g e r and t h i r s t .  ROSS If  ROSS  compilers likely  were  compiled  using  a  decrease  low-level  representations LISP:  this  considerably.  language. and w i t h  If  t h e world  The  MRTs  a  and i n t h e f a c t  in  such  the  possibility  the  and  definition  procedures  could  better  PL/1  time  would  perhaps  procedures  dealing with be  ring-  rewritten  in  r e s u l t i r a great  loss of  t h a t MRTs w o u l d no l o n g e r  appear  c o m p a c t f o r m ; i n t h e l o n g r a n g e , i t would a l l o w f o r o f new c o n c e p t s ,  modified  n o t be t o o h a r d  procedures,  by t h e r o b o t s '  l i k e l a n g u a g e would be o f g r e a t should  of  ROSS were t o be e x t e n s i v e l y  would, i n t h e s h o r t - r a n g e ,  of e f f i c i e n c y ,  created  one  a v a i l a b l e [ F r e , I B M ] , i t s s i z e and e x e c u t i o n  u s e d i t w o u l d be w o r t h w r i t i n g in  might  d i m e n s i o n s ; a l l o w a mere g e n e r a l  v a r i o u s forms of m o t i v a t i o n  4.2.3  one  F o r i n s t a n c e : u s e an e n v i r o n m e n t  t o three  o f v i s i o n ; o r make  o f ways i n w h i c h  to extend  w i t h e x p l o r i n g a n d moving  and  own p r o c e d u r e s .  use i n d e a l i n g ROSS t o i n c l u d e  problems.  with  plans  being  A PLANNERplans.  It  ways o f d e a l i n g  Robot  S.,  Simulation  Studies  71  Ai  Aida,  Cordelia, I . , a n d I v a c e v i c , N., " V i s u a l - t a c t i l e symbiotic system for stereometric pattern recognition", Second International Joint C o n f e r e n c e on A r t i f i c i a l I n t e l l i g e n c e , B r i t i s h C o m p u t e r S o c i e t y (1971) .  Am  A m a r e l , S . , "On r e p r e s e n t a t i o n s of problems cf reasoning about a c t i o n s " , J a c h i n e I n t e l l i g e n c e 3 , e d i t e d by. D.Michie, Edinburgh University Press, E d i n b u r g h (1968) , p p . 1 3 1 - 1 7 1 .  As  Asimov,  Ba1  Barrow,  Ba2  Barrow,H.G.,  Bo  B o w e r , T.G.R., " T h e o b j e c t i n t h e w o r l d of the infant", S c i e n t i f i c " A m e r i c a n , 2 2 5 , No. 4 ( O c t o b e r 1 9 7 1 ) , pp.30-38.  Bu  Burstall,  Ca  C a p e k , K a r e l , "R.U.R."  Ch  C h a p u i s , A l f r e d , and D r o z , Edmond, Automata G r i f f o n , Neuchatel (1958).  Co  Cohen,  D1  Doran,  J.E., "Experiments with a pleasure-seeking automaton". M a c h i n e I n t e l l i g e n c e 3 , e d i t e d by D. Michie, Edinburgh University Press, Edinburgh (1968), pp.131-171.  D2  Doran,  J . E . , "Planning and generalisation i n an automaton/environment system", Machine Intelligence 4 , edited by D. M i c h i e S B. M e l t z e r , American E l s e v i e r P u b l i s h i n g Company, I n c . , New Y o r k ( 1 9 6 9 ) , p p . 4 3 3 - 4 5 4 .  I s a a c , I j , Robot and The Rest P a n t h e r Books (1967,1968).  the  of  Robots  ,  H.G., and Popplestone, R.J.,"Relational descriptions i n picture-processing", Machine Intelligence 6 , e d i t e d b y B . M e l t z e r a n d D. Michie, Edinburgh University Press, Edinburgh (1971) , p p . 3 7 7 - 3 9 6 . and Salter, S.H., " D e s i g n of low-cost equipment for cognitive robot research", Masking I n t e l l i g e n c e 5 , e d i t e d b y B . M e l t z e r 8 D. Michie, American Elsevier Publishing C o m p a n y , I n c . , N.Y. ( 1 9 7 0 ) , p p . 5 5 5 - 5 6 6 .  R.M., "How a r o b o t m i g h t come t o u n d e r s t a n d i t s environment by u s i n g the a l g e b r a i c theory of decomposition of automata", Dept. Of Machine Intelligence and P e r c e p t i o n , University of E d i n b u r g h , M I P - R - 5 6 (May 1 9 6 9 ) . (1920). ,  Editions  John, Human - R o b o t s i n Myth and S c i e n c e A l l e n 5 Unwin L t d . (1966).  du  ,, G e o r g e  Robot  Simulation  72  Studies  D3  Doran,  J . E. , " P l a n n i n g and r o b o t s " , M a c h i n e I n t e l l i g e n c e 5 , e d i t e d by B. M e l t z e r & D. Michie, American Elsevier P u b l i s h i n g C o m p a n y , I n c . , N.Y. ( 1 9 7 0 ) , pp. 519-532.  DU  D o r a n , J . E . , "Some r e c e n t m o d e l s of the b r a i n " , Machine Intelligence 6 , edited by B. M e l t z e r & D. Michie, American E l s e v i e r Publishing Company, I n c . , N.Y. ( 1 9 7 1 ) , p p . 2 0 7 - 2 2 0 .  E  Ejiri,M.,  Fe1  F e l d m a n , J . A . , e t a l . , " T h e S t a n f o r d h a n d -" e y e project", Proceed ings of the International Joint Conference on Artificial I n t e l licjence , W a s h i n g t o n (May 1969) , p p . 52 1 - 5 2 6 a .  Fe2  Feldman,  Dno,T., Yoda,H., G o t o , T . , and T a k e y a s u , K . , "An i n t e l l i g e n t r o b o t w i t h c o g n i t i o n and decisionmaking ability", Second International Joint C o n f e r e n c e on A r t i f i c i a l I n t e l l i g e n c e , B r i t i s h Computer S o c i e t y (1971) , p p . 3 5 0 - 3 5 3 .  J . A . , e t a l . , "The u s e o f v i s i o n a n d m a n i p u l a t i o n to s o l v e t h e ' i n s t a n t i n s a n i t y ' p u z z l e " . Second Internationa 1 Joint Conference on Artificial Intelligence , B r i t i s h Computer S o c i e t y (1971) , pp. 359-364.  Fi1  Pikes,  R i c h a r d E., "Monitored execution produced by STRIPS ", IFIP Ljubljana, Yugoslavia (1971).  of robot Congress  Fi2  Fikes,  R i c h a r d E. , and N i l l s c n , N i l s J . , "STRIPS : a new approach t o t h e a p p l i c a t i o n o f theorem p r o v i n g t o problem s o l v i n g " , Second I n t e r n a t i o n a l J o i n t C o n f e r e n c e on A r t i f i c i ^ a l I n t e l l i g e n c e , E r i t i s h Computer S o c i e t y (1971) , p p . 6 0 8 - 6 2 0 .  Fre  Freibeurghouse, "The Multics PL/1 conference proceedings, pp. 187-199.  Fr1  Friedman,  L., " I n s t i n c t i v e behaviour and i t s computer s y n t h e s i s " , B e h a v i o u r a l S c i e n c e , _12 ( 1 9 6 7 ) , p p . 85-108.  Fr2  Friedman,  L . , "Robot c o n t r o l s t r a t e g y " . P r o c e e d i n g s of t h e International Joint Conference on Artificial I n t e l l i g e n c e , W a s h i n g t o n (May 1 9 6 9 ) , p p . 5 2 7 540.  Gr  Gregory,R.L., "The social implications of intelligent machines", Machine I n t e l l i g e n e e 6 , e d i t e d by B. Meltzer & D. Michie, American Elsevier P u b l i s h i n g C o m p a n y , I n c . , N.Y. ( 1 9 7 1 ) , p p . 3 - 1 3 .  G  de G r o o t , J . J . M . , The r e l i g i o u s s y s t e m o f C h i n a  compiler", 35, FJCC  ,  plans 197 1,  AFIPS (1969)  v o l . 4,  Robot  Leyden  Simulation  (1907),  p . 342 f f .  Hd  Hadamard,  Ha1  Hayes, P . J . , " R o b o t o l o g i c " , Machine I n t e l l i g e n c e 5 , e d i t e d b y B . M e l t z e r S D. M i c h i e , American Elsevier Publishing C o m p a n y , I n c . , N.Y. ( 1 9 7 0 ) , p p . 5 3 3 554.  Ha2  H a y e s , P . J . , "A l o g i c o f a c t i o n s " , M a c h i n e I n t e l l i g e n c e 6 , e d i t e d by B . Meltzer & D. Michie, American Elsevier P u b l i s h i n g C o m p a n y , I n c . , N.Y. ( 1 9 7 1 ) , pp. 495-520.  He  H e w i t t , C a r l , "PLANNER : a l a n g u a g e f o r m a n i p u l a t i n g m o d e l s and proving theorems in a robot", M.I.T. Project MAC, A r t i f i c i a l I n t e l l i g e n c e Memo. N o . 168 ( A u g u s t 1970).  Hu  Hume, D a v i d , Eng_ui_ry; c o n c e r n i n g human e d i t i o n dated 1777.  IBM  "OS  J ., "The mathematical (1945).  Studies  psychology of i n v e n t i o n i n the f i e l d " , Princeton University Press  understanding  PL/1 O p t i m i z i n g C o m p i l e r " , Program  ,  number  first  5734-  PL1 IBM Ka K  "OS Kant,  PL/1 Checkout C o m p i l e r " , Prograir  Immanuel,  Crjtigjje  of  pu re r e a s o n  number  5734-PL2  , first  edition  d a t e d 178l7 Kinoshita,Gen-ichiro, Shuhei,Aida, Mori,Masahiro, "Pattern recognition by an a r t i f i c i a l t a c t i l e sense", Second International Joint Conference on Artificial Int. e l l i c j e n c e , Eritish Computer S o c i e t y (1971) , p p . 3 7 6 - 3 8 4 .  L  Liao  - chai  c h i ( i ) c h . 15.  Lc  Locke,John,  Lo  Lorenz,  Mc1  M c C a r t h y , J . , E a r n e s t , L . D . , R e d d y , D.R., "A c o m p u t e r w i t h h a n d s , e y e s , 1968, pp. 329-338.  Mc2  M c C a r t h y , J . , a n d H a y e s , P . J . , "Some p h i l o s o p h i c a l p r o b l e m s from the standpoint of artificial i n t e l l i g e n c e " . Machine I n t e l l i g e n c e 4 , edited by D. Michie & B. M e l t z e r , American Elsevier P u b l i s h i n g C o m p a n y , I n c . , New Y o r k ( 1 9 6 9 ) , p p . 463-502.  Essa^ concerning p u b l i s h e d 1690.  human  uM§£§ t a j i d j L n g  K o n r a d Z . , Jin<j S o l o m c n ^ s R i n g C o m p a n y , New Y o r k (1961).  , Thomas  ^  first  Y. C r o w e l l  and V i c e n s , P . J . , and ears", FJCC  Robot S i m u l a t i o n  Studies  74  Mc3  McCarthy, J . , et a l . , Stanford Artificial Intelligence R e p o r t , P r o j e c t T e c h n i c a l R e p o r t , March 1971.  Mc4  McCarthy,  Mk  MacKay,D.M.,  Mn1  Minsky,  Marvin L., "Introduction", Semantic information Processing , edited b y M . L . M i n s k y , MIT P r e s s (1968), pp. 1-32.  Mn2  Minsky,  M a r v i n , " F o r m a n d computer s c i e n c e " , J . A . C M . No.2 ( A p r i l 1 9 7 0 ) , p p . 1 9 7 - 2 1 5 .  Mu1  Munson,  Mu2  Munson, John  Ne1  Needham,  Ne2  N e e d h a m , J o s e p h , Man a m a c h i n e , I n c . , New Y o r k ( 1 9 2 8 ) .  Nil  Nilsson,  Nils J . , and R a p h a e l , B., " P r e l i m i n a r y d e s i g n o f an i n t e l l i g e n t r o b o t " , C o m p u t e r a n d I n f o r m a t i o n S c i e n c e s , Vol™ 2 , A c a d e m i c Press I n c . , New York ( 1 9 6 7 ) , pp. 235-259.  Ni2  Nilsson,  Nils J . , "A m o b i l e a u t o m a t o n : a n a p p l i c a t i o n o f artificial intelligence techniques", ?£oceed ings pf the Inter n a t i o n a l J o i nt Conference on Artificial Intelligence , W a s h i n g t o n (May 1 9 6 9 ) , p p . 5 0 9 - 5 2 0 .  No  Noton,  Ph  Pohl,  John, "Programs with common s e n s e " (November 1958), and "Situations, actions, and causal laws" (1963), reprinted together a s Ch.7 o f Semantic Information Processing, edited by M . L . M i n s k y , MIT P r e s s ( 1 9 6 8 ) . "The epistemological problem f o r automata", Automata Studies , Annals of Mathematics Studies No. 34, Princeton Dniversity Press (1956) , p p . 2 3 5 - 2 5 1 .  _17,  John H., " T h e S R I i n t e l l i g e n t a u t o m a t o n p r o g r a m " , Stanford Research Institute, Artificial Intelligence G r o u p , T e c h n i c a l n o t e 19 (January 1970). H., " R o b o t p l a n n i n g , e x e c u t i o n , a n d m o n i t o r i n g in an uncertain environment", Second International Joint Conference on A r t i f i c i a l Intelligence , B r i t i s h Computer S o c i e t y (1971), pp. 338-349.  Joseph, Science and C i v i l i s a t i o n i n China , Volume 2: "History of Scientific Thought", C a m b r i d g e U n i v e r s i t y P r e s s (196 2 ) . W.W.Norton  and  Company  David, and Stark, Lawrence, "Eye movements and visual perception", Scientific American 224, No. 6 (June 1 9 7 1 ) , p p . 3 4 - 4 3 . I r a , "Bi-directional and problems". Technical  h e u r i s t i c search Report No. CS  i n path 136 ,  Robot  Simulation  Computer University  Studies  Science {May 1969).  75  Department,  S tanford  Po1  Popplestone,  R.J., "Freddy in Toyland", Machine IHtelligence 4 , edited by D. M i c h i e & B. M e l t z e r , American E l s e v i e r P u b l i s h i n g Company, inc., New Y o r k {1969) , p p . 4 5 5 - 4 6 2 .  Po2  Popplestone,  R . J . , "How Department Perception, (May 1971).  R1  Raphael,  R2  Raphael,  Bertram, "The r e l e v a n c e of robot research to artificial intelligence", Stanford Research Institute, Artificial Intelligence Group, T e c h n i c a l N o t e 13 (May 1 9 6 9 ) .  R3  Raphael,  Bertram, "The frame problem i n p r o b l e m - s o l v i n g s y s t e m s " , P r o c e e d i n g s A d v a n c e d Study_ Institute on Artificial Intelligence and heuristic EE°3£amming , Menaggio, I t a l y (August 1970).  Sc  Scheinman,  Se  Second  Sh  Sheu-shen  ki  Si  Sloman,  Aaron, "Interactions between philosophy and a r t i f i c i a l i n t e l l i g e n c e : the r o l e of i n t u i t i o n and non-logical reasoning i n intelligence", Second International Joint Conference on Artificial Intelligence , British Computer S o c i e t y (1971) , pp. 2 7 0 - 2 7 8 .  Su  Sutro,  Tr  Travis,Larry  U  Uhr,  Wa  W a l t e r , W . G r e y , The  Freddy c o u l d put t h i n g s t o g e t h e r " , of Machine Intelligence and University of E d i n b u r g h , MIP-R-88  Bertram, "programming a I!l2£^ssin3 68 , North ( 1 9 6 9 ) , p p . 1 5 7 5 - 1581 .  V. , "Design of a manipulator", AIM-92, Intelligence Project.  robot". Information H o l l a n d P u b l i s h i n g Co.  computer Stanford  International Joint Conference I n t e l l i g e n c e , B r i t i s h Computer Ch.  controlled Artificial  cn Artificial Society (1971).  1.  Louis L., and Kilmer, William I . , "Assembly of computers to command and control a robot", AFIPS C o n f e r e n c e P r o c e e d i n g s , 34, SJCC ( 1 9 6 9 ) , pp. 113-137. E.  Leonard, and Kochen, Manfred, "Mikrckosmos and r o b o t s " . P r o c e e d i n g s of the I n t e r n a t i o n a l J o i n t Conference on A r t i f i c i_a 1 Intelligence , Washington (May 1969) , p p . 54 1 - 5 5 5 . Living  Brain  ,  Duckworth  (1953),  and  Robot  Penguin  Simulation  Books  Studies  76  L t d . (1961).  Wi  Winston,  P a t r i c k H., " L e a r n i n g s t r u c t u r a l d e s c r i p t i o n s f r o m examples", Project MAC report TR-76, MIT ( S e p t e m b e r 1 970) .  Y  Young, Robert M., Mind^ Brain^ Nineteenth C^ntur_y O x f o r d (1970) .  and ,  Adaptation Clarendon  i n the Press,  Robot S i m u l a t i o n  Appendix  The  corner  directed starts  left-hand course,  This  of  the  of  to  with  object,  of  the  algorithm  be  In  structure  this  of  computer  lists  p o i n t e r s , one  f o r each  to  a l l the  define  this  associated trying,  bottom  with  in this  bottom  edges of  side  ;  the  left,  appendix,  as  a  data  h o w e v e r , the  The temporary  may  i s in  information  of  the  the  top  at  downwards and ring  of  i s  at  end  the  symbol  s i d e . The of  an  a  for and  keep  defined  "MRT" the  object top  has,  bottom, right  produce  stands four  of and  and  top  a  for  )  list a  data of  and  a  four list  maximal s u b r e c t a n g l e  point  the top  in  list  the  the  ring  which  pointers  in  s i d e s . Note the  helped the  that  we  concept  computer.  list are  of  a  that of  an  In  general,  confused.  parts. Part by  a  sides  i n s e c t i o n 2 . 3 . 2 , and  within  required  then  pointers  distinct  s a f e l y be  two  y-  the  ; i t produces  representation  right, to  object  bottom, r i g h t ,  side  structure  concepts  algorithm  as  top  d o e s more  an  similarly  maximal s u b r e c t a n g l e MRT  whose  containing  (left,  the  i t s origin  representation  described  subrectangle  with  directed  appendix, the  w i t h i n the  associated  x-axis  sides  17.  maximal of  has  respectively, left,  maximal subrectangles  MRTs.  DECOMP  object  edge  figure  to  algorithm  object.. A maximal s u b r e c t a n g l e  called,  i s shown i n  The  left  the  f o r d e f i n i n g the  an  right.  the  sides  used  of  the  the  corner  four  The of  system  subrectangles  left-hand  top.  d e s c r i p t i o n of  coordinate  maximal  always  77  A  D§taileJ  axis  Studies  Part  2.  1 merely A phrase  generates such  as  some "the  top left  right  sr X  bottom  Coordinate system used has i t s o r i g i n a t the t o p l e f t hand corner o f the o b j e c t , i - a x i s d i r e c t e d downward and y - a x i s d i r e c t e d t o the r i g h t . The c o o r d i n a t e s o f a few p o i n t s o f OBJA a r e l i s t e d : A ( 0 , 0 ) , E ( 4 , - 2 ) , K (7,10) .  Sides o f a maximal rectangle.  D e f i n i t i o n o f t h e coordinates o f an edge Type  Coordinates  left  Y l ,X I , X I  Diagram Yl  1  2  Xl'...  XI ... 2  bottom  Xb, Y b , Y b 1  Xb  2  Yb  right  Yr, X r , X r 1  yi  2  Yr .:*... X r  2  ... X r top  Xt,Y t , Y t 1  2  Xt ... Y;1  *2 Yt  D e f i n i t i o n s r e q u i r e d f o r the a l g o r i t h m DECOMP. F i g u r e 17.  Robot  next  right  obtained  by  edge"  Simulation  means  "the  Studies  next  right  t r a v e r s i n g the representation  (anti-clockwise)  order".  See f i g u r e s  Algorithm Input  :  The  representation  Output  :  A  list  of  edge  ring  1 8 , 19  in  i n the the  order  natural  .  DECOMP  ring  MRTs  corresponding  7 8  o f an  of  to each  this  maximal  object. object,  exactly  subrectangle  one  of  the  f o r each  edge  contains  the  object.  Part  J  Run  around  the d e s c r i p t i o n ring  four  new  f i e l d s of information.  type  of  three  f i e l d s contain  the  upon t h e t y p e  This  edge  : left,  The  first  bottom, r i g h t ,  the coordinates  as f o l l o w s  Field  Left  Yl  Xli  X12  Bottom  Xb  ?b*  Yb2  Right  Yr  Xr i  Xr 2  Top  Xt  Yt*  Yt 2  ring  "concentric"  Part  2  Dl.  S e t up  DLL  Take  t h e empty  the f i r s t  DL2. Take t h e next return  i n my  with  MRT  left  a pointer  2  Field  remaining  which  depend  3  program as the c o n s t r u c t i o n  the representation  left  o r t o p . The  :  Held-J  implemented  field  of the edge,  Type  i s  and g e n e r a t e  of a  new  ring.  list. edge  edge  L and  go  to  L . I f no m o r e  t o t h e MRT  list.  DEL left  edges, stop  and  name = OBJECT 2 Sedges - 20 a b s o l u t e l o c a t i o n o f the top l e f t hand corner, A. •  s  p o i n t e r t o edgel •  v:  Upper h a l f : the r i n g - r e p r e s e n t a t i o n o f OBJA. Lower h a l f : the r i n g o f temporary information generated by Part 1  o f the  a l g o r i t h m DECOMP, " c o n c e n t r i c " w i t h the r i n g - r e p r e s e n t a t i o n .  name : MRT 1 l e f t side :y = bottom s i d e : x = right side : y = top s i d e :x = p o i n t e r s t o edges p o i n t e r s t o edges p o i n t e r s to edges p o i n t e r s t o edges  name : MRT 7 l e f t side :y = bottom s i d e : x = right side :y = top s i d e :x = p o i n t e r s t o edges p o i n t e r s t o edges p o i n t e r s t o edges p o i n t e r s t o edges  i 0 3 9 2 defining defining defining defining  l e f t s i d e : edgel bottom s i d e : edge2, edgel4 r i g h t s i d e : edgel 5 t o p s i d e : edgel8  T h i s corresponds t o maximal subrectangle R7 o f OBJA.  ^  4 7 6 0 defining defining defining defining  l e f t s i d e : edge9, edgel7 bottom s i d e : edgel0 r i g h t s i d e : edgel3 t o p s i d e ; edgel6  T h i s corresponds t o maximal subrectangle R8 o f OBJA.  The output from DECOMP i s a l i s t o f nine MRTs, one f o r each o f the maximal subrectangles o f OBJA. Two members o f t h i s l i s t a r e shown.  Robot S i m u l a t i o n S t u d i e s  DB1. Take  the  first  bottom  edge  79  B accessible  from  L and go t o  DR1 . DB2. T a k e  t h e next bottom  bottom DR1. T a k e to DR2.  edge  e d g e , go b a c k the f i r s t  B accessible  L. I f  no  such  t o DL2.  right  edge  R accessible  from  L a n d B and go  DTO.  Take  the next  such  right  right  edge R a c c e s s i b l e  DT1. S e a r c h  through  (a)  T lies  (b)  Yl < such  (c)  from  L a n d B.  If  no  e d g e , go b a c k t o D B 2 .  DTO. L e t F a i l b o u n d = M i n [Xl*, X b ,  If  from  those  top edges T t h a t  between t h e r i g h t  Yt2  i s found  Xt > Failbound then find  edge R and t h e l e f t  edge L  f o r which  go b a c k t o DR2.  t h e maximum v a l u e o f X t f o r a l l t o p e d g e s  satisfying  (a) a n d ( b ) , a n d c a l l  first  t o p edge  such  satisfy  and Y t * < Y r .  a t o p edge  DT2. O t h e r w i s e ,  Xr2).  this  v a l u e MAXT. T a k e  the  h a v i n g X t = MAXT.  < The c o n d i t i o n X t < Minf X I 2 , X b , Xr2] now <  holds, Also,  by v i r t u e the  coordinates  DT3,  Search Yr, DT5.  rectangle  whose  sides  are  given  by  Y l , Xb, Y r , Xt i s a maximal s u b r e c t a n g l e .  t h e MRT  Xt.  o f DTO a n d DT1 ( c ) . >  I f  list such  f o r a n MRT  with  a n MRT i s f o u n d ,  sides call  given  the  >  b y Y l , Xb.,  i t MRT* a n d g o t o  DT4.  < No in  MRT  with  t h e MRT  Place MRT  a  new  l i s t .  given  sides  a  pointer  the l e f t  B,  T) .  R,  back  the r e p r e s e n t a t i o n  and  L satisfying  found  given on  Y l , Xb, Y r , X t on  the  ring  of  with  edge L  Xt#  =  back  HA X T . t o T#  pointers  the top side  T#  of  top)  between  For each cn  the  (respectively,  f o r a l l top edges  a pointer  associated  list  (respectively, bottom, r i g h t ,  (a) , (b) , a n d  i f any, place  by  the  such list  t h e MET.  Go  T T# of  back  DR2.  Place left  a pointer  edge  pointer  i s  DT4 Go  on  and  to  Definitions  L not  of p o i n t e r s side B,R)  provided  already  (from  previous  present  with  o f MRT* b a c k  (respectively,  f o r DB1,  required  (a)  XI- 1 <  (b)  Y l  1  the  to the  that  the  entries  to  a left  B#  D R 1 , DR2  bottom  :  b o t torn e d g e  edge B a f t e r  L  that  accessible  from  satisfies  Xb  < Yb2  next  DB2,  edge I , t h e f i r s t  i s the f i r s t  Given  associated  DR2.  Given a l e f t  edge  list  DT5).  back  the  the  ( r e s p e c t i v e l y , bottom, right)  defining  L  Y r , Xt has been  to the d e f i n i n g  Scan  to  by Y l , X b ,  with  Place with  80  Studies  >  MRT  o f t h e MRT  pointers  (ii)  sides  sides  found,  i)  Simulation  list.  associated  DT5.  Robot  . edge 1  bottom after  edge B  and  a bottom  accessible that  edge  from  satisfies  B accessible  L i s the f i r s t (a),  (b)  from  L,  bottom  above  and  Robot S i m u l a t i o n  Xbfl < Xb  Studies  81  .  (iii) Given the  a left first  right  (iv)  edge L right  Yl <  (d)  Xr*  Given  B  Xb  left  edge L  that  edge  and  a right  §^3§  a c c e s s i b l e from  Yb1  L and  B i s the  L,  first  satisfies  a bottom  < Yr#  <  and  Yr  edge  R a c c e s s i b l e from 1 and  R that s a t i s f i e s  Termination  B a c c e s s i b l e from  .  and  after  edge  Yr <  a  a bottom  edge a c c e s s i b l e from  edge R a f t e r  (c)  and  L and  B i s the  ( c ) , (d)  B accessible B,  first  above  the  from  next  right  L  right  edge  R#  and  ,  correctness  of  part  2 of  the  algorithm  DECORP.  2 ormi nat i o n We  omit  considered  always But  DB2  But  DR2  i s the  to  of  that  each  at  since  step  i s the  the  termination  always  returns  DB2,  DL1,  Clearly,  once gone  beyond  number o f  left  ...  DT5,  then,  the  b e c a u s e by will  the  eventually  DR2,  i f , having because  by  DL2,  control  edges i s  to  finite.  DL2.  once gone  which r e t u r n s c o n t r o l occurs  to  CI,  DL2.  i f , having  edges c o n t r o l step  steps  that returns control  r e t u r n s to  only  the  step  i f , having  termination occurs  bottom  of  terminates.  occur  DL2,  only  always  Therefore, control  only  terminates  Therefore,  number  can  returns  control  proof  independently,  Termination algorithm  the  beyond  finiteness return to  DB2, of  to  DL2.  DB2.  once gone beyond the  the  finiteness  of  DR2, the  Robot  number o f r i g h t  Simulation  edges c o n t r o l  will  D T 1 , D T 4 , a n d DT5 a r e t h e o n l y  DR1  a n d DR2 a r e t h e o n l y  beyond  D R 2 , a n d when  prove  that  or  i fcontrol  DT5 ; b u t t h i s  Finally,  that  i s obvious  we o b s e r v e  that,  eventually  s t e p s which  allovi  from  i tpasses  pass  beyond  t o DB2. B u t  control  control  t o DTO. So  i tpasses  inspection  on e n t r y  t o D L 1 , DB1, DR1, and t h e n  return  return  t o DTO t h e n  turn  82  s t e p s which  happens  passes  Studies  of  t o pass we  must  t o D T 1 , DT4 ,  the  algorithm.  t o DECOMP, c o n t r o l  DTO s o t h a t  to R2.  control  passes i n does  once  D L 2 , D B 2 , D R 2 . Q.E.D.  Correctness  The  algorithm  that  we c a n p r o v e  1)  Given  any  representing 2)  Every  MRT  subrectangle  decomp_  can  the following maximal mrt*  be proved  correct  two s t a t e m e n t s :  subrectangle  tnrt*  of  o c c u r s i n t h e output from  produced  by  DECOMP  o f OBJA.  However, t h e d e t a i l s  i n the sense  are omitted.  represents  OBJA,  an  MRT  DECOMP. some  maximal  Robot  Appendix  us  consider  would  be  plans.  At  every  one  step  180 he  could  On  as  eventually drive  by  turn  randomly  of  time  with  U.B.C. t o  the  to  Robbie  of  the  has  is .  no  83  Note  turn  of  carry  i t  would  have  P . N . E . by  of  "go  one  at  Shakespeare's  the  and  tc  world  turn  through (a,b)" at  after  a  the  position  typewriter  sonnets. [Like  making  random  :  actions  Then  reached  no  actions  four  out.  i t  and  position  his  the  that  four  right,  command  monkey  first  model of  a choice  left,  mythical a l l  plan  choosing  attempting  the  type  from  by  g i v i n g Robbie  lapse  just  get  forward,  proceed  sufficient  to  what a  i n s t a n t Robbie  i n s t a n t and  (a,b),  just  possible  degrees.  every  Studies  B  Let  take  Simulation  would  trying  turns  at  to  every  intersection. ]  Secondly world.  After  position sequence in  a  of  be  random  to  by  a  we  turns  of  that  be  turns.  behaviour  be  manner  would  and  have  plans  repetitions would  efficient  steps  can  in  that  hundred  whiskering  right  i s anything fortuitous  but  and  would  get  with  no  the  action  lost,  and  Kcnrad the  left  model of  to  memorize  him  tc  ; h o w e v e r i f he  straight.  factors  of  able  Lorenz  to  position  (a,b)  deviated  recourse  observed  time  "go  exact  [Lo,  surroundings,  a l l the  the  an  once  his only  water-shrew  water-shrew] moves, i n s t r a n g e  step,  path  and  s e q u e n c e he  kind  "...[the  Robbie  steps  reasonably the  that  sufficient  (a,b)"  from  this  note  and  would  exactly  p.107-109]. only  following a  I t s course i s determined  when  i t walks  that  step  way  for  by the  Bohot S i m u l a t i o n  first  time.  But, a f t e r  shrew r e c o g n i z e s it  repeats,  performed  a few r e p e t i t i o n s ,  the l o c a l i t y  with  i n which  t h e utmost  the p r e v i o u s  i n t h e h a b i t u a l path  time.  threw  i t i s evident  i tfinds i t s e l f  exactitude,  and  complete  P . N . E . when  the  alteration  confusion."  sequence  of t u r n s t o make, and no knowledge o f t h e c i t y . ]  that  given  c o n s t r u c t i o n , s t a t e m e n t , and e x e c u t i o n .  action  "go t o p o s i t i o n  actions,  assuming  the exact  i n v o l v e a model o f t h e w o r l d  their  (a,b)"  only  [Like  from  we have p l a n s  that  t h e movements which i t  ... [ H o w e v e r , ] any major  i t into  that the  driving  Thirdly  U.B.C. t o  84  Studies  in  For i n s t a n c e , t h e  might be decomposed  into  the sub-  Robbie i s c u r r e n t l y i n MRT1,  "move t h r o u g h  MRT1  i n t o IRT1"  "move t h r o u g h  MRT3 i n t o  IRT4"  • • •  ...<now R o b b i e i s i n t h e same MRT a s t h e p o s i t i o n "go  The  in a straight  line  to  a c t u a l sequence of s t e p s  any  one e x e c u t i o n  of t h i s  (a,b) " .  and t u r n s  plan  instructions Hastings,  [Like  : "Go e a s t  then  P.N.E. t o w e r . " Of  course,  still  driving  go e a s t  from  O.B.C*  for  few  a  he  particular to  until  can  as he  reach  you  day Main go  your d e s i r e d a c t i o n - b e c a u s e  model o f t h e o r g a n i s a t i o n o f V a n c o u v e r . ]  ; so l o n g  on Main u n t i l  miles  street  take i n  his  t o t h e P.N.E. g i v e n t h e  ; go n o r t h  However, on t h i s  out  plan  t o Main  y o u m e r e l y use a n o t h e r  carry  t h a t Robbie might  i s not s p e c i f i e d  "remembers" where he i s i n t h e o v e r a l l destination.  (a,b)>  you h i t see  the  i s blocked.  north  on,  and  you have a good  Robot S i m u l a t i o n  If  we  compare the  model,  versus  one  of  to  way  enable  allowing We  may  we  viewing  ( e.g.  a  world  us  to  construct  been t a u g h t  i n f a n t s are  and  permanence•of  is  a  world  interpreting  the  and  conclusion,  execute  plans  may  born  is  a  also from  world  possess  with  the  no  we  see  that  that  we  use  efficiently,  or,  more  by  model. likely,  i t as  an  instinct  concepts  of  solidity  to  Bower [ B o ]  a  basis  our  and  i n v o l v i n g the  i t , or  we  plan  heuristic  ourselves,  inputs  then,  a  no  model -  heuristic  It  sensory  cases -  e n v i r o n m e n t more  objects, according ?  85  i n v o l v i n g the  our  apparently  model our  third  model i s as  move a r o u n d  invented  and  plan  to  have  In  plus  us  have  may  model  first  Studies  ) . What  else  for organising  and  environment.  model i s  a  heuristic  device  for (i)  organising  (ii)  allowing out  us  our to  experience  of  the  environment  c o n s t r u c t , s t a t e , and  some a c t i o n o r  desire  i n an  execute  efficient  plans  manner.  to  carry  

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-0051197/manifest

Comment

Related Items