Ph.D. dissertation "Bi-directional and heuristic search in path problems" (Stanford, Computer Science, 1970) summarized in this article in Machine Intelligence 6 (1971).In the uni-directional algorithms, the search proceeds from an initial nodeforward until the goal node is encountered. Problems for which the goal nodeis explicitly known can be searched backward from the goal node. Analgorithm combining both search directions is bi-directional.This method has not seen much use because book-keeping problems werethought to outweigh the possible search reduction. The use of hashingfunctions to partition the search space provides a solution to some of theseimplementation problems. However, a more serious difficulty is involved.To realize significant savings in bi-directional search, the forward andbackward search trees must meet in the 'middle' of the space. The potentialbenefits from this technique motivates this paper's examination of thetheoretical and practical problems in using bi-directional search.

This paper describes an effort to design a heuristic problem-solving program which accepts problems stated in a nondeterministic programming language and applies constraint satisfaction methods and heuristic search methods to find solutions. The use of nondeterministic programming languages for stating problems is discussed, and ref, the language accepted by the problem solver arf, is described. Various extensions to ref are considered. The conceptual structure of the program is described in detail and various possibilities for extending it are discussed. The use of the input language and the behaviour of the program are described and analyzed in sixteen sample problems.

Note: PDF of full volume downloadable by clicking on title above (32.8 MB). Selected individual chapters available from the links below.CONTENTSINTRODUCTORY MATERIALMATHEMATICAL FOUNDATIONS1 Program scheme equivalences and second-order logic. D. C. COOPER 32 Programs and their proofs: an algebraic approach.R. M. BURSTALL and P. J. LANDIN 173 Towards the unique decomposition of graphs. C. R. SNOW andH. I. SCOINS 45THEOREM PROVING4 Advances and problems in mechanical proof procedures. D. PRAWITZ 595 Theorem-provers combining model elimination and Tesolution.D. W. LOVELAND 736 Semantic trees in automatic theorem-proving. R. KOWALSKI andP. J. HAYES 877 A machine-oriented logic incorporating the equality relation.E. E. SIBERT 1038 Paramodulation and theorem-proving in first-order theories withequality. G. ROBINSON and L. Wos 1359 Mechanizing higher-order logic. J. A. ROBINSON 151DEDUCTIVE INFORMATION RETRIEVAL10 Theorem proving and information retrieval. J. L. DARLINGTON 17311 Theorem-proving by resolution as a basis for question-answeringsystems. C. CORDELL GREEN 183MACHINE LEARNING AND HEURISTIC PROGRAMMING12 Heuristic dendral: a program for generating explanatory hypothesesin organic chemistry. B. BUCHANAN, G. SUTHERLAND andE. A. FEIGENBAUM 20913 A chess-playing program. J. J. SCOTT 25514 Analysis of the machine chess game. I. J. GOOD 26715 PROSE—Parsing Recogniser Outputting Sentences in English.D. B. VIGOR, D. URQUHART and A. WILKINSON 27116 The organization of interaction in collectives of automata. 285V. I. VARSHAVSKY COGNITIVE PROCESSES: METHODS AND MODELS17 Steps towards a model of word selection. G. R. Kiss 31518 The game of hare and hounds and the statistical study of literaryvocabulary. S. H. STOREY and M. A. MAYBREY 33719 The holophone —recent developments. D. J. WILLSHAW andH. C. LONGUET-HIGGINS 349PATTERN RECOGNITION20 Pictorial relationships — a syntactic approach. M. B. CLOWES 36121 On the construction of an efficient feature space for optical characterrecognition. A. W. M. COOMBS 38522 Linear skeletons from square cupboards. C. J. HILDITCH 403PROBLEM-ORIENTED LANGUAGES23 Absys 1: an incremental compiler for assertions; an introduction.J. M. FOSTER and E. W. ELCOCK 423PRINCIPLES FOR DESIGNING INTELLIGENT ROBOTS24 Planning and generalisation in an automaton/environment system.J. E. DORAN 43325 Freddy in toyland. R. J. POPPLESTONE 45526 Some philosophical problems from the standpoint of artificialintelligence. J. MCCARTHY and P. J. HAYES 463INDEX 505 Machine Intelligence Workshop

COMPUTER SOLUTION OF CALCULUS WORD PROBLEMS* Eugene Charniak Massachusetts Ins:itute of Technology Cambridge, Massachusetts SUMMARY A program was written to solve calculus word problems. The program, CARPS (CAlculus Rate Problem Solver), is restricted to rate problems. The overall plan of the program is similar to Bobrow's STUDENT, the primary difference being the introduction of "structures" as the internal model in CARPS. Structures are stored internally as trees, each structure holding the information gathered about one object. It was found that the use of structures made CARPS more powerful than STUDENT in several respects. In calculus word problems it is not uncommon to have two or three sentences providing information for one equation. For example, in a problem about a filter, ALTITUDE was interpreted as ALTITUDE OF THE FILTER because CARPS knew that since the filter was a cone and cones have altitudes the filter had an altitude. The program has solved 14 calculus problems, most taken (sometimes with slight modifications) from standard calculus texts. CARPS is written in two languages. The bulk of the coding is in LISP.

See also: Education Resources Information CenterSupplement to Proceedings of the IFIP 68 International Congress, Edinburgh, August 1968. Published in A. J. H. Morrell (ed.), Information Processing 68, Vol. II, pp. 1008-1022, Amsterdam: North-Holland, 1969.

A robot, in order to act intelligently, must be able to reason from facts which its sensors detect to conclusions which govern its actions. This reasoning process is so central to human intelligence that it seems immediately relevant to the problems of robot design to consider its properties, how it might be analysed and imitated.

This paper is a survey and discussion of research work relevant to the task of constructing some kind of reasoning robot. The emphasis is entirely on the organization of the reasoning processes, in particular planning, rather than on hardware. In practice the reasoning would most probably be carried out within a digital computer. My objective is to clarify the relationship between some superficially rather disparate approaches to this task, and simultaneously to indicate what seem to be the key problem areas. No new experimental results are presented, but the approach to the subject which I have adopted is a consequence of earlier experimentation with a simple computer simulation of a robot (Doran 1968a, 1969).

Note: PDF of full volume downloadable by clicking on title above (26 MB). Selected individual chapters available from the links below. CONTENTSINTRODUCTION MATHEMATICAL FOUNDATIONS1 The morphology of prex—an essay in meta-algorithmics. J. LAS KS 32 Program schemata. M. S. PATE RSON 193 Language definition and compiler validation. J. J. FLORENTIN 334 Placing trees in lexicographic order. H. I.S COINS 43 THEOREM PROVING5 A new look at mathematics and its mechanization. B. M ELTZER 636 Some notes on resolution strategies. B. MELTZER 717 The generalized resolution principle. J. A. ROBINSON 778 Some tree-paring strategies for theorem proving. D.LUCKHAM 959 Automatic theorem proving with equality substitutions andmathematical induction. J. L. D ARLINGTON 113 MACHINE LEARNING AND HEURISTIC PROGRAMMING10 On representations of problems of reasoning about actions.S.AMAREL 13111 Descriptions. E.W.ELCOCK 17312 Kalah on Atlas. A.G.BELL 18113 Experiments with a pleasure-seeking automaton: J. E. DORAN 19514 Collective behaviour and control problems. V.I.VARSHAVSKY 217 MAN—MACHINE INTERACTION15 A comparison of heuristic, interactive, and unaided methods ofsolving a shortest-route problem. D.MICHIE, J. G. FLEMING andJ. V.OLDFIELD 24516 Interactive programming at Carnegie Tech. A.H.BOND 25717 Maintenance of large computer systems—the engineer's assistant.M.H.J.BAYLIS 269 COGNITIVE PROCESSES: METHODS AND MODELS18 The syntactic analysis of English by machine. J.P.THORNE,P.BRATLEY and H.DEWAR 28119 The adaptive memorization of sequences. H.C.LONOUETHIGGINSand A.ORTONY 311 PATTERN RECOGNITION20 An application of Graph Theory in pattern recognition.C.J.HILDITCH 325 PROBLEM-ORIENTED LANGUAGES21 Some semantics for data structures. D. PARK 35122 Writing search algorithms in functional form. R.M.BURSTALL 37323 Assertions: programs written without specifying unnecessaryorder. J.M.FOSTER 38724 The design philosophy of Pop-2. R.J.POPPLESTONE 393 INDEX 403 Machine Intelligence Workshop

Attempts to write'intelligent' computer programs have commonly involved the choice for attack of some particular aspect of intelligent behaviour, together with the choice of some relevant task, or range of tasks, which the program must perform. The emphasis is sometimes on the generality of the program's ability, sometimes on the importance of the particular task which it can perform. Well-known examples of such programs are Newell, Shaw, and Simon's General Problem Solver (1959; see also Ernst and Newell, 1967), which is applicable to a wide range of simple problems, Samuel's checker (draughts) playing program (1959, 1967), and the program written by Evans (1964), which solves geometric analogy problems. However, there is another approach to the goal of machine intelligence which stresses the relationship of an organism to its environment and which sets out from the start to understand what is involved in this relationship. Long ago Grey Walter (1953) experimented with mechanical'tortoises' which could range over the floor in a lifelike manner. Toda (1962), in a whimsical and illuminating paper, has discussed the problems facing an automaton in a simple artificial environment. Friedman (1967), a psychologist, has described a computer simulation of instinctive behaviour involving an automaton equipped with sensory and motor systems.

"The purpose of this paper is to clarify some basic issues of choice of representation for problems of reasoning about actions. The general problem of re- Presentation is concerned with the relationship between different ways of formulating a problem to a problem solving system and the efficiency with which the system can be expected to find a solution to the problem. An understanding of the relationship between problem formulation and problem solving efficiency is a prerequisite for the design of procedures that can automatically choose the most `appropriate' representation of a problem ( they can find a `point of view' of the problem that maximally simplifies the process of finding a solution).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. A formal definition of this class of problems is given in the next section, in the context of a general conceptual framework for formulating these problems for computers. Everyday examples of reasoning about actions include planning an airplane trip, organizing a dinner party, etc. There are many examples of industrial and military problems in this category, such as scheduling assembly and transportation processes, designing a program for a computer, planning a military operation, etc."In D.Michie (Ed.), Machine intelligence 3. New York: American Elsevier,131-171