ITCS661 - Lecture 3 (1) (1).pdf

Lecture 3 Thanapon Noraset Faculty of ICT, Mahidol University Adapted from AIMA by Stuart Russell and Peter Norvig, and UC Berkeley CS188 by Dan Klein and Pieter Abbeel (ai.berkeley.edu) Announcements & Agenda 1. Uninformed...

Lecture 3 Thanapon Noraset Faculty of ICT, Mahidol University Adapted from AIMA by Stuart Russell and Peter Norvig, and UC Berkeley CS188 by Dan Klein and Pieter Abbeel (ai.berkeley.edu) Announcements & Agenda 1. Uninformed Search Strategies a. Depth-First Search b. Breadth-First Search c. Iterative-Deepening Search d. Uniform-Cost Search 2. Informed Search Strategies a. Heuristic Function b. Greedy Search c. A* Search d. Admissibility and Consistency 1. Uninformed-Search Strategies (cont.) Path Cost Function: g(n) Modified Graph Search Algorithm Strategy 4: Uniform Cost Search (UCS) Uniform Cost Search (UCS) Evaluation 2. Informed Search Strategies Heuristic Function: h(s) Example: Heuristic Functions for Pathfinding Example: Abstract State Space with Heuristic Values 4 0 5.5 2 1.5 4.5 1.5 7 3 6 2.5 4.5  Strategy 5: Greedy Best-First Search (GS) State h(s) State h(s) S 7 f 1.5 a 4 h 3 b 5.5 p 6 c 2 q 4.5 d 4.5 r 2.5 e 1.5 G 0 Greedy Best-First Search (GS) Evaluation Path Cost Function + Heuristic Function: f(n)  Strategy 6: A* Search State h(s) State h(s) S 7 f 1.5 a 4 h 3 b 5.5 p 6 c 2 q 4.5 d 4.5 r 2.5 e 1.5 G 0 A* Evaluation Optimality of A*: Admissibility Poll: Why do you think A* fails here? Optimality of A*: Consistency Activity: Romania Path Finding (Extra) Heuristic Functions How to get admissible heuristic functions Inadmissible (pessimistic) heuristics Admissible (optimistic) heuristics Example: Heuristic functions for pathfinding 4.5 Example: Heuristic functions for 8-puzzle (1) Example: Heuristic functions for 8-puzzle (2) 7 2 4 Example: Heuristic 1 vs Heuristic 2 Summary Planning = Search Problem → Graph Search → A sequence of actions Exploration Strategy: Choose the ____ nodes in the open set first - DFS: Deepest - BFS: Shallowest - IDS runs DFS with depth limit several times - UCS: Cheapest (path cost) - GS: Closest (heuristic) - A*: Lowest f-value - Admissibility - Consistency