1쪽
CS361(Artificial Intelligence) Lecture2 Problem Solving as Search Dr. Hala Abdel-Galil & Dr. Amr S. Ghoneim (Computer Science Dept.) Helwan University Fall 2019 Lectures are based on their counterparts in the following courses: o Intelligent Systems, University of British Columbia (Dept. of Computer Science) o Introduction to Artificial Intelligence, University of Wisconsin-Madison o Artificial Intelligence, University of Illinois at Urbana-Champaign o Artificial Intelligence, University of California, Berkeley 1
2쪽
Resourcesforthislecture o This lecture covers the following chapters: o Chapter 3 (Solving Problems by Searching; only sections 3.1, 3.2, & 3.3) from Stuart J. Russell and Peter Norvig, "Artificial Intelligence: A Modern Approach," Third Edition (2010), by Pearson Education Inc. … AND … o Part II (pages 41 to 45) and Chapter 3 (only sections 3.0, 3.1, and 3.2) from George F. Luger, "Artificial Intelligence: Structures and strategies for complex problem solving, " Sixth edition (2009), Pearson Education Limited.
3쪽
Outline o Solving problems by Searching o Types of agents o State Space Search o Example: Tic-Tac-Toe Game o Example: Mechanical Fault o State Space Search Strategies Diagnosing o State Space Search Strategies: o How human beings think? Selecting Search Strategy o Heuristic Search o Search: Basic idea o Search o Search tree o Search problem components o Tree Search Algorithm Outline o Example: Romania o Tree search example o State space o Handling repeated states o Example: Vacuum world o Backtracking Search o Vacuum world state space graph o Backtracking Algorithm Data o Example: The 8-puzzle Structure o Example: Robot motion o Backtracking Algorithm planning o Example: Tic- Tac-Toe o Example: Traveling Salesperson
5쪽
TypesofAgents Reflex agent Planning agent Consider how the world IS Consider how the world WOULD BE • Choose action based on current • Decisions based on (hypothesized) percept. consequences of actions. • Do not consider the future • Must have a model of how the world consequences of actions. evolves in response to actions. • Must formulate a goal. Source: D. Klein, P. Abbeel
6쪽
StateSpaceSearch Problems are solved by searching among alternative choices. o Humans consider a number of alternative strategies on their way to solving a problem. o A Chess player considers a number of alternative moves. o A mathematician chooses from a different strategies to find a proof for a theorem. o A physician evaluates a number of possible diagnoses.
8쪽
Example:MechanicalFaultDiagnosing Start ask: What is the problem? Engine trouble Transmission breaks … ask: ask:……… ask: …… Does the car start? Yes No Engine starts Engine won’t start ask: ask:………. Will engine turn over? Yes No battery Yes ok Turn over Won’t turn over ask: No ask: …….. Do lights come on? battery dead
9쪽
Howhumanbeingsthink? • Human beings do not search the entire state space (exhaustive search). • Only alternatives that experience has shown to be effective are explored. • Human problem solving is based on judgmental rules that limit the exploration of search space to those portions of state space that seem somehow promising. • These judgmental rules are known as “heuristics”.
10쪽
HeuristicSearch • A heuristic is a strategy for selectively exploring the search space. • It guides the search along lines that have a high probability of success. • It employs knowledge about the nature of a problem to find a solution. • It does not guarantee an optimal solution to the problem but can come close most of the time. • Human beings use a large number of heuristics in problem solving.
11쪽
Search We will consider the problem of designing goal-based agents in fully observable, deterministic, discrete, known environments. Start State Goal State
12쪽
Search We will consider the problem of designing goal-based agents in fully observable, deterministic, discrete, known environments. The agent must find a sequence of actions that reaches the goal. The performance measure is defined by: (a) reaching the goal, and … (b) how “expensive” the path to the goal is.
13쪽
SearchProblemComponents Initial Initial state State Actions Transition model What state results from performing a given action in a given state? Goal state Solution Path Path cost Assume that it is a sum of Goal nonnegative step costs State The optimal solution is the sequence of actions that gives the lowest path cost for reaching the goal.
14쪽
Example:Romania - On vacation in Romania; currently in Arad. - Flight leaves tomorrow from Bucharest. Initial state o Arad Actions o Go from one city to another Transition model o If you go from city A to city B, you end up in city B Goal state o Bucharest Path cost o Sum of edge costs (total distance traveled)
15쪽
StateSpace The initial state, actions, and transition model define the state space of the problem; • The set of all states reachable from initial state by any sequence of actions. • Can be represented as a directed graph where the nodes are states and links between nodes are actions. What is the state space for the Romania problem?
16쪽
StateSpace An AI problem can be represented as a state space graph. A graph is a set of nodes and links that connect them. Graph theory: o Labeled graph. ○ Parent. o Directed graph. ○ Child. o Path. ○ Sibling. o Rooted graph. ○ Ancestor. o Tree. ○ Descendant.
17쪽
StateSpace Graph Theory, Kônigsberg Bridges Problem, & Euler Tour .. Riverbank 1 4 River Island 1 1 Island 2 7 Riverbank 2
18쪽
StateSpace A state space is represented by four-tuple [N, A, S, GD]. o N, is the set of nodes or states of the graph. These correspond to the states in the problem-solving process. o A, is the set of arcs between nodes. These correspond to the steps in a problem-solving process. o S, a nonempty subset of N, contains the start-state (s) of the problem. o GD, a nonempty subset of N, contains the goal-state(s) of the problem. The states in GD are described using either: o A measurable property of the states encountered in the search. o A property of the solution path developed in the search (a solution path is a path through this graph from a node in S to a node in GD).
19쪽
Example:VacuumWorld o States: o Agent location and dirt location o How many possible states? o What if there are n possible locations? o The size of the state space grows exponentially with the “size” of the world! o Actions: o Left, right, suck. o Transition model ..
앞 19페이지만 표시됩니다. 전체를 보려면 자료를 다운로드하세요.
댓글 (0)
댓글이 없습니다. 첫 댓글을 남겨보세요!