19040663
Hybrid Knowledge Bases
Deductive databases that interact with, and are accessed by, reasoning agents in the real world (such as logic controllers in automated manufacturing, weapons guidance systems, aircraft landing systems, land-vehicle maneuvering systems, and air-traffic control systems) must have the ability to deal with multiple modes of reasoning. Specifically, the types of reasoning we are concerned with include, among others, reasoning about time, reasoning about quantitative relationships that may be expressed in the form of differential equations or optimization problems, and reasoning about numeric modes of uncertainty about the domain which the database seeks to describe. Such databases may need to handle diverse forms of data structures, and frequently they may require use of the assumption-based nonmonotonic representation of knowledge. A hybrid knowledge base is a theoretical framework capturing all the above modes of reasoning. The theory tightly unifies the constraint logic programming scheme of Jaffar and Lassez (1987), the generalized annotated logic programming theory of Kifer and Subrahmanian (1989), and the stable model semantics of Gelfond and Lifschitz (1988). New techniques are introduced which extend both the work on annotated logic programming and the stable model semantics.
723151
Secure mediated databases
With the evolution of the information superhighway, there is now an immense amount of information available in a wide variety of databases. Furthermore, users often have the ability to access legacy software packages developed by external sources. However, sometimes both the information provided by a data source, as well as one or more of the functions available through a software package may be sensitive-in such cases, organizations require that access by users be controlled. HERMES (HEterogeneous Reasoning and MEdiator System) is a platform that has been developed at the University of Maryland within which mediators may be designed and implemented. HERMES has already been used for a number of applications. In this paper, we provide a formal model of security in mediated systems. We then develop techniques that are sound and complete and respect security constraints of packages/databases participating in the mediated system. The security constraints described an this paper have been implemented, and we describe the existing implementation.
15968948
Amalgamating knowledge bases
The integration of knowledge for multiple sources is an importantaspect of automated reasoning systems. When different knowledge basesare used to store knowledge provided by multiple sources, we are facedwith the  problem of integrating multiple knowledge bases: Under thesecircumstances, we are also confronted with the prospect ofinconsistency. In this paper we present a uniform theoretical framework,based on <?Pub Fmt italic>annotated logics<?Pub Fmt /italic>, foramalgamating multiple knowledge bases when these knowledge bases(possibly) contain inconsistencies, uncertainties, and nonmonotonicmodes of negation. We show that annotated logics may be used, with somemodifications, to <?Pub Fmt italic>mediate<?Pub Fmt /italic> betweendifferent knowledge bases. The multiple knowledge bases are amalgamatedby a transformation of the individual knowledge bases into new annotatedlogic programs, together with the addition of a new axiom scheme. Wecharacterize the declarative semantics of such amalgamated knowledgebases and study how the semantics of the amalgam is related to thesemantics of the individual knowledge bases being combined.
<abstrbyl><?Pub Fmt italic>—Author's Abstract<?Pub Caret><?Pub Fmt /italic></abstrbyl>
629579
Query caching and optimization in distributed mediator systems
Query processing and optimization in mediator systems that access distributed non-proprietary sources pose many novel problems. Cost-based query optimization is hard because the mediator does not have access to source statistics information and furthermore it may not be easy to model the source's performance. At the same time, querying remote sources may be very expensive because of high connection overhead, long computation time, financial charges, and temporary unavailability. We propose a cost-based optimization technique that caches statistics of actual calls to the sources and consequently estimates the cost of the possible execution plans based on the statistics cache. We investigate issues pertaining to the design of the statistics cache and experimentally analyze various tradeoffs. We also present a query result caching mechanism that allows us to effectively use results of prior queries when the source is not readily available. We employ the novel invariants mechanism, which shows how semantic information about data sources may be used to discover cached query results of interest.
813161
Collaborative Multimedia Systems: Synthesis of Media Objects
When a group {/1,..., l/sub n/} of individuals wishes to collaboratively construct a complex multimedia document, the first requirement is that they be able to manipulate media-objects created by one another. For instance, if individual L/sub j/ wishes to access some media objects present at participant l/sub k/'s site, he must be able to: 1) retrieve this object from across the network, 2) ensure that the object is in a form that is compatible with the viewing/editing resources he has available at his node, and 3) ensure that the object has the desired quality (such as image size and resolution). Furthermore, he must be able to achieve these goals at the lowest possible cost. In this paper, we develop a theory of media objects, and present optimal algorithms for collaborative object sharing/synthesis of the sort envisaged above. We then extend the algorithms to incorporate quality constraints (such as image size) as well as distribution across multiple nodes. The theoretical model is validated by an experimental implementation that supports the theoretical results.
18315365
Towards a theory of collaborative multimedia
We develop a theory of media objects, and present optimal algorithms for collaborative synthesis of media objects. We then extend the algorithms to incorporate quality constraints (such as image size) as well as distribution across multiple nodes. The theoretical model is validated by an experimental implementation that supports the theoretical results.
18059666
IMPACT: the interactive Maryland platform for agents collaborating together
We describe a platform called IMPACT to support multiagent interactions. The platform provides a set of servers (yellow pages, thesaurus, registration, type, and interface) that facilitate agent interoperability in an application independent manner. In IMPACT agents have an associated set of service descriptions, specifying the services they provide. We develop an HTML-like language for such service descriptions. When an agent wishes to identify another agent that provides a service, the requested service must be matched, using a metric approach, against existing service descriptions. We provide a formal framework within which this may be done, and develop algorithms to compute the k nearest matches, as well as all matches within a given distance from the requested service. We report on experiments evaluating our algorithms with large data sets.
3198208
Heterogeneous Active Agents, I: Semantics
Abstract Over the years, many different agent programming languages have been proposed. In this paper, we propose a concept called Agent Programs using which, the way an agent should act in various situations can be declaratively specified by the creator of that agent. Agent Programs may be built on top of arbitrary pieces of software code and may be used to specify what an agent is obliged to do, what an agent may do, and what an agent may not do. In this paper, we define several successively more sophisticated and epistemically satisfying declarative semantics for agent programs. We further show that agent programs cleanly extend well understood semantics for logic programs, and thus are clearly linked to existing results on logic programming and nonmonotonic reasoning.
7868446
Heterogeneous Active Agents, II: Algorithms and Complexity
Abstract In Part I of this series of papers, we developed a language called Agent Programs for defining the operational behavior of software agents and defined a set of successively more satisfying (epistemically) semantics for such agent programs. In Part II of this series of papers, we study the computation price to be paid (in terms of complexity) for these epistemic desiderata. In particular, we develop algorithms for the above semantics, and describe results on their computational complexity. We show that (surprisingly) the reasonable status set semantics is the easiest to compute of the semantics proposed.
19021462
Combining Knowledge Bases Consisting of First Order Theories
Consider the construction of an expert system by encoding the knowledge of different experts. Suppose the knowledge provided by each expert is encoded into a knowledge base. Then the process of combining the knowledge of these different experts is an important and non-trivial problem. We study this problem here when the expert systems are considered to be first order theories. We present techniques for resolving inconsistencies in such knowledge bases. We also provide algorithms for implementing these techniques.
14637576
Heterogeneous active agents, III: Polynomially implementable agents
Abstract In “Heterogeneous active agents, I” (Eiter et al., 1999), two of the authors have introduced techniques to build agents on top of arbitrary data structures, and to “agentize” new/existing programs. They provided a series of successively more sophisticated semantics for such agent systems, and showed that as these semantics become epistemically more desirable, a computational price may need to be paid. In this paper, we identify a class of agents that are called weakly regular —this is done by first identifying a fragment of agent programs (Eiter et al., 1999) called weakly regular agent programs ( WRAP s for short). It is shown that WRAP s are definable via three parameters—checking for a property called “safety”, checking for a property called “conflict-freedom” and checking for a “deontic stratifiability” property. Algorithms for each of these are developed. A weakly regular agent is then defined in terms of these concepts, and a regular agent is one that satisfies an additional boundedness property. We then describe a polynomial algorithm that computes (under suitable assumptions) the reasonable status set semantics of regular agents—this semantics was identified by Eiter et al. (1999) as being epistemically most desirable. Though this semantics is coNP-complete for arbitrary agent programs (Eiter and Subrahmanian, 1999), it is polynomially computable via our algorithm for regular agents. Finally, we describe our implementation architecture and provide details of how we have implemented RAP s, together with experimental results.