Lucent Technologies Inc.

At&t Bell Laboratories

Bart Selman

Henry A Kautz

Allen E Milewski

Leonard Mark Canale

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.

Methods and apparatus for constraint satisfaction

Techniques for reducing the amount of junk e-mail received by a user of an e-mail system. A recipient description containing non-address information is added to an e-mail message. The user has an e-mail filter which has access to information which provides a model of the user. The e-mail filter uses the non-address information and the model information to determine whether the e-mail message should be provided to the user. The e-mail filter further has access to information which provides models of the user's correspondents. If the filter does not provide the message to the user, it uses the non-address information and the model information of the user's correspondents to determine who the message might be forwarded to. A sender of e-mail can also use the model information of the sender's correspondents together with the non-address information to determine who the message should be sent to. The techniques are used in a system for locating expertise.

Message filtering techniques

A technique for increasing the efficiency of a system such as an artificial intelligence system or a data base system in which a query is applied to a set of formulas. The technique creates an approximation of the set of formulas which is computationally more tractable than the original set. The original set is used to answer the query only if the approximation fails to provide the answer. The approximation is made by a compilation process which provides a series of ever-closer approximations. A given query is answered using the currently-closest approximation. The approximation may consist of a first set of formulas which is an upper bound (i.e. implied by) of the original set, and a second set which is a lower bound (i.e. implies) of the original set. In this case, the compilation process produces a series of increasing lower bounds and decreasing upper bounds until a greatest lower bound and a least upper bound are reached. Example applications of the technique are given for propositional languages, first order languages, languages based on definite clauses, and frame languages.

Growing community of inventors

Summit, NJ, United States of America

Bart Selman