PLANNING
Strips Planning Systems
Describing States and Goals
- The frame problem can be delead by using a combination of state space and situation calculus approaches.
- The planning states here are referred as state descriptions.
- The formulas of predicate calculus which describe the set of world state are imagined as a type of state.
- These formulas are regarded as a data structure which changes when actions are performed.
- The data structures are searched to find the one that describes the set of world states which satisfies the goal.
- The goal wff is of the form (∃x1, x2, xn) g(x1, x2, xn) and considered as g(xl, x2,..... xn).
- If a goal wff g is given then, the actions that are to be performed to get a world state by a state description Sd, so that Sd ⊨= g.
- The search process can be from initial state to goal state which is called forward search and also known as progression planning.
- The search may also be from backward direction that is from goal state to initial state.
Forward Search Methods
- In order to search for the goal state operations are needed to perform actions so that state description can be changed.
- These operators are based on a system called STRIPS
- A search process is finished successful when a state description S produced such that Sd ⊨= g
- The operator in SRR, PS system consists o three parts,
- A set in order to represent the before the operations are performed. It is denoted by PC.
- A set in order to represent the ground literals that are present in the delete, list which are to be deleted, denoted by D.
- A Set of ground literals that are to be added, denoted by A.
- If an action is to be performed, then we delete the literals which are present in D from the description before action state.
- Next the literals in add list are added.
- The literals in D are not carried over to after-action state description instead the other literals get carried over this is known as STRIPS assumption.
- The STRIPS assumption helps to solve the frame problem
- STRIPS rule is an operator schema It consists of free variables.
- STRIPS rule example with free variables p, q and r is explained as follows, move .(p, q, r).
The predictions of this operation are On(p, q) ∧ Clear(p) ∧ Clear(r).
The delete list Consists of Clear(r), On(p, q) as p has to move onto r.
The add list consists of On(p, r), Clear(y),clear(F).
The Fig. 3.10.1 illustrates the application of strips operators.
Fig. 3.10.1 A STRIPS Operator
- In this method, the new state descriptions are produced by applying the instances of STRIP rules. This process continues till we reach a state description which satisfies the wff of goal state.
- It is economically beneficial to keep track of changes, instead of all literals which are not changed.
- Using of forward search in real-time applications, is not beneficial as we do not know the information about which rules are to be applied as there are large number of rules.
- Identifying islands is a method to make forward search beneficial.
