SEMANTICS AND IMPLEMENTATION OF KNOWLEDGE OPERATORS IN APPROXIMATE DATABASES

Diploma

Abstract

In order that epistemic formulas might be coupled with approximate databases, it is necessary to have a well-defined semantics for the knowledge operator and a method of reducing epistemic formulas to approximate formulas. In this thesis, two possible definitions of a semantics for the knowledge operator are proposed for use together with an approximate relational database:

     KI, based upon logical entailment (being the dominating notion of knowledge in literature); sound and complete rules for reduction to approximate formulas are explored and found not to be applicable to all formulas.

     KII, based upon algorithmic computability (in order to be practically feasible); the correspondence to KI on the one hand, and to the deductive capability of the agent on the other hand, is explored.

Also, an inductively defined semantics for a “know whether”-operator, Kw, is proposed and tested. Together with a database that supports it, this facilitates reasoning about knowledge not yet attained, which is of potential use in knowledge-based planning. Finally, an algorithm implementing the above is proposed, carried out using Java, and tested.

On knowledge in AI

An intelligent agent is an artificial system that is designed to work in some environment, receiving data from its surroundings and making its own decisions in an intelligent fashion, as a human might. Examples include vacuum cleaner robots, autonomous surveillance aircraft, and web spiders.

When one sets out to construct agents that are to function intelligently in complex environments, ultimately performing tasks such as a human might perform, it becomes necessary to make use of knowledge representation techniques. Rather than writing explicit programs (which must handle every possible situation) or training adaptive algorithms (using scenarios that may or may not resemble the actual situations the agent will find itself in), knowledge-based techniques instead allow designers to make the agent reason about its environment in abstract terms, just as a human would.

In this context, knowledge operators become instrumental. They make it possible to express what is known in a given application domain. Formulas containing knowledge operators are called epistemic formulas, “epistemic” meaning “knowledge theoretical”.