Artificial Intelligence CSB2104 Lecture Notes PDF

Artificial Intelligence CSB2104 Prof. Abdel-Rahman Hedar Solving Problems by Searching Chapter 3 – Part I 2  Contents » Introduction to Problem Solving » Complexity » Uninformed search Problem formulation Search strategies: depth-first, breadth-first » Informed search...

Artificial Intelligence CSB2104 Prof. Abdel-Rahman Hedar Solving Problems by Searching Chapter 3 – Part I 2  Contents » Introduction to Problem Solving » Complexity » Uninformed search Problem formulation Search strategies: depth-first, breadth-first » Informed search Search strategies: best-first, A* Heuristic functions 3 Introduction 4  Example: Measuring Problem! » Problem: Using these three buckets, measure 7 liters of water. 9l 3l 5l Example: Measuring Problem! 9l 3l 5l Which solution do we prefer? Solution 1: Solution 2: a b c a b c 0 0 0 start 0 0 0 start 3 0 0 0 5 0 0 0 3 3 2 0 3 0 3 3 0 2 0 0 6 3 5 2 3 0 6 3 0 7 goal 0 3 6 3 3 6 1 5 6 0 5 7 goal Problem-Solving Agents 8 Problem-Solving Agents Problem solving Goal formulation Problem formulation (states, operators) Search for solution Problem formulation Initial state Operators Goal test Path cost  Problem-Solving » Goal formulation, based on the current situation and the agent’s performance measure, is the first step in problem solving. » Problem formulation is the process of deciding what actions and states to consider, given a goal. » Search for the solution is the process of looking for a sequence of actions that reaches the goal. A search algorithm takes a problem as input and returns a solution in the form of an action sequence.  Problem Formulation » The initial state that the agent starts in. » A description of the possible actions available to the agent. Given a particular state s, ACTIONS(s) returns the set of actions that can be executed in s. We say that each of these actions is applicable in s. » Transition model is a description of what each action does specified by a function RESULT(s, a) that returns the state that results from doing action a in state s. We also use the term successor to refer to any state reachable from a given state by a single action.  Problem Formulation » A path in the state space is a sequence of states connected by a sequence of actions. » The goal test, which determines whether a given state is a goal s » A path cost is a function that assigns a numeric cost to each path. » The step cost of taking action a in state s to reach state s is denoted by c(s, a, s). Examples of Search Problems 13  Example 1: Buckets » Measure 7 liters of water using a 3-liter, a 5-liter, and a 9-liter buckets. » Formulate goal: Have 7 liters of water in 9-liter bucket » Formulate problem: States: amount of water in the buckets Operators: Fill bucket from source, empty bucket » Find solution: sequence of operators that bring you from current state to the goal state 14  Example 2: Vacuum World » Simplified world: 2 locations, each may or not contain dirt, each may or not contain vacuuming agent. » Goal of agent: clean up the dirt. States: Integer Dirt, Robot Location Actions: L, R, S, Off Goal Test: No dirt Path Cost: 1 for (L, R, S), 0 for (Off) 15  Example 3: 8-Queens Problem » The goal of the 8-queens problem is to place eight queens on a chessboard such that no queen attacks any other. A queen attacks any piece in the same row, column or diagonal. » An incremental formulation involves operators that augment the state description, starting with an empty state; for the 8-queens problem, this means that each action adds a queen to the state. » A complete-state formulation starts with all 8 queens on the board and moves them around. Example 3: 8-Queens Problem  Example 3: 8-Queens Problem » States: Any arrangement of 0 to 8 queens on the board is a state. » Initial state: No queens on the board. » Actions: Add a queen to any empty square. » Transition model: Returns the board with a queen added to the specified square. » Goal test: 8 queens are on the board, none attacked. In this formulation, we have 64×63×…×57 ≈ 1.8×1014 possible sequences to investigate.  Example 4: Romania »In Romania, on vacation. Currently in Arad. »Flight leaves tomorrow from Bucharest. »Formulate goal be in Bucharest »Formulate problem: states: various cities operators: drive between cities »Find solution: sequence of cities, such that total driving distance is minimized. 19 Example 4: Romania 20  Example 5: 8-Puzzle » State: integer location of tiles (ignore intermediate locations) » Operators: moving blank left, right, up, down (ignore jamming) » Goal test: does state match goal state? » Path cost: 1 per move 21  Example 5: 8-Puzzle » Why search algorithms? 8-puzzle has 9!/2 = 181, 440 states 15-puzzle has 16!/2 ≈ 10^12 states 24-puzzle has 25!/2 ≈ 10^25 states Note: we have two possible solutions, the blank block in the first or in the last. » So, we need a principled way to look for a solution in these huge search spaces. 22 Search Algorithms 23  Search Algorithms » Basic idea: Offline, systematic exploration of simulated state-space by generating successors of explored states (expanding) 24 Search Algorithms: Examples 25  Infrastructure for Search Algorithms » The appropriate data structure for this is a queue. The operations on a queue are as follows: EMPTY?(queue) returns true only if there are no more elements in the queue. POP(queue) removes the first element of the queue and returns it. INSERT(element, queue) inserts an element and returns the resulting queue. 26  Infrastructure for Search Algorithms » Three common variants of queues are: the first-in, first-out or FIFO queue, which pops the oldest element of the queue; the last-in, first-out or LIFO queue (also known as a stack), which pops the newest element of the queue; and the priority queue, which pops the element of the queue with the highest priority according to some ordering function. 27  Search Strategies » A strategy is defined by picking the order of node expansion. » Strategies are evaluated along the following dimensions: Completeness: does it always find a solution if one exists? Time complexity: number of nodes generated/expanded Space complexity: maximum number of nodes in memory Optimality: does it always find a least-cost solution? » Time and space complexity are measured in terms of 𝑏: maximum branching factor of the search tree 𝑑: depth of the least-cost solution 𝑚: maximum depth of the state space (may be ∞) 28  Uninformed Search Strategies » Uninformed strategies use only the information available in the problem definition » Breadth-first search » Uniform-cost search » Depth-first search » Depth-limited search » Iterative deepening search 29 Breadth-First Search 30  Breadth-First Search » Expand shallowest unexpanded node » Implementation: frontier is a FIFO queue 31  Breadth-First Search » Complete: Yes (if 𝑏 is finite). » Time: 1 + 𝑏 + 𝑏 2 + ⋯ + 𝑏 𝑑 = 𝑂 𝑏 𝑑. » Space:𝑂 𝑏 𝑑+1 = 𝑂 𝑏 𝑑. » Optimal: Yes, (if step cost = 1). In general, not optimal. 32  Uniform-Cost Search » Expand least-cost unexpanded node » Implementation: frontier = queue ordered by path cost, lowest first » Equivalent to breadth-first if step costs all equal 33 Best-First Search Algorithm 34 BFS & UCS Algorithms 35 UCS Example 36 Depth-First Search 37  Depth-First Search Expand deepest unexpanded node Implementation:  frontier is a LIFO queue 38  Depth-First Search » Complete: No (Faills in infinite depth sapce or ). » Time: 𝑂 𝑏 𝑚 , terrible if 𝑚 is much greater than 𝑑. » Space:𝑂 𝑏𝑚 , linear space » Optimal: No. 39  Depth-Limited Search & Iterative Deepening Search » Depth-Limited Search = depth-first search with depth limit 𝑙, » i.e., nodes at depth 𝑙 have no successors. » Iterative Deepening Search is successive implementation of Depth-Limited Search with incremental 𝑙. 40 DLS & IDS Algorithms 41 IDS Example 42  Conclusion » Problem formulation usually requires abstracting away real-world details. » Once problem is formulated in abstract form, complexity analysis helps us picking out best algorithm. » Variety of uninformed search strategies; the difference lies in the method used to pick nodes that will be further expanded. » Iterative deepening search only uses linear space and not much more time than other uniformed search strategies. 43 Questions & Comments Abdel-Rahman Hedar [email protected] https://shorturl.at/ntI2x