Methods and apparatus for constraint satisfaction
AssigneeLucent Technologies Inc.
InventorsHenry A. Kautz, Bart Selman
Life of this patent
Estimating the term…
Abstract
A technique for finding values which satisfy a set of constraints. The technique is used with local search procedures for finding such values and overcomes the tendency of such local search procedures to "get stuck" at local minima. The technique dynamically adds weight to constraints in the set which are not satisfied by the current set of values and uses the weights of the constraints to determine the next set of values to be used in the local search. In the disclosed embodiment, the technique is used in the GSAT greedy local search procedure. Also disclosed is a system for controlling a robot arm which uses the technique.
Claims12
An improved method of controlling a system whose operations on a physical entity are subject to constraints, the method including the steps of:
- finding values of variables in the constraints such that the values satisfy the constraints;
- and
- controlling the system using the values such that the constraints are not violated in the operations, and
- the improvement comprising, in the step of finding values of variables, the steps of:
- associating a weight with each constraint;
- and
- repeating the steps of
- using the weights to select at least one of the variables of the constraints whose value is to be altered to produce a current assignment of values to the variables, and
- dynamically updating the weight for each constraint according to whether the current assignment of values to the variables satisfies that constraint,
- the steps of using the weights and dynamically updating the weight being repeated until the current assignment of values to the variables satisfies all of the constraints.
Improved control apparatus for controlling a system whose operations on a physical entity are subject to constraints, the control apparatus including:
- means for finding values of variables in the constraints such that the values satisfy the constraints;
- and
- means for controlling the system using values the such that the constraints are not violated in the operations;
- the improvement comprising:
- in the means for finding values of variables,
- means for associating a weight with each constraint;
- and
- means for dynamically updating the weight for each constraint according to whether a current assignment of values to the variables satisfies that constraint;
- and wherein
- the means for finding values of variables uses the weights to select at least one variable of the constraints whose value is to be altered to produce a new current assignment of values.
Dependencies are inferred from the claim text.