第 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 ..
评论 (0)
暂无评论。快来抢沙发吧！