Failsafe - A Floor Planner that Uses EBG to Learn from Its Failures

Abstract

Analysis of failed problem solving efforts enables people to guide subsequent problem solving to avoid similar failures. This kind of learning while doing is essential in complex domains. We define Explanation­ based Learning from Failure (ELF), a technique for achieving such a capability, and describe its prototype implementation in Failsafe, a Prolog program that learns from failure while solving floor planning problems.

I Introduction . Explanation Based Generalization (EBG) [Mitchell et al 86] has been proposed as a method whereby problem-solvers can speed up with practice by learning from positive examples of problem-solving behavior [Prieditis & Mostow 87]. However, complex domains like design may require an unreasonable amount of brute-force search to find positive examples from which to learn. [Mostow 85] suggests that in such domains the problem solver must do intelligent adaptive search to converge to a solution quickly. One way to do adaptive search is to find the properties that make a generated solution unacceptable and, in future, avoid proposing solutions with these properties. We call such unacceptable solutions failures. In this paper, we propose that a system can use EBG to explain its failures in order to get sufficient conditions for them. These sufficient conditions, when negated, give necessary conditions for success which, in turn, can be used as negative heuristics to prune the search.

As a test bed for exploring the approach, we have chosen a simplified floor planning task developed by Prof. Chris Tong for an intermediate AI course. In this domain, a problem consists of fitting rectangular rooms into a rectangular area called 'house' of given integer length and width, subject to the following

constraints:

*This work is supported by NSF under Grant Number DMC-8610507, by the Rutgers Center for Computer Aids to Industrial Productivity, and by DARPA under Contract Number N00014-85-K-0116.

Failsafe -- A Floor Planner that Uses EBG to Learn

from its Failures

Jaek Mostow and Neeroj Bhatnagar*

Rutgers University Computer Science Department New Brunswick, New Jersey 08903, USA

• Room length and width must be integers in the ranges given in the problem.
• Rooms must not overlap.
• Rooms must be inside the house.
• The rooms must cover the entire house area.
• Every room must touch at least one side of the house.
• In addition, a problem may require that a given room be adjacent to another along a specified direction, or to a specified side of
• the house.

This paper describes Failsafe, a prototype floor planner implemented in Prolog. Failsafe uses Explanation-based Learning from Failures (ELF) to learn new operator preconditions.

II Description of the Technique

We now use an example to introduce ELF. We shall assume that the reader is familiar with the EBG learning paradigm described in [Mitchell et al 86].

Consider a generate-and-test (G&T) problem solver that generates floor plans using the operator 'Locate(R,X,Y,Sx,Sy)' to place room 'R' with width 'Sx', length 'Sy', and front left corner at (X,Y), where the front left corner of the house is at (0,0). An N room floor plan is generated by N applications of this operator. This plan is then passed to the tester module, which tests if all constraints of the problem are satisfied. Initially, operator 'Locate' has no knowledge about which placements of rooms would generate 'obviously wrong' floor plans and should be avoided. It has the following STRIPS-style definition:

Operator: Locate(R,X, Y ,Sx,Sy)

Preconditions: room(R) 1\ is_in_house(X,Y) 1\ valid_width(Sx) 1\ valid_Iength(Sy)

Add List: located(R,X,Y,Sx,Sy)

I

J

~

The preconditions check that the object to be placed is a room, that the width and length are in the legal ranges, and . that the room's front left corner will fall in the house area.

Suppose the floor planner defined above is given the following trivial floor planning problem: fit two rooms, 'r1' and 'r2', of length 1 and width either 1 or 2, in a house of length 1 and width 3. A solution to this problem is shown in Figure 11-1. However, starting from the lower left corner of the house and giving the smallest allowed size to the rooms, the floor planner first generates the plan shown in Figure 11-2. Here S 0 is the initial state, S 2 is the final failure state, and the failure path contains two applications of o~rator 'Locate.'

One reason this plan fails is that it has overlapping rooms. The simple G&T floor planner will, at this stage, chronologically backtrack to the point where it made its last choice, say the size of room 'r2', and select the next possible value, namely 2xl. This behavior is doubly stupid, first because the floor planner places the rooms in overlapping positions, and second because in changing the size of 'r2', it tries to repair the faulty plan at a place away from the fault.

Suppose the floor planner has the domain knowledge shown in Figure 11-3. Here "failure" is a global assertion which the learning module tries to prove whenever the tester fails a generated solution.

ELF uses the following four steps to recover and learn from this failure.

• ( 1) Prove the failure: Based on the domain knowledge, explain why the current state s. is not a I goal state and find Ci = F 1 A F 2 A ... A F k· which is a sufficient but specific condition for failure. Here, each conjunct F is considered operational, i.e., verifiable without search, whether by database lookup (located) or procedure (at).

In our example, we get

C2= located(r1,0,0,1,1) A located(r2,0,0,1,1) A ne(rl,r2) A ge(O,O) A ge(O,O) A same(l,O+l) A gt(l,O) A same(~,0+1) A gt(l,O).

1. Get a general condition 'G' for failure: Regress Ci through the· proof tree to get the generalization, Gi, of Ci such that the same proof of failure holds.

In our example, C 2 can be generalized to G 2 , given below.

G 2 = located(R1,Xl,Y1,Sxl,Sy1) A located(R2,X2,Y2,Sx2,Sy2) A ne(R1,R2) A ge(X2,Xl) A ge(Y2,Y1) A same(X3,XI+Sxl) A gt(X3,X2) A same(Y3,YI+Sy1) A gt(Y3,Y2).

Figure ll-4: Regress the failure condition back.

(3) Regress 'G' up the failed path to the place of recovery: Suppose that state Si was reached through states sl' ... , sj, ... , si-1 by applying operators (not necessarily distinct) 01 through oi to the initial state s 0 · Regress Gi back through the operators Oi, oi-l' .. . , oj+l' until it changes to some different condition G'i = Regress(Gi, Oj+l) t Gi = Regress(Gi, Oj+ 2 ..· 0i), as shown in Figure 11-4.

If G'. holds in a state s., the operator sequence I J Q.+l' ... , oi will not take the solver to the goal state. rd fact, Failsafe assumes that all instantiations of Oj+l which satisfy G'i will lead to. failure, no matter which operators are applied subsequently. This assumption is justified in Failsafe because it has no operators besides Locate. In general, justifying this assumption would require proving that no other operators applicable at each point in the path can lead to success. Such proofs require domain knowledge or exhaustive search (as in PRODIGY [Minton & Carbonell 87]) in amounts unrealistic for adaptive search in complex domains. Fortunately, this requirement· is stronger than necessary: safety requires

only that ELF not prevent the problem-solver from reaching a correct solution. Section V .A discusses this ~sue in more depth.

Notice that the condition being regressed back may pass unchanged through one or more operator applications, i.e., Regress(Gi, Oirrelevant) = Gi. In learning from this failure, we can simply filter out such operators from the operator ·sequence, since they have no effect on the sufficient condition for failure. An interesting case occurs when all but one of the operators are thrown out. In this case we d~cover a new precondition of the single operator left in the sequence after throwing irrelevant operators out.

This condition describes a situation in which a room 'R2' to be placed with width 'Sx2,' length 'Sy2,' and lower-left corner at location (X2,Y2} would overlap with an already located room 'Rl'. G 2 ' can be treated as a negative heuristic: when placing 'r2' the planner should make sure that G 2 ' not hold. Since G 2 ' has no problem-specific constant, we add -,G 2 ' to the preconditions for the operator 'Locate', as shown below. The resulting conjunction could be simplified, but Failsafe does not do so.

Operator: Locate(R,X,Y,Sx,Sy}

Preconditions: room(R} 1\ is_in_house(X,Y)

1\ valid_ width(Sx) 1\ valid_length(Sy)

1\ ..., (room(R) 1\ is_in_house(X,Y}

1\ valid_ width(Sx) 1\ valid _length(Sy)

1\ Located(Rl,Xl,Yl,Sxl,Syl} 1\ ne(R,Rl}

1\ ge(X,Xl} 1\ ge(Y,Yl}

1\ same(X3,Xl+Sxl} 1\ gt(X3,X)

1\ same(Y3,Yl+Syl) 1\ gt(Y3,Y)]

Add List: Located(R,X,Y,Sx,Sy)

1. Resume the search: Select a new instantiation o 'j+l of Oj+l for which G'i fails to hold, and continue the search until the goal state is reached or another failure is detected. If no such instantiation exists and no other operator is applicable, regress G'i further up until it undergoes another change at operator om, m<j+l, and repeat. If, backtracking in this fashion, the search reaches state S 0 , and no instantiation of 0 1 is applicable, and no other untried operator applies at S 0 , then the problem does not have a solution.

In our example the problem solver will now try alternate sizes and locations for room 'r2' that do not overlap the room 'rl'.

I

III Description of the Architecture

In designing Failsafe, we chose a very simple generate and test architecture, because it provides failures in abundance and is easy to implement.

Failsafe's solution generator initially uses exhaustive search to place the rooms, starting from the front left corner of the house space and going left to right and front to back. After every application of the operator 'Locate(R,X,Y,Sx,Sy),' the generator adds the new fact 'located(R,X,Y,Sx,Sy)' to the problem state. When all rooms are located, the solution is passed to the tester.

The tester checks if the generated floor plan meets all the problem constraints. If not, it rejects the solution.

The learning module uses ELF to learn new preconditions for the operator 'Locate'. It has a knowledge base of theorems about floor planning, some of which are shown in Figure 11-3. Whenever the tester rejects a floor plan, Failsafe uses these theorems to try to prove the goal "failure" in the context of the failed plan. Failsafe explains and generalizes the failure using a Prolog implementation of EBG [Kedar-Cabelli &l McCarty 87].

IV Results of the Implementation

We now present the results of experiments carried out to measure Failsafe's performance, the effect of increasing problem complexity, and transfer of learning from one problem to another.

A Performance on Three Problems

To test the effectiveness of ELF, we ran Failsafe on three example problems of increasing complexity, shown in Figure IV-1.

We measured Failsafe's performance by counting the number of PROLOG subgoals generated while solving each problem. We ran Failsafe on these problems with learning switched off, while learning, and after learning. Table IV-1 shows the results.

Improvement in performance is apparent for each of the three problems. Even for small problems the learning overhead is outweighed by improvement in performance, thanks in large part to the inefficiency of Failsafe's initial G&lT problem solver. Performance after learning is, as expected, better ·than during learning, although the difference is not as dramatic as in systems that learn from positive examples. For instance, Soar [Laird et al 86] learns a chunk for an entire problem, which enables it to solve the same problem in a single step the next time around.

B Between-problem Transfer

Table IV-2 shows the between-problem transfer effect for each pair of example problems. We measured this effect by training Failsafe on the first problem and then testing it on the second.

Solving P2 or P3 teaches Failsafe not to overlap rooms and not to cross house boundaries. Transfer is therefore ideal from P2 to P3, i.e., P2 trains Failsafe for P3 as well as P3 itself would.

Since no boundary-crossing happens to occur during the normal solution of Pl, transfer is negative from P2 or P3 to Rl: checking for crossed boundaries only slows things down. Since accumulating control knowledge indiscriminately c:an degrade performance, it may be a good idea to store and test only those preconditions that are frequently violated.

V Open Issues

Currently Failsafe finesses several issues.

A Safety .

ELF is defined as ·afe whenever it does not prevent the problem-solver from finding a correct solution. ELF uses a single failed path to reject an entire subtree without searching it exhaustively. While this strategy is crucial for efficient adaptive search of large spaces, it risks losing the ability to find a solution. ELF's safety depends on the problem-solver's operators and the nature of the failed constraint.

A constraint is monotonicalllf nece11ar1f if, once violated in a partial plan, it will remain violated in all extensions of this plan [Mostow 83a]. Such constraints are safe to learn as preconditions, since no solutions are thereby rendered unreachable; we will call violations of them monotonic failure·. For example, room overlap is a monotonic: failure in Failsafe, since it cannot be repaired by placing additional rooms.

If the effects of an operator· c:an be reversed by other operators, there c:an be no monotonic: failures, since every partial plan can be extended into a (possibly non-optimal) plan that leads to the goal state, assuming one exists. Failsafe's single operator, 'Locate,' has no such inverse.

Even if a condition is not monotonically necessary, it can be treated as such provided there are ways to solve the problem without . violating it. Such a condition c:an be called pseudo-monotonicalllf necessar1f. For example, suppose Failsafe had an operator for sliding an already-placed room from one location to another. Non-overlap would be pseudo-monotonically necessary if every room could be placed without ali ding.

Some conditions are not even pseudo-monotonically necessary. For instance, the constraint that every point in tlie house be covered by some room c:an be made true by placing additional rooms. Even such constraints c:an safely be learned as operator preconditions by restricting the c:irc:umatanc:es under which they are tested. For example, if the covering condition is only applied to complete floor plans, we c:an learn that the last room to be placed must include the remaining uncovered points.

B The Hopeless State Problem

At an intermediate state in planning, decisions made during the placement of earlier rooms c:an make it impossible to satisfy the preconditions of 'Locate' for the next room. We call such a state hopeleBB. An example of a hopeless state is shown in Figure V-1. Here room 'r2' is required to be adjacent to the left and front walls of the house, but room 'rl' has already been placed there, so 'r2' cannot be placed as required.

Learning to efficiently recognize hopeless states might enable FailsaJe to handle much larger problems. Currently Failsafe recognizes hopeless states only after exhaustive search fails to satisfy the preconditions of an operator. We plan to extend Failsafe to invoke learning at this point; at present learning occurs only when a complete floor plan is rejected by the tester.

C The Non-operational Precondition Problem

To be operational in the sense defined in [Mostow 81, Mostow 83b], an operator precondition must refer only to information available when the operator is selected, such as the operator's parameters and the steps used to get ·to the current state. The non­ operational precondition problem occurs when the learned precondition refers to parameters bound by operators selected later on. For example, when the non-overlap condition is regressed back through the sequence

locate(rl,Xl,Yl, Wl,Ll);locate(r2,X2,Y2, W2,L2), the resulting condition refers not only to Xl, Yl, Wl and Ll but also to X2, Y2, W2 and L2. In fact, the regressed condition is a precondition for the two­ operator macro, not for the first operator by itself.

One possible approach is to constrain Xl, Yl, Wl, and Ll to leave at least one acceptable assignment for X2, Y2, W2, and L2. However, evaluating this condition involves searching for such an assignment, and is therefore liable to defeat the purpose of testing preconditions -- enhancing efficiency.

D Detecting Failures

To learn from its failures, a planner must first detect them. In general, detection of failures is difficult. Failsafe gets around this difficulty because in its domain the length of the target plan is fixed and known: exactly N applications of the operator

'Locate' are required to- complete an N room floorplan. Failure detection requires other methods when the maximum length of the solution path is not known, such as noticing cycles [Langley 83, Minton & Carbonell 87].

E Which Necessary Conditions to Test

Explanation-based learning becomes counterproductive when so many macro operators are learned that testing their preconditions costs more than rediscovering them by search [Minton 85]. ELF is potentially subject to the same problem.

A system like Failsafe could sample how often a given condition fails and, before trying an operator, test only those which fail more frequently than some threshold that reflects the relative costs of precondition testing and search. This threshold could be modified dynamically depending on the performance of the system.

VI Related Work

The usefulness of negative heuristics learned by analyzing problem-solving failures has been reported previously. [Kibler & Morris 83] reports four negative heuristics obtained by manually analyzing "stupid" actions taken by a blocks world planner. By guiding the planner to avoid such actions, these four heuristics reduce search to almost zero.

CHEF [Hammond 86] uses domain knowledge to anticipate the failures that might occur while trying to satisfy a goal. When such failures occur, this knowledge is used to repair the plan instead of re­ planning from scratch.

[Siklossy & Dowson 77] describes preprocessing of STRIPS operators to discover conditions that cannot simultaneously hold in any legal state. Such ·conditions become indicators of failures . For example, inspection of the operator definitions reveals that no state can satisfy holding(X) and clear(X) for the same block X, since operators that · assert one delete the other. Knowledge gained by preprocessing the operators is used to prune planning states that satisfy two or more mutually inconsistent conditions.

FOO [Mostow 83a] refines a G&T search procedure into a heuristic search by using monotonically necessary conditions to prune partial paths, and by using monotonically sufficient conditions to reorder the search. While FOO uses static analysis to refine the procedure without ever executing it, Failsafe relies on executing the search to identify the conditions that actually lead to failure in practice. FOO uses domain knowledge to split tests into monotonic components so it can move them, while Failsafe lacks the ability to reformulate its tests. FOO mechanically applies the sequence of progr-am transformations that modifies the search procedure, but relies on a user to select the sequence. Unlike FOO, Failsafe is completely automatic.

PRODIGY learns search control knowledge from the failure of an entire subtree to produce a solution [Minton & Carbonell 87]. In contrast, ELF learns from a single failed path, though the resulting control knowledge is over-general for non-monotonic failures.

ELF's technique for backtracking to the closest node where the failure might be repaired resembles the dependency directed backtracking method used in the EL system [Stallman 77]. However, unlike Failsafe, EL does not generalize.

VII Conclusion

We have presented an implemented technique for learning useful search control knowledge from failures that occur during se·arch. Failsafe's performance improvement more than compensates for its learning overhead, even for small problems, and even when learning while doing.

We have shown how EBG can be used to learn from negative examples, not just positive ones. Learning from failure while problem-solving makes it possible to solve problems too complex to solve otherwise. However, learning from success seems to create more powerful cont.-ol knowledge, such as Soar's chunks for achieving goals in one step. Future research should compare and integrate methods for learning from success and failure.

Acknowledgments

We thank Chris Tong and Prasad Tadepalli for their excellent ideas during various stages of this work, Smadar Kedar-Cabelli for her Prolog implementation of EBG, Lou Steinberg for his continuing encouragement, and Steve Minton and an anonymous referee for their helpful comments.