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 S i m u l a t i o n S t u d i e s b.Y P e t e r F* Howat , B . A . , C a n t a b . , 1 9 6 3 . A t h e s i s s u b m i t t e d i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r t h e d e g r e e o f M a s t e r o f S c i e n c e i n t h e d e p a r t m e n t o f Compute r S c i e n c e . We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t c t h e r e q u i r e d s t a n d a r d THE UNIVERSITY OF BR IT ISH COLUMBIA MARCH 1 9 7 2 . In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British 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 is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia Vancouver 8, Canada Date X ( i i ) F o r t h o s e who s u s t a i n e d me i n t i m e o f n e e d : E J , N i c k o , M i c k e y , M i k e , A l i s t a i r , a nd t h e w i l d m o u n t a i n o u s p l a c e s . "The b e s t - l a i d schemes o' mice an* men Gang a f t a g l e } " R o b e r t B u r n s . ( i i i ) A b s t r a c t The h i s t o r y o f t h e r o b o t as a c o n c e p t and a s a f a c t i s i n d i c a t e d , and t h e c u r r e n t l i n g u i s t i c a p p r o a c h t o r o b o t o l o g y d i s c u s s e d . The p r o b l e m o f d e s i g n i n g a r o b o t - c o n t r o l l e r i s a p p r o a c h e d by t a k i n g a s i m p l i f i e d , c o m p u t e r - s i m u l a t e d , model o f a 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 p r o g r a m s t o e n a b l e t h e r o b o t t o move a r o u n d i t s e n v i r o n m e n t i n a r e a s o n a b l y i n t e l l i g e n t manner. The p r o b l e m s o f c o n c e p t r e p r e s e n t a t i o n a n d t h e c r e a t i o n and e x e c u t i o n o f p l a n s a r e d e a l t w i t h i n t h i s s i m p l e s y s t e m , and t h e p r o b l e m o f e x p l o r a t i o n i s e n c o u n t e r e d b u t n o t s a t i s f a c t o r i l y d e a l t w i t h . . The r o b o t s ' e n v i r o n m e n t c o n s i s t s o f a r e c t a n g u l a r g r i d i n w h i c h s q u a r e s a r e l a b e l l e d a s b e l o n g i n g t o t h e b o u n d a r y , t o f i x e d o r m o v a b l e o b j e c t s , o r t o h o l e s , w h i l e t h e r o b o t i t s e l f o c c u p i e s a s i n g l e s q u a r e , can s e n s e t h e l a b e l s o f t h e e i g h t s u r r o u n d i n g s q u a r e s , c a n t u r n , a nd c a n p i c k u p , move, and d r o p m ovable o b j e c t s . The b o u n d a r y o f a t y p i c a l e n v i r o n m e n t i s t h u s a r e c t a n g u l o i d p o l y g o n , w h i c h c a n be c o m p a r e d t o t h e f l o o r - p l a n o f a o n e - l e v e l h o u s e . A f t e r an i n i t i a l e x p l o r a t i o n t h e b a s i c r e p r e s e n t a t i o n o f t h e e n v i r o n m e n t i s a s a s e q u e n c e o f edge-l e n g t h s and t u r n s , c a l l e d t h e r i n g - r e p r e s e n t a t i c n . An a l g o r i t h m i s d e s c r i b e d w h i c h p r o d u c e s t h e s e t o f m a x i m a l s u b r e c t a n g l e s o f t h e e n v i r o n m e n t ( i . e . r o o m s , p a s s a g e s , d o o r w a y s ) f r o m t h e r i n g r e p r e s e n t a t i o n . To make p l a n s f o r moving w i t h i n t h e e n v i r o n m e n t , t h e r o b o t f i r s t v i e w s t h e m a x i m a l s u b r e c t a n g l e s a s t h e v e r t i c e s (iv) of a graph, wherein two vertices are connected by an edge i f and only i f the corresponding maximal subrectangles overlap, and then uses a path-finding algorithm to find a path between two vertices of the graph. This path constitutes a "plan of action". Whenever an iso 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 of objects and holes within the environment can be compared in various ways. In pa r t i c u l a r , an algorithm i s described which compares the shape of a movable object with that of a hole to ascertain i f the movable object could be moved to f i t inside the hole without "physically" moving the object. . BOSS , an in 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 specify tasks for the robot at various conceptual le v e l s . Several problems are l i s t e d concerning the ways in which a robot might explore, represent, and make plans about, i t s environment, most of which are amenable to direct attack in this 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 two-dimensional rectanguloid shapes are raised. (v) T a b l e of c o n t e n t s I n t r o d u c t i o n 1 Chapter 1 - Preamble on 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 1.1 H i s t o r y of t h e r o b o t concept 2 1.2 Robots i n f a c t 4 1.3 An e s s a y on r o b o t r e s e a r c h 6 1.3.1 Importance to a r t i f i c i a l i n t e l l i g e n c e 6 1.3.2 P h i l o s o p h y 7 1.3.3 G o a l s 11 Chapter 2 - Design of the s i m u l a t e d r o b o t 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 model of the world 17 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 Maximal s u b r e c t a n g l e s : the a l g o r i t h m DECOMP 19 2.3.3 Containment:the a l g o r i t h m CONTAIN 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 25 2.4 E x p l o r a t i o n 29 2.5 Summary of Robbie's world 31 Chapter 3 - ROSS: a r o b o t s i m u l a t i o n system 3.1 How to use 33 3.1.1 G e n e r a l d e s c r i p t i o n 33 3.1.2 Commands 35 3.1.3 Summary of ROSS commands 50 3.1.4 Sample o u t p u t 52 3.2 Implementation 63 Chapter 4 - C o n c l u s i o n (v i ) 4.1 Summary 65 4 .2 D i r e c t i o n s f o r f u r t h e r work 65 4 . 2 . 1 P r e a m b l e 66 4 . 2 . 2 D e s i g n 66 4 . 2 . 3 ROSS 70 B i b l i o g r a p h y 7 1 A p p e n d i c e s A D e t a i l e d d e s c r i p t i o n o f t h e a l g o r i t h m DECOMP 77 B P l a n s and m o d e l s o f t h e w o r l d 83 ( v i i ) l i s t o f f i g u r e s F i g u r e 1 f o l l o w i n g page 16 F i g u r e 2 16 F i g u r e 3 18 F i g u r e 4 18 F i g u r e 5 18 F i g u r e 6 19 F i g u r e 7 19 F i g u r e 8 19 F i g u r e 9 21 F i g u r e 10 22 F i g u r e 11 23 F i g u r e 12 25 F i g u r e 13 25 F i g u r e 14 26 F i g u r e 15 26 F i g u r e 16 28 F i g u r e 17 77 F i g u r e 18 78 F i g u r e 19 78 ( v i i i ) 3±i.§t o f s n a p s h o t s Zi£§i e p i s o d e Snap #4 Snap #6 S na. p #13 Snap #23 Snap #27 Snap #30 Snap #32 Snap #34 S e c o n d e p i s o d e S n a p #8 f o l l o w i n g page 53 53 54 54 54 54 56 57 58 (ix) I am g r e a t l y indebted to Dr. Rosenberg, my s u p e r v i s o r , f o r h i s e x c e l l e n t guidance. I thank the N a t i o n a l Research C o u n c i l f o r p r o v i d i n g me with f i n a n c i a l support while the t h e s i s was i n p r e p a r a t i o n , through t h e i r grants 67-5552 and 67-7642. I' must a l s o acknowledge UBC's IBM System 360/67 computer i t s e l f , f o r i t was e s s e n t i a l to t h i s t h e s i s i n two ways. I t executed the programs d e s c r i b e d here, and i t was the medium through which the t h e s i s was prepared and typed. B i l l Webb's FORMAT program c o n t r o l l e d the format, and the MTS f i l e e d i t o r was e x t e n s i v e l y used to r e v i s e and a l t e r the t e x t . Above a l l , my deepest thanks go t o Nona, my partner i n l i f e , f o r supporting and i n s p i r i n g me i n a multitude of ways. Only through her i s t h i s t h e s i s here now. Robot Simulation Studies 1 IB i n d u c t i o n This thesis i s an attempt at formulating and solving the l o g i c a l problems involved in the design of a robot, or in other words we try to face the question "How do you design the brain of a robot?". Our approach i s to simulate an extremely simple robot-environment system by means cf a computer, and develop programs of the simplest sort which w i l l enable the robot to execute elementary tasks in i t s environment i n a reasonably i n t e l l i g e n t manner. I t may well be the case that i n a real robot the engineering problems of fabrication and control w i l l cause further l o g i c a l problems to a r i s e , but since we are unable to foresee such problems short of building a physical 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 be read more or less independently. Chapter 1 i s a brief but general survey of robotics and a r t i f i c i a l i n t e l l i g e n c e . Chapter 2 considers the design of a simulated robot, i t s simulated world, and the robot's conceptual world, while chapter 3 describes a running computer program which implements the design of chapter 2. A b r i e f summary i n chapter 4 i s followed by a l i s t of problems brought to l i g h t by the work described i n chapters 2 and 3. R o b o t S i m u l a t i o n S t u d i e s 2 C h a p t e r J 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 i n t e l l i g e n c e 1.1 H i s t o r y o f t h e r o b o t c o n c e p t The c o n c e p t o f a r o b o t has b e e n w i t h us s i n c e a n c i e n t t i m e s . I n d e e d , as Cohen s a y s [ C o , p . 7 ] , " a u t o m a t o n d e s e r v e s an e n c y c l o p a e d i a . [ T h e r e i s ] . . . s o m e c o n t i n u i t y b e t w e e n one o f t h e most p r e g n a n t c o n c e p t s o f modern s c i e n c e and t e c h n o l o g y and f a n t a s i e s w h i c h had t h e i r b i r t h i n t h e d a r k . . . abysm o f t i m e , a c o n t i n u i t y w h i c h l i n k s Homer w i t h B a b b a g e , . . . [ a n d ] j o i n s t o g e t h e r t h e i m a g i n a t i v e w o r k s o f C h i n a , I n d i a , P e r s i a , E g y p t , and W e s t e r n E u r o p e . " C h a p u i s and Droz [ C h ] a l s o t r a c e t h e h i s t o r y o f r o b o t s , b u t a r e m a i n l y c o n c e r n e d w i t h t h e a u t o m a t a o f S w i s s c l o c k - m a k e r s . The word " r o b o t " was i n t r o d u c e d t o t h e E n g l i s h l a n g u a g e by K a r e l Capek i n h i s p l a y R. U. R» i n 1920. " R o b o t i c s " was c o i n e d by I s a a c A s i m o v i n h i s s c i e n c e f i c t i o n w r i t i n g [ A s ] t o d e n o t e t h e t h e o r y and t e c h n o l o g y r e q u i r e d t c b u i l d r o b o t s , a l t h o u g h " r o b o t o l o g y " now a p p e a r s i n t h e s c i e n t i f i c l i t e r a t u r e . R o b o t s o c c u r i n s e v e r a l p l a c e s i n G r e e k m y t h o l o g y . F o r e x a m p l e , i n Homer's I l i a d , Book X V I I I , T h e t i s v i s i t s t h e s m i t h -god V u l c a n t o o b t a i n d i v i n e l y f o r g e d armour f o r h e r s o n , Robot Simulation Studies 3 A c h i l l e s , The lame V u l c a n comes o u t t o meet T h e t i s , w h i l e " b e s i d e and a r o u n d t h e i r l o r d , [ mov *d n i m b l y P a g e s i n f i n e - w r o u g h t g o l d , i n f o r m l i k e u n t o l i v i n g m a i d e n s ; Which have w i t h i n t h e i r h e a r t a m i n d , 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 ; and c a n n y s e r v i c e know by g i f t s o f gods i m m o r t a l . T h e s e 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 by W.J.Newman.] I n s h o r t , t h e y were r o b o t s . A most s t r i k i n g t a l e r e c o u n t e d by J o s e p h Needham [ N e 1 , p „ 5 3 ] makes i t c l e a r t h a t even a s e a r l y a s t h e t h i r d c e n t u r y B.C. t h e i d e a o f a man-made r o b o t was known i n C h i n a . Many C h i n e s e myths i n v o l v e i n a n i m a t e o b j e c t s b e c o m i n g a n i m a t e [ G , S h , L ]1. I n t h e E u r o p e a n m i d d l e a g e s , t h e i d e a o f a man-made i m a g e s p r i n g i n g t o l i f e was w e l l - k n o w n , i n v i e w o f t h e Golem s t o r i e s w h i c h i n v o l v e d c l a y o r wooden i m a g e s b e c o m i n g a n i m a t e . S i n c e Mary S h e l l e y ' s F r a n k e n s t e i n , and up t o 1 9 4 0 , t h e u s u a l p l o t f o r a s c i e n c e f i c t i o n t a l e o f r o b o t s was: r o b o t s were c r e a t e d and s u b s e q u e n t l y d e s t r o y e d t h e i r c r e a t o r . I n r e a c t i o n t o t h i s , A s i m o v began t o w r i t e s c i e n c e f i c t i o n i n w h i c h t h e r o b o t s had b u i l t i n t o them t h e " T h r e e Laws o f R o b o t i c s " , w h i c h were t o p r e v e n t any r o b o t f r o m i n j u r i n g a human b e i n g . T h e s e l a w s a r e : 1. 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 i n a c t i o n , a l l o w a human b e i n g t o come t o harm. 2. A r o b o t must obey t h e o r d e r s g i v e n i t by human b e i n g s e x c e p t , where s u c h o r d e r s w o u l d c o n f l i c t w i t h t h e F i r s t Law. 3. A r o b o t must p r o t e c t i t s own e x i s t e n c e a s l o n g as s u c h 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 Second Law,. W i t h t h e s e a s a b a s i s , Asimov h a s w r i t t e n many a t a l e o f * . I c a n n o t r e f r a i n f r o m m e n t i o n i n g t h e s t r a n g e t a l e f r o m t h e L i a o d y n a s t y [ A . D . 9 0 0 - 1 1 6 9 ] , w h e r e i n [ G , L ] "an image o f a dead man may become t h i s man h i m s e l f , s o 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" . R o b o t S i m u l a t i o n S t u d i e s 4 r o b o t s . I t i s i n t e r e s t i n g t o n o t e t h a t , w i t h t h e i n t r o d u c t i o n o f t h e T h r e e L a w s , r o b o t s i n s c i e n c e f i c t i o n r e t u r n e d t o b e i n g b e n e v o l e n t c r e a t u r e s j u s t as i n t h e myths c f a n t i q u i t y , i n c o n t r a s t t o t h e m a l e v o l e n t r o b o t s o f F r a n k e n s t e i n a nd p r e - 1 9 4 0 s c i e n c e f i c t i o n . 1.2 R o b o t s i n f a c t I t w i l l a l w a y s be d i f f i c u l t t o s a y when t h e f i r s t r o b o t was b u i l t . T h e r e h a v e been s t a t u e s t h a t c o u l d move and t a l k by means o f a h i d d e n p r i e s t , p u p p e t s , and many m e c h a n i c a l m o d e l s t h r o u g h t h e a g e s [ C h , C o ] ; and a l t h o u g h t h e r e a r e now s e v e r a l r o b o t p r o j e c t s i n e x i s t e n c e [ Po 1, N i 1, H, Su ] , no r e a l r o b o t e x i s t s , o r e v e r has e x i s t e d , w h i c h c o m p a r e s w i t h t h e r o b o t s o f s c i e n c e f i c t i o n o r o f w h i c h i t c o u l d r e a s o n a b l y be s a i d t h a t " i t was a m e c h a n i c a l man". M e c h a n i c a l t o r t o i s e s w h i c h c o u l d wander a r c u n d a f l o o r o r s o l v e a maze h a v e been b u i l t by many p e o p l e ; t h e s e i n c l u d e Thomas Ross ( 1 9 3 8 ) , R . A . W a l l a c e ( 1 9 5 2 ) , C l a u d e S h a n n o n , and G r e y W a l t e r ( [ W ] , 1 9 5 3 ) . E a c h t o r t o i s e was b u i l t t o d e m o n s t r a t e t h a t c e r t a i n a s p e c t s o f b e h a v i o u r c o u l d be r e a l i z e d by m e c h a n i c a l means. Grey W a l t e r ' s m a c h i n e d e m o n s t r a t e d , f o r i n s t a n c e , e x p l o r a t o r y b e h a v i o u r , p o s i t i v e and n e g a t i v e i n t e r a c t i o n w i t h i t s e n v i r o n m e n t and s e l f - and m u t u a l - r e c o g n i t i o n . H o w e v e r , t h e s e i n g e n i o u s t o y s were d e v e l o p e d no f u r t h e r , and t h e s p e c i e s (of genus r o b c t o ) d i e d o u t . The members o f t h e n e x t s p e c i e s t o a p p e a r on t h e s c e n e were n o t r e a l m a c h i n e s a t a l l : t h e y were c o m p u t e r s i m u l a t i o n s ! Robot S i m u l a t i o n S t u d i e s 5 F r i e d m a n [ F r 1 , F r 2 ] , a p s y c h o l o g i s t , d e s c r i b e d a c o m p u t e r s i m u l a t i o n o f i n s t i n c t i v e b e h a v i o u r i n v o l v i n g an a u t o m a t o n w i t h s e n s o r y and motor s y s t e m s . Uhr and K o c h e n [U ] s i m u l a t e d a p o p u l a t i o n o f o r g a n i s m s w a n d e r i n g a r o u n d an e n v i r o n m e n t w i t h t h e p u r p o s e o f e x p l i c a t i n g t h e i n t e r - r e l a t i o n s h i p s o f p a t t e r n r e c o g n i t i o n , h y p o t h e s i s f o r m a t i o n , and n e e d - s a t i s f a c t i o n c a p a b i l i t i e s . D o ran [ D 1 , D 2 ] s i m u l a t e d a r a t i n i t s s u r r o u n d i n g s w h i c h d i s p l a y e d some r u d i m e n t a r y i n t e l l i g e n c e i n t h a t t h e s i m u l a t e d r a t was p l e a s u r e - s e e k i n g , and was a l s o c a p a b l e o f e l e m e n t a r y p l a n n i n g and g e n e r a l i s a t i o n . D o r a n ' s s y s t e m i s t h e one c l o s e s t i n s p i r i t t o my own. F o r i n s t a n c e , i n n e i t h e r c a s e i s i t i n t e n d e d t h a t t h e work be a s e r i o u s r o b o t s i m u l a t i o n , b u t r a t h e r i t i s an i n v e s t i g a t i o n o f what h e u r i s t i c p r o c e s s e s a r e n e e d e d , and how t h e y m i g h t be c o m b i n e d i n an e f f e c t i v e r o b o t c o n t r o l l e r . N i l s s o n and R a p h a e l [ N i l ] c a r r i e d c u t a v e r y s i m p l e r o b o t s i m u l a t i o n a s a p r e l i m i n a r y t o b u i l d i n g a r e a l r o b o t a t t h e S t a n f o r d R e s e a r c h I n s t i t u t e ( S.R.I ) . F i n a l l y we come t o t h e h a r d w a r e r o b o t s . A m o b i l e r o b o t c a l l e d " S h a k e y " h a s been b u i l t a t S,. R . I . , a l t h o u g h c u r r e n t l y i t s s o f t w a r e i s b e i n g 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 E d i n b u r g h a s t a t i o n a r y r o b o t w i t h m o b i l e s u r r o u n d i n g s has b e e n u s e d [ B a 2 ] . S y s t e m s c o n s i s t i n g o f a m e c h a n i c a l hand p l u s v i s u a l o r t a c t i l e r e c e p t o r s t h a t c a n m a n i p u l a t e s i m p l e o b j e c t s a r e i n us e i n J a p a n [ K ] , E d i n b u r g h [ P c 1 , P o 2 ] , M.I.T., and S t a n f o r d U n i v e r s i t y [ Fe2 , Mc 1 ,Mc3 , Sc ] , A c o m b i n e d v i s u a l - t a c t i l e p a t t e r n r e c o g n i t i o n s y s t e m t h a t u s e s a m e c h a n i c a l arm i s p r o p o s e d i n I t a l y [ A i ] . The p a p e r s p r e s e n t e d i n S e s s i o n 8 c f t h e S e c o n d 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 [ S e ] R o b o t S i m u l a t i o n S t u d i e s 6 g i v e a good d e s c r i p t i o n o f t h e c u r r e n t work (197 1 ) . Some i d e a o f t h e g e n e r a l c u r r e n t l e v e l o f p e r f o r m a n c e f o l l o w s : " S h a k e y " c o u l d n a v i g a t e a c r o s s a f l o o r h a v i n g s e v e r a l p l a n e - f a c e d " o b j e c t s i n t h e way, and push a s p e c i f i e d o b j e c t t o a s p e c i f i e d p o s i t i o n , w h i l e t h e S t a n f o r d U n i v e r s i t y h a n d - e y e s y s t e m c a n m a n i p u l a t e b l o c k s w e l l enough t o 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 . One o f t h e p a r a d i g m p r o b l e m s c u r r e n t l y g u i d i n g r e s e a r c h i n v a r i o u s c e n t e r s [ E , P o 2 ] i s t h a t o f u s i n g a h a n d - e y e (-touch) s y s t e m t o a s s e m b l e a c o m p l e x whole f r o m i t s c o n s t i t u e n t p a r t s . F o r e x a m p l e , P o p p l e s t o n e [ P o 2 ] c o n s i d e r s t h e p r o b l e m o f a s s e m b l i n g a model a i r c r a f t e n g i n e . However, t h e a r t o f v i s u a l r e c o g n i t i o n o f e v e r y d a y o b j e c t s , a s o p p o s e d t o n i c e c l e a n s i m p l e p o l y h e d r a , i s i n a p r i m i t i v e s t a t e [ B a 1 ] , and i t may be t h a t t h e a t t e m p t s a t t h e a s s e m b l i n g p r o b l e m a r e p r e m a t u r e . 1.3 An e s s a y on r o b o t r e s e a r c h 1.3.1 I m p o r t a n c e t o a r t i f i c i a l i n t e l l i g e n c e Why i s r o b o t r e s e a r c h i m p o r t a n t t o a r t i f i c i a l i n t e l l i g e n c e ? F o r one t h i n g , b e c a u s e i n any w o r k i n g r o b o t many p r o b l e m s p r e v i o u s l y c o n s i d e r e d i n i s o l a t i o n f r o m e a c h o t h e r must now be c o n s i d e r e d i n a r e a s o n a b l y u n i f o r m manner, so t h a t , a t t h e v e r y minimum, t h e p r o g r a m s d e a l i n g w i t h s e p a r a t e p r o b l e m s c a n c o m m u n i c a t e w i t h e a c h o t h e r . F o r i n s t a n c e , p r o g r a m s f o r p r o b l e m - s o l v i n g , p a t t e r n - r e c o g n i t i o n , i n f o r m a t i o n s t o r a g e a nd r e t r i e v a l , l a n g u a g e u n d e r s t a n d i n g , e t c . , a r e a l l r e q u i r e d . F o r a n o t h e r , s e v e r a l p r o b l e m s d i f f i c u l t , o r v e r y a r t i f i c i a l , t o d e a l R o b o t S i m u l a t i o n S t u d i e s 7 w i t h i n i s o l a t i o n must be s q u a r e l y f a c e d . T h e s e i n c l u d e t h e p r o b l e m o f b u i l d i n g an a d e q u a t e w o r l d - m o d e l i n t o t h e m a c h i n e { t h i s a l s o a s s i s t s g r e a t l y i n l a n g u a g e u n d e r s t a n d i n g ) , t h e p r o b l e m o f a u n i v e r s a l and b e s t r e p r e s e n t a t i o n o f k n o w l e d g e , and t h e p r o b l e m o f c r e a t i n g and e x e c u t i n g p l a n s . Robot r e s e a r c h i s a l s o v a l u a b l e b e c a u s e o f t h e n a t u r e o f t h e d a t a b e i n g u s e d ; n a m e l y , r e a l i n p u t s from t h e e x t e r n a l w o r l d , w i t h a l l t h e i r u n c e r t a i n t i e s and c o n c u r r e n t i l l - d e f i n e d p r o b l e m s , a s o p p o s e d t o t h e p r e c i s e f o r m a l r e p r e s e n t a t i o n s u s e d , f o r i n s t a n c e , i n t h e o r e m p r o v e r s . F i n a l l y , t h e r e i s t h e s h e e r p r o b l e m o f o r g a n i s i n g a c o m p l e x s y s t e m ; "The m a i n p r i n c i p l e . . . i s t h e d e p e n d e n c e o f e v e r y t h i n g on e v e r y t h i n g . " [ F e 1 ] , The i m p o r t a n c e o f r o b o t r e s e a r c h i s e x p o u n d e d f u r t h e r i n [R2 ] . S i n c e v i r t u a l l y e v e r y p r o b l e m t a c k l e d by w o r k e r s i n a r t i f i c i a l i n t e l l i g e n c e i s r e l e v a n t t o t h e d e s i g n o f t h e u l t i m a t e r o b o t , we s h o u l d n o t e t h a t , c o n v e r s e l y , r o b o t r e s e a r c h c a n be c o n s i d e r e d t o i n c l u d e a l l o f a r t i f i c i a l i n t e l l i g e n c e . 1.3.2 P h i l o s o p h y . I n r o b o t r e s e a r c h , w h i c h c a n n o t be c a l l e d a t h e o r e t i c a l s c i e n c e d e s p i t e t h e e f f o r t s o f H a y e s [ H a 1 ] , H e w i t t f H e ] and o t h e r s t o make i t s o , an e x p e r i m e n t c o n s i s t s o f r u n n i n g a p r o g r a m (or r o b o t ) w h i c h 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 t h e r e s u l t a n t b e h a v i o u r . The u s e f u l n e s s o f t h e i d e a i s j u d g e d by c o m p a r i n g t h e r e s u l t a n t b e h a v i o u r e i t h e r w i t h human b e h a v i o u r o r w i t h t h e b e h a v i o u r o f o t h e r s i m i l a r p r o g r a m s , i f a n y . J u s t as i n a r t i f i c i a l i n t e l l i g e n c e as a w h o l e , t h e r e a r e R o b o t S i m u l a t i o n S t u d i e s 8 t h r e e common a p p r o a c h e s t o t h e s e t t i n g up o f e x p e r i m e n t s . V e r y b r i e f l y , one i s t o t r y t o s i m u l a t e t h e p h y s i o l o g y o f t h e human b r a i n and b o d y , a n o t h e r i s t o t r y t o s i m u l a t e human p s y c h o l o g y as d e v e l o p e d i n v a r i o u s t h e o r i e s , a nd a t h i r d i s t o f o r g e t a b o u t human p h y s i o l o g y and p s y c h o l o g y and make a d i r e c t a t t a c k on t h e p r o b l e m s . The NASA r o b o t p r o j e c t [ S u ] t a k e s t h e p h y s i o l o g i c a l a p p r o a c h u s i n g Warren M c c u l l o c h ' s p h y s i o l o g i c a l c o n c e p t s . H o w e v e r , i n v i e w o f t h e c u r r e n t l a c k o f u n d e r s t a n d i n g o f how t h e b r a i n f u n c t i o n s { t h e r e v i e w by Doran [ D ] h a s a b i b l i o g r a p h y ) , we c a n n o t e x p e c t g r e a t s u c c e s s e s w i t h t h i s a p p r o a c h . A l l o t h e r h a r d w a r e r o b o t p r o j e c t s have t a k e n t h e t h i r d a p p r o a c h , o f making a d i r e c t a t t a c k on t h e p r o b l e m s , and t h a t i s t h e a p p r o a c h I h a v e u s e d i n my s i m u l a t e d r o b o t . W i t h i n t h e t h i r d , d i r e c t , a p p r o a c h , t h e r e a r e two o p p o s i n g a t t i t u d e s . One i s t h e f o r m a l i s t i c o r l i n g u i s t i c a t t i t u d e , most r e c e n t l y e x p o u n d e d by M c C a r t h y and H a y e s [ M c 2 ] , and t h e o t h e r i s t h e n o n - f o r m a l , i n t u i t i v e a t t i t u d e e x p l i c i t l y s t a t e d by S l o m a n [ S i ] . M c C a r t h y and Hayes m a i n t a i n t h a t e v e r y t h i n g must be r e d u c e d t o some l o g i c a l f o r m a l i s m , and t h i s i s i n d e e d t h e a p p r o a c h t a k e n by t h e S . R . I . P r o j e c t [ F i 2 ] . H o w e v e r , I w i s h t o p r o p o s e a t h e s i s : r e a s o n i n g i s b a s i c a l l y , n on- U n g u i s t i c . N o t e t h a t I do n o t deny t h e i m p o r t a n c e o r e x i s t e n c e o f l i n g u i s t i c r e a s o n i n g . The t h e s i s i s b a s e d on t h e f o l l o w i n g o b s e r v a t i o n s , t o w h i c h I hope t h e r e a d e r w i l l a s s e n t . 1) T h e r e were i n t e l l i g e n t b e i n g s l o n g b e f o r e any l a n g u a g e was u s e d , and t h e r e a r e many i n t e l l i g e n t R o b o t S i m u l a t i o n S t u d i e s 9 c r e a t u r e s t h a t p o s s e s s no l a n g u a g e s i m i l a r t o human l a n g u a g e . F o r i n s t a n c e , d ogs and h o r s e s ( d o l p h i n s a r e t o o c o n t r o v e r s i a l ) . 2) A human i n f a n t o f o n l y 18 months c a n c l e a r l y p l a n and do some i n t e l l i g e n t a c t i o n s , e v e n t h o u g h i t c a n n o t s p e a k y e t . 3) E v e r y d a y e x p e r i e n c e : we do n o t r e a s o n v e r b a l l y when p l a n n i n g t o go t o t h e c o r n e r s t o r e f o r a n e w s p a p e r , o r when moving f u r n i t u r e . 4) L a n g u a g e i s u s e d f o r c o m m u n i c a t i n g i d e a s (amongst o t h e r t h i n g s ) , n o t f o r r e a s o n i n g a b o u t o r f o r c r e a t i n g i d e a s . 5) A c c o r d i n g t o Hadamard[Hd ] , t h e m e n t a l p r o c e s s e s o f many g i f t e d m a t h e m a t i c i a n s a r e a p p a r e n t l y h i g h l y i n t u i t i v e and n o n - l i n g u i s t i c . The l i n g u i s t i c a p p r o a c h s t e m s f r o m M c C a r t h y ' s h i g h l y i n f l u e n t i a l p r o p o s a l f o r t h e A d v i c e T a k e r p r o g r a m , i n w h i c h he s t a t e s [ Mc4,p.406 ] : "The o n l y way we know o f e x p r e s s i n g a b s t r a c t i o n s (...) i s i n l a n g u a g e . T h a t i s why we have d e c i d e d t o p r o g r a m a s y s t e m w h i c h r e a s o n s v e r b a l l y . " L a t e r [ p . 4 1 0 ] he s t a t e s : "We b e l i e v e t h a t human i n t e l l i g e n c e d e p e n d s e s s e n t i a l l y on t h e f a c t t h a t we c a n r e p r e s e n t i n l a n g u a g e f a c t s a b o u t o u r s i t u a t i o n , o u r g o a l s , and t h e e f f e c t s o f v a r i o u s a c t i o n s t h a t we c a n p e r f o r m . " Robot S i m u l a t i o n S t u d i e s 10 I do n o t w i s h t o d e n i g r a t e M c C a r t h y ' s p r o p o s a l ; i n f a c t t h e A d v i c e T a k e r p r o g r a m has been t h e g o d f a t h e r t o many p r o j e c t s o f w h i c h o n e , C a r l H e w i t t ' s PLANNER language}" He] f o r m a n i p u l a t i n g m odels and p r o v i n g t h e o r e m s i n r o b o t s , i s a mongst t h e most s i g n i f i c a n t o f t o - d a y ' s a r t i f i c i a l i n t e l l i g e n c e p r o j e c t s . I m e r e l y w i s h t o p o i n t o u t t h a t more a t t e n t i o n s h o u l d be d e v o t e d t o i n t u i t i v e , e v e n i n t r o s p e c t i v e , a p p r o a c h e s . My f i r s t g u o t e f r o m M c C a r t h y r e a d s l i k e a n c n - s e q u i t u r . The f a c t t h a t we a r e a b l e t o e x p r e s s o u r a b s t r a c t i o n s v e r b a l l y does no t n e c e s s a r i l y i m p l y t h a t we r e p r e s e n t o u r a b s t r a c t i o n s i n a l i n g u i s t i c manner o r t h a t we r e a s o n w i t h them i n a way a t a l l c l o s e l y r e l a t e d t o o u r v e r b a l e x p r e s s i o n s c f t h e m . T a k e m a t h e m a t i c i a n s , f o r i n s t a n c e . I w o u l d go so f a r a s t o c l a i m t h a t t h e r e a s o n i n g done by m a t h e m a t i c i a n s i n c r e a t i n g and u s i n g m a t h e m a t i c s i s t h e h i g h e s t f o r m o f i n t u i t i v e r e a s o n i n g known; t h a t i s why t h e i r p a p e r s a r e d i f f i c u l t t o r e a d , and why m a t h e m a t i c i a n s h a v e t o r e s o r t t o f o r m a l , n o n - l i n g u i s t i c methods ( e g u a t i o n s , d e f i n i t i o n s , s y m b o l m a n i p u l a t i o n e t c ) t o e x p r e s s t h e m s e l v e s . ( I n S t r a c h e y ' s w o r d s , t h e s y m b o l m a n i p u l a t i o n s u s e d t o e x p r e s s t h e i r i d e a s a r e s i m p l y " s y n t a c t i c s u g a r i n g " . ) As f o r f o r m a l i s m , t h e r e a r e a v a r i e t y o f r e a s o n s , w h i c h I s h a l l n o t go i n t o h e r e , why i t s h o u l d n e t be t a k e n t o o s e r i c u s l y . H o w e v e r , airy i m p l e m e n t a t i o n o f an a p p r o a c h by c o m p u t e r , i f i t i s a t a l l e l e g a n t , s h o u l d be r e g a r d e d a s a f o r m a l i s a t i o n o f t h a t a p p r o a c h . M i n s k y i n v e i g h s a g a i n s t an o b s e s s i v e c o n c e r n w i t h f o r m and f o r m a l i s m i n c o m p u t e r s c i e n c e i n [ H n 2 ] . R o b o t S i m u l a t i o n S t u d i e s P e r h a p s t h e d i c h o t o m y between t h e f o r m a l , l i n g u i s t i c a p p r o a c h and t h e o p p o s i n g i n t u i t i v e a p p r o a c h i s an e x a m p l e o f a c o n f l i c t b e t w e e n G r e y W a l t e r s ' two e x t r e m e p e r s o n a l i t y t y p e s : t h e f i r s t c o r r e s p o n d i n g t o a P t y p e - t h e n o n - v i s u a l , l o g i c a l t h i n k e r s w i t h p e r s i s t e n t a l p h a r h y t h m a c t i v i t y - and t h e s e c o n d c o r r e s p o n d i n g t o an M t y p e - t h e h i g h l y v i s u a l t h i n k e r s w i t h no s i g n i f i c a n t a l p h a r h y t h m a c t i v i t y (H f o r minus) [W, p.185 f f ] . I n e x a m i n i n g t h e m i n d s o f m a t h e m a t i c i a n s , Hadaraard f o u n d a c o m p a r a b l e d i c h o t o m y b e t w e e n l o g i c a l and i n t u i t i v e t y p e s o f m a t h e m a t i c a l mind[ Hd , p. 10 6 ] . One m i g h t e v e n s p e c u l a t e t h a t , one d a y , t h e two a p p r o a c h e s t o r o b o t r e s e a r c h w i l l c o r r e s p o n d i n g l y e n g e n d e r two e x t r e m e r o b o t p e r s o n a l i t y t y p e s ! 1.3.3 G o a l s . One g o a l o f r o b o t r e s e a r c h i s t h e use o f t h e f u t u r e r o b o t a s a t o o l f o r t e s t i n g , r e f i n i n g , and d e v e l o p i n g v a r i o u s s t a n d -a l o n e i n t e l l e c t u a l p r o g r a m s . F o r i n s t a n c e , p a t t e r n r e c o g n i z e r s and l a n g u a g e t r a n s l a t o r s . The g o a l o f r o b o t r e s e a r c h p e r se i s o f c o u r s e t h e c o n s t r u c t i o n o f c o m p e t e n t m e c h a n i c a l men. T h e s e w i l l have a m u l t i t u d e o f u s e s , a s w r i t t e n a b o u t i n s c i e n c e f i c t i o n . The most o b v i o u s i n i t i a l u s e s a r e f o r j o b s t h a t man f i n d s b o r i n g a n d d a n g e r o u s , o r f o r j o b s i n s i t u a t i o n s where man c o u l d not s u r v i v e , e . g . p l a n e t a r y e x p l o r a t i o n , deep o c e a n e x p l o r a t i o n . T h e r e i s a l s o t h e h o r r i f i c p r o s p e c t o f t h e use o f r o b o t s i n w a r f a r e ; i t w i l l be t h e r e s p o n s i b i l i t y o f r o b o t r e s e a r c h e r s t o p r e v e n t t h i s b e c o m i n g r e a l i t y , p e r h a p s by i n c o r p o r a t i n g some R o b o t S i m u l a t i o n S t u d i e s 12 f o r m o f A s i m o v ' s T h r e e L a w s , o r by u s i n g a s e l f - d e s t r u c t m e c h a n i s m . The s o c i a l i m p l i c a t i o n s o f i n t e l l i g e n t m a c h i n e s , w h i c h must be c a r e f u l l y c o n s i d e r e d by f u t u r e r o b o t o l o g i s t s , a r e e x p l o r e d by G r e g o r y f Gr ] . S u p p o s i n g r o b o t r e s e a r c h s u c c e e d s i n b u i l d i n g a m e c h a n i c a l man, i n what l i g h t s h o u l d we v i e w t h e s e c r e a t i o n s ? W i l l i t be m e r e l y a m a c h i n e , o r w i l l i t be a " f r e e and p u r p o s e f u l b e i n g " ? T h i s i m m e d i a t e l y r a i s e s t h e f r e e - w i l l q u e s t i o n , c n w h i c h I s h a l l n o t comment. J u s t a s f o r m a n[Ne2], t h e two v i e w s e x p r e s s e d i n t h i s q u e s t i o n w i l l d o u b t l e s s be f o u n d t o be e s s e n t i a l l y i n c o m p a t i b l e - y e t c o - e x i s t e n t . Robot S i m u l a t i o n S t u d i e s 13 C h a p t e r 2 De s i c m o f t h e s i mula t e d •. r o b o t fly w hole a p p r o a c h has b e e n on an ad h o c b a s i s : u s e any method t h a t w o r k s a n d , when i n d o u b t , use t h e s i m p l e s t . The hope was, and i s , t h a t we m i g h t d e r i v e f r o m t h i s a p p r o a c h some t e c h n i q u e s and i d e a s u s e f u l i n t h e d e s i g n o f a r e a l r o b o t , and b r i n g t o l i g h t some p r o b l e m s w o r t h y o f a t t a c k i n t h e i r own r i g h t . I have d e l i b e r a t e l y a v o i d e d u t i l i z i n g any c f t h e w e l l - k n o w n l i n g u i s t i c o r f o r m a l a p p r o a c h e s , f o r r e a s o n s e x p l i c a t e d i n t h e p r e a m b l e , s e c t i o n 1.3.2. A l s o I hoped t h a t i t would be p o s s i b l e t o a v o i d t h e r a t h e r u n n a t u r a l " f r a m e " problem]"R3 ] , w h i c h h a s p l a g u e d some o f t h e e x t a n t r o b o t p r o j e c t s , o r a t l e a s t t h a t i n my r e s u l t i n g s y s t e m i t m i g h t a r i s e and be d e a l t w i t h i n a n a t u r a l manner. However I must s a y h e r e t h a t R o b b i e c a n do o n l y p r e t t y e l e m e n t a r y t h i n g s , so t h e f r a m e p r o b l e m h a s n ' t even had a c h a n c e t o r e a r i t s h e a d . 2.1 B a s i c a p p r o a c h Suppose we a r e i n t r o d u c e d t o a new e n v i r o n m e n t - f o r Robot S i m u l a t i o n S t u d i e s e x a m p l e , a l a r g e o n e - f l o o r h o u s e , or a u n i v e r s i t y campus - and c o n s i d e r t h e f o l l o w i n g t a s k s . T a s k 1 : e x p l o r e and form an i n t e r n a l m o d e l o f t h e e n v i r o n m e n t . T a s k 2 : f i n d o u r way f r o m one p o i n t t o a n o t h e r , i n a r e a s o n a b l y e f f i c i e n t manner. T a s k 3 : move a l a r g e o b j e c t ( e . g . a t a b l e ) f r o m one p o i n t t o a n o t h e r . T h e s e t a s k s a r e v e r y s i m p l e f o r humans, i n f a c t so s i m p l e t h a t we c a n c a r r y them o u t a l m o s t u n c o n s c i o u s l y . B u t i f a s k e d "How do we c a r r y o u t t h e s e t a s k s ? " ( i n t e r m s o f t h e d a t a p r o c e s s i n g r e q u i r e d ) , we a r e h a r d p r e s s e d t o g i v e an a n s w e r . B e f o r e a r o b o t c a n be b u i l t t h a t i s c a p a b l e o f c a r r y i n g out t h e t a s k s m e n t i o n e d a b o v e , we must f i r s t a nswer t h e q u e s t i o n o f "How?", f o r e a c h o f t h em. The b a s i c i d e a b e h i n d t h e work r e p o r t e d i n t h i s t h e s i s i s t h i s ; l e t us t a k e a s i m p l e , i d e a l i z e d , model o f a r o b o t i n a n e n v i r o n m e n t , and l e t us s e e what t h e r o b o t r e q u i r e s t o e n a b l e i t t o c a r r y o u t t h e above t a s k s . The model s h o u l d be k e p t a s s i m p l e a s p o s s i b l e , b u t n o t so s i m p l e t h a t t h e above t a s k s d o n ' t make s e n s e . We s h a l l s t a r t w i t h d a t a s t r u c t u r e s and p r o c e d u r e s a s s i m p l e a s p o s s i b l e and p r o c e e d f r o m t h e r e , b u i l d i n g more c o m p l e x s t r u c t u r e s and p r o c e d u r e s as r e q u i r e d . When o u r model r o b o t i s a b l e t o c a r r y o u t t h e a b o v e t h r e e t a s k s t h e n we w i l l be a b l e t o a n s w e r t h e q u e s t i o n o f "How ?" f o r e a c h o f them. A l s o , h o p e f u l l y , we m i g h t have g l e a n e d seme i n s i g h t i n t o what f o r m t h e " w o r l d m o d e l " o f a r e a l r o b o t m i g h t t a k e . As e x t r a m o t i v a t i o n R o b o t S i m u l a t i o n S t u d i e s 15 f o r s e t t i n g up p r o c e d u r e s and d a t a f o r t h e r o b o t , we keep i n mind t h e f o l l o w i n g s i m p l e game w h i c h i s o b v i o u s l y r e l a t e d t o t h e games p l a y e d by young c h i l d r e n : c o n s i d e r an e n v i r o n m e n t w h i c h c o n t a i n s , a p a r t f r o m i t s w a l l s a nd e t h e r f i x e d o b j e c t s , a number o f m o v a b l e o b j e c t s o f v a r i o u s s h a p e s , and an e q u a l number o f f i x e d h o l e s o f v a r i o u s s h a p e s . L e t t h e r o b o t wander a r o u n d and d i s c o v e r and d e s c r i b e t h e m o v a b l e o b j e c t s and h o l e s . Then i t must d e c i d e w h i c h o b j e c t s { i f any ) f i t i n t o w h i c h h o l e s , and t h e n , f o r e a c h o b j e c t w h i c h i t knows f i t s i n t o a c e r t a i n h o l e , move t h a t o b j e c t t h r o u g h t h e e n v i r o n m e n t and i n t o t h e h o l e , i f t h a t i s p o s s i b l e . O n l y t a s k s 1 and 2 a r e d e a l t w i t h i n t h e s y s t e m , s i m p l e as t h e y a r e . I h a v e d e f i n i t e i d e a s a b o u t t a s k 3 b u t t h e y a r e n o t i m p l e m e n t e d . T a s k s 1 and 2 a r e c l o s e l y l i n k e d : t o e x p l o r e an e n v i r o n m e n t t h e r o b o t must move f r o m p l a c e t o p l a c e , w h e r e a s t o move f r o m p l a c e t o p l a c e i t must have some c o n c e p t i o n o f what i t s e n v i r o n m e n t l o o k s l i k e b e f o r e h a n d . I n c o n n e c t i o n w i t h t h e s e t a s k s , t h e most b a s i c q u e s t i o n t h a t a r i s e s i s : "How s h o u l d t h e r o b o t ' s p e r c e p t i o n s o f i t s e n v i r o n m e n t be r e p r e s e n t e d i n i t s memory ? " . C o n c e r n i n g o u r c h o i c e o f r e p r e s e n t a t i o n we have been g u i d e d by a d e s i r e a) f o r s i m p l i c i t y , b) f o r u s e f u l n e s s i n c o n n e c t i o n w i t h t h e t a s k s b e i n g a t t e m p t e d , a n d c) t h a t t h e r e p r e s e n t a t i o n be i n d e p e n d e n t o f s i z e ( ±.e'. a s q u a r e w i t h s i d e s o f l e n g t h 2 i s r e p r e s e n t e d i n t h e same way B o b o t S i m u l a t i o n S t u d i e s 16 a s a s q u a r e w i t h s i d e s o f l e n g t h 100 ) b u t d e p e n d e n t on c o m p l e x i t y . By " c o m p l e x i t y ' * we mean t h e i n t u i t i v e f e e l i n g t h a t , f o r i n s t a n c e , a s q u a r e i s s i m p l e r o r l e s s c o m p l e x t h a n a "W". { See f i g u r e 1. ) I n what f o l l o w s we r e f e r a n t h r o p o r a o r p h i c a l l y t o t h e s i m u l a t e d r o b o t a s " R o b b i e " o r " h i m " ; t h o s e who o b j e c t t o t h i s u s a g e must e v e r y w h e r e s u b s t i t u t e " t h e r o b o t " f o r " R o b b i e " and " i t " f o r "he" o r " h i m " . 2.2 The s i m u l a t e d w o r I d R o b b i e l i v e s i n a c h e s s - b o a r d t y p e o f w o r l d : an n-by-n g r i d o f s g u a r e s where e a c h s q u a r e i s marked w i t h a l e t t e r , C u r r e n t l y t h e v a l u e o f n i s s e t t o 2 8 , b u t t h e p e r f o r m a n c e o f R o b b i e i n no way d e p e n d s on t h i s number. The l a r g e r t h e g r i d , t h e more i n t e r e s t i n g t h e e n v i r o n m e n t s we c a n g i v e R o b b i e t o work i n . The l e t t e r s h a v e t h e f o l l o w i n g m e a n i n g s : ' ' ( b l a n k ) t h e s q u a r e i s v a c a n t . 'B' t h e s q u a r e i s a b a r r i e r : f o r m s p a r t o f t h e i b o u n d a r y o r p a r t o f a f i x e d o b j e c t . 'M* t h e s q u a r e f o r m s p a r t o f a movable o b j e c t . 'H' t h e s q u a r e f o r m s p a r t o f a h o l e . A t any i n s t a n t R o b b i e o c c u p i e s one s q u a r e , s p e c i f i e d by c o o r d i n a t e s ( x , y ) , and i s i n one o f f o u r o r i e n t a t i o n s , n o r t h , s o u t h , e a s t , o r w e s t . An e n v i r o n m e n t p l u s R o b b i e i n a s p e c i f i c p o s i t i o n and o r i e n t a t i o n i s c a l l e d a c o n f i g u r a t i o n ( see f i g u r e 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 one s q u a r e a t a I n t u i t i v e l y , the square i s l e ss complex than the "W". Figure 1. 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 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 |H H 1" H 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 H B B 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 An example of a configuration : 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 that he can "see". There i s a f i x e d object marked with B's, a hole marked with H's, and the M*s mark a movable object that could be moved to f i t into the hole. Figure 2 . R o b o t S i m u l a t i o n S t u d i e s 17 t i m e i n t h e d i r e c t i o n he i s f a c i n g , and c a n t u r n l e f t o r r i g h t o r t h r o u g h 180 d e g r e e s w h i l e r e m a i n i n g on t h e same s q u a r e . H i s s e n s o r y c a p a b i l i t i e s a r e l i m i t e d : he c a n o n l y s e n s e t h e c o n t e n t s o f t h e e i g h t s q u a r e s s u r r o u n d i n g h i m . He c a n o n l y o c c u p y b l a n k s g u a r e s . A s q u a r e marked «B' o r 'H» b l o c k s h i s way. I n g e n e r a l a s q u a r e marked 'M' a l s o b l o c k s h i s way. I f , h o w e v e r , he i s f a c i n g an 'M' s q u a r e he c a n p i c k up t h e whole m o v a b l e o b j e c t , OBJA s a y , o f w h i c h t h a t s q u a r e i s a p a r t . He and OBJA t h e n become a r i g i d body : i f he t a k e s a s t e p c r t u r n s , OBJA goes w i t h h i m , p r o v i d e d no c o l l i s i o n o c c u r s between t h e p r o p o s e d f i n a l p o s i t i o n o f OBJA and some w a l l o r o t h e r o b j e c t . I f s u c h a c o l l i s i o n o c c u r s t h e n t h e c o n f i g u r a t i o n r e m a i n s a s i t was b e f o r e t h e a t t e m p t e d s t e p o r t u r n . The d e f i n i t i o n o f a c o l l i s i o n i s , t o d a t e , r a t h e r u n n a t u r a l , i n t h a t no a c c o u n t i s t a k e n o f o b j e c t s i n t h e a r e a w h i c h i s sw e p t o u t by OBJA d u r i n g t h e e x e c u t i o n o f a t u r n . As a r e s u l t o f R o b b i e ' s m a n o e u v r e s , OBJA may o v e r l a p t h e s g u a r e s o f a h o l e . A f t e r OBJA has been p i c k e d and moved, R o b b i e may d r o p OBJA. T h e r e u p o n R o b b i e and OBJA c e a s e t o be a r i g i d body and he may walk away. 2.3 S o b b i e ^ s m o d e l o f t h e w o r l d s 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 t o m a n i p u l a t e i t . _ 2.3.1 The r i n g r e p r e s e n t a t i o n o f o b j e c t s . I n t h e l i g h t o f t h e r e q u i r e m e n t s o f s i m p l i c i t y and i n d e p e n d e n c e o f s i z e , we c h o s e t o r e p r e s e n t o b j e c t s , m o v a b l e o b j e c t s , h o l e s i n t h e e n v i r o n m e n t , and t h e e n v i r o n m e n t i t s e l f , a s a c y c l i c l i s t o f t h e edges and c o r n e r s t h a t o c c u r when one Robot S i m u l a t i o n S t u d i e s 18 goes r o u n d t h e o b j e c t . The n a t u r a l way t o r e p r e s e n t t h i s w i t h i n t h e c o m p u t e r i s a s a " r i n g " o f l i n k e d nodes where e a c h node g i v e s t h e l e n g t h o f an edge and t h e t y p e o f t u r n ( l e f t o r r i g h t ) a t i t s e n d . fin e x a m p l e i s g i v e n i n f i g u r e 3. D e f i n i t i o n : t h i s r i n g o f n o d e s i s t h e ri_nc[ r e p r e s e n t a t i o n o f an o b j e c t . On e n c o u n t e r i n g s u c h an o b j e c t i n h i s e n v i r o n m e n t , R o b b i e w a l k s r o u n d t h e edge o f t h e o b j e c t , k e e p i n g t o t h e l e f t , a nd g e n e r a t e s t h e a b o v e d e s c r i p t i o n . T h i s w o u l d seem t o be a b o u t as s i m p l e a d e s c r i p t i o n a s one c o u l d d e v i s e . U s i n g i t , we f o u n d i t s t r a i g h t f o r w a r d t o compare two o b j e c t s f o r c o n g r u e n c e ( c a n one be t r a n s l a t e d and r o t a t e d t o l i e e x a c t l y on t o p o f t h e o t h e r ? ) , f o r s i m i l a r i t y ( i s one an e x p a n s i o n o r c o n t r a c t i o n o f t h e o t h e r ? s e e f i g u r e 4 ) , and f o r c o r n e r - c o n g r u e n c e ( b o t h t h e same "up t o c o r n e r s " - i . e . do t h e y b o t h h a v e t h e same number o f e d g e s and c o r n e r s , where t h e c o r n e r t y p e s must a g r e e b u t t h e edge l e n g t h s may n o t ? - s e e f i g u r e 5 ) . I t i s i n t e r e s t i n g t o n o t e t h a t t h e r i n g r e p r e s e n t a t i o n o f an o b j e c t as u s e d h e r e i s v e r y s i m i l a r t o t h e " f e a t u r e r i n g " p r o p o s e d by N o t o n and S t a r k [ N o ] , i n t h e c o n t e x t o f v i s u a l p e r c e p t i o n , as a f o r m a t f o r t h e i n t e r n a l r e p r e s e n t a t i o n o f an o b j e c t i n t h e b r a i n . I n c o n n e c t i o n w i t h t h e o b j e c t - t o - h o l e game m e n t i o n e d i n s e c t i o n 2.1, we a l s o t r i e d t o d e c i d e , g i v e n t h e r i n g d e s c r i p t i o n s o f two o b j e c t s , w h e t h e r one c o u l d be moved t o f i t i n s i d e t h e o t h e r . T h i s d i d n o t seem f e a s i b l e u s i n g r i n g d e s c r i p t i o n s , s o we d e v i s e d a d e c o m p o s i t i o n o f t h e r i n g r e p r e s e n t a t i o n w h i c h i n v o l v e s a d e e p e r a n a l y s i s o f t h e s h a p e o f 6 7 8 9 X ' 9 -10 •11 -12 -13 This "L" - shaped object has the the r i n g - representation diagrammed below. name = OBJECT 3 # edges = 6 top l e f t hand corner (9»5) length=4 turn = L length=2 turn = R y length=3 turn = L s length=2 turn = L Figure 3 S i m i l a r objects. Figure 4. Corner - congruent objects. Figure 5. Robert S i m u l a t i o n S t u d i e s 19 t h e o b j e c t ( o r o f t h e b o u n d a r y o f t h e e n v i r o n m e n t i t s e l f ) . I n f a c t t h i s d e c o m p o s i t i o n i s b a s i c t o most o f t h e p r o c e d u r e s t h a t R o b b i e i s endowed w i t h , so i s o f c e n t r a l i m p o r t a n c e t o t h i s t h e s i s . 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 . I n t h e e n v i r o n m e n t i n w h i c h we o p e r a t e , a r e c t a n g l e i s t h e s i m p l e s t k i n d o f o b j e c t . G i v e n two r e c t a n g l e s , i t i s t r i v i a l t o d e c i d e i f one c a n f i t i n s i d e t h e o t h e r ; a l s o , s u p p o s i n g R o b b i e i s i n s i d e a r e c t a n g u l a r e n v i r o n m e n t , i t i s t r i v i a l t o move f r o m p l a c e t o p l a c e . The n a t u r a l s u g g e s t i o n , t h e n , i s t h a t a more c o m p l i c a t e d o b j e c t o r e n v i r o n m e n t s h o u l d be decomposed i n t o a c o n g l o m e r a t i o n o f o v e r l a p p i n g r e c t a n g l e s . F o r e x a m p l e , an " L " and a "U" a r e decomposed 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 as i n f i g u r e 6 . However i t i s n o t q u i t e s o o b v i o u s hew an o b j e c t s u c h as i n f i g u r e 7 s h o u l d be decomposed i n t o r e c t a n g l e s . What we need a r e a l l t h e " b i g g e s t1 1 r e c t a n g l e s c o n t a i n e d i n an o b j e c t . D e f i n i t i o n : a j a x i m a l _ s u b r e c t a n g _ l e o f an o b j e c t 0 i s a r e c t a n g l e R c o n t a i n e d i n 0 s u c h t h a t e a c h s i d e o f R has a s u b i n t e r v a l i n common w i t h an edge o f 0 . Our r e p r e s e n t a t i o n o f an o b j e c t c o n t a i n s , b e s i d e s t h e r e p r e s e n t a t i o n r i n g , t h e l i s t o f a l l i t s m a x i m a l s u b r e c t a n g l e s ( a b b r e v i a t e d "MRT"s ) . F o r i n s t a n c e t h e o b j e c t i n f i g u r e 7 i s decomposed i n t o t h e c o l l e c t i o n o f MRTs i n f i g u r e 8 . DECOMP i s a b a s i c p r o c e d u r e i n o u r s y s t e m w h i c h d e c o m p o s e s t h e r i n g r e p r e s e n t a t i o n o f an o b j e c t i n t o a l i s t o f a l l i t s Decomposition of simple shapes into overlapping rectangles. Figure 6. top l e f t hand corner £ T r 20 1 r T Q 19 17 , 18R O B J A ± H 8 I -7 9 16 T 1 1 r 15 13 M 12 1 1 r 11 j i I 6 G J 10 I t i s not immediately obvious how to break the shape of OBJA i n t o overlapping rectangles ( but see fi g u r e 8 ). The-digits by each edge give the edge-number. K Figure 7. ' ' • Conceptual decomposition of the shape of OBJA (figure 7) into the MRTs R1 , R2, ... , R9. Figure 8. Robot S i m u l a t i o n S t u d i e s 20 MRTs. I n a s e n s e one c a n s a y t h a t DECOMP " p a r s e s " an o b j e c t i n t o i t s c o n s t i t u e n t MRTs. S i n c e t h e a l g o r i t h m u s e d may be o f i n d e p e n d e n t i n t e r e s t , f u l l d e t a i l s a r e g i v e n i n a p p e n d i x A. What f o l l o w s i s a b r i e f d e s c r i p t i o n o f t h e p r o c e d u r e . The a l g o r i t h m CECOMP D l . [ I n i t i a l i z e ] . S e t up t h e empty MRT l i s t . D L L Take t h e f i r s t l e f t edge L and go t o DB1. DL2. Take t h e n e x t l e f t edge L . I f no more l e f t e d g e s , s t o p and r e t u r n t h e MRT l i s t . DB1. Take t h e f i r s t b o t t o m edge B a f t e r L i n r i n g o r d e r w h i c h i s a c c e s s i b l e from L , t h a t i s , i t w o u l d be p o s s i b l e t o draw a r e c t a n g l e w i t h i t s l e f t s i d e d e f i n e d by L and i t s b o t t o m s i d e d e f i n e d by B. Go t o DR1. DB2. Take t h e n e x t b o t t o m edge B a c c e s s i b l e f r o m L . I f no s u c h b o t t o m edge e x i s t s , go b a c k t o DL2. DR1. Take t h e f i r s t r i g h t edge R a f t e r B w h i c h i s a c c e s s i b l e f r o m L and B , t h a t i s , i t w o u l d be p o s s i b l e t o draw a r e c t a n g l e w i t h i t s l e f t s i d e d e f i n e d by L , i t s b o t t o m s i d e d e f i n e d by B , and i t s r i g h t s i d e d e f i n e d by R. Go t o DT. DR2. Take t h e n e x t r i g h t edge R w h i c h i s a c c e s s i b l e from L and B. I f no s u c h r i g h t edge e x i s t s , go back t o DB2. DT. Check t h r o u g h t h o s e t o p edges w h i c h l i e b e t w e e n t h e r i g h t edge R and t h e l e f t edge L i n r i n g o r d e r , and w h i c h o v e r l a p t h e h o r i z o n t a l i n t e r v a l d e f i n e d by L and R. I f one o f t h e s e l i e s a t o r b e l o w t h e b o t t o m e n d s o f b o t h L and R, t h e n no i n s c r i b e d r e c t a n g l e e x i s t s whose l e f t , b o t t o m , a nd r i g h t s i d e s a r e d e f i n e d by L , B , and R r e s p e c t i v e l y ; go ba c k t o DR2. O t h e r w i s e , l e t T be t h e l o w e s t o f t h e t o p Robot Simulation Studies 21 e d g e s c h e c k e d t h r o u g h . Then t h e r e c t a n g l e whose l e f t , b o t t o m , r i g h t , and t o p s i d e s a r e d e f i n e d by L , B, R and T r e s p e c t i v e l y i s a m a x i m a l s u b r e c t a n g l e : add i t t o t h e MRT l i s t and go back t o DR2. I t may be o b j e c t e d t h a t o n l y t h e m a x i m a l s u b r e c t a n g l e s shown i n f i g u r e 9 a r e n e e d e d i n t h e d e c o m p o s i t i o n o f OEJA o f f i g u r e 7. T h i s i s t r u e , f o r c e r t a i n g u e s t i o n s . E x a mple 1. S u p p o s e we have a n o t h e r o b j e c t OBJB and a s k "Can o b j e c t OBJA be moved t o f i t i n s i d e OEJB ? " . ( T h i n k o f OBJB a s a h o l e i n t h e e n v i r o n m e n t . ) I t i s s u f f i c i e n t i n t h i s c a s e t o know t h a t , under a c e r t a i n t r a n s l a t i o n and r o t a t i o n , e a c h o f t h e m a x i m a l s u b r e c t a n g l e s R1 t o R5 f i t s i n t o OBJB. Example 2 . S u p p o s e we c o n s i d e r OBJA a s an e n v i r o n m e n t f o r R o b b i e , and we a s k R o b b i e t o move f r o m a p o i n t i n R2 t o somewhere i n R5. S u p p o s e a l s o t h a t he knows how t h e m a x i m a l s u b r e c t a n g l e s R1 t o R5 i n t e r s e c t w i t h e a c h o t h e r , i n p a r t i c u l a r t h a t R2 o v e r l a p s R3 and R3 o v e r l a p s R 5 . Then i t i s a f a i r l y s i m p l e t a s k f o r him t o come up w i t h t h e f o l l o w i n g p l a n o f a c t i o n : i ) move o n t o t h e 1-by-2 i n t e r s e c t i o n o f R2 and R3 i i ) move t h r o u g h R3 o n t o t h e 1-by-2 i n t e r s e c t i o n o f R3 and R5 i i i ) move t o t h e r e q u i r e d p o s i t i o n i n R 5 . H o w e v e r , f o r c e r t a i n o t h e r q u e s t i o n s t h e l i s t o f a l l t h e m a x i m a l s u b r e c t a n g l e s o f OBJA i s n e e d e d . Example 1. S u p p o s e we have a n o t h e r o b j e c t OEJB and we ask "Can OBJB be moved t o f i t i n s i d e OBJA ? " . I f OBJB c o n s i s t s o f a This c o l l e c t i o n of MRTs, which covers OBJA of f i g u r e 7, s u f f i c e s f o r some, but not a l l , questions concerning the shape of OBJA. Figure 9. Robot Simulation Studies 22 s i n g l e 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 from t h e l i s t i n f i g u r e 8 t h a t t h e answer i s " y e s " , whereas i t i s not a t a l l o b v i o u s from the l i s t i n f i g u r e 9. Example 2. Suppose we a g a i n c o n s i d e r OBJA as an environment f o r Robbie, but t h i s time 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 of 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 ask "Can Robbie move the 1-by-3 r e c t a n g l e t o the bottom r i g h t -hand c o r n e r of the environment ( i . e . of R5 ) ?". I t i s p o s s i b l e , w i t h a s u i t a b l e p e r u s a l of the l i s t i n f i g u r e 8, t o answer " yes" and i n a d d i t i o n say how t c c a r r y out the t a s k ; but t h i s would be ve r y hard to do from the l i s t i n f i g u r e 9. Cons e g u e n t l y , we r e t a i n the complete l i s t of MRTs of an o b j e c t . { The above examples suggest t h a t we sho u l d use two l i s t s of MRTs of an o b j e c t . c o v e r i n g l i s t : t h o s e MRTs which a re e s s e n t i a l t o c o v e r the o b j e c t . (There i s no way t o c o v e r OBJA of f i g u r e 7 w i t h o u t i n c l u d i n g the MRTs R1, R2, ... R5. ) The secondary l i s t : a l l o f the MRTs not i n the c o v e r i n g l i s t . However, we have not implemented t h i s . } F i g u r e 10 g i v e s examples of shapes f o r which d e c o m p o s i t i o n i n t o MRTs i s c l e a r l y not the b e s t approach, but f o r the moment we i g n o r e these c o m p l i c a t i o n s . 2.3.3 Containment : the a l g o r i t h m CONTAIN Examples of shapes for which representation by straight-forward decomposition into MRTs is clearly not the best approach. Figure 10. Robot S i m u l a t i o n S t u d i e s 23 H a v i n g d e s c r i b e d t h e d e c o m p o s i t i o n o f an o b j e c t i n t o i t s max i m a l s u b r e c t a n g l e s , we a r e now r e a d y t o answer t h e q u e s t i o n , c o n c e r n i n g two o b j e c t s OBJA and OBJB, "Can OBJA be moved t o f i t i n s i d e OBJB ?•». We f i r s t h a v e t o f i n d t h e " s u p e r - r e c t a n g l e " c f e a c h o b j e c t . D e f i n i t i o n : t h e § u _ p e r - r e c t a n c j l e c f an o b j e c t i s t h e s m a l l e s t r e c t a n g l e w h i c h c o n t a i n s t h a t o b j e c t . The p a r t i a l o r d e r i n g g i v e n by t h e r e l a t i o n o f c o n t a i n m e n t b e t w e e n r e c t a n g l e s i s n a t u r a l l y r e p r e s e n t e d a s a l a t t i c e . We c l a s s i f y t h e MRTs o f e a c h o b j e c t a c c o r d i n g t o t h e i r d i m e n s i o n s and a r r a n g e them i n t h e l a t t i c e g i v e n by t h e c o n t a i n m e n t r e l a t i o n . S i n c e s e v e r a l MRTs i n d i f f e r e n t p a r t s o f an o b j e c t may have t h e same d i m e n s i o n s t h e l a t t i c e s t r u c t u r e i s a c t u a l l y i m p o s e d on e q u i v a l e n c e c l a s s e s o f MRTs r a t h e r t h a n on i n d i v i d u a l MRTs. The l a t t i c e o f an o b j e c t i s i n v a r i a n t u n d e r r o t a t i o n s . F o r e x a m p l e , f o u r r e c t a n g l e s o f d i m e n s i o n s 3 - b y - 4 , 3 - b y - 9 , 7 - b y - 5 , and 7-by-9 w o u l d be a r r a n g e d i n a diamond s h a p e d l a t t i c e w i t h t h e ( t h e e q u i v a l e n c e c l a s s c o n s i s t i n g o f t h e } 7-by-9 r e c t a n g l e a t t h e t o p c o v e r i n g t h e two i n c o m p a r a b l e r e c t a n g l e s 3-by-9 and 7 - b y - 5 , w h i l e t h e 3-by-4 r e c t a n g l e w o u l d be a t t h e b o t t o m , c o v e r e d by t h e 3-by-9 and 7-by-5 r e c t a n g l e s . The t o p p o s i t i o n s o f t h e l a t t i c e c o r r e s p o n d t o { e q u i v a l e n c e c l a s s e s o f } MRTs i n t o one c f w h i c h e v e r y o t h e r MET c o u l d f i t . As an e x a m p l e , t h e MRTs o f f i g u r e 7 f o r m t h e l a t t i c e shown i n f i g u r e 11. The t o p p o s i t i o n s i n t h i s l a t t i c e c o r r e s p o n d t o MRTs o f d i m e n s i o n s 3-by-6, 1-by-12, 7 - b y - 2 . Now we o u t l i n e t h e a l g o r i t h m CONTAIN f o r a n s w e r i n g t h e 7-by-r12 ( s u p e r - r e c t a n g l e 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 the MRTs o f OBJA o f f i g u r e 7. Figure 11 Robot S i m u l a t i o n S t u d i e s 24 q u e s t i o n of containment. The input to CONTAIN c o n s i s t s of two ob j e c t s OBJA and OBJB where each i n p u t o b j e c t has been decomposed i n t o a l i s t of MRTs, and the component MRTs organised i n t o a l a t t i c e s t r u c t u r e . The output i s e i t h e r a s t r a i g h t "no", or "yes" together with the r o t a t i o n and t r a n s l a t i o n r e q u i r e d t o move OBJA i n t o OBJB ( i g n o r i n g the c o m p l i c a t i o n s of p o s s i b l e o b s t r u c t i o n s such as other o b j e c t s , w a l l s , e t c . ) . For i n s t a n c e , i f one of the i n p u t arguments to CONTAIN were the OBJA of f i g u r e 7, i t would be accompanied by the l i s t of 9 MRTs i n d i c a t e d i n f i g u r e 8 and the l a t t i c e shown i n f i g u r e 11. l J h e _a l 2o r i^m_C08TAIN CT1. Can the s u p e r - r e c t a n g l e of OBJA f i t i n s i d e the s u p e r - r e c t a n g l e of OBJB, or i n other words are the x- and y-dimensions of OBJA both l e s s than or equal to the x- and y-dimensions cf OBJB ? If not, answer "no" and s t o p . CT2. I f OBJB i s a s i n g l e r e c t a n g l e , answer "yes" and stop. CT3. Can the s u p e r - r e c t a n g l e of OBJA f i t i n t o one of the top MRTs of OBJB ? I f so, answer "yes" and stop. If not, and OBJA i s a s i n g l e r e c t a n g l e , answer "no" and stop ; otherwise proceed. CT4. Can each of the top MRTs of OBJA f i t i n t o one of the top MRTs of OBJB ? I f not, answer "no" and stop. < Now we know t h a t , d i s r e g a r d i n g the r e l a t i v e p o s i t i o n s of the MRTs of CBJA, every MRT of OBJA can f i t i n t o OBJB somewhere. > R o b o t S i m u l a t i o n S t u d i e s 25 CT5. Take e a c h o f t h e t o p MRTs c f OBJA i n t u r n a nd c o u n t how many d i f f e r e n t ways t h e r e a r e t o f i t i t i n t o MRTs o f OBJB, t h e n p i c k an MET A* o f OBJA f o r w h i c h t h e number o f d i f f e r e n t ways i s a minimum. CT6. F o r e a c h o f t h e d i f f e r e n t ways i n w h i c h A* c a n f i t i n t o O B J B , t a k e t h e t r a n s l a t i o n o f OBJA r e q u i r e d and c h e c k i f a l l t h e r e m a i n i n g MRTs o f OBJA a r e i n d e e d i n s i d e an MRT o f OEJB. I f a s u i t a b l e t r a n s l a t i o n i s f o u n d , a n s w e r " y e s " and s t o p ; o t h e r w i s e , a n s w e r "no" and s t o p . F i g u r e 12 shows two c a s e s i n w h i c h CT6 must be i n v o k e d t o a n s w e r " y e s " o r "no" c o r r e c t l y . The above a l g o r i t h m w o r k s r e a s o n a b l y w e l l f o r two o b j e c t s o f s i m i l a r s i z e and c o m p l e x i t y o f s h a p e . H o w e v e r , i t i s a " b r u t e - f o r c e " s o l u t i o n t o t h e p r o b l e m and i m p r o v e m e n t s c o u l d be made. F o r i n s t a n c e , t h e s e a r c h i n g r e g u i r e d i n CT5 c o u l d be c o n s i d e r a b l y r e d u c e d by m a k i n g u s e o f c o n n e c t e d n e s s when t h e o b j e c t s b e i n g compared c o n s i s t o f l o n g s e q u e n c e s o f c o n n e c t e d MRTs, a s i l l u s t r a t e d i n f i g u r e 1 3. T h i s w o u l d be done by u t i l i z i n g t h e f o l l o w i n g o b v i o u s f a c t a b o u t c o n n e c t i v i t y : I f MRTs A1 and A2 a r e c o n n e c t e d i n OEJA, and A1 c a n f i t i n t o MRT B1 o f OBJB, t h e n A2 c a n o n l y f i t i n t o B1 o r some MRT o f OBJB 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 B 1 . 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 a nd e x e c u t i o n . The p l a n s d e a l t w i t h i n t h e s y s t e m so f a r a r e m e r e l y t h o s e r e q u i r e d f o r R o b b i e t o move f r o m p l a c e t o p l a c e i n a r e a s o n a b l y ] OBJA OBJB CONTAIN (OBJA,OBJB) doesn't answer "no" until CT6« U OBJA L_ OBJB CONTAIM (OBJA.OBJB) doesn't answer "yes" until 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. O B J A O B J B An example of a p a i r of objects f o r which COI.TALN(OBJA,OBJB) performs p a r t i c u l a r l y badly. Figure 13. R o b o t S i m u l a t i o n S t u d i e s 26 e f f i c i e n t manner w i t h i n an e n v i r o n m e n t where t h e o n l y o b s t a c l e s a r e s m a l l f i x e d o b j e c t s . At t h e t i m e o f w r i t i n g e v e n t h e s e p l a n s a r e l i m i t e d , i n t h a t R o b b i e c a n n o t y e t d e a l s a t i s f a c t o r i l y w i t h t h e u n e x p e c t e d o c c u r r e n c e o f l a r g e f i x e d o r movable o b j e c t s w h i l e e x e c u t i n g a p l a n . We make e x t e n s i v e use o f R o b b i e ' s model of t h e w o r l d i n t h e c o n s t r u c t i o n and e x e c u t i o n o f p l a n s . [The r e l a t i o n b e t w e e n p l a n s and m o d e l s o f t h e w o r l d i s c o n s i d e r e d f u r t h e r i n a p p e n d i x B. } We t a k e t h e d e c o m p o s i t i o n o f t h e e n v i r o n m e n t i n t o MRTs and s e t up f o r e v e r y p a i r o f o v e r l a p p i n g MRTs an " o v e r l a p " l i n k and i n s e r t b e t w e e n them an " i n t e r s e c t i o n r e c t a n g l e " { a b b r e v i a t e d "IRT" ) w h i c h s p e c i f i e s how t h e y o v e r l a p . Now s u p p o s e R o b b i e i s a t p o s i t i o n A i n M RT 1 i n t h e e n v i r o n m e n t , and he must r e a c h p o s i t i o n B i n MRT5 i f t h a t i s p o s s i b l e , a s i l l u s t r a t e d i n f i g u r e 14. The e n v i r o n m e n t , when decomposed i n t o MRTs and w i t h o v e r l a p l i n k s and i n t e r s e c t i o n r e c t a n g l e s i n s e r t e d , may be v i e w e d a s a g r a p h whose v e r t i c e s a r e MRTs and whose e d g e s a r e t h e o v e r l a p l i n k s b e t w e e n MRTs. The p r o g r a m MAKPLAN u s e s a p a t h - f i n d i n g a l g o r i t h m t o f i n d a c h a i n o f MRTs c o n n e c t e d by o v e r l a p l i n k s f r o m M RT1 t o MRT5.. I f s u c h a c h a i n i s f o u n d , i t c o n s t i t u t e s a p l a n o f a c t i o n f o r g o i n g f r o m A t o B ; o t h e r w i s e , no s u c h c h a i n e x i s t s and i t i s i m p o s s i b l e t o r e a c h B f r o m A. F i g u r e 15. i l l u s t r a t e s t h e c o n s t r u c t i o n o f a p l a n t o r e a c h p o s i t i o n B. The p a t h - f i n d i n g a l g o r i t h m may be d e s c r i b e d a s f o l l o w s . C a l l t h e s t a r t i n g node i n t h e g r a p h HERE and t h e node t o w h i c h a p a t h must be f o u n d THERE. C o l o u r HEBE r e d and THERE b l u e . No o t h e r n o des a r e c o l o u r e d i n i t i a l l y . A w a v e f r o n t o f r e d nodes Decomposition of E i n t o MRTs plus overlap l i n k s and intervening i n t e r s e c t i o n rectangles (shaded). Figure 14. MRT4 MRT1 HST2 MET 5 The graph form of environment E. Sta r t i n MRT1 Hove through MRT1 i n t o IRT1 Move through MRT3 i n t o 1RT4 Move through MRT4 in t o IRT5 Ends i n MRT5. Prin t e d output of the path-finding program MAKPLAN. MRT1 MRT3 MRT4 MRT5 o IRT1 IRT4 IRT5 The chain of pointers produced by MAKPLAN. Figure 15. R o b o t S i m u l a t i o n S t u d i e s 27 e x p a n d s i n s t e p s f r o m HERE and a w a v e f r o n t o f b l u e n o d e s e x p a n d s i n s t e p s f r o m THERE. A t s t e p n t h e r e d w a v e f r o n t c o n s i s t s o f a l l nodes whose s h o r t e s t p a t h back t o HERE i s o f l e n g t h n , and t h e b l u e w a v e f r o n t c o n s i s t s o f a l l nodes whose s h o r t e s t p a t h back t o THERE i s o f l e n g t h n . A node r e t a i n s t h e c o l o u r f i r s t a s s i g n e d t o i t . The r e d and b l u e w a v e f r c n t s a r e e x p a n d e d i n a l t e r n a t e s t e p s . When t h e w a v e f r o n t s m eet, a p a t h has been f o u n d f r o m HERE t o THERE, and t h i s i s t h e p a t h p r o d u c e d by t h e a l g o r i t h m . N o t e t h a t t h i s i s a p a t h o f m i n i m a l l e n g t h , and t h a t i t w o u l d be a s i m p l e m a t t e r t o m o d i f y t h e a l g o r i t h m t o o b t a i n a l l p a t h s f r o m HERE t o THERE. The a l g o r i t h m PF_. P F1 . [ I n i t i a l i z e . ] C o l o u r t h e node HERE r e d and t h e node THERE b l u e . S e t up t h e l i s t RWAVE c o n s i s t i n g of t h e node HERE a l o n e , and t h e l i s t BWAVE c o n s i s t i n g o f THERE a l o n e . P F 2 . [ E x p a n d RWAVE. ] S e t up t h e t e m p o r a r y l i s t RWAVEt and i n i t i a l i z e i t t o be e m p t y . F o r e a c h node P i n t h e RWAVE l i s t , t a k e e a c h node Q t h a t i s c o n n e c t e d by an o v e r l a p l i n k t o P. T h r e e c a s e s a r i s e . PF2.1 I f Q i s n e i t h e r r e d n o r b l u e t h e n c o l o u r Q r e d , add Q to t h e l i s t RWAVE#, and s e t a p o i n t e r f r o m Q b a c k t o P . PF2.2 I f Q i s a l r e a d y r e d t h e n do n o t h i n g - e i t h e r Q was c o l o u r e d a t an e a r l i e r s t a g e o r i s i t s e l f a member o f RWAVE. PF2.3 I f Q i s a l r e a d y b l u e t h e n a c o n n e c t i o n has been f o u n d b e t w e e n a r e d p a t h e m a n a t i n g f r o m HERE and a b l u e p a t h e m a n a t i n g f r o m THERE. R e v e r s e t h e p o i n t e r s a l o n g R o b o t S i m u l a t i o n S t u d i e s 28 t h e r e d p a t h and s e t a p o i n t e r f r o m P t o Q, so t h a t a d i r e c t e d c h a i n o f nodes f r o m HERE t o THERE r e m a i n s , and s t o p . When a l l t h e n o d e s P i n t h e RWAVE l i s t have been c o n s i d e r e d , r e s e t RWAVE t o t h e new l i s t RWAVE#. P F 3 . [ E x p a n d BWAVE.] S e t up t h e t e m p o r a r y l i s t BWAVE* and i n i t i a l i z e i t t o be e m p t y . F o r e a c h node P i n t h e BWAVE l i s t , t a k e e a c h node Q t h a t i s c o n n e c t e d by an o v e r l a p l i n k t o P . T h r e e c a s e s a r i s e . PF3.1 I f Q i s n e i t h e r r e d n o r b l u e t h e n c o l o u r Q b l u e , a d d Q t o t h e l i s t BWAVE#, and s e t a p o i n t e r f r o m Q back t o P. PF3.2 I f Q i s a l r e a d y b l u e t h e n do n o t h i n g - e i t h e r Q was c o l o u r e d a t an e a r l i e r s t a g e o r i s i t s e l f a member o f B WAVE. PF3.3 I f Q i s a l r e a d y r e d t h e n a c o n n e c t i o n has been f o u n d b e t w e e n a r e d p a t h e m a n a t i n g f r o m HERE and a b l u e p a t h e m a n a t i n g f r o m THERE. R e v e r s e t h e p o i n t e r s a l o n g t h e r e d p a t h and s e t a p o i n t e r f r o m Q t o P , so t h a t a d i r e c t e d c h a i n o f nodes from HERE t o THERE r e m a i n s , and s t o p . When a l l t h e n o d e s P i n t h e BWAVE l i s t have been c o n s i d e r e d , r e s e t BWAVE t o t h e new l i s t BWAVE*. PFU. [ No p a t h e x i s t s . ] I f e i t h e r t h e RWAVE l i s t o r t h e BWAVE l i s t i s e m p t y , s t o p and r e p o r t f a i l u r e . O t h e r w i s e go back t o P F 2 . The a l g o r i t h m i s i l l u s t r a t e d i n f i g u r e 16.. The a l g o r i t h m was w r i t t e n q u i t e i n d e p e n d e n t l y o f E o h l , who d i s c u s s e s p a t h 0 © i s a node that has been coloured red. i s a node that has been coloured blue. The e n c i r c l e d groups of nodes of the graph are the successive wavefronts as found by the algorithm PF. The table below gives the order i n which the wavefronts are found. Successive RWAVEfronts Successive BWAVEfronts The path Nl , N3, N6, N11 , N H from HERE to THERE i s found when advancing the BWAVEfront f o r the second time. Example to i l l u s t r a t e the a c t i o n of the algorithm PF on a graph. Figure 16. Robot S i m u l a t i o n S t u d i e s 29 p r o b l e m s i n d e p t h and d e s c r i b e s a s i m i l a r p a t h - f i n d i n g a l g o r i t h m i n s i m i l a r l a n g u a g e [ P b , p . 1 5 ] . A p l a n p r o d u c e d by MAKPLAN i s e x e c u t e d by t h e p r o g r a m EXPLAN. The e x e c u t i o n o f a p l a n i s h i e r a r c h i c a l l y o r g a n i s e d . EXPLAN c a l l s on MOVE, MOVE c a l l s cn L I N E A R , LINEAR c a l l s on STEP and TURN, and t h e e f f e c t s o f STEP and TURN a r e d e f i n e d by t h e s i m u l a t e d r e a l i t y . MOVE i s i n c h a r g e o f e a c h l e g o f t h e p l a n , where a t y p i c a l l e g i s "move t h r o u g h MRT3 i n t o I R T 4 " ; i t i s a l s o i n c h a r g e o f a v o i d i n g any u n e x p e c t e d o b s t a c l e s . LINEAR i s i n c h a r g e o f moving as l i n e a r l y a s p o s s i b l e f r o m R o b b i e ' s c u r r e n t p o s i t i o n t o a s p e c i f i e d d e s t i n a t i o n p o s i t i o n . One o f t h e d i f f i c u l t i e s i n h e r e n t i n a n y s y s t e m f o r e x e c u t i n g a p l a n i s d e a l i n g w i t h t h e u n e x p e c t e d . T h i s t a k e s d i f f e r e n t f o r m s a t d i f f e r e n t l e v e l s . A t t h e l o w e s t l e v e l i n o u r s y s t e m , STEP c a n f a i l b e c a u s e t h e s g u a r e i n f r o n t o f R o b b i e i s not v a c a n t . TURN c a n f a i l o n l y when R o b b i e i s h o l d i n g an o b j e c t . LINEAR c a n f a i l i f STEP f a i l s , and r e p o r t s t h i s b a c k t o MOVE.. MOVE f a i l s when LINEAR f a i l s , a s s u m e s t h e f a i l u r e i s due t o an u n e x p e c t e d o b j e c t , and t a k e s a v o i d i n g a c t i o n w i t h c a l l s t o STEP and TURN. EXPLAN f a i l s i f MOVE p e r s i s t s i n f a i l i n g a f t e r s e v e r a l a t t e m p t s a t a v o i d i n g a c t i o n , and r e p o r t s f a i l u r e b a c k t o t h e c o n t r o l p r o g r a m . I n a more s o p h i s t i c a t e d s y s t e m we would h a v e , a t t h i s l e v e l , r e - p l a n n i n g by MAKPLAN. 2.4 E x £ l o r a t i o n So f a r we ha v e nowhere i n d i c a t e d e i t h e r how R o b b i e i s t o g e n e r a t e t h e r i n g - d e s c r i p t i o n o f h i s e n v i r o n m e n t i n t h e f i r s t R o b o t S i m u l a t i o n S t u d i e s 30 p l a c e , o r how he m i g h t f i r s t f i n d an i s o l a t e d o b j e c t and t h e n g e n e r a t e t h i s o b j e c t s ' r i n g - d e s c r i p t i o n . We e f f e c t i v e l y a l l o w a c h e a t i n o r i g i n a l l y g e n e r a t i n g t h e r i n g - d e s c r i p t i o n . The p r o c e d u r e FIND s e n d s R o b b i e o f f i n a s t r a i g h t l i n e u n t i l a 'B' s q u a r e i s f o u n d . Then t h e p r o c e d u r e FOLLOW c a u s e s R o b b i e t o f o l l o w t h e b o u n d a r y t h r o u g h 360 d e g r e e s , u s i n g a s e t o f p r o c e d u r e s c a l l e d RINGS t o g e n e r a t e t h e r i n g -d e s c r i p t i o n a s he g o e s . T h i s i s a r a t h e r u n i n t e l l i g e n t way t o p r o c e e d . A b e t t e r a p p r o a c h , w h i c h has n o t b e e n i m p l e m e n t e d , w o u l d be a l o n g t h e f o l l o w i n g l i n e s . R o b b i e s t a r t s w i t h a p r e c o n c e i v e d n o t i o n o f what t h e e n v i r o n m e n t l e e k s l i k e - t h e s i m p l e s t one p o s s i b l e , w h i c h has a s q u a r e b o u n d a r y w a l l and i s o t h e r w i s e e m p t y . He makes random p r o b e s i n v a r i o u s d i r e c t i o n s , and whenever he e n c o u n t e r s an o b j e c t ( o r w a l l o r h o l e ) t h a t d o e s n o t f i t w i t h h i s p r e v i o u s c o n c e p t i o n o f t h e e n v i r o n m e n t he s e t s o f f t o e x p l o r e t h i s o b j e c t by f o l l o w i n g i t s b o u n d a r y u n t i l he i s q u i t e c l e a r how t h e new o b j e c t f i t s i n t o h i s m o d e l o f t h e e n v i r o n m e n t . To f i n d i s o l a t e d o b j e c t s R o b b i e d o e s t h e f o l l o w i n g f o r e a c h MRT o f h i s e n v i r o n m e n t . F i r s t he goes t o i t , u s i n g PLANS, t h e n he u s e s t h e p r o c e d u r e EXPLORE t o e x p l o r e i t . EXPLORE i s , a t t h e t i m e o f w r i t i n g , e x t r e m e l y c r u d e : i t m e r e l y s e n d s R o b b i e t o t h e c e n t r e o f t h e MRT, and i f by c h a n c e he e n c o u n t e r s a n o n - b l a n k s q u a r e he u s e s t h e p r o c e d u r e FOLLOW t o f o l l o w t h e b o u n d a r y o f t h e o b j e c t o f w h i c h t h i s s q u a r e was a p a r t . Robot Simulation Studies 2.5 Summary of Rpbbie_^s world On the leve l of direct contact with the outside world, Robbie knows his position and orientation and can "see" the eight squares surrounding him, and possesses a pickup arm which, when "active", "holds" a movable object in the outside world. The data structures used in Robbie's conceptual model of the world are extremely simple, at the top level he has two pointers and four stacks of objects. One pointer, called "home", points to the header of the ring representation of his environment. The other pointer, called "currentnsrt", points to the MRT of the environment in which'he i s currently located. The stacks are used for the four different kinds cf objects that Robbie may find i n his environment : fixed objects, moveable objects, holes, and anything else that doesn't f i t into one of the f i r s t three categories. The header of the ring representation of the. environment or of any object contains several pointers. Pour point into the ring representation (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 structure associated with the MRTs of that object. The pointer to the l a t t i c e structure 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 S i m u l a t i o n S t u d i e s 3 2 p a i r o f o v e r l a p p i n g MRTs p o s s e s s e s a p o i n t e r t o t h e i n t e r s e c t i o n r e c t a n g l e o f t h a t p a i r . The p r o g r a m s w h i c h b u i l d and m a n i p u l a t e R o b b i e ' s model o f t h e w o r l d w i l l now be l i s t e d . T h e s e s h o u l d be r e g a r d e d as b e i n g p a r t and p a r c e l o f h i s model : t h e p r o g r a m s and t h e r e p r e s e n t a t i o n s on w h i c h t h e y a c t a r e i n e x t r i c a b l y i n t e r t w i n e d . RINGS s i m p l y c o n s t r u c t s a r i n g r e p r e s e n t a t i o n when R o b b i e i s f o l l o w i n g t h e b o u n d a r y 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 l i s t o f MRTs f r o m a r i n g r e p r e s e n t a t i o n . SETOLAP c o n s t r u c t s t h e o v e r l a p p o i n t e r s . LATCONS c o n s t r u c t s t h e l a t t i c e s t r u c t u r e o f an o b j e c t f r o m i t s l i s t o f MRTs. FIND and FOLLOW f i r s t f i n d and t h e n f o l l o w t h e b o u n d a r y o f t h e e n v i r o n m e n t c r o f an o b j e c t . PLANS i n c o r p o r a t e s MAKPLAN and EX PLAN , and i s p e r h a p s t h e most o f t e n u s e d p r o g r a m , MAKPLAN u s e s t h e o v e r l a p p o i n t e r s t o c o n s t r u c t a p l a n w h i c h i s t h e n e x e c u t e d i n h i e r a r c h i c a l f a s h i o n by EXPLAN . CONGRUENT , C_CONGRU ENT , SIMILAR and CONTAIN a r e u s e d t o compare t h e s h a p e s o f two o b j e c t s . EXPLORE f i n d s new i s o l a t e d o b j e c t s . Robot S i m u l a t i o n S t u d i e s 33 C h a p t e r 3 ROSS :a r o b o t s i m u l a t i o n s y s t e m 3.1 How t o use 3.1.1 G e n e r a l d e s c r i p t i o n ROSS i s an i n t e r a c t i v e c o m p u t e r p r o g r a m w h i c h s i m u l a t e s a r o b o t l i v i n g i n a t w o - d i m e n s i o n a l , r e c t a n g u l a r , t y p e o f e n v i r o n m e n t . The r o b o t has t h e b a s i c a b i l i t i e s t o t a k e s t e p s and t o t u r n , and t o p i c k u p , m a n i p u l a t e , and d r o p m ovable o b j e c t s , at a h i g h e r l e v e l i t c a n e x p l o r e and w a l k a b o u t t h e e n v i r o n m e n t i n a r e a s o n a b l y i n t e l l i g e n t manner. The e n v i r o n m e n t c o n s i s t s o f a r e c t a n g u l a r g r i d i n w h i c h s g u a r e s a r e l a b e l l e d a s b e l o n g i n g t o t h e b o u n d a r y , t o f i x e d o r m o v a b l e o b j e c t s , t o h o l e s , o r t o o t h e r t h i n g s w h i c h a r e c a l l e d " o d d i t i e s " . The r o b o t i t s e l f , c h r i s t e n e d " R o b b i e " , may be c o n c e i v e d o f as a b l i n d man o c c u p y i n g a s i n g l e s q u a r e and a b l e t o s e n s e t h e l a b e l s o f h i s e i g h t n e a r e s t n e i g h b o u r s . H i s s i t u a t i o n m i g h t a l s o be compared w i t h t h a t o f a man w i t h good e y e s i g h t w a n d e r i n g t h r o u g h a dense f o r e s t . I n t h e c o u r s e o f a ROSS e p i s o d e , t h e u s e r s i t s a t a c o m p u t e r t e r m i n a l w i t h a t y p e w r i t e r k e y b o a r d and CRT d i s p l a y R o b o t S i m u l a t i o n S t u d i e s 34 s c r e e n . He i s s u e s ROSS a c t i o n commands and w a t c h e s R o b b i e e x e c u t e them by means o f s n a p s h o t s w h i c h p e r i o d i c a l l y a p p e a r on t h e s c r e e n . A s n a p s h o t c o n s i s t s o f a p i c t u r e o f t h e e n v i r o n m e n t w i t h a s i n g l e " 3 " c h a r a c t e r m a r k i n g R o b b i e ' s p r e s e n t p o s i t i o n a n d , u s u a l l y , a t r a i l o f d o t s r e c o r d i n g h i s r e c e n t m o t i o n s . B e l o w t h e p i c t u r e a p p e a r a l l t h e d e t a i l s o f R o b b i e ' s p h y s i c a l s t a t e ( s e n s e s , p o s i t i o n , o r i e n t a t i o n and what he i s h o l d i n g i f a n y t h i n g ) and a few d e t a i l s o f h i s m e n t a l s t a t e , o r model o f t h e w o r l d (what MRT he t h i n k s h e ' s i n , and t h e numbers o f , r e s p e c t i v e l y , f i x e d o b j e c t s , m ovable o b j e c t s , and h o l e s known t o him a t t h i s t i m e ) . An MRT i s , r o u g h l y , any r o o m , h a l l , o r p a s s a g e w a y i n h i s e n v i r o n m e n t ; t h e d e f i n i t i o n i s i n s e c t i o n 2 . 3 . 2 . Between t h e p i c t u r e o f t h e e n v i r o n m e n t and t h e d e t a i l s o f R o b b i e ' s s t a t e t h e r e i s a " c u r t a i n " o f d o t s drawn a c r o s s t h e s c r e e n : t h i s i s t o r e m i n d t h e u s e r t h a t a l t h o u g h he c a n v i e w t h e e n v i r o n m e n t a s a w h o l e , R o b b i e c a n n o t ; h i s o n l y d i r e c t c o n t a c t w i t h t h e e n v i r o n m e n t i s t h r o u g h h i s " s e n s e s " . I s h o u l d a l s o m e n t i o n t h a t R o b b i e i s a l l o w e d t o r e f e r t o h i s a b s o l u t e p o s i t i o n w i t h i n h i s e n v i r o n m e n t , and i m m e d i a t e l y p o i n t o u t t h a t , i f we a l l o w him t o c o u n t h i s s t e p s and t u r n s , a s I d o , t h e n t h i s i s no a d d i t i o n t o h i s k n o w l e d g e . F o r , i f he d i d n ' t knew h i s a b s o l u t e p o s i t i o n t h e n he c o u l d t a k e h i s i n i t i a l p o s i t i o n a s t h e o r i g i n and r e l a t e a l l h i s s u b s e q u e n t p o s i t i o n s t o t h i s . I n r e f e r r i n g t o a p o s i t i o n a s ( x , y ) , x c o u n t s r o w s f r o m t h e t o p down and y c o u n t s c o l u m n s f r o m l e f t t o r i g h t . The u s e r c a n a l s o i s s u e a c o m p a r a t i v e command a s k i n g R o b b i e Robot S i m u l a t i o n S t u d i e s 35 t o c o m p a r e t h e s h a p e s o f two known o b j e c t s i n one o f f o u r w a y s . I n a d d i t i o n t o t h e a c t i o n and c o m p a r a t i v e commands which a r e e x e c u t e d by R o b b i e h i m s e l f , t h e r e a r e t h e g l o b a l and d i s p l a y commands w h i c h a r e e x e c u t e d by t h e s u p p o r t i n g s y s t e m . D e f i n i t i o n : a c o n f i g u r a t i o n c o n s i s t s o f an e n v i r o n m e n t p l u s R o b b i e ' s p h y s i c a l s t a t e a t a p a r t i c u l a r i n s t a n t . The g l o b a l commands a r e us e d 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 e p i s o d e , o r p e r h a p s t o w i p e o u t a l l o f B o b b i e ' s c u r r e n t model o f t h e w o r l d . The d i s p l a y commands a l l o w t h e u s e r t o c o n t r o l t h e p r o d u c t i o n o f s n a p s h o t s and t o o b t a i n p r i n t o u t s o f v a r i o u s o t h e r i n f o r m a t i o 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 by t h e u s e r , ROSS assumes by d e f a u l t t h e t r i v i a l c o n f i g u r a t i o n c o n s i s t i n g o f a l a r g e s i n g l e empty s q u a r e w i t h R o b b i e i n t h e m i d d l e , f a c i n g n o r t h . A c o m p l e t e r e c o r d o f t h e c o n v e r s a t i o n between t h e u s e r a nd ROSS ( s n a p s h o t s e x c l u d e d ) , and v a r i o u s o t h e r i n f o r m a t i o n , i s w r i t t e n i n a d e b u g g i n g f i l e . T h i s c a n be v i e w e d a t any t i m e d u r i n g o r a f t e r a ROSS e p i s o d e . To a i d i n r e v i e w i n g an e p i s o d e l a t e r , e v e r y s n a p s h o t i s numbered and a r e f e r e n c e t o i t p l a c e d i n t h e d e b u g g i n g f i l e . 3.1,2 Commands The f i r s t word o f a command must b e g i n i n t h e f i r s t c h a r a c t e r p o s i t i o n o f a l i n e , and t h e f i r s t t h r e e c h a r a c t e r s o f t h i s word s u f f i c e f o r ROSS t o i n t e r p r e t t h e r e s t o f t h e command c o r r e c t l y . No b l a n k s h o u l d a p p e a r b e t w e e n a c o l o n and a R o b o t S i m u l a t i o n S t u d i e s 36 f o l l o w i n g w o r d . I f p a r t o f a word o r p h r a s e i s u n d e r l i n e d t h e n t h e n o n - u n d e r l i n e d p a r t may be o m i t t e d : ROSS w i l l s t i l l i n t e r p r e t t h e word c o r r e c t l y . The commands a r e d e s c r i b e d i n f o u r g r o u p s : G l o b a l A c t i o n C o m p a r a t i v e D i s p l a y . G l o b a l Commands FIXED An i n t e r a c t i v e p r o c e d u r e i s e n t e r e d w h i c h p r o m p t s t h e u s e r t o s p e c i f y t h e f i x e d p a r t o f t h e e n v i r o n m e n t by means o f t h e f o l l o w i n g f i x e d - f o r m a t sub-commands. CHARS=ch C a u s e s a l l s g u a r e s s p e c i f i e d i n s u b s e q u e n t ROW and COL sub-commands t o be l a b e l l e d w i t h t h e s i n g l e c h a r a c t e r * c h ' , u n t i l a n o t h e r CHARS sub-command i s r e c e i v e d . I n a b s e n c e o f a CHARS sub-command t h e c h a r a c t e r 'B' i s a s s u m e d . T h i s c h a r a c t e r i s r e f e r r e d t o a s t h e f i l l c h a r a c t e r . E x a m p l e : Robot S i m u l a t i o n S t u d i e s 37 CHARS=H BOS=x10x2,COL=y*Uy2 L a b e l s s q u a r e s w i t h t h e f i l l c h a r a c t e r , as i l l u s t r a t e d i n t h e e x a m p l e s . H e r e x 1 , x 2 , y 1 , y 2 a r e two d i g i t i n t e g e r s , p o s s i b l y w i t h a l e a d i n g z e r o , and £ i s r e p l a c e d by e i t h e r o r ' - » . E x a m p l e s : ROW=02- 12,COL = 05-17 C a u s e s a l l s q u a r e s i n t h e r e c t a n g l e d e l i m i t e d b y , and i n c l u d i n g , rows 2 t o 12 and c o l u m n s 5 t o 17 t o be l a b e l l e d w i t h t h e c u r r e n t f i l l c h a r a c t e r . ROW=0 2&12,COL=0 5&17 C a u s e s t h e f o u r s q u a r e s a t p o s i t i o n s ( 2 , 5 ) , ( 2 , 1 7 ) , ( 1 2 , 5 ) , (12,17) t o be l a b e l l e d w i t h t h e f i l l c h a r a c t e r . ROH=02S12 fCOl=0 5-17 L a b e l s t h e s q u a r e s f r o m p o s i t i o n s 5 t o 17 i n c l u s i v e i n r o w s 2 and 12 w i t h t h e f i l l c h a r a c t e r . POSITION=x,y P l a c e s R o b b i e i n s q u a r e ( x , y ) . ORIENTATION=d C a u s e s R o b b i e t o f a c e n o r t h , e a s t , s o u t h , o r Robot S i m u l a t i o n S t u d i e s 38 west a c c o r d i n g as the d i g i t d i s 0 , 1 ,2., or 3 r e s p e c t i v e l y . MARKER=m Causes Robbie's motions to be recorded i n the snapshots by the c h a r a c t e r ' m», Example: M&RKER=. FIN STOP Both cause c o n t r o l to r e t u r n to the user. MOBILE An i n t e r a c t i v e procedure i s entered which prompts the user to s p e c i f y the mobile o b j e c t s i n the environment with f r e e - f o r m a t s p e c i f i c a t i o n s . In t e r m i n a l mode t b i s procedure i s s e l f - e x p l a n a t o r y ; f o r batch usage the i n p u t c a r d s must conform to the f o l l o w i n g grammar. A sequence of c h a r a c t e r s or phrase enclosed by qu o t a t i o n marks must appear on a separate card. raobileobjects ::= m o b j l i s t terminator m o b j l i s t ::= mobjspec | m o b j l i s t mobjspec mobjspec ::= t l h c r e c t l i s t terminator t l h c ::= "x,y" r e c t l i s t ::= r e c t | r e c t l i s t r e c t r e c t ::= «'xoff,yoff,xdim,ydim" xdim,ydim ::- p o s i t i v e i n t e g e r Robot Simulation Studies 39 x , y , x o f f , y o f f ::- i n t e g e r t e r m i n a t o r ::= " F I N " | "STOP" In t h e a b o v e , " x , y " g i v e s t h e p o s i t i o n o f t h e t o p l e f t - h a n d c o r n e r o f a new m o b i l e o b j e c t ; a nd " x o f f , y o f f , x d i m , y d i m " s p e c i f i e s t h a t a r e c t a n g l e w i t h d i m e n s i o n s x d i m - b y - y d i m i s t o be p a r t o f t h e m o b i l e o b j e c t c u r r e n t l y b e i n g d e f i n e d , a t an o f f s e t o f ( x o f f , y o f f ) f r o m i t ' s t o p l e f t - h a n d c o r n e r . F o r e x a m p l e t o s p e c i f y a T - s h a p e d o b j e c t i n t h e n o r t h w e s t g u a d r a n t and a U-shaped o b j e c t i n t h e s o u t h e a s t q u a d r a n t o f a 28-by-28 e n v i r o n m e n t , t h e f o l l o w i n g c a r d s m i g h t f o l l o w t h e MOBILE command. 5,5 0,0,2,6 2 f 2 f 3 f 2 F I N 16,18 0,0,4,2 3^2^2/2 0,4,4,2 F I N F I N STOP T e r m i n a t e s e x e c u t i o n o f ROSS . SIGNCFF T e r m i n a t e s e x e c u t i o n and s i g n s t h e u s e r o f f . R o b o t s i m u l a t i o n S t u d i e s 40 MTS I n t e r r u p t s e x e c u t i o n and r e t u r n s c o n t r o l t o MTS. ROSS c a n be r e s t a r t e d w i t h a $RESTABT, T h i s i s u s e f u l t o g e t a p r i n t e d c o p y on t h e l i n e p r i n t e r o f t h e r e c e n t t e r m i n a l d i s p l a y . SET STEPS= s t e p b d SET TURNS= t u r n b d These commands s e t t h e maximum number o f s t e p s and t u r n s t h a t R o b b i e may t a k e i n t h e c o u r s e c f one e p i s o d e . They c a n be r e g a r d e d a s t h e f u e l a l l o w a n c e . A t a t e r m i n a l , i f one o f t h e s e b o u n d s i s e x c e e d e d ROSS w i l l prompt t h e u s e r t o e n t e r new v a l u e s f o r t h e m . RESET C a u s e s a l l k n o w l e d g e a b o u t t h e e n v i r o n m e n t t h a t R o b b i e may have g a i n e d t h r o u g h p r e v i o u s e x p l o r a t i o n s t o be wi p e d o u t . A c t i o n commands T h e s e come i n t h r e e l e v e l s . L e v e l 1 C o n s i s t s o f t h e most b a s i c commands: P I C K U P , DROP, STEP, TURN, FACE, LINEAR. L e v e l 2 C o n s i s t s o f t h e commands F I N D , FOLLOW. L e v e l .3 Of most i n t e r e s t , t h i s c o n s i s t s o f t h e Robot S i m u l a t i o n S t u d i e s commands HOME, WALK, EXPLORE. L e v e l I PICKUP C a u s e s R o b b i e t o p i c k u p t h e m o v a b l e o b j e c t t h a t he i s f a c i n g , i f a n y ; o t h e r w i s e t h e command f a i l s . The 3-by-3 a r r a y MSENSE w h i c h a p p e a r s on t h e s n a p s h o t s a l l o w s him t o " s e e " u n d e r w h a t e v e r m o v a b l e o b j e c t he i s h o l d i n g and t h u s e n a b l e s him t o a v o i d f a l l i n g i n t o h o l e s . When no o b j e c t i s b e i n g h e l d MSENSE i s u n d e f i n e d - d e n o t e d by t h e s i g n s i n t h e s n a p s h o t s . DROP C a u s e s R o b b i e t o d r o p w h a t e v e r o b j e c t he was h o l d i n g , i f a n y . MSENSE becomes u n d e f i n e d . STEP C a u s e s R o b b i e t o t a k e one s t e p i n t h e d i r e c t i o n he i s f a c i n g , p r o v i d e d t h e s q u a r e i n f r o n t o f him i s b l a n k . I f he i s h o l d i n g a movable o b j e c t , MSENSE i s u s e d t o t e l l w h e t h e r t h e s t e p c a n be t a k e n ; a l s o , t h e s t e p m i g h t f a i l b e c a u s e o f a c o l l i s i o n between t h e o b j e c t b e i n g h e l d and o t h e r o b j e c t s i n t h e e n v i r o n m e n t . STEP :n I s e q u i v a l e n t t o n STEP commands. TURN : r o t a t i o n R o b o t S i m u l a t i o n S t u d i e s 42 C a u s e s R o b b i e t o t u r n l e f t , r i g h t , o r t h r o u g h 180 d e g r e e s a c c o r d i n g a s < r o t a t i c n > i s L E F T , RIGHT, o r ABOUT. I f R o b b i e i s c u r r e n t l y h o l d i n g a m o v a b l e o b j e c t t h i s command may f a i l t h r o u g h a c o l l i s i o n o f t h e o b j e c t b e i n g h e l d w i t h t h e e n v i r o n m e n t . FACE : d i r e c t i o n C a u s e s R o b b i e t o f a c e n o r t h , s o u t h , e a s t , o r west a c c o r d i n g as < d i r e c t i o n > i s NORTH, SOUTH, EAST, o r WEST. J u s t a s f o r t h e TURN command, t h i s c a n f a i l . E x a m p l e : FACE :WEST LINEAR :x,y C a u s e s R o b b i e t o move i n an a p p r o x i m a t e l y s t r a i g h t l i n e f r o m h i s p r e s e n t p o s i t i o n t o (x,y) by e x e c u t i n g a s e q u e n c e o f s t e p s and t u r n s . As e a c h s q u a r e i s r e a c h e d , he f i g u r e s o u t what h i s n e x t move s h o u l d b e . Of c o u r s e , t h i s command may f a i l t h r o u g h f a i l u r e o f any one o f t h e c o n s t i t u e n t s t e p and t u r n a c t i o n s . E x a m p l e : LINEAR :3,21 L e v e l 2 FIND : » c h ' C a u s e s R o b b i e t o s e a r c h f o r a s q u a r e l a b e l l e d w i t h t h e c h a r a c t e r 'ch* i n a random manner. Robot S i m u l a t i o n S t u d i e s E x a mple : FIND :'H' C a u s e s R o b b i e t o s e a r c h f o r a h o l e . FOLLOW : ' c h ' hand [ S T A C K ] U s u a l l y i s s u e d i m m e d i a t e l y a f t e r a s u c c e s s f u l FIND : ' c h ' command, when R o b b i e i s f a c i n g a ' c h ' s q u a r e . C a u s e s R o b b i e t o n o t e h i s s t a r t i n g p o s i t i o n and t h e n , i f he i s c u r r e n t l y f a c i n g a s q u a r e l a b e l l e d ' c h ' , t o f o l l o w a c o n t i n u o u s s e q u e n c e o f ' c h ' s q u a r e s u n t i l t h e s t a r t i n g p o i n t i s r e g a i n e d , g e n e r a t i n g a r i n g d e s c r i p t i o n as he p r o c e e d s . He k e e p s t o t h e r i g h t o r l e f t a c c o r d i n g a s <hand> i s RIGHT o r LEFT r e s p e c t i v e l y . The command f a i l s i f e i t h e r he i s n o t i n i t i a l l y f a c i n g a " c h ' s q u a r e , o r i f t h e r e i s no c o n t i n u o u s s e q u e n c e o f ' c h ' s q u a r e s l e a d i n g b a c k t o t h e s t a r t i n g p o i n t . T h i s would be t h e c a s e i f , f o r i n s t a n c e , a movable o b j e c t had e d g e - c o n t a c t w i t h a h o l e , R o b b i e was f a c i n g an 'M' s q u a r e o f t h e movable o b j e c t , and t h e command FOLLOW :'H» LEFT were i s s u e d . I f t h e ' c h ' s q u a r e s f o r m an e n c l o s u r e t h e command FOLLOW:'ch' RIGHT s h o u l d be u s e d , b u t i f t h e y f o r m an i s o l a t e d o b j e c t t h e n FOLLOW :'ch» LEFT s h o u l d be u s e d . T h i s i s b e c a u s e t h e r i n g - d e s c r i p t i o n o f a s h a p e i s , by c o n v e n t i o n g i v e n i n a n t i - c l o c k w i s e o r d e r . H o w e v e r , no harm i s done i f t h e wrong command i s i s s u e d : t h e c l o c k w i s e r i n g o f e d g e s w i l l a u t o m a t i c a l l y be r e v e r s e d . I f t h e o p t i o n STACK a p p e a r s t h e n i f i t t u r n s o u t t h a t t h e ' c h ' s q u a r e s f o r m an i s o l a t e d o b j e c t , t h e o b j e c t ' s r i n g Robot S i m u l a t i o n S t u d i e s 44 d e s c r i p t i o n i s s t a c k e d a c c o r d i n g t o t h e o b j e c t ' s t y p e . T h a t i s , i t i s p l a c e d on t h e f i x e d o b j e c t , m o v a b l e o b j e c t , o r h o l e s t a c k a c c o r d i n g a s t h e c h a r a c t e r ' c h ' i s B, M, o r H; o t h e r w i s e i t i s p l a c e d on t h e o d d i t y s t a c k . E x a m p l e : FOLLOW :'H' LEFT STACK L e v e l 3 HOME [ NEW ] T h i s i s u s u a l l y t h e f i r s t a c t i o n command i s s u e d . I t s o b s e r v a b l e a c t i o n i s e q u i v a l e n t t o t h e p a i r o f commands FIND: 'B1 , FOLLOW: 'B' RIGHT, w i t h t h e p r o v i s o t h a t i f t h e o b j e c t s o f o l l o w e d i s an i s o l a t e d o b j e c t i n s t e a d o f an e n c l o s u r e , i t s r i n g d e s c r i p t i o n i s s t a c k e d and t h e same p a i r o f commands r e - i s s u e d . T h i s i s r e p e a t e d u n t i l e i t h e r f a i l u r e o f some s o r t o c c u r s o r t h e b o u n d a r y i s s u c c e s s f u l l y f o u n d and f o l l o w e d . Then R o b b i e 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 and s e t s t h e c u r r e n t m r t p o i n t e r t o t h e f i r s t MRT f o u n d w h i c h c o n t a i n s R o b b i e . A l s o , t h e i n t e r s e c t i o n r e c t a n g l e s (IRTs ) b e t w e e n o v e r l a p p i n g MRTs a r e f o u n d . The MRTs o f t h e e n v i r o n m e n t w i l l be d i s p l a y e d u n l e s s s u p p r e s s e d t h r o u g h a SET PRINT command. I f two HOME commands a r e i s s u e d , t h e s e c o n d one w i l l R o b o t S i m u l a t i o n S t u d i e s 45 be i n t e r p r e t e d a s an e r r o r and w i l l be i g n o r e d u n l e s s t h e o p t i o n NEW a p p e a r s . T h i s i s u s e f u l i f d u r i n g t h e c o u r s e o f one e p i s o d e , new FIXED o r MOBILE commands a r e i s s u e d t o ch a n g e t h e e n v i r o n m e n t , a nd we want R o b b i e t o be a b l e t o make c o r r e c t p l a n s f o r moving a b o u t i n t h e new e n v i r o n m e n t . WALK :MRT i C a u s e s R o b b i e t o c r e a t e and e x e c u t e a p l a n t o r e a c h MRT i . He w i l l s u c c e s s f u l l y s i d e s t e p an o b s t a c l e c o n s i s t i n g o f a s i n g l e i s o l a t e d n o n - b l a n k s q u a r e , whereas h i s c h a n c e s o f a v o i d i n g a n y t h i n g l a r g e r a r e n e t z e r o , b u t s m a l l and r a t h e r u n p r e d i c t a b l e . The p l a n c r e a t e d w i l l be p r i n t e d on t h e t e r m i n a l d i s p l a y s c r e e n u n l e s s s u p p r e s s e d by a SET PRINT command. A t r a c e o f t h e e x e c u t i o n o f t h e p l a n a p p e a r s i n t h e d e b u g g i n g f i l e . WALK : x,y I f ( x,y) l i e s i n MRT i , t h i s i s e q u i v a l e n t t o t h e command WALK :MRT i f o l l o w e d by t h e command LINEAR :x,y i f t h e f i r s t command i s s u c c e s s f u l . EXPLORE C a u s e s R o b b i e t o e x p l o r e h i s c u r r e n t MRT f o r a n y o b j e c t s t h a t m i g h t be p r e s e n t . Whenever a s g u a r e i s f o u n d t h a t i s n o t p a r t o f t h e b o u n d a r y b u t i s l a b e l l e d w i t h a n o n - b l a n k c h a r a c t e r 'ch* , what e s s e n t i a l l l y h appens i s R o b o t S i m u l a t i o n S t u d i e s 46 t h a t t h e a c t i o n F O L L O W c h ' LEFT STACK i s t a k e n . EXPLORE : MRT i T h i s i s e q u i v a l e n t t o t h e p a i r o f commands WALK:MRT i , EXPLORE where f a i l u r e o f t h e WALK coir ma nd c a u s e s t h e o r i g i n a l EXPLORE command t o f a i l . EXPLORE : x , y T h i s i s e q u i v a l e n t t o t h e command WALK:x,y f o l l o w e d by two a l t e r n a t i v e a c t i o n s . I f t h e WALK command s u c c e e d s t h e n R o b b i e e x p l o r e s t h e MRT c o n t a i n i n g ( x , y ) , o r i n o t h e r words t h e u p d a t e d c u r r e n t MRT. I f i t f a i l s b e c a u s e o f an o b s t a c l e c o n s i s t i n g o f ' c h ' s q u a r e s e n c o u n t e r e d on t h e way t o ( x , y ) , t h e a c t i o n F O L L O W ^ c h ' LEFT STACK i s e x e c u t e d and c o n t r o l r e t u r n e d t o t h e u s e r . EXPLORE :ALL E q u i v a l e n t t o i s s u i n g a s e g u e n c e o f EXPLORE:MRT i commands, one f o r e a c h o f t h e MRTs i n t h e e n v i r o n m e n t . EXPLORE :ROOMS { o r :SPACES } T h i s i s s i m i l a r t o EXPLORE:ALL, e x c e p t t h a t o n l y t h o s e MRTs w i t h d i m e n s i o n s a t l e a s t 4-by-4 and o c c u p y i n g a t o p p o s i t i o n i n t h e l a t t i c e o f MRTs o f t h e e n v i r o n m e n t a r e e x p l o r e d . R o b o t S i m u l a t i o n S t u d i e s 47 The c o m p a r a t i v e command I S ? o b s p e c c o m p a r a t o r o b s p e c c o m p a r a t o r ::= CONGRENT TO ] C_CONGRUENT TO | SIMILAR TO | CONTAINABLE IN o b s p e c ::= o b t y p e : obno o b t y p e ::= OBJECT | MOBILE | BOLE | OtDITY obno ::= i n t e g e r The I S ? command c a u s e s t h e s h a p e s of two o b j e c t s i n t h e e n v i r o n m e n t t o be co m p a r e d f o r c o n g r u e n c e , c o r n e r -c o n g r u e n c e , s i m i l a r i t y , o r c o n t a i n m e n t . The r e s p o n s e i s a s i m p l e " y e s " o r " n o " . E x a m p l e s : S u p p o s e t h a t R o b b i e knows o f two f i x e d o b j e c t s c a l l e d OBJECT 2 S OBJECT 3 , two mo v a b l e o b j e c t s c a l l e d OBJECT 4 S OBJECT 5, two h o l e s c a l l e d OBJECT 6 & OBJECT 7 , and one o b j e c t whose s q u a r e s a r e l a b e l l e d w i t h Qs and c a l l e d OBJECT 8 . Then t h e f o l l o w i n g a r e v a l i d c o m p a r a t i v e commands. I S ? 0BJECT:2 CONGRUENT TO MOBILE :4 I S ? M0BILE:4 SIMILAR TO H0LE:6 I S ? MOBILE:4 C_CONGRUENT TO ODDITY :8 I S ? MOBILE : 5 CONTAINABLE IN HOLE : 7 However, t h e n e x t conrcand would f a i l . Robot S i m u l a t i o n S t u d i e s 48 I S ? MOBILE : 5 CONGRUENT TO HOLE : 8 I n t h e c a s e o f I S ? .... CONTAINABLE I N . . . commands, d e t a i l s o f t h e l a t t i c e o f MRTs c o n s t r u c t e d f o r t h e two o b j e c t s b e i n g c o m p a r e d a r e p r o d u c e d , u n l e s s s u p p r e s s e d by a SET command. JLispifLI commands DISPLAY C a u s e s a s n a p s h o t o f t h e c u r r e n t c o n f i g u r a t i o n t o be d i s p l a y e d . SET ACTDSW SET INTDSW SET DEBUGSW SET PRINTSW T h e r e a r e f o u r b a n k s o f s w i t c h e s w i t h i n ROSS t h a t c o n t r o l ROSS ' S o u t p u t . The a c t i o n d i s p l a y s w i t c h e s (ACTDSW) c o n t r o l , t h e p r o d u c t i o n o f s n a p s h o t s a f t e r c o m p l e t i o n o f an a c t i o n command. The d e f a u l t s y s t e m a c t i o n i s t o p r o d u c e a s n a p s h o t a f t e r e v e r y a c t i o n command. The i n t e r n a l d i s p l a y s w i t c h e s ( INTDSW ) c o n t r o l t h e p r o d u c t i o n o f s n a p s h o t s a f t e r c o m p l e t i o n o f an a c t i o n t h a t was c a l l e d i n t e r n a l l y . F o r i n s t a n c e , t h e INTDSW c o u l d be s e t so t h a t e v e r y t i m e a LINEAR a c t i o n o c c u r r e d a s n a p s h o t w o u l d a p p e a r . T h i s c o u l d R o b o t S i m u l a t i o n S t u d i e s 49 be u s e f u l f o r w a t c h i n g R o b b i e ' s p r o g r e s s w h i l e e x e c u t i n g a WALK command, f o r e x a m p l e . The d e f a u l t s y s t e m a c t i o n i s t o p r o d u c e no s n a p s h o t a f t e r an a c t i o n i s c a l l e d i n t e r n a l l y . The debug, s w i t c h e s ( DEBUGSW ) c o n t r o l t h e p r i n t i n g o f d e b u g g i n g i n f o r m a t i o n on t h e d e b u g g i n g f i l e . The £ r i n t s w i t c h e s c o n t r o l t h e p r i n t i n g o f t h e l i s t o f MRTs o f t h e e n v i r o n m e n t o r c f a n o b j e c t , t h e i n t e r s e c t i o n r e c t a n g l e s b e t w e e n o v e r l a p p i n g MRTs, t he p l a n s p r o d u c e d f o r a WALK command, t h e l a t t i c e o f MRTs p r o d u c e d i n t h e c o u r s e o f an I S ? . . . CONTAINABLE . . . . command, and s o o n . The d e f a u l t i s f o r a l l t h e p r i n t s w i t c h e s t o be o n . They may be ch a n g e d by a SET PRINTSW command. A s e t command must be f o l l o w e d by a s e q u e n c e o f o n / o f f s w i t c h s e t t i n g s , and must be t e r m i n a t e d by a "STOP" c a r d . E x a m p l e s : SET ACTDSW STEPS-OFF LIN E A R=OF F WALK=ON STOP S u b s e q u e n t l y , no s n a p s h o t w i l l a p p e a r a f t e r a STEP or LINEAR command, b u t w i l l a p p e a r a f t e r a WALK command. SET INTDSW L I N EAR=ON STOP Robot S i m u l a t i o n S t u d i e s 50 S u b s e q u e n t l y , e a c h t i m e t h e a c t i o n LINEAR i s i n v o k e d i n t e r n a l l y a s n a p s h o t w i l l a p p e a r on c o m p l e t i o n o f t h e a c t i o n . SET DEBUG SW FOLLCW=OFF EXPLOR E=0 EF STOP S u p p r e s s e s t h e p r i n t i n g c f d e b u g g i n g i n f o r m a t i o n f r o m t h e FOLLOW and EXPLORE p r o c e d u r e s . SET PROTSW PLANS=0FF LATTICE=0N STOP S u p p r e s s e s t h e p r i n t i n g o f any p l a n s t h a t m i g h t be made i n t h e c o u r s e o f a WALK o r EXPLORE command, and e n s u r e s t h e p r i n t o u t o f any l a t t i c e c o n s t r u c t e d i n t h e c o u r s e o f an I S ? command. PRINT STACK C a u s e s t h e names o f t h e o b j e c t s on e a c h o f R o b b i e ' s f o u r s t a c k s t o be p r i n t e d . 3 .1.3 Summary o f ROSS commands G l o b a l commands R o b o t S i m u l a t i o n S t u d i e s 51 FIXED Must be f o l l o w e d by a s e q u e n c e o f f i x e d f o r m a t s u b -commands, MOBILE M u s t be f o l l o w e by a s e q u e n c e o f m o b i l e o b j e c t s p e c i f i c a t i o n s . MTS RESET SET STEPS= s t e p b d SET TURNS= t u r n b d SIGNOFF STOP A c t i o n commands x l e v e l J PICKUP DROP STEP [ : n ] TURN : r o t a t i o n FACE : d i r e c t i o n LINEAR :x,y A c t i o n commands, l e v e l 2 FIND :'c h ' FOLLOW :'ch« hand [ S T A C K ] A c t i o n commands^, l e v e l 3 HOME [NEW] R o b o t S i m u l a t i o n S t u d i e s 52 WALK rwmode wmode MRT i | x,y EXPLORE :emode emode MRT i | x,y | ALL | ROOMS | SPACES C o m p a r a t i v e coinmand I S ? o b s p e c c o m p a r a t o r o b s p e c ^ i s £ i 9 L l commands CIS FLAY SET ACTDSW SET INTDSW SET DEBUGSW SET PRINTSW S e t commands must be f o l l o w e d by a s e q u e n c e o f . s w i t c h s e t t i n g s t e r m i n a t e d w i t h "STOP". PRINT STACKS 3.1.4 Sample o u t p u t The f o l l o w i n g pages c o n t a i n c o n d e n s e d v e r s i o n s o f two ROSS e p i s o d e s . The b i g g e s t o m i s s i o n s a r e - m a r k e d w i t h " . . . " . Comments added l a t e r a r e e n c l o s e d by " $ " s i g n s . U s e r commands a r e p r e f i x e d w i t h t h e s i g n ">". Robot S i m u l a t i o n S t u d i e s 53 I n t h e f i r s t e p i s o d e R o b b i e moves o b j e c t s a r o u n d u n d e r t h e d i r e c t c o n t r o l o f t h e u s e r , and t h e n , a f t e r a ROME command, c a r r i e s o u t a WALK command f o l l o w e d by a EXPLORE command. I n t h e s e c o n d t h e e n v i r o n m e n t i s s l i g h t l y d i f f e r e n t . T h r o u g h e x p l o r e commands R o b b i e l e a r n s o f f o u r m o v a b l e o b j e c t s and one h o l e , and t h e n a n s w e r s s i x I S ? q u e s t i o n s . I n t h e l a s t two I S ? q u e s t i o n s , l a t t i c e s o f MRTs a r e c o n s t r u c t e d and p r i n t e d o u t . Note t h a t "MOBJ 1","M0BJ 2", . . . a r e names u s e d by t h e w o r l d s i m u l a t i o n p r o c e d u r e s t o r e f e r t o the m o v a b l e o b j e c t s i n t h e e n v i r o n m e n t , whereas "OBJECT 1", "OBJECT 2 " , . . . a r e names g e n e r a t e d by R o b b i e i n t h e c o u r s e o f h i s e x p l o r a t i o n s f o r t h e f i x e d o b j e c t s , m ovable o b j e c t s , h o l e s o r o d d i t i e s e n c o u n t e r e d . *WELCOME TO ROSS: RECORD OF EPISODE AT 04:55 P.M. J A N . 2 0 , 1972 >SET STEPS=1000 >LIN EAR :19,22 * LINEAR 19 22 ENTERED >FACE :SOUTH >PICKUP $ mobj 3 $ SNAP # 4 >TURN:ABOUT >STEP :6 SNAP* 6 >DROP >FACE:WEST $ t h e n e x t few commands manoeuvre r o b b i e ROBOT SIMULATION STUDIES PICKUP OK SN AP# 4 1 2 3 4 5 6 7 8 9 1011121314 1516171819202122232425262728 Y 1 B 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 2 B B 3 B B B 4 B B B 5 B B 6 B B B B B E E B B B B B B B B B B B B B B B B B 7 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 E 9 B B B M M M B 10 B M M M M M B B M M M W E 1 1 B M M M M M B B M M M M H H B 12 B M M B B B H E 13 B M B B H H H H a B 14 B M M M E B H H H H H E 15 B $inobj 4$ B B B 16 B B B B B B B B B B B B E 17 B B B B B B E B B B B B • B 18 B B B B B B B B B B B B <* B 19 B B B a B 20 B B B M M M M M M M B 21 B B B M M M M M M M B 22 B B B M M M M M M M E 2 3 B B B M B 24 B B B M E 25 B B B M B 26 B B B $mobj 3$ E 27 B B B B 28 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 X M M M| 3 I M SEN SE SENSE POSITION: (19,22) ORIENTATION: SOUTH HOLDING: MOBJ 3 CURRENT MRT: UNDEFINED #FIXED OBJECTS KNOWN: 0 #MO VA BLE OBJECTS KNOWN: 0 WHOLES KNOWN: 0 ROBOT SIMULATION STUDIES 5 TH STEP BAD SNAP# 6 1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728 Y 1 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 2 B B 3 B B B 4 B B E 5 B B 6 B B B B B E E B B B B B B B B E B B E B E B B E 7 B B B B B B E B B B B B B B B B B B B B B B B B 8 B B B E 9 B B B M M M M B 10 B M M M M M B B M M M M M E 1 1 B M M M M M B B M M M M M H H B 12 B M M B B M M M M M M M H B 13 B M B B M M M M M M M H B 14 B M M M B B M M M M M" M M H B 15 B B B 5) B 16 B B B B B B B B B B B E « E 17 B B B B B E B B B B B B * B 18 B B B B B B B B B B E B • E 19 B B B * B 20 B B B E 21 B B B B 22 B B B B 23 B B B B 24 B B B B 25 B B B B 26 B E B E 27 B B B B 28 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 E X | H H | | M M M | I a I I a ] I I I I MSENSE SENSE # F I X E D #MO V A B L E POSITION: ORIENTATION: HOLDING: CURRENT MRT: OBJECTS KNOWN: OBJECTS KNOWN: #HOLES KNOWN: ( 15, 22) NORTH MOBJ 3 UNDEFINED 0 0 0 R o b o t S i m u l a t i o n S t u d i e s 54 r e a d y t o p i c k up mobj 3 a g a i n . $ >STEP :6 >PICKUP >TURN :LEFT SNAP* 13 >DRCP >LINFA R : 19,15 $ mobj 3 $ $ t h e n e x t h a l f - d o z e n commands manoeuvre r o b b i e r e a d y t o p i c k up mobj 4. $ >PICKUP >TU RN :L EFT SNAP# 23 >DROP $ mobj 4 5 $ t h e n e x t few commands move r o b b i e a r o u n d t o a d i f f e r e n t p a r t o f mobj 4 t o p i c k i t up a g a i n . $ >PICKUP SNAP# 27 SNAP! 30 $ u s e r i s s u e d commands t o move mobj 4 t h r o d o o r way $ >H OM E * FIND('B') ENTERED * FOLLOW{'B', 1 , ) ENTERED RING5:0BJECT 1 $ t h e r i n g r e p r e s e n t a t i o n o f t h e e n v i r o n m e n t f o l l o w s $ #EDGES= 20 R O B O T S I M U L A T I O N S T U D I E S T O R N L E F T B A D SNAP* 13 1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728 1 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 2 B E 3 B B B 4 B B E 5 B B 6 B B B B E E E B B B B B B B B E B B B B B B B E 7 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 9 B B B M M M M B 10 B M W M M M B B M M M M M E 1 1 B M M M M M B B M M M M M H H B 12 B M M B B M M M M M M M H E 13 B M B B . a M M M M M M M H B 14 B M M M B B M M M M M M M H B 15 B B B B 16 B B B B B B B B B B B B E 17 B B B B B E B B B B B B B 18 B B B B B B B B B B B B E 19 B B B B 20 B B B B 21 B B B B 22 B E B B 23 B B B B 24 B B B B 25 B B B B 26 B E E B 27 B B B B 28 B B B B B B B B B B B E B B B B B B B B B B B B E B B B |M M M| I a I M S E N S E S E N S E P O S I T I O N : (13,18) O R I E N T A T I O N : E A S T H O L D I N G : M O B J 3 C U R R E N T MRT: U N D E F I N E D # 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 # H O L E S KNOWN: 0 ROBOT S I M U L A T I O N S T U D I E S TURN L E F T OK S N A P * 23 1 2 3 4 5 6 7 8 9 1 0 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 Y 1 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 2 B E 3 B B B 4 B B • • E 5 B • * B 6 B B B B B E B B B B • B B B B B B B B E B B B B B 7 B B B B B B B B B B • B B B B B B B B B B B B B B 8 B • B B E 9 B • B B M M M B 10 B M M M M M • B B * M M M M B 1 1 B M M M M M B B M M M M H B B 12 B M M a M M B B H H B 13 B M B B H H H H H B 14 B M E B H H H H H E 15 B B B m B 16 B B B B B B B B B B B B M E 17 B B B B B E E B B B B B m m M B 18 B B B B B B B B B B B B M E 19 B B B • • M M M M M M M B 20 B B B • M M M M M M M B 21 B B B M M M M M M M B 22 B B B E 23 B B B B 24 B B B B 25 B B B B 26 B B B E 27 B B B B 28 B B B B B B B B B B B E B B B B B B B B B B B B E B B B X M 3 MSENSE S E N S E P O S I T I O N : ( 1 2 , 1 0 ) O R I E N 1 A T I G N : EAST HOLDING: MOBJ 4 CURRENT MRT: UND E F I N E D # F I X E D O B J E C T S KNOWN: 0 #MOVABLE O B J E C T S KNOWN: 0 t H O L E S KNOWN: 0 ROBOT S I M U L A T I O N S T U D I E S P I C K U P OK SNAP# 27 1 2 3 4 5 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 1 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 2 B B 3 B B » B . •4 B B • B 5 B * • B 6 B B B B B E B B B B . . B B B B B B B B B B B B B E 7 B B B B B B B B B B . B B B B B B B B B B B B B B 8 B • • B B B 9 B • B B M M M B 10 B M M M M M B B M .M M  E 1 1 B M M M M M . s B B M M M  H H B 12 B M M . M M B B H H B 13 B M B B H H H H H B 14 B M B B H H E H H B 15 B B B B 16 B B B B B B B B B B B B M B 17 B B B B B E E B B B B B m M B 18 B B B B B B B B B B B B M E 19 B B B m , . . M M M M M M M B 20 B B B . . M M M M M M M E 21 B B B M M M M M M M B 22 B B B E 23 B B B B 24 B B B B 25 B B B B 26 B B B E 27 B B B B 28 B B 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 X |M M I 3 MSENSE SENSE P O S I T I O N : ( 1 1 , 1 1 ) O R I E N T A T I O N : SOUTH HOLDING: MOBJ 4 CURRENT MRT: U N D E F I N E D # F I X E D O B J E C T S KNOWS: 0 •MOVABLE O B J E C T S KNOWN: 0 ftHOLES KNOWN: 0 ROBOT SIMULATION STUDIES 3 STEP OK SNAP* 3 0 1 2 3 4 5 6 7 8 9 1011121314 1516171819202122232425262728 Y 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 B B 3 B B B 4 B B * • B 5 B • • B 6 B B B B B E E B B B . B B B B B E B B E B E B B B 7 B B B B B B E B B B * B B B B B B B B B B B B B B 8 B B B E 9 B B B M M M B 10 B M ' M M M M B B M M M M B 1 1 B M M M M M B B M M M M H H B 12 B M M B B R H B 13 B B B H H H R H B 14 B E B H B H B H B 15 B B B m B 16 B B B B B B B B B B B B M E 17 B B B B B E E B B B m B B' M B 18 B B B B B B B B B B B B » M E 19 B B B • M M M M M M M B 20 B E B • M M M M M M M B 21 B B B M M M M M M M B 22 B M S -a • B B E 23 B M M M B B B 24 B B B B 25 B B B B 26 B B B E 27 B B B B 28 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 X I M M I a MSENSE SENSE POSITION: (22, 8) ORIESTATIGN: WEST HOLDING: MOBJ 4 CURRENT MRT: UNDEFINED #FIXED OBJECTS KNOWN: 0 #MO VABLE OBJECTS KNOWN: 0 #HOL ES KNOWN: 0 Robot S i m u l a t i o n S t u d i e s 55 TLHC 0 HAS COORDS 2 2 HEAD 0 POINTS TO EDGE 11 RING OF EDGES FOLLOWS EDGE 11 STEPS= 4 T0RN= -1 EDGE 12 STEPS= 9 TUBN= 1 •» • » * THE RING REP. OF "HOME" IS CALLED OBJECT 1 MRTS OF OBJECT 1 FOLLOW.. MRT 6 LEFT , Y=15 ; RIGHT , Y = 17; TOP,X= 2; M ST 5 L EFT,Y= 1 5 ; BOTTOM, X=28; RIGHT,Y=28; TOP,X= 8; • • • MRT 1 LEFT,Y= 2; BOTTOM,X= 6; RIGHT,Y=28; TOP,X= 2; END OF MRTS. OUTOLAP:OVERLAPS BETWEEN MRTS OF OBJECT 1 MRTL1ST FOLLOWS MRT 6 OVERLAPS MRT 1 OVERLAPS MRT 5 WITH INTERSECTION IRT 2 WITH INTERSECTION IRT 1 MRT 5 OVERLAPS MRT 6 WITH INTERSECTION IRT 1 Robot S i m u l a t i o n S t u d i e s 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; RIGHT, Y= 11 ; TOP,X= 0; • • • IRT 1 LEFT , Y =13 ; BOTTOM,X=26; RIGHT,Y=15; TOP,X= 6; OUTOLAP:END SNAP# 32 >WALK TO :MRT 5 WALKA:SEARCHING FOR MRT 5 DETAILS OF PLAN: STARTS IN MRT 1 MOVE THROUGH MRT 1 MOVE THROUGH MRT 6 ENDS IN MRT 5 EXPLAN:MOVING THRO MRT 1 MOVE: MRT 1 IRT 2 • LINEAR 3 15 ENTERED EXPLAN--MOVING THRO MRT 6 INTO IRT 2 INTO IRT 1 INTO IRT 2 INTO I ET 1 >EXPLORE :MRT 3 EXPLORE{-1, 3) :S EARCHIN G FOR MRT 3 DETAILS OF PLAN: STARTS IN MRT 5 ROBOT SIMULATION STUDIES HOME:SETTLED IN OK SNAP# 32 1 2 3 4 5 6 7 8 9 1 0 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 Y 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 B . . . . . . . . . . . . . . . . . . . . . . . . . . E 3 B . B . B 4 B . B . E 5 B . . . . . . . . . . . . 3 . . . . . . . . B 6 B B B B B E E B B B . . B B . . . B B B B B B B B B B B E 7 B B B B B E E B B B . . B B . . B B B B B B B B B B B B 8 B B B B 9 B . . B B . MMM . B 10 B . M M M M M . B B . M M M M . B 1 1 B . MMMMM . B B . MMMM H H . B 1 2 B . MM . B B . H H . B 13 B . , . B B . H H H H H . B 14 B . . B B . H H H H H . B 1 5 B . . . B B . . B 1 6 B B B B B B B B B B . . B B . M . B 1 7 B B B B B B E B B B . . B B . M . B 1 8 B B B B B B B B B B . . B B . M .. B 1 9 B . . . . B B . MMMMMMM . B 20 B . . B B . MMMMMMM . E 21 B . . B B . MMMMMMM . B 22 B . M . . . . . . B B . . E 23 B . MMM . B B . . B 24 B . . B B . . E 25 B . . B B . . B 26 B . . B B . . E 27 B B B . B 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 E X % % %\ | B| % 3 % | I n) B | % % %\ | | MSENSE SENSE POSITION: ( 5,13) ORIENTATION: EAST HOLDING: NOTHING CURRENT MRT: MRT 1 #FIXED OBJECTS KNOWN: 0 •MOVABLE OBJECTS KNOWN: 0 #HOLES KNOWN: 0 Robot Si m u l a t i o n S t u d i e s MOVE THROUGH MRT 5 INT0 IRT 1 MOVE THROUGH MRT 6 INTO IRT 2 MOVE THROUGH MRT 1 INTO IRT 5 MOVE THROUGH MRT 2 INTO IRT 4 ENDS IN MRT 3 EXPLAN:MOVING THRO MRT 5 INTO 1ST 1 MOVE: MRT 5 IRT 1 * LINEAR 17 15 ENTERED • -» * * • •* * LINEAR 12 7 ENTERED * FOLLOW('M•,- 1 , ) ENTERED RING5:OBJECT 2 #EDGES = 6 TLHC 0 HAS COORDS 10 4 -» * HEAD 0 POINTS TO EDGE 24 * » * • • • RING OF EDGES FOLLOWS EDGE 24 STEPS= 2 TURN= -1 * XPLMRT : FOUND" M" OBJECT * EXPLORE(-1, 3):XPLMRT FAILED SNAP* 34 ROBOT SIMULATION STUDIES EXPLORE MRT 3 BAD SNAP* 34 1 2 3 4 5 6 7 8 9 10 11121314 1516171819202122232425262728 Y 1 B 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 2 3 B B B a B B 4 B B • • B 5 B B 6 B B B B B B B B B B B B B B B B B B B B B B B B 7 8 B 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 9 B B B M M M B 10 B • M M M M M • B B * M M M M B 11 B • M M M M M m E B M M M M B E •B 12 B • • . m M M a * m B B m H H B 13 B m * , B B H H H H H B 14 B B B H H H H H B 15 B B B „ B 16 B B B B B B B B B B B B M B 17 B B B B B B B B B B E B • • M B 18 B B B B B B B B B B B B • M B 19 B B B M M M M M M M E 20 B B B M M M M M M M B 21 B B B M M M M M M M B 22 B M B B B 23 B M M M E B E 24 B B B B 25 B B B B 26 B B B B 27 B B B B 28 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 X \% % %\ |M | % 2 %| |MS \% % %] | MSENSE SENSE POSITION: (12, 9) ORIENTATION: NORTH HOLDING: NOTHING CURRENT MRT: MRT 3 #FIXED OBJECTS KNOWN: 0 #MO V ABLE OBJECTS KNOWN: 1 #H01ES KNOWN: 0 Robot S i m u l a t i o n S t u d i e s 58 >STOF * ACTS FINISHED T=2.19 DR=0 $ c p u t i m e u s e d by e p i s o d e was 2.19 s e c o n d s $ The s e c o n d e p i s o d e f o l l o w s . •WELCOME TO ROSS: RECORD OF EPISODE AT 04:41 P.M. J A N . 2 9 , 1972 >EXFLORE RING5:OBJECT 2 >EXPLORE :MRT 3 * X PLM RT: FO UN D"M" OBJECT RING5:OBJECT 3 >EXPLORE :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 6 SNAP# 8 >IS? MOBILE:2 CONGRUENT TO MOBILE:3 CONGR OBJECT 2 OBJECT 3 :ENTERED 0 STEPS FAILED AT EDGE 24 EDGE 30 * * » * NO,MOBILE 2 IS'NT CONGRUENT TO MOBILE 3 ROBOT SIMULATION STUDIES EXPLORE M R T 5 BAD SNAP* 8 1 2 3 4 5 6 7 8 9 1 0 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 Y 1 . 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 2 B B 3 B E B 4 B B B 5 B E 6 B B B B B B B B B B E E B B B B B B B B B B B B 7 B B B B B E B B B B B B B B B B B B B B B B B B 8 B B B . . . . . . . . . B 9 B B B . M M M B 1 0 B M M M M M B B M M M M . . 3 . B 11 B M M M M M B B M M M M . H H . B 12 B M M B B $cbject 5$ H H . B 13 B Sobject 3$ B B . H H H H H H . B 14 B B B . H H H H H H . B 15 B B B . . . . . . . . B 1 6 B B B B B E E B B B B B M $cbject 6$ B 1 7 B B B B B B B B B B E B M B 1 8 B B B B E E E B B B B B M B 19 B B B M M M M M M M B 2 0 B B B M M M M M M M B 21 B B B M M M M M M M B 22 B M B B B 23 B M M M B B Sobject 4$ E 24 B B B B 25 B Sobject 2$. E E 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) ORIENTATION: WEST HOLDING: NOTHING CURRENT MRT: MRT 5 #FIXED OBJECTS KNOWN: 0 # M 0 V A EL E OBJECTS KNOWN: 4 #HOLES KNOWN: 1 Robot Simulation Studies 59 >IS? M0BILE:2 SIMILAR TO MOBILE:3 SIMILAR OBJECT 2 OBJECT 3 : ENTERED 0 TURNS FAILED AT EDGE 24 EDGE 30 1 STEPS NOT PROP. AT EDGE 22 EDGE 31 * NC,MOBI.LE 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 , AND 17 STEPS RIGHT. *YES,MOBILE 2 IS SIMILAR TO HOLE 6 >IS? MOBILE:3 C_CON TO HOLE:6 C_CONGR OBJECT 3 OBJECT 6 CENTERED 0 TURNS FAILED AT EDGE 30 EDGE 51 * LAST ALLOCATION OF MOV_PAR FOLLOWS: * TURN LEFT, MOVE 0 STEPS DOWN, AND 15 STEPS RIGHT. *YES,MOBILE 3 IS 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. R o b o t S i m u l a t i o n S t u d i e s 60 MRT12 LEFT,Y=16; BOTTOM,X=22; RIGHT,1=23; T0P,X=19; » J T 1 1 LEFT,Y=19; BOTTOM,X=22; RIGHT,Y=20; TOP,X=16; ENjD OF MRTS. CONTAIN OBJECT 3 OBJECT 4 :CONSTRUCTING LATTICE FOR OBJECT 4 LATCONS ENTERED * LATTICE OF OBJECT 4 FOLLOWS BNODE 8 $ BNODES a r e e q u i v a l e n c e c l a s s e s BN0DE 7 o f MRTs $ BNODE DETAILS ENODE 8 XDIM= 6 YDIM = 1 EQUIVCT= 1 HAS THE FOLLOWING MRTS MRT 11 HAS NO SUCCESSORS BNODE 7 XDIH= 3 YDIM = 7 EQUIVCT= 1 HAS THE FOLLOWING MRTS MRT 12 HAS NO SUCCESSORS •CONTAIN OBJECT 3 OBJECT 4 :SUCCESS AT STEP CT3 * LAST ALLOCATION OF MOV_PAR FOLLOWS: * TURN -NONE, MOVE 9 STEPS DOWN, AND 12 STEPS RIGHT. •YES,MOBILE 3 I S CONTAINED I N MOBILE 4 >IS? MOBILE:5 CONTAINABLE IN HOLE:6 Robot Simulation Studies 61 CONTAIN OBJECT 5 OBJECT 6 :ENTERED CONTAIN OBJECT 5 OBJECT 6 -.CONSTRUCTING MRTLIST FOR OBJECT 5 MRTS OF OBJECT 5 FOLLOW. BOTTOM,X =12 BOTTOM,X=10 BOTTOM/X= 12 RIGHT , Y = 21; TOP,X=10; RIGHT,1=22; TOP,X= 9; RIGHT,Y= 21; TOP,X= 9; MRT15 L EFT,Y=17 MRT14 LEFT , Y=19 MRT13 LEFT , Y=19 END OF MRTS. CONTAIN OBJECT 5 OBJECT 6 :CONSTRUCTING LATTICE FOR OBJECT 5 LATCCNS ENTERED * LATTICE OF OBJECT 5 FOLLOWS BNODE12 $ the top equivalence classes i n BNODE10 the l a t t i c e $ BNO.DE DETAILS BNODE12 XDIM= 3 Y DIM= 2 EQUIVCT= 1 HAS THE FOLLOWING MRTS MRT 1 3 HAS NO SUCCESSORS BNODE10 XDIM= 2 YDIM= n EQUIVCT= 1 HAS THE FOLLOWING MRTS MRT 15 HAS THESE IMMEDIATE SUCCESSORS BNODE11 Robot Simulation Studies 62 BNODE11 XDIM= 1 Y DIM= 3 EQUIVCT= 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 WITH THETA= 2 * STEP CT5:MRT13 IS BEST- FITS INTO OBJECT 6 IN 2 WAYS. •CONTAIN OBJECT 5 OBJECT 6 :FAIL AT STEP CT6 * NO,MOBILE 5 IS * NT CONTAINED IN HOLE 6 >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 END OF STACK * END OF PR STACK $ one hole $ $ no oddity $ Robot Simulation Studies 63 3.2 l!£l£IL§J]£i^ tion Lo g i c a l l y , the system consists of: The simulated world. The simulated robot, Robbie. Robbie's model of his world. To make i t into a usable system, there i s , f i r s t l y , a "camera" to provide snapshots of the world, and to give output showing how Robbie uses his model of the world, and secondly there i s a command interpreter to accept the user's commands and pass them onto Robbie (action and comparative commands) or to the routines which administer the simulated world (global commands), or to the camera (display commands). The system consists of over 25 PL/1 external procedures. About 4,700 PL/1 statements are involved. When loaded, ROSS occupies 50 pages of core. This figure grows rapidly when any list-processing i s done. For instance, by the end of the f i r s t episode l i s t e d i n section 3.1.4 an extra 16 pages had been used. This figure would be considerably reduced i f a) PL/1's AREA variables 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 done at the appropriate places. It takes about 36 seconds of CPU-time to load the program, most of which i s spent cn the PL/1 l i b r a r y . However, after 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 single declaration of most interest i s that of R o b o t S i m u l a t i o n S t u d i e s 64 an MRT, w h i c h i n ROSS i s t h e programmed e q u i v a l e n t o f t h e c o n c e p t o f a r e c t a n g u l a r r o o m . DCL 1 MRT BASED (MRTPTR) , 2 MRTNAME CHAR (10) , (2 YL,2 XB,2 YR,2 XT) FIXED B I N ( 1 6 , 0 ) , /*BOUNDING L I N E S * / (2 L E L I S T , 2 B E L I S T , 2 RE L I S T , 2 TELIST) PTR, / * L E L I S T POINTS TO LIST OF LEFT EDGES WH. DEFINE LEFT SIDE OF MRT*/ /* SIMLY FOR B E L I S T , R E L I S T , T E L I S T */ 2 MRTLINK PTR, /*FOR MAINTAINING MRT STACK*/ 2 LATLINK PTR, /*FOR USE I N L A T T I C E * / 2 MLAP PTR, /*HEAD S L I S T OF LAPNODES GIVING OVERLAP 5 INTERSECT PTES*/ 2 TRACEBACK PTR, /*FOR TRACING PATHS FROM PLACE TO PLACE IN ENVIRON*/ 2 IRTBACK PTR, /*FOR LOCATING CORRECT I R T , WEEN USING TRACEBACK*/ 2 WAVEPTF PTR, /*FOR LINKING W AVEFRONT * / 2 COLOUR FIXED BIN ( 1 6 , 0 ) ; /*FOR COLOURING MRTS * / The l a s t f o u r e n t r i e s a r e u s e d i n PLANS t c i m p l e m e n t t h e p a t h - f i n d i n g a l g o r i t h m i n a r a t h e r c l u m s y f a s h i o n . They c o u l d be removed w i t h an i m p r o v e d v e r s i o n o f PLANS ( i t w o u l d t h e n a l s o be e a s y t o s t o r e o l d p l a n s ) . The f i r s t e p i s o d e r e c o r d e d i n 3.1.4 t o o k o n l y 2.19 s e c o n d s o f CPU t i m e , s o t h e e x e c u t i o n t i m e 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 S t u d i e s 65 C h a s t e r 4 C o n c l u s i o n 4 . 1 S u ro ma r % We have d e s i g n e d and i m p l e m e n t e d a s i m p l e r o b o t s i m u l a t i o n s y s t e m . The r o b o t c a n e x p l o r e i t s e n v i r o n m e n t i n a v e r y s i m p l e manner, and c a n make e l e m e n t a r y p l a n s t o move f r o m p l a c e t o p l a c e . The r o b o t u s e s an e l e m e n t a r y model o f h i s w o r l d t o move a b o u t , and c a n add new i n f o r m a t i o n t o t h i s w o r l d i n a n u n s t r u c t u r e d way a s he e x p l o r e s h i s w o r l d . I n t h e c o u r s e o f o u r s i m u l a t i o n s t u d i e s we have d e a l t s i m p l e m i n d e d l y w i t h two b a s i c p r o b l e m s : c o n c e p t 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 a nd e x e c u t i o n o f p l a n s . We h a v e e n c o u n t e r e d t h e p r o b l e m o f e x p l o r a t i o n , b u t o u r method o f d e a l i n g w i t h i t needs i m p r o v e m e n t . I n a n y a t t e m p t s t o make t h e r o b o t more i n t e l l i g e n t we w i l l f i n d o u r s e l v e s f a c i n g some i m p o r t a n t p r o b l e m s , a s d e t a i l e d b e l o w i n s e c t i o n 4 . 2 . 2 . . 4.2 ' D i l ^ c t i o n s f o r f u r t h e r work T h e s e w i l l be d i s c u s s e d i n t h r e e p a r t s , one f o r e a c h o f t h e p r e c e e d i n g c h a p t e r s . R o b o t S i m u l a t i o n S t u d i e s 66 4.2.1 P r e a m b l e F i r s t l y , i t i s c l e a r t h a t a d e f i n i t i v e h i s t o r y o f a u t o m a t a and o f t h e r o b o t c o n c e p t i s s t i l l t o be w r i t t e n ; none o f t h e r e f e r e n c e s g i v e n i n 1.1 p r o v i d e a c o m p r e h e n s i v e t r e a t m e n t . F o r i n s t a n c e , I know o f no s t u d y o f t h e Golem l e g e n d s . S e c o n d l y , c o n c e r n i n g t h e a p p r o a c h e s t o a r t i f i c i a l i n t e l l i g e n c e , i t m i g h t be u s e f u l t o s t u d y some o f t h e c l a s s i c a l w orks on e p i s t e m o l o g y [ H u , K a , L c ] a s p o s s i b l e s o u r c e s o f i d e a s f o r i n c o r p o r a t i n g k n o w l e d g e o f t h e w o r l d i n t o m a c h i n e s . The s c h o l a r l y s t u d y by R o b e r t M. Young [ Y ] , w h i c h t r a c e s t h e most i m p o r t a n t p h i l o s o p h i c a l , p s y c h o l o g i c a l and p h y s i o l o g i c a l i d e a s o f n i n e t e e n t h c e n t u r y w o r k e r s c o n c e r n i n g t h e r e l a t i o n s among m i n d , body and t h e e n v i r o n m e n t , may a l s o be a u s e f u l s o u r c e . H a y e s , i n a p a p e r e n t i t l e d " R o b o t c l o g i c " [ H a 1 ] , u s e s r e s u l t s and a r g u m e n t s f r o m modern p h i l o s o p h i c a l l o g i c and a n a l y t i c a l p h i l o s o p h y . T h i r d l y , t h e d i s c u s s i o n c o n c e r n i n g t h e a p p a r e n t c o n f l i c t b e t w e e n t h e i n t u i t i v e and l i n g u i s t i c a p p r o a c h e s t o a r t i f i c i a l i n t e l l i g e n c e c o u l d be g r e a t l y e x p a n d e d ; t h e i s s u e s r a i s e d w o u l d a l s o , I t h i n k , be f u n d a m e n t a l t o t h e p r o b l e m o f l a n g u a g e u n d e r s t a n d i n g . 4.2.2 D e s i g n I n t h e work r e p o r t e d h e r e we have m e r e l y s c r a t c h e d t h e s u r f a c e o f some o f t h e p r o b l e m s i n v o l v e d i n e i t h e r s i m u l a t i n g o r b u i l d i n g an i n t e l l i g e n t r o b o t . I s h a l l l i s t what seem t o me t o Robo t S i m u l a t i o n S t u d i e s 67 be t h e most p r e s s i n g p r o b l e m s . T h e r e a r e two o f t h e s e . T h e f i r s t i s : What " e x p e c t a t i o n s " s h o u l d t h e r o b o t h a v e , and how s h o u l d i t b e h a v e , when f i r s t i n t r o d u c e d to a new e n v i r o n m e n t ? S u p p o s i n g the r o b o t s ' b e h a v i o u r i s t o make random p r o b e s i n t o i t s new s u r r o u n d i n g s , how s h o u l d t h e r e s u l t i n g p i e c e - m e a l b i t s o f i n f o r m a t i o n be u t i l i z e d ? A vague s u g g e s t i o n c o n c e r n i n g t h i s was made i n s e c t i o n 2 .4 . T h e s e c o n d e x p l o r i n g p r o b l e m i s t h i s . When the r o b o t has d i s c o v e r e d a new o b j e c t i n i t s s u r r o u n d i n g s , how s h o u l d i t use t h i s new i n f o r m a t i o n to i m p r o v e i t s p l a n n i n g a b i l i t i e s , and t h u s t o i m p r o v e i t s e f f i c i e n c y a t w a l k i n g f rom p l a c e t o p l a c e ? E a s j j nov ing p r g b l e m s How s h o u l d t h e r o b o t p l a n i t s a c t i o n s when i t wants to move a s i m p l e o b j e c t , s u c h as a r e c t a n g l e o f d i m e n s i o n s 2 - b y - 6 , f r o m one p a r t o f i t s e n v i r o n m e n t t o a n o t h e r ? How s h o u l d the r o b o t r e p r e s e n t i t s w o r l d when i n t h e m i d d l e o f s u c h an a c t i o n , f o r i n s t a n c e when t h e 2-by-6 r e c t a n g l e i s i n the m i d d l e o f a doorway and o v e r l a p s t h r e e d i f f e r e n t MRTs (at l e a s t ) ? T h e b a s i c q u e s t i o n i s : How t o r e p r e s e n t t h e e n v i r o n m e n t p l u s known o b j e c t s ? Some o f t h e d e s c r i p t i o n s u sed by W i n s t o n [ W i ] m i g h t be u s e f u l h e r e . S u b t l e movino. p r o b l e m s Suppose t h e r e i s an ' L ' - s h a p e d o b j e c t i n a room w i t h one d o o r w a y , and t h e l e n g t h s o f t h e arms o f t h e ' L ' a r e g r e a t e r t h a n Robot S i m u l a t i o n S t u d i e s 68 the width of the doorway. Then i f the two s i d e s are f l u s h with one another there i s no way t h a t the 'L' could be moved out of the room. But i f the s i d e s of the doorway are o f f s e t from one another by at l e a s t as much as the width of the arms of the 'L*, then the 'L' can probably be moved through the doorway i n a • s u b t l e ' f a s h i o n . In other words, a simple s l i d i n g b l o c k p u z z l e . How should the robot solve t h i s problem? Once the easy moving problem has been s o l v e d , the ' s u b t l e ' moving problem w i l l probably turn out to be r a t h e r easy, using known problem-solving techniques. Concept formatjLon In the design of our robot we have "endowed" i t from " b i r t h " with the concept of a r e c t a n g u l a r space (MRT), with the procedures f o r moving w i t h i n one such space, and with the procedures f o r r e l a t i n g these spaces to one another i n a manner u s e f u l f o r moving from p l a c e t o place w i t h i n a n O n - t r i v i a l environment. A b a s i c q u e s t i o n i s : How could a robot be programmed to l e a r n these concepts and procedures? I would s p e c u l a t e t h a t concepts and procedures a t t h i s l e v e l are, i n Nature, b u i l t - i n , or i n other words have been " l e a r n t " through e v o l u t i o n . Consequently i t w i l l be hard to design a robot to l e a r n anything l i k e the concept of a maximal s u b r e c t a n g l e . T h i s problem was considered by Larry T r a v i s [ T r ] , A n a l y s i s , d e s c r i p t i o n ^ and comparison 9.%. JE^ctancjuloid shapes Robot S i m u l a t i o n S t u d i e s 69 A n a l y z e s h a p e s s u c h a s t h o s e i n f i g u r e 10 i n ways w h i c h w i l l be u s e f u l t o a r o b o t i n r e a s o n i n g a b o u t i t s w o r l d . The t o p and b o t t o m e x a m p l e s c l e a r l y r e q u i r e a n o t i o n o f " a p p r o x i m a t i o n " b e t w e e n r e c t a n g u l o i d s h a p e s . A g a i n , W i n s t o n ' s t h e s i s [ W i ] m i g h t be a good s t a r t i n g p o i n t . S i n c e r e c t a n g l e s a r e , i n a c e r t a i n s e n s e , t h e s i m p l e s t k i n d o f r e c t a n g u l o i d s h a p e , any a l g o r i t h m w h i c h a n a l y z e s o r p a r s e s an a r b i t r a r y s h a p e o f t h i s s o r t i n t o i t s m a x i m a l s u b r e c t a n g l e s i s n o t i n s i g n i f i c a n t . I s u s p e c t t h a t DECOMP ( s e c t i o n 2.3.2) i s a r e a s o n a b l y good a l g o r i t h m f o r t h e t a s k . Can a m a t h e m a t i c a l a n a l y s i s be p r o v i d e d w h i c h p r o v e s t h i s , o r e l s e c a n a s u b s t a n t i a l l y b e t t e r a l g o r i t h m be d e v i s e d ? The o p e r a t i o n o f c o m p a r i n g two s h a p e s f o r c o n t a i n m e n t , w h e t h e r r e c t a n g u l o i d s h a p e s o r o t h e r w i s e , w o u l d seem t o be a f u n d a m e n t a l t w o - d i m e n s i o n a l o p e r a t i o n i n many c o n t e x t s . Can t h e a l g o r i t h m CONTAIN g i v e n i n s e c t i o n 2 . 3.3, w h i c h i s c l e a r l y v e r y c r u d e , be i m p r o v e d ? More g e n e r a l l y , d e v i s e a CONTAIN a l g o r i t h m f o r t h r e e o r more d i m e n s i o n s . The e f f i c i e n c y o f t h e p r e s e n t CONTAIN a l g o r i t h m i s h i g h l y d e p e n d e n t on t h e " c o m p l e x i t y " o f t h e r e c t a n g u l o i d s h a p e s b e i n g c o m p a r e d ; i n d e e d , t o c ompare t h e e f f i c i e n c i e s o f d i f f e r e n t CONTAIN a l g o r i t h m s i t w i l l be n e c e s s a r y t o m e a sure a n d / o r bound t h e " c o m p l e x i t i e s " o f t h e c o m p a r a n d s . T h i s r a i s e s t h e p r o b l e m : g i v e a g ood d e f i n i t i o n o f c o m p l e x i t y f o r t w o - d i m e n s i o n a l ( r e c t a n g u l o i d ) s h a p e s . I s t h e c o m p a r i s o n o f s h a p e s f o r c o n t a i n m e n t a f u n d a m e n t a l l y c o m p l e x o p e r a t i o n ? Robot S i m u l a t i o n S t u d i e s 70 G e n e r a l i z a t i o n s F i n a l l y t h e r e a re a whole h o s t of ways i n which one might g e n e r a l i z e the system. For i n s t a n c e : use an environment which a l l o w s more g e n e r a l shapes than r e c t a n g u l a r p o l y g o n s ; e x t e n d t h e r e c t a n g u l a r world t o t h r e e d i m e n s i o n s ; a l l o w a mere g e n e r a l form of v i s i o n ; or make the r o b o t t r u l y autonomous by i n c l u d i n g v a r i o u s forms of m o t i v a t i o n such as hunger and t h i r s t . 4.2.3 ROSS I f ROSS were c o m p i l e d u s i n g one of the b e t t e r PL/1 c o m p i l e r s 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 time would l i k e l y d e c r e a s e c o n s i d e r a b l y . I f ROSS were t o be e x t e n s i v e l y used i t would be worth w r i t i n g t h e world d e f i n i t i o n p r o c e d u r e s i n a l o w - l e v e l language. The pro c e d u r e s d e a l i n g w i t h r i n g -r e p r e s e n t a t i o n s and w i t h MRTs c o u l d perhaps be r e w r i t t e n i n LISP: t h i s would, i n the s h o r t - r a n g e , r e s u l t i r a g r e a t l o s s of of e f f i c i e n c y , and i n the f a c t t h a t MRTs would no l o n g e r appear i n such a compact form; i n the l o n g range, i t would a l l o w f o r the p o s s i b i l i t y of new c o n c e p t s , p r o c e d u r e s , and p l a n s b e i n g c r e a t e d and m o d i f i e d by the r o b o t s ' own pr o c e d u r e s . A PLANNER-l i k e language would be of g r e a t use i n d e a l i n g w i t h p l a n s . I t s h o u l d not be too hard to extend ROSS to i n c l u d e ways o f d e a l i n g w i t h e x p l o r i n g and moving problems. Robot S i m u l a t i o n S t u d i e s 71 A i A i d a , S., C o r d e l i a , 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 s y m b i o t i c s y s t e m f o r s t e r e o m e t r i c p a t t e r n r e c o g n i t i o n " , S e c o n d 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 , B r i t i s h C omputer 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 o f p r o b l e m s c f r e a s o n i n g a b o u t 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 . M i c h i e , E d i n b u r g h U n i v e r s i t y P r e s s , E d i n b u r g h (1968) , pp. 1 3 1 - 1 7 1 . As A s i m o v , I s a a c , I j , R o b o t and The R e s t o f t h e R o b o t s , P a n t h e r B o o k s ( 1 9 6 7 , 1 9 6 8 ) . Ba1 B a r r o w , H.G., and P o p p l e s t o n e , R . J . , " R e l a t i o n a l d e s c r i p t i o n s i n p i c t u r e - p r o c e s s i n g " , 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. M e l t z e r and D. M i c h i e , E d i n b u r g h U n i v e r s i t y P r e s s , E d i n b u r g h (1971) , p p . 3 7 7 - 3 9 6 . Ba2 B a r r o w , H . G . , and S a l t e r , S.H., " D e s i g n o f l o w - c o s t e q u i p m e n t f o r c o g n i t i v e r o b o t r e s e a r c h " , Masking Intelligence 5 , e d i t e d by B . M e l t z e r 8 D. M i c h i e , A m e r i c a n E l s e v i e r P u b l i s h i n g Company, I n c . , N.Y. ( 1 9 7 0 ) , p p . 5 5 5 - 5 6 6 . Bo Bower, T.G.R., "The o b j e c t i n t h e w o r l d o f t h e i n f a n t " , 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 ) , p p . 3 0 - 3 8 . Bu B u r s t a l l , 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 e n v i r o n m e n t by u s i n g t h e a l g e b r a i c t h e o r y o f d e c o m p o s i t i o n o f a u t o m a t a " , D e p t . Of M a c h i n e I n t e l l i g e n c e and P e r c e p t i o n , U n i v e r s i t y o f E d i n b u r g h , MIP-R-56 (May 1 9 6 9 ) . Ca C a p e k , K a r e l , "R.U.R." ( 1 9 2 0 ) . Ch C h a p u i s , A l f r e d , and D r o z , Edmond, A u t o m a t a , E d i t i o n s du G r i f f o n , N e u c h a t e l ( 1 9 5 8 ) . Co C o h e n , J o h n , Human - R o b o t s i n Myth and S c i e n c e ,, G e o r g e A l l e n 5 Unwin L t d . ( 1 9 6 6 ) . D1 D o r a n , J . E . , " E x p e r i m e n t s w i t h a p l e a s u r e - s e e k i n g a u t o m a t o n " . 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. M i c h i e , E d i n b u r g h U n i v e r s i t y P r e s s , E d i n b u r g h ( 1 9 6 8 ) , p p . 1 3 1 - 1 7 1 . D2 D o r a n , J . E . , " P l a n n i n g a nd g e n e r a l i s a t i o n i n an a u t o m a t o n / e n v i r o n m e n t s y s t e m " , M a c h i n e I n t e l l i g e n c e 4 , e d i t e d by D. M i c h i e S B. M e l t z e r , A m e r i c a n 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 (1969) , p p . 4 3 3 - 4 5 4 . R o b o t S i m u l a t i o n S t u d i e s 72 D3 D o r a n , 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. M i c h i e , A m e r i c a n E l s e v i e r P u b l i s h i n g Company, I n c . , N.Y. ( 1 9 7 0 ) , p p . 5 1 9 - 5 3 2 . DU D o r a n , J . E . , "Some r e c e n t m o d e l s o f t h e b r a i n " , M a c h i n e Intelligence 6 , e d i t e d by B . M e l t z e r & D. M i c h i e , A m e r i c a n E l s e v i e r P u b l i s h i n g Company, I n c . , N.Y. ( 1 9 7 1 ) , pp. 2 0 7 - 2 2 0 . E E j i r i , M . , 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 d e c i s i o n -m a k i n g a b i l i t y " , S e c o n d 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 , B r i t i s h C omputer S o c i e t y (1971) , p p . 3 5 0 - 3 5 3 . J . A . , e t a l . , "The S t a n f o r d hand -" eye p r o j e c t " , P r o c e e d i n g s o f t h e 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 c j e n c e , W a s h i n g t o n (May 1969) , p p . 52 1-526a. J . A . , e t a l . , "The u s e o f v i s i o n and m a n i p u l a t i o n t o 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 " . S e c o n d I n t e r n a t i o n a 1 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 , B r i t i s h C o m p u t e r S o c i e t y (1971) , pp. 3 5 9 - 3 6 4 . F i 1 P i k e s , R i c h a r d E., " M o n i t o r e d e x e c u t i o n o f r o b o t p l a n s p r o d u c e d by STRIPS ", I F I P C o n g r e s s 197 1, L j u b l j a n a , Y u g o s l a v i a ( 1 9 7 1 ) . F i 2 F i k e s , R i c h a r d E . , and N i l l s c n , N i l s J . , "STRIPS : a new a p p r o a c h t o t h e a p p l i c a t i o n o f t h e o r e m p r o v i n g t o p r o b l e m s o l v i n g " , S e c o n d 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 C omputer S o c i e t y (1971) , pp. 6 0 8 - 6 2 0 . F r e F r e i b e u r g h o u s e , "The M u l t i c s PL/1 c o m p i l e r " , AFIPS c o n f e r e n c e p r o c e e d i n g s , 3 5 , FJCC (1969) pp. 187-199. F r 1 F r i e d m a n , L . , " I n s t i n c t i v e b e h a v i o u r and i t s c o m p u t e r 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 . 8 5 - 1 0 8 . F r 2 F r i e d m a n , L . , " R o b o t 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 o f t h e 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 , W a s h i n g t o n (May 1969) , p p . 527-5 4 0 . Gr G r e g o r y , R . L . , "The s o c i a l i m p l i c a t i o n s o f i n t e l l i g e n t m a c h i n e s " , M a c h i n e I n t e l l i g e n e e 6 , e d i t e d by B. M e l t z e r & D. M i c h i e , A m e r i c a n E l s e v i e r P u b l i s h i n g Company, I n c . , N.Y. ( 1 9 7 1 ) , p p . 3 - 1 3 . Fe1 F e l d m a n , Fe2 F e l d m a n , 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 , v o l . 4, Robot S i m u l a t i o n S t u d i e s L e y d e n ( 1 9 0 7 ) , p. 342 f f . Hd Hadamard, J . , "The p s y c h o l o g y o f i n v e n t i o n i n t h e m a t h e m a t i c a l f i e l d " , P r i n c e t o n U n i v e r s i t y P r e s s ( 1 9 4 5 ) . Ha1 H a y e s , P . J . , " R o b o t o l o g i c " , 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 S D. M i c h i e , A m e r i c a n E l s e v i e r P u b l i s h i n g Company, I n c . , N.Y. (1970) , p p . 533-5 5 4 . 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. M e l t z e r & D. M i c h i e , A m e r i c a n E l s e v i e r P u b l i s h i n g Company, I n c . , N.Y. ( 1 9 7 1 ) , p p . 4 9 5 - 5 2 0 . 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 models and p r o v i n g t h e o r e m s i n a r o b o t " , M.I.T. P r o j e c t MAC, A r t i f i c i a l I n t e l l i g e n c e Memo. No. 168 ( A u g u s t 1 9 7 0 ) . Hu Hume, D a v i d , Eng_ui_ry; c o n c e r n i n g human u n d e r s t a n d i n g , f i r s t e d i t i o n d a t e d 1 7 7 7 . IBM "OS PL/1 O p t i m i z i n g C o m p i l e r " , P r o g r a m number 5734-PL1 IBM "OS PL/1 C h e c k o u t C o m p i l e r " , P r o g r a i r number 5734-PL2 Ka K a n t , I m m a n u e l , C r j t i g j j e o f pu r e r e a s o n , f i r s t e d i t i o n d a t e d 178l7 K K i n o s h i t a , G e n - i c h i r o , S h u h e i , A i d a , M o r i , M a s a h i r o , " P a t t e r n r e c o g n i t i o n by an a r t i f i c i a l t a c t i l e s e n s e " , S e c o n d 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 c j e n c e , E r i t i s h C o mputer S o c i e t y (1971) , p p . 3 7 6 - 3 8 4 . L L i a o - c h a i c h i ( i ) c h . 15. L c L o c k e , J o h n , E s s a ^ c o n c e r n i n g human uM§£§ tajidjLng ^ f i r s t p u b l i s h e d 1690. Lo L o r e n z , K o n r a d Z. , Jin<j S o l o m c n ^ s R i n g , Thomas Y. C r o w e l l Company, New Y o r k ( 1 9 6 1 ) . 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., and V i c e n s , P . J . , "A c o m p u t e r w i t h h a n d s , e y e s , and e a r s " , FJCC 1968, p p . 3 2 9 - 3 3 8 . Mc2 M c C a r t h y , J . , and 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 f r o m t h e s t a n d p o i n t o f a r t i f i c i a l i n t e l l i g e n c e " . M a c h i n e I n t e l l i g e n c e 4 , e d i t e d by D. M i c h i e & B . M e l t z e r , A m e r i c a n 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 (1969) , p p . 4 6 3 - 5 0 2 . Robot S i m u l a t i o n S t u d i e s 74 Mc3 M c C a r t h y , J . , e t a l . , S t a n f o r d A r t i f i c i a l I n t e l l i g e n c e 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 , M a r c h 1 9 7 1 . Mc4 M c C a r t h y , J o h n , " P r o g r a m s w i t h common s e n s e " (November 1 9 5 8 ) , and " S i t u a t i o n s , a c t i o n s , and c a u s a l l a w s " ( 1 9 6 3 ) , r e p r i n t e d t o g e t h e r a s Ch.7 o f S e m a n t i c I n f o r m a t i o n P r o c e s s i n g , e d i t e d by M . L . M i n s k y , MIT P r e s s ( 1 9 6 8 ) . Mk MacKay,D.M., "The e p i s t e m o l o g i c a l p r o b l e m f o r a u t o m a t a " , A u t o m a t a S t u d i e s , A n n a l s o f M a t h e m a t i c s S t u d i e s No. 3 4 , P r i n c e t o n D n i v e r s i t y P r e s s (1956) , pp. 2 3 5 - 2 5 1 . Mn1 M i n s k y , M a r v i n L . , " I n t r o d u c t i o n " , S e m a n t i c i n f o r m a t i o n P r o c e s s i n g , e d i t e d by M . L . M i n s k y , MIT P r e s s ( 1 9 6 8 ) , pp. 1-32. Mn2 M i n s k y , M a r v i n , "Form and computer s c i e n c e " , J . A . C M . _17, No.2 ( A p r i l 1 9 7 0 ) , p p . 1 9 7 - 2 1 5 . Mu1 Munson, J o h n H., "The SRI 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 " , S t a n f o r d R e s e a r c h I n s t i t u t e , A r t i f i c i a l I n t e l l i g e n c e G r o u p , T e c h n i c a l n o t e 19 ( J a n u a r y 1 9 7 0 ) . Mu2 Munson, J o h n H., " R o b o t p l a n n i n g , e x e c u t i o n , and m o n i t o r i n g i n an u n c e r t a i n e n v i r o n m e n t " , S e c o n d 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 , B r i t i s h C o m p u t e r S o c i e t y ( 1 9 7 1 ) , pp. 3 3 8 - 3 4 9 . Ne1 Needham, J o s e p h , S c i e n c e and C i v i l i s a t i o n i n C h i n a , Volume 2: " H i s t o r y o f S c i e n t i f i c T h o u g h t " , 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 ) . Ne2 Needham, J o s e p h , Man a m a c h i n e , W.W.Norton and Company I n c . , New Y o r k (1928) . N i l N i l s s o n , N i l s 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 and 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 P r e s s I n c . , New York ( 1 9 6 7 ) , p p. 2 3 5 - 2 5 9 . N i 2 N i l s s o n , N i l s J . , "A m o b i l e a u t o m a t o n : an a p p l i c a t i o n o f a r t i f i c i a l i n t e l l i g e n c e t e c h n i q u e s " , ? £ o c e e d i n g s p f t h e I n t e r n a t i o n a l J o i nt 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 , W a s h i n g t o n (May 1969) , p p . 5 0 9 - 5 2 0 . No N o t o n , D a v i d , and S t a r k , L a w r e n c e , "Eye movements and v i s u a l p e r c e p t i o n " , S c i e n t i f i c A m e r i c a n 2 2 4 , No. 6 ( J u n e 1 9 7 1 ) , p p. 3 4 - 4 3 . Ph P o h l , I r a , " B i - d i r e c t i o n a l and h e u r i s t i c s e a r c h i n p a t h p r o b l e m s " . T e c h n i c a l R e p o r t No. CS 136 , R o b o t S i m u l a t i o n S t u d i e s 75 Computer S c i e n c e U n i v e r s i t y {May 1 9 6 9 ) . D e p a r t m e n t , S t a n f o r d Po1 P o p p l e s t o n e , R . J . , " F r e d d y i n T o y l a n d " , M a c h i n e I H t e l l i g e n c e 4 , e d i t e d by D. M i c h i e & B . M e l t z e r , A m e r i c a n 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 {1969) , pp. 4 5 5 - 4 6 2 . Po2 P o p p l e s t o n e , R . J . , "How F r e d d y c o u l d p u t t h i n g s t o g e t h e r " , D e p a r t m e n t o f M a c h i n e I n t e l l i g e n c e and P e r c e p t i o n , U n i v e r s i t y o f E d i n b u r g h , MIP-R-88 (May 1 9 7 1 ) . R1 R a p h a e l , Se Sh B e r t r a m , " p r o g r a m m i n g a r o b o t " . I n f o r m a t i o n I!l2£^ssin3 68 , N o r t h H o l l a n d P u b l i s h i n g Co. (1969) , p p . 1575- 1581 . R2 R a p h a e l , B e r t r a m , "The r e l e v a n c e o f r o b o t r e s e a r c h t o a r t i f i c i a l i n t e l l i g e n c e " , S t a n f o r d R e s e a r c h I n s t i t u t e , A r t i f i c i a l I n t e l l i g e n c e G r o u p , T e c h n i c a l N o t e 13 (May 1 9 6 9 ) . R3 R a p h a e l , B e r t r a m , "The f r a m e p r o b l e m 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_ I n s t i t u t e on A r t i f i c i a l I n t e l l i g e n c e and h e u r i s t i c E E°3£ a m m i n g , M e n a g g i o , I t a l y ( A u g u s t 1 9 7 0 ) . Sc Scheinman, V. , " D e s i g n o f a c o m p u t e r m a n i p u l a t o r " , AIM-92, S t a n f o r d I n t e l l i g e n c e P r o j e c t . c o n t r o l l e d A r t i f i c i a l S e c o n d 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 cn 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 er S o c i e t y ( 1 9 7 1 ) . S h e u - s h e n k i C h . 1. S i S l o m a n , Su Sutro, A a r o n , " I n t e r a c t i o n s b e t w e e n p h i l o s o p h y and a r t i f i c i a l i n t e l l i g e n c e : t h e r o l e o f i n t u i t i o n and n o n - l o g i c a l r e a s o n i n g i n i n t e l l i g e n c e " , S e c o n d 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 , B r i t i s h Computer S o c i e t y (1971) , pp. 2 7 0 - 2 7 8 . L o u i s L . , and K i l m e r , W i l l i a m I . , " A s s e m b l y o f c o m p u t e r s t o command and c o n t r o l a r o b o t " , A F I P S C o n f e r e n c e P r o c e e d i n g s , 3 4 , SJCC ( 1 9 6 9 ) , pp. 113-137. Tr T r a v i s , L a r r y E . U U h r , L e o n a r d , and K o c h e n , M a n f r e d , " M i k r c k o s m o s and r o b o t s " . P r o c e e d i n g s o f t h e 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 1 I n t e l l i g e n c e , W a s h i n g t o n (May 1969) , p p . 54 1-555. Wa W a l t e r , W.Grey, The L i v i n g B r a i n , D u c k w o r t h ( 1 9 5 3 ) , and Robot S i m u l a t i o n S t u d i e s 76 P e n g u i n Books L t d . ( 1 9 6 1 ) . Wi W i n s t o n , 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 e x a m p l e s " , P r o j e c t MAC r e p o r t TR-76, MIT ( S e p t e m b e r 1 970) . Y Y o u n g , R o b e r t M., M i n d ^ B r a i n ^ and A d a p t a t i o n i n t h e N i n e t e e n t h C^ntur_y , C l a r e n d o n P r e s s , O x f o r d (1970) . R o b o t S i m u l a t i o n S t u d i e s 77 A p p e n d i x A D § t a i l e J d e s c r i p t i o n o f t h e a l g o r i t h m DECOMP The c o o r d i n a t e s y s t e m u s e d f o r d e f i n i n g t h e s i d e s o f t h e m a x i m a l s u b r e c t a n g l e s o f an o b j e c t h a s i t s o r i g i n a t t h e t o p l e f t - h a n d c o r n e r o f t h e o b j e c t , x - a x i s d i r e c t e d downwards and y-a x i s d i r e c t e d t o t h e r i g h t . The r e p r e s e n t a t i o n r i n g o f an o b j e c t a l w a y s s t a r t s w i t h t h e l e f t edge whose t o p end i s a t t h e t o p l e f t - h a n d c o r n e r o f t h e o b j e c t . . A m a x i m a l s u b r e c t a n g l e h a s , o f c o u r s e , f o u r s i d e s c a l l e d , r e s p e c t i v e l y , l e f t , b o t t o m , r i g h t and t o p . T h i s i s shown i n f i g u r e 17. The a l g o r i t h m t o be d e s c r i b e d d o e s more t h e n p r o d u c e a l i s t o f t h e m a x i m a l s u b r e c t a n g l e s o f an o b j e c t ; i t p r o d u c e s a l i s t o f MRTs. I n t h i s a p p e n d i x , t h e s y m b o l "MRT" s t a n d s f o r a d a t a s t r u c t u r e w i t h i n t h e c o m p u t e r c o n t a i n i n g t h e f o u r s i d e s o f a m a x i m a l s u b r e c t a n g l e ( l e f t , b o t t o m , r i g h t , and t o p ) and f o u r l i s t s o f p o i n t e r s , one f o r e a c h s i d e . The p o i n t e r s i n t h e l i s t a s s o c i a t e d w i t h t h e b o t t o m s i d e o f a m a x i m a l s u b r e c t a n g l e p o i n t t o a l l t h e b o t t o m edges o f t h e r e p r e s e n t a t i o n r i n g w h i c h h e l p e d d e f i n e t h i s s i d e ; s i m i l a r l y f o r t h e p o i n t e r s i n t h e l i s t a s s o c i a t e d w i t h t h e l e f t , r i g h t , and t o p s i d e s . N o t e t h a t we a r e t r y i n g , i n t h i s a p p e n d i x , t o keep d i s t i n c t t h e c o n c e p t o f a m a x i m a l s u b r e c t a n g l e a s d e f i n e d i n s e c t i o n 2 . 3 . 2 , and t h a t o f an MRT a s a d a t a s t r u c t u r e w i t h i n t h e c o m p u t e r . In g e n e r a l , h o w e v e r , t h e c o n c e p t s may s a f e l y be c o n f u s e d . The a l g o r i t h m i s i n two p a r t s . P a r t 1 m e r e l y g e n e r a t e s some t e m p o r a r y i n f o r m a t i o n r e q u i r e d by P a r t 2. A p h r a s e s u c h as " t h e top l e f t r i g h t sr X bottom Sides of a maximal rectangle. Coordinate system used has i t s o r i g i n at the top l e f t hand corner of the object, i - a x i s d i r e c t e d downward and y-axis d i r e c t e d to the r i g h t . The coordinates of a few points of OBJA are l i s t e d : A (0,0), E (4,-2), K (7,10) . D e f i n i t i o n of the coordinates of an edge Type Coordinates Diagram l e f t Y l , X I 1 , X I 2 Y l X l ' . . . X I 2 . . . bottom Xb, Yb 1, Yb 2 Xb Yb y i 2 Yr r i g h t Y r, X r 1 , X r 2 .:*... Xr ... Xr top X t, Y t 1 , Y t 2 Xt ... Y ;1 *2 Yt D e f i n i t i o n s required f o r the algorithm DECOMP. Figure 17. R o b o t S i m u l a t i o n S t u d i e s 7 8 n e x t r i g h t e dge" means " t h e n e x t r i g h t e d ge i n t h e o r d e r o b t a i n e d by t r a v e r s i n g t h e r e p r e s e n t a t i o n r i n g i n t h e n a t u r a l ( a n t i - c l o c k w i s e ) o r d e r " . See f i g u r e s 18, 19 . A l g o r i t h m DECOMP I n p u t : The r e p r e s e n t a t i o n r i n g o f an o b j e c t . O u t p u t : A l i s t o f MRTs o f t h i s o b j e c t , e x a c t l y one c o r r e s p o n d i n g t o e a c h m a x i m a l s u b r e c t a n g l e o f t h e o b j e c t . P a r t J Run a r o u n d t h e d e s c r i p t i o n r i n g and g e n e r a t e f o r e a c h edge f o u r new f i e l d s o f i n f o r m a t i o n . The f i r s t f i e l d c o n t a i n s t h e t y p e o f t h e edge : l e f t , b o t t o m , r i g h t , o r t o p . The r e m a i n i n g t h r e e f i e l d s c o n t a i n t h e c o o r d i n a t e s o f t h e e d g e , w h i c h depend upon t h e t y p e a s f o l l o w s : Type H e l d - J F i e l d 2 F i e l d 3 L e f t Y l X l i X12 B o t t o m Xb ?b* Yb2 R i g h t Y r X r i X r 2 Top Xt Yt* Yt 2 T h i s i s i m p l e m e n t e d i n my p r o g r a m a s t h e c o n s t r u c t i o n o f a new r i n g " c o n c e n t r i c " w i t h t h e r e p r e s e n t a t i o n r i n g . P a r t 2 D l . S e t up t h e empty MRT l i s t . D L L Take t h e f i r s t l e f t edge L and go t o D E L DL2. Take t h e n e x t l e f t edge L. I f no more l e f t e d g e s , s t o p and r e t u r n a p o i n t e r t o t h e MRT l i s t . name = OBJECT 2 Sedges - 20 absolute l o c a t i o n of the top l e f t hand corner, A. • s pointer to edgel • v: Upper h a l f : the r i n g - representation of OBJA. Lower hal f : the r i n g of temporary information generated by Part 1 of the algorithm DECOMP, "concentric" with the r i n g - representation. i name : MRT 1 l e f t side : y = 0 bottom side : x = 3 ri g h t side : y = 9 top side : x = 2 pointers to edges d e f i n i n g l e f t side : edgel pointers to edges d e f i n i n g bottom side : edge2, edgel4 pointers to edges d e f i n i n g r i g h t side : edgel 5 pointers to edges d e f i n i n g top side : edgel8 ^ name : MRT 7 l e f t side : y = 4 bottom side : x = 7 ri g h t side : y = 6 top side : x = 0 pointers to edges d e f i n i n g l e f t side : edge9, edgel7 pointers to edges d e f i n i n g bottom side : edgel0 pointers to edges d e f i n i n g r i g h t side : edgel3 pointers to edges d e f i n i n g top side ; edgel6 The output from DECOMP i s a l i s t of nine MRTs, one f o r each of the maximal subrectangles of OBJA. Two members of t h i s l i s t are shown. This corresponds to maximal subrectangle R7 of OBJA. This corresponds to maximal subrectangle R8 of OBJA. Robot Simulation Studies 79 DB1. Take t h e f i r s t b o t t o m edge B a c c e s s i b l e f r o m L and go t o DR1 . DB2. Take t h e n e x t b o t t o m edge B a c c e s s i b l e f r o m L . I f no s u c h b o t t o m e d g e , go b a c k t o DL2. DR1. T a k e t h e f i r s t r i g h t edge R a c c e s s i b l e f r o m L and B and go t o DTO. DR2. Take t h e n e x t r i g h t edge R a c c e s s i b l e f r o m L and B. I f no s u c h r i g h t e d g e , go bac k t o DB2. DTO. L e t F a i l b o u n d = M i n [Xl*, X b , X r 2 ) . DT1. S e a r c h t h r o u g h t h o s e t o p e d g e s T t h a t s a t i s f y (a) T l i e s between t h e r i g h t edge R and t h e l e f t edge L (b) Y l < Y t 2 and Y t * < Y r . I f s u c h a t o p edge i s f o u n d f o r w h i c h (c) X t > F a i l b o u n d t h e n go b a c k t o DR2. DT2. O t h e r w i s e , f i n d 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 s a t i s f y i n g (a) and ( b ) , and c a l l t h i s v a l u e MAXT. Take t h e f i r s t s u c h t o p edge h a v i n g X t = MAXT. < The c o n d i t i o n X t < Minf X I2, X b , Xr2] now h o l d s , by v i r t u e o f DTO and DT1 ( c ) . > < A l s o , t h e r e c t a n g l e whose s i d e s a r e g i v e n by t h e c o o r d i n a t e s Y l , X b , Y r , Xt i s a m a x i m a l s u b r e c t a n g l e . > DT3, S e a r c h t h e MRT l i s t f o r an MRT w i t h s i d e s g i v e n by Y l , Xb., Y r , X t . I f s u c h an MRT i s f o u n d , c a l l i t MRT* and go t o DT5. Robot S i m u l a t i o n S t u d i e s 80 DT4. < No MRT w i t h s i d e s g i v e n by Y l , X b , Y r , Xt has been f o u n d i n t h e MRT l i s t . > P l a c e a new MRT w i t h s i d e s g i v e n by Y l , Xb, Y r , X t on t h e MRT l i s t . P l a c e a p o i n t e r on t h e l i s t o f p o i n t e r s a s s o c i a t e d w i t h t h e l e f t ( r e s p e c t i v e l y , b o t t o m , r i g h t , t o p ) s i d e s o f t h e MRT back t o t h e d e f i n i n g edge L ( r e s p e c t i v e l y , B , R, T) . S c a n t h e r e p r e s e n t a t i o n r i n g f o r a l l t o p e d g e s T# b e t w e e n T and L s a t i s f y i n g (a) , (b) , and Xt# = HA XT. F o r e a c h s u c h T# f o u n d , i f a n y , p l a c e a p o i n t e r b a c k t o T# cn t h e l i s t o f p o i n t e r s a s s o c i a t e d w i t h t h e t o p s i d e of t h e MET. Go b a c k t o DR2. DT5. P l a c e a p o i n t e r on t h e l i s t o f p o i n t e r s a s s o c i a t e d w i t h t h e l e f t ( r e s p e c t i v e l y , b o t t o m , r i g h t ) s i d e o f MRT* back t o t h e d e f i n i n g e d ge L ( r e s p e c t i v e l y , B,R) p r o v i d e d t h a t t h e p o i n t e r i s n o t a l r e a d y p r e s e n t ( f r o m p r e v i o u s e n t r i e s t o DT4 and D T 5 ) . Go b a c k t o DR2. D e f i n i t i o n s r e q u i r e d f o r DB1, DB2, DR1, DR2 : i ) G i v e n a l e f t edge I , t h e f i r s t b o t torn edge a c c e s s i b l e f r o m L i s t h e f i r s t b o t t o m edge B a f t e r L t h a t s a t i s f i e s (a) XI-1 < Xb (b) Y l1 < Yb2 . ( i i ) G i v e n a l e f t edge 1 and a b o t t o m edge B a c c e s s i b l e f r o m L , t h e n e x t b o t t o m edge a c c e s s i b l e f rom L i s t h e f i r s t b o t t o m edge B# a f t e r B t h a t s a t i s f i e s ( a ) , (b) a b o v e and Robot S i m u l a t i o n S t u d i e s 81 Xbfl < Xb . ( i i i ) G i v e n a l e f t edge L and a b o t t o m edge B a c c e s s i b l e f r o m L , t h e f i r s t r i g h t edge a c c e s s i b l e f r o m L and B i s t h e f i r s t r i g h t edge R a f t e r B t h a t s a t i s f i e s (c) Y l < Y r (d) X r * < Xb . ( i v ) G i v e n a l e f t edge L and a b o t t o m edge B a c c e s s i b l e f r o m L and a r i g h t edge R a c c e s s i b l e f r o m L and B, t h e n e x t r i g h t §^3§ a c c e s s i b l e f r o m 1 and B i s t h e f i r s t r i g h t edge R# a f t e r R t h a t s a t i s f i e s ( c ) , (d) a b o v e and Y b1 < Yr# < Yr , T e r m i n a t i o n and c o r r e c t n e s s o f p a r t 2 o f t h e a l g o r i t h m DECORP. 2 o r m i n a t i o n We o m i t t h e p r o o f t h a t e a c h o f t h e s t e p s C I , DL1, . . . DT5, c o n s i d e r e d i n d e p e n d e n t l y , t e r m i n a t e s . T e r m i n a t i o n c a n o n l y o c c u r a t s t e p DL2. C l e a r l y , t h e n , t h e a l g o r i t h m t e r m i n a t e s i f , h a v i n g once gone beyond DL2, c o n t r o l a l w a y s r e t u r n s t o DL2, s i n c e t h e number o f l e f t e d g e s i s f i n i t e . But DB2 i s t h e o n l y s t e p t h a t r e t u r n s c o n t r o l t o DL2. T h e r e f o r e , t e r m i n a t i o n o c c u r s i f , h a v i n g once gone b e y o n d DB2, c o n t r o l a l w a y s r e t u r n s t o DB2, b e c a u s e by t h e f i n i t e n e s s o f t h e number o f b o t t o m e d g e s c o n t r o l w i l l e v e n t u a l l y r e t u r n t o DL2. But DR2 i s t h e o n l y s t e p w h i c h r e t u r n s c o n t r o l t o DB2. T h e r e f o r e , t e r m i n a t i o n o c c u r s i f , h a v i n g once gone b e y o n d DR2, c o n t r o l a l w a y s r e t u r n s t o DR2, b e c a u s e by t h e f i n i t e n e s s o f t h e R o b o t S i m u l a t i o n S t u d i e s 82 number o f r i g h t e d g e s c o n t r o l w i l l e v e n t u a l l y r e t u r n t o DB2. B u t DT1, DT4, and DT5 a r e t h e o n l y s t e p s w h i c h r e t u r n c o n t r o l t o R 2 . DR1 and DR2 a r e t h e o n l y s t e p s w h i c h a l l o v i c o n t r o l t o p a s s b e y o n d DR2, and when t h a t happens i t p a s s e s t o DTO. So we must p r o v e t h a t i f c o n t r o l p a s s e s t o DTO t h e n i t p a s s e s t o DT1, DT4 , or DT5 ; b u t t h i s i s o b v i o u s f r o m i n s p e c t i o n of t h e a l g o r i t h m . F i n a l l y , we o b s e r v e t h a t , on e n t r y t o DECOMP, c o n t r o l p a s s e s i n t u r n t o D L 1 , DB1, DR1, and t h e n DTO so t h a t c o n t r o l does o n c e p a s s b e y o n d DL2, DB2, DR2. Q.E.D. C o r r e c t n e s s The a l g o r i t h m decomp_ c a n be p r o v e d c o r r e c t i n t h e s e n s e t h a t we c a n p r o v e t h e f o l l o w i n g two s t a t e m e n t s : 1) G i v e n any m a x i m a l s u b r e c t a n g l e t n r t * o f OBJA, an MRT r e p r e s e n t i n g m r t * o c c u r s i n t h e o u t p u t f r o m DECOMP. 2) E v e r y MRT p r o d u c e d by DECOMP r e p r e s e n t s some m a x i m a l s u b r e c t a n g l e o f OBJA. However, t h e d e t a i l s a r e o m i t t e d . Robot S i m u l a t i o n S t u d i e s 83 A p p e n d i x B L e t us c o n s i d e r j u s t what a p l a n i s . Note f i r s t t h a t i t w o u l d be p o s s i b l e t o g e t by w i t h no model o f t h e w o r l d and no p l a n s . A t e v e r y i n s t a n t R o b b i e h a s a c h o i c e of f o u r a c t i o n s : t a k e one s t e p f o r w a r d , t u r n l e f t , t u r n r i g h t , and t u r n t h r o u g h 180 d e g r e e s . On g i v i n g R o b b i e t h e command "go t c p o s i t i o n ( a , b ) " he c o u l d p r o c e e d by r a n d o m l y c h o o s i n g one o f h i s f o u r a c t i o n s a t e v e r y i n s t a n t and a t t e m p t i n g t o c a r r y i t o u t . Then a f t e r a s u f f i c i e n t l a p s e o f t i m e R o b b i e w o u l d have r e a c h e d t h e p o s i t i o n ( a , b ) , j u s t as t h e m y t h i c a l monkey a t t h e t y p e w r i t e r w o u l d e v e n t u a l l y t y p e a l l o f S h a k e s p e a r e ' s s o n n e t s . [ L i k e t r y i n g t o d r i v e f r o m U.B.C. t o t h e P.N.E. by making random t u r n s a t e v e r y i n t e r s e c t i o n . ] S e c o n d l y n o t e t h a t we c a n h ave p l a n s w i t h no m odel o f t h e w o r l d . A f t e r s u f f i c i e n t r e p e t i t i o n s o f t h e a c t i o n "go t o p o s i t i o n ( a , b ) " R o b b i e w o u l d be a b l e t o m emorize an e x a c t s e q u e n c e o f s t e p s and t u r n s t h a t w o u l d g e t him t c p o s i t i o n (a,b) i n a r e a s o n a b l y e f f i c i e n t manner ; however i f he o n c e d e v i a t e d f r o m t h e s e q u e n c e he w o u l d be l o s t , and h i s o n l y r e c o u r s e w o u l d be t o random s t e p s and t u r n s . K c n r a d L o r e n z o b s e r v e d e x a c t l y t h i s k i n d o f b e h a v i o u r i n t h e w a t e r - s h r e w [ L o , p . 1 0 7 - 1 0 9 ] . " . . . [ t h e w a t e r - s h r e w ] moves, i n s t r a n g e s u r r o u n d i n g s , o n l y s t e p by s t e p , w h i s k e r i n g r i g h t and l e f t a l l t h e t i m e and f o l l o w i n g a p a t h t h a t i s a n y t h i n g b u t s t r a i g h t . I t s c o u r s e i s d e t e r m i n e d by a h u n d r e d f o r t u i t o u s f a c t o r s when i t w a l k s t h a t way f o r t h e Bohot S i m u l a t i o n S t u d i e s 84 f i r s t time. But, a f t e r a few r e p e t i t i o n s , i t i s evident that the shrew r e c o g n i z e s the l o c a l i t y i n which i t f i n d s i t s e l f and that i t r e p e a t s , with the utmost e x a c t i t u d e , the movements which i t performed the previous time. ... [However,] any major a l t e r a t i o n i n the h a b i t u a l path threw i t i n t o complete c o n f u s i o n . " [ L i k e d r i v i n g from U.B.C. to the P.N .E. when given only the exact sequence of turns t o make, and no knowledge of the c i t y . ] T h i r d l y we have plans that i n v o l v e a model of the world i n t h e i r c o n s t r u c t i o n , statement, and ex e c u t i o n . For i n s t a n c e , the a c t i o n "go to p o s i t i o n (a,b)" might be decomposed i n t o the sub-a c t i o n s , assuming Robbie i s c u r r e n t l y i n MRT1, "move through MRT1 i n t o IRT1" "move through MRT3 i n t o IRT4" • • • ...<now Robbie i s i n the same MRT as the p o s i t i o n (a,b)> "go i n a s t r a i g h t l i n e to (a,b) " . The a c t u a l sequence of steps and turns that Robbie might take i n any one exe c u t i o n of t h i s plan i s not s p e c i f i e d ; so long as he "remembers" where he i s i n the o v e r a l l plan he can reach h i s d e s t i n a t i o n . [ L i k e d r i v i n g from O.B.C* to the P.N.E. given the i n s t r u c t i o n s : "Go east to Main ; go north on Main u n t i l you h i t Hastings, then go east f o r a few miles u n t i l you see the P.N.E. tower." However, on t h i s p a r t i c u l a r day Main i s blocked. Of course, you merely use another s t r e e t to go north on, and s t i l l c a r r y out your d e s i r e d a c t i o n - because you have a good model of the o r g a n i s a t i o n of Vancouver.] R o b o t S i m u l a t i o n S t u d i e s 85 I f we c o m p a r e t h e f i r s t and t h i r d c a s e s - no p l a n and no m o d e l , v e r s u s model p l u s p l a n i n v o l v i n g t h e model - we s e e t h a t one way o f v i e w i n g a w o r l d model i s a s a h e u r i s t i c t h a t we u s e t o e n a b l e us t o move a r o u n d o u r e n v i r o n m e n t more e f f i c i e n t l y , by a l l o w i n g us t o c o n s t r u c t and e x e c u t e p l a n s i n v o l v i n g t h e m o d e l . We may have i n v e n t e d t h e h e u r i s t i c o u r s e l v e s , o r , more l i k e l y , we may have been t a u g h t i t , o r we may p o s s e s s i t a s an i n s t i n c t ( e . g . i n f a n t s a r e a p p a r e n t l y b o r n w i t h t h e c o n c e p t s o f s o l i d i t y and p e r m a n e n c e • o f o b j e c t s , a c c o r d i n g t o Bower [ B o ] ) . What e l s e i s a w o r l d model ? I t i s a l s o a b a s i s f o r o r g a n i s i n g and i n t e r p r e t i n g o u r s e n s o r y i n p u t s f r o m o u r e n v i r o n m e n t . I n c o n c l u s i o n , t h e n , a w o r l d model i s a h e u r i s t i c d e v i c e f o r ( i ) o r g a n i s i n g o u r e x p e r i e n c e o f t h e e n v i r o n m e n t ( i i ) a l l o w i n g us t o c o n s t r u c t , s t a t e , and e x e c u t e p l a n s t o c a r r y o u t some a c t i o n o r d e s i r e i n an e f f i c i e n t manner. 

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