STRIPS in AI

In AI, planning involves generating a sequence of actions to achieve a specific goal. One of the most influential approaches to automated planning is the Stanford Research Institute Problem Solver, commonly known as STRIPS. Developed in the late 1960s at Stanford Research Institute (now SRI International) by Richard Fikes and Nils Nilsson, STRIPS has laid the groundwork for many of the concepts used in modern AI planning systems.

This article explores the fundamental concepts of STRIPS, its mechanics, and its applications in various fields.

STRIPS is a formal language used for expressing planning problems and was originally designed to control the actions of a robot in a manipulable environment. It is primarily concerned with the automatic generation of plans, which are sequences of actions that transition a system from its initial state to a desired goal state.

Key Components of STRIPS:

• States: Defined by a set of logical propositions.
• Goals: Specified as a set of conditions that describe the desired outcome.
• Actions: Each action in STRIPS is characterized by three components:
  • Preconditions: Conditions that must be true for the action to be executed.
  • Add Effects: Conditions that become true as a result of executing the action.
  • Delete Effects: Conditions that become false as a result of executing the action.

Before going through the details, we must be familiar about the terms heuristics and symbols.

• Heuristics: are techniques that helps individuals to solve problems in feasible amount of time. It aims to find approximate solution and in some cases may find the optimal solution as well.
• Symbols: are representation​s that acts as a medium between human knowledge and the AI systems so that the systems can understand the knowledge that it receives and establish the relationships.

Basically STRIPS makes use of heuristics and symbols to solve a real world problem. The features of STRIPS are as follows:

• STRIPS makes use of symbols to represent knowledge so that AI systems can process the incoming data.
• STRIPS makes use of logical reasoning so that appropriate relationship is established among the symbols and that we get appropriate outputs based on the reasoning.
• STRIPS plans the execution of sub problems in a sequential fashion.

The STRIPS algorithm operates by maintaining a database of predicates that describe the state of the world. Each action available to the system is defined in terms of its preconditions and its effects (both add and delete). The planning process in STRIPS involves searching through the space of possible actions to find a sequence that transitions the system from the initial state to the state where the goal predicates are satisfied.

Planning with STRIPS:

1. Define the Initial State: Where the system starts.
2. Set the Goal State: What the system should achieve.
3. Develop Actions: Defined by their preconditions and effects.
4. Search for Solutions: Using a strategy like backward chaining from the goal state to the initial state, identifying actions that satisfy the goal conditions.

Problem Statement: Given three blocks labeled A, B, and C, the objective is to stack Block A on Block B, and Block B on Block C.

Initial State Representation

In STRIPS, the initial state of the environment is crucial for defining the problem. For our scenario:

• OnTable(A) indicates Block A is on the table.
• OnTable(B) indicates Block B is on the table.
• OnTable(C) indicates Block C is on the table.

The notation OnTable(X) is used in STRIPS to denote that block X is resting on the table.

Goal State

The goal state specifies the desired arrangement of blocks:

• On(A,B) means Block A should be on top of Block B.
• On(B,C) means Block B should be on top of Block C.

Using On(X,Y), we denote that Block X is directly on top of Block Y.

Step-by-Step STRIPS Planning Approach

The solution involves a series of actions, each changing the state of the blocks to move towards the goal state. STRIPS formalizes this with actions defined by preconditions (what must be true before the action) and effects (what becomes true after the action).

1. Action: MoveBlock(A, B)

• Preconditions:
  • OnTable(A): A is on the table.
  • Clear(B): B has no other blocks on it.
• Effects:
  • On(A,B): A is now on B.
  • Clear(A): Top of A is clear.
  • ¬OnTable(A): A is no longer on the table.
  • ¬Clear(B): B is no longer clear since A is on it.

This action transitions Block A from the table to being on top of Block B, achieving our first sub-goal On(A,B).

2. Action: MoveBlock(B, C)

• Preconditions:
  • OnTable(B): B is on the table.
  • Clear(C): C has no other blocks on it.
• Effects:
  • On(B,C): B is now on C.
  • Clear(B): Top of B is clear.
  • ¬OnTable(B): B is no longer on the table.
  • ¬Clear(C): C is no longer clear since B is on it.

With this action, Block B is moved onto Block C, achieving the second sub-goal On(B,C).

Results

Combining the results of these actions, we find:

• Final Configuration: Block A is on Block B, and Block B is on Block C. This configuration satisfies our goal state of On(A,B) and On(B,C).

This methodical approach using STRIPS not only simplifies complex problems into manageable actions but also ensures that each step is logically sound, leading to a successful execution in environments such as robotics and automated planning systems.

STRIPS methodology is widely used in many fields. Some applications are as follows:

1. Manufacturing of automobiles

Manufacturing of automobiles requires sequential planning. Here STRIPS play a very important role since it is action-goal oriented. For instance, first the parts needs to be assembled. Then the the parts are embedded in the automobile one by one. Finally the automobiles are painted and lubricated followed by testing.

2. Robotic Systems

STRIPS mechanism is widely used in Robots. For example there are three blocks A, B, C lying on the ground. A robot arm is present and the goal is to place Block B on Block A and Block C on Block B. So the robot arm needs to plan its actions in such a way so that the blocks are placed on one another and that the sequence is maintained while achieving the goal.

3. Knowledge Representation

Since STRIPS makes use of symbols, it is widely used in representing knowledge. It helps to represent the actions, states and goals. It also ensures that appropriate logic has been established for each action that has been taken.

STRIPS has been fundamental in the development of AI systems across various domains, including:

• Robotics: STRIPS algorithms are used to plan the sequence of movements and tasks for robots, especially in manufacturing and assembly lines where precise and repeative actions are required.
• Video Games: AI characters and non-player characters (NPCs) use planning algorithms derived from STRIPS to decide on actions based on player behavior and game dynamics.
• Automated Reasoning: STRIPS provides a basis for systems that need to reason about the effects of actions in various scenarios, such as automated theorem provers and problem solvers.

While STRIPS was revolutionary, it has limitations, primarily its assumption of a static world and the lack of support for actions with nondeterministic outcomes or concurrent actions. These limitations led to the development of more sophisticated planning languages like PDDL (Planning Domain Definition Language), which extend and generalize the concepts introduced by STRIPS to accommodate more complex planning scenarios and capabilities.

STRIPS remains a cornerstone in the study of AI planning systems, providing a clear and structured way to model and solve planning problems. Although newer models and languages have built upon and extended its original framework, the basic principles of STRIPS continue to influence the field of AI.