Artificial Intelligence State space explanation with solutions for MCA 2016
Production Systems:
Systems that generate (produce) rules (states) to reach a solution
A production system commonly consists of following four basic components:
1. A set of rules of the form CiAiwhere Cirefers to starting state and Airepresents consequent state. Also Cithe condition part and Aiis the action part.
2. One or more knowledge databases that contain whatever information is relevant for the given problem.
3. A control strategy that ascertains the order in which the rules must be applied to the available database
4. A rule applier which is the computational system that implements the control strategy and applies the rules to reach to goal (if it is possible).
State space search is a process used in which successive or statesof an instance are
considered, with the goal of finding a goal statewith a desired property.
State space search often differs from traditional search (sequential, indexed sequential,
binary search etc) methods because the state space is implicit: the typical state space
graph is much too large to generate and store in memory. Instead, nodes are generated
as they are explored, and typically discarded thereafter.
E.g. in a tic tack toe game, every move by a player forms a state space and the three
similar (O or X) consecutive (row, column or diagonal) symbolsforms goal state.
In a chess game also state space forms a set of moves by players.
We discuss water jug problem in the next section.
State Space Search
The water jug problem:
You are given two jugs, a 4-litre one and a 3-litre one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly2 litres of water into 4-litre jug. Let x and y be the amounts of water in 4-Lt and 3-Lt Jugs respectively Then (x,y) refers to water available at any time in 4-Lt and 3-Lt jugs. Also (x,y) (x-d,y+dd) means drop some unknown amount d of water from 4-Lt jug and add dd onto 3-Lt jug. All possible production rules can be written as follows
1.(x, y)→(4, y) if x<4 4="" div="" fill="" ifx="" it="" nbsp="" remains="" to="" unchanged="" y="">
2.(x, y)→(x, 3)if y<3 3="" div="" fill="" ify="" it="" nbsp="" remains="" to="" unchanged="" x="">
3.(x, y)→(x −d, y) if there is some water in 4 Lt jug, drop
if x >0some more water from it
4.(x, y)→(x, y −d) if there is some water in 3 Lt jug, drop ify >0some more water from it
5. (x, y)→(0, y) if there is some water in 4-Lt, empty it, y remains unchanged ifx >0
6.(x, y)→(x, 0) if there is some water in 3-Lt, empty it, x remains unchanged ify >0
7.(x, y)→(4, y −(4 −x)) if there is some water in 3-Lt, the sum of ifx +y ≥4,y >0 water of 4-Lt and 3-Lt jug is >=4, then fill water in 4-Lt jug to its capacity from 3-Lt jug
8.(x, y)→(x −(3 −y), 3) same as 7 with suitable change in x,y ifx +y ≥3,x >0
9. (x, y)→(x +y, 0) if sum of water in both jugs <=4, then drop ifx +y ≤4,y >0 whole water from 3-Lt into 4-Lt
10.(x, y)→(0, x +y) if sum of water in both jugs <=3, then drop ifx +y ≤3,x >0whole water from 4-Lt into 3-Lt
11.(0, 2)→(2, 0) Transfer 2-Lt from 3-Lt jug into empty 4-Lt jug
12.(2, y)→(0, y) Empty 2 Lt water onto ground from 4-Lt jug without disturbing 3 Lt jug
Solution of Water Jug Problem Obviously to solve water jug problem, we can perform following sequence of actions, (0,0) (0,3) (3,0) (3,3) (4,2) (0,2) (2,0) By applying rules 2,9,2,7,5 and 9 with initial empty jugs
Remember: There is NO hard and fast rules to follow this sequence. In any state space search problem, there can be numerous ways to solve, your approach can be different to solve a problem and sequence of actions too.
State Space Search Other problems
1. Cannibals and missionaries problems: In the missionaries (humans)and cannibals (human eaters) problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people. At any time number of cannibals on either side should not be greater than number of missionaries otherwise former will eat latter. Also The boat cannot cross the river by itself with no people on board.
2. Tower of Hanoi Problem: It consists of three pegs, and a number of disks ( usually 60) of different sizes which can slide onto any peg. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallestat the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
Only one disk must be moved at a time.
Each move consists of taking the upper disk from one of the rodsand sliding it onto another rod, on top of the other disks that may already be present on that rod.
No disk may be placed on top of a smaller disk.
3. Monkey Banana Problem: A monkey is in a room. A bunch of bananas is hanging from the ceiling and is beyond the monkey's reach. However, in the room there are also a chair and a stick. The ceiling is just the right height so that a monkey standing on a chair could knock the bananas down with the stick. The monkey knows how to move around, carry other things around, reach for the bananas, and wave a stick in the air. What is the best sequence of actions for the monkey?
