Module-4

Planning and Machine Learning

4.1 Basic Plan Generation Systems

Planning

Planning refers to the process of computing several steps of a problem solving before executing
any of them. Planning is useful as a problem-solving technique for non-decomposable problem.
Components of Planning System:
In any general problem-solving systems, elementary techniques to perform following
functions are required
• Choose the best rule (based on heuristics) to be applied
• Apply the chosen rule to get new problem state
• Detect when a solution has been found
• Detect dead ends so that new directions are explored.

To choose the rules ,

• first isolate a set of differences between the desired goal state and current state,
• identify those rules that are relevant to reducing these difference,
• if more rules are found then apply heuristic information to choose out of them.

To apply rules,
In simple problem-solving system,
• applying rules was easy as each rule specifies the problem state that would result from
its application.
• In complex problem we deal with rules that specify only a small part of the complete
problem state.
Let us consider the famous problem name as Block World Problem, which helps to
understand the importance of planning in artificial intelligent system.

The block world environment has,

• Square blocks of same size
• Blocks can be stacked one upon another.
• Flat surface (table) on which blocks can be placed.
• Robot arm that can manipulate the blocks. It can hold only one block at a time.
In block world problem, the state is described by a set of predicates representing the facts that
were true in that state. One must describe for every action, each of the changes it makes to the
state description. In addition, some statements that everything else remains unchanged is also
necessary. We are having four types of operations done by robot in block world
environment .They are

1|P a g e
UNSTACK (X, Y) : [US (X, Y)]
• Pick up X from its current position on block Y. The arm must be empty and X has no
block on top of it.
STACK (X, Y): [S (X, Y)]
• Place block X on block Y. Arm must holding X and the top of Y is clear.
PICKUP (X): [PU (X) ]
• Pick up X from the table and hold it. Initially the arm must be empty and top of X is
clear.
PUTDOWN (X): [PD (X)]
• Put block X down on the table. The arm must have been holding block X.
Along with the operations ,some predicates to be used to describe an environment [Link]
predicates are,

• ON(X, Y) - Block X on block Y.

• ONT() - Block X on the table.
• CL(X) - Top of X clear.
• HOLD(X) - Robot-Arm holding X.
• AE - Robot-arm empty.

Logical statements true in this block world.

X Holding X means, arm is not empty
($ X) HOLD (X) ® ~ AE

X is on a table means that X is not on the top of any block

(" X) ONT (X) ® ~ ($ Y) ON (X, Y)

Any block with no block on has clear top

(" X) (~ ($ Y) ON (Y,X)) ® CL (X)
Initial State

2|P a g e
Armempty
clear(block2)
ontable(block2)
ontable(block1)
clear(block1)

Goal State

Armempty
ontable(block2)
on(block1, block2)
clear(block1)
We have to generate a plan to reach goal state from initial state [Link] this example the initial
state has two blocks Block1 and Block [Link] is placed on [Link] reach the goal state first
we have to
PICKUP(Block 1)

3|P a g e
We need to check whether we reach goal state or not ,after completion of each and every
operation. Here the environment looks like,
Hold(block1)
Clear(Block2)

On Table(Block2)
This is not the goal state .so ,we have to continue the process. Next the block 1 needs to be
place on block 2,to achieve this do the operation STACK(Block1,Block2). After this operation
the environment looks like,

ArmEmpty,on(Block1,Block2),Clear(Block1),On Table(Block2)

We reach the goal state,the plan for reaching goal state is

PICKUP(Block1) and Stack(Block1,Block2)

4.2 Strips
STRIPS
STRIPS stands for "STanford Research Institute Problem Solver," was the planner used in
Shakey, one of the first robots built using AI technology ,which is an action-centric
representation ,for each action , specifies the effect of an action.

The STRIPS representation for an action consists of three lists,

• Pre_Cond list contains predicates which have to be true before operation.
• ADD list contains those predicates which will be true after operation
• DELETE list contain those predicates which are no longer true after operation

Predicates not included on either of these lists are assumed to be unaffected by the
4|P a g e
[Link] axioms are specified implicitly in STRIPS which greatly reduces amount of
information [Link] us discuss about the action lists for operations of block world problem.
Stack (X, Y)
Pre: CL (Y) ,HOLD (X)
Del: CL (Y), HOLD (X)
Add: AE , ON (X, Y)
UnStack (X, Y)
Pre: ON (X, Y) , CL (X) , AE
Del: ON (X, Y) , AE
Add: HOLD (X) , CL (Y)
Pickup (X)
Pre: ONT (X) , CL (X) ,AE
Del: ONT (X) , AE
Add: HOLD (X)
Putdown (X)
Pre: HOLD (X)
Del: HOLD (X)
Add: ONT (X) , AE

Consider a Block world problem ,

Initial State
on(block2, block1)
clear(block2)
ontable(block3)

5|P a g e
on(block4, block3)
on(block5, block4)
clear(block5)

Goal State
empty
on(block3, block4)
on(block5, block1)
ont(block2)

Identify the style operators for given problem,

Unstack(block5,block4)

Pre: ON (block5, block4) , CL (block5) , AE

Del: ON (block5,block4) , AE
Add: HOLD (block5) , CL (block4)

6|P a g e
Putdown(block5)
Pre: HOLD (block5)
Del: HOLD (block5)
Add: ONT (block5) , AE

Unstack(block4,block3)
Pre: ON (block4, block3) , CL (block4) , AE
Del: ON (block4,block3) , AE
Add: HOLD (block4) , CL (block3)

Putdown(block4)

Pre: HOLD (block4)

Del: HOLD (block4)
Add: ONT (block4) , AE

7|P a g e
Pickup(block3)
Pre: ONT (block3) , CL (block3) ,AE
Del: ONT (block3) , AE
Add: HOLD (block3)

Stack(block3,block4)
Pre: CL (block3) ,HOLD (block3)
Del: CL (block4), HOLD (block3)
Add: AE , ON (block3, block4)

8|P a g e
Unstack(block2,block1)

Pre: ON (block2, block1) , CL (block2) , AE

Del: ON (block2, block1) , AE
Add: HOLD (block2) , CL (block3)

Putdown(block2)

Pre: HOLD (block2)

Del: HOLD (block2)
Add: ONT (block2) , AE

Pickup(block5)

Pre: ONT (block5) , CL (block5) ,AE

Del: ONT (block5) , AE
Add: HOLD (block5)

9|P a g e
Stack(block5,block1)

Pre: CL (block1) ,HOLD (block5)

Del: CL (block1), HOLD (block5)
Add: AE , ON (block5, block1)

After completing all the operations what we found for the given problem,we had reaches the
goal state.

armempty
on(block3, block4)
on(block5, block1)
ont(block2)
4.3 Advanced plan generation systems
Planning-Goal Stack Algorithm
One of the earliest techniques is planning using goal stack. Problem solver uses single stack
that contains
• sub goals and operators both
• sub goals are solved linearly and then finally the conjoined sub goal is solved.
Plans generated by this method will contain complete sequence of operations for solving one
goal followed by complete sequence of operations for the next etc.

10 | P a g e
Problem solver also relies on
• A database that describes the current situation.
• Set of operators with precondition, add and delete lists.

Let us assume that the goal to be satisfied is:

GOAL = G1 ^ G2 ^ … ^Gn
Sub-goals G1, G2, … Gn are stacked with compound goal G1 ^ G2 ^ …^ Gn at the bottom.
Top G1
G2
:
Gn
Bottom G1 ^ G2 ^ … ^ G4
At each step of problem solving process, the top goal on the stack is pursued.

Algorithm
• Find an operator that satisfies sub goal G1 (makes it true) and replace G1 by the
operator.
• If more than one operator satisfies the sub goal then apply some heuristic to choose
one.
• In order to execute the top most operation, its preconditions are added onto the stack.
• Once preconditions of an operator are satisfied, then we are guaranteed that operator
can be applied to produce a new state.
• New state is obtained by using ADD and DELETE lists of an operator to the existing
database.
• Problem solver keeps tract of operators applied.
• This process is continued till the goal stack is empty and problem solver returns the
plan of the problem.

Goal Stack Example

With this example,let us explain the working method of Goal Stack Algorithm.

11 | P a g e
Initial State: ON(B, A) ^ ONT(C) ^ ONT(A) ^ ONT(D) ^ CL(B) ^CL(C) ^ CL(D) ^ AE
Goal State: ON(C, A) ^ ON(B, D) ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE
We notice that following sub-goals in goal state are also true in initial state.
ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE
Represent for the sake of simplicity - TSUBG.
Only sub-goals ON(C, A) & ON(B, D) are to be satisfied and finally make sure
that TSUBG remains true.
Either start solving first ON(C, A) or ON(B, D). Let us solve first ON(C, A).
Goal Stack:
ON(C, A)
ON(B, D)
ON(C, A) ^ ON(B,
D) ^ TSUBG
• To solve ON(C, A), operation S(C, A) could only be applied.
• So replace ON(C, A) with S(C, A) in goal stack.

Goal Stack:
S (C, A)
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG
S(C, A) can be applied if its preconditions are true. So add its preconditions on the stack.

Goal Stack:
CL(A)
HOLD(C) Preconditions of STACK
CL(A) ^ HOLD(C)
S (C, A) Operator
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG

To do the S(C,A) operation all preconditions should be true. In the given problem CL(A) is
not [Link],to make the state true ,replace CL(A) by U(B,A) and write the preconditions of
Unstack operator.

12 | P a g e
Goal Stack:
ON(B, A)
CL(B) Preconditions of UNSTACK
AE
ON(B, A) ^ CL(B) ^ AE
US(B, A) Operator
HOLD(C) Preconditions of STACK
CL(A) ) ^ HOLD(C)
S (C, A) Operator
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG
• ON(B, A), CL(B) and AE are all true in initial state, so pop these along with its
compound goal.
• Next pop top operator US(B, A) and produce new state by using its ADD and
DELETE lists.
• Add US(B, A) in a queue of sequence of operators.
SQUEUE = US (B, A)
State_1:
ONT(A) ^ONT(C) ^ ONT(D) ^ HOLD(B) ^CL(A) ^ CL(C) ^ CL(D)

Goal Stack:
HOLD(C) Preconditions of STACK
CL(A) ) ^ HOLD(C)

13 | P a g e
S (C, A) Operator
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG
To execute the S(C,A),all the preconditions of Stack operator should be [Link] in this case
HOLD(C) is not true .To make the state true use the operator S(B,D)
S(B,D) Operator
HOLD(C)
CL(A) ) ^ HOLD(C) Preconditions of STACK
S (C, A) Operator
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG
Write down the preconditions of S(B,D)

Goal Stack
CL (D) ^ HOLD (B) Preconditions of STACK
S(B,D) Operator
HOLD(C)
CL(A) ) ^ HOLD(C) Preconditions of STACK
S (C, A) Operator
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG
Add S(B, D) in a queue of sequence of operators.
SQUEUE = US (B, A), S (B, D)
State_2:
ONT(A) ^ONT(C) ^ ONT(D) ^ ON(B, D) ^ CL(A) ^ CL(C) ^ CL(B) ^ AE

14 | P a g e
Goal Stack
HOLD(C)
CL(A) ) ^ HOLD(C) Preconditions of STACK
S (C, A) Operator
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG
To execute S(C,A) all the preconditions should be [Link] HOLD(C) is not true,to make the
state true use the operator PU(C) and write the preconditions .

Goal Stack
ONT (C)^CL (C)^ AE Preconditions of PICKUP
PU (C) Operator
HOLD(C)
CL(A) ) ^ HOLD(C) Preconditions of STACK
S (C, A) Operator
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG
Here, all the preconditions of PU operator is true,so add PU(C) in a queue of sequence of
operators.

SQUEUE = US (B, A), S (B, D),PU(C)

State_3:
ONT(A) ^ HOLD(C) ^ ONT(D) ^ ON(B, D) ^ CL(A) ^ CL(B)

15 | P a g e
Goal Stack
HOLD(C)
CL(A) ) ^ HOLD(C) Preconditions of STACK
S (C, A) Operator
ON(B, D)
ON(C, A) ^ ON(B, D) ^ TSUBG
Here all the preconditions of S(C,A) is true ,so add S(C,A) in queue
SQUEUE = US (B, A), S (B, D),PU(C),S(C,A)

State_4:
ONT(A)^ON(C, A)^ ONT(D) ^ON(B, D) ^CL(C) ^CL(B)^ AE

Finally ,we reached goal state after S(C,A) using Goal Stack algorithm,so the plan for the
given problem is,

UnStack (B, A)
Stack (B, D)
PickUp(C)
Stack(C,A)
4.4 K strips
Modal Operator K :

We are familiar with the use of connectives ∧ and V in logics. Thinking of these connectives
as operators that construct more complex formulas from simpler components. Here, we want
to construct a formula whose intended meaning is that a certain agent knows a certain
proposition.

The components consist of a term denoting the agent and a formula denoting a proposition
that the agent knows. To accomplish this, modal operator K is introduced.

For example, to say that Robot (name of agent) know that block A is on block B, then write,
K( Robot, On(A,B))

16 | P a g e
The sentence formed by combining K with the term Robot and the formula On(A,B) gets a
new formula, the intended meaning of which is “Robot knows that block A is on block B”.

The words “knows” and “belief” is different in meaning. That means an agent can believe a
false proposition, but it cannot know anything that is false.

Some examples,

K(Agent1, K(Agent2, On(A,B) ) ], means Agent1 knows that Agent1 knows that A is on B.
K(Agent1, On(A,B)) V K(Agent1, On(A,C) ) means that either Agent1 knows that A is on B
or it knows that A is on C.
K(Agent1, On(A,B)) V K(Agent1, ¬On(A,B) ) means that either Agent1 knows whether or
not A is on B.

Knowledge Axioms:

The operators ∧ and V have compositional semantics (depends on truth value) , but the
semantics of K are not compositional. The truth value of K(Agent1, On(A,B) ) for example,
cannot necessarily be determined from the properties of K, the denotation of Agent1 and the
truth value of On(A,B). K Operator is said to be referentially opaque.

Example in Planning Speech Action:

We can treat speech acts just like other agent systems. Our agent can use a plan-generating
system to make plans comprising speech acts and other actions. To do so, it needs a model of
the effects of these actions.

Consider for example, Tell( A, φ ) , where A is Agent and φ is true.

We could model the effects of that action by the STRIPS rule :

Tell( A, φ ) :

Precondition : Next_to(A) ∧ φ ∧ ¬K(A, φ)

Delete : ¬K(A, φ)

Add : K(A, φ)

The precondition Next_to(A) ensures that our agent is close to agent A to enable
communication.
The precondition φ is imposed to ensure that our agent actually believes φ before it can
inform another agent about the truth.
The precondition ¬K(A, φ) ensure that our agent does not communicate redundant
information.

17 | P a g e
 4.5 Strategic explanations
Why, Why not and how explanations
Most expert systems have explanation facilities that allow the user to ask questions- why and
how it reached some conclusion
The questions are answered by referring to the system goals, the rules being used, and
existing problem solving. The rules typically reflect empirical or “compiled” knowledge.
They are codes of an expert’s rule of thumb, not the expert’s deeper understanding.
Example:

18 | P a g e
Learning

Learning
“Learning denotes changes in a system that enables system to do the same task more
efficiently next time.”
Machine Learning:-Definition
A computer program is said to learn from experience E with respect to some class of tasks T
and performance measure P,if its performance at tasks in T,as measured by P,improves with
experience E.

Components of Learning System

19 | P a g e
Performance Element:
The performance element is the agent that acts in the world. It percepts and decides on
external actions.
Learning Element:
It responsible for making improvements, takes knowledge about performance element and
some feedback, determines how to modify performance element.
Critic:
It tells the learning element how agent is doing by comparing with the fixed standard of
performance.
Problem Generator:
This component suggests problems or actions that will generate new examples or experience
that helps the system to train further.
Let us see the role of each component with an example.
Example: Automated Taxi on city roads
Performance Element: consists of knowledge and procedures for driving actions.
eg:turning ,accelerating, breaking are the performance elements on roads.

Learning Element: It formulates goals.

Eg:learn rules for breaking,accelerating,learn geography of the city.

Critic: Observes world and passes information to learning element.

20 | P a g e
Eg:quick right turn across three lanes of traffic ,observe reaction of other drivers.

Problem Generator: Try south city road

Learning Paradigm:

• Rote learning
• Induction
• Clustering
• Analogy
• Discovery
• Genetic algorithms
• Reinforcement

Rote Learning:
Rote learning technique avoids understanding the inner complexities but focuses on
memorizing the material so that it can be recalled by the learner exactly the way it read or
heard.
Learning by memorization:
which avoids understanding the inner complexities the subject that is being learned.
Learning something from Repeating:
saying the same thing and trying to remember how to say it;it does not help to understand ,it
helps to remember ,like we learn a poem,song ,etc.

There are two types of inductive learning,

· Supervised
· Unsupervised

Supervised learning:( The machine has access to a teacher who corrects it.)
learning is the machine learning task of inferring a function from labeled training data. The
training data consist of a set of training examples. In supervised learning, each example is a
pair consisting of an input object (typically a vector) and a desired output value (also called
the supervisory signal). Example : Face recognition
Unsupervised Learning:( No access to teacher. Instead, the machine must search for “order”
and “structure” in the environment.)

since there is no desired output in this case that is provided therefore categorization is done so
that the algorithm differentiates correctly between the face of a horse, cat or human
(clustering of data)

21 | P a g e
Clustering:

In clustering or unsupervised learning, the target features are not given in the training examples.
The aim is to construct a natural classification that can be used to cluster the data. The general
idea behind clustering is to partition the examples into clusters or classes. Each class predicts
feature values for the examples in the class. Each clustering has a prediction error on the
predictions. The best clustering is the one that minimizes the error.
Example: An intelligent tutoring system may want to cluster students' learning behavior so that
strategies that work for one member of a class may work for other members.
Reinforcement Learning:
Imagine a robot that can act in a world, receiving rewards and punishments and
determining from these what it should do. This is the problem of reinforcement
[Link] Reinforcement Learning research is conducted with in the mathematical
framework of Markov Decision Process.

Adaptive Learning
The fourth generation of machine intelligence, adaptive learning, creates the first truly
integrated human and machine learning environment. For text analytics, this has given us the
most accurate analytics to date, allowing us to get actionable information in many areas for the
first time. In the examples we will share here, we show that adaptive learning is 95% accurate
in predicting people’s intention to purchase a car. Adaptive learning correlates with actual
sales, unlike any previous approach to Machine Intelligence.
Adaptive learning combines the previous generations of rule-based, simple machine learning,
and deep learning approaches to machine intelligence. Human analysts are optimally engaged
in making the machine intelligence smarter, faster, and easier to interpret, building on a
network of the previous generations of machine intelligence.
The first generation of machine intelligence meant that people manually created rules. For
example, in text analytics someone might create a rule that the word “Ford” followed by
“Focus” meant that “Ford” referred to a car, and they would create a separate rule that “Ford”
preceded by “Harrison” meant that “Ford” referred to a person.
The rule-based approach is very time consuming and not very accurate. Even after an analyst
has exhausted all the words and phrases they can think of, there are always other contexts and
22 | P a g e
new innovations that aren’t captured. For one of our clients, their experts analysts were only
able to capture 11% of the documents they wanted to analyze using rules: this clearly is too
limited.
The dominant form of machine intelligence today is simple machine learning. Simple machine
learning uses statistical methods to make decisions about data processing. For example, a
sentence might have the word “Ford” labeled as a car, and the machine learning algorithm will
learn by itself that the following word “Focus” is evidence that “Ford” is a car in this context.
Simple machine learning can be fast, provided that you already have labeled examples for
‘supervised learning’. It also tends to be more accurate, because statistics are usually better
than human intuition in deciding which features (like words and phrases) matter. The major
drawback for supervised machine learning is that you need the labeled examples: if you have
too few labels or the labels aren’t representative of the entire data set, then the accuracy is low
or limited to a specific domain.
There has been a recent rise in the use of machine learning that learns more sophisticated
relationships between features, known as deep learning. For example, if you had the sentence
“We Will Let Harrison Ford Focus on Star Wars”, there is conflicting evidence between
“Harrison” and “Focus” about whether “Ford” is a person or a car.
Deep learning can automatically learn how to use combinations of features when making a
decision. For simple machine learning, a human has to tell the algorithm which combination of
features to consider. Deep learning often cuts down on the amount of human time needed and
typically gets up to 5% more accurate results than simple machine learning for text analytics–
although only when applied to data from the same sources as it learned from.
Adaptive learning brings human analysts into the process at every step. This is in contrast to
rule-based, simple machine learning and deep learning approaches, where the humans only
create rules and label data at the start of the process. For example, if you had the sentence “We
Will Help Tom Ford Escape from New York”, and your system hadn’t seen any examples of
“Tom Ford” or “Ford Escape”, you will need human input to build the knowledge.
Adaptive learning systems require the least human effort because they only require human
input when it matters most and continually expand their knowledge when new information is
encountered. As we show here, they are also the most accurate. They combine the three other
types of machine intelligence, adding new types of ‘unsupervised machine learning’ and
methods for optimizing the input from multiple, possibly disagreeing, humans.

*****************************

23 | P a g e