Some Considerations Concerning The Problem Base Of Purposeful Systems

Introduction

The notion of purposeful system seems to be a fundamental one in the fi­ eld of Machine Intelligence. Consider a certa in integrated model structure refle­ cting some pertinent properties of the physical world. One or more substructu­ res are singled out representing active subjects. Some fixed configuration of the integrated structure is called a state. The structure can change along with time, so we must deal with a set of states. An initial state is fixed. In some or other way the goal state is characterized. Cer­ tain states are prohibited. The problem is to plan the behaviour of the active subjects, and then to execute the plan bringing the whole system in one of the goal states Gvoiding the prohibited ones and satisfying the given restrictione on time and resourses. The situation is re­ ally more complicated: we postulate the incomplete knowledge about the system. It results in so to sny spontaneous chan­ ges of its state which cannot be predic­ ted by the planning system. Then, not all act ive subjects are liable to our control. Some of them may represent natural pro­ cesses (seasonal changes during the year, eruption of volcanoes, snow-slips, etc.) or represent subjects being under control of some other system (or systems). At last, it is pra~atically more useful to investigate the behaviour of the large system. In this case we must abandon the hopes to obtain the true optimal solution. We are going to study an :lrtifi ci ­ al system represented in the form of co­ mputer software which is able to act pur ­ posefully in the foregoi~ sense, and ex­ ternal operational mode of which resem­ bles the behaviour patterns of natural intelligence. The artificial system will not copy its neurophysiological proces­ ses; though some undoubted facts or em­ pirically useful hypotheses obtained by the students of the living brain can be profitably taken into account duri ng si­ mulation. The creator of computer aodel has a possibility to organize its data base and operational sections in accordance with peculiarities of hard- and software at his disposal. It seems more appropriate to use the term ''Machine In­ telligence" instead of "Artificial Intel­ ligence" in this case.

Apparently, the everyday reasoning problems will suit us all right at the beginning stage of the investigat i on.

There is no doubt that success i n development of purposeful systems rather generally defined above will strongly stimulate the growth of effectiveness i n many applications: natural langua~e i n­ teraction with computer, CAI, control systems for integrated autonomous robots , models of large enterprises, etc.

Known approaches

The development of purposeful sys­ tems (PS) attracts attention of resear­ chers for a lo~ time. The term "General Problem Solver" was coined by Newell, Shaw, and Simon in 1957 [2] , and since then ideas layed in its foundat i on were refind, improved durin~ the decade and used in many implementations. J.McCarthy (1959) proposed developing of un iversal progr~ms with common sense having the flexible strate~ which can be effecti­ vely improved duri~ the interaction wi th human creator (Advice Taker). A number of imfortant considerations c ~n be f ound i n [3 · A unique approach to the oroblem un­ der discussion was evolved and deployed during efforts headed by U.Klykov, D.Po­ spelov and their colle~ues; the results obtained can be found in [4].

Starting from 1969 the progress i n the art of purposeful systems design had been tied with the development of special prograaaing langu~es for AI research

(C.Hewitt, [5] ). The power of this app­ roach had been convincing~ demonstrated by T.Winograd [6] · The use of pure me­ chanical theorem proving technique in PS­ area is handicapped with serious practi­ cal limitations. The successful combina­ tion of theorem proving with the philoso­ phy of GPS [1] along with many important mechanisms such as generalization of plans was evolved in SRI [7-9]. Among the most interesting recent~ issued papers is that of E.Sacerdoti [101. A series of important results was obtained by the re­ search group under R.F.Simmons in the Uni­ versity of Texas. It includes the inves­ tigation carried out by G.Hendrix which resulted in recommendations concerning the modelling of simultaneous interactive processes including the processes with continuous changes of model parameters.

The works mentioned above appreci­ ably influenced the shaping of our appro­ ach.

The Problem Description Lapsua5e

It seems reasonable to express all useful findings in PS-area in the form of speci al PS-oriented language. Apparent~ it is the most effective way to generali­ ty. Next follows the discussion of the main premises for problea base construc­ tion of such a language.

Information about the physical world naturally falls into two categories: des­ criptive and operational. The former de­ clares names, properties and relations between objects specifying the model with names of properties and relations being predicates and that of objects--constants and variables. Operational part of the system changes a model. It results in de­ letion of some clauses and addition of some others. Situation can become even more complicated: the system can be acted upon by several operators concurrently; some can effect in gradual changes of va­ lues for various numeric objects. A seri­ es of operators can be under the control of planning systemt others can be provoked by uncontrollable ractors or be initiated by systems-competitors. Besides operators can have complex causative bonds.

All this aroses serious doubts in the practicability of the first order predi­ cate calculus for description of such sy­ stems. Moreover, when the transition is performed from the semantic net represen­ tation to the uniform set of clauses be­ ing the problem base for resolution-type theorem provers, one can notice that some important information fades away. It is the non-homogeneous structure of semantic net which is associated with its objects. This organisation of data naturally pro­ vides straightforward acquisition of re­ levant sentences tied in contexts, disco­ vering links between various contexts and the goal directed transformation of their content. The greater practicability of se­ mantic nets was also emphasized earlier by R.F.Simmons (12].

It seems reasonable to abandon the uniformity and formal elegance of logic in behalf of flexible universal program­ ming language. This language must allow the manipulation of complex data structu­ res and provide the convenient facilities for procedural embedding of semantics in­ herent in the processes being simulated. Trying to draw the expressive means of the language to those (hypothetically) used by humans one ought to work out uni­ form, or at least similar, format for de­ scriptive and operational information. At last the fundamental relations, such as sub-, superconcepts, cause-effect and time must simply and naturally be inter­ preted by the system.

Experimental heuristics oriented la­ nguage for purposeful systems simulation (HEOPS) was decided to embed in LISP 1.5 paying the tribute to its universalityi laconisa and complex data structures a - lowed. The concept classes hierarchy and time synchronization for processes in HEOPS is borrowed substantially from SIMULA [13) ·

The System's Problem Base

The problem base of the HEOPS inclu­ des two basic parts: declarative section and operational space. Declarative sec­ tion includes the definitions of all con­ cepts and relations currently existing in the system. In the operational space is "builded" the initial situation for a gi­ ven problem. Its solution coprises seve­ ral transformations through the applica­ tion of the sole operation: "instantiate" one or other definition from the declara­ tive section. The boundary between the two sections is rather conventional: it is allowed to transfer non-instantiated definitions from declarative to operati­ onal part; one can imagine the inverse too: synthesis of some new definition in the operational space which is followed by its transfer to the declarative secti­ on for further use.

.Two types of objects are liable to declaration: relations and concepts.

Declaration of Relations

It is instructive to think about re­ lations as arcs of semantic net. However the number of their arguments not neces­ sary equals to two. Extra arguments play the role of relation modifiers. Thus, let A and B be two nodes. The relation (DIS­ TANCE A B X) means: "The distance is de­ fined between objects designated by the names A and B, and this distance equals to X". It is convenient in computer to gather all relations of the semantic net having identical first arguments and pla­ ce them on the property list of the cor­ responding node, deleting its name from the explicit forms of the relations.

When the declaration of some relati­ on is interpreted the relevant informati­ on defining the semantics of the given relation is put on the property li~+. of the choosen relation name in the form of traditional property-value pairs:

• The number and also the necessary properties tor arguments of the relation are specified. In the foregoing example A and B should be physical bodies, and X-a number.
• The pointer to the "superrelation" is inserted. Thus, the predicate SAY can h~ve as its superrelation the predicate COMMUNICATE.
• The pointer may be inserted to the list of "subrelations" currently existing in the system. The predicate COMMUNICATE thus can contain in its subrelations' list: SAY, WRITE, SUGGEST, HINT, etc.

Declaration of Concepts

Concepts are the main object type in the HEOPS. Declared are classes of con­ cepts. Each class gets its name, for exa­ mple, ROOM, MONKEY, GET, APPROACH, etc.

In class declaration generallY are included:

1. Semantic net of applicability (application pattern), probably, with poi­ nters to super- and subconcepts.
2. Activation pattern.

3. Operational section.

3.1 Delete-list.

3.2 Add-list.

3.3 Recomputation formulae.

3.4 Notice-list.

1. Passivation pattern.
2. Suppression pattern.

Such classes usually represent a pro­ cess. The class wl th sections 2--4 absent is called assertional and represents sim­ ple or compound entity--the part of sema­ ntic net with some set of nodes and rela­ tions between them.

The nodes used in declarations fall into one of the following categories:

• P: - free node of simple type: during instantiation can be replaced with own, terminal, or classified node.
• G: - free node of generic type; not disappear when instantiated, but produces moreover the finite set of nodes (P:-type) each of which can be further instantiated.
• T: - te~nal node; its semantics comprises solely its name, it cannot have &Dy other properties and cannot be further instantiated.
• C: - classified node, i.e. the node baviDg its class declaration in the ·ys­ tea. When instantiated requires pattern utching upon existing net.

Inatantiation of Concepts

The first argument of the aforemen­ tioned operation of instantiation is the name of concept declared (dynamically) earlier. The second argument is the list of instantiation parameters. Thus, the concept MONKEY can obtain after i nstanti ­ ation the fixed name, specific location in some room; it can have some object in its hands. It can even start moving at once if in its class declaration the ap­ propriate operational section is present .

During instantiation the application· pattern of the given concept is matched upon the current configuration of the ope­ rational space: explicitly--through ins­ tantiation parameters and implici tly­ upon the nodes and arcs of the currently existing semantic net. The relevant i n­ formation is choosen in this case by the concept body itself. Instantiation resu­ lts in the new state of the operational space with new concept "illlplanted" there . Otherwise inapplicability is indicated. The more interesting mode of operation results in the sequence of recursive ca­ lls for instantiation of some other con­ cepts in order to eliminate the discrepa­ ncies found. This process is guided main­ ly by special pointers extant in declara­ tions and relating some relations with concepts responsible for their ori ginat i­ on, support, or removal.

Operational information is reflected in the proposed problem base in two ways: in ready to use procedural fora as opera­ tional section (3) of concept class dec­ laration, and as a so called possibility hint. In the later case in the applicabi­ lity pattern (1), add-list (3.2) of class declaration, or somewhere in the semanti c net of the operational space are inserted nodes--reflections of certain concepts-­ processes. Thus the node MONKEY can be linked with possibility node MOVE, proba­ bly with some restrictions on the extent of mobility (say, remaining on some solid surface). This aeans that the MONKEY c a n move. In order for it really to move the concept corresponding to thi s node of the net must be inatant i ated us ing the declaration of MOVE.

Instantiation can be done par tially : i.e. implanted concept can retain some of its free nodes. As for example, during the process of getting bananas in the well known AI problem, it may turn out that the distance between the monkey and bana­ nas can be diminished if the monkey will be standing on s o m e t h i n g rising above the floor. The node designating this "something" reaaiD& free until i t even­ tually becomes instantiated to, say, a box if the later is available.

Time dependency

Time and cause-effect bonds deserve special discussion. In HEOPS it i s plan­ ned to use the sequence list akin to that introduced in SIMULA [131. Recomputation formulae (3.3) are used ln class declara­ tions in order to fix the crucial moments ot time. The notice-list (3.4) contains the pointers to the instantiated concept s in the operational space which must be activated after fulfilment of certain con­ ditions. The provision of special machi­ nery for process interception at arbitra­ ry moment with return to the arbitrary continuation point is not planned. Inste­ ad the processing of concepts (also qua­ siparallel processes) is arranged so that exit and reentrance are done in precpeci­ fied point.s; special provisions must be used to retain the contexts' value.

Super- and Subconcept Relations

During the instantiation process the need in certain more general relations can arise. Each instantiated node in the semantic net has a pointer to its class name. For example, the specific monkey named Cheetah remains to be a monkey ha­ ving all its properties. A MONKEY is a subconcept of ANIMAL, and the fact that any animal needs food need not be repea­ ted for all subconcepts of the concept ANIMAL. An appeal to more general conce­ pts proved useful in some situation can be fixed in instantiated subconcept as explicit addition to the semantic net.

Conclusion

Organizational principles of the HEOPS language problem base for simulati­ on of purposeful systems, informally dis­ cussed in this paper, will be specified more accurately in future. Under current consideration are also the principles of its computer implementation. In particu­ lar, we are faced with working out the efficient methods for contexts· bookkee­ ping to hold the nodes' values after in­ stantiation and preserving the convenient access to the hierarchy of concepts. One of the crucial points in future investi­ gations will be the realization of effec­ tive bootstrapping procedure for the sys­ tem both in descriptive and operational aspects. This process can be regarded as system's learning in one of the most im­ portant mode: algorithmic evolution.

The simulation of the system is be­ ing done on BESM-6 computer with DIAPACK OS. The host language is LISP 1.5 ~4,15) which is run under TELELISP monitor sys­ tem implemented in the Institute of Mathe­ matics, Siberian Br. Acad. Sci. USSR, pro­ vided with archives and text editor which make it possible to interact with the ma­ chine from distant terminal.