(A star) Search in AI

• A* search algorithm is algorithm.
• Used to find the optimal path from the initial state to the goal state.
• A* search algorithm evaluates nodes by using the function,

f(n) = g(n) + h(n)

• g(n) = Cost from initial state to the state at the current node n
• h(n) = Estimated cost from the state at node n to a goal state

(A star) Search in AI

A

B

C

D

E

F

G

1

4

2

3

5

2

3

4

1

(A star) Search in AI

A

B

C

f(n) = g(n) + h(n)

C

D

E

F

G

G

Path: A → B → D → F → G

Path Cost: 7

Greedy Best First Search in AI

• Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly.
• Thus, it evaluates nodes by using the heuristic function; that is,

f(n) = h(n)

• h(n) = estimated cost from the state at node n to a goal state

Greedy Best First Search

A

D

B

F

E

G

40

32

25

35

19

17

10

0

C

H

f(B)=h(B)=32

f(D)=h(D)=35

f(C)=h(C)=25

START

END

Greedy Best First Search

A

D

B

F

E

G

40

32

25

35

19

17

10

0

C

H

f(F)=h(F)=17

f(E)=h(E)=19

START

END

Greedy Best First Search

A

D

B

F

E

G

40

32

25

35

19

17

10

0

C

H

f(D)=h(D)=35

f(G)=h(G)=0

START

END

Path: A → C → F → G

Uniform Cost Search Algorithm

• Uniform-cost search (Branch & Bound) is an uninformed search algorithm in Artificial Intelligence
• UCS algorithm uses the lowest cumulative cost to find a path from the source node to the goal node.
• Nodes are expanded, starting from the root, according to the minimum cumulative cost.
• The uniform-cost search is implemented using a Priority Queue.

Uniform Cost Search Algorithm

• Insert the root node into the priority queue.
• Remove the element with the highest priority.
• If the removed node is the goal node,
• print total cost and stop the algorithm
• Else
• Enqueue all the children of the current node to the priority queue, with their cumulative cost from the root as priority and the current node to the visited list.

Uniform Cost Search Algorithm

Start

A

B

C

G

F

E

End

1

3

5

3

5

2

1

Uniform Cost Search Algorithm

Start

A

B

C

G

F

D

End

1

3

5

3

5

2

1

Start

A

B

C

G

F

D

End

1

3

5

3

5

2

1

1

3

5

4

8

7

8

Path: Start → C → D → End

AO Star Search Algorithm

• AO* algorithm is a heuristic search algorithm in AI
• AO* algorithm uses the concept of AND-OR graphs to decompose any complex problem given into smaller set of problems which are further solved.
• Working of AO* algorithm:
• The AO* algorithm works on the formula given below :

f(n)=g(n)+h(n)

where,

g(n): The actual cost of traversal from initial state to the current state.

h(n): The estimated cost of traversal from the current state to the goal state.

f (n): The actual cost of traversal from the initial state to the goal state.

AO Star Search Algorithm

• Here, in the above example all numbers in brackets are the heuristic value i.e. h(n).
• Each edge is considered to have a value of 1 by default.

A

B

C

D

E

F

G

H

I

J

4

6

8

2

3

0

0

0

2

AO Star Search Algorithm

• Step-1
• Starting from node A, we first calculate the best path.
• f(A-B) = g(B) + h(B) = 1+4= 5, where 1 is the default cost value of travelling from A to B and 4 is the estimated cost from B to Goal state.
• f(A-C-D) = g(C) + h(C) + g(D) + h(D) =1+2+1+3 = 7, here we are calculating the path cost as both C and D because they have the AND-Arc.
• The default cost value of travelling from A-C is1, and from A-D is 1, but the heuristic value given for C and D are 2 and 3 respectively hence making the cost as 7.

A

B

C

D

E

F

G

H

I

J

4

6

8

2

3

0

0

0

2

5

7

AO Star Search Algorithm

• Step-2
• From the B node,

f(B-E)=1+6=7

f(B-F)=1+8=9

• Hence, the B-E path has lesser cost. Now the heuristics have to be updated since there is a difference between actual and heuristic value of B.
• The minimum cost path is chosen and is updated as the heuristic, in our case the value is 7.. And because of change in heuristic of B there is also change in heuristic of A which is to be calculated again.

f(A-B)=g(B)+ updated((h(B))=1+7=8

A

B

C

D

E

F

G

H

I

J

6

8

2

3

0

0

0

2

5

7

7

9

4

AO Star Search Algorithm

• Step-2
• From the B node,

f(B-E)=1+6=7

f(B-F)=1+8=9

• Hence, the B-E path has lesser cost. Now the heuristics have to be updated since there is a difference between actual and heuristic value of B.
• The minimum cost path is chosen and is updated as the heuristic, in our case the value is 7.. And because of change in heuristic of B there is also change in heuristic of A which is to be calculated again.

f(A-B)=g(B)+ updated((h(B))=1+7=8

A

B

C

D

E

F

G

H

I

J

6

8

2

3

0

0

0

2

5

7

7

9

4 7

5 8

AO Star Search Algorithm

Step-3

• Now the current node becomes C node and the cost of the path is calculated,

f(C-G) = 1+2 = 3

f(C-H-I) = 1+0+1+0 = 2

f(C-H-I) is chosen as minimum cost path.

• Heuristic of path of H and I are 0 and hence they are solved,
• But Path A-D also needs to be calculated , since it has an AND-arc.
• f(D-J) = 1+0 = 1, hence heuristic of D needs to be updated to 1.
• And finally the f(A-C-D) needs to be updated.

f(A-C-D) = g(C) + h(C) + g(D) + updated((h(D))= 1+2+1+1 =5.

A

B

C

D

E

F

G

H

I

J

6

8

2

3

0

0

0

2

7

7

9

4 7

5 8

3

2

1

Solved

AO Star Search Algorithm

Step-3

• Now the current node becomes C node and the cost of the path is calculated,

f(C-G) = 1+2 = 3

f(C-H-I) = 1+0+1+0 = 2

f(C-H-I) is chosen as minimum cost path.

• Heuristic of path of H and I are 0 and hence they are solved,
• But Path A-D also needs to be calculated , since it has an AND-arc.
• f(D-J) = 1+0 = 1, hence heuristic of D needs to be updated to 1.
• And finally the f(A-C-D) needs to be updated.

f(A-C-D) = g(C) + h(C) + g(D) + updated((h(D))= 1+2+1+1 =5.

A

B

C

D

E

F

G

H

I

J

6

8

2

3

0

0

0

2

7

7

9

4 7

5 8

3

2

1

3 1

7 5

Solved

Solved

Solved

Solved

Solved

Transition Model (Toy Problem)

• A problem can be defined formally by six components:
• States
• Initial State
• Actions
• Transition Model
• Goal Test
• Path Cost

A

B

Transition Model (Toy Problem)

• States: The state is determined by both the agent location and the dirt locations.
• The agent is in one of two locations, each of which might or might not contain dirt.
• Thus, there are 2 x 2² = 8 possible world states.
• A larger environment with n locations has n x 2ⁿ states.

A

B

Transition Model (Toy Problem)

1. {Loc(A), Dirty(A), Dirty(B)}

2. {Loc(A), Clean(A), Dirty(B)}

3. {Loc(A), Dirty(A), Clean(B)}

4. {Loc(A), Clean(A), Clean(B)}

5. {Loc(B), Dirty(A), Dirty(B)}

6. {Loc(B), Clean(A), Dirty(B)}

7. {Loc(B), Dirty(A), Clean(B)}

8. {Loc(B), Clean(A), Clean(B)}

A

B

Transition Model (Toy Problem)

• Initial state: Any state can be designated as the initial state.
• Actions: Each state has just three actions:
• Left, Right, and Suck.

A

B

Transition Model (Toy Problem)

• Transition model: The actions have their expected effects, except that moving Left in the leftmost square, moving Right in the rightmost square, and Sucking in a clean square have no effect.

B

A

Transition Model (Toy Problem)

• Goal test: This checks whether all the squares are clean
• Path cost: Each step costs 1, so the path cost is the number of steps in the path.

B

A

Transition Model (Toy Problem)

R

L

R

L

S

S

S

S

S

S

S

R

R

R

L

R

L

L

L

L

R

R

L

S