chapter3-search.pdf

1Introduce to Artificial Intelligence Solving Problems by Lecturer：Zhaoman Department of Computer Science, Computer School China University of Geosciences Searching : Chapter 3 Outline Problem-solving agents – A kind of goal-based agent Problem types – Single state (fully observable) Lecturer：Zhaoman, Department of Computer Science, CS, CUG – Search with partial information Problem formulation – Example problems Basic search algorithms – Uninformed Example: Romania ? On holiday in Romania; currently in Arad ? Flight leaves tomorrow from Bucharest ? Formulate goal ? Be in Bucharest Lecturer：Zhaoman, Department of Computer Science, CS, CUG ? Formulate problem ? States: various cities ? Actions: drive between cities ? Find solution ? Sequence of cities; e.g. Arad, Sibiu, Fagaras, Bucharest, … Problem-solving agent ? Four general steps in problem solving: ? Goal formulation ? What are the successful world states ? Problem formulation ? What actions and states to consider given the goal Lecturer：Zhaoman, Department of Computer Science, CS, CUG ? Search ? Determine the possible sequence of actions that lead to the states of known values and then choosing the best sequence. ? Execute ? Give the solution perform the actions. Searching is about the exploration of alternatives. Problem-solving agent function SIMPLE-PROBLEM-SOLVING-AGENT(percept) return an action static: seq, an action sequence, initially empty state, some description of the current world state goal, a goal problem, a problem formulation state ? UPDATE STATE(state percept) Lecturer：Zhaoman, Department of Computer Science, CS, CUG - , if seq is empty then goal ? FORMULATE-GOAL(state) problem ? FORMULATE-PROBLEM(state,goal) seq ? SEARCH(problem) action ? FIRST(seq) seq ? REST(seq) return action Problem types ? Deterministic, fully observable ? single state problem ? Agent knows exactly which state it will be in; solution is a sequence. ? Partial knowledge of states and actions: ? Non-observable ? sen