Strips(ID:2413/str018)Extra-logical problem solverfor STanford Research Institute Problem Solver Extra-logical problem solver Stanford Research Institute STRIPS is a formal language invented by Richard Fikes and Nils Nilsson for declaring instances of automated planning problems in artificial intelligence. A STRIPS instance is composed of: An initial state; The specification of the goal states ie situations which the planner is trying to reach; A set of actions. For each action, the following are included: preconditions (what must be established before the action is performed); postconditions (what is established after the action is performed). Related languages
References: in Artificial Intelligence, Volume 2, Winter 1971 view details in Artificial Intelligence, Volume 2, Winter 1971 view details in Proceedings of the Second International Joint Conference on Artificial Intelligence (IJCAI), September 5 - 8, 1971, London, England view details The principal service we offer to other network participants is the availability of various parts of our own research software. The most notable examples are QA3.6, a first-order resolution theorem prover; STRIPS, an extra-logical problem solver; and possibly QA4, a language oriented toward problem-solving strategies. in Proceedings of the Second International Joint Conference on Artificial Intelligence (IJCAI), September 5 - 8, 1971, London, England view details States of the world of the robot are represented as a set of problems in first-order differential calculus. The application of an operator still move the robot from one state to another. An operator can be applied to a state if the preconditions of the operator are satisfied by the state. The new state is then obtained by deleting some clauses from the old state, and adding some new ones. (This is a neat solution to the so-called frame problem.) Operators are the internal representation of physical actions: the robot's moving to a place or pushing an object. Given a starting state and a desired final state, the robot attempts to find a sequence of operators -- a path -- transforming the former to the latter. A GPS- like means ends analysis is used to find the path the robot should take. STRIPS tries to prove the final state from the initial state using a resolution-based theorem prover; and an incomplete proof (as terminated after a certain amount of computation has been expended) serves as the difference given to the means-ends system. Such use of a theorem prover is very interesting. The theorem-prover could also prove derived facts about a state, although the paper gives no examples. The behavior of STRIPS is exemplified through three tasks. Originally, three boxes and the robot are in one of several rooms. Task 1 asks the robot to turn on a light, switch, which requires it to climb on box 1. Task 2 asks the robot to push the three boxes together. Task 3 asks the robot to go to a location in a different room. In spite of a very convenient problem formulation, there are several difficulties with the axiomatization and some weaknesses in the performance of STRIPS. Some of the difficulties include: ) The axiomatization, as given, cannot be extended concisely to several robots, since it uses a predicate ATROBOT(location,) instead of an AT(robot, location) similar to AT(box, location); 2) Task 2 is axiomatized as: NEXTTO(BOX1,BOX2) A NEXTTO(BOX2,BOX3). Task 2 cannot be solved if it is axiomatized more symmetrically as: NEXTTO(BOX1,BOX2) A NEXTTO(BOX2, BOX3) A NEXTTO(BOX3,BOX1). 3) If the robot goes next to boxl, pushes boxl next to box2, goes next to box2, and pushes box2 next to box3 (at some third location C), then at that point, all dynamic information about boxl (i.e. whether boxl is AT some place or NEXTTO some object) disappears. It is possible, if tricky, to lose all dynamic information about all the boxes. 4) As axiomatized, the behavior of the robot differs markedly from our physical intuition. If the robot goes next to boxl (at location A) then pushes boxl next to itself (which does not make much sense, but is allowed), and finally goes next to box2 at some other location B. then boxl still remains next to the robot. Hence the robot is simultaneously next to two objects that are arbitrarily far from each other! Let us consider performance now. GPS- like systems, if conceptually appealing, have seldom been good performers. STRIPS is no exception. Since no system existed that could be compared to STRIPS, the reviewer and car workers designed and programmed two different problem-solvers, RPS1 and RPS2, and compared their performances to STRIPS. The total time taken by STRIPS to solve the three tasks is 313 see garbage collections, in partially compiled LISP on a PDP-10). Since the paths to solution are only 4, 4, and 5 steps long, a breadth-first exhaustive search procedure is quite feasible and is implemented in RPS1. RPS1 solves the same three tasks in 12 see (FORTRAN on a CDC-6600), the respective search spaces being 161, 131, and 307 nodes. RPS1 is sufficiently fast to explore the total search space, which is found to contain 6,aSa nodes (329 see; nodes of the form NEXTTO(i,i) are rejected). The longest tasks require 15 steps, and there are 27a such tasks. RPS2 generates a set of subtasks from a given task, and solves the subtasks. RPS2 solves the same three tasl;s in 0.1 to 0.2 see each (interpreted LISP on CDC-6600) while the longest tasks (requiring 15 steps) are solved III less than 0.7 sec. Obviously, if the search space becomes larger and the proofs longer, an exhaustive search procedure will not be feasible. It is a matter of experiment to determine whether RPS2 (or extensions of it) can solve efficiently problems in a richer robot environment. There appear to be three main approaches to robot work: 1) The robot is given only very general methods to find its path. The STRIPS work exemplifies this approach. 2) The robot is given advice on what to do. PLANNER, for example, was designed specifically to program such advice. RPS2 contains some built-in advice. 3) The reviewer is attempting to bridge the gap between the above two approaches. As we conceive of it, the robot explores its environment and its own capabilities (introspection!) and builds up its own store of advice. This review benefited from programs written by J. Dreussi and C. Thompson. in ACM Computing Reviews 13(05) May 1972 view details Extract: STRIPS The STRIPS system (Fikes and Nilsson, 1971) is a problem solving program that attempts to find a sequence of operators that transform a given initial model (configuration) into a model in which a given goal formula is true. STRIPS represents a model as a collection of formulas in the first-order predicate calculus, and uses a resolution approach (Robinson, 1965) to theorem proving in order to answer questions about the model. in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details Extract: Introduction Introduction STRIPS (Fikes and Nilsson 1971) is a problem solver which operates with world models, represented by sets of formulas of first order-logic. A STRIPS system is defined by an initial world model, which describes the initial state of the world, and by a set of operators, which correspond to actions changing the current state. Using means-ends analysis, STRIPS attempts to find a sequence of operators transforming the initial world model into a model which satisfies a given goal formula. The description of each operator consists of its precondition (the applicability condition, expressed by a first-order formula), its add list (the list of formulas that must be added to the current world model), and its delete list (the list of formulas that may no longer be true and therefore must be deleted). A resolution theorem prover is used for the verification of operator preconditions, for establishing the validity of the goal formula in the last world model, and also for directing the search. The explanation of the meaning of operator descriptions in (Fikes and Nils-son 1971) is very brief and is almost completely reproduced in the parenthesized comments above. It is not immediately clear how to make this explanation more precise; more specifically, it turns out to be a non-trivial task to define under what conditions the delete list of an operator may be considered sufficiently complete. Moreover, some minor and seemingly harmless modifications in the main example of (Fikes and Nilsson 1971) cause STRIPS to produce incorrect results (see Sections 4 and 5 below). Alan Bundy observes that the AI literature "abounds with plausible looking formalisms, without a proper semantics. As soon as you depart from the toy examples illustrated in the paper, it becomes impossible to decide how to represent information in the formalism or whether the processes described are reasonable or what these processes are actually doing" (Bundy 1983). Is STRIPS a formalism of this sort? In this paper we do the additional theoretical work needed to make sure that this is not the case. We study the difficulties with interpreting STRIPS operator descriptions and define a semantics which draws a clear line between "good" and "bad" uses of the language of STRIPS. in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details Planners are specialized production-system programs. In a production system the control responsibility for rule selection may be contained within the rules, lie outside the rules or be some combination of the two. Backtrack-control information in Prolog, for example, is found in the clauses. A lack of domain-specific control knowledge can lead to inefficiency in planning. Early examples of control information incorporated into the rules are PLANNER, QA4 and CONNIVER. The STRIPS model was one of the first applications of forward production. In the STRIPS model the world consisted of blocks that could be moved around by a simplified robot hand. Blocks could be cleared, placed on top of each other and the robot hand could be emptied. Several precondition formulas (used as implicational rules) constrained production-rule firing. A database described the world to which additional structures were appended. Forward production rules modeled robot actions which altered a global database. The STRIPS approach generates plans in advance but error in execution can cause plan failure. Improvement is obtained by applying partially executed, and previous plans, via plan splicing or dynamic replanning. These techniques provide an error execution recovery scheme. Domain specific knowledge must be incorporated in any planner that plans for real-world problems on a local level. in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details Resources
|