On Methods To Decide Solvability of Transformation Problems

Introduction

The solution of transformation problems can be more easily found if information about the structure of the problem space is available. Such information may be for instance an evaluation function describ­ ing an approximation of the goal distance or an approximative description of the applicability sets of the operators (Pohl /1/, Banerji /2/)·

Structural information about the problem space may also be used to decide the solvability of any given problem. This saves fruitless effort in handling in­ solvable problems. Authors usually do not pay attention to this important question; one exception is the article by ~iklossy and Roach /3/.

In the present paper there will be given statements about the solvability of trans­ formation problems in a problem space depending on structural properties of the problem space.

In section 2 we shall discuss questions of solvability of problems and give gene­ ral methods for deciding solvability in a problem space.

Section 3 contains the definition of a special class of problem spaces - the so­ called binary - coded problem spaces. Finally, in section 4 we apply the gene­ ral methods stated in section 2 to binary­ coded problem spaces.

~ome Teneral remarks on solvability o transformation problems

Let S be the finite nonempty set of situa­ tions of a problem space and F the finite nonempty set of 1-place operators over s. That is, for each f€F, f: sf-s, tnhere sf 5 s. sf is the subset of situations to which f is applicable (see also Banerji /2/ and Ernst /4/). A transformation problem in the problem space (S, F) is an ordered pair (s 1 ,s 2 ), where s 1 , s 2 e S and s 1 and s 2 ere the initial situation and the goal situation, respectively · . \ solution to the problem (s 1 , s 2 ) is a sequence cf operators from F, 'f= f 1 f 2 ··· fm such that f is appli­ cable to s 1 and \f(s 1 ) = s 2 · 'f is appli­ cable to s 1 if and only if s 1 e Sf and 1 f 1 ··· f . (s 1 )E:Sf for all ~ . i+l i €: {1, ... , m- 1} .

~e want to investigate two important que~tions on solvability of transforma­ tion problems in problem spaces (S, F). Firstly, it is intere!ting to know whether ell possible problems (s 1 , s 2 )

in s problem space are solvable. Problem spaces with this property are called total l y-solvable problem spaces. recondly, we wish to formulate a method for deciding the solvability of any given problem.

For investigation of solvability of transformation problems the concept of type-k-separated subsets of the situa­ tion set S is introduced as follows: Let s 1 be an arbitrary subset of s.

Definition 1:

1. s 1 is a type-1-separated subset of S if &nd only if for all f6 F and all se.s 1 _nsf' f(s)es 1 ·
2. s 1 is a type-2-separated subset of S if and only if for all f e. F and all ne: {S '-. S 1 )!l Sf' f(s)E S '- s 1 · *
3. s 1 is a type-3-soparated subset of S if and only if s 1 is both a type-l­ and a type-2-separated subset of s.

In the representation of a problem space as a directed graph a type-1-separated subset of S corresponds to a subset of nodes not being left by an arrow and a type-2-separated subset of S to a subset

• *The expression S' s 1 moans exactly the same as s n sl.

of nodes not being arrived by an arrow. Therefore, for instance, in the problem space presented in Figure 1 ts 5 , s 8 ) is a typa-l-separated subset, {s 1 , s 2 } is a type-2-separated subset and {s 7 , s 9 } is a type-3-separated subset of s.

Using Definition 1, the followina theorem may be formulated on the-total solvability of a problem space.

Theorem 1: A problem space {S, F) is not totally-solvable if and only if there is a nonempty proper subset of 5 which is a type-1-, type-2- or type-3-separated subset of 5.

Proof: (~) Suppose there is a non­ empty proper subset s 1 of s which is a separated subset of one of the three types. Obviously, in this case there also exists a nonempty proper subset 51 of S which is a type-1-separated subset of s. Then the problem (s 1 , s 2 ) with s 1 e. Si and s 2 E. S '-51 is insolvable. (~) Suppose {S, F) is not totally­ solvable and let s 1 be any situation in s. If there exists no nonempt~ proper subset of 5 which is a type-k-separated subset (k · 1, 2, 3) then we can show by induction that each s 2 e. 5 can be arrived from s 1 by applying an applicable ope­

rator sequence. Hence, all possible problems in ( ~ . F) are solvable. This contradicts the assumption and completes the proof. Q.E.D.

Theorem 1 implies that algorithms which detect type-k-separated subsets may be used to decide the total solvability of a problem space.

Now to the second main question, the decision of the solvability of concrete problems.

Let 5 be a nonempty proper type-1separAted subset of 5. Then a problem (s 1 , 8 2 ) r1ith s 1 , s 2 e.5 is not solvable if s 1 E:. s 1 and s 2 f. 5 1 · Analogous etatements hold for type-2and type-3-sep~rated subsets. Let ~= {s 1 , ··· , 5q} be a set of type1-separated subsets of S then, for de­ ciding the insolvability of a p~oblem (s 1 , s 2 ) in {S, F) we can use the following Decision ~ule 1: (s 1 , s 2 ) is not solvable if there is en Si E l{' such that s 1 €. Si and s 2 f. si.

2imila rly, Decision F:ule 2 and Decision Rule 3 may be formulated for type~2- and type-3-separated subsets, respectively.

On the other hanc: , if ~is any set of (not necessari l y disjointed) subsets of S then we define ss follows, 3ssuming k = 1, 2, 3:

Definition 2:

~is a consistent type-k-system of sut­ sets of S if and only if for all s 1 e. S, s 2 E:. S the sta'tement defined by Decision Rule k is true.

It may be proved in ~ simple ~Ey t~et Y is a consistent type-k-system of subsets of s if and only if for all sie.~ , si

is a type-k-separeted subset of s.

In the example of Fi9ure 1 the system Y" = { { s5 · sa~ · t 5 7' sgl }

is a consistent type-1-system of subsets of 5.

Using a consistent type-k-system of sub­ sets and the corresponding decision rule for deciding solvability of transforma­ tion problems, we commonly detect only some of the insolvable problems. But about the solvability of the other problems in the problem space we know nothing. Therefore, it seems to be necessary to introduce the concept of an admissible system of subsets. Let '("be any set of subsets of 5, then we define (k K 1, 2, 3):

Definition 3:

ris an admissible type-k-system of sub­ sets of S if and only if for all s 1 , s 2 e. 5 the following is true: (s 1 , s 2 ) is solvable if ~nd only if for all 5 1 E~ holds condition Ck, where Cl, C2

and C3 are def~ned as follows: Cl: s 1 E. 5 1 implies s 2 ~ s 1 C2: 8 2 6 5i implies s 1 6 Si · C3: s 1 e s 1 if ~nd only if s 2 c. si · Then, using admissible type-k-systems, we decide the eolvability of a trans­ formation problem (s 1 , s 2 ) in the follo­ wing manner:

We construct the set E(s 1 ) of all S 1 E.~

containing the initial situation s 1 and the set E( s 2 ) of all S.c.~ containing the goal si~uation s 2 .J Then the problem (s 1 , s 2 ) will be de­ cided as solvable if and only if E(s 1 ) c: E(s 2 ) for type-1-systems o: E(s 1 ) ~ L(s 2 ) for type-2-~yster.~s X": r:(s 1 ) = E(s 2 ) for type-3-systems 6. An example of an admissible system of subsets ~ill be given later in Figure 3. The concept of using systems of subsets of S to decide solvability of trans­ formution problems may be generalized to using systems of type-different systems of subsets of S, for instance to using a · type-1-system und a type-2-system at the same time. This comes from the possibili­ ty tha~ sometimes both some type-1cep~rated subsets and some type-2separated subsets are easy to detect ~nd to describe, but the description of an admissible type-1- or type-2-system of subsets of S is more difficult.

In th~ next section we ~ill introduce a special class of problem spaces - the so-called binary-coded problem spaces.

Description of a special class of problem spaces

Let n be any positive integer, called the degree of the problem space. Then the set S of situations of a binary­ coded problem space consists of all n­ dimensional vectors x 1 ··· xn with xiE {o, 1J for 1 = 1, ··· , n. Any special situation s 1 € S is specified by the values of its components, s 1 (1) ··· s 1 (n). The set F of operators is F = £f 1 , ··· , fn 1, where for all i = 1, ··· , n fi negates the value of the situation component xi if it is ~ppli­ cable. That is, if fieF, s 1 c. S, fi applicable to s 1 and fi(s 1 ) = s 2 then the following conditions are satisfied: s 2 (i) = 1 - s 1 (i) s 2 (j} = s 1 (j} ~or ~11 j = 1, ··· , n with J # lo According to section 2 the ~pplicability sets of the operc:.tors f::., ··· , fn c.re denoted by sf 1 ooo1 sf

Since the situation components are binary the applicability sets may be represented by Boolean conditions (applicability conditions), p 1 , ··· , Pn· where the

situation components stand for variables.

Figure 2 shows a simple binary-coded problem space of degree 4 in graph re­ presentation. The edges of the presented graph are labeled by the indices of the corresponding operators.

Applicability conditione of the ope­ rators:

Ficure 2

~ith respect to the form of the applic6bility conditions, subclcsseG of binary­ coded problem spcces may be defined. For instance, we define the cl~ss of con­ junctiv6 binary-cocec problem sp·ces (c~lled briefly: conjunctive problcr.1 ~paces) in the following mEnner: .. binary-coded problem space of degree n is a conjunctive problem space of degree n if and only if all applicability con­ ditions pi may be represented ss

Consequently, the problem spoce of Figu­ re 2 is a conjunctive ~roblem spece. For lster investigations it ic con­ venient to define a binary relation ~ over the operator set F of a conjunctive problem space as !-allows (fi, fjeF): f i >- f j if and only if qij € f x j, x j ~

The class of disjunctive problem spaces may be defined analogous to the defini­ tion of conjunctive problem spaces.

In this section ne will state some solva­ bility theorems for binary-coded problem spaces.

First we give a necessary definition.

Definition 4:

A binary-coded prob l em space of degree n, (f,F') with the applicability conditions Pi····· p~ is ~ subspace of a binarycoded problem spocc of degree n, ( S, F) with the applic~bi ~ ity conditions p 1 , ···· Pn if and only if for all i = 1, ··· , n the statement Pi_.Pi holds.

To decide solvability properties it may be useful to approximate problem spaces.

Let ('., F' ) and (;"":, ~=') be two binary­ coded problem sp~ces of the same degree. Then, ( ~ , F') is called an underapproxi­ mation of ( :. , r) if ( ~ , F') is o sub­ space of (f, r-). (S, F') is called an overapproximation of (:, F) if (C, F) is a subspace of ( ~ , F'),

Using these definitions we state the following theorem (without proof):

Theorem 2:

1. Suppose ( : , F') is en underapproxi­ mation of ($, i-). Then the following is true:
2. If (s, r-') is totally-solvable then (:, F) is also totally solvable;
3. For all s 1 , s 2 es: If (s 1 , s 2 ) is solvable in( ~ , F') then in (t"', F), too.
4. Suppose( <, F') is an overapproxi­ mation of ( " , F). Then the follo~ing is true:
5. a} If ( C, F'} is not totally-solvable then (:, F) is also not totally­ solvable;
6. For all s 1 , s 2 6 S: If (s 1 , s 2 ) is not solvable in (!:, F') then also not in(:, F).

Suppose that a binary-coded problem space is described by applicability conditions in disjunctive normal form. Then we ob­ tain an underapproximation if we con­ struct a set of new applicability condi­ tions by taking only one conjunction from each of the original conditions to the corresponding new conditions. The resul­ ting problem space is a conjunctive problem s.pace.

We obtain an overapproximation of the original problem space if we construct each new applicability condition as a disjunction which contains only one variable from each conjunction of the original corresponding condition. This resulting approximation is a disjunctive problem space. That is, conjunctive pro­ blem spaces are suitable as under­ approximations of a binary-coded problem space and disjunctive problem spaces as overapproximations. Therefore, with respect to theorem 2, solvability pro­ perties of binary-coded problem spaces can be investigated by analysing solva­ bility properties of these two important subclasses.

In this paper we shall il l ustrate this analysis for conjunctive problem spaces only.

First, we give the following definition:

Definition 5:

~ithin the operator set F of a con­ junctive problem space there is a cycle with respect to the relation ~· if and only if there are operators fi , ··· , f. E. F such thCit 1 1 1

Further we ~tate the follo~ing lemma without proof (Florath /5/):

Lemma 1: In a conjunctive problem space (5, F) there is a type-k-sep~rated subset of S (k 6 f1, 2, 31 ) if and only if there is a cycle with respect to th~ relation ).. within F.

Combining Lemma 1 and Theorem 1 we im­ mediatly get

Theorem 3: A conjunctive problem spece (S, F) is totally-solvable if and only if within the operator set F there is no cycle with respect to the relation )- ·

After investigating ·the question of total solvability we now shall define a method for the construction of type-k-systems of subsets for conjunctive problem spaces. For simplicity, let us assume that the graphs defined by the problem spaces are undirected. Consequently, each type-k­ separated subset must be of type 3 and we construct type-3-systeme of subsets.

It can be shown, that for each cycle with respect to the relation )- within the operator set F there exists a correspon­ ding type-3-separated subset of s. Let c 1 , ···· Cq be all the cycles with respect to .>- within F. Let further s 1 , ··· , Sq be the corresponding type-3separated subsets. Hence, the system d'" 0 · { s 1 , ··· , sq, s '\ s 1 , ··· , s '\. sql

is a consistent type-3-system of subsets of s. Then we construct the wanted ad­ missible type-3-system of subsets, ~ , stepwise from ¥"" 0 in the following manner: Let ~k be the system after k steps (k = 1, 2, ··· ). If for all Si E. ~k and all fjE.F, for which there are situations s 1 , s 2 e f:i with s 1 (j) i s 2 (j), there exists an s esi such that s esf then we j set

and the process of construction termina­ tes. In the other case, if there ere Si € d'""k' f je F such that there exist s 1 , s 2 € Si with s 1 (j) i s 2 (j) and for all sESi, sf.Sf then d'""k must be modifiec. j

It is possible to prove that the defined construction process.yields an admis­ sible type-3-system ~ of subsets of S for all undirected conjunctive problem spaces if complete information about the applicability conditions is available. Moreover, the construction of ~can be realized very simply. Especially the identification of an element of (( k

which should be replaced by two new ele­ ments is accomplished through simple coefficient matching.

Figure 3 show& ~n example of a con­ junctive problem space and the construc­ tion of an admissible type-3-system (( for this problem space. In Figure 3 an expression like ·110 means a cylinder set of situations.

If i~formation about the applicability conditions of a problem space is in­ complete, then the described construc­ tion process yields a consistent but not necessarily an edmissible type-3-system of subsets of s.

Conclusions

Insolvability of insolvable transforma­ tion problems may be decided, for in­ stance, by means of type-k-systems of subsets of the situation set, as defined in section 2.

Such additional expense in handling pro­ blems is profitable if it is exceeded by the saved amount of problem solving ef­ fort for insolvable problems.

However, information about the structure of the problem space is necessary for detecting type-k-separated subsets of

situations.