We will discuss what facts a person or robot must take into account in order to achieve a goal by some strategy of action. We will ignore the question of how these facts are represented, e.g., whether they are represented by sentences from which deductions are made or whether they are built into the program. We start with great generality, so there are many difficulties. We obtain successively easier problems by assuming that the difficulties we have recognized don't occur until we get to a class of problems we think we can solve.
1. We begin by asking whether solving the problem requires the co-operation of other people or overcoming their opposition. If either is true, there are two subcases. In the first subcase, the other people's desires and goals must be taken into account, and the actions they will take in given circumstances predicted on the hypothesis that they will try to achieve their goals, which may have to be discovered. The problem is even more difficult if bargaining is involved, because then the problems and indeterminacies of game theory are relevant. Even if bargaining is not involved, the robot still must ``put himself in the place of the other people with whom he interacts''. Facts like a person wanting a thing or a person disliking another must be described.
The second subcase makes the assumption that the other people can be regarded as machines with known input-output behavior. This is often a good assumption, e.g., one assumes that a clerk in a store will sell the goods in exchange for their price and that a professor will assign a grade in accordance with the quality of the work done. Neither the goals of the clerk or the professor need be taken into account; either might well regard an attempt to use them to optimize the interaction as an invasion of privacy. In such circumstances, man usually prefers to be regarded as a machine.
Let us now suppose that either other people are not involved in the problem or that the information available about their actions takes the form of input-output relations and does not involve understanding their goals.
2. The second question is whether the strategy involves the acquisition of knowledge. Even if we can treat other people as machines, we still may have to reason about what they know. Thus an airline clerk knows what airplanes fly from here to there and when, although he will tell you when asked without your having to motivate him. One must also consider information in books and in tables. The latter information is described by other information.
The second subcase of knowledge is according to whether the information obtained can be simply plugged into a program or whether it enters in a more complex way. Thus if the robot must telephone someone, its program can simply dial the number obtained, but it might have to ask a question, ``How can I get in touch with Mike?'' and reason about how to use the resulting information in conjunction with other information. The general distinction may be according to whether new sentences are generated or whether values are just assigned to variables.
An example worth considering is that a sophisticated air traveler rarely asks how he will get from the arriving flight to the departing flight at an airport where he must change planes. He is confident that the information will be available in a form he can understand at the time he will need it.
If the strategy is embodied in a program that branches on an environmental condition or reads a numerical parameter from the environment, we can regard it as obtaining knowledge, but this is obviously an easier case than those we have discussed.
3. A problem is more difficult if it involves concurrent events and actions. To me this seems to be the most difficult unsolved epistemological problem for AI--how to express rules that give the effects of actions and events when they occur concurrently. We may contrast this with the sequential case treated in (McCarthy and Hayes 1969). In the sequential case we can write
where 
is the situation that results when event e occurs
in situation s. The effects of e can be described by
sentences relating , e and s. One can attempt a similar
formalism giving a partial situation that results from an
event in another partial situation, but it is difficult to see
how to apply this to cases in which other events may affect
with the occurrence.
When events are concurrent, it is usually necessary to regard time as continuous. We have events like raining until the reservoir overflows and questions like Where was his train when we wanted to call him?.
Computer science has recently begun to formalize parallel processes so that it is sometimes possible to prove that a system of parallel processes will meet its specifications. However, the knowledge available to a robot of the other processes going on in the world will rarely take the form of a Petri net or any of the other formalisms used in engineering or computer science. In fact, anyone who wishes to prove correct an airline reservation system or an air traffic control system must use information about the behavior of the external world that is less specific than a program. Nevertheless, the formalisms for expressing facts about parallel and indeterminate programs provide a start for axiomatizing concurrent action.
4. A robot must be able to express knowledge about space, and the locations, shapes and layouts of objects in space. Present programs treat only very special cases. Usually locations are discrete--block A may be on block B but the formalisms do not allow anything to be said about where on block B it is, and what shape space is left on block B for placing other blocks or whether block A could be moved to project out a bit in order to place another block. A few are more sophisticated, but the objects must have simple geometric shapes. A formalism capable of representing the geometric information people get from seeing and handling objects has not, to my knowledge, been approached.
The difficulty in expressing such facts is indicated by the limitations of English in expressing human visual knowledge. We can describe regular geometric shapes precisely in English (fortified by mathematics), but the information we use for recognizing another person's face cannot ordinarily be transmitted in words. We can answer many more questions in the presence of a scene than we can from memory.
5. The relation between three dimensional objects and their two dimensional retinal or camera images is mostly untreated. Contrary to some philosophical positions, the three dimensional object is treated by our minds as distinct from its appearances. People blind from birth can still communicate in the same language as sighted people about three dimensional objects. We need a formalism that treats three dimensional objects as instances of patterns and their two dimensional appearances as projections of these patterns modified by lighting and occlusion.
6. Objects can be made by shaping materials and by combining other objects. They can also be taken apart, cut apart or destroyed in various ways. What people know about the relations between materials and objects remains to be described.
7. Modal concepts like event e1 caused event e2 and person e can do action a are needed. (McCarthy and Hayes 1969) regards ability as a function of a person's position in a causal system and not at all as a function of his internal structure. This still seems correct, but that treatment is only metaphysically adequate, because it doesn't provide for expressing the information about ability that people actually have.
8. Suppose now that the problem can be formalized in terms of a single state that is changed by events. In interesting cases, the set of components of the state depends on the problem, but common general knowledge is usually expressed in terms of the effect of an action on one or a few components of the state. However, it cannot always be assumed that the other components are unchanged, especially because the state can be described in a variety of co-ordinate systems and the meaning of changing a single co-ordinate depends on the co-ordinate system. The problem of expressing information about what remains unchanged by an event was called the frame problem in (McCarthy and Hayes 1969). Minsky subsequently confused matters by using the word ``frame'' for patterns into which situations may fit. (His hypothesis seems to have been that almost all situations encountered in human problem solving fit into a small number of previously known patterns of situation and goal. I regard this as unlikely in difficult problems).
9. The frame problem may be a subcase of what we call the qualification problem, and a good solution of the qualification problem may solve the frame problem also. In the missionaries and cannibals problem, a boat holding two people is stated to be available. In the statement of the problem, nothing is said about how boats are used to cross rivers, so obviously this information must come from common knowledge, and a computer program capable of solving the problem from an English description or from a translation of this description into logic must have the requisite common knowledge. The simplest statement about the use of boats says something like, ``If a boat is at one point on the shore of a body of water, and a set of things enter the boat, and the boat is propelled to the another point on the shore, and the things exit the boat, then they will be at the second point on the shore''. However, this statement is too rigid to be true, because anyone will admit that if the boat is a rowboat and has a leak or no oars, the action may not achieve its intended result. One might try amending the common knowledge statement about boats, but this encounters difficulties when a critic demands a qualification that the vertical exhaust stack of a diesel boat must not be struck square by a cow turd dropped by a passing hawk or some other event that no-one has previously thought of. We need to be able to say that the boat can be used as a vehicle for crossing a body of water unless something prevents it. However, since we are not willing to delimit in advance possible circumstances that may prevent the use of the boat, there is still a problem of proving or at least conjecturing that nothing prevents the use of the boat. A method of reasoning called circumscription, described in a subsequent section of this paper, is a candidate for solving the qualification problem. The reduction of the frame problem to the qualification problem has not been fully carried out, however.
