Representation & Reasoning Overview

Structuring Knowledge & Data in AI Programs and How AI Programs Solve Problems

In the 1960s and 1970s, students frequently asked, "Which kind of representation is best?" and I usually replied that we'd need more research. ... But now I would reply: To solve really hard problems, we'll have to use several different representations. This is because each particular kind of data structure has its own virtues and deficiencies, and none by itself would seem adequate for all the different functions involved with what we call common sense.

- Marvin Minsky

"The mind's mechanism for storing and retrieving knowledge is fairly transparent to us. When we 'memorize' an orange, we simply examine it, think about it for a while, and perhaps eat it. Somehow, during this process, all the essential qualities of the orange are stored. Later, when someone mentions the word 'orange,' our senses are activated from within, and we see, smell, touch, and taste the orange all over again.

Computers, unfortunately, are not as adept at forming internal representations of the world. ... Instead of gathering knowledge for themselves, computers must rely on human beings to place knowledge directly into their memories.

This suggests programming, but even before programming begins, we must decide on ways to represent information, knowledge, and inference techniques inside a computer."

- Arnold, William R. and John S. Bowie. 1985. Artificial Intelligence: A Personal Commonsense Journey. Englewood Cliffs, NJ: Prentice Hall. Excerpt taken from the Introduction to Chapter 3 at page 46.


Definition of the Area - Representation

"What is a knowledge representation? We argue that the notion can best be understood in terms of five distinct roles that it plays, each crucial to the task at hand:

  • First, a knowledge representation is most fundamentally a surrogate, a substitute for the thing itself, that is used to enable an entity to determine consequences by thinking rather than acting, that is, by reasoning about the world rather than taking action in it.
  • Second, it is a set of ontological commitments, that is, an answer to the question, In what terms should I think about the world?
  • Third, it is a fragmentary theory of intelligent reasoning expressed in terms of three components: (1) the representation’s fundamental conception of intelligent reasoning, (2) the set of inferences that the representation sanctions, and (3) the set of inferences that it recommends.
  • Fourth, it is a medium for pragmatically efficient computation, that is, the computational environment in which thinking is accomplished. One contribution to this pragmatic efficiency is supplied by the guidance that a representation provides for organizing information to facilitate making the recommended inferences.
  • Fifth, it is a medium of human expression, that is, a language in which we say things about the world."

From What Is a Knowledge Representation? by Randall Davis, Howard Shrobe, and Peter Szolovits. AI Magazine (Spring, 1993).


Definition of the Area - Reasoning

Many problems of practical importance are problems of reasoning about actions. In these problems, a course of action has to be found that satisfies a number of specified conditions. Everyday examples include planning an airplane trip, organizing a dinner party, etc. ...

A problem of reasoning about actions is given in terms of an initial situation, a terminal situation, a set of feasible actions, and a set of constraints...The task of a problem solver is to find the best sequence of permissible actions that can transform the initial situation into the terminal situation.

- Saul Amarel, On Representations of Problems of Reasoning About Actions.

"When the system is required to do something that it has not been explicitly told how to do, it must reason - it must figure out what it needs to know from what it already knows. For instance, suppose an information retrieval program 'knows' only that Robins are birds and that All birds have wings. Keep in mind that for a system to know these facts means only that it contains data structures and procedures that would allow it to answer the questions:

  • Are Robins birds? Yes 
  • Do all birds have wings? Yes

If we then ask it, Do robins have wings? the program must reason to answer the query. In problems of any complexity, the ability to do this becomes increasingly important. The system must be able to deduce and verify a multitude of new facts beyond those it has been told explicitly."

  • Handbook of Artificial Intelligence, Volume 1, ed. Barr, Avron, and Edward A. Feigenbaum (1981, Stanford / Los Altos, CA: Heuris Tech Press / William Kaufmann, Inc.) page 146.


Vertical Tabs

Good Starting Places
General Readings
Educational Resources
Hardware and Software