006 Searching Methods in AI.pptx

APP002-4-2-IAI& Introduction to Artificial Intelligence SEARCH METHODS IN AI Module Code & Module Title Slide Title SLIDE 1  TOPIC LEARNING OUTCOMES...

APP002-4-2-IAI& Introduction to Artificial Intelligence SEARCH METHODS IN AI Module Code & Module Title Slide Title SLIDE 1  TOPIC LEARNING OUTCOMES Atthe end of this topic, you should be able to: 1. Name at least one example of informed search algorithm 2. Name at least one example of uninformed search algorithm 3. Explain the concept of informed search 4. Explain the concept of uninformed search 5. Compare the advantages and disadvantages of the informed search and the uninformed search 6. Apply informed search algorithm in real-life use cases 7. Apply uninformed search algorithm in real-life use cases Module Code & Module Title Slide Title SLIDE 2  CONTENTS & STRUCTURE 1. Uninformed Search 2. Breadth First Search 3. Depth First Search 4. Informed Search 5. Heuristic Search 6. A* Search Module Code & Module Title Slide Title SLIDE 3  Recap From Last Lesson Can an expert system manage without knowledge representation? Image credits: google.com Module Code & Module Title Slide Title SLIDE 4  Why is a search strategy important? Image credits: google.com Module Code & Module Title Slide Title SLIDE 5  Search Algorithms in AI Artificial intelligence is the study of developing agents that act rationally. Most often, these agents run some sort of search algorithm in the background to accomplish their tasks. Image credits: google.com Module Code & Module Title Slide Title SLIDE 6  Search Algorithms in AI Image credits: google.com Module Code & Module Title Slide Title SLIDE 7  Uninformed Search Algorithms Uninformed search algorithms or blind search algorithms are the search algorithms used to find solutions to a problem that does not involve domain knowledge. They are used in artificial intelligence to find relevant solutions by exploring all possibilities of the problem space. Image credits: google.com Module Code & Module Title Slide Title SLIDE 8  Uninformed Search Algorithms…cont. Features of Uninformed Search Algorithms have no prior information about the states or actions associated with the problem domain. systematically explore the problem space until they find a solution or exhaust all possibilities. rely solely on the definition of the problem and some predefined rules. guarantee a solution if a possible solution for this problem exists. easy to implement as they do not require any additional expertise. Module Code & Module Title Slide Title SLIDE 9  Uninformed Search Algorithms Image credits: google.com Module Code & Module Title Slide Title SLIDE 10  Uninformed Search Algorithms…cont. Breadth First Search ( BFS ) is used to explore all neighboring states or nodes of the initial node. BFS goes wide. This means that we traverse a graph level by level. We take a node, traverse all its subordinate nodes and then go to another node. This is because all subordinate nodes of a node are on the same level. Image credits: google.com Module Code & Module Title Slide Title SLIDE 11  Uninformed Search Algorithms…cont. Breadth First Search ( BFS ) is used to explore all neighboring states or nodes of the initial node. BFS goes wide. This means that we traverse a graph level by level. We take a node, traverse all its subordinate nodes and then go to another node. This is because all subordinate nodes of a node are on the same level. Image credits: google.com Module Code & Module Title Slide Title SLIDE 12  Uninformed Search Algorithms…cont. Breadth First Search ( BFS ) Image credits: google.com Module Code & Module Title Slide Title SLIDE 13  Uninformed Search Algorithms…cont. Queue for Level-Wise Search A queue is a linear structure of data that follows the First-In- First-Out (FIFO) principle. The element that enters a queue first is also the first to leave it. Image credits: google.com Module Code & Module Title Slide Title SLIDE 14  Uninformed Search Algorithms…cont. Queue for Level-Wise Search 1. Start with a root node and push (move) it to the queue. 2. Mark the root node as visited and print it 3. Continue a loop until the queue is empty: 3.1. Pop (remove) the front node from the queue 3.2. Push (move) the child nodes/neighboring nodes of the front node into the queue 3.3 Mark them as visited and print Image credits: google.com Module Code & Module Title Slide Title SLIDE 15  Uninformed Search Algorithms…cont. Image credits: google.com Module Code & Module Title Slide Title SLIDE 16  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) traverses the graph and explores each adjacent node before backtracking and moving to the next node. Image credits: google.com Module Code & Module Title Slide Title SLIDE 17  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) Vertex A is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex A. Vertex A is connected to the unvisited nodes B and G. Image credits: google.com Module Code & Module Title Slide Title SLIDE 18  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) Vertex B is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex B. Vertex B is connected to the unvisited nodes C and G. Image credits: google.com Module Code & Module Title Slide Title SLIDE 19  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) Vertex C is also added to the discovery list and is marked as visited. Vertex C is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex C. Vertex C is connected to the unvisited node E. Image credits: google.com Module Code & Module Title Slide Title SLIDE 20  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) Vertex E is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex E. Vertex E is connected to the unvisited nodes G, J, and K. Image credits: google.com Module Code & Module Title Slide Title SLIDE 21  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) The DFS algorithm pushes G onto the stack. Vertex G is also added to the discovery list and is marked as visited. Vertex G is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex G. Vertex G is connected to the unvisited node J. Image credits: google.com Module Code & Module Title Slide Title SLIDE 22  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) The DFS algorithm pushes J onto the stack. Vertex J is also added to the discovery list and is marked as visited. Vertex J is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex J. Vertex J is connected to the unvisited nodes D and F. Image credits: google.com Module Code & Module Title Slide Title SLIDE 23  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) The DFS algorithm pushes D onto the stack. Vertex D is also added to the discovery list and is marked as visited. Vertex D is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex D. Vertex D is connected to the unvisited nodes F and K. Image credits: google.com Module Code & Module Title Slide Title SLIDE 24  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) The DFS algorithm pushes F onto the stack. Vertex F is also added to the discovery list and is marked as visited. Vertex F is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex F. Vertex F is connected to the unvisited node K. Image credits: google.com Module Code & Module Title Slide Title SLIDE 25  Uninformed Search Algorithms…cont. Depth First Search ( DFS ) The DFS algorithm pushes K onto the stack. Vertex K is also added to the discovery list and is marked as visited. Image credits: google.com Module Code & Module Title Slide Title SLIDE 26  Quick Review Question Use the BFS algorithm to find all vertices of the following graph. Image credits: google.com Module Code & Module Title Slide Title SLIDE 27  Quick Review Question Use the BFS algorithm to find all vertices of the following graph. Image credits: google.com Module Code & Module Title Slide Title SLIDE 28  Quick Review Question Use the DFS algorithm to find all vertices of the following graph. Image credits: google.com Module Code & Module Title Slide Title SLIDE 29  Quick Review Question Use the DFS algorithm to find all vertices of the following graph. Image credits: google.com Module Code & Module Title Slide Title SLIDE 30  Informed Search Algorithms Informed search algorithms use domain-specific heuristics to guide the search process efficiently. They prioritize exploring paths or states that are most likely to lead to a solution. A heuristic function helps the search algorithm to select a branch from the available branches. It helps in the decision-making process by using additional knowledge about the search space. Module Code & Module Title Slide Title SLIDE 31  Informed Search Algorithms…cont. Best First Search (BFS) The best first search algorithm is a version of the first depth-first search using heuristics. Each node is evaluated according to its distance to the target. The node closest to the final state is explored first. If the path does not reach the goal, the algorithm goes back and chooses another node that did not previously appear to be the best. Module Code & Module Title Slide Title SLIDE 32  Informed Search Algorithms…cont. Best First Search (BFS) Algorithm 1. Create a priority queue. 2. Insert the starting node. 3. Remove a node from the priority queue. 3.1. Check if it is the goal node. If yes, then exit. 3.2. Otherwise, mark the node as visited and insert its neighbors into the priority queue. The priority of each will be its distance from the goal. Image credits: google.com Module Code & Module Title Slide Title SLIDE 33  Informed Search Algorithms…cont. Best First Search (BFS) Algorithm 1. Create a priority queue. 2. Insert the starting node. Image credits: google.com Module Code & Module Title Slide Title SLIDE 34  Informed Search Algorithms…cont. Best First Search (BFS) Algorithm 1. Create a priority queue. 2. Insert the starting node. 3. Remove a node from the priority queue. Image credits: google.com Module Code & Module Title Slide Title SLIDE 35  Informed Search Algorithms…cont. Best First Search (BFS) Algorithm 1. Create a priority queue. 2. Insert the starting node. 3. Remove a node from the priority queue. 3.1. Check if it is the goal node. If yes, then exit. Image credits: google.com Module Code & Module Title Slide Title SLIDE 36  Informed Search Algorithms…cont. Best First Search (BFS) Algorithm 1. Create a priority queue. 2. Insert the starting node. 3. Remove a node from the priority queue. 3.1. Check if it is the goal node. If yes, then exit. 3.2. Otherwise, mark the node as visited and insert its neighbors into the priority queue. The priority of each will be its distance from the goal. Image credits: google.com Module Code & Module Title Slide Title SLIDE 37  Informed Search Algorithms…cont. A* Search The previous algorithm we discussed only considers the distance of the nodes from the target. A* uses the path from the start node to the current node and the path from the current node to the destination. The heuristic function is therefore: Image credits: google.com Module Code & Module Title Slide Title SLIDE 38  Informed Search Algorithms…cont. A* Search Algorithm 1. Create a Priority Queue. 2. Insert the starting node. Image credits: google.com Module Code & Module Title Slide Title SLIDE 39  Informed Search Algorithms…cont. A* Search Algorithm 1. Create a Priority Queue. 2. Insert the starting node. 3. Remove a node from the priority queue. Image credits: google.com Module Code & Module Title Slide Title SLIDE 40  Informed Search Algorithms…cont. A* Search Algorithm 1. Create a Priority Queue. 2. Insert the starting node. 3. Remove a node from the priority queue. 3.1. Check if it is the goal node. If yes, then exit. Image credits: google.com Module Code & Module Title Slide Title SLIDE 41  Informed Search Algorithms…cont. A* Search Algorithm 1. Create a Priority Queue. 2. Insert the starting node. 3. Remove a node from the priority queue. 4. 3.1. Check if it is the goal node. If yes, then exit. 5. 3.2. Otherwise, mark the node as visited and insert its neighbors into the priority queue. The priority of each node will be the sum of its cost from the start and the goal. Image credits: google.com Module Code & Module Title Slide Title SLIDE 42  Quick Review Question Name two types of algorithms that are used to explore a search space and find the target state from an initial state. Image credits: google.com Module Code & Module Title Slide Title SLIDE 43  Uninformed vs Informed Search Algorithms Image credits: google.com Module Code & Module Title Slide Title SLIDE 44  Quick Review Question Name two advantages and disadvantages of the informed and uninformed search algorithms. Image credits: google.com Module Code & Module Title Slide Title SLIDE 45  Question and Answer Session Module Code & Module Title Slide Title SLIDE 46 Module Code & Module Title Slide Title SLIDE 47  Summary / Recap of Main Points An overview of the key features, benefits and limitations of informed and uninformed search algorithms, which are fundamental concepts in artificial intelligence and problem solving. The choice between these two types of algorithms depends on the problem at hand and the available expertise. Module Code & Module Title Slide Title SLIDE 48  What To Expect Next Week In Class Preparation for Class Searching Methods in AI Automated System (Robotics)AI Module Code & Module Title Slide Title SLIDE 49