Solving Temporal Constraints Using Neural Networks

Solving Temporal Constraints using Neural Networks Gage Klein and Malek Mouhoub Department of Math & Computer Science, University of Lethbridge 4401 University Drive, Lethbridge, Alberta, Canada, T1K 3M4 phone : (+1 403) 329 2557 fax : (+1 403) 329 2519 mouhoub,klein9
@cs.uleth.ca

Abstract There was a resurgent in research of neural nets during the late 70’s and 80’s due to advances made in learning algorithms for feed-forward and feedback networks. These advances, coupled with better computer technology, made it possible for practical applications of such networks to be made. In 1985, John Hopfield and David Tank first attempted using neural nets as an approximation method to solve optimization problems, mainly the Traveling Salesman Problem. Since then, there has been wide spread interest in applying neural nets to solve different types of optimization problems. In this paper we will mainly focus on using the Hopfield model to solve the Maximal Temporal Constraint Satisfaction Problem (MTCSP). An MTCSP is an optimization problem that consists of looking for a solution that satisfies the maximal number of temporal constraints. This can be the case of over constrained problems involving time constraints and where a complete solution does not exist, or those problems such as real time applications where a solution is needed by a given deadline. The quality of the solution (number of satisfied constraints) depends here on the time allocated for computation. Experimental comparison study of the method we propose and based on the Hopfield model with approximation methods based on local search is reported in this paper. The method based on the Hopfield model presents better results than the other methods in the case of over-constrained problems.

Keywords: Temporal Reasoning, Neural Networks, Hopfield Model, Optimization Problems, Planning and Scheduling.

1

Introduction

There was a resurgent in research of neural nets during the late 70’s and 80’s due to advances made in learning algorithms for feed-forward and feedback networks. These advances, coupled with better computer technology, made it possible for practical applications of such networks to be made. In 1985, John Hopfield and David Tank first attempted using neural nets as an approximation method to solve optimization problems, mainly the Traveling Salesman Problem. Since then, there has been wide spread interest in applying neural nets to solve different types of optimization problems. In this paper we will mainly focus on using the Hopfield model to solve the Maximal Temporal Constraint Satisfaction Problem (MTCSP). Before we define the MTCSP, let us introduce the notions of CSP and TCSP. A CSP (Constraint Satisfaction Problem)[1][2] [3][4] involves a list of variables defined on finite domains of values and a list of relations (constraints) between variables. A binary CSP is a CSP where the relations are binary. In order to represent and manage numeric and symbolic time information we have developed the model TemPro[5], extending the Interval Algebra defined by Allen[6] to handle numeric constraints. TemPro transforms any problem under qualitative and quantitative constraints into a binary CSP where constraints are disjunctions of Allen primitives[6] and variables, representing temporal events, are defined on domains of time intervals. We call this later problem a TCSP (Temporal Constraint

Satisfaction Problem)1 Solving a CSP (and hence a TCSP) consists of finding an assignment of a value from its domain to every variable, in such a way that every constraint is satisfied. In the case of over constrained problems or those problems, such as real time applications, where a solution is needed by a given deadline, looking for a complete solution is impossible of impractical. An alternative consists of partially solve the problem by looking for an assignment that satisfies the maximal number of constraints. This latter problem is called an MCSP (Maximal Constraint Satisfaction Problem)[8]. An MTCSP is an MCSP involving temporal constraints (as defined by our model TemPro). An MCSP (and hence an MTCSP) is an optimization problem where the objective function (quality of the solution) is the number of satisfied constraints. In a previous work[9][10], we have used exact and approximation methods to solve an MTCSP. The exact method is based on partial constraint satisfaction techniques[8]. Local consistency techniques and backtrack search methods we have used to solve the TCSP[5] were adapted to cope with, and take advantage of, the differences between partial and complete constraint satisfaction. The exact method is based on branch and bound techniques and has the advantage to provide a solution that is guaranteed to be optimal [9]. However, as we mentioned in [9][10], this method is impractical for large size problems and is in general useful to verify the optimality and, therefore, the quality of the solution returned by approximation methods. Approximation methods, on the other hand, do not guarantee the optimality of the solution provided but are obviously of interest when they provide near optimal solutions. In [10] we have compared different stochastic local search methods for solving MTCSPs. The experimental results showed that the Min-Conflict Random Walk method (MCRW) was the best one for solving under constraint and over constraint temporal problems.

In this paper, we will use the Hopfield model to solve an MTCSP. To evaluate the method based on the Hopfield model, experimental comparisons with the approximation methods we mentioned above have been performed on randomly generated MTCSPs. The results of this study show that the method based on the Hopfield model presents better results than the other methods in the case of over-constrained problems. The rest of the paper is organized as follows. In the next section we will present, through an example, our model TemPro for representing numeric and symbolic time information. Section 3 and 4 are dedicated respectively to the representation of numeric and symbolic time information using Neural Networks (the Hopfield model). In order to compare the performance in time of the method based on the Hopfield model and the other approximation methods based on local search, we did some experiments on temporal constraint problems randomly generated. The details of the experiments and the corresponding results results of these experiments are described in section 5. Concluding remarks are presented in section 6.

1 Note that TCSP was used in the literature to describe a model for representing problems involving numeric and symbolic constraints[7]. This latter approach is different from our method in the way numeric (and also symbolic) constraints are represented. See [5] for a comparison of the two methods.

2 This problem is basically taken from an example presented by Ligozat, Guesgen and Anger at the tutorial : Tractability in Qualitative Spatial and Temporal Reasoning, IJCAI’01. We have added numeric constraints for the purpose of our work.

2

CSP-based Representation of Numeric and Symbolic Constraints : the model TemPro

Consider the following typical temporal reasoning problem2 : Example 1 John, Mary and Wendy separately rode to the soccer game. It takes John 30 minutes, Mary 20 minutes and Wendy 50 minutes to get to the soccer game. John either started or arrived just as Mary started. John either started or arrived just as Wendy started. John left home between 7:00 and 7:10. Mary and

Wendy arrived together but started at different times. Mary arrived at work between 7:55 and 8:00. John’s trip overlapped the soccer game. Mary’s trip took place during the game or else the game took place during her trip. The soccer game starts at 7:30 and lasts 105 minutes. The above story includes numeric and qualitative information (words in boldface). There are four main events : John, Mary and Wendy are going to the soccer game respectively and the soccer game itself. Some numeric constraints specify the duration of the different events, e.g 20 minutes is the duration of Mary’s event. Other numeric constraints describe the temporal windows in which the different events occur. And finally, symbolic constraints state the relative positions between events e.g John’s trip overlapped the soccer game. Given these kind of information, one important task is to represent and reason about such knowledge and to answer queries such as : “is the above problem consistent ?”, “what are the possible times at which Wendy arrived at the soccer game ?”,  etc. To reach this goal, and using an extension of the Allen algebra [6] to handle numeric constraints, our model TemPro transforms a temporal problem involving numeric and symbolic information into a temporal constraint satisfaction problem (TCSP) including : 



a set of events  EV1    EVn  , each defined on a discrete domain standing for the set of possible occurrences (time intervals) in which the corresponding event can hold, and a set of binary constraints, each representing a qualitative disjunctive relation between a pair of events and thus restricting the values that the events can simultaneously take. A disjunctive relation involves one or more Allen primitives.

Figure 1 corresponds to the transformation of the temporal reasoning problem, we presented before, to a TCSP using the model TemPro. Information about the relative position between each

Relation X precedes Y X equals Y

Symbol P E

Inverse P E

X meets Y X overlaps Y

M O

M O

X during y

D

D

X starts Y

S

S

X finishes Y

F

F

Meaning XXX YYY XXX YYY XXXYYY XXXX YYYY XXX YYYYYY XXX YYYYY XXX YYYYY

Table 1: Allen primitives

pair of events is converted into a disjunction of Allen primitives. Indeed, Allen [6] has proposed 13 basic relations between time intervals : starts (S), during (D), meets (M), overlaps (O), finishes (F), precedes (P), their converses and the relation equals (E) (see table 1 for the definition of the 13 primitives). For example, the information “John either started or arrived just as Wendy started” is translated as follows : J S M  W. In the case where there is no information between a pair of events, the corresponding relation is represented by the disjunction of the 13 Allen primitives (since this constraint is not considered during the resolution process, it does not appear on the graph of constraint as it is the case in figure 1 concerning the relation between Wendy and the Soccer game). The domain of each event corresponding to the Set Of Possible Occurrences (we call it SOPO) that each event can take is generated given its earliest start time, latest end time, duration and the discretization step. In the case of Wendy’s event, since we do not have any information about the earliest and latest time, these parameters are set respectively to 0 and the constant horizon (time before which all events should be performed). After a symbolic numeric pre-process, these parameters are then set to 5 and 60 respectively.

[0, 40, 30, 1] {(0 30) .. (10 40)} J SM

M [35, 60, 20, 1] {(35 55) .. (40 60)} D D-

SM

F F-

O

W [5, 60, 50, 1] {(5 55) .. (10 60)}

Sc [30, 135, 105, 1] {(30 135)}

Figure 1: TCSP corresponding to the problem presented in example 1.

To represent an assignment of an interval to a particular event in terms of neural states, there should only be two neurons ’on’ while the rest of the neurons ’off’ for each given event. The two ’on’ neurons represent the start and end times of the event interval. The distance between them (number of neurons between the start and end time neurons) represents the duration. Let us consider the example presented in section 2. Using the neural network representation, the quantitative constraints corresponding to the 4 events John (J), Mary (M), Wendy (W) and the soccer game (Sc), and a possible solution to the problem, are illustrated by the following bidimensional array of neurons (see figure 2). 0

...

...

As we mentioned in the previous section, events are the temporal objects handled by our model TemPro. The quantitative constraint associated to each event is represented by the SOPO (finite Set of Possible Occurrences the event can take). In other words, the SOPO is the domain of values on which the event is defined. The SOPO corresponding the an event EVi is defined by the fourfold in fi  supi  di  si  where :  

in fi is the earliest start time of EVi ,



supi is the latest end time of EVi ,



di is the duration of EVi , and si is the discretization step of EVi .

To represent the SOPO in terms of neurons, a two-dimensional array is adequate. One axis depicts the time line; one neuron equates to one discretization step. The other axis represents an individual SOPO event. The choice of which axis should represent what will have no impact on the final outcome. Thus, in an attempt to follow standards, the x-axis was chosen to represent the time (discretization steps) and the y-axis was chose to represent the different SOPO events.

J

35

55

60

55

60

M

...

Events

3 Neural Representation of Numeric Constraints

40

30

5 ...

...

W

30

135 ...

...

Sg

Time Line Figure 2: Neural Representation of Numeric Constraints When dealing with the constraint and energy functions, the ’on’ state is considered to be 1 and the ’off’ state is considered to be 0. Each neuron ai j represents a time point i for a given neuron j. ai j can have only 2 possible values 0 or 1. The approach we use to satisfy the numeric constraints is essentially a Lagrangian relaxation of the constraints, i.e minimize the following energy function : F



α1C1  α2C2  αnCn

(1)

where : 

each Ci is a nonnegative penalty function representing a given constraint and such that Ci  0. 

i αi 

0.

In our case, F can be written as follows : F



αF1  βF2

(2)

where : 

F1 represents the fact that there should be exactly 2 activated neurons (equal to 1) per row. F! includes also the constraint forcing each neuron to have a digital value (0 or 1). n is the number of events and h is the constant horizon (time before which all events should be processed).

a neural representation for each of the 13 primitives (see table 1 for the definition of the 13 Allen primitives). Let us consider the functions begin and end returning respectively the start and end time of an event. The following energy functions represent properties between the end points of two events I and J.



n  h

∑

∑ ai j  2 2 

i 1 j  1

n

i 1 j  1



n  supi  di

∑ ∑

i  1 s  in fi

∑



F4

ai j  (3)



begin i #

ni k !

in fi " k " supi  di

di 



represents the fact : end i % end j 

F2 states that there are exactly 2 activated neurons per row within the temporal window of the event (EVi ) and distant by di . F2

F5

∑





in f j " k " sup j  d j

ais  ai s !

di 

2 2

represents the fact : begin j ( end i 

(4)

By comparing F1 and F2 with the following energy function of a Hopfield net H, we are able to find proper weights w and thresholds wo for the network.

ni k  n j k  2 



represents the fact : begin i % end j 

h

∑ ∑ ai j 1 



in fi " k " supi  di



F1 

∑



F3



F6

∑



in f j " k " sup j  d j



ni k !



n j k!

2

di 

2

begin j #

2

 

1 wij kl ai j akl 2 i∑ jkl 

∑ woij ai j

(5)

i j

If we multiply out the summations in (2) we obtain constant terms, linear terms proportional to one ai j and quadratic terms with two ai j ’s. The quadratic terms can be represented by connections wi j kl between the units, while the linear terms can be considered as thresholds.

dj 

2

2

(9)

represents the fact : end j & begin i '

end j ) end i  In the following we will present examples of the representation of the different Allen primitives between two events I and J. F 7 * ∑in fi " k " supi  di ni k  n j k  2  2  2  ∑in fi " k " supi  di ni k ! di  n j k ! di   2  represents the relation I E J. 





F 8 * ∑in fi " k " supi  di ni k ! di  n j k  2  2  ∑in fi ! di ! 1 " k " supi  d j ni k  n j k  2  1   ∑in fi " k " supi  di  1 ni k  n j k  2  1 

4 Neural Representation of Symbolic Constraints As we mentioned in section 2, in our model TemPro qualitative constraints are disjunctions of Allen primitives. Thus, to represent qualitative constraints using neural networks, we need to find

(8)

begin i $



H

(7)

begin j '

ni k  n j k  2 

n j k!

(6)

begin j $

end i &

dj 

2

represents the relation I S J.







F 9 * ∑in fi " k " supi  di ni k  n j k + 2  2  ∑in fi " k " supi  di ni k ! di  n j k ! di + 2  1   ∑in f j " k " sup j  d j ni k ! d j  n j k ! d j + 2  1  represents the relation I F J.

5 Experimentation In this section, we present comparative tests concerning different approximation algorithms based on local search, namely the Min-Conflict-Randomwalk (MCRW), the Steepest-Descent-RandomWalk (SDRW) and the Tabu Search methods, and the method based on neural networks using the Hopfield model. Tests were performed on consistent and inconsistent temporal constraint problems randomly generated, each having 200 variables. We use two criteria to compare the different approximation methods. The first one is the quality of the solution, i.e the minimum number of violated constraints of the solution provided by the method. The second criterion is the computing effort needed by an algorithm to find its best solution. This last criterion is measured by the running time in seconds required by each algorithm. The experiments were performed on a SUN SPARC Ultra 5 station. All the procedures are coded in C/C++. The performance of the approximation algorithms we use are greatly influenced by the following parameters : the size of the tabu list, tl size, in the case of tabu search; and the random walk probability, p, in the case of MCRW and SDRW. Preliminary tests determine the following ranges of parameter values : , ,

10 - tl size - 20 0 . 05 - p - 0 . 15

The generated problems are characterized by their tightness, which can be measured, as shown in [11], using the following definition : The tightness of a CSP problem is the fraction of all possible pairs of values from the domain of two variables that are not allowed by the constraint. The tightness depends in our case on the parameters Horizon / Nr and the density of the problem. In the case of inconsistent problems, we randomly pick a number of pairs belonging to an initial solution and add other randomly generated pairs of values. This is then considered as the initial incomplete solution that we will use to generate the list of qualitative and quantitative constraints as shown above.

5.1 Results Table 2 presents tests performed on consistent problems randomly generated. It gives a summary of the best results of MCRW, SDRW, Tabu Search and the Hopfield method for the chosen instances

in terms of quality of the solutions. The results correspond to the average running time and the quality of the solution provided by each method. To obtain these results, the algorithms were run 100 times on each instance, each run being given a maximum of 100,000 moves in the case of MCRW and 10,000 moves in the case of SDRW and Tabu Search. The parameter of each algorithm (the size of the Tabu list tl size and the random-walk probability p) is fixed according to the best value found during the parametric study. Note that, as mentioned in [10], the cost in time of a move in the case of Tabu Search and SDRW is equal to N times the cost of a move in the case of the MCRW method, where N is the number of variables (events). From the data of Table 2, when comparing the methods based on local search we can make the following observations. For under-constrained and middle-constrained problems, the MCRW method always provides the best results. It always founds a complete solution within a reasonable amount of time which is not the case of the other two methods. It is also faster than the other two methods to find solutions of the same quality. However for over-constrained problems (see last row of table 2) SDRW and Tabu Search have better performance. We can explain this by the fact that, for under constrained problems the initial configuration is in general of good quality. A complete solution can be obtained in this case by only changing the values of some conflicting variables (case of MCRW) instead of looking for the best neighbor which is much more expensive. When comparing the method based on the Hopfield model with the methods based on Local search, we notice that the former one provides better results for over-constrained problems. Table 3 presents tests performed on inconsistent problems randomly generated. For each instance, the exact method based on branch and bound techniques[9] was first performed in order to get the optimal solution (solution with the minimum number of violated constraints). The three algorithms are then run 100 times on each instance, each run being given a maximum of 100,000 moves in the case of MCRW and 10,000 moves in

Tightness of the problem 0.0002 0.0004 0.001 0.002 0.0037 0.006 0.03 0.044 0.045 0.058 0.1 0.14 0.35 0.44 0.55 0.67

p 5 5 5 5 5 5 15 5 5 5 5 5 5 5 5 5

qual 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 372

MCRW time 0.12 0.28 0.46 0.95 1.74 4 86 73 72 15 12 8.47 181 137 315 13945

# moves 5 18 28 68 145 255 3713 1633 1633 433 332 304 2009 1291 2505 100000

p 15 15 5 5 10 10 10 5 5 5 5 5 15 5 5 5

qual 0 0 0 0 0 0 33 4 4 74 0 0 0 220 0 0

SDRW time 2.67 4.95 8.24 11.22 126 33 33802 9595 9614 12333 34 39 66 8346 66 130

# moves 80 136 193 212 712 336 10000 10000 10000 10000 225 243 210 10000 210 297

tl size 10 10 10 10 10 10 10 15 10 15 10 10 20 10 10 10

Tabu Search qual time 0 0.17 1 185 0 0.6 2 294 1 270 3 286 12 349 25 355 16 376 12 364 0 112 0 112 68 714 63 646 0 262 0 422

# moves 4 5000 16 10000 10000 10000 10000 10000 10000 10000 211 193 10000 10000 190 224

Hopfield qual time 0 10.55 0 21.25 0 32.34 0 46 0 54 0 56 0 77 0 66 0 65 0 60 0 33 0 27 0 32 0 38 0 34 20 112

Table 2: Comparative results of Tabu search, MCRW, SDRW and the Hopfield model for consistent problems Tightness of the problem 0.0002 0.001 0.002 0.0037 0.006 0.03 0.044 0.1 0.14 0.35 0.44 0.67

p 5 5 5 5 5 15 5 5 5 5 5 5

qual 8 10 2 14 20 21 43 41 208 141 531 858

MCRW time # moves 0.44 32 0.7 53 0.68 43 1237 100000 5.83 425 190 5406 853 25 10 318 10.14 279 259 3015 105 271 156 315

p 15 5 5 10 10 10 5 5 5 15 5 5

qual 8 10 3 14 20 32 46 106 208 141 531 858

SDRW time 4.5 10.26 7.77 14.62 33 3663 4827 41 37 439 82 98

# moves 107 199 183 238 336 10000 10000 233 215 554 216 206

tl size 10 10 10 10 10 10 15 10 10 20 10 10

Tabu Search qual time # moves 8 0.28 6 11 242 5000 2 194 5000 18 230 5000 22 377 10000 85 341 10000 45 255 10000 91 25 230 230 22 197 141 201 415 531 48 195 924 58 224

Hopfield qual time 12 120 15 88 8 49 20 22 24 27 25 105 43 120 41 22 208 22 141 34 531 22 858 27

B Bound qual 8 10 2 14 20 21 43 41 208 141 531 858

Table 3: Comparative results of Tabu Search, MCRW, SDRW and the Hopfield model for non consistent problems the case of SDRW and tabu search. Quality values in boldface correspond to the best quality (optimal solution) found by the exact method. From table 3 we can make the same observations as for table 2 i.e the MCRW method is the algorithm of choice if we have to deal with underconstrained or middle-constrained problems. The effort made by SDRW and tabu search methods to look for the best neighbor helps only in the case of over constrained problems. As we can easily see, the Hopfield method is the best one for overconstrained problems. The Branch and Bound method is used here to check for the goodness of the approximation method.

6 Conclusion In this paper we have presented a method, based on the Hopfield model, to solve MTCSPs. An

MTCSP is an optimization problem consisting of looking for a solution that satisfies the maximal number of temporal constraints. This can be the case of over constrained problems involving time constraints and where a complete solution does not exist or those problems, such as real time applications, where a solution is needed by a given deadline. The quality of the solution (number of satisfied constraints) depends here on the time allocated for computation.

In order to evaluate the performance of the Hopfield method, experimental comparison with approximation methods based on local search have been performed. Results show that the Hopfield method presents better results for over constrained problems.

References [1] E. Tsang. Foundation of Constraint Satisfaction. Academic Press, 1994. [2] A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99–118, 1977. [3] A. K. Mackworth and E. Freuder. The complexity of some polynomial networkconsistency algorithms for constraint satisfaction problems. Artificial Intelligence, 25:65–74, 1985. [4] R.M. Haralick and G.L. Elliott. Increasing tree search efficiency for Constraint Satisfaction Problems. Artificial Intelligence, 14:263–313, 1980. [5] M. Mouhoub, F. Charpillet, and J.P. Haton. Experimental analysis of numeric and symbolic constraint satisfaction techniques for temporal reasoning. Constraints: An International Journal, 2:151–164, Kluwer Academic Publishers, 1998. [6] J.F. Allen. Maintaining knowledge about temporal intervals. CACM, 26(11):832–843, 1983. [7] I. Meiri. Combining qualitative and quantitative constraints in temporal reasoning. Artificial Intelligence, 87:343–385, 1996. [8] R. J. Wallace. Partial constraint satisfaction. Lecture Notes in Computer Science, 923:121–138, 1995. [9] M. Mouhoub. Reasoning about Numeric and Symbolic Time Information. In the Twelfth IEEE International Conference on Tools with Artificial Intelligence(ICTAI’2000), pages 164–172, Vancouver, 2000. IEEE Computer Society. [10] M. Mouhoub. Analysis of Approximation Algorithms for Maximal Temporal Constraint Satisfaction Problems. In The 2001 International Conference on Artificial Intelligence (IC-AI’2001), pages 165–171, Las Vegas, 2001.

[11] D. Sabin and E. C. Freuder. Contradicting conventional wisdom in constraint satisfaction. In Proc. 11th ECAI, pages 125–129, Amsterdam, Holland, 1994.