KLAP Seminar Home Page
Fall 2003

This is a weekly seminar which discusses issues related to the areas of logic and constraint programming, knowledge representation, and parallel processing. It is organized by members of the Knowledge representation, Logic, and Advanced Programming Laboratory (KLAP).
The seminar is open to everyone.

Time: Friday, 1:45 pm
Location: SH 124

Upcoming Seminar

There will be no more seminars in Fall 2003.
The seminar will resume in Spring 2004.

Schedule of talks

Previous Seminars

November 21, 2003

Abstract

The Open Agent Architecture (OAA), developed and user for several years at SRI International, makes it possible for software services to be provided through the cooperative efforts of distributed collections of autonomous agents. Communication and cooperation between agents are brokered by one or more facilitators, which are responsible for matching requests, from users and agents, with descriptions of the capabilities of other agents. Thus it is not generally required that a user or agent know the identities, locations, or number of other agents involved in satisfying a request. OAA is structured so as to minimize the effort involved in creating new agents and "wrapping" legacy applications, written in various languages and operating on various platforms; to encourage the reuse of exisiting agents; and to allow for dynamism and flexibility in the makeup of agent communities. Distinguishing feature of OAA as compared with related work include extreme flexibility in using facilitator-based provision of multimodal user interfaces; and built-in support for including the user as a privileged member of the agent community. This paper explains how agent-based systems are constructed with OAA. To provide technical context, we describe the motivations for its design, and situate its features within the relam of alternative software paradigms. A summary is given of OAA-based systems to date. The characteristics and use of each major component of OAA infrastructure are described, including the agent library, the Interagent Communication Language, capabilities declarations, service requests, facilitation, management of data repositories, and autonomous monitoring using triggers.

November 14, 2003

Abstract

In this paper we define a sequent calculus to formally specify, simulate, debug and verify security protocols. In our sequents we distinguish between the current knowledge of principals and the current global state of the session. Hereby, we can describe the operational semantics of principals and of an intruder in a simple and modular way. Furthermore, using proof theoretic tools like the analysis of permutability of rules, we are able to find efficient proof strategies that we prove complete for special classes of security protocols including Needham-Schroeder. Based on the results of this preliminary analysis, we have implemented a Prolog meta-interpreter which allows for rapid prototyping and for checking safety properties of security protocols, and we have applied it for nding error traces and proving correctness of practical examples.

November 7, 2003

October 31, 2003

Abstract

Parallel logic programming systems have been studied for more than a decade. Techniques and scheduling strategies for or-parallel systems have been established for systems that run on centralised memory architectures. As new parallel platforms such as clusters of workstations or clusters of PCs gain popularity, these techniques vastly studied for centralised memory systems may become obsolete and inefficient. In this work we study several scheduling strategies commonly used in orparallel systems designed for centralised memory architetcures. We simulate these strategies on different parallel environments in order to estimate the costs associated to these scheduling strategies in each environment. We use a benchmark set commonly studied by the or-parallel community. Our study concentrates on simulating top-most, bottommost, and left-most strategies while modelling costs associated to centralised and distributed memory architectures. We then implement our own strategy that selects best work based on the costs to move to a piece of work.

October 24, 2003

Abstract

Sensing (or knowledge producing) actions have been the topic of intensive research in reasoning about action and change and planning. Most of current approaches based on high-level description languages to reasoning actions concentrate on providing the solution to the frame problem for domains with Boolean fluents and sensing actions. Although the simplication to domains with Boolean fluents does not limit the expressiveness of the fluents, this solution is too cumbersome and not intuitive.

In this paper, we discuss the weakness of current action languages for sensing actions with respect to modeling domains with multi-valued fluents. To address this problem, we propose a language with sensing actions and multi-valued fluents, called AM_k, and provide a transition function based semantics for AM_k. We define the entailment relationship between action theories and queries in AM_k, denoted by AM_k. We discuss some complexity result about the planning problem in AM_k. Finally, we demonstrate the use of AM_k through examples from the literature.

October 17, 2003

Abstract

Disjunctive Logic Programming (DLP) is a very expressive formalism: it allows to express every property of finite structures that is decidable in the complexity class (NP^NP). Despite the high expressiveness of DLP, there are some simple properties, often arising in real-world applications, which cannot be encoded in a simple and natural manner. Among these, properties requiring to apply some arithmetic operators (like sum, times, count) on a set of elements satisfying some conditions, cannot be naturally expressed in DLP. To overcome this deficiency, in this paper authors extend DLP by aggregate functions. They formally define the semantics of the new language, named DLP(A). They show the usefulness of the new constructs on relevant knowledge-base problems. They analyze the computational complexity of DLP(A), showing that the addition of aggregates does not bring a higher cost in that respect. They provide an implementation of the DLP(A) language in DLV - the state-of-the-art DLP system - and report on experiments which confirm the usefulness of the proposed extension also for the efficiency of the computation.

October 10, 2003

One of the main reasons for them is that in many real-life problems, we are interested in the value of the physical quantity y that is difficult or even impossible to measure directly: e.g., the amount of oil in the well, or the distance to the galaxies. In such cases, we measure some other quantities xi that are in a known way connected with y (i.e., for which y=f(x1,...,xn)), and then use the results Xi of these measurements to compute the estimate Y=f(X1,...,Xn) for y. The corresponding data processing algorithm f can be very time-intensive, that is why we need computers to perform these computations.

The following problem is often overlooked in computing, but is of great importance in practice: Measurements are never absolutely precise, so there can be measurement errors; we usually know the guaranteed accuracy Di of each measurement. As a result, the only information that we have about the actual (unknown) value of xi is that xi belongs to the interval [xi]=[Xi-Di,Xi+Di]. We also know the algorithm f that transforms the values xi into the value of the desired quantity y. We want to know the interval of possible values of y.

Computations that solve this problem are called interval computations.

In 1981, it was proven that even for polynomial functions f, the problem of computing the range Y exactly is computationally intractable (NP-hard).

In this talk, we describe heuristic techniques that provide reasonably good estimates for the desired range, and show how these techniques can be used to solve optimization problems and other decision problems.

We also describe what happens if, in addition to the upper bound D on the measurement error X-x, we also have some additional information about the probabilities of different values of this error.