A Problem Reduction Model for Non-Independent Subproblems

Abstract

A hypergraph model is introduced, which besides including the AND/OR graph and state space graph models as particulars, is adequate for problem solving tasks involving non independent subproblems. The hypergraph model is shown to be grounded on a nonstandard notion of conjunction such that the truth of a conjunction does not necessarily imply the truth of the conjuncts. A hypergraph search algorithm is given and shown to be equivalent to a resolution-based theorem prowr in a first order logic augmented with the special conjunction. A characteriza­ tion is given of the class of problems requiring the full descriptive power of our model. The class includes problems involving resources, plan forma­ tion, simplification of predicate logic programs.

I . Introduction

AND/OR graphs arc widely used as problem solving model through problem reduction [I). The assumption underlying both the model and the existing search algorithms is that subproblems can be solved inde­ pendently, i.e. the solutions to the original problem can be obtained by linear composition of the solutions to the reduced subproblems. The in­ dependence assumption yields a nice and clean yet not sufficiently general model. Examples have been proposed in the literature (2-6 J of problems for which the AND/OR graph model is inadequate because the independ­ ence assumption is not valid . The examples fall into three classes we will try to hriefly outline . ·

The first class consists of problems in which the solution to a sub­ problem may modify other subproblems. Problems in this class, which wiD be called interaction problems, arise when variables are needed for problem descriptions and subproblem descriptions exhibit common varia­ bles.

The second class consists of problems whose solution involves the expenditure of scarce resources (resource problems). A typical example is the one given by Simon [2), where John (owning $5000) needs a car(cos­ ting $5000) and a yacht (costing $5000) in order to seduce an actress. The independence assumption would lead to a positive (yet erroneous) solution to the problem "Can John seduce the actress? ".

The third and more general class consists of problems whose formu­ lation requires the use of concepts defined as conjunctions of non inde­ pendent terms. Examples of problems in this class, which we call conjunc· tion problems, are also given in [2). We will give in Section 5 a detailed description of conjunction problems and show their relevance to artificial intelJisence .

Difficulties arising from the AND/OR graph model inadequacy are · generaUy duped by means of problem dependent tricks. The authors have introduced a model (5 ), based on a generalization of AND/OR graphs, which is adequate for problem reduction in the most general case . This model, which is defined in the next Section, provides a unifying frame­ work for representing the above classes of problems.

2 .. ~!obleh~-r~~ucti~_n_ hypergrap~~

A problc·m solving task is defined as a set of prob/c?ms D and a finite set of N:ducticm OfH.'Trllors F. Set D must contain two distinct clements 1 (bottom) and T (top) denuling the "undefined solution problem" and the "terminal (trivially solved) problem" . respectively . Each reduction operator f; maps an m;·luplc of problems d: . ...· d~; into an n;·luple of problems d! ·. ... d~; · and it is represented by the productiou

The problems d; (j=l ·...· m;) and d~ (k=l ....· n;) are called f;·iuput problems

G. Levi and F. Sirovich Jstituto di Elaborazione della Jnformazione Consiglio Nazionale delle Ricerche, Pisa, Italy

and !;-output problems, respectively .

A problem solving task can be represented by a problem reduction hypergraph (prh) H which is defined as a finite directed hypergraph· whose nodes are in one-to-one correspondence with (and labelled by) the elements of D and whose edges are in one-to-one correspondence with (and labelled by) the elements of F. Note that prh's include both AND/ OR graphs and state space graphs as particulars. AND/OR graphs are prh's whose edges have a single initial node, while state space graphs are prh 's whose edges have both a single initial node and a single final node (hence are edges in the usual sense).

An edge labelled f; can be graphically represented by a special node whose input edges come from the nodes labelled by f;·initial problems and whose output edges lead to f(final problems. Figure I· represents the prh corresponding to the problem solving task in Table I. When a prh reduces to an AND/OR graph, prh edges and nodes obviously correspond to OR nodes and AND nodes, as defined by Nilsson (I).

Prh's are searched in order to find solutions , to show how the unde­ fined solution problem 1 can be solved by reducing it to the trivially solved problem T. Solutions arc defined over the (generally infinite) hypcrtree If' associatC'd to the prh II and which is obtained by unfolding H. i.e . by recursively duplicating the output edges of those nodes having more than one input edge, starting from the node labelled by 1.

· A finite hyperpopll )7) ;, a pair II : (N.I'.), where N ;, a finilr ICI of nodi's, and E ;, · .cl of subsel< (cd~es) of N. A finite dire<·Ud hy~apll ;, a pair II =(N .E~ where N ;, a finile ,., of nodes, and 1'. ;, a sel, such that each elemenl (dirtcteJ tdx<'l c; i< an ordered pair (1;. 0;1 of ·ubscls of N. The clements of I; and of 0 ; arc called respectively initial and {iMI node~ of ei.

In order to exactly define solutions, let us firstly give the definition of context. A context of a prh H is any subgraph c of the hypertree H' associated to H, such that :

1. The node labelled 1 belongs to c;
2. ii) For any node n belonging to c, either n has no output edges in c ( i.e. n is a leal) . or c contains exactly one edge e such that n is an initial node of e in II', and all the initial nodes of e in II' he long In c;
3. iii) For any edge c belonging to c, all the final nodes of c in II' belong In c.

A solution is a context such that all its leaves arc labelled by T.

Figure 2 shows all the contexts of the prh in Figure I . Context c 9 is the (only) solution.

Given a problem solving task, implicitly defming a prh H, a top-down algorithm searches the space of contexts of H in order to find a solution . The basic operation of such an algorithm is the expansion of a context c 1 by applying all the applicable productions. A production f k is applicable to a context c 1 iff for each fk ·input problem dl there exists a separate seltcted leaf of c 1 labelled by di' Clearly fk may identify different sets of selected leaves on cr For each set s. of selected leaves a successor context is obtained from c. by connecting the set of nodes in s. to a set of nodes labelled by the fk~utput problems, by means of an edge labelled by fk. (For example, context c 6 in Figure 2 is obtained by applying production f 4 to context c 5 ) . The expansion of a context yields the set of all its successor contexts. A context with no successors is either a solution or a failure.

An admissible and optimal heuristic top-down algorithm was given in (5) . Here, we will instead describe a backtrack algorithm.

Step. I . Let c 0 be the context consisting of a node labelled by 1, and S be an empty stack .

Step. 2. Expand c 0 to obtain its successor contexts c 1 . .... ck. If no successor contexts arc found (i .e. c 0 is a failure) backtrack to Step 3. If one of the successor contexts, say ci' is a solution, exit with ci; otherwise set c 0 to c 1 · put the successor contexts· Cz · ... , ck (if any) on stack S

· Note tltut it is 1ufficient to store on 5tack S simply the list of the leaves of each context.

and iterate Step 2.

Step 3. If Sis empty, exit with failure; otherwise set c 0 to the head of S, pop S and go to Step 2.

When the backtrack algorithm is applied, for example, to the pro· blem solving task of Table I , the contexts represented in Figure 2 are expanded in the following sequence : c 1 , ca, c 4 (failure), c 3 , c 5 , c 6 · c 7 . The successor c 9 of c 7 is the solution .

1. lnt!lr_aclion problems and nnndetcrministk algorithms

l'roblem reduction hypcrgraphs go beyond the capacity of AND/OK graphs with respect to two characteristics.

1. The prh reduction operators arc context-sensitive, i.e. the may have more than one input problem;
2. ii) The prh search space is the space of prh's contexts, whlle the AND/OR graph search space is the AND/OR graph itself (1, 8, 9]·.

The first characteristic will be discussed later at lenght. In order to show the relevance of the second one, we will consider the interaction problems .· i.e. problems whose reduction operators contain variables and therefore must be represented by production schemes. A classical exam· pie, often used to explain the behavior of PLANNER programs, is the following.

f, : 1-+ Fallible(x), Greek(x)

fa : Fallible(x)-+ Human(x)

f 3 : Human(Turing)-+ T

f 4 : Human{Socrates)-+ T

f 5 : Greek(Socratts) -+ T

Since variables occur in problem descriptions, the application of a produc· tion requires a problem description matching operation and results in a unifying substitution associated to the edge corresponding to the produc· tion application.

The prh describing the example is shown in Figure 3. In this case, the prh is an AND/OR tree and represents also the search space of the AND/OR algorithm. It is clear that the problems Fallible(x) and Greek(x) cannot be solved independently . Once a solution is found to Fallible(x) in which a substitution for variable x occurs, the substitution must be carried over to Greck(x). A depth-first AND/OR search algorithm will first solve Falliblc(x) binding x to Turing. The modified problem Greek(Turing) is then unsolvable, thus making unsolvable the 1 problem. The only way out is to backtrack to the already solved problem Human(x) to find a diffe· rent solution. The need then arises of bringing the search tree back to the state in which Human(x) was firstly expanded. This may be obtained by undoing all the operations performed from that expansion on . In conclu­ sion, the machinery that is needed for correctly handling interaction pro· blems is a substantial running over the AND/OR graph model.

· The aft:urilhm in 1101 is lhe only known AND/OR Jraph search atsorilhm whose ooarch space is somewhat akin to prh 's.

Alternatively, the state of the AND/OR tree could be saved every time a nondeterministic expansion occurs. Such a state Sllllillg leads to a modification of the search space, i.e. to the prh's context space. In the above example, when context c 1 is expanded (see Figure 4) context c 2 is considered for further expansion, while the other successor contexts, among which is cl' are saved onto the stack. Note that problem interac­ tion is accounted for by applying the unifying substitution to all the leaves of the newly generated context. When context c 2 is recognized to be a failure, the search algorithm backtracks to context c 3 whose succes­ sor is the solution.

The nature of interaction problems. which need either undoing or state saving, shows a close relationship to nondeterministic algorithms. The search for a solution to a problem defined by a set of productions can be seen as the execution of a nondeterministic algorithm. The state of a possible problem solution is described by the leaves of a context, and corresponds to the state of a nondeterministic algorithm computation. Actually. the name "context" has been borrowed from the context mechanism used by some languages for artificial intelligence (for example, QA4 I 11 I and MAGMA - LISP l/2) to allow nondeterministic programming.

4. Resource problems and context dependency

We will now discuss the first prh's characteristic we mentioned above, i.e. the context-dependency of prh reduction operators and show how this feature is crucial to handle resource problems. A resource problem is for­ mulated as a set of "goals" to be achieved through the expenditwe of (some of the) limited available resources. The task can be tackled by pro­ blem reduction, where reduction operator application may depend upon the availability of some resource and result in the consumption of the resour~-e. Resources arc then represented as problems themselves, which act as context for problem reduction. Since the solution of a resource problem does not require the expenditure of all available rt::.ouru:~. suit­ able productions reduce each resource to the terminal problem T. As an example, the actress problem described in Section I can be represented in the following way .

I, : 1 -+ Having-$5000, Seduce-the-actress

1 2 : Seduce-the-actress -+ Get-a-car, Get-a-yacht

1 3 : Havirw-$5000, Get-a-car-+ T

1 4 : Havillg-$5000, Get-a-yacht-+ T

1 5 : Havirw-$5000 -+ T

Produciions 1 3 and / 4 are context-sensitive because they have more than one input problem. Actually, they represent that interaction between problems and the available resource (Having-$5000) which makes this problem solving task unsolvable.

Let us note that interaction problems can be seen as resource problems. In fact, the state of a variable acts as a "context" for the application of reduction operators and could accordingly be represented as a re~urce .

An important class of problems that can be handled as resource problems is the class of problems dealing with changing world states, typically robot plaMing problems, in which world states are modified by reduction operators. Each state component I 13) describes a state proper­ ty . Each component may act as a "context" for , and be modif~ed by, the application of reduction operators, hence is represented by a problem. The planning task is reduced to the description of the desired fmal state while the description of the initial state. is reduced to the terminal problem T. This representation is similar to the state-space representation proposed in I /3) and similarly it is not subject to the frame problem. On the other side, our representation does not constrain an operator to have a single input problem.

lem. As an example, we will consider the following simple planning prob-

The initial state of this task is represented by production start and con­ sists of two boxes and two robots, at locations A,B,C and D respectively . Robot R I can move around and push boxes, while robot R2 can only lift boxes up into a shelf. The reduction operator go{w,x) describes R J's action of moving from location w to location x . Note that since the task is solved working backward the reduction operators are inverted descrip­ tions of the actual actions. Reduction operator push{ b,z.x) described R J's action of pushing box b from location z to location x, and reduction op­ erator lilt( b) describes R2's action of storing box b in a shelf. Finally, production stop describes the desired state in which both boxes are sto­ red on a shelf. Note that action describing productions are similar to STRIPS' operators {14).

Figure 5 shows one prh solution to the above planning task. The plan is obtained by " reading back" the prh solution from node T. Note that the plan is not bound to be an action sequence but it is in general represented by a partial ordering showing that subplans can be done in parallel . The plan obtained by the solution in Figure 5 is shown in Figu­ re 6.

We have thus considered the classes of interaction problems and resource problems. The next Section is concerned with the relationship between problem reduction hypergraphs and first order logic theorem proving. We will then be able to introduce the most general class of prob­ lems that can be modelled by problem reduction hypergraphs.

S. First_ O!~C!..!~ a!!d conjunct!~!'Jlroblems

Let us consider the following problem solving task .

• k 1 : 1-+ Times(s(O),s(s(O)).u 1 ).Times(s(O),s(s(O)),u 1 )J'Ius(u 1 ,u 1 ,r)
• k 1 : Plus(x.s(y).z)-+ Plus(s(x),y,z)

k 3 : Times(x,s(y),z)-+ Times(x,y,w)J'Ius(x,w,z)

k 4 : Times(x,z,v 1 ).Times(y,z,v 1 ),Pius(v 1 .v 1 ,w) -+Pius(x,y.v 3 ), Times(v 3 ,z,w)

k 5 : P/us{x,O,x)-+ T

• k 6 : Times(x,s(O).x)-+ T

Problems arc first order logic atomic formulas whose terms are built from universally quantified variable symbols, the only constant symbol 0 (zero), the monadic function symbol s(successor). The symbols l and T can be interpreted as the truth values 'false' and 'true' respectively . Any context· free production is therefore a Horn clause [6), whose equivalent clause is the disjunction of the left-hand formulas and the negated right-hand for· mulas. The clauscsc 1 , c 1 · c 3 , c 5 , c 6 equivalent to k 1 . k 1 . k 3 .k 5 ,k 6 are the following .

• c 1 : -Times(s(O),s(s(O)),u 1 1 V -Times(s(O),s(s(O)),u 1 ) V -Pius(u 1 ,u 1 ,r)
• c 1 : P/us{x,s(y),z) V -Pius(s(x),y,z)

c 3 : Times{x, .~(y),z) V -Times(x,y,w) V -Pius(x,w,z)

c 5 : Plus(x,O.x)

c 6 : Times(x,s(O).x)

Any context-sensitive production can be converted into a hypl'r·daiiSI' which is a disjunction of the single conjunction of the left-hand formulas, and the negated right-hand formulas . In our example, k 4 is equivalent to

The production arrow symbol is interpreted as "is implied by", so that a production of the general form

is interpreted as A/'IA 1 11. .11Am if 8 1 118 2 11 ... 118 0 ·.

The productions with the l symbol correspond to the clauses ob· tained from the negation of the well-formed formula to be proved, while the remaining productions correspond to a set of axioms. The application of a reduction operator can easily be seen to correspond to an application of the resolution principle. In particular, 1 -+ A,B,C and A,B -+ D can be reduced to 1-+ C,D, while equivalently the corresponding clauses -A V-B V-c and (AfiB) V -D resolve, with respect to the pair A and B, to the clause -c V -D. A problem reduction hypergraph search algorithm can then be seen as a resolution based, yet non complete, theorem proving strategy.

In a. pure first order logic framework, a hyper·clau~e (A 1 A ... Mm) V -8 1 V ... V -Bn is equivalent to (and would be accordingly transformed into) the set of m clauses

The equivalence does not apply to problem reduction hypergraphs. This peculiarity, which corresponds to the context-sensitivity feature of prh's, is grounded by a different logic, in which a conjunction does not neces· sarily imply its conjuncts. In such a logic, "I want cigarettes and matches" does not imply "I want matches". thus settling the ambiguity reported by Simon [2). As correctly Simon pointed out, the ambiguity stems from the non independence of the terms of this kind of conjunction.

Such an interdependence is accounted for in problem reduction hypergraphs by left-hand side special conjunctions. The hyper-clause (A 1 11A 2 11 ... 11Am) V -8 1 V ... V -Bn allows only to assign a denotation to the single compound relation (A 1 AA/1 ... 11Am)' while the individual conjunct denotations are undefined . On the other hand, the compound relation cannot be repre~entcd by a single compound predicate, since the A;'s may occur in other clauses.

The semantics of a problem reduction hypergraph H is strongly de· pendent upon the above defined semantics for special conjunctions. In fact, if 1-1 is transformed according to the standard conjunction semantics, a different nonequivalent problem solving task is obtained. Consider for example the actress task of Section 4, which would be transformed in the following obviously nonequivalent and misleading formulation .

/ 1 : 1 -+ 1/aving-$5000, Seduce-the-actress

f 1 : Seduce-the-actress -+ Get-a-car, Get-a-yacht

J;: Get-a-car-+ T

f. : Get·a-yacht -+ T

f. : Havilrg-$5000 -+ T

The conjunction problems mentioned in Section I are exactly those problems whose formulation requires the above defined special conjunction, in addition to the usual one, i.e . problems in which the interdependence among some of the subproblems cannot be ignored. This class includes the class of problems described in Sections 3 and 4. In fact, in interaction problems, variables introduce a simple kind of interdependence among conjunct subproblems. The context-sensitive productions for resource problems define compound relations among interdependent state compo­ nents. Therefore, conjunction problems are the most general class of problems with subproblem interdependence. The problem reduction hy­ pergraph model is the only known model which is adequate for this class of problems.

· Note that hypcr-clauoes are different from non·Horn clauoes 161 l>o.'cau"' lheir left-hand sides arc not disjunctions.

We will conclude by showing that problem reduction hypergraphs come forth as candidate model for an extension of artificial inteUigence goal oriented languages. Let us consider Kowalski's predicate logic [ /5) which is a model of present goal oriented languages. The context-free pro­ ductions shown at the beginning of this Section are actually statements of Kowalski's language. In the example, statements k 1 and k 5 are procedures defining (by means of relations) the function Plus over the domain of the integers, defined in terms of the successor function s and the constant 0. Statements k 3 and k 6 are procedures defining the function Times and k 1 is a goal statement requiring to compute r as (1·2) + (1·2). Statement k 4 cannot be interpreted in Kowalski's language and means that w=(x-z) + (y"'Z) if w = (x+y)-z, i.e. represents one possible way of applying the distributivity property. This context-sensitive production, which can be seen as a multi-name procedure, is intended to reduce the task of com­ puting an expression of the form (x-z) + (y·z) into the task of compu­ ting the simpler expression (x+y )·z . This production conveys therefore a pragmatic meaning which can only be expressed in terms of a complex relation involving three non independent predicates. The above example has been introduced in order to show the relevance of context-sensitive productions to the issue of computation optimization.

As a final remark, let us note that, similarly to goal oriented lan­ guages, a bidirectional search of problem reduction hypergraphs is possi­ ble, since a bottom-up search algorithm can easily be defined .

Problem reduction hypergraphs have been shown to be adequate models for problem solving tasks involving interdependent subproblems, and provide a unifying view of problems apparently of different nature, as problems involving variables, resource problems, plan formation, and program simplification problems. The two features which are essential to a correct treatment of conjunction problems are related to the search space and the context-sensitivity of the productions. The search algorithm is a correct and completely general implementation of nondeterrninism and mirrors the state-saving approach to nondeterministic algorithm interpre­ tation. The context-sensitive productions, which intend to augment first order logic with a special kind of conjunction, are a generalization of Horn clauaes and provide a basis for an extension of goal oriented laguages.