Trang 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
Trang 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.
Trang 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
Trang 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
Trang 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.
Trang 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
Trang 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”.
Trang 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.
Trang 11
Search We will consider the problem of designing goal-based agents in fully observable, deterministic, discrete, known environments. Start State Goal State
Trang 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.
Trang 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.
Trang 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)
Trang 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?
Trang 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.
Trang 17
StateSpace Graph Theory, Kônigsberg Bridges Problem, & Euler Tour .. Riverbank 1 4 River Island 1 1 Island 2 7 Riverbank 2
Trang 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).
Trang 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 ..
Hiển thị 19 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!