Procedural Embedding of knowledge in Planner
(1971)

Since the l a s t I JCAI , the PLANNER problem s o l v i n g fo rma l i sm has con t i nued to deve lop . Our ep ls temo lgy f o r the f ounda t i ons f o r problem s o l v i n g has been ex tended . An overv iew of the f o rma l i sm Is g iven from an I n f o r m a t i o n p rocess ing v i e w p o i n t . A s imp le example Is e x p l a i n e d us ing snapshots of the s t a t e of the problem s o l v i n g as the example I s worked, f i n a l l y , c u r r e n t a p p l i c a t i o n s f o r the fo rma l i sm are I i s ted . 1 . The S t r u c t u r a l Foundat ions o f Problem S o l v i n g We would l i k e to develop a f o u n d a t i o n f o r problem s o l v i n g analogous In some ways to the c u r r e n t l y e x i s t i n g f ounda t i ons f o r mathemat ics . Thus we need to analyze the s t r u c t u r e of f o u n d a t i o n s f o r mathemat ics . A f o u n d a t i o n f o r mathematics must p rov ide a d e f i n i t i o n a l f o rma l i sm In which mathemat ica l o b j e c t s can be d e f i n e d and t h e i r e x i s t e n c e p roved . For example set t heo ry as a f o u n d a t i o n p rov ides t h a t o b j e c t s must be b u i l t out o f s e t s . Then the re must be a deduc t i ve f o r m a l i s m In which fundamental t r u t h s can be s t a t e d and the means p rov ided to deduce a d d i t i o n a l t r u t h s f rom those a l r e a d y e s t a b l i s h e d . Cur rent mathemat ica l f ounda t i ons such as set theo ry seem q u i t e n a t u r a l and adequate f o r the vas t body o f c l a s s i c a l mathemat ics . The o b j e c t s and reason ing of most mathemat ica l domains such as a n a l y s i s and a lgebra can be e a s i l y founded on set t h e o r y . The e x i s t e n c e o f c e r t a i n a s t r o n o m i c a l l y l a r g e c a r d i n a l s poses some problems f o r set t h e o r e t i c f o u n d a t i o n s . However, the problems posed seem to be of p r a c t i c a l Importance on l y t o c e r t a i n ca tego ry t h e o r i s t s . Foundat ions o f mathemat ics have devoted a g rea t deal o f a t t e n t i o n to the problems o f c o n s i s t e n c y and comple teness. The problem of cons i s t ency Is Impor tant s i nce I f the f ounda t i ons are i n c o n s i s t e n t then any fo rmu la whatsoever may be deduced thus t r i v i a l i z i n g the f o u n d a t i o n s . Semantics f o r f ounda t i ons o f mathemat ics are d e f i n e d model 167 t h e o r e t i c a l l y In terms o f the n o t i o n o f s a t i s f i a b i l i t y . The problem o f completeness is t h a t , f o r a f o u n d a t i o n of mathematics to be I n t u i t i v e l y s a t i s f a c t o r y a l l the t r u e fo rmu las shou ld be proveab le s ince a f o u n d a t i o n mathemat ics alms to be a theory of mathemat ica l t r u t h . S i m i l a r fundamental ques t i ons must be faced by a f o u n d a t i o n f o r problem s o l v i n g . However t he re are some impor tant d i f f e r e n c e s s ince a f o u n d a t i o n of problem s o l v i n g alms more to be a theory of a c t i o n s and purposes than a theory of mathemat ica l t r u t h . A f o u n d a t i o n f o r problem s o l v i n g must s p e c i f y a g o a l o r l e n t e d f o rma l i sm In which problems can be s t a t e d . Fur thermore the re must be a f o rma l i sm f o r s p e c i f y i n g the a l l o w a b l e methods o f s o l u t i o n of p rob lems. As p a r t o f the d e f i n i t i o n o f the f o r m a l i s m s , the f o l l o w i n g elements must be d e f i n e d : the data s t r u c t u r e , the c o n t r o l s t r u c t u r e , and the p r i m i t i v e p rocedures . The problem of what are a l l o w a b l e data s t r u c t u r e s f o r f a c t s about the wo r l d Immediate ly a r i s e s . Being a theory of a c t i o n s , a f o u n d a t i o n f o r problem s o l v i n g must c o n f r o n t the problem of change: How can account be taken of the changing s i t u a t i o n In the wor ld? In o rder f o r the re to be problem s o l v i n g , the re must be a problem s o l v e r . A f o u n d a t i o n f o r problem s o l v i n g must cons ide r how much knowledge and what k ind of knowledge problem s o l v e r s can have about themse lves . In c o n t r a s t to the f o u n d a t i o n o f mathemat ics , the semant ics f o r a f o u n d a t i o n f o r problem s o l v i n g should be d e f i n e d In terms of p r o p e r t i e s of p rocedures . We would l i k e to see mathemat ica l I n v e s t i g a t i o n s on the adequacy of the f o u n d a t i o n s f o r problem s o l v i n g p rov ided by PLANNER. In chap te r C of the d i s s e r t a t i o n , we have made the beg inn ings of one k ind of such an I n v e s t i g a t i o n . To be more s p e c i f i c a f o u n d a t i o n f o r problem s o l v i n g must concern I t s e l f w i t h the f o l l o w i n g complex o f t o p i c s . PROCEDURAL EMBEDDING: How can " r e a l w o r l d " knowledge be e f f e c t i v e l y embedded In p rocedures . What are good ways to express problem s o l u t i o n methods and how can p lans f o r the s o l u t i o n of problems be fo rmu la ted? GENERALIZED COMPILATION: What are good methods f o r t r a n s f o r m i n g h igh l e v e l g o a l o r l e n t e d language in to s p e c i f i c e f f i c i e n t a l g o r i t h m s .