The Use of Parallelism to Implement a Heuristic Search

I. Introduction

Many AI sy~tem~ that perform a "heuristic search" (i.e. they can be thought of as searching some space of pos~ibilities for an answer) are based upon one or both of two programming techniques known ~ constraint propagation and hypothniu-and-test.

In a ~)'~tern ba~ed on con~traint propagation, internal data structure~ represent (implicitly or eKplicitly) potentially acceptable point~ in the search ~pace. Computation proceed~ in narrowing down these po~~ibilitie~ by employing knowledge of the domain in the structure of the computation. There i~ not enough space here to properly introduce the concept~ involved in constraint propagation. The reader is referred to some systems described in the literature [I, II) for an introduction. One point we wish to empha.<ize about pure comtraint propagation i~ that at any time the internal data ~tructure~ will be con~i~tent with any solution to the problem. Thu~. if more than one wlution is po~~ible, pure propagation of con~traints will be unable to select only one of them. Further, even if a unique solution eKists, a con~traint propagation sy~tem may not be able to find it.

The hypothesize-and-te~t methodology allow~ the program to make a.s~umptions that narrow the ~ize of the search space; there is no guarantee that the a~~umption i~ con~istent with any ~olution to the problem. The program continue~ to make hypotheses until a solution is located. or it ha~ been determined that no ~olution is possible with the current set of a~~umption~. There is no requirement that any hypothesi~ be correct and so mechanisms must be available that prevent commitment to any hypothesis until it has been demonstrated to be acceptable. The most commonly available mechanism i~ known a.< backtroc/r.ing. Backtracking allows the program to return to an environment that would eKist had that a.<~umption not been made.

A~ long a~ the search ~pace i~ enumerable (a very weak a.<sumption)> hypothe~ize - and - te~t can be easily seen to be logically more powerful. If there are several consi~tent solutions, a pure constraint propagation system has no way to establish preference for one of them. Even if only one wlution i~ possible a constraint propagation system will not necessarily find it; this will be demonstrated later by how to guide the ~earch proce~~ to gain efficiency. In this ~tudy, concurrency is nece~sary to make use of thi~ meta-level knowledge.

2. The problem

We are given three mings of letters, e.g. "ooNI\LO", "OERun·, and "p,onrR 1" that repre~ent integers when substitutions of digits are made for each of the letters. There is at lea.·t one pNsible a.·signment of digit~ for letters so that the numbers represented by the first two ("noNI\LD" and "Gr:R.un"), when added, yield the number represented by the third ("RORER r"). Any one of the~e B!'signment~ i~ a ~olution. In the problems we will be looking at, each will contain exactly ten letter~. A wlution con~ist~ or a mapping from these ten letters onto the ten digits 0 through 9.

3. A Constraint Propagation Solution

In our construction of the constraint network we will use the actor model of computation .. We find it a very natural formali~m for building these sorts of systems. In this formalism nodes of the network are implemented as actors. Constr1int propagation between nodes is implemented by sending of mes.'llges containing the new constraints to the no~e being constrained. For our cryptarithmetic problem solver we have three kinds of nodes: letters, digits, and columns. They are arranged as shown:

COLUMN NOOf"S

LETTER rJOOf)

DIGIT

,.JoofS

Arcs in the diagram indicate flow of constraints. Thus column nodes can constrain their left and right neighbor columns and certain letter nodes (the one~ representing letters contained within the column). letter nodes can constrain digit nodes and column nodes that contain their respective letters. Digit nodes can constrain letter nodes. In the initial configuration, before constraint propagation begins, we store at each letter node 1 list or po~sible digits that contains all ten digits. SimilarlY., each digit node contaim a "possible letter~ list" containing all ten letters. We will give a short description of what each node has to do when it receives a message informing it of a new constraint.

Columns. A column can receive message~ informing it of new constraints on letters it contains and on possible values for its carry-in and carry-out. If a column node receives any such messages, it computes possible new con~traint~ on its letters, carry-in, and carry-out. If any one of these has no possible values a CON{RI\OIC fiON is asserted. When a CONlRI\DICTION is asserted the code implementing hypothesize-and-test i~ invoked to take an appropriate act ion. New constraints on letters are sent to the respective letter nodes. New constraints on carry-in and carry-out are sent to the right and left neighbor columns respectively.

Letters. letters receive messages that" indicate subsets of the digits

0 through 9 that they can possibly be. If they learn of digits that they cannot be, node~ repre~enting those digit~ are ~ent me~~ages. Also, t'ach column that contains the letter receives a new message informing it or the new restrictions on the valul' or the particular letter. If the ~l't of p(mible digits become~ .null, a CONTRI\I)JCliON i~ asserted.

Digits. These receive ml'~sages from letter nodes indicating that they are or are not the respective letter. If the set or possible letters is reduced to a singleton, a message is sent to the particular letter. If the set or po~sible letters is reductd to null, a CONTRI\I)JCliON is &serted.

We can observe some things about the ability of this system to satisfactorily cll'rive a unique solution. Fint, if there is more than one pMsibleo solution it will not find any of them. Since the letter and digit assignments of each possible ~olution are certainly possible a~~ignment~. they will appear on the po~sibility lish attached to each node. Even if there is only one po~~ible solution (or no possible ~olutions) the systl'm may not find it (or discover that no ~olution~ exi~t). For example, the "t>ONUO" + "OJ:RI\LD' · and "RonF.RT" puzzle ha~ only one ~olution: the constraint network described will quie~ce before finding it. Neverthell'~~. the knowledge can be ~aid to be "prl'~ent" in t.he network: if the nodes of the network are in~tantiatl'd with an assignment or leters to digits, the network will as~ert a CONTR "OICTION iff the as~ignment i~ not a ~olution. Our constraint network, thl'n. neeod~ the ability to make a~~umptions and te~t them if it i~ to be able to ~olve these puzzle~.

4. Hypothesize and Test in Ether

The constraint network and hypothesize-and-te~t methodologie~ were writtl'n in the Ether language (7, H We will only give enough detail~ about the implementation to ~upport the ensuing di~cu~~ion. The interested reader is referreod to (9) for a more detailed discu~~ion of the implementation.

The primitive operations of the Ether languages are ba~ed around the notion of an assrrtion rather than message pas~ing. Rather than coding in a me~~ageo pa.·~ing formalism "Send the node for the letter 0 that is 5" we instead ~ay "A~sert that D i~ s· and a process of compilation turn~ thi~ a~sertional code into a me~~age pa~~ing implementation. For certain problem~ thi~ proces~ of compilation is imp<>rtant !>ecause certain idea~ can be expressed quite naturally in the a~sertional form that compile into vpry complex me~~age passing codeo. These i~sue~ will be discu~sed in (9~

Becau~e we are interestl'd in the po~~ibility or pur~uing more than one instantiation of the constraint network in parallel, Wl' nel'd the ability to have more than one available for processing. For this we introducl' the notion of a virMpoint. Each vil'wpoint tag~ a mutually compatibll' colleoction of a~sumptions about the possible values or letters and digits together with the constraint~ that derive via propagation from these assumption~. (i .e. a viewpoint is one particular instantiation of the network). Viewpoints are related to each other by an inhl'ritance mechani~m. The viewpoint in which A is a.<sumed to be ·!I and B i~ assumed to be 4 might be a ~ubviewpoint of the one in which A i~ as~umed 5 and no other a.·sun1ptions have been made. Vil'wpoints are the repo~itorie~ of a.·~umptions and fact~ derivl'd from these assumptions.

In Nder to be able to hypothe~ize and te~t Wl' need to introduce ~orne control primitive~. These primitives are built around a con~truct known as an activity. All proces~ing that happem during execution happens un<ler the au~pice~ of ~orne activity. There are language con~truct~ for conveniently grouping pam of a related task into a single activity. For example, we can create an activity, make a new a~~umption in a viewpoint, and cause all further work within the viewpoint (i.e. all further constraint passing in the instance of the network defined by the ~~umption) to be part of the activity.

Activ i.t ie~ are of intere~t becau~e they give u~ way~ to control quantitie~ of ~y~tem re~ource~ available for the execution of alternative exploration~. If we stiflt an activity, all execution with the activity ~top~: a ~tined activity cannot be re~tarted. We al~ have the ability to control the rate~ thai non-~tined activitie~ run. Different activitie~ can be a~~igned different amounts of procnsiflg powl'r, the total amount of CI'U time an activity will get during an interval of time i~ proportional to it~ proce~~ing power. The proce~~ing power of an activity can be altered by the ~y~tem a~ynchronou~ly with the running of the activity.

Sy~tem~ using hypothe~ize-and-te~t can be constructed in Ether by u~ing vicwpoiflts to represent a~umptions made, and octMtitS to control which parts of the search ~pace are explored, and with what vigor.

S. A Simple Parallel Solution

In thi~ treatment we will ignore many details of how both the Ether ~y~tem and the cryptarithmetic sy~tem implemented within it are constructed. If we wi~h to "create a new instance of the conmaint network" that inherits from another, we create a new viewpoint (u~ing the new-viewpo1nt construct). To add an ~sertion about a letter being ~~ociated with a digit within the context of this viewpoint, we execute (assert (one -of .. letter ( .. digH))) where letter and digit are bound to the re~pective letter and digit which we want to a~sume are identified in thi~ viewpoint. The second argument to one-of is a liM of possible digits that the letter can be. So, for example. we could execute (assert (ona-of s (I 3 57 9))) to indicate that S is odd. Ether ~yntax make~ u~e of a quasi-quote convention in which ~ymbols prefaced by the character · .. · are sub~tituted with the value~ of the ~~ociated ~)·mbol~. If Iotter were bound to ·o· and digit were bound to ·s·. the item actually a~~erted would be (one -of D (S)). If the assert is executed within the context of a certain activity, then all . work propagating constraints that follow from that a.<serrion will happen within that activity.

The implementation de~ribed in this section is quite simple. It first create~ a viewpoint in which no ~sumption~ are made and continues propagating conMraint~ within this viewpoint until it h~ quil'scl'd, i.e. no more propagation can happen. When this state h~ been achieved, if each letter does not have a unique digit that it can be identified with; it is determined which letter hu the lea.<l number of po~sible digit~ that it can be (excluding those !etten that already have . a unique .a~~ignment). For each one of these digit~. a new viewpoint and a new activity are created. Within these (in parallel), the letter i~ a~~t>rted (assumt>d) to be the digit and propagation of constraints continue~. If quie~ence is reached in this new activity and the problem h~ not been ~olved, we recurse.

The function shown below takes a letter, a list of alternative digits, and a viewpoint. It use~ the environment contained in the viewpoint to create new ~ubviewpoint~ in which the letter is a~sumed to be t>ach of tile alternative digit~. We fiut check to see if there is at lt>ast one possible digit. If not, there cannot be a possible ~olution to this problem consi~tent with the parent viewpoint and ~ we assert that there is a contradict ion within the parent viewpoint. Otherwi~e we iterate over each digit in the alternatives list and for each one we create a new viewpoint whose .parent is the parent viewpoint and a new activity with parent stert-act and assert the letter i~ the particular digit: thi~ initiate~ propagation of con~traint~. If we discover there i~ a contradiction within the viewpoint (this is accompli~ht>d by the code. fragment beginning with "{when ( (contradict ion) n we assert within the parent viewpoint . that the lettt>r cannot be the particular digit. We are ju~titied in doing thi~ because the only difference, in terms of a.<~umptions made, between the current viewpoint and the parent viewpoint is the one a.<sumption of the letter being identified with a particular digit that was a po~~ible altt>rnative in the parent viewpoint: if this a.<sumption leads to a contradiction, we know that this is not a pos~ible identification for the letter. In addition we ~title (~top from executing) the activity that wa~ pur~uing the now known to be invalid ~~~umption. We further check to see if the activity quie~ces in the section of code beginning with "(when ((quiucent ... ,, ·. If this has occurred, we first check to see if the problem h~ been ~olved. If so we are done: otherwise we determine the letter in the viewpoint with the least number of po~~ible digit5 (but greater than I) and recur~iveh· call perollel-solva on this.

(defun perellel-solve (letter elternothu perent-viewpoint) (if (null elternetives) :If tlltrt Grt "" ritlhlt GlltrltG/ntt, : tlrtn rllrrt '' "" ronJIJitnl a.ul&nmtnl pouiblt (within-viewpoint parent -viewpoint ( usert (contradict ion))) ; Otlrtr··iu, forA on tGrlr GlttrnGiirt (foruch digit elternatives (let ( ( v (new-viewpoint pGrtltl pare~~t-v1ewpo i nt)) (· (new-activity pllrtnl start-oct))) (within-viewpoint · (u.sert (one-of .. latter (·digit))) ( ect ivate (when ((controdtction)l ( within-v 1ewpoint parent-viewpoint (usert (cont -bo .. lattor .. digit))) (1tifle a)))) (activate · ; If tilt Grtiri/J ll111 quinutl, "'' mwll fir II rllrrA if :tilt probltm lrtu bttn Jolrttl; if so, wt 11rt tlont. ; Otlltrwiu wt mu.<l pirl .11 nrw br11nrll to go ;down itt 11 tltptll·fint fashion. (when ((quiescent .. a)l (if (total-solution (quiucent-lttter-constroinh v)) (halt-ether) ;lntlir111t1 ,., ., tlont (let ( (1111npa1r (111ini"'""' I' ( l1111bdo (pair) (let ((L (length (cedr pair)))) (if (· L I) 11. L))) (quiescent- htter-eonstreinh v)))) (parellel-solve (cer lllinpe;r) (codr 111inpoir) v)))))))))

When a new activity has been created (and hu ~omething to do) it immediately begin$ executing concurrently with already exiMing activitie$. The default allocation of proce~~ing power, when no explicit allocation h'-· been done, is such that each running activity get~ approximately equal servicing (in term$ of CPU second$) by the scheduler.

6. Alternathe Parallel Programs

The simple parallel program de.<eribed might well be reasonable if we had a large number of proce~~rs. With a $mall number .of proce~son (in particular, only one proce$~Or, the ca~e actually ~tudied) it is con~iderably le~~ efficient in term$ of average total run time than some other ~olutions. All the ~lution~ we will examine are elaboration~ of, or $imple modifications to the ba.<ic parallel program already pre$ented.

We ob~erve that a traditional depth-first search (with backtracking) i$ but a trivial modification of the code above. When new alternat)vt> digit~ are propo~ed for a letter, in~tead of Marting them up in concurrent viewpoint~ a~ was done above, they are placed on a li~t. Only the activity for the fir~t one on the list is s.iven any proce~sing power. If it quie~e$ we recursively call porelltl-solve. If it h di~overed that the v·iewpoint i$ contr~dictory, the next one i~ begun (if a next one exist~): otherwi~e. the parent viewpoint is asserted to be incon~istent. A$serting that it is inconsi~tent will trigger the activity monitoring the next higher viewpoint to pick the next pc»~ibility on it~ Ji~t. Depth.fir~t is a degenerate ca.'t of parallel search in which only one activity at a time is given non-zero proce~~ing power.

6.1 Heuristic Infor .. atlon to Control Resource Allocation

A ~imple elaboration we can make to the parallel implementation pre~ented that pre~rve~ it~ parallel character i~ to vary the proce~~ing power ba.'td on an ~~~~ment of how likely the 8$5Umption~ we have made within its ~~iated viewpoint are to lead to u~eful information (either leading to a solution or determining that the viewpoint is contradictory). We ba~e the quantity of proce~<ing power allocated to the activity doing the exploration on the numerical value of thi~ judgement. For this particular prf)blem, we are more likely to learn in a short period of time whether a viewpoint contain~ a valid solution or is contradictory if it i~ already fairly well conMrained, i.e. if the ·letten in the viewpoint onl)' have a few possible digits that they could be. After ~ome experimentation we came upon the following formula for determining relative processing power allocations for the variou:!> different activities participating in the search:

where each ni i~ the number of po~~ible digit ~signments for the letter i in the viewpoint. If the !etten tend to have fewer po~sible digit po~~ibilitie~. the sum terms (10- ni) will tend to be large. Squaring thi~ number, and squaring the final ~um ~erves to accentuate the relative difference~ between the different viewpoints. When the system is first set up, a "'parate activity known a.< the managt'r actirity continually monitor~ each of the other running activitie~ and evaluate~ thh< function for each associated viewpoint. The proce~sing power allocations to these activities are adjuMed in proportion to the numerical value of this formula. The_ Ether command we u~e for modifying the processing power allocations of an activity is called support-in-retios. It takes three argument~: an activity, a li~t of activities (that are children of the fint) and a list of non-negative number~ with the ~ame number of elements as the liM of activitie~. The proce~sing power a.<signed to the parent activity is (re)divided among the children ~tivities in proportion to the numbers in this list. Thu$. if a factor for a given activity is 0 the activity get~ no processing power: if the factor as~iated with the activity is twice the ·factor as~iated with another, then the former activity gets twice as much processing power as the latter. The allocator de~cribed i~ implemented 8$ follows:

(defunc squere-both-ellocetor () (support - in-ratios I''""" s tert · ect tJctl·ltltJ current ly·np1or1ng-ect1v1t its f·ctorl (fori ht vpt currently-explored-viewpoints · (let ( (stet us (quiescent· tetter-conatreinta Ypt)) (1101 1).) (foruch peir shtus ( incr1111ent I IIIII (expt (- 11 (length (cadr pair))) Z))) (IIIIK (npt SUIII 2) 1)))))

We c reate a separate activity at top-level called the ··n·ger-ect1v1ty and execute the following to have the allocation strategy continually called asynchronously with the activities doing the actual search:

(within-activity maneger-ect1v1ty (continuously-execute (funcell l'squere-both-allocetor))l

The maneger-ect hHy is given a processing power o.f .I (meaning it will use, on the average, a tenth of the total CI'U time for the entire run).

This scheme gives con~iderably .better performance than the simple parallel solution. It does better than the backtracking ~olution on some eKBmples with a single processor implementation, although on the average the backtracking ~olution is more efficient. It is important to under~tand the ~ource of thi~ improvement. We have a Kheme for e~timating the likelihood that a running activity will return useful information in a ~hort period of time. We allocate more re~ource~ to tho~ activities that we e~timate will supply u~ with information for the le&l-t amount of re~ource expenditure. A~~uming our heuri~tic i~ re&l-onable, the average time to complete the ~earch i~ reduced.

There are three more improvements we have made to the proce~~ing power allocation ~trategy before reaching the final strateg)' for which we have collected data in the next section. Each will be described in turn.

6.% Concurrrncy Futors

We hiiVe observed in the allocation ~trategy di~cus~d thu~ far that even though activitie~ are running with different amounts of proces~ing power that are related to our e~timate of the utility of getting useful inf<>rmation back from them, there still seem~ to be so many activities running that they tend to thra.<h again~t one another. We would like to limit the amount of concurrency ~o that the running activit ies can get something done. For this purpo~e we introduce the notion of a conC'urrency factor. Instead of letting all runnable activities run, we pick the n mo~t promising activities (u~ing the metric above), where n i~ the concurrency factor, and give only tho~e activitie~ proce~~ing power and in the ratios defined by the metric. The optimal value for the concurrency factor is picked experimentally and i~ di~u~~ed below.

The value of the concurrency factor that yields the best result is a reflection of two a~pect~ of the problem: the quality of our heuri~tic knowledge and the di~tribution of computational expen~e for picking bad branche~ in the ~earch. Obviou~ly if our heuristic knowledge were perfect, i.e. it could always point to the correct branch to explore next, the optimal concurrency factor would be I

it ~hould ~imply explore thi~ be~t branch. If we are le~s ~ure we are about which is the be~t. more branches ~hould be explored. Al~o. if the computational co~t of exploring a bad branch i~ always small, a ~mall concurrency factor would be appropriate. If. however, the cost of a bad branch can be very large we would want to use a larger concurrency factor. With a small concurrency factor we increase the probability that the problem solver will become stuck for a very long time. A limiting case of thi~ is with a search ~pace that i~ infinite (introducing the po~~ibility of a bad branch that never runs out of possibiliti~) and a concurrency factor of I. If the problem ~olver happen~ to pick one of the~e branches it will diverge.

Hayeo~-Roth ha~ noted an analogy with portfolio theory, the purpose of which h to pick an investment strategy that will yield the greate~t expected capital appreciation. Uncertainty about the future performance of certain industrie~ and volatility in the market place argue for greater diver~ification of the portfolio.

6.3 Estimating Which Assumptions Are Most Valuable

Our ~trategy ~o far ha~ been to u~e hypothe~ize-and-te~t on ont lrttrr only in each viewpoint. ,We ~prout one new viewpoint and activity to te~t the hypothe~i~ that that letter i~ each one of the digit~ it could po~sibly be in the parent viewpoint. This i~ not nece~sarily the be~! ~trategy . By h)· pothe~izing a letter i~ a certain digit we may learn a lot or a little. We have ·learned a lot" if we (I) di~over quickly that a viewpoint is contradictory, or (2) cau~e a lot of conMraint propagation activity that significantly increa~e~ our evaluation of the new viewpoint. One thing we have ob~erved i~ that the amount we learn from a~~uming a letter i~ a particular digit dors not significantly dq>l'nd on M'hich digit K't USl'. In other word~. if we a.·~ume the letter N is 2 and di~c<wer a contradiction, then we are likely to either di~ccwer a contradiction or ~ignficantly constrain our ~olution by a~~uming N i~ any other digit on it~ lht of alternatives. To take advantage of thi~ phenomenon the program rememben what happened when it make~ particular a~~umption~. When it creates 1 new viewpoint to ~tudr the re~ult of a.·~uming a letter is 1 particular digit the re~ult i~ recorded in the parent viewpoint when it has completed. There are two po~~ible result~. If it led to a contradiction thi~ fact i~ recorded. If it led to a quie~ent (but con~i~tent) ~tate it record~ the difference of the evaluation metric applied to the parent viewpoint and the evaluation metric on the quie~cent viewpoint -- our estimale of the amount of reduction that is likely to be obtained by assuming this letter to be a digit. Our new evaluation metric attempts to take thi~ information into con~ideration . When ~~uming a letter l i~ a specific digit we use the old evaluation metric if we do not have have never ~sumed l to be a particular digit from thi~- viewpoint: otherwise, we uJe the average of the evaluations for each of the resultant viewpoints. We then multiply this figure by the factor I -+ .S · n where n is the number of letters that we have a.·sumed ·l to be and determined that they lead to contradiction~.

Now that we have a mechanism for taking advantage of information learned by making different ~sumptions we would like to ensure that a variety of choices are tried _at each branching point. We will slightly modif)' the technique for picking the activitie~ to be run at any given time (in accordance with the concurrency factor). Where c is the concurrency factor, we. use the following algorithm to pick the c activities to run at a given time:

I . The activity with the highest evaluation is ~heduled.

2. If n < c activities have been selected for running, the n+ht activity is (a) the one with the highest metric if it does not duplicate any ,of the first n activities in terms of which letter it is making an a~~umption about for a given viewpoint, or (b) the highe~t rated non-duplicated activity unle~~ the highest rated activity has a rating at lea~t three time~ higher in which ca~e we use the highe~t rated activity. The factor three wa~ picked etperimentally and is b~ed on tlie following argument. There is a certain advantage in having a diversity of letter~ being te~ted becau~e this gives u~ a greater chance to di~cover a~~umption~ that will cau~e ~ignificant shrinkage by con~traint propagation. However, there i~ al~o an advantage to running the activity that we have estimated will give u~ the be~t result. The factor three is the ratio of estimates for upected gain for which we would rather run the higher estimated te~t than one that will increa~e our divenity.

7. An Experiment

In order to test for the exi~tence of a speed-up with concurrency we timed I 0 problem~ using the final parallel algorithm de~ribed above for ~everal concurrency factors. The problems tested are:

1) DONALD + GERALD · ROBERT 2) CRIME + TRIAL · THIEF 3) POTATO + TOIIATO · VEGIES 4) MIGHT + RIGHT · MOIIEY 5) FUNNY + CLOWN · SHOWS 6) FEVER + CHILL · SLEEP 7) SHOVEL + TROWEL · WORKER 8) TRAVEL + NATIVE · SAVAGE 9) RIVER + WATER · SHIPS 11) LONGER + LARGER · MIDDLE

They were picked b)· a trial-and-error proce~~ of ~electing possible problem~ and then running the111 to see if they have a solution. It h not known whether they have one or more than one rolution. The program fini~he~ when it ha~ found one !-Oiution. The~e te~t~ were run on the MIT li~p machine, a single user machine designed for efficient execution of lisp program~. The times represent proce~~or run time only and are adju~ted for time lo~t due to paging. The manager activity, which continually monitors the state of the ~earch activities and readjusts proce~~ing power accordingly, receives a proce~sing power allocation of .1. We tested with concurrency factors between I and 7. Numbers 2 through 7 each gave rome improvement with 4 being. the best. Here we report the results for concurrency factors I and 4. Time~ reported are in seconds:

With a concurrency factor of I the algorithm becomes, functionally, a depth-first search. A concurrency factor of 4 represents the value which yields lea.·t average run time for the problems examined. Concurrency factors larger and ~maller yield higher average values. We caution the reader not to take the numbers too seriously. We only wish to demonstrate that the parallel algorithm runs with rome improvement of efficiency over the sequential algorithm.

Some intere~ting facts can be learned by examining the data. Although the parallel rolution beat out the sequential solution in only 6 of the I 0 cases, these six cases are the ones for which the sequential solution~ take the longest. In particular, problems 6 and 9 have show by far the longe~t time~ for the. sequential solution and the time ~aving of the parallel ~olution i~ considerable. Similarly, for the cases in which the · ~equential ~olution finished quickly, the parallel solution tended to take longer. Thi~ phenomenon is fairly e~y to explain. The parallel ~olution ~upplies ·in~urance against picking bad branche~ in the search ~pace. If the ~equential ~olution happened to pick a bad branch (or several bad branche~) there was no recoune but to follow it through. Similarly, if the sequential program found a relatively quick path to the solution, the extra efficiency of the parallel solution w~ not needed.

If. Conclusions

We have demonstrated that cryptarithmetic puzzle~ can be solved with a certain increase in average efficiency by the parallel algorithm described over a more traditional depth-first ~earch solution. While thi~ re~ult in and of itself i~ of little use it doe~ demonstrate a tool that may be of great use in heuristic programming -- the u~e of parallelism to control a heuristic search. Several writer~ have pointed to the use of m<Ya-lt'ftl knowlrrlgt (e.g.

Davi~ (2)) in controlling a ~earch. Meta-level knowledge is knowledge about how to u~ the prob.lem solving tools 11 hand in a way that increa.<e~ overall ~earth efficiency. The allocation strategies we have examined are meta-level ·knowledge for cryptarithmetic problem~. By allowing a few to run in parallel, and with controllable amount~ of. proce~sing power we are able to increa.<e the efficiency of the ~earch. Although the increa.-e we gained is not dramatic there i~ rea.<on to suspect that it would be more significant in more intere~ting problems. The size of the ~arch space in the~e problems is relatively quite small. Thus picking a "bad branch" in the ~earth can't be too catastrophic. With 1 search space that is much larger, and po~~ibly infinite (» is the case with many intere~ting problems), a bad branch· u~ing a parallel ~arch can only do. a bounded amount of harm, bounded by the quantity of processing power allocated to it. Very similar results have been obtained in speech understanding re~arch projects {14, 3] in which competing hypothese~ are u~ed to control the allocation of resources for further inve~tigation.

We introduced several concept~ that were u~d in the construction of the allocation ~trategy. l'roce~sing power is allocated in proportion to an . e~timate of how likely we are to get useful information out of the exploration of a branch. UJitcurrcncy factors have been introduced to keep the problem solver rea.<Onably focu~ed. A certai'n amount of diver~ity is incorporated in the algorithm to increa·ed the likelihood of discovering assumptions that can be made that will lead to valuable information quickly. Although the only problem we have examined is cryptarithmetic, there is nothing about these general strategies that is specific to cryptarithmetic. They contribute to a general theory of parallel problem ~olving.

The form of the code is quite simple to write and understand. The algorithm comi~t~ of a mixture of con~traint propagation and parallel hypothesize-and-test. The programs involve asynchronous, concurrent activities processing different sets of assumptions. Furthermore, the re~ources allocated to these activities can be altered asynchronously with the execution of the activities.

We have demomtrated that introducing concurrency in the search process does actually i.ncrease overall efficiency, in particular it does no harm. This lends support to efforts to design a computing system for message pa.<~ing languages that involves many intercommunicating autonomous processors (e.g. Hewitt (5]). It suggests there is inherent concurrency in search problems that could be gainfully run on multiple processors. We are interested in generalizing the control notions we have developed, such as proce~sing power and quiescence, to be implementable on truly parallel architectures.

9. Acknowledgements

Deppe Attardi, Roger Duffey, Carl Hewitt, Kurt Konolige, David levitt, Reid Smith, and Barbara White were kind enough to read earlier drafts of this work and have su~tantially aided the presentation.

I offer my sincere thanh to the lisp machine development group at MIT. Without the ~uperb computing environment available on the lisp machine the program development neces~ary to carry out this research would have been impossible.

10. References

• (I] Borning, Alan, Thinglab -- A GJnstraint-Oricnterl Simulation Laboratory, XEROX PARC report SSl-79-3, July 1979.
• [2) Davis, Randall; M~a-Rules: Rta:J!}ning About �Jntro~ MIT Artificial Intelligence Laboratory memo 576, March 1980.
• [3) Erman, L., F. Hayes-Roth, V. Lesser, D. R. Reddy, The HC'anay-11 SpC'rch-Undastanding Systtm: Integrating KnoM·It'rlgc to Resolvl' Unurtainty, ACM Computing Surveys, Volume 12. Number 2, June 1980.
• (4] Ga.<ehnig, John, PrrformanC't' MC'Dsuremrnt and Analysis of Crrtaifl SC'Drch Algorithm$, Carnegie-Mellon report CMU-CS-79-124. May 1979.
• [!i] Hewitt, Carl, Dt'Sign of the APIARY for Actor Systrms. Proceeding~ of the 1980 Lisp Conference, Stanford, CA, August 1980.
• [6) lmai, Ma~aharu, Yuuji Yoshida. Teruo Fukumura. A Parallel Searching ScltC'mC' fo~ Multiprocessor Systems and its Application to OJmbinatoria/ Probltms, Sixth International Joint Conference on Artificial Intelligence, August 1979.
• Kornfeld, William, ETHER -- A Parallel Problt'm So/ring System, Sixth International Joint Conference on Artific\al Intelligence, Augu~t 1979.
• [8) Kornfeld, William, Using Paralll'/ Processing for Probll'm Solving, MIT Artificial Intelligence laborator)' memo 561, December 1979.
• Kornfeld, William A., PhD thesis, in preparation, 1981.
• Newell, Alan, Herbert A. Simon, Human Problem So/ring, l·rentice Hall, I 972.
• [II) Steele, Guy l., Gerald Sus~man, GJnstraints, MIT Artificial Intelligence laboratory memo 502, November 1978.
• Steele, Guy l., Tht D~flititJfl and /mplemtntation of a Computt'r Programming Languagt · Dasrd on GJnstraints, MIT Artificial Intelligence laboratory TR-595, Augu~t 1980.
• [13) Waltz, David, Gtntrating Stmantic DC'JCriptitJns from DraM;ngs of Scenes with SltadoM'S, PhD thesi~ Massachu~tts ln~titute Of Technology, I 972.
• [14) Wood~. William A., Si.ortfall and Density Scoring Strategies for Spccr:h Understanding GJntrol. Proceeding~ of the Fifth lnternation Joint Conference on Artificial Intelligence, 1977.