**Defining Problem as a State Space Search**

- A state space consists of a set of nodes representing each state of the problem, arc between nodes representing the legal moves from one state to another, an initial state and a goal state.

- A problem as a state space can be defined by:

a) initial state

b) actions

c) goal test

d) path cost

- The state space is represented as tree or graph

- A solution is a path from initial state to goal state

- A problem is called well defined problem if defined with a state space components.

Example: consider a problem given as:

- On holidays in Nepal ; currently in dharan.

- Flight leaves tomorrow from Kathmandu.

This problem can be well defined by defining it as a state space:

#initial state: Dharan

#actions : s(x)=set of action – state pairs

i.e s(dharan)= {itahari,itahari>,

saptari,saptari>,…….}

#goal test: x=Kathmandu

#path cost: sum of distances

#solution : sequence of actions leading from initial state to goal state.

**Problem Types; Well Defined Problems**

1) Single state problem deterministic,accessible)

- Agent knows about the world

- Can calculate optional action sequence solution

- Playing chess

2) Multi state problem (deterministic, inaccessible)

- Agent does not know exact state.

- State assumption to reach goal.

- Eg: walking in dark room

a) If you are at door, go straight leads to kitchen

b) If you are at kitchen, turn left leads to bedroom

3) Contingency problem(non-deterministic, inaccessible)

- Solution is tree of policy

- Interleave search

- Eg: new skater in an arena.

a) sliding problem

b) Other skaters

4) Exploration problem

- Unknown stare space

- Discover and learn about environment while acting

- Eg:maze

**Constraint Satisfaction Problem**

Constraint satisfaction problem is a search procedure that operates in a space of constraints.

Constraints are added by making a guess about something t. the problem can be defined as a set of variables(x1,x2…..)and constraints(c1,c2,……)constraint propagation terminates if no solution is consistent with known constraints and no further changes can be made based on current knowledge .

E.g.: crypto-arithmetic problems.

Q) solve the following crypto – arithmetic problems:

send more= money

ans:-

carry={0,1}

variable={S,E,N,D,M,O,R,Y}

numbers={0………………9)

constraints:

1) D+E= Y+10C1……………(1)

2) N+R+C1=E+10C2…………..(2)

3) R+O+C2=N+10C3……..(3)

4) S+M+C1=O+1C4………(4)

5) C4=M…….(5)

6) Every variable should have unique value.

Solving equation 5;

M=C4

Assuming that MSD can not be 0, hence c4=1

.·. M=1

Solving equation 4;

S+M+C3=0+10*1

S+c3+1=0+10

Here, to get C4=1

S=9(maximum value)

Then,

If C3=1, 0=1

If C3=0 , O=0

As 1 has already been mapped, O=0

So, equation 4 becomes:

S+C3+1=10………….(6)

Solving equation (3)

E+O+C3=N+10C3

.·.E+c2=N+10C3

As E and N can not have same value, it must differ by 1 so , C2=1

.·.E+1=N+10c3..(7)

To have c3=1, E must be 9, then :

N=0 (not possible)

So, c3=0

.·.E+1=N……..(8)

From equation (6)

S+0+1=10

.·. S=9

From equation 2:

N+R+c1=E+10C2

Or, N+R+C1=E+10

Or, (E+1)+R+C1=E+10(from 8)

Or , R+C1=9

If C1=0 , R=9 but 9 is already mapped

So, C1=1 and R=8

From equation 1;

D+E=Y+10C1

Or, D+E=Y+10………(9)

Here D and E sums up to give a number greater than 10, but, the minimum value for Y is 2. Since, 8 and 9 are already mapped and for Y to be at least 2, one of two D or E must be &.

If E=7, then N=8 (from 8), but * is already mapped.

So, D=7

The value of E most be or 6 for Y to be at least 2.

If E=6, y=3 and N =7 . but 7 is already mapped .

.·. E=5

From equation 9:

Y=2

From equation 8;

N=6

Hence , the solution is

9 5 6 7

+1 0 8 5

-----------------

1 0 6 5 2

RIGHT + RIGHT =WRONG

ANS

Carry ={0,1}

Variables={R,I,G,H,T,W,O,N}

Numbers ={0,1,2,…………..9}

Constraints:

1) 2T=G +10C1………..(1)

2) 2H+C1=N+10C2………(2)

3) 2G+C2=0+10C3……..(3)

4) 2I+C3=R+10C4……..(4)

5) 2R + C4=W……..(5)

6) Every variable should have unique value.

Solving equation (5)

2R+ C4=W

As 2R+C4 do not result in carry i.e. carry=0, the value of R may be 0,1,2,3 and 4

R Cy W

0 0 0

0 1 1

1 0 2

1 1 3

2 0 4

2 1 5

3 0 6

3 1 7

4 0 8

4 1 9

As MSB can not be 0; R can be 1,2,3 and 4.

Let R-1,Cy=0;W=2

2I + C3=1(from 4)

I=0 and C3=1

Solving equation 3,

C2+2C1=0+10C3

Or, C2+2C1=0+10

Here, the value of G must ranges from 5 to 9

G Cy W

5 0 0

5 1 1

6 0 2

6 1 3

7 0 4

7 1 5

8 0 6

8 1 7

9 0 8

9 1 9

Assume, G=7 and C20; => O=4

Solving equation 1;

2T=G+10C1

Or, 2T=7+10C1(not possible)

Here 10C1+7 yield odd number

Again,

Assume G-6 and C2=1;

0=3

Solving equation 1;

2T=G +10C1

Or, 2t=6=10c1

If C1=0;T=3[·.· not possible]

If c1=1;t=8

Solving equation 2;

2h+c1=n+10c2

Or 2h+1=n+10

Or 2h=n+9………(6)

Here, n must be odd for validity

So the possible values of n are 5,7 and 9

If n=5,2h=5+9

.·.h=7

The solution is :

1 0 6 7 8

1 0 6 7 8

-----------------

2 1 5 5 6

**Game playing and Production System**

- A production system is a system that consists of a set of rules. Each rule consists of a pattern on left side that determines applicability of rules and operation to be performed on right side if rule is applied.

- E.g.: for a vacuum world, assume a be the environment, then:

[a, clean]=>move right

[a, dirt]=>clean

- It also have control strategy that specifies order which rules will be selected and a way to resolve conflicts.

Ⓒ Copyright ESign Technology 2019. A Product of ESign Technology. All Rights Reserved.