Heuristic in AI (Rule of thumb) [what, why, how] What: Mental shortcuts that ease the cognitive load of making a decision. Why: Solve problems and speed up our decision-making process How: Eucledian Distance, Manhattan Distance, etc

Estimated cost (or distance) of minimal cost path from start to a goal state.
h(n) → a heuristic function
Purpose of heuristic function is to guide the search process in the most profitable path among all that are available

1. Intelligent Systems Course No. CS 6109 / CE 7205

2. Objective Introduction Informed Search Strategies Heuristic Search & Function Greedy best-first search A* search

3. Introduction Search with domain knowledge. Uninformed (blind) searches are normally very inefficient. Why?????? Adding domain knowledge can improve the search process. Heuristic Search Greedy Best-First Search A* Search

4. Informed methods add domain-specific information Estimated cost (or distance) of minimal cost path from start to a goal state. h(n) → a heuristic function Purpose of heuristic function is to guide the search process in the most profitable path among all that are available

5. Heuristic Solution Heuristic in AI (Rule of thumb) [what, why, how] What : Mental shortcuts that ease the cognitive load of making a decision. Why : Solve problems and speed up our decision-making process How: Eucledian Distance, Manhattan Distance, etc It is a provide the Good Solution. But not provides the guarantee of the optimal solution .

6. Eucledian Distance Calculate Distance using Pythagoras theorem. X-Axis Y-Axis (x 1 ,y 1 ) (x 2 ,y 2 ) A B C AC 2 = AB 2 + BC 2 AC = AB 2 + BC 2 AC = (x 2 -x 1 ) 2 + (y 2 -y 1 ) 2 x 1 x 2 y 1 y 2

7. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal

8. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal 1

9. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal 1 2 1

10. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal 1 2 3 1 1

11. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal 1 2 3 4 1 1 2

12. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal 1 2 3 4 5 1 1 2

13. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal 1 2 3 4 5 6 1 1 2 2

14. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal 1 2 3 4 5 6 7 1 1 2 2 2

15. Manhattan Distance Taking 8–Puzzle Problem 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Start State Goal 1 2 3 4 5 6 7 8 1 1 2 2 2 Manhattan Distance: 0+1+1+2+0+2+2+0 = 8

16. Manhattan Distance Method 1 Calculate MD value 1 3 2 6 5 4 8 7 Start State Goal 1 3 2 5 4 6 8 7 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Move UP: 0+1+1+2+0+3+2+0 = 9 Move Right: 0+1+1+2+0+2+2+1 = 9

17. Manhattan Distance Method 2 Calculate Misplaced Tile 1 3 2 6 5 4 8 7 Start State Goal 1 3 2 5 4 6 8 7 1 3 2 6 5 4 8 7 1 2 3 4 5 6 7 8 Move UP: 0+1+1+1+0+1+1+0 = 5 Move Right: 0+1+1+1+0+1+1+1 = 6

18. 8-Puzzle Problem with Heuristic 1 2 3 4 6 7 5 8 1 2 3 7 4 6 5 8 1 2 3 4 6 7 5 8 1 2 3 4 6 7 5 8 2 3 1 4 6 7 5 8 1 2 3 4 6 7 5 8 1 2 3 4 5 6 7 8 Start State Goal Move UP h=4 Move Down h=4 Move Right h =2 Move Left (NA) h =Nil Initial h=3

19. 8-Puzzle Problem with Heuristic 1 2 3 4 6 7 5 8 1 2 3 4 5 6 7 8 1 2 3 4 6 7 5 8 1 2 3 4 6 7 5 8 1 3 4 2 6 7 5 8 1 2 3 4 6 7 5 8 1 2 3 4 5 6 7 8 Start State Goal Move UP h=3 Move Down h=1 Move Right h =3 Move Left h =3 Previous h=2

20. 8-Puzzle Problem with Heuristic 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 6 7 5 8 1 2 3 4 6 7 5 8 1 2 3 4 5 6 7 8 Start State Goal Move UP h=2 Move Down (NA) h=Nil Move Right h =0 Move Left h =1 Previous h=1 1 2 3 4 5 6 7 8

21. Heuristic Search - Characteristics Has some domain knowledge Usually more efficient than blind searches Also called informed search Heuristic searches work by deciding which is the next best node to expand (there is no guarantee that it is the best node)

22. Greedy Best-First Search Greedy best-first search algorithm always selects the path which appears best at that moment. It is the combination of depth-first search and breadth-first search algorithms. It uses the heuristic function and search. Best-first search allows us to take the advantages of both algorithms .

23. Greedy Best-First Search Expand the node with the lowest expected cost. Not always guaranteed to find an optimal solution . Behaves like DFS: follows to depth paths that look promising. Advantage : moves quickly towards the goal. Disadvantage : can get stuck in deep paths.

24. GBS – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes Node H(n) Closed List Open List

25. GBS – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes Node S H(n) 7 Closed List Open List Distance:

26. GBS – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 Node A B H(n) 9 8 Closed List Open List Distance:

27. GBS – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 Node A B H(n) 9 8 Closed List Open List Distance:

28. GBS – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 B/8 Node A C G H(n) 9 5 Closed List Open List Distance: 1 +

29. GBS – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 B/8 Node A C G H(n) 9 5 Closed List Open List Distance: 1 +

30. GBS – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 B/8 G/0 Node A C H(n) 9 5 Closed List Open List Distance: 1 + 12 = 13

31. GBS – Exampl e 2

32. A* Search A * algorithm is a searching algorithm that searches for the shortest path between the initial and the final state. f(n) =g(n) + h(n) g(n) = Actual cost from Start node to n node h(n) = Estimation Cost from n to Goal node. Time complexity = O(Node + Edges) = O(b d ) Space complexity = O(b d )

33. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes Nodes S h(n) 7 g(n) f(n) 7 Closed List Open List F(n) = g(n) + h(n) F(S) = 0 + 7 = 7 For Node S, g(n)= 0 h(n)=7

34. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 Nodes S h(n) 7 g(n) f(n) 7 Closed List Open List F(n) = g(n) + h(n) . .

35. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 Nodes SA SB h(n) g(n) f(n) Closed List Open List F(n) = g(n) + h(n) . .

36. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 Nodes SA SB h(n) 9 g(n) 1 f(n) 10 Closed List Open List F(n) = g(n) + h(n) F(A) = 1 + 9 = 10 For Node A, g(n)=1 h(n)=9

37. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 Nodes SA SB h(n) 9 g(n) 1 f(n) 10 Closed List Open List F(n) = g(n) + h(n) F(A) = 1 + 9 = 10 For Node A, g(n)=1 h(n)=9

38. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 Nodes SA SB h(n) 9 8 g(n) 1 1 f(n) 10 9 Closed List Open List F(n) = g(n) + h(n) F(B) = 1 + 8 = 9 For Node B, g(n)=1 h(n)=8

39. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 Nodes SA SB h(n) 9 8 g(n) 1 1 f(n) 10 9 Closed List Open List F(n) = g(n) + h(n) F(B) = 1 + 8 = 9 For Node B, g(n)=1 h(n)=8

40. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 Nodes SA SBC SBG h(n) 9 g(n) 1 f(n) 10 Closed List Open List F(n) = g(n) + h(n) . .

41. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 Nodes SA SBC SBG h(n) 9 5 g(n) 1 1+6 f(n) 10 12 Closed List Open List F(n) = g(n) + h(n) F(C) = 1 + 6 + 5 = 12 For Node C, g(n)=1+6 h(n)=5

42. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 Nodes SA SBC SBG h(n) 9 5 g(n) 1 1+6 1+12 f(n) 10 12 13 Closed List Open List F(n) = g(n) + h(n) F(G) = 1 + 12 + 0 = 13 For Node G, g(n)=1+6 h(n)=0

43. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 Nodes SA SBC SBG h(n) 9 5 g(n) 1 1+6 1+12 f(n) 10 12 13 Closed List Open List F(n) = g(n) + h(n) . .

44. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 Nodes SBC SBG SAB h(n) 5 g(n) 1+6 1+12 f(n) 12 13 Closed List Open List F(n) = g(n) + h(n) . .

45. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 Nodes SBC SBG SAB h(n) 5 8 g(n) 1+6 1+12 1+9 f(n) 12 13 18 Closed List Open List F(n) = g(n) + h(n) F(G) = 1 + 9 + 8 = 18 For Node B, g(n)=1+9 h(n)=8

46. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 SBC/12 Nodes SBC SBG SAB h(n) 5 8 g(n) 1+6 1+12 1+9 f(n) 12 13 18 Closed List Open List F(n) = g(n) + h(n) . .

47. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 SBC/12 Nodes SBG SAB h(n) 8 g(n) 1+12 1+9 f(n) 13 18 Closed List Open List F(n) = g(n) + h(n) . .

48. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 SBC/12 Nodes SBG SAB SBCG h(n) 8 g(n) 1+12 1+9 f(n) 13 18 Closed List Open List F(n) = g(n) + h(n) . .

49. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 SBC/12 Nodes SBG SAB SBCG h(n) 8 g(n) 1+12 1+9 1+6+5 f(n) 13 18 12 Closed List Open List F(n) = g(n) + h(n) F(G) = 1 + 6 + 5 = 12 For Node G, g(n)=1+6+5 h(n)=0

50. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 SBC/12 SBCG/12 Nodes SBG SAB SBCG h(n) 8 g(n) 1+12 1+9 1+6+5 f(n) 13 18 12 Closed List Open List F(n) = g(n) + h(n) F(G) = 1 + 6 + 5 = 12 For Node G, g(n)=1+6+5 h(n)=0

51. A* – Exampl e 1 Path H(n) Cost S->A 7 1 S->B 7 1 A->B 9 9 B->C 8 6 B->G 8 12 C->G 5 5 S/7 B/8 A/9 C/5 G/0 1 1 9 12 6 5 Nodes S/7 SB/9 SA/10 SBC/12 SBCG12 Nodes SBG SAB h(n) 8 g(n) 1+12 1+9 f(n) 13 18 Closed List Open List F(n) = g(n) + h(n) . .

52. A* – Exampl e 2

53. Summary Greedy search: Estimated cost of reaching goal from current state – Heuristic evaluation functions, h(n). A* search: f(n) = g(n) + h(n). A* uses both backward costs and (estimates of) forward costs. Admissibility: h(n)never overestimates the actual cost of getting to the goal state.

54. Query Regarding Lecture Email: [email protected]

55. Thanks Email: [email protected]