Min conflicts algorithm
Encyclopedia
The min conflicts algorithm is a search algorithm
to solve constraint satisfaction problem
s (CSP problems).
It assigns random values to all the variables of a CSP. Then it selects randomly a variable, whose value conflicts with any constraint of the CSP. Then it assigns to this variable the value with the minimum conflicts. If there are more than one minimum, it chooses one among them randomly. After that, a new iteration starts again until a solution is found or a preselected maximum number of iterations is reached.
Because a CSP can be interpreted as a local search problem
when all the variables have assigned a value (complete states), the min conflicts algorithm can be seen as a heuristic that chooses the state with the minimum number of conflicts.
inputs: csp, a constraint satisfaction problem
max_steps,the number of steps allowed before giving up
current<-- an initial assignment for csp
for i=1 to max_steps do
if current is a solution of csp then return current
var<-- a randomly chosen, conflicted variable from VARIABLES[csp]
value<-- the value v for var that minimizes CONFLICTS(var,v,current,csp)
set var = value in current
return failure
Although not specified in the algorithm, a good initial assignment can be critical for quickly approaching a solution. Use a greedy algorithm with some level of randomness and allow variable assignment to break constraints when no other assignment will suffice. The randomness helps min-conflicts avoid local minima created by the greedy algorithm's initial assignment. In fact, Constraint Satisfaction Problems that respond best to a min-conflicts solution do well where a greedy algorithm almost solves the problem. Map coloring problems do poorly with Greedy Algorithm as well as Min-Conflicts. Sub areas of the map tend to hold their colors stable and min conflicts cannot hill climb to break out of the local minimum. The CONFLICTS function counts the number of constraints violated by a particular object, given that the state of the rest of the assignment is known.
had known and reasoned about Constraint Satisfaction Problems for many years, it was not until the early 1990s that this process for solving large CSPs had been codified in algorithmic form. Early on, Mark Johnston of the Space Telescope Science Institute
looked for a method to schedule astronomical observations on the Hubble Space Telescope
. In the process, he created a neural network capable of solving a toy N-queens problem (for 1024 queens). Steven Minton and Andy Philips analyzed the neural network algorithm and separated it into two phases: (1) an initial assignment using a greedy algorithm and (2) a conflict minimization phases (later to be called "min-conflicts"). A paper was written and presented at AAAI-90; Philip Laird provided the mathematical analysis of the algorithm.
Subsequently, Mark Johnston and the STScI staff used min-conflicts to schedule astronomers' experiment time on the Hubble Space Telescope.
Min-Conflicts solves the N-Queens Problem by randomly selecting a column from the Chess board for queen reassignment. The algorithm searches each potential move for the number of conflicts (number of attacking queens), shown in each square. The algorithm moves the queen to the square with the minimum number of conflicts, breaking ties randomly. Note that the number of conflicts is generated by each new direction that a queen can attack from. If two queens would attack from the same direction (row, or diagonal) then the conflict is only counted once. Also note that if a queen is in a position in which a move would put it in greater conflict than its current position, it does not make a move. It follows that if a queen is in a state of minimum conflict, it does not have to move.
This algorithm's run time for solving N-Queens is independent of problem size. This algorithm will even solve the million-queens problem on average of 50 steps. This discovery and observations lead to a great amount of research in 1990 and began research on local search problems and the distinctions between easy and hard problems. N-Queens is easy for local search because solutions are densely distributed throughout the state space. It is also effective for hard problems. For example, it has been used to schedule observations for the Hubble Space Telescope
, reducing the time taken to schedule a week of observations from three weeks to around 10 minutes.
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
to solve constraint satisfaction problem
Constraint satisfaction problem
Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...
s (CSP problems).
It assigns random values to all the variables of a CSP. Then it selects randomly a variable, whose value conflicts with any constraint of the CSP. Then it assigns to this variable the value with the minimum conflicts. If there are more than one minimum, it chooses one among them randomly. After that, a new iteration starts again until a solution is found or a preselected maximum number of iterations is reached.
Because a CSP can be interpreted as a local search problem
Local search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
when all the variables have assigned a value (complete states), the min conflicts algorithm can be seen as a heuristic that chooses the state with the minimum number of conflicts.
Algorithm
function MIN-CONFLICTS(csp,max_steps) returns a solution or failureinputs: csp, a constraint satisfaction problem
max_steps,the number of steps allowed before giving up
current<-- an initial assignment for csp
for i=1 to max_steps do
if current is a solution of csp then return current
var<-- a randomly chosen, conflicted variable from VARIABLES[csp]
value<-- the value v for var that minimizes CONFLICTS(var,v,current,csp)
set var = value in current
return failure
Although not specified in the algorithm, a good initial assignment can be critical for quickly approaching a solution. Use a greedy algorithm with some level of randomness and allow variable assignment to break constraints when no other assignment will suffice. The randomness helps min-conflicts avoid local minima created by the greedy algorithm's initial assignment. In fact, Constraint Satisfaction Problems that respond best to a min-conflicts solution do well where a greedy algorithm almost solves the problem. Map coloring problems do poorly with Greedy Algorithm as well as Min-Conflicts. Sub areas of the map tend to hold their colors stable and min conflicts cannot hill climb to break out of the local minimum. The CONFLICTS function counts the number of constraints violated by a particular object, given that the state of the rest of the assignment is known.
History
Although Artificial Intelligence and Discrete OptimizationDiscrete optimization
Discrete optimization is a branch of optimization in applied mathematics and computer science.As opposed to continuous optimization, the variables used in the mathematical program are restricted to assume only discrete values, such as the integers.Two notable branches of discrete optimization...
had known and reasoned about Constraint Satisfaction Problems for many years, it was not until the early 1990s that this process for solving large CSPs had been codified in algorithmic form. Early on, Mark Johnston of the Space Telescope Science Institute
Space Telescope Science Institute
The Space Telescope Science Institute is the science operations center for the Hubble Space Telescope and for the James Webb Space Telescope...
looked for a method to schedule astronomical observations on the Hubble Space Telescope
Hubble Space Telescope
The Hubble Space Telescope is a space telescope that was carried into orbit by a Space Shuttle in 1990 and remains in operation. A 2.4 meter aperture telescope in low Earth orbit, Hubble's four main instruments observe in the near ultraviolet, visible, and near infrared...
. In the process, he created a neural network capable of solving a toy N-queens problem (for 1024 queens). Steven Minton and Andy Philips analyzed the neural network algorithm and separated it into two phases: (1) an initial assignment using a greedy algorithm and (2) a conflict minimization phases (later to be called "min-conflicts"). A paper was written and presented at AAAI-90; Philip Laird provided the mathematical analysis of the algorithm.
Subsequently, Mark Johnston and the STScI staff used min-conflicts to schedule astronomers' experiment time on the Hubble Space Telescope.
Example
A two step example of the Min-conflicts algorithm looking at the N-Queens Problem:Min-Conflicts solves the N-Queens Problem by randomly selecting a column from the Chess board for queen reassignment. The algorithm searches each potential move for the number of conflicts (number of attacking queens), shown in each square. The algorithm moves the queen to the square with the minimum number of conflicts, breaking ties randomly. Note that the number of conflicts is generated by each new direction that a queen can attack from. If two queens would attack from the same direction (row, or diagonal) then the conflict is only counted once. Also note that if a queen is in a position in which a move would put it in greater conflict than its current position, it does not make a move. It follows that if a queen is in a state of minimum conflict, it does not have to move.
This algorithm's run time for solving N-Queens is independent of problem size. This algorithm will even solve the million-queens problem on average of 50 steps. This discovery and observations lead to a great amount of research in 1990 and began research on local search problems and the distinctions between easy and hard problems. N-Queens is easy for local search because solutions are densely distributed throughout the state space. It is also effective for hard problems. For example, it has been used to schedule observations for the Hubble Space Telescope
Hubble Space Telescope
The Hubble Space Telescope is a space telescope that was carried into orbit by a Space Shuttle in 1990 and remains in operation. A 2.4 meter aperture telescope in low Earth orbit, Hubble's four main instruments observe in the near ultraviolet, visible, and near infrared...
, reducing the time taken to schedule a week of observations from three weeks to around 10 minutes.
External links
- Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method, Steven Minton, Mark D. Johnston, Andrew B. Philips, and Philip Laird. Presented at the Eighth National Conference on Artificial Intelligence (AAAI-90), Boston, Massachusetts
- A visualization of the N-Queens puzzle solved using the min-conflicts algorithm. Created by Yuval Baror.
- http://catalogue.nla.gov.au/Record/4057689 The min-conflicts heuristic microform : experiment and theoretical results / Steven Minton ... [et al.]. NASA, Ames Research Center, Artificial Intelligence Research Branch. Distributed to depository libraries in microfiche.