ABSTRACT This research involves a method for finding global maxima in constraint satisfaction networks. It is an annealing process butt unlike most otherst requires no annealing schedule. Temperature is instead determined locally by units at each updatet and thus all processing is done at the unit level. There are two major practical benefits to processing this way: 1) processing can continue in'bad t areas of the networkt while'good t areas remain stablet and 2) processing continues in the'bad t areast as long as the constraints remain poorly satisfied (i.e. it does not stop after some predetermined number of cycles). As a resultt this method not only avoids the kludge of requiring an externally determined annealing schedulet but it also finds global maxima more quickly and consistently than externally scheduled systems (a comparison to the Boltzmann machine (Ackley et alt 1985) is made).

Jared Leinbach Deparunent of Psychology Carnegie-Mellon University Pittsburgh, PA 15213 ABSTRACT This research involves a method for finding global maxima in constraint satisfaction networks. It is an annealing process butt unlike most otherst requires no annealing schedule. Temperature is instead determined locally by units at each updatet and thus all processing is done at the unit level. There are two major practical benefits to processing this way: 1) processing can continue in'badt areas of the networkt while'goodt areas remain stablet and 2) processing continues in the'bad t areast as long as the constraints remain poorly satisfied (i.e. it does not stop after some predetermined number of cycles). As a resultt this method not only avoids the kludge of requiring an externally determined annealing schedulet but it also finds global maxima more quickly and consistently than externally scheduled systems (a comparison to the Boltzmann machine (Ackley et alt 1985) is made).

The paper offers a systematic way of regrouping constraints into hierarchical structures capable of supporting search without backtracking. The method involves the formation and preprocessing of an acyclic database that permits a large variety of queries and local perturbations to be processed swiftly, either by sequential backtrack-free procedures, or by distributed constraint propagation processes.

In IJCAI-89, Vol. 1, pp. 290-296.

There are three existing connection::;t models in which network states are assigned a computational energy.

There are three existing connection::;t models in which network states are assigned a computational energy.

There are three existing connection::;t models in which network states are assigned a computational energy.

We propose an approach for meeting real-time constraints in AI systems that views (1) time as a resource that should be considered when making control decisions, (2) plans as ways of expressing control decisions, and (3) approximate processing as a way of satisfying time constraints that cannot be achieved through normal processing. In this approach, a real-time problem solver estimates the time required to generate solutions and their quality. This estimate permits the system to anticipate whether the current objectives will be met in time. The system can then take corrective actions and form lower-quality solutions within the time constraints. These actions can involve modifying existing plans or forming radically different plans that utilize only rough data characteristics and approximate knowledge to achieve a desired speedup. A decision about how to change processing should be situation dependent, based on the current state of processing and the domain-dependent solution criteria. We present preliminary experiments that show how approximate processing helps a vehicle-monitoring problem solver meet deadlines and outline a framework for flexibly meeting real-time constraints.

Many AI tasks can be formulated as constraint-satisfaction problems (CSP), i.e., the assignment of values to variables subject to a set of constraints. While some CSPs are hard, those that are easy can often be mapped into sparse networks of constraints which, in the extreme case, are trees. This paper identifies classes of problems that lend themselves to easy solutions, and develops algorithms that solve these problems optimally. The paper then presents a method of generating heuristic advice to guide the order of value assignments based on both the sparseness found in the constraint network and the simplicity of tree-structured CSPs. The advice is generated by simplifying the pending subproblems into trees, counting the number of consistent solutions in each simplified subproblem, and comparing these counts to decide among the choices pending in the original problem.

IEEE Computer, pages 100-109, January