Lecture - 3
Introduction to Production Systems and
Issues in Design of Search Programmes
VALLURI NIKHIL CHANDRA
R NO : 19092007
DTI
Contents
Introduction to AI
Production System(PS)
Characteristics of PS
Heuristic Search Process
Issues in Design of Search
Process
Traditional Programming Artificial Intelligence
Data Algorithm Data Algorithm Output
Machine Artificial Intelligence
Output Modified Algorithm
Output
Huge data , High computing power , High Performance
Algorithms demanded AI.
Machine learning and Deep Learning are integral parts
which form CORE part of intelligence.
AI problem solving technique
Define the problem with all
necessary specifications,
initial state and final state.
Analyze the problem by
decomposing it into micro
problems.
Search & Process individual
solution and integrate to
form a final solution.
Integration with least effort
will be our optimal path.
Production System
Definition:
Core of Intelligence
Search & Process “Production Systems” are
structures which
provides and facilitates
the performing of these
search processes
A Production System mainly consists of :
1) Rule : Action lookup
2) DataBases
3) Control Strategies
Production Systems
Rule:Action DataBase Control
This lookup Which will Strategy
will help you to contain the Which helps to
determine necessary determine the
which action to knowledge base order in which
perform when Of the required the rules should
Rule is Domain(s). be applied.
satisfied.
Designing a Production System
Problem Statement
Micro Micro Micro
.............
Problem-1 Problem-2 Problem-n
RULE:ACTION RULE:ACTION RULE:ACTION
Set-1 set-2 . . . . . set-n
Production System
Features of Production System
Simplicity
Modifiability Production Modularity
System
Knowledge
Intensive
Ref: https://www.analyticsindiamag.com/ai-production-system-basic/
Production System Characteristics:
We can characterise a Production System based on which
Class of Production System it belongs to and what is the
Relationship between the production system and problem
type.
Classes of Production System:
Monotonic : The application of a rule never prevents the
later application of another rule that could also have been
applied at the time the first rule was selected.
NON- Monotonic: isn’t a monotonic!
Partially Commutative : which have a property that if
a set of rules in this PS convert the state x of a process
to state y , then any permutations of those rules, that is
allowable, will also convert state x to state y.
Commutative: A production system which is both
monotonic and partially commutative.
Not Partially Commutative : which have a property
that if a set of rules in this PS convert the state x of a
process to state y , then any permutations of those rules,
that is allowable, will never convert state x to state y.
Production System Problem
Monotonic Ignorable
NON- Recoverable
Monotonic
Partially Irrecoverable
Commutative
Commutative Certain/
Uncertain
Examples:
Class of PS Monotonic Non-
Monotonic
Partially Theorem Blocks
Commutative Proving Problem
(Ignorable & (Recoverable
Certain) and Certain)
Not Partially Irreversible Card games
Commutative process (Irrecoverable
(chemical and
synthesis) Uncertain)
Control Strategies of PS
As we learned, we require a good and suitable control
structure, for the production system ,so that the search can
be as efficient as possible.
A search method provides a way to find solution for a
problem by trying different sequences of actions/
operators until a solution is found.
Some of the Control Strategies(Search Methodologies) are
: BFS ,DFS.
Search Strategies are evaluated along the following
dimensions:
Completeness
Optimality
Time & Space complexities
(0,0)
(0,3) (5,0)
(3,3) (2,3)
(5,1) (0,2)
DFS
(0,1)
(5,2)
(1,0)
(4,3)
(1,3)
(4,0)
BFS
(4,3)
From above we could design a PS:
Consider both the jars(x-> 5liters jar,y -> 3 liters jar)
are empty in first step therefore :
(x=0,Y=0 : Fill up the 3-liter jar(y=3)
(Rule : Action)
Similarly it can be structured completley using
different rules and these rules are accessed using
control strategies.
Figure 1
Ref: Elain Rich & Kevin Knight
Redundancy:
Multiple Nodes may occur
repeatedly.
Matching: Direction
Improper of
Matching Traverse:
may lead to Issues in Forward /
Locked Design Backward
states, due to according to
redunancy of the Problem
states
Node Representation:
Dynamic node
representation needed
Matching and Redundancy:
If Proper Matching is not performed due to the Redundant
states (0,0) &(4,3) may lead to locked states which results in
the paths of arbitary lenghts.
Dynamic node
Representation:
A node in a chess
may require an array
of Positions along
with cartesian
co-ordinates and
a set of variables
to count the number
of deadspots to
predict the further
moves.
Issues in Design of Search Programs
So instead of traversing a search Tree we traverse a
search Graph.
Since all the nodes are saved in the search Graph ,
redundancy can be eliminated.(Fig:2)
But here in the directed graphs we could see the loop like
structures (Lock stage) which are created due to
redundancy and may lead to paths with arbitrary length.
So it may become more difficult to show that a graph
traversal algorithm is guaranteed to terminate.
Issues in Design of Search Programs
Graph search process are especially useful for dealing
with the partial commutative PS in which the given set of
operations may produce identical states regardless of the
order in which operations are applied.
Thisis what we observed in the above water jug model
problem.
Additional Problems:
Missionaries and Cannibals
Crypto arithmetic…etc
Artificial intelligence is not merely a science of toy
problems but many of these techniques that have
been developed from these problems have become
the Core of the systems used to solve vital queries.
