Methods and apparatus for constraint satisfaction

Details Methods and apparatus for constraint satisfaction Methods and apparatus for constraint satisfaction

1996-02-22

1997-06-03

Downs, Robert W.

G06F 944, G06F 1518

Patent

active

056363281

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.

REFERENCES:
patent: 4835690 (1989-05-01), Gangarosa et al.
patent: 5228115 (1993-07-01), Natarojan
patent: 5249261 (1993-09-01), Natarajan
patent: 5267346 (1993-11-01), Maruyama
D.S. Johnson, C. H. Papdimmitrou, and M. Yannakakis, "How Easy is Local Search", Journal of Computer and System Sciences, vol. 37, pp. 79-100, 1988.
B. Selman, H. Levesque, and D. Mitchell, "A New Method for Solving Hard Satisfiability Problems", Proceedings of the Tenth National Conference on Artificial Intelligence, pp. 440-446, 1992.
J. Gu, "Efficient Local Search for Very Large-Scale Satisfiability Problems", Sigart Bulletin, vol. 3, No. 1, pp. 8-12, 1992.
S. Kirkpatrick, C. D. Gellett, and M. P. Vechi, "Optimization by Simulated Annealing", Science, vol. 220, pp. 621-630, 1983.
P. Morris, "The Breakout Method for Escaping From Local Minima", AAAI-93 & IAAI-93, Proceedings of the Eleventh National Conference on Artificial Intelligence, Washington, D.C., Jul. 1993.
B. Selman, H. Kautz, "An Empirical Study of Greedy Local Search of Satisfiability Testing", AAAI-93 & IAAI-93, Proceedings of the Eleventh National Conference on Artificial Intelligence, Washington, D.C., Jul. 1993.
C. J. Wang, E. P. K. Tsang, "Solving Constraint Satisfaction Problems Using Neural Networks", Second International Conference on Artificial Neural Networks, Nov. 18-20, 1991.
S. Selman, H. Levesque, D. Mitchell, "A New Method for Solving Hard Satisfiability Problems", AAAI-92, Proceedings Tenth National Conference on Artificial Intelligence, Jul. 12-16, 1992.
Maruyama et al, "Solving Combinatorial Constraint Satisfaction and Optimization Problems using Sufficient Conditions for Constraint Violation", Proc Int'l Symposium on AI, Nov. 13-15 1991, pp. 269-275.
Smith et al, "Combining Constraint Satisfaction and Local Improvement Algorithm to Construct Anaesthetists Rates" Proc 8th Conf on AI for Applications, Mar. 2-6, 1992, pp.106-112.
Wang et al, "Solving Constraint Satisfaction Problems Using Neural Networks" and Int'l Conf on Neural Networks, Nov. 18-20, 1991.
Miltal et al, "Dynamic Constraint Satisfaction Problems", Proc 8th Nat'l Conference on AI, vol. 1 pp. 25-32, Jul. 29-Aug. 3 1990.
Minton et al, "Solving Large Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method", Proc 8th Nat'l Conf on AI, vol. 1, pp. 17-24, Jul. 29-Aug. 3, 1990.
Selman et al, "A New Method for Solving Hard Satisfiability Problems", Proc 10th Nat'l Confon AI pp. 440-446, 1992.

Affiliated with

Also associated with

Rating

Methods and apparatus for constraint satisfaction does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and apparatus for constraint satisfaction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for constraint satisfaction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-398454