\documentstyle[jair,twoside,11pt,theapa]{article} \input epsf %% at top of file \jairheading{1}{1993}{1-15}{6/91}{9/91} \ShortHeadings{Minimizing Conflicts: A Heuristic Repair Method}% {Minton, Philips, Johnston, \& Laird} \firstpageno{25} \begin{document} \title{Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems} \author{\name Steven Minton \email minton@ptolemy.arc.nasa.gov \\ \name Andy Philips \email philips@ptolemy.arc.nasa.gov \\ \addr Sterling Federal Systems, AI Research Branch, Mail Stop: 269-2,\\ NASA Ames Research Center, Moffett Field, CA 94035 USA \AND \name Mark D. Johnston \email johnston@stsci.edu \\ \addr Space Telescope Science Institute, 3700 San Martin Drive,\\ Baltimore, MD 21218 USA \AND \name Philip Laird \email laird@ptolemy.arc.nasa.gov \\ \addr NASA Ames Research Center, AI Research Branch, Mail Stop: 269-2,\\ Moffett Field, CA 94035 USA} \maketitle \begin{abstract} This paper describes a simple heuristic approach to solving large-scale constraint satisfaction and scheduling problems. In this approach one starts with an inconsistent assignment for a set of variables and searches through the space of possible repairs. The search can be guided by a value-ordering heuristic, the {\em min-conflicts heuristic}, that attempts to minimize the number of constraint violations after each step. The heuristic can be used with a variety of different search strategies. We demonstrate empirically that on the $n$-queens problem, a technique based on this approach performs orders of magnitude better than traditional backtracking techniques. We also describe a scheduling application where the approach has been used successfully. A theoretical analysis is presented both to explain why this method works well on certain types of problems and to predict when it is likely to be most effective. \end{abstract} \section{Introduction} \label{Introduction} One of the most promising general approaches for solving combinatorial search problems is to generate an initial, suboptimal solution and then to apply local {\em repair} heuristics. Techniques based on this approach have met with empirical success on many combinatorial problems, including the traveling salesman and graph partitioning problems \cite{papad}. Such techniques also have a long tradition in AI, most notably in problem-solving systems that operate by debugging initial solutions \cite{simmons-aaai88,hacker}. In this paper, we describe how this idea can be extended to constraint satisfaction problems (CSPs) in a natural manner. Most of the previous work on CSP algorithms has assumed a ``constructive'' backtracking approach in which a partial assignment to the variables is incrementally extended. In contrast, our method \cite{min-aaai} creates a complete, but inconsistent assignment and then repairs constraint violations until a consistent assignment is achieved. The method is guided by a simple ordering heuristic for repairing constraint violations: identify a variable that is currently in conflict and select a new value that minimizes the number of outstanding constraint violations. We present empirical evidence showing that on some standard problems our approach is considerably more efficient than traditional constructive backtracking methods. For example, on the $n$-queens problem, our method quickly finds solutions to the one million queens problem. We argue that the reason that repair-based methods can outperform constructive methods is because a complete assignment can be more informative in guiding search than a partial assignment. However, the utility of the extra information is domain dependent. To help clarify the nature of this potential advantage, we present a theoretical analysis that describes how various problem characteristics may affect the performance of the method. This analysis shows, for example, how the ``distance'' between the current assignment and solution (in terms of the minimum number of repairs that are required) affects the expected utility of the heuristic. The work described in this paper was inspired by a surprisingly effective neural network developed by Adorf and Johnston \cite{adorf,johnston} for scheduling astronomical observations on the Hubble Space Telescope. Our heuristic CSP method was distilled from an analysis of the network. In the process of carrying out the analysis, we discovered that the effectiveness of the network has little to do with its connectionist implementation. Furthermore, the ideas employed in the network can be implemented very efficiently within a symbolic CSP framework. The symbolic implementation is extremely simple. It also has the advantage that several different search strategies can be employed, although we have found that hill-climbing methods are particularly well-suited for the applications that we have investigated. We begin the paper with a brief review of Adorf and Johnston's neural network, and then describe our symbolic method for heuristic repair. Following this, we describe empirical results with the $n$-queens problem, graph-colorability problems and the Hubble Space Telescope scheduling application. Finally, we consider a theoretical model identifying general problem characteristics that influence the performance of the method. We include a second gratuitous citation to ourselves to illustrate a short citation \shortcite{min-aaai}. \section{Previous Work: The GDS Network} \label{network} By almost any measure, the Hubble Space Telescope scheduling problem is a complex task \cite{mj-early,sam}. Between ten thousand and thirty thousand astronomical observations per year must be scheduled, subject to a great variety of constraints including power restrictions, observation priorities, time-dependent orbital characteristics, movement of astronomical bodies, stray light sources, etc. Because the telescope is an extremely valuable resource with a limited lifetime, efficient scheduling is a critical concern. An initial scheduling system, developed using traditional programming methods, highlighted the difficulty of the problem; it was estimated that it would take over three weeks for the system to schedule one week of observations. As described in section \ref{results}, this problem was remedied by the development of a successful constraint-based system to augment the initial system. At the heart of the constraint-based system is a neural network developed by Adorf and Johnston, the Guarded Discrete Stochastic (GDS) network, which searches for a schedule \cite{adorf,johnston}. From a computational point of view the network is interesting because Adorf and Johnston found that it performs well on a variety of tasks, in addition to the space telescope scheduling problem. For example, the network performs significantly better on the $n$-queens problem than methods that were previously developed. The $n$-queens problem requires placing $n$ queens on an $n \times n$ chessboard so that no two queens share a row, column or diagonal. The network has been used to solve problems of up to 1024 queens, whereas most heuristic backtracking methods encounter difficulties with problems one-tenth that size \cite{stones}. The GDS network is a modified Hopfield network \cite{hopfield}. In a standard Hopfield network, all connections between neurons are symmetric. In the GDS network, the main network is coupled asymmetrically to an auxiliary network of {\em guard neurons} which restricts the configurations that the network can assume. This modification enables the network to rapidly find a solution for many problems, even when the network is simulated on a serial machine. Unfortunately, convergence to a stable configuration is no longer guaranteed. Thus the network can fall into a local minimum involving a group of unstable states among which it will oscillate. In practice, however, if the network fails to converge after some number of neuron state transitions, it can simply be stopped and started over. To illustrate the network architecture and updating scheme, let us consider how the network is used to solve binary constraint satisfaction problems. A problem consists of $n$ variables, $X_{1}\ldots X_{n}$, with domains $D_{1}\ldots D_{n}$, and a set of binary constraints. Each constraint $C_{\alpha}(X_{j},X_{k})$ is a subset of $D_{j} \times D_{k}$ specifying incompatible values for a pair of variables. The goal is to find an assignment for each of the variables which satisfies the constraints. (In this paper we only consider the task of finding a single solution, rather than that of finding all solutions.) To solve a CSP using the network, each variable is represented by a separate set of neurons, one neuron for each of the variable's possible values. Each neuron is either ``on'' or ``off'', and in a solution state, every variable will have exactly one of its corresponding neurons ``on'', representing the value of that variable. Constraints are represented by inhibitory (i.e., negatively weighted) connections between the neurons. To insure that every variable is assigned a value, there is a guard neuron for each set of neurons representing a variable; if no neuron in the set is on, the guard neuron will provide an excitatory input that is large enough to turn one on. (Because of the way the connection weights are set up, it is unlikely that the guard neuron will turn on more than one neuron.) The network is updated on each cycle by randomly picking a set of neurons that represents a variable, and flipping the state of the neuron in that set whose input is {\em most inconsistent} with its current output (if any). When all neurons' states are consistent with their input, a solution is achieved. To solve the $n$-queens problem, for example, each of the $n \times n$ board positions is represented by a neuron whose output is either one or zero depending on whether a queen is currently placed in that position or not. (Note that this is a local representation rather than a distributed representation of the board.) If two board positions are inconsistent, then an inhibiting connection exists between the corresponding two neurons. For example, all the neurons in a column will inhibit each other, representing the constraint that two queens cannot be in the same column. For each row, there is a guard neuron connected to each of the neurons in that row which gives the neurons in the row a large excitatory input, enough so that at least one neuron in the row will turn on. The guard neurons thus enforce the constraint that one queen in each row must be on. As described above, the network is updated on each cycle by randomly picking a row and flipping the state of the neuron in that row whose input is most inconsistent with its current output. A solution is realized when the output of every neuron is consistent with its input. \section{Why does the GDS Network Perform So Well?} \label{mv-heuristic} Our analysis of the GDS network was motivated by the following question: ``Why does the network perform so much better than traditional backtracking methods on certain tasks''? In particular, we were intrigued by the results on the $n$-queens problem, since this problem has received considerable attention from previous researchers. For $n$-queens, Adorf and Johnston found empirically that the network requires a linear number of transitions to converge. Since each transition requires linear time, the expected (empirical) time for the network to find a solution is $O(n^2)$. To check this behavior, Johnston and Adorf ran experiments with $n$ as high as 1024, at which point memory limitations became a problem.\footnote{The network, which is programmed in Lisp, requires approximately 11 minutes to solve the 1024 queens problem on a TI Explorer II. For larger problems, memory becomes a limiting factor because the network requires approximately $O(n^{2})$ space. (Although the number of connections is actually $O(n^{3})$, some connections are computed dynamically rather than stored).} \vspace*{-0.05in} \subsection{Nonsystematic Search Hypothesis} \vspace*{-0.05in} Initially, we hypothesized that the network's advantage came from the nonsystematic nature of its search, as compared to the systematic organization inherent in depth-first backtracking. There are two potential problems associated with systematic depth-first search. First, the search space may be organized in such a way that poorer choices are explored first at each branch point. For instance, in the $n$-queens problem, depth-first search tends to find a solution more quickly when the first queen is placed in the center of the first row rather than in the corner; apparently this occurs because there are more solutions with the queen in the center than with the queen in the corner \cite{stones}. Nevertheless, most naive algorithms tend to start in the corner simply because humans find it more natural to program that way. However, this fact by itself does not explain why nonsystematic search would work so well for $n$-queens. A backtracking program that randomly orders rows (and columns within rows) performs much better than the naive method, but still performs poorly relative to the GDS network. \begin{figure} \begin{center} \setlength{\unitlength}{0.010in} \begin{picture}(575,170)(15,465) \put(255,480){\circle{10}} \put(105,510){\circle{10}} \put(205,510){\circle{10}} \put( 95,510){\circle{10}} \put(193,509){\circle{10}} \put(115,510){\circle{10}} \put(215,510){\circle{10}} \put(510,510){\circle{10}} \put(429,510){\circle{10}} \put(469,510){\circle{10}} \put(390,510){\circle{10}} \put(550,510){\circle{10}} \put(350,510){\circle{10}} \put(255,550){\line( 1,-1){ 40}} \put(255,550){\line( 1,-2){ 20}} \put(255,550){\line( 0,-1){ 40}} \put(225,550){\line( 1,-2){ 20}} \put(225,550){\line( 1,-4){ 10}} \put(225,550){\line( 0,-1){ 40}} \put(205,550){\line( 1,-4){ 10}} \put(205,550){\line( 0,-1){ 40}} \put(205,550){\line(-1,-4){ 10}} \put(105,550){\line( 1,-4){ 10}} \put(105,550){\line( 0,-1){ 40}} \put(105,550){\line(-1,-4){ 10}} \put( 85,550){\line( 0,-1){ 40}} \put( 85,550){\line(-1,-4){ 10}} \put( 85,550){\line(-1,-2){ 20}} \put( 55,550){\line( 0,-1){ 40}} \put( 55,550){\line(-1,-2){ 20}} \put( 55,550){\line(-1,-1){ 40}} \put(215,590){\line( 1,-1){ 40}} \put(215,590){\line( 1,-4){ 10}} \put(175,590){\line( 3,-4){ 30}} \put(175,590){\line( 0,-1){ 40}} \put(135,590){\line( 0,-1){ 40}} \put(135,590){\line(-3,-4){ 30}} \put( 95,590){\line(-1,-4){ 10}} \put( 95,590){\line(-1,-1){ 40}} \put(155,630){\line( 1,-2){ 20}} \put(155,630){\line( 3,-2){ 60}} \put(155,630){\line(-1,-2){ 20}} \put(155,630){\line(-3,-2){ 60}} \put(135,550){\line(-1,-4){ 10}} \put(135,550){\line( 1,-4){ 10}} \put(175,550){\line( 1,-4){ 10}} \put(175,550){\line(-1,-4){ 10}} \put(175,550){\line( 0,-1){ 40}} \put(135,550){\line( 0,-1){ 40}} \put(430,550){\line( 0,-1){ 40}} \put(470,550){\line( 0,-1){ 40}} \put(470,550){\line(-1,-4){ 10}} \put(470,550){\line( 1,-4){ 10}} \put(430,550){\line( 1,-4){ 10}} \put(430,550){\line(-1,-4){ 10}} \put(450,630){\line(-3,-2){ 60}} \put(450,630){\line(-1,-2){ 20}} \put(450,630){\line( 3,-2){ 60}} \put(450,630){\line( 1,-2){ 20}} \put(390,590){\line(-1,-1){ 40}} \put(390,590){\line(-1,-4){ 10}} \put(430,590){\line(-3,-4){ 30}} \put(430,590){\line( 0,-1){ 40}} \put(470,590){\line( 0,-1){ 40}} \put(470,590){\line( 3,-4){ 30}} \put(510,590){\line( 1,-4){ 10}} \put(510,590){\line( 1,-1){ 40}} \put(350,550){\line(-1,-1){ 40}} \put(350,550){\line(-1,-2){ 20}} \put(350,550){\line( 0,-1){ 40}} \put(380,550){\line(-1,-2){ 20}} \put(380,550){\line(-1,-4){ 10}} \put(380,550){\line( 0,-1){ 40}} \put(400,550){\line(-1,-4){ 10}} \put(400,550){\line( 0,-1){ 40}} \put(400,550){\line( 1,-4){ 10}} \put(500,550){\line(-1,-4){ 10}} \put(500,550){\line( 0,-1){ 40}} \put(500,550){\line( 1,-4){ 10}} \put(520,550){\line( 0,-1){ 40}} \put(520,550){\line( 1,-4){ 10}} \put(520,550){\line( 1,-2){ 20}} \put(550,550){\line( 0,-1){ 40}} \put(550,550){\line( 1,-2){ 20}} \put(550,550){\line( 1,-1){ 40}} \put(270,475){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt = solution}}} \end{picture} \end{center} \caption{Solutions Clustered vs. Solutions Evenly Distributed} \label{shotgun} \end{figure} The second potential problem with depth-first search is more significant and more subtle. As illustrated by figure \ref{shotgun}, a depth-first search can be a disadvantage when solutions are not evenly distributed throughout the search space. In the tree at the left of the figure, the solutions are clustered together. In the tree on the right, the solutions are more evenly distributed. Thus, the average distance between solutions is greater in the left tree. In a depth-first search, the average time to find the first solution increases with the average distance between solutions. Consequently depth-first search performs relatively poorly in a tree where the solutions are clustered, such as that on the left \cite{ginsberg,langley}. In comparison, a search strategy which examines the leaves of the tree in random order is unaffected by solution clustering. We investigated whether this phenomenon explained the relatively poor performance of depth-first search on $n$-queens by experimenting with a randomized search algorithm, called a Las Vegas algorithm \cite{brassard}. The algorithm begins by selecting a path from the root to a leaf. To select a path, the algorithm starts at the root node and chooses one of its children with equal probability. This process continues recursively until a leaf is encountered. If the leaf is a solution the algorithm terminates, if not, it starts over again at the root and selects a path. The same path may be examined more than once, since no memory is maintained between successive trials. The Las Vegas algorithm does, in fact, perform better than simple depth-first search on $n$-queens \cite{brassard}. However, the performance of the Las Vegas algorithm is still not nearly as good as that of the GDS network, and so we concluded that the systematicity hypothesis alone cannot explain the network's behavior. \subsection{Informedness Hypothesis} Our second hypothesis was that the network's search process uses information about the current assignment that is not available to a constructive backtracking program. 's use of an iterative improvement strategy guides the search in a way that is not possible with a standard backtracking algorithm. We now believe this hypothesis is correct, in that it explains why the network works so well. In particular, the key to the network's performance appears to be that state transitions are made so as to reduce the number of outstanding inconsistencies in the network; specifically, each state transition involves flipping the neuron whose output is most inconsistent with its current input. From a constraint satisfaction perspective, it is as if the network reassigns a value for a variable by choosing the value that violates the fewest constraints. This idea is captured by the following heuristic: {\small \begin{quote} {\bf Min-Conflicts heuristic:}\\ {\em Given:} A set of variables, a set of binary constraints, and an assignment specifying a value for each variable. Two variables {\em conflict} if their values violate a constraint.\\ {\em Procedure:} Select a variable that is in conflict, and assign it a value that minimizes the number of conflicts. (Break ties randomly.) \end{quote} } We have found that the network's behavior can be approximated by a symbolic system that uses the min-conflicts heuristic for hill climbing. The hill-climbing system starts with an initial assignment generated in a preprocessing phase. At each choice point, the heuristic chooses a variable that is currently in conflict and reassigns its value, until a solution is found. The system thus searches the space of possible assignments, favoring assignments with fewer total conflicts. Of course, the hill-climbing system can become ``stuck'' in a local maximum, in the same way that the network may become ``stuck'' in a local minimum. In the next section we present empirical evidence to support our claim that the min-conflicts approach can account for the network's effectiveness. There are two aspects of the min-conflicts hill-climbing method that distinguish it from standard CSP algorithms. First, instead of incrementally constructing a consistent partial assignment, the min-conflicts method {\em repairs} a complete but inconsistent assignment by reducing inconsistencies. Thus, it uses information about the current assignment to guide its search that is not available to a standard backtracking algorithm. Second, the use of a hill-climbing strategy rather than a backtracking strategy produces a different style of search. \begin{figure} {\small {\bf \begin{verbatim} Procedure INFORMED-BACKTRACK (VARS-LEFT VARS-DONE) If all variables are consistent, then solution found, STOP. Let VAR = a variable in VARS-LEFT that is in conflict. Remove VAR from VARS-LEFT. Push VAR onto VARS-DONE. Let VALUES = list of possible values for VAR in ascending order according to number of conflicts with variables in VARS-LEFT. For each VALUE in VALUES, until solution found: If VALUE does not conflict with any variable that is in VARS-DONE, then Assign VALUE to VAR. Call INFORMED-BACKTRACK(VARS-LEFT VARS-DONE) end if end for end procedure Begin program Let VARS-LEFT = list of all variables, each assigned an initial value. Let VARS-DONE = nil Call INFORMED-BACKTRACK(VARS-LEFT VARS-DONE) End program \end{verbatim} } } \caption{Informed Backtracking Using the Min-Conflicts Heuristic} \label{iback} \end{figure} \subsubsection{Repair-Based Search Strategies} (This is a example of a third level section.) Extracting the method from the network enables us to tease apart and experiment with its different components. In particular, the idea of repairing an inconsistent assignment can be used with a variety of different search strategies in addition to hill climbing. For example, we can backtrack through the space of possible repairs, rather than using a hill-climbing strategy, as follows. Given an initial assignment generated in a preprocessing phase, we can employ the min-conflicts heuristic to order the choice of variables and values to consider, as described in figure \ref{iback}. Initially, the variables are all on a list of {\sc vars-left}, and as they are repaired, they are pushed onto a list of {\sc vars-done}. The algorithm attempts to find a sequence of repairs, such that no variable is repaired more than once. If there is no way to repair a variable in {\sc vars-left} without violating a previously repaired variable (a variable in {\sc vars-done}), the algorithm backtracks. Notice that this algorithm is simply a standard backtracking algorithm augmented with the min-conflicts heuristic to order its choice of which variable and value to attend to. This illustrates an important point. The backtracking repair algorithm incrementally extends a consistent partial assignment (i.e., {\sc vars-done}), as does a constructive backtracking program, but in addition, uses information from the initial assignment (i.e., {\sc vars-left}) to bias its search. Thus, it is a type of {\em informed backtracking}. We still characterize it as repair-based method since its search is guided by a complete, inconsistent assignment. \section{Experimental Results} \label{results} [section ommitted] \section{A Theoretical Model} \label{analysis} [section ommitted] \section{Discussion} [section ommitted] \acks{The authors wish to thank Hans-Martin Adorf, Don Rosenthal, Richard Franier, Peter Cheeseman and Monte Zweben for their assistance and advice. We also thank Ron Musick and our anonymous reviewers for their comments. The Space Telescope Science Institute is operated by the Association of Universities for Research in Astronomy for NASA. } \appendix \section*{Appendix A. Probability Distributions for N-Queens} [section ommitted] \vskip 0.2in \bibliography{sample} \bibliographystyle{theapa} \end{document}