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. This process of forming new subgoals and new states continues until a state is produced in which the original goal is provable; the sequence of operators producing that state is the desired solution. In the case of a single goal wff, the objective is quite simple: achieve the goal (possibly while minimizing some combination of planning and execution cost). The objective of the system is to achieve the single positive goal (perhaps while minimizing search and execution costs) while avoiding absolutely any state satisfying the negative goal.
"In this paper we describe some major new additions to the STRIPS robot problem-solving system. The first addition is a process for generalizing a plan produced by STRIPS so that problem-specific constants appearing in the plan are replaced by problem-independent parameters.The generalized plan, stored in a convenient format called a triangle table, has two important functions. The more obvious function is as a single macro action that can be used by STRIPS—either in whole or in part—during the solution of a subsequent problem. Perhaps less obviously, the generalized plan also plays a central part in the process that monitors the real-world execution of a plan, and allows the robot to react "intelligently" to unexpected consequences of actions.We conclude with a discussion of experiments with the system on several example problems."Artificial Intelligence 3:251-288
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.