heoretical which develops bas is to achieve these objectives. The major relevant disciplines include, as a minimum set, non classical control theory, probability, queueing theory, and Markov decision theory. Technology requirements include the determination of system-wide objectives of missions and the development of theoretical and practical bases to achieve those objectives; development of non classical control theory of complex man-machine informatidn systems; probability theory applicable to complex infotrmation systems; and Markov decision theory for complex information systems.
6.1.11 Plan Formation and Scheduling In those cases where robots are called upon to operate in sophisticated task environments, the machine system first performs some computation which can be considered problem-solving, then takes action based upon the problem solving result which is called the "plan formation" process. The part of the resulting plan which identifies the times at which actions are to occur is called the schedule. Whether the machine system is a relatively small mobile robot as might be used in planetary surface exploration, or a large distributed intelligence such as an Earth-sensing information system, several common features dominate in achieving effective and flexible operation (Sacerdoti, 1979): • The ability to represent the state of the relevant parts of the world (the "world model") • The deductive ability to recognize consequences of a particular world state description • The ability to predict what changes will occur in the world state, possibly due to some action or actions a complex autonomous system itself might perform. In most realistic environments it is impossible to completely build a detailed plan and execute it in unmodified form to obtain the desired result. Several difficuhies preventing such a direct line of attack are: (1) The external reality may not be known in sufficient detail to accurately predict the outcome of some action. If the action in question is the final one in a plan, then it may not achieve the overall intention of the plan. If it is an earlier action in a several-step plan, then it may not produce a required intermediate state for the overall sequence of actions to achieve the goal of the plan. If the goal is to make an observation to obtain information about the environment, the information obtained may not be adequate. (2) Even if a perfect, or effectively perfect, model of the external environment is available to the robot, there may still be inaccuracy associated with the robot's control of itself (e.g., mechanical inaccuracy of motion). (3) Other agents, with goals of their own, may alter the environment in unpredictable ways be tbre the robot can complete the execution of its plan. In such cases some form of overall coordination is necessary. It is not adequate simply to have the main goals of all of the active agents compatible. Even with this precaution, it is still possible to have a contention for resources or intermediate configurations in achieving the common goal. Aside from the problem of avoiding explicit conflict among several active agents there is the inverse problem of achieving efficiency increases by proper cooperative action among the agents. For these reasons, a robot must continually monitor the results of its actions during plan execution, and modify the plan -in essence, re-plan -during plan execution. A further complication arises when the plans must meet real-time constraints -that is, definite short-term requiremerits for actions where failure to meet the timing requiremerits carries significant undesirable consequences. Two types of real-time constraints, "hard" and "soft," may be distinguished. A "hard real-time constraint" is that the failure to carry out a successful plan that attains the relevant goal within the limits will result in a consequence so undesirable that extreme care must be taken not to overrun the time boundary. An example in the area of large-scale space construction might be the joining of two relatively massive but fragile substructures. Failure to initiate timely deceleration of substructures approaching each other could result in large economic losses. An example of a "soft real-time constraint" is in the maximization of the utilization of a costly resource, such as the observation satellites in an Earth-sensing system where it is important to schedule observations in such a way so as to minimize the number of satellites necessary to provide a given level of observational coverage. In this case, each individual failure to meet the real-time constraints has, in general, only minor consequences, but a continuing high-frequency of ailure will result in economic losses through inefficient operation. Because of the need to re-plan during plan execution, and because of the necessity to meet real-time constraints, it is important that complex autonomous systems have plan formation capabilities well in excess of current state of the art. Current assessmenr A considerable amount of work has been done in AI on problem-solving in general, and on planning and plan execution in particular. In the last 10 years the problem-solving emphasis has shifted away from planning towards the perceptual processes of vision and speech recognition. Table 6.3 lists some techniques for problem solving and. planning, and various representational schemes (NASA SP-387, 1976). The frame notion of Minsky initially generated much interest and discussion, but little has been accomplished to date in terms of applications. There are attempts from several different perspectives to implement frame-based languages for programming, as for example KRL (Bobrow and Winograd, 1_977), FRL (Goldstein and Roberts, 1977),
