This paper describes some recent experiments with a computer program which is capable of useful, or at least interesting, application to a number of different problems. The program, the Graph Traverser, has been described in detail in a previous paper (Doran & Michie 1966). However, we shall here need to view the basic algorithm from a rather more general standpoint, corresponding to an actual extension in the flexibility of the program, so that a restatement of what the program can do is desirable. The Graph Traverser, which is written in Elliott 4100 Algol, is potentially applicable to problem situations which can be idealised in the following way (see for comparison Newell and Ernst 1965). There is given a set of'states', which are connected by a set of'transformations', or, as I shall call them, 'operators'.

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).

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.

I shall discuss automatic methods of search for solutions in problems susceptible of a particular formal representation, namely that on which the Graph Traverser program (Doran & Michie 1966, and see Doran p. 105) has been based. In Burstall's (see pp. 65-85) problem a solution is defined as a network, the calculated 135 MACHINE LEARNING AND HEURISTIC PROGRAMMING After an initial trial network has been proposed, the program then follows rules invented to allow moves of the following two elementary kinds within the limits set by the security constraints: (1) adding a line joining points i and j for any 10j; (2) deleting a line joining points i and j for any i0j; together with two more obtained as compounds of these; namely (3) two operations of (1) above; (4) two or more operations of (2) above. For any substantial number of points in the network, the number of possible moves which can be generated in these four categories becomes very large, necessitating drastic methods of selection. The way in which this selection is effected is discussed by Burstall (loc. The point I wish to make here is that the basic moves by which neighbouring states are inter-transformable may be unalterably fixed in the structure of the problem as given, or definitions of allowable moves may be imported into the problem in order to give it a structure susceptible to general search methods.

How to travel from London to Birmingham may, in some circumstances, be a'problem'. So may be a crossword puzzle, the planning of a school timetable, the solving of an algebraic equation, and the curing of a sick person. I shall not attempt to define a'problem', except to suggest that the A problem-solving program must solve, or help solve, problems. Even when a problem is precisely stated, and when a method of solution known to be infallible is available, it does not follow that this provides a useful method of attack in practice. A solution must be obtained within certain limits of time, and the machine will have a finite'memory'.