PROBLEM SOLVING AND SEARCH CHAPTER 3 Chapter 3 1
Problem solving and search Chapter 3 Chapter 3 1
Reminders Assignment 0 due 5pm today Assignment 1 posted,due 2/9 Section 105 will move to 9-10am starting next week Chapter 3 2
Reminders Assignment 0 due 5pm today Assignment 1 posted, due 2/9 Section 105 will move to 9-10am starting next week Chapter 3 2
Outline Problem-solving agents ◇Problem types ◇Problem formulation ◇Example problems Basic search algorithms Chapter 33
Outline ♦ Problem-solving agents ♦ Problem types ♦ Problem formulation ♦ Example problems ♦ Basic search algorithms Chapter 3 3
Problem-solving agents Restricted form of general agent: function SIMPLE-PROBLEM-SOLVING-AGENT(percept)returns an action static:seg,an action sequence,initially empty state,some description of the current world state goal,a goal,initially null problem,a problem formulation stateUPDATE-STATE(state,percept) if seg is empty then goal-FORMULATE-GOAL(state) problem+FORMULATE-PROBLEM(state,goal) seg-SEARCH(problem) action-RECOMMENDATION(seg,state) seg-REMAINDER(seg,state) return action Note:this is offline problem solving;solution executed "eyes closed." Online problem solving involves acting without complete knowledge. Chapter 3 4
Problem-solving agents Restricted form of general agent: function Simple-Problem-Solving-Agent( percept) returns an action static: seq, an action sequence, initially empty state, some description of the current world state goal, a goal, initially null problem, a problem formulation state ← Update-State(state, percept) if seq is empty then goal ←Formulate-Goal(state) problem ←Formulate-Problem(state, goal) seq ← Search( problem) action ←Recommendation(seq,state) seq ← Remainder(seq,state) return action Note: this is offline problem solving; solution executed “eyes closed.” Online problem solving involves acting without complete knowledge. Chapter 3 4
Example:Romania On holiday in Romania;currently in Arad. Flight leaves tomorrow from Bucharest Formulate goal: be in Bucharest Formulate problem: states:various cities actions:drive between cities Find solution: sequence of cities,e.g.,Arad,Sibiu,Fagaras,Bucharest Chapter 3 5
Example: Romania On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest Formulate goal: be in Bucharest Formulate problem: states: various cities actions: drive between cities Find solution: sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest Chapter 3 5