Subject: Artificial Intelligence (CSE 472) Tw : Problem Solving Agents Course : B.Tech. - CSE ST Cie AI Mee MAAS eC EIS \c Pere iey Bester haces pean’ Rete care Stet et) Sharda University, Greater Noida, U.P beterContents 1. Problem Solving using Search Techniques 2. Uninformed Search Strategies i. Breadth First Search (BFS) ii, Depth First Search (DFS) ili, Depth Limited Search (DLS) iv. Uniform CostSearch (UCS) v. Iterative Deepening Depth First Search (IDFS) vi. Bidirectional Search (BDS) 3. Informed Search Strategies 1. Greedy Best Search Heuristic Functions A* searchBe eA NIVE Problem Solving using Search Techniques Objective of Searching algorithms is to find the shortest path from source to destination The algorithms provide search solutions through a sequence of actions that transform the initial state to the goal state. Without these algorithms, Al machines and applications cannot implement search functions and find viable solutions. Importance of Search Algorithms + Solving Problems: Search algorithms enhance the solving of problems in artificial intelligence through logical search mechanisms such as problem definition, actions and search space. + Search Programming: Many Al tasks can be programmed in terms of search, which enhances the formulation of the solution to a given problem. + Goal-Based Agents: Search algorithms enhance the effective operation of goal-based agents. These agents solve problems by searching for the most ideal series of actions that can provide the best solution toa problem. + Support Production Systems: These are systems that support Al applications through the use of rules and the procedures for implementing them. Production systems use search algorithms to search for the sequence ofrules that can result in the desired action. + Neural Network Systems: Neural networks are used to perform various tasks in artificial intelligence Search algorithms enhance the searching of connection weights that will lead to the desired input-output mapping et artProblem Solving using Search Techniques Mee Properties of Search Algorithms Search algorithms have the following main properties: Completeness: A search algorithm can be said to be complete if it provides a solution for a given input when there exists at least one solution for this input. Optimality: Search algorithms are also characterized by optimal solutions. These are the best solutions given by the search algorithms at the lowest path cost. Time Complexity: These algorithms have a maximum time needed to accomplish a task or provide a solution. The time taken is usually based on the complexity of the task. Space Complexity: They have a maximum memory or storage space needed when conducting a search operation. This memoryis also based on the complexity of the task. aed araBe eA NIVE Problem Solving using Search Techniques How Search Algorithms work? Search algorithms work in two main phases: + defining the problem + searching in the search space Defining the Problem Before formulating a problem, various factors need to be defined to enable the search algorithms to perform the required course of action. Defining these factors provides the basis for searching and providing a solution, The following are the factors that need to be defined: Initial state: This is the start state in which the search starts. State space: These are all the possible states that can be attained from the initial state through a series of actions Actions: These are the steps, activities, or operations undertaken by Al agents in a particular state. Goal state: This is the endpoint or the desired state. Goal test: This is a test conducted to establish whether particular state is a goal state. Path cost: This is the costassociated with a given path taken by the agents. aed araBe eA NIVE Problem Solving using Search Techniques How Search Algorithms work? Search algorithms work in two main phases: + defining the problem + searching in the search space. Searchingin the search space Aiterdefining the factors, the agents use the search algorithms to performa search in the search space. A search spaces an abstract configuration that consists ofa Search tree of possible solutions. + Asearch tree is used to configure the series of actions. + The initial state is configured as the root of the search tree. The branches are the actions while the nodes are the outcomes ofthe actions. Ina given problem of Al, the search algorithm will identify the inital state, state space, actions, goal state, and the path cost. + From the initial state, a series of actions will be performed as the search algorithms search for the goal state. + For every state attained by the Al agents, the search algorithms will conduct a goal test to establish whether the state is the desired state. If a particular state attained by the agents is not the goal state then the search algorithm will continue searching until the goal state is attained. aed araBasic concepts of Tree and Graph Search Men mae Objective of Searching algorithms is to find the shortest path from source to destination. Search problems are those in which an Al agent aims to find the optimal sequence of actions that lead the agent fromits start state to one of the goal states. Differencebetween Treeand Graph Tree Graph It is a noniinear data structure It is nontinear data structure A graph is a set of verticesinodes A tee is a set of nodes and edges, and edges In the graph, there is no unique In a tree, there is a unique ode which is known as root node which is known as root Each node can have several edges Usually, a tree can have several child nodes, and in the case of binary trees, each node consists of two child nodes Graphs can form cycles. Trees cannot form a cycle. Aes aaMskoRDS Graph Search Search & Rescue Graphs have become a powerful means of modelling and capturing data in real-world scenarios such as social media networks, Web PAGES sur: and links, and locations and routes in GPSSearch Techniques and Tree Search There are two Techniques: types of Search Blind (unguided or uninformed) search: having no additional information about states beyond that provided in the problem definitions. examples:- Breadth first search, Depth first search Heuristic (guided or informed) search: additional information about the problem is provided in order to guide the search in a specific direction. examples:- Best first search, A* search etc. MskoRDS How searching takes place in a Tree? ‘A tree search starts at the root and explores nodes from there, looking for a goal node (a node that satisfies certain conditions, depending on the problem). For some problems, any goal node is acceptable (NN oF J) for other problems, a minimum-depth goal node is reuited. ile, a goal node nearest the root (only J) Initial state Root of the tree Search space: The entire tree Aes aaUninformed Search + Breadth-First search (BFS) + Depth-First search (DFS) + Depth Limited Search (DLS) + Uniform Cost Search (UCS) + Iterative Deepening Depth First Search (IDFS) + Bidirectional Search (BDS)Breadth-First Search a DeSen 0 A breadth-first search (BFS) explores nodes nearest the root before exploring nodes further away. O It follows, First-In-First-Out methodology. It is open on both ends, where one end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Q For example, after searching A, then B, then C, the search proceeds with D, E, F, G Q Node are explored in the order ABC DEF GHIJKLMNOPQ Q J will be found before N Aes aaBreadth-First Search Tree Simply Remove D, then E, as they have no children and the goal F is. found Front _ Initial State: A Tail [Ay | | TT ExpandA B [c | Expand B (front) and place at tail c |p |E Expand C (front) and place at tail D [E |F F | a Be eA aed araBreadth-First Search DeSen Applications of Breadth-First Search Algorithm 1. Crawlers in Search Engines: Breadth-First Search is one of the main algorithms used for indexing web pages. The algorithm starts traversing from the source page and follows all the links associated with the page. Here each web page will be considered as a nodein a graph. 2, GPS Navigation systems: Breadth-First Search is one of the best algorithms used to find neighboring locations by using the GPS system. 3, Find the Shortest Path & Minimum Spanning Tree for an unweighted graph: When it comes to an unweighted graph, calculating the shortest path is quite simple since the idea behind shortest path is to choose a path with the least number of edges. Breadth-First Search can allow this by traversing a minimum number of nodes starting from the source node. Similarly, for a spanning tree, we can use either ofthe two, Breadth-First Search or Depth-first traversal methods to find a spanning tree. 4, Peer to Peer Networks. In Peer to Peer Networks like BitTorrent, Breadth First Search is used to find all neighbor nodes. 5, Social Networking Websites: In social networks, we can find people within a given distance ‘k’ from a personusing Breadth First Search till’ levels. eesDepth-First Search Mey Q A depth-first search (DFS) explores a path all the way to a leaf before backtracking and exploring another path. Q DFS follows Last in First Out (LIFO) methodologies. Q For example, after searching A, then B, then D, the search backtracks and tries another path from B co Node are explored in the order ABD EHL MNIOPCFGJKQ Q N will be found before J Aes aaThe goal F is found Depth-First Search Front Initial State:A Tail Expand A [fal | T UT 7] B {Cc () (<) Expand B (front) and place at front BD IE ic Simply remove D and then E, as they have no children. Expand C (front) and place at tail [Fi T 7 TT] Aes aaDepth-First Search Backtracking Application In this search, a single branch of the tree has to pursue unti it yields a solution or until a decision to terminate the path is made. It makes sense to terminate a path if it reaches dead-end, produces a previous state. In + such a state backtracking occurs. Depth-first search is a common way that many people Chronological Backtracking naturally approach solving problems like mazes. Order in which steps are i undone depends only on the First, a path in the maze is selected for example, let's choose temporal sequence in which @ path and follow it until a dead end hit or reach the finishing steps were initially made. point of the maze. ‘Specifically most recent step is, If a given path doesn't work, then backtrack and take an always the first to be undone. alternative path from a pastjunction, and try that path. This is also. simple backtracking, ares aratUNIVERSITY Iterative Deepening SearchIterative Deepening Search Be eA UNIVER depth limit Begin the depth-first search with a depth limit of 1. If no solution is found, raise the limit by 1 and start searching from the beginning, and so on. This iterative raising of the depth limit is called iterative deepening The Herative Deepening Depth-First Search (or Iterative Deepening search) algorithm, repeatedly applies depth-imited search with increasing limits It gradually increases limits from 0,1,...d, until the ‘goal node ‘s found, I: terminates in the folowing two cases. 4.When the goal node is found 2The goal node does not exist in the oraphitiee, IDDFS with max depth-limit = 3 Note that iteration terminates at depth-limit=2 Iteration Iteration Iteration 2: A->B-2D->E->C->F->G LeveLo Levelt Lever LeveL3. source node = goal node Aes aaIterative Deepening Search MskoRDS The Iterative Deepening Search combines the positive elements of breadith-first and depth-first searching to create an algorithm which is often an improvement over each method individually. There is a maximum depth which defines how many levels deep the algorithm can look for solutions. A node at the maximum level of depth is treated as terminal, even if it would ordinarily have successor nodes Ifa search “fails,” then the maximum level is increased by one and the processrepeats. The value forthe maximum depth is initially set at 0 (i.e. only the initial node). a D) Depth=1 ° A /\ 1 4 ; hae H) depth=2 ABEFCGDH CP r N) Depth=3 4 ABEIFIKOPCGLRDHMNS Se | S) Depth=4 ees ABEIFIKCGLDHMNDepth Limited Search Mee Depth limited search is an extended and refined version of the DFS algorithm. To avoid the infinite loop status while executing the codes, and depth limited search algorithm is being executed into a finite set of depth called depth limit. Depth-limited search can be halted in two cases: + Standard Failure Value (SFV): The SFV tells that there is no solution to the problem. + Cutoff Failure Value (CFV): The Cutoff Failure Value tells that there is no solution within the given depth-limit. Limit = 2 ~ aves ardUniform Cost Search SNEN?A Uniform-cost search is an uninformed search algorithm that uses the lowest cumulative cost to find a path from the source to the destination. Nodes are expanded, starting from the rect, according to the minimum cumulative cost. UCS expands node with least path cost g. UCS is the modification of BFS. Instead of using the First-In- First-Out queue, it uses a priority queue with path cost g(n) to orderthe nodes Example: in the directed Solution GRAPH, the start node a and end node is d a a ao branching factor d-> depth of the shallowest solution m -> max. depth of search tree I> depth limit a> complete if b is finite b> complete if step costs >= E for E>0 ¢ -> optimal if step costs are same d-> if both directions use BFS aed araHeuristics Search Method UNInformed Search Algorithms a DeSen The informed search algorithm is also called heuristic search or directed search. Informed search algorithms require details such as distance to reach the goal, steps to reach the goal, cost of the paths which makes this algorithm more efficient. The goal state can be achieved by using the heuristic function. The heuristic function is used to achieve the goal state with the lowest cost possible. This function estimates how close a state is to the goal. aed araHeuristics Search Be eA Heuristics are problem-solving strategies which in many cases find a solution faster than uninformed search, Heuristic decisionsare closely linked with the needto make real-time decisions with limited resources. Heuristic search is also called guided search because in this, the search is guidedin a specific direction. Heuristic is only an informedguess of the next step to be taken for solving a problem. Additional information or knowledge about the problems is given in the form of clues or guidelines, which are called ‘heuristics.’ A heuristic evaluation function f(s) for states is used to mathematically model a heuristic. The goal is to find a solution with litle effortand with minimal total cost The bestheuristic would be a function that calculates the actual costs from each nodeto the goal. Heuristic Function= Cost from start state to currentstate+ Estimated distance from state to a goal Start State Current State Goal State NV; Cost Heuristic Function= Cost + Heuristic ares araHeuristics Search a CNET BestFirst Search (Greedy Search) + Greedy best-first search algorithm always selects the path which appears bestat that moment. + Itis the combination of depth-first search and breadth-first search algorithms + Ituses the heuristic function and search. Bestirst search allows us to take the advantages of both algorithms. Sew ed A 13 B 12 c 4 D 7 — E 3 F 8 6 2 H 0 ‘The path of traversal is A—>C—>G—>H Aes aaHeuristics Search Be eA Best First Search (Greedy Search): Steps Step 1: Traverse the root node Step 2: Traverse any neighbour of the root node, that is maintaining a least distance from the root node and insert them in ascending orderinto the queue. Step 3: Traverse any neighbour of neighbour of the root node, that is maintaining a least distance from the root node and insert them in ascending orderinto the queue ‘Step 4: This process will continue until we are getting the goal node Algorithm: Step 1: Place the starting node or root node into the queue. Step2: Ifthe queue is empty, then stop and return failure. Step 3: Ifthe first element of the queue is our goal node, then stop and return success. Step 4: Else, remove the first element from the queue. Expand it and compute the estimated goal distance for each child. Place the children in the queue in ascending order to the goal distance. Step 5: Goto step-3 Step6: Exit aed araSHARDA Heuristics Search UNIVERSIT Best First Search (Greedy Search): Start State: A Goal State: M Step 1 Consider the node A as our root node. So the first element of the queue is A whishis ot our goal node, so remove it from the queue and find its neighbour that are to inserted in ascending order. ca Step 2: ‘The neighbours of A are B and C. They will be inserted into the queue (22) (>) In ascending order. La A Step3 oO o Now B is on the FRONT end of the queue So calculate the neighbours of B that are maintaining a least distance from the roof c B FRONT end of the queue But as it has no further children, so remove it from the queue and Step 4: Now the node F is on the proceed further x Aes aa qoicSHARDA Heuristics Search UNIVERSIT Best First Search (Greedy Search): Start State: A Goal State: M Step 6: Now E is the FRONT end. So the children of E are J and K. Insert them into queue in ascending order EPP E E Step 6: Now K is on the FRONT end and as it has no further children, so remove it and proceed further TTpyC K @2){0) ODIOK) Step 7: % Also, .J has no corresponding children. So remove it and move further. @) ) dye J @) @) Step 8: Now Dis on the FRONT end and calculates the children of D and put it into the queue. id D Aes aaSHARDA Heuristics Search UNIVERSIT Best First Search (Greedy Search): Start State: A Goal State: M Step 9: Now lis the FRONT node and it has no children. So proceed further after removing this node from the queue. [ Fo : Step 10: Now G is the FRONT node, so calculate the neighbours of C that are 10 be inserted in ascending order inthe queue. @2)(0) (e) as (6) ® (as) ww “og Jb %, ‘o Now remove G from the queue and calculate its neighbours that is (9) (7) to be inserted in ascending order in the queue EEA e Step 12: Now M isthe FRONT node of the queue which is our GOAL node. ft _F M ares anitReferences Book: Attificial Intelligence: A Modem Approach by Stuart J. Russelland Peter Norvig Web Links bttos://tackovorlow.com/questions/10680180/uhat.i¢ the 4 ferance-betweon-graph search end.tree search Flos lowardsdatasciene e eom/‘0-gragh-aigoithms su aly-2xclained-e57faa 133693 hos fs. stanford edu/pe ple/abicesos Fis Jimecium com/@dsthegieyitertivedee pening-search-51702ce 297 d5, hos ig. opengenus.o1/teraine-deepening-search) bine lia-master gtboois ciheuretic-searchicontentivae-greedy best frst-sanrch ht [os wy msealearinacom/loabestfist sea Li bins Avwur section inenge bocninderstand elgarthms-n-al htlos Jw edieba com/depthsimited-search! tos. /amw snalticevidhya.con/elog/202-/02/uninformad-search-alaocthms.n-a bios: Aww geaksforpeeks og/a-seerch-aloonthoy ilps JMowacisdatascience com/search-algorthmikstras-alooithm-unilorm-cost-sessch-wilh-python-ccbee?60bao bos: opengenus.org'biiactionalsearch’ bins si ovolng 20 020m xch-algortinesin-a Aes aa