Knowledge Representation

Knowledge representation (KR) is the study of how knowledge about the world can be represented and what kinds of reasoning can be done with that knowledge. Important questions include the tradeoffs between representational adequacy, fidelity, and computational cost, how to make plans and construct explanations in dynamic environments, and how best to represent default and probabilistic information.

CIRL

CIRL's work in KR focuses on extending traditional representation methods in ways that improve their expressive power while retaining or enhancing machine abilities to reason using the representation in question. A natural outgrowth of this focus is the study of how KR systems can be used to solve real problems.

Pointers

Do Computers Need Common Sense?

This paper makes and defends three claims. First, it is incumbent on the knowledge representation and nonmonotonic communities to demonstrate that their ideas will eventually lead to improvements in the performance of implemented systems. Second, a reasonable working definition of "commonsense" is that it is the process of using polynomial techniques to convert a large instance of an NP-hard problem to a smaller instance on which search techniques can be applied effectively. And finally, it is a consequence of these first two claims that the most pressing problem facing the commonsense community is the identification of realistic problems and problem structures for which commonsense reductions are both necessary and effective. Written by Matt Ginsberg and appeared in Proc. KR in 1996. Compressed postscript document.

Epistemological and Heuristic Adequacy Revisited

McCarthy and Hayes observed in 1969 that an effective AI program must deal with both epistemological and heuristic difficulties. The epistemological problems arise from the fact that the program must be adequate in theory: It must be able to solve problems given access to arbitrarily large computational resources. McCarthy and Hayes go on to suggest that it is the epistemological problems that should be the focus of AI research. The argument, roughly speaking, is that epistemological issues are a separable subproblem whose solution will underlie subsequent work on heuristics and other practical techniques.

The view that I defend in this article is that McCarthy and Hayes are exactly wrong: Epistemological and heuristic adequacy are not separable, and any attempt to solve either in isolation from the other is doomed to failure. This view is supported by an examination of both AI's recent successes and its relative failures. Written by Matt Ginsberg and appeared in ACM Computing Surveys in 1995. Compressed postscript document.

Subareas:

Language

Modeling

Solution structure

References

Ginsberg, Matt, Essentials of Artificial Intelligence, Morgan Kaufmann, San Mateo, California, 1993.

Back to the CIRL Overview Page.