--- title: "The Use of Parallelism to Implement a Heuristic Search" authors: - "William A. Kornfeld" doi: "" url: "https://ijcai.org/proceedings/1981/108" pdf: "https://ijcai.org/proceedings/1981/0108.pdf" venue: "Proceedings of the Seventh International Joint Conference on Artificial Intelligence" year: 1981 pages: "575-579" track: "Search" keywords: --- # The Use of Parallelism to Implement a Heuristic Search William A. Kornfeld *Proceedings of the Seventh International Joint Conference on Artificial Intelligence*, pages 575-579. ## Abstract The role of parallel proce~~ing in heuri~tic ~earth i~ eumined by mean~ nf an example (cryptarithmetic addition). A problem ~olver is con~tructed that combine~ the metaphors of con~traint propagation and hypothe~ize-and - te~t. The ~ystem i~ capable of working on many incompatible hypothe~e~ at one time. Furthermore. it is capable of allocating different amounts of processing power to running activitie~ and changing the~e allocations ~computation proceed~. It i~ empirically f<>und that the parallel algorithm is, on the average, more efficient than a corre~ponding sequential one. Implications of thi~ for problem ~olving in general are di~cussed. ## Full text ## 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 ![Image](https://ijcai.org/proceedings/1981/fulltext/108/image_000000_2e597e2d3dbe04d092bba14f01e8deabca54844ca88db36f6b60f782edd09673.png) 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.