Page 25 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 2: Problems, Problem Spaces and Search

Monotonic production system: A system in which the application of a rule never averts the later Notes
application of another rule, that could have also been applied at the time the first rule was chosen.

2.2.4 Partially Commutative Production System

A production system in which the application of a specific sequence of rules transforms state X
into state Y, then any permutation of those rules that is permissible also converts state X into
state Y.
Theorem proving falls under monotonic partially communicative system. Blocks world and 8
puzzle problems such as chemical analysis and synthesis come under monotonic, not partially
commutative systems. Playing the game of bridge comes under non monotonic, not partially
commutative system.
For any problem, numerous production systems exist. Some will be competent than others.
However it may appear that there is no association among kinds of problems and kinds of
production systems, in practice there is a definite relationship.
Partially commutative, monotonic production systems are functional for solving ignorable
problems. These systems are significant for man accomplishment standpoint since they can be
executed without the ability to back off to earlier states, when it is exposed that an incorrect path
was followed. Such systems augment the efficiency as it is not essential to keep track of the
changes done in the search process.

Monotonic partially commutative systems are functional for problems in which alterations take
place but can be upturned and in which the order of operation is not decisive (ex: 8 puzzle
problem).
Production systems that are not partially commutative are functional for many problems in
which permanent alterations happen, such as chemical analysis.

Did u know? When dealing with partially commutative production system, the order in
which operations are performed is very significant and therefore correct decisions have to
be made at the first time itself.
Self Assessment

Fill in the blanks:
4. A system that utilizes this form of knowledge representation is known as a ............................ .
5. Partially commutative, monotonic production systems are functional for solving
.................................... problems.
2.3 Breadth-first Search

In graph theory, breadth-first search (BFS) is a graph search algorithm that starts at the root
node and discovers all the adjacent nodes. Then for each of those adjoining nodes, it discovers
their unknown neighbor nodes, and so on, until it finds the objective.

2.3.1 How does it Work?

BFS is an uninformed search technique that intends to enlarge and scrutinize all nodes of a graph
or amalgamation of sequences by methodically penetrating via every solution. Alternatively, it

LOVELY PROFESSIONAL UNIVERSITY 19