Fundamentals of Artificial Intelligence - Uninformed Search Lecture Notes PDF

Fundamentals of Artificial Intelligence – Uninformed Search Matthias Althoff TU München Winter semester 2024/25 Matthias Althoff Uninformed Search Winter semester 2024/25 1 / 116 Organizat...

Fundamentals of Artificial Intelligence – Uninformed Search Matthias Althoff TU München Winter semester 2024/25 Matthias Althoff Uninformed Search Winter semester 2024/25 1 / 116 Organization 1 Formulating Problems 2 Example Problems 3 Search Algorithms 4 Uninformed Search Strategies Breadth-First Search Uniform-Cost Search (aka Dijkstra’s algorithm) Best-First Search Depth-First Search Depth-Limited Search Iterative Deepening Search Bidirectional Search 5 Comparison and Summary The content is covered in the AI book by the section “Solving Problems by Searching”, Sec. 1-4. Matthias Althoff Uninformed Search Winter semester 2024/25 2 / 116 Learning Outcomes You can create formally defined search problems. You understand the complexity of search problems. You understand how real world problems can often be posed as a pure search problem. You understand the difference between tree-like search and graph search. You can apply the most important uninformed search techniques: Breadth-First Search, Uniform-Cost Search, Depth-First Search, Depth-Limited Search, Iterative Deepening Search. You understand why Best-First Search generalizes the above search techniques. You can compare the advantages and disadvantages of uninformed search strategies. Matthias Althoff Uninformed Search Winter semester 2024/25 3 / 116 Motivation One example how search is used in my research group: Automated vehicles have to search a collision-free path from a start to a goal configuration. Searching in continuous space is difficult. We discretize the search problem in space and time by offering only a finite number of possible actions at discrete time steps. This makes it possible to use classical search techniques as introduced in this lecture. start goal configuration configuration Matthias Althoff Uninformed Search Winter semester 2024/25 4 / 116 Introducing CommonRoad Composable Benchmark CommonRoad Website Scenario Vehicle Cost Ranking Model Function 1. Evaluation Vehicle Parameters J(x,u) Motion Planner Solution Website: https://commonroad.in.tum.de Matthias Althoff Uninformed Search Winter semester 2024/25 5 / 116  Formulating Problems Another Example: Holiday in Romania On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest. Oradea 71 Neamt Zerind 87 75 151 Iasi Arad 140 92 Sibiu Fagaras 99 118 Vaslui 80 Timisoara Rimnicu Vilcea 142 111 Pitesti 211 Lugoj 97 70 98 146 85 Hirsova Mehadia 101 Urziceni 75 138 86 Bucharest Dobreta 120 90 Craiova Eforie Giurgiu Matthias Althoff Uninformed Search Winter semester 2024/25 6 / 116  Formulating Problems Well-Defined Search Problems A search problem can be formally defined as follows: Component Example State Space: set of possible states {Arad, Zerind,...} Initial State: where the agent starts in Arad Actions Actions(s): possible actions Actions(Arad)={ToSibiu, that are applicable in a state s ToTimisoara, ToZerind} Transition Model Result(s, a): re- Result(Arad, ToZerind) turns result of action a in state s = Zerind Goal Test Is-Goal(s): checks whether Is-Goal(Pitesti)=false, s is a goal state Is-Goal(Bucharest)=true Action Cost (s, a, s'): cost of ap- c(Arad, ToZerind, plying action a in state s to reach s’ Zerind) = 75 Matthias Althoff Uninformed Search Winter semester 2024/25 7 / 116  Example Problems Vacuum-Cleaner World A B Percepts: location and contents, e.g., [A, Dirty ] Actions: Left, Right, Suck, NoOp (No Operation) Matthias Althoff Uninformed Search Winter semester 2024/25 8 / 116  Example Problems Vacuum World (Toy Problem I) 1 2 3 4 5 6 7 8 States: Combination of cleaner and dirt locations: 2 · 22 = 8 states. Initial state: any state. Actions: Left, Right, and Suck. Transition model: see next slide. Goal test: checks whether all locations are clean. Action cost: Each step costs 1. Matthias Althoff Uninformed Search Winter semester 2024/25 9 / 116  Example Problems Vacuum World: Transition Model R L R L S S R R L R L R L L S S S S R L R L S S The transition model can be stored as a directed graph, just like the Holiday-in-Romania-Problem. This is possible for all discrete problems. Matthias Althoff Uninformed Search Winter semester 2024/25 10 / 116  Example Problems 8-Puzzle (Toy Problem II) 7 2 4 5 1 2 3 5 6 4 5 6 8 3 1 7 8 Start State Goal State Tiles can move to the blank space. How to reach the goal state? States: Specify the location of each tile and the blank space: 9!/2 = 181440 states (only half of possible initial states can be moved to the goal state; see Moodle attachment). Initial state: Any state. Actions: Movement of the blank space: Left, Right, Up, and Down. Transition model: Huge, but trivial e.g., if Left applied to start state: ’5’ and ’blank’ are switched. Goal test: Checks whether the goal configuration is reached. Action cost: Each step costs 1. Matthias Althoff Uninformed Search Winter semester 2024/25 11 / 116  Example Problems 8-Queens Problem (Toy Problem III) Place 8 queens on a chessboard such that no queens attack each other (A queen attacks any piece in the same row, column or diagonal). Is the above figure a feasible solution? Two formulations: Incremental formulation: Start with an empty chessboard and add a queen at a time. Complete-state formulation: Start with 8 queens and move them. Matthias Althoff Uninformed Search Winter semester 2024/25 12 / 116  Example Problems 8-Queens Problem Description We try the following incremental formulation: States: Any arrangement of 0 − 8 queens: 64 · 63 ·... · 57 ≈ 1.8 · 1014 states. 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 on the board, none attacked. Action cost: Does not apply. Improvement to reduce complexity: Do not place a queen on a square that is already attacked. States*: Any arrangement of 0-8 queens with no queens attacking each other in the n leftmost columns (now only 2057 states). Actions*: Add a queen to any empty square in the leftmost empty column such that it is not attacked by any other queen. Matthias Althoff Uninformed Search Winter semester 2024/25 13 / 116  Example Problems Examples of Real-World Problems Not relevant for the exam Route-Finding problem: Airline travel planning, video streams in computer networks, etc. Touring problem: How to best visit a number of places, e.g., in the map of Romania? Layout of digital circuits: How to best place components and their connections on a circuit board? Robot navigation: Similar to the route-finding problem, but in a continuous space. Automatic assembly sequencing: In which order should a product be assembled? Protein design: What sequence of amino acids will fold into a three-dimensional protein? Matthias Althoff Uninformed Search Winter semester 2024/25 14 / 116  Search Algorithms Generating a Search Tree (1) We are searching for an action sequence to a goal state. The possible actions from the initial state form the search tree: Root: Initial state. Branches: Actions. Nodes: Reached states. Leaves: Unexpanded nodes. We call the set of leaves the frontier. A search tree is expanded by applying actions to leaves. Example: Arad Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Matthias Althoff Uninformed Search Winter semester 2024/25 15 / 116  Search Algorithms Generating a Search Tree (2) We are searching for an action sequence to a goal state. The possible actions from the initial state form the search tree: Root: Initial state. Branches: Actions. Nodes: Reached states. Leaves: Unexpanded nodes. We call the set of leaves the frontier. A search tree is expanded by applying actions to leaves. Example: Arad Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Matthias Althoff Uninformed Search Winter semester 2024/25 16 / 116  Search Algorithms Generating a Search Tree (3) We are searching for an action sequence to a goal state. The possible actions from the initial state form the search tree: Root: Initial state. Branches: Actions. Nodes: Reached states. Leaves: Unexpanded nodes. We call the set of leaves the frontier. A search tree is expanded by applying actions to leaves. Example: Arad Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Matthias Althoff Uninformed Search Winter semester 2024/25 17 / 116  Search Algorithms Tree-Like Search Algorithm The basic principle of expanding leaves until a goal is found can be implemented by the subsequent pseudo code. function Tree-Like-Search (problem) returns a solution or failure initialize the frontier using the initial state of problem loop do if the frontier is empty then return failure choose a leaf node and remove it from the frontier if the node contains a goal state then return the corresponding solution expand the chosen node, adding the resulting nodes to the frontier Matthias Althoff Uninformed Search Winter semester 2024/25 18 / 116  Search Algorithms Tweedback Questions Does tree-like search always find a solution if one exists? Is the search tree of a finite graph also finite? Matthias Althoff Uninformed Search Winter semester 2024/25 19 / 116  Search Algorithms Avoiding Cycles in the Search Tree Problem: In the previous example, we went back to Arad from Sibiu: Expanding from Arad only contains repetitions of previous possibilities. Arad Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Solution: Only expand nodes that have not been visited before. Reached states are stored in a reached set. This idea is referred to as graph search (see next slide). Matthias Althoff Uninformed Search Winter semester 2024/25 20 / 116  Search Algorithms Graph Search Algorithm Differences to the tree search are highlighted in orange. function Graph-Search (problem) returns a solution or failure initialize the frontier using the initial state of problem initialize the reached set to be empty loop do if the frontier is empty then return failure choose a leaf node and remove it from the frontier if the node contains a goal state then return the corresponding solution expand the chosen node, adding the resulting nodes to the frontier and the reached set, but only if not yet in the reached set on an equal or better path Matthias Althoff Uninformed Search Winter semester 2024/25 21 / 116  Search Algorithms Graph Search Algorithm: Illustrations A sequence of search trees generated by graph search. The northernmost city has become a dead end; this would not have happened with tree-like search. (a) (b) (c) The frontier (white nodes) separates the reached nodes (black nodes) from the unreached nodes (gray nodes). Nodes are not expanded to previously visited ones. Matthias Althoff Uninformed Search Winter semester 2024/25 22 / 116  Search Algorithms Tweedback Questions Is it possible that graph search is slower than tree-like search? What is the maximum number of steps required in graph search (according to slide 21)? A The shortest number of edges from the initial state to the goal state. B The number of edges of the graph. C The number of nodes of the graph minus one. You have to assemble parts and each part exists only once. What search technique would you use? A Tree-like search. B Graph search. Matthias Althoff Uninformed Search Winter semester 2024/25 23 / 116  Search Algorithms Graph Search is Not Always Required Example: What is the best assembly of a modular robot to fulfill a task? Graph search would only require more memory without adding any benefit. Matthias Althoff Uninformed Search Winter semester 2024/25 24 / 116  Search Algorithms Measuring Problem-Solving Performance We can evaluate the performance of a search algorithm using the following criteria: Completeness: Is it guaranteed that the algorithm finds a solution if one exists? Optimality: Does the strategy find the optimal solution (minimum costs)? Time complexity: How long does it take to find a solution? Space complexity: How much memory is needed to perform the search? Matthias Althoff Uninformed Search Winter semester 2024/25 25 / 116  Search Algorithms Infrastructure for Search Algorithms Structure of a node n n.STATE: The state in the state space to which the node corresponds; n.PARENT: The node in the search tree that generated this node; n.ACTION: The action that was applied to the parent to generate the node; n.PATH-COST: The cost, traditionally denoted by g (n), of the path from the initial state to the node. Operations on a queue (required for the frontier) Empty(queue): Returns true if queue is empty; Pop(queue): Removes the first element of the queue and returns it; Add(node, queue): Inserts a node and returns the resulting queue. Matthias Althoff Uninformed Search Winter semester 2024/25 26 / 116  Search Algorithms Obtaining the Solution 1 Obtain solution (i.e, state and action sequence) by iterating backwards over parents. 2 Apply actions forward to reach the goal. solution generation initial node goal node n.STATE = A n.STATE =... n.STATE = C n.STATE = G n.PARENT = ∅ n.PARENT = A n.PARENT =... n.PARENT = C n.ACTION = ∅ n.ACTION = γ n.ACTION =... n.ACTION = µ application State sequence: A,... , C, G. Action sequence: γ,... , µ. Matthias Althoff Uninformed Search Winter semester 2024/25 27 / 116  Uninformed Search Strategies Uninformed Search vs. Informed Search Uninformed search No additional information besides the problem statement (states, initial state, actions, transition model, goal test, action cost) is provided. Uninformed search can only produce next states and check whether it is a goal state. Informed search Strategies know whether a state is more promising than another to reach a goal. Informed search uses measures to indicate the distance to a goal. Matthias Althoff Uninformed Search Winter semester 2024/25 28 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Idea (1) Special instance of the graph-search algorithm (slide 21): All nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded: A B C D E F G Matthias Althoff Uninformed Search Winter semester 2024/25 29 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Idea (2) Special instance of the graph-search algorithm (slide 21): All nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded: A B C D E F G Matthias Althoff Uninformed Search Winter semester 2024/25 30 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Idea (3) Special instance of the graph-search algorithm (slide 21): All nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded: A B C D E F G Matthias Althoff Uninformed Search Winter semester 2024/25 31 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Idea (4) Special instance of the graph-search algorithm (slide 21): All nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded: A B C D E F G This will be realized by a FIFO queue (first-in-first-out) for the frontier: by first popping the first-added nodes, nodes are expanded level-by-level. Matthias Althoff Uninformed Search Winter semester 2024/25 32 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm ( UninformedSearch.ipynb) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) Matthias Althoff Uninformed Search Winter semester 2024/25 33 / 116  Uninformed Search Strategies Breadth-First Search Auxiliary Algorithm: Expand function Expand (problem, node) yields nodes s ← node.State for each action in problem.Actions(s) do s ′ ← problem.Result(s, action) cost ← node.Path-Cost + problem.Action-Cost(s, action, s ′ ) yield Node(State=s ′, Parent=node, Action=action, Path-Cost=cost) Matthias Althoff Uninformed Search Winter semester 2024/25 34 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 1a) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal: F B C node: A frontier: A D E F G reached: A Matthias Althoff Uninformed Search Winter semester 2024/25 35 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 1b) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal: F B C node: A frontier: ∅ D E F G reached: A Matthias Althoff Uninformed Search Winter semester 2024/25 36 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 1c) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal: F B C node: A frontier: B D E F G reached: A, B Matthias Althoff Uninformed Search Winter semester 2024/25 37 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 1d) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal: F B C node: A frontier: B, C D E F G reached: A, B, C Matthias Althoff Uninformed Search Winter semester 2024/25 38 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 2a) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal: F B C node: B frontier: C D E F G reached: A, B, C Matthias Althoff Uninformed Search Winter semester 2024/25 39 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 2b) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal: F B C node: B frontier: C, D D E F G reached: A, B, C, D Matthias Althoff Uninformed Search Winter semester 2024/25 40 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 2c) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal: F B C node: B frontier: C, D, E D E F G reached: A, B, C, D, E Matthias Althoff Uninformed Search Winter semester 2024/25 41 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 3a) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal: F B C node: C frontier: D, E D E F G reached: A, B, C, D, E Matthias Althoff Uninformed Search Winter semester 2024/25 42 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Algorithm (Step 3b) function Breadth-First-Search (problem) returns a solution or failure node ← Node(State=problem.Initial-State, Path-Cost=0) if problem.Is-Goal(node.State) then return Solution(node) frontier ← a FIFO queue with node as the only element reached ← {node.State} loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do s ← child.State if problem.Is-Goal(s) then return Solution(child) if s is not in reached then add s to reached frontier ← Add(child,frontier) A goal state F found! B C node: C frontier: D, E D E F G reached: A, B, C, D, E Matthias Althoff Uninformed Search Winter semester 2024/25 43 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Performance We introduce the branching factor b (maximum number of successors of any node), the depth d (depth of the shallowest goal node, where root is at depth 0), the maximum length m of any path in the state space, and use the previously introduced criteria: Completeness: Yes, if depth d and branching factor b are finite. Optimality: Yes, if cost is equal per step; not optimal in general. Time complexity: The worst case is that each node has b successors. The number of explored nodes sums up to b + b 2 + b 3 + · · · + b d = O(b d ) Space complexity: All explored nodes are O(b d−1 ) and all nodes in the frontier are O(b d ) Matthias Althoff Uninformed Search Winter semester 2024/25 44 / 116  Uninformed Search Strategies Breadth-First Search Landau Notation aka Big O Notation (for students from other disciplines) Describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Shall f (x) be the actual function for parameter x, then there exist positive constants M, x0 , such that |f (x)| ≤ M|g (x)| for all x > x0. Here, f (b) = b + b 2 + b 3 + · · · + b d and g (b) = b d. Possible combinations of M, b0 for d = 5 are: M = 2, b0 = 2, M = 1.5, b0 = 3, M = 1.35, b0 = 4. Since M, b0 only have to exist and their concrete values do not matter, we just write O(b d ). Matthias Althoff Uninformed Search Winter semester 2024/25 45 / 116  Uninformed Search Strategies Breadth-First Search Tweedback Question Assume: branching factor is b = 10 Up to what depth is a breadth-first-search problem solvable on your laptop? A d =8 B d = 16 C d = 32 Matthias Althoff Uninformed Search Winter semester 2024/25 46 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: Complexity Issue An exponential complexity, such as O(b d ), is a big problem. The following table lists example time and memory requirements for a branching factor of b = 10 on a modern computer: Depth Nodes Time Memory 2 110 0.11 ms 107 kilobytes 4 11, 110 11 ms 10.6 megabytes 6 106 1.1 s 1 gigabyte 8 108 2 min 103 gigabytes 10 1010 3h 10 terabytes 12 1012 13 days 1 petabyte 14 1014 3.5 years 99 petabytes 16 1016 350 years 10 exabytes Matthias Althoff Uninformed Search Winter semester 2024/25 47 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: CommonRoad Example Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 48 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: CommonRoad Example Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 48 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: CommonRoad Example Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 48 / 116  Uninformed Search Strategies Breadth-First Search Breadth-First Search: CommonRoad Example Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 48 / 116  Uninformed Search Strategies Uniform-Cost Search (aka Dijkstra’s algorithm) Uniform-Cost Search (aka Dijkstra’s algorithm): Idea (1) When all step costs are equal, breadth-first is optimal because it always expands the shallowest nodes. Uniform-cost search is optimal for any step costs, as it expands the node with the lowest path cost g (n) = n.Path-Cost. This is realized by storing the frontier as a priority queue ordered by g. S Sibiu (S) 99 Fagaras (F) 80 R F Rimnicu Vilcea (R) Pitesti (P) 211 97 P B 101 B Bucharest (B) Matthias Althoff Uninformed Search Winter semester 2024/25 49 / 116  Uninformed Search Strategies Uniform-Cost Search (aka Dijkstra’s algorithm) Uniform-Cost Search (aka Dijkstra’s algorithm): Idea (2) When all step costs are equal, breadth-first is optimal because it always expands the shallowest nodes. Uniform-cost search is optimal for any step costs, as it expands the node with the lowest path cost g (n) = n.Path-Cost. This is realized by storing the frontier as a priority queue ordered by g. S Sibiu (S) 99 Fagaras (F) 80 R 80 F 99 Rimnicu Vilcea (R) Pitesti (P) 211 97 P B 101 B Bucharest (B) Matthias Althoff Uninformed Search Winter semester 2024/25 50 / 116  Uninformed Search Strategies Uniform-Cost Search (aka Dijkstra’s algorithm) Uniform-Cost Search (aka Dijkstra’s algorithm): Idea (3) When all step costs are equal, breadth-first is optimal because it always expands the shallowest nodes. Uniform-cost search is optimal for any step costs, as it expands the node with the lowest path cost g (n) = n.Path-Cost. This is realized by storing the frontier as a priority queue ordered by g. S Sibiu (S) 99 Fagaras (F) 80 Rimnicu Vilcea (R) R 80 F 99 Pitesti (P) 211 97 P 80+97 B =177 101 B Bucharest (B) Matthias Althoff Uninformed Search Winter semester 2024/25 51 / 116  Uninformed Search Strategies Uniform-Cost Search (aka Dijkstra’s algorithm) Uniform-Cost Search (aka Dijkstra’s algorithm): Idea (4) When all step costs are equal, breadth-first is optimal because it always expands the shallowest nodes. Uniform-cost search is optimal for any step costs, as it expands the node with the lowest path cost g (n) = n.Path-Cost. This is realized by storing the frontier as a priority queue ordered by g. S Sibiu (S) 99 Fagaras (F) 80 R 80 F 99 Rimnicu Vilcea (R) Pitesti (P) 211 99+211 97 P 177 B =310 101 B Bucharest (B) Matthias Althoff Uninformed Search Winter semester 2024/25 52 / 116  Uninformed Search Strategies Uniform-Cost Search (aka Dijkstra’s algorithm) Uniform-Cost Search (aka Dijkstra’s algorithm): Idea (5) When all step costs are equal, breadth-first is optimal because it always expands the shallowest nodes. Uniform-cost search is optimal for any step costs, as it expands the node with the lowest path cost g (n) = n.Path-Cost. This is realized by storing the frontier as a priority queue ordered by g. S Sibiu (S) 99 Fagaras (F) 80 Rimnicu Vilcea (R) R 80 F 99 Pitesti (P) 211 97 P 177 B 310 101 177+101 B Bucharest (B) =278 Matthias Althoff Uninformed Search Winter semester 2024/25 53 / 116  Uninformed Search Strategies Best-First Search Best-First Search: A generalization of Uniform-Cost Search Uniform-Cost Search is a special form of a more general search approach: Best-First Search. It uses a priority queue for the frontier, which is ordered by some parametrized evaluation function f (n): always the node with the minimum value of f (n) is expanded first. → different functions f result in different algorithms. → Uniform-Cost Search is Best-First Search with f (n) = g (n). Matthias Althoff Uninformed Search Winter semester 2024/25 54 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Changes to Breadth-First Search Goal test is applied to a node when it is selected for expansion rather than when it is first generated. Reason: the first generated goal node might be on a suboptimal path. A test is added in case a better path to an already reached state is found. Realization: subsequent operations on the lookup table reached. Operations on the lookup table reached s in reached: returns true if reached contains the state s. reached[s]: returns the node for state s in reached; due to the internal structure of lookup tables, this can be done in constant timea. reached[s] ← n: sets the value of state s to the node n. a https://www.geeksforgeeks.org/introduction-to-hashing-data-structure-and-algorithm-tutorials/ Matthias Althoff Uninformed Search Winter semester 2024/25 55 / 116  Uninformed Search Strategies Best-First Search Best-First: Algorithm ( UninformedSearch.ipynb) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Insert(child,frontier) By removing the lines in orange we obtain a tree-like search. Matthias Althoff Uninformed Search Winter semester 2024/25 56 / 116  Uninformed Search Strategies Best-First Search Tweedback Question Can Breadth-First Search be implemented using Best-First Search? Matthias Althoff Uninformed Search Winter semester 2024/25 57 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 1a) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: A(0) (path cost in parentheses) 1 4 5 2 frontier: A(0) D E F G reached: A Matthias Althoff Uninformed Search Winter semester 2024/25 58 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 1b) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: A(0) 1 4 5 2 frontier: ∅ D E F G reached: A Matthias Althoff Uninformed Search Winter semester 2024/25 59 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 1c) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: A(0) 1 4 5 2 frontier: B(2) D E F G reached: A, B Matthias Althoff Uninformed Search Winter semester 2024/25 60 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 1d) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: A(0) 1 4 5 2 frontier: B(2), C(3) D E F G reached: A, B, C Matthias Althoff Uninformed Search Winter semester 2024/25 61 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 2a) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: B(2) 1 4 5 2 frontier: C(3) D E F G reached: A, B, C Matthias Althoff Uninformed Search Winter semester 2024/25 62 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 2b) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: B(2) 1 4 5 2 frontier: C(3), D(3) D E F G reached: A, B, C, D Matthias Althoff Uninformed Search Winter semester 2024/25 63 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 2c) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: B(2) 1 4 5 2 frontier: C(3), D(3), E(6) D E F G reached: A, B, C, D, E Matthias Althoff Uninformed Search Winter semester 2024/25 64 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 3a) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: C(3) 1 4 5 2 frontier: D(3), E(6) D E F G reached: A, B, C, D, E Matthias Althoff Uninformed Search Winter semester 2024/25 65 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 3b) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: C(3) 1 4 5 2 frontier: D(3), E(6), F(8) D E F G reached: A, B, C, D, E, F Matthias Althoff Uninformed Search Winter semester 2024/25 66 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 3c) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: C(3) 1 4 5 2 frontier: D(3), G(5), E(6), F(8) D E F G reached: A, B, C, D, E, F, G Matthias Althoff Uninformed Search Winter semester 2024/25 67 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 4) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: D(3) 1 4 5 2 frontier: G(5), E(6), F(8) D E F G reached: A, B, C, D, E, F, G Matthias Althoff Uninformed Search Winter semester 2024/25 68 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 5a) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal: G B C node: G(5) 1 4 5 2 frontier: E(6), F(8) D E F G reached: A, B, C, D, E, F, G Matthias Althoff Uninformed Search Winter semester 2024/25 69 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Algorithm for f (n) = g (n) (Step 5b) function Best-First-Search (problem, f ) returns a solution or failure node ← Node(State=problem.Initial-State,Path-Cost=0) frontier ← a priority queue ordered by f , with node as the only element reached ← a lookup table, with one entry (node.State → node) loop do if Is-Empty(frontier) then return failure node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node) for each child in Expand(problem,node) do s ← child.State if s is not in reached or child.Path-Cost < reached[s].Path-Cost then reached[s] ← child frontier ← Add(child,frontier) 2 A 3 goal state G found! B C node: G(5) 1 4 5 2 frontier: E(6), F(8) D E F G reached: A, B, C, D, E, F, G Matthias Althoff Uninformed Search Winter semester 2024/25 70 / 116  Uninformed Search Strategies Best-First Search Best-First Search: Performance for f (n) = g (n) We introduce the cost C∗ of the optimal solution, the minimum step-cost ǫ, and use the previously introduced criteria: Completeness: Yes, if costs are greater than 0 (otherwise infinite optimal paths of zero cost exist). Optimality: Yes (if cost ≥ ǫ for positive ǫ). Time complexity: The worst case is that the goal branches of a node with huge costs and all other step costs are ǫ. The number of explored nodes (for e.g. d = 1) sums up to (b − 1) + (b − 1)b + (b − 1)b 2 + · · · + (b − 1)b ⌊C ∗ /ǫ⌋ = O(b 1+⌊C ∗ /ǫ⌋ ), where ⌊a⌋ returns the next lower integer of a. Space complexity: Equals time complexity since all nodes are stored. Matthias Althoff Uninformed Search Winter semester 2024/25 71 / 116  Uninformed Search Strategies Best-First Search Best-First Search: CommonRoad Example for f (n) = g (n) Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). g (n): Time to reach current state. Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 72 / 116  Uninformed Search Strategies Best-First Search Best-First Search: CommonRoad Example for f (n) = g (n) Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). g (n): Time to reach current state. Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 72 / 116  Uninformed Search Strategies Best-First Search Best-First Search: CommonRoad Example for f (n) = g (n) Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). g (n): Time to reach current state. Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 72 / 116  Uninformed Search Strategies Best-First Search Best-First Search: CommonRoad Example for f (n) = g (n) Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). g (n): Time to reach current state. Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 72 / 116  Uninformed Search Strategies Best-First Search Best-First Search: CommonRoad Example for f (n) = g (n) Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). g (n): Time to reach current state. Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 72 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Idea (1) We always expand the deepest node in the frontier: A B C D E F G H I J K L M N O Matthias Althoff Uninformed Search Winter semester 2024/25 73 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Idea (2) We always expand the deepest node in the frontier: Matthias Althoff Uninformed Search Winter semester 2024/25 74 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Idea (3) We always expand the deepest node in the frontier: Matthias Althoff Uninformed Search Winter semester 2024/25 75 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Idea (4) We always expand the deepest node in the frontier: Matthias Althoff Uninformed Search Winter semester 2024/25 76 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Idea (5) We always expand the deepest node in the frontier: Matthias Althoff Uninformed Search Winter semester 2024/25 77 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Idea (6) We always expand the deepest node in the frontier: Matthias Althoff Uninformed Search Winter semester 2024/25 78 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Idea (7) We always expand the deepest node in the frontier: Matthias Althoff Uninformed Search Winter semester 2024/25 79 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Idea (8) We always expand the deepest node in the frontier: Matthias Althoff Uninformed Search Winter semester 2024/25 80 / 116  Uninformed Search Strategies Depth-First Search Tweedback Question Can Depth-First Search be implemented using Best-First Search? Solution: Best-First Search with f (n) = −n.Depth. But: usually implemented as a tree-like search (for pseudo-code, please see Depth-Limited Search on slide 86 with limit=∞). Matthias Althoff Uninformed Search Winter semester 2024/25 81 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: Performance Reminder: Branching factor b, depth d, maximum length m of any path. Completeness: No. But: for finite state spaces, completeness can be achieved by checking for cycles. Optimality: No. Why? Time complexity: The worst case is that the goal path is tested last, resulting in O(b m ). Reminder: Breadth-first has O(b d ) and d ≤ m. Space complexity: The advantage of depth-first search is a good space complexity: One only needs to store a single path from the root to the leaf plus unexplored sibling nodes (see next slide). There are at most m nodes to a leaf and b nodes branching off from each node, resulting in O(bm) nodes. Matthias Althoff Uninformed Search Winter semester 2024/25 82 / 116  Uninformed Search Strategies Depth-First Search Space Requirement for Depth-First Search Example: b = 10, d = m = 16: breadth-first: 10 exabytes depth-first: 156 kilobytes better by a factor of ≈ 7 · 1013 Matthias Althoff Uninformed Search Winter semester 2024/25 83 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: CommonRoad Example Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 84 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: CommonRoad Example Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 84 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: CommonRoad Example Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 84 / 116  Uninformed Search Strategies Depth-First Search Depth-First Search: CommonRoad Example Frontier Collision (Currently) Explored Concatenation of motion primitives. Note: Colliding states are not further considered (collision with obstacle or out of road boundary). Link to tutorial: cr uninformed search tutorial.ipynb. Matthias Althoff Uninformed Search Winter semester 2024/25 84 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Idea Shortcoming in depth-first search: Depth-first search does not terminate in infinite state spaces. Why? Solution: Introduce depth limit l. New issue: How to choose the depth-limit? Realization: LIFO queue (last-in-first-out, also known as stack) for the frontier: it first pops the most recently added node. Matthias Althoff Uninformed Search Winter semester 2024/25 85 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm ( UninformedSearch.ipynb) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff // check limit after popping node else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result Here: the function Is-Cycle(node) iterates the chain of Parent-pointers upwards to check whether the state node.State already exists in a previous node. The maximum number of iterated Parent-pointers is generally user-defined. Matthias Althoff Uninformed Search Winter semester 2024/25 86 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 1) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: - E F frontier: A D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 87 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 2a) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: A E F frontier: ∅ D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 88 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 2b) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A.Depth=0 A limit: 1 B C node: A E F frontier: ∅ D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 89 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 2c) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: A E F frontier: B D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 90 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 2d) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: A E F frontier: B, C D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 91 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 3a) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: C E F frontier: B D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 92 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 3b) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D C.Depth=1 A limit: 1 B C node: C E F frontier: B D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 93 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 3c) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: C E F frontier: B, E D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 94 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 3d) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: C E F frontier: B, E, F D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 95 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 4a) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: F E F frontier: B, E D result: failure G H Matthias Althoff Uninformed Search Winter semester 2024/25 96 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 4b) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D F.Depth=2 A limit: 1 B C node: F E F frontier: B, E D result: cutoff G H Matthias Althoff Uninformed Search Winter semester 2024/25 97 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 5a) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D A limit: 1 B C node: E E F frontier: B D result: cutoff G H Matthias Althoff Uninformed Search Winter semester 2024/25 98 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 5b) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result goal: D E.Depth=2 A limit: 1 B C node: E E F frontier: B D result: cutoff G H Matthias Althoff Uninformed Search Winter semester 2024/25 99 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 6a) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result A goal: D limit: 1 B C node: B D E F frontier: ∅ result: cutoff G H Matthias Althoff Uninformed Search Winter semester 2024/25 100 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 6b) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result A goal: D B.Depth=1 limit: 1 B C node: B D E F frontier: ∅ result: cutoff G H Matthias Althoff Uninformed Search Winter semester 2024/25 101 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 6c) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result A goal: D limit: 1 B C node: B D E F frontier: D result: cutoff G H Matthias Althoff Uninformed Search Winter semester 2024/25 102 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 7a) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result A goal: D limit: 1 B C node: D D E F frontier: ∅ result: cutoff G H Matthias Althoff Uninformed Search Winter semester 2024/25 103 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Algorithm (Step 7b) function Depth-Limited-S. (problem,limit) returns a solution or failure/cutoff frontier ← a LIFO queue (stack) with Node(problem.Initial-State) as the only element result ← failure while not Is-Empty(frontier) do node ← Pop(frontier) if problem.Is-Goal(node.State) then return Solution(node) if node.Depth > limit then result ← cutoff else if not Is-Cycle(node) then for each child in Expand(problem,node) do frontier ← Add(child,frontier) return result A goal state D found! limit: 1 B C node: D D E F frontier: ∅ result: cutoff G H Matthias Althoff Uninformed Search Winter semester 2024/25 104 / 116  Uninformed Search Strategies Depth-Limited Search Depth-Limited Search: Performance Reminder: Branching factor b, depth d, maximum length m of any path, and depth limit l. Completeness: No, if l < d. Why? Optimality: No, if l > d. Why? Time complexity: Same as for depth-first search, but with l instead of m: O(b l ). Space complexity: Same as for depth-first search, but with l instead of m: O(bl ). Matthias Althoff Uninformed Search Winter semester 2024/25 105 / 116  Uninformed Search Strategi