In R. O. Freedle and J. B. Carroll (Eds.), Language comprehension and the acquisition of knowledge. Washington, D.C.: Winston, 41-69

For the past several years research on robot problem-solving methods has centered on what may one day be called'simple' plans: linear sequences of actions to be performed by single robots to achieve single goals in static environments. Recent speculation and preliminary work at several research centers has suggested a variety of ways in which these traditional constraints could be relaxed. In this paper we describe some of these possible extensions, illustrating the discussion where possible with examples taken from the current Stanford Research Institute robot system.

BBN Rep. No. 2378, Bolt Beranek and Newman, Inc., Cambridge, Mass.

The study of perception is divided among many established sciences: physiology, experimental psychology and machine intelligence; with several others making contributions. But each of the contributing sciences tends to have its own concepts, and ways of considering problems. Each -- to use T. S. Kuhn's term (1962) -- has its own'paradigm', within which its science is respectable. This can make cooperation difficult, as misunderstandings (and even distrust) can be generated by paradigm differences. This paper is a plea to consider perceptual phenomena from many points of view, and to consider whether a general paradigm for perception might be found.

The intention is as follows.

We will now consider each of these problems.

This report considers the problem of constructing an abstract model of story comprehension. The use of questions that go beyond the story as a test of understanding the story raises a methodological problem which is discussed in detail.

The frame problem in representing natural-language information is discussed. It is argued that the problem is not restricted to problem-solving-type situations, in which it has mostly been studied so far, but also has a broader significance. A new solution to the frame problem, which arose within a larger system for representing natural-language information, is described. The basic idea is to extend the predicate calculus notation with a special operator, Unless, with peculiar properties. Some difficulties with Unless are described.

And-or graphs and theorem-proving graphs determine the same kind of search space and differ only in the direction of search: from axioms to goals, in the case of theorem-proving graphs, and in the opposite direction, from goals to axioms, in the case of and-or graphs. Bidirectional search strategies combine both directions of search. We investigate the construction of a single general algorithm which covers unidirectional search both for and-or graphs and for theorem-proving graphs, bidirectional search for path-finding problems and search for a simplest solution as well as search for any solution. We obtain a general theory of completeness which applies to search spaces with infinite or-branching. In the case of search for any solution, we argue against the application of strategies designed for finding simplest solutions, but argue for assigning a major role in guiding the search to the use of symbol complexity (the number of symbol occurrences in a derivation).

In this paper we compare three models of transformational grammar: the mathematical model of Ginsburg and Partee (1969) as applied by Salomaa (1971), the mathematical model of Peters and Ritchie (1971 and forthcoming), and the computer model of Friedman et al. (1971). All of these are, of course, based on the work of Chomsky as presented in Aspects of the Theory of Syntax (1965). We were led to this comparison by the observation that the computer model is weaker in three important ways: search depth is not unbounded, structures matching variables cannot be compared, and structures matching variables cannot be moved. All of these are important to the explanatory adequacy of transformational grammar. Both mathematical models allow the first, they each allow some form of the second, one of them allows the third. We were interested in the mathematical consequences of our restrictions. The comparison will be carried out by reformulating in the computer system the most interesting proofs to date of the ability of transformational grammars to generate any recursively enumerable set. These are Salomaa's proof that the Ginsburg-Partee model can generate any recursively enumerable (r.e.) set from a regular base, and the Peters-Ritchie proof that any r.e.