V. R. Lesser

JAIR Journal 2006 Journal Article

Asynchronous Partial Overlay: A New Algorithm for Solving Distributed Constraint Satisfaction Problems

• R. Mailler
• V. R. Lesser

Distributed Constraint Satisfaction (DCSP) has long been considered an important problem in multi-agent systems research. This is because many real-world problems can be represented as constraint satisfaction and these problems often present themselves in a distributed form. In this article, we present a new complete, distributed algorithm called Asynchronous Partial Overlay (APO) for solving DCSPs that is based on a cooperative mediation process. The primary ideas behind this algorithm are that agents, when acting as a mediator, centralize small, relevant portions of the DCSP, that these centralized subproblems overlap, and that agents increase the size of their subproblems along critical paths within the DCSP as the problem solving unfolds. We present empirical evidence that shows that APO outperforms other known, complete DCSP techniques.

AAAI Conference 1980 Conference Paper

Quantifying and Simulating the Behavior of Knowledge-Based Interpretation Systems

• V. R. Lesser

IJCAI Conference 1977 Conference Paper

A Retrospective View of the Hearsay-II Architecture

• V. R. Lesser
• L D. Erman

The Hearsay model has heen presented as a paradigm for attacking errorful knowledge-intensive problems requiring multiple, cooperating knowledge sources. The Hearsay-II architecture is the latest attempt to explore the model. This paper describes experiences gained while successfully applying this architecture to the problem of speech understanding. The major conclusions are: 1. The paradigm of viewing problem solving in terms of hypothesize-and-test actions distributed among distinct representations of the problem has been shown to be computationally feasible. 2. A global working memory (the "blackboard"), in which the distinct representations are integrated in a uniform manner, has made it convenient to construct and integrate the individual sources of knowledge needed for the problem solution. 3. The use of a uniform data-directed structure for controlling knowledge-source activity has made the system easy to understand and modify. 4. A solution has been demonstrated to the problem of focusof-attention in this type of control environment. This solution does not need to be modified when the sources of knowledge in the system are changed.

IJCAI Conference 1977 Conference Paper

W. A. Woods Focus of Attention in the Hearsay-II Speech Understanding System

• F. Hayes-Roth
• V. R. Lesser