ETHER - A Parallel Problem Solving System

I. Introduction

ETHER is an attempt to form a ~ynthe~i~ of ideas about parallel programming with concept~ of pattern-directed invocation. There have been several researcher~ propo~ing parallel AI sy~tems [I, 2) u well as ~y~tem~ that make u~e of agendas and similar mechani~ms [3, 4) to get parallel-like behavior. This paper is concerned with the motivation and ba.\iC concepts of parallel pattern-directed invocation using ETH£R. Due to space limitations it is sketchy in many areas: a much more complete discussion can be found in [5~

2. Phxloseny of PIRnner-like Langu;~ses

In the early 1970\ there was great interest in developinB languages for Artificial Intelligence. Thi~ began with PLANNER [6) which was implemented as nitRO-PLANNER (7~ Experience with the ideas of PLANNER and earlier theorem proving systems led to the development of several more sophi~ticated systems at different center~: CONNIVER (8) at MIT, QA4 (9) at SRI, and POPLER (10) at Edinburgh. The general contribution these languages have made to programming are greater flexibility in representing and acc~sing data and the ability to gain access to procedures, not by their name, but by an indication of what they can do (so called pattern-dirtcttd inrocation) [6~ If there was a problem to be solved, the routine charged with solving it could instantiate a goal.

IGOAL (·lllj proble· h ... "ll

The implementation would then match the statement of the problem against statements of what each procedure could do, and procedures that are relevant would be invoked.

The ori,inal focus of PLANNER was the writing of programs that manife~ted Intelligence by the combined effect of l~ly coupled procedures. In nttRO.-PLANNER it was po~~ible to create independent units that said "If you want to accomplish the following result, try the following: .. ." The interpreter was charged with the task of combining this knowledge. It treated the theorems of ftiCitO-PlANNER as any standard language interpreter would treat subroutines. However, because nothing specified the order theorems were tried, nitRO-PlANNER programs followed a wasteful, undirected depth-first search. using chronological backtracking.

CONNIVER tned to amend this situation by putting the control structure in the hands of the user [8~ Programs had control over the generation and selection of problem solving strategies. Unfortunately, these new abilities destroyed much of the expressive ability inherent in the original ftiCRO-PI.flllll£11 modularity [Ill Our view is that the failure of nitRO-PLANNER programs to control their search was because program control !tad to be located at one point in tltt program at any given timr. This a.~sumption is implicit in the so-called Von Neumann machine model that underlies virtually all current hardware and software systems but has come under attack recently by M!Veral researchers. We introduce the notion of an activity and show how it can be u~ed to control reasoning in a highly parallel sy~tem. The context mechansm introduced in (9] is generalized to platforms all of which may be concurrently manipulated.

3. Pidgia·ETHER

Thi~ paper describes a language called ETHER that allows the user to construct problem ~olving sy~tems embodying the philo~ophy discu~~ed above. The analog of the PLANNER theorem is called in ETHER a ·~prite. Sprites have two principle parts, a pattern and a body. Once created, a sprite watches for an as~ertion to appear that matches its pattern, and, if this occurs, its body is executed. The body may contain commands to create new ~prite~ or commands to broadcast new a~sertions that other sprites may trigger on. This section dev.elops a subset of the ETHER language known as pidt~in-£THER. The ideas in pidgin-ETHER are quite similar to tho~e in [Ill To illustrate the difference between ETHER and ftltRO-PLANNER, consider the following PLANII£11-Jike consequent theorem:

lto-prove !BACHELOR ?XI !GOAl CUNnARRIEO ?Xll IGOAL cnALE ?Xlll

This says ·u you want to determine if X is a bachelor try to show that he is both male and unmarried." A nitRO-PLANNER interpreter would first try all pos~ible ways of showing that x is unmarried, and then if it achieves success, all possible ways of showing X is male. The analog to this in pidgin-ETHER might be written:

<when ICOAl !BACHELOR oxll

lbroadcas I IGOAL CUNnARRIEO xlll

lbroadcaat IGOAL lnALE xlll

<when& C CUNnARRIEO xl

CftALE xll

(broadcast !BACHELOR xllll

This example makes use of explicit goal assertions [II. 12) instead of primitive consequent rules. When this sprite receives a matching assertion (such as "IGOAL FREOl") simultaneously three things occur: a goal assertion is broadcast that causes work to begin on determining whether x is unmarried, a goal assertion is broadcast that causes the system to begin work on determining whether · is male, and a new sprite is created that wait~ for the~ &sertion~ to appear in the databa.·e. When (and if) they finally appear the BACHELOR a.·sertion is broadcast satisfying the goal.

In the ETHER example both goal$ are worked on simultan«Jusly. Each of the GOAL &$ertions (requests to work on the goals) may each be picked up by several sprites serving & consequent theorems and in turn may themselves cause several subgoals to be pursued concurrently.

4. Activities and Stifle

This example h& one problem. When a goal h& been solved, computation attempting to achieve it will not stop. For example, even if FRED has been shown to be a BACHELOR, consequent sprites working on the problem of determining if FRED is a BACHELOR will continue doing so. It is desirable to be able to stop this additional processing so that system resources can be reclaimed.

To allow this kind of behavior we will introduce the concepts of activity and stifle to the pidgin-t:THER so far described. An activity can be thought of & a locus of control with some specific purpose. When the work being carried out by an activity is found to be no longer necessary the activity is stifled. This causes all computation involving sprites that are part of this activity to cease. An activity may be created to achieve some goal. If the goal h& been achieved then the program should stifle this activity.

To illustrate the use of activities is redone the above example using them. Activities are initiated by giving broadcast a second argument of the name of the new activity. If a sprite receives this broadca.·t, newly created sprites are placed in the new activity. Suppo~ we wish to work on the goal of «BACHELOR FREDI. The following broadcast is done with GOAL33 being the name of the activity created to work on this goal.

Cbroadcas t I GOAL !BACHELOR FRED I I COAL331

There may be a number of different ways to accomplish a goal (each by a different consequent sprite). One way, & w& done above, is to demomtrate FRED is both nALE and UNnARRIED.

Because this is one of perhaps many ways to accomplish a goal, its investigation should occur in a distinct activity.

lwhen !GOAL I BACHELOR ··I I

llet Csubgoal I now-act I vi tyll

!broadcast !COAL IUNnARRIED ·II subgoall

lbroadcas t I COAL cnALE · I I subgoall

I when& I !UNMARRIED ·I

CnALE ·I I

!broaden t !BACHELOR · I I I

Cwhen !BACHELOR ·I

Cbroadcas t CST IFLE subgoal II II I

The code given is like the previous eKample with some additions to show the use of activities. The function now-activit\! creates a new activity. The name of this activity is returned and becomes the value of subial. All work begun by this sprite occurs in this activity. The ast sprite occuring in its body watches for !BACHELOR FREDI to be broadca.·t, indicating successful completion. If this is ever broadcast, the sprite broadca.·ts a special a.·sertion instructin~ the system to Mifle the subgoal activity and any activities 11 might have created. A stifled activity ceases to work on the goal. It does not matter how the goal was finally achieved for the stifling to occur, only that it was achieved.

If the same goal &sertion is broadcast twice with different activity markers then only one new activity rather than two will be created. This new activity will be a subactivity of both parents. Thus, if there are two different goals that create a common subgoal, the work on this subgoal will not be duplicated.

S. Platforms and Opponents

Planner-like languages frequently need to create little worlds or contexts inside the machine in which to reason. Contexts are usually defined so that only one is visible to the problem solver at a time. A parallel problem solving system must not contain such a restriction because different activities may be set up to concurrently reason about several incompatible world models. We have generalized the context concept to the notion of a platform. All platforms are accessible to all sprites at all times. We (S] have found several uses for many concurrently accessible platforms.

Gelernter, in his cl&sic geometry theorem proving program (13], introduced the concept of a goal filter. His program worked by using strict backward chaining from the theorem. Before attempting to work on a subtheorem it would check a diagrammatic representation of the subtheorem to see if the subtheorem wa.· consistent. If it w& not, the goal was immediately pruned. The concept of checking a subgoal for plausibility is an important one in maintaining coherency in the problem solving process. In Gelernter's progfam the test was e&y to make and would be guaranteed to terminate with an answer in a short span of time. In many problem solving situations goal filters can make u~e of the full capabilities of the problem solver and may not be guaranteed to terminate. The use of goal filters ~till may be justified because of the de~irability of cutting off exponentially growing trees of usele~s backward chaining.

One common mode of rea.·oning that people use to filter goals is to assume the object of a goal is true and then seeing if there is an anomaly. For example in a geometry theorem proving program we may have a goal of demonstrating satisfiablilty of the statement "Line AB is longer than line AC' in the following:

(llneABI

lllneBCI

Cline A Cl

Cr lcJhl-angle A I Cl

We create an activity and broadca.·t in this activity:

Cgo·l !greater (llneABI CiineACII

As in the previous examples this will cause consequent processing to happen on this platform attempting to prove this goal. Sprites doing consequent processing will not realize that the goal is unattainable though this is easily apparent to humans. Consequent reasoning sprites will implement backward chaining from this unattainable subgoal.

A method people use for seeing this is by determining the obvious consequents of the proposition that line AB is longer than line AC and seeing that an anomaly arises.

In ETHER, data assertions are grouped in specific platforms. We create a new platform that inherits from the platform containing the description of the figure and in it we broadcast:

C9reater (line A Bl I line A Cl I

Many antecedent sprites are created to allow the system to determine the implications of this assumption. We also instantiate for this platform sprites that can detect contradictions. In this particular example, the &sumption h& one e&ily seen consequent, that angle ACB is greater than angle ABC. This implies angle ACB > 90 degrees, and that triangle ADC h& internal angles that sum to more than 180 degrees, an anomaly. A sprite watches for the occurrence of anomalies and then stifles the activity attempting to do consequent rea.-oning on this goal.

We concurrently do consequent processing attempting to prove the goal and antecedent processing to determine if the goal is not realizable. The activity attempting to achieve the goal is known as a proponent. The activity in which antecedent processing is being done on the goal to determine if anomalies exist is an opponent. If the goal is achieved, the result is broadcast and both the opponent and proponent activities are stifled. If the opponent succeeds in finding an anomaly, both activities are stifled.

The inherent parallelism of ETHER is necessary to allow use of opponent platforms. In a sequential problem solving system, the problem solver must choose to do one or the other first. It cannot allow opponent processing that is not guaranteed to terminate in a reasonable amount of time. Goal filters can be implemented in our scheme by creating a platform that executes the task of the goal filter, stifling the goal proponent if the filter is successful.

The full power of the problem ~olver can be brought to bear on the ta.·k of filtering goal~.

The inheritance mechanism is such that assertions appearing in the parent of a hypothesis platform rirtual/y appear in the hypothesis platform itself. The program may inherit antecedent sprites from a parent to a child platform. When this is done, the only new a.·sertion~ that get generated and placed in the hypothesis platform are only thNe that depend on the as~rtions broadcast in this hypothe~is platform. Thus the creation of an opponent platform is relatively inexpensive.

6. Further Ideas

The ETHER language is much more extensive than the kernel described here. We brieny summarize some of the other features that are discussed in (5~

As A parallel langua~e The semantic~ of the language have been carefully designe so that it is implementable on highly parallel hardware without introducing bottleneck$ or the po~~ibility of deadlock caused by the use of synchroniution primitive~. We believe that many of the choices made in this regard are al~o the right choices from the point of view of language design for modular programming; the language makes it ea.·y to design program~ devoid of the timing errors that plague most parallel system~.

Processing power. The concept of an agenda has been proposed for incorporating rnource-limitrd computation in AI systems. We feel this is too low level a concept because the individual parts of the system must worry about their own scheduling. Imagine how much harder it would be to write programs for a time-sharing ~y~tem if the individual programs had to schedule each time quantum for themselve~. In ETHER the individual activities are tfuly parallel. To incorporate resource-limited computation we introduce the notion of procNJing por.·er. If some activites seem to be more likely to achieve their purposes than others they are given a larger share of processing power. The u~r is given a set of primitives in which to build in heuristic knowledge to improve the performance of the program.

Objects and coreference. Most PLANNER-like langua~es allow variables to appear in goals. ETHER contains a generalization of the notion of an anonymous object. The program can place a.·sertions on a platform causing the object to be coreferential with another object on that platform. We show that variables can be replaced with the~ objects rl'sulting in solutions to many problems that are much more tightly controlll'd than a solution using variables. Objects also have important applications in planning.

Manipulative inheritance. The inheritance mechanism discussed for platforms above will inherit all assertions from a parent to a child. While this is valuable for the creation of opponents it is not generally useful in planning. Planning situations usually require the ability to make certain a.·sertions invisible through inheritance links. For eKBmple, if a block A is taken off of a block 8 in a hypothetical situation we would like the a.·~rtion ION A 8> to be invisible in the hypothesis' platform even though it is present in the hi~her platform. We employ the use of inheritance filters and justiJications in our solution to the frame problem. The user may tag assertions with markers and allow the system to automatically compute dependency information for newly created assertions. A platform inheritance link can specify a filter that indicates the ci~Ss of a.·sertions that can be "seen" through the inheritance link.

Virtual Collections of Assertions. A common complaint of pattern-directed invocation systems is that they are too inefficient. We would like to supply a facility that allows the u~r to interface efficient Lisp code to the ETHER system in a transparent manner, i.e. from the point of view of the ETHER program this efficient subprogram loob a.· if it is implemented in sprites. For each virtual collection the program must specify two items: the assertions that it would like to know about if they are asserted in the database, and the kinds of assertions for which it can decide virtual presence in the databa.·e. We envision a facility like this being used to tie together many relatively large, special purpose, programs so that they can interact in a useful fashion with one another.

7. Conclusions

ETHER is a language that allows arbitrarily much processing to occur in parallel. We believe this feature allows programs to maintain modularity and independence of individual methods while still allowing programs to carefully control their search. We have developed two kinds of generalized control structures. In ETHER it is possible to run many methods in parallel and arrange that computation that becomes unnecessary to be stined. ETHER makes possible a generalization of the concept of a goal filter in which the filtering computation runs in parallel with the the attempted attainment of the goal. ETHER code is clear and simple and counters the commonly held belief that parallel programs are hard to design and understand.

ETHER has been implemented by the author a.· part of his rna.·ters thesis research. I am currently improving the implementation and modifying it for use on the MIT Lisp Machine.