ITCS661 - Lecture 2 (1).pdf

Lecture 2 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. Agent, Envi...

Lecture 2 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. Agent, Environment, and State 2. Planning and State-space Exploration 3. Search Algorithms 4. Uninformed Search Strategies 1. Agent, Environment, and State Utility-based, model-based Agent prev state observation Memory State Function cur state trial action Transition function Environment future state Exploration Strategy Utility function no Best yes action outcome? Agent Example: Tower of Hanoi Example: Collect and Goal 6 1 7 5 4 3 2 G Poll: Can you come up with a good order of the balls we should collect? 2. Planning and State-space Exploration Planning: Assumptions and Objectives Activity 1: Find a plan for the least energy path. Assume that - the state contains X and Y variable. - the actions include {Up, Down, Left, Right} On a piece of paper, please answer the following questions 1. If the goal is to get to the door using least energy, what should be the utility function? 2. From the current state, if Joe takes actions [D, D], what is the resulting state? 3. Find at least 3 plans to take Joe to the door and Energy Cost: their associated utility values. 8, 1, 2, 6 4. Suggest a general method or insight to find an optimal plan. State Space State-Space Exploration 3. Search Algorithms Search Problem Formulation Example: Pathfinding Step 1 Formulation Example: Routing Example: Rubik Cube F’ U Example: 8-Puzzle Example: Abstract State-Space Graph Graph Search Algorithm 4. Uninformed-Search Strategies Strategy 1: Depth-First Search (DFS) Strategy 2: Breadth-First Search (BFS) Depth-First Search (DFS) Evaluation Breadth-First Search (BFS) Evaluation Combining DFS and BFS Strategy 3: Iterative-Deepening Search (IDS) Strategy: Repeatedly run DFS but increasing the limit of depth each round - Round 1: Run a DFS with depth limit 1, if no solution… - Round 2: Run a DFS with depth limit 2, if no solution… - Round 3: Run a DFS with depth limit 3, if no solution… - … - Round n: Run a DFS with depth limit n + step Wasteful? Strategy 3: Iterative-Deepening Search (IDS) Iterative-Deepening Search (IDS) Evaluation