Knowledge Representation Techniques

The basis for the material in this book centers around research done in an ongoing long-term project which focuses on the development of highly autonomous unmanned aerial vehicle systems.¹ The actual platform which serves as a case study for the research in this book will be described in detail later in this chapter. Before doing that, a brief background of the motivations behind this research will be provided. One of the main research topics in the project is knowledge representation and reasoning and its use in Uav platforms. A very strong constraint has been placed on the nature of research done in the project where theoretical results, to the greatest extent possible, should serve as a basis for tractable reasoning mechanisms for use in a fully deployed autonomous Uav operating under soft real-time constraints associated with the types of mission scenarios envisioned. Considering that much of the work with knowledge representation in this context focuses on application domains where one can only hope for an incomplete characterization of such domains, this methodological constraint has proven to be quite challenging since, in essence, the focus is on tractable approximate and nonmonotonic reasoning systems. As is well known, until recently, nonmonotonic formalisms have had a notorious reputation for lack of tractable and scalable reasoning systems. At an early stage, a decision was made to investigate a number of standard nonmonotonic reasoning approaches and their combination with approximate reasoning techniques based on the use of rough set theory, or at the very least, guided by intuitions from rough set theory. In addition, a decision was also made to deal seriously with the sense/reasoning gap associated with most state-of-the-art robotic systems where it is often the case that high-level reasoning systems are not strongly grounded in the sensory data continually generated by sensor platforms.

We define the syntax of various logical languages using Bnf notation with some commonly used additions. Elements (words) of the defined language are called terminal symbols. Syntactic categories, i.e., sets of well-formed expressions are represented by non-terminal symbols and denoted by <Name>, where Name is the name of a category. Syntactic categories are defined over non-terminal and terminal symbols using rules of the form:

The methodology we propose and develop in this book is founded on the concept of rough sets. In many AI applications one faces the problem of representing and processing incomplete, imprecise, and approximate data. Many of these applications require the use of approximate reasoning techniques. Before we introduce rough sets formally, let us begin with an intuitive example where representation of approximate data and reasoning with it is an essential component in the modeling process.

Relational and deductive databases provide basic tools for storing, querying and manipulating data. From the point of view of knowledge engineering, databases provide a fundamental layer on which other representation may be built. The choice of the underlying tools is then extremely important and seriously influences further use of the knowledge engineering techniques. In this chapter we sketch some possible choices concerning deductive database solutions. Let us start by introducing some basic definitions.

Traditional logics are monotonic, i.e., adding new premises (axioms) will never invalidate previously inferred conclusions (theorems), or, equivalently, the set of conclusions non-decreases monotonically with the set of premises. Formally, a logic is monotonic if and only if it satisfies the condition that for any sets of premises S and S^′,

Consider an autonomous system such as a ground robot or an unmanned aerial vehicle operating in a highly complex and dynamic environment. For systems of this sort to function in an intelligent and robust manner, it is useful to have both deliberative and reactive capabilities. Such systems combine the use of reactive and deliberative capabilities in achieving task goals. Reactive capabilities are necessary so the system can react to contingencies which arise unexpectedly and demand immediate response with little room for deliberation as to what the best response should be. Deliberative capabilities are useful in the sense that internal representations of aspects of the system’s operational environment can be used to predict the course of events in the near or intermediate future. These predictions can then be used to determine more selective actions or better responses in the present which potentially save the system time, effort and resources in the course of achieving task goals.

This chapter presents a framework for specifying, constructing, and managing a particular class of approximate knowledge structures for use with intelligent artifacts, ranging from simpler devices such as personal digital assistants to more complex ones such as unmanned aerial vehicles. The basic structure for the concepts presented is that of an approximation transducer which takes approximate relations as input, and generates a (possibly more abstract) approximate relation as output. This is done by combining the approximate input relations with a crisp local logical theory representing dependencies between the input and output relations.

In the case of large data sets and knowledge databases one of the major concerns is the ability to react to events or queries in a reasonable and acceptable time. In particular, any real-time reasoning process has to be highly efficient. On the other hand, there is a trade-off between the accuracy of data/knowledge representation and effectiveness of querying knowledge databases and reasoning. In consequence, there is also a trade-off between the accuracy of data/knowledge representation and the response time of autonomous agents reacting on occurring events.

Knowledge engineering often involves the development of modeling tools and inference mechanisms (both standard and non-standard) which are targeted for use in practical applications, where expressiveness in representation must be traded off for efficiency in use. Some representative examples of such applications would be the structuring and querying of knowledge on the semantic web, or the representation and querying of epistemic states used with softbots, robots or smart devices. In these application areas, declarative representations of knowledge enhance the functionality of such systems and also provide a basis for insuring the pragmatic properties of modularity and incremental composition. On the other hand, the mechanisms developed should be tractable, but at the same time, expressive enough to represent such aspects as default reasoning, or approximate or incomplete representations of the environments in which the entities in question are embedded or used, be they virtual or actual.

In this chapter, we formalize a subset of default logic using the Cake method.¹ The goal of this chapter is to do a case study showing how the Cake method can be used to model a particular type of reasoning commonly used in knowledge representation and important in many applications. This will be done by representing two basic versions of default logic: rough default logic and rough default logic with strong prerequisites. The main difference between the two versions that will be modeled lies in different treatment of the prerequisite of a default while determining the default’s applicability. In the former, a default can be applied if its prerequisite is believed (not contradicting known information). In the latter, we may require that the prerequisite of a default (or a part of it) has to be known, rather than believed, to make the default applicable. The possibility of using both versions substantially increases the expressive power of the resulting logic. We also show that both rough default logic and rough default logic with strong prerequisites can be naturally extended to their prioritized versions by slightly changing the voting policy mechanism used.

In the current chapter we provide a small case study, based on the Witas Uav application domain to illustrate various knowledge representation and reasoning techniques presented in the book.

Solving complex problems by intelligent systems, in such areas as identification of objects by autonomous systems, web mining or sensor fusion, requires techniques for combining information from many different sources with different degrees of quality. Usually, the information is inaccurate and incomplete. One paradigm for dealing with such complex problems is granular computing.

In traditional approaches to knowledge representation, notions such as tolerance measures on data, distance between objects or individuals, and similarity measures between primitive and complex data structures such as properties and relations, elementary and complex descriptors, decision rules, information systems, and relational databases, are rarely considered. This is unfortunate because many complex systems which have knowledge representation components receive and process data which is incomplete, noisy, and uncertain. There is often a need to use tolerance and similarity measures in processes of data and knowledge abstraction. This is a particular problem in the area of cognitive robotics where data input by sensors has to be fused, filtered and integrated with more traditional qualitative knowledge structures. A great many levels of knowledge abstraction and data reduction must be used as one tries to integrate newly acquired data with existing data which has previously been abstracted and represented implicitly in the form of more qualitative data and knowledge structures.