AI Search Algorithms With Examples
The Application of AI Search Algorithms To Solve Real-World Problems
Finding for something known is called ‘Search’ in contrast to what we call ‘Research’ which is looking for something unknown. As the name suggests the duty of AI Search algorithms is also, searching. Problem-solving is one direct application of search. Effective and efficient solutions can be formulated for real-world problems with the help of AI search algorithms.
Before diving deep into algorithms, first, we should understand the nature of a problem and some related terminology. Generally, a problem consists of 04 major components as States, Actions/Operations, Goals, Path. Simply, problem-solving can be identified as a process involving transforming a set of states through actions or operations to a goal along a path/paths.
State-Space
State-space consists of all the possible states together with actions to solve a specific problem. In the graphical representation of state space (such as trees), the states are represented by nodes while the actions are represented by arcs. Any state space has an initial ‘Start’ node and an ending ‘Goal’ node or multiple Goal States. The path from the initial start node to the final goal node is known as the ‘Solution’ for the particular problem.
Note: A problem may have multiple goals as well as paths.
Problem 01:
For a clear understanding of state space, consider the following problem [Figure 2].
Imagine there is a robot in room ‘A’ (initial state), and it needs to go to room ‘Z’ (goal state). We can draw a state space in terms of a tree if we consider all the possible movements of the robot in each room (node). For example, when the robot is at initial state A, he can either go to B or D. When the robot moved to the next state B, he can move to C, E, or back to A [Figure 3].
Based on all the possible movements of the robot at each state we can draw the state space for the above scenario as follows:
We can identify many paths beside the direct path A, B, C, Z.
Ex: A B C Z
A B A B C Z
A D E B C Z
A D E B A B C Z
....It can be observed that some paths are shorter while others are longer. The real problem arises here. We can figure out the best/shortest path in cases like the above example where the state space is small. But imagine a state-space with hundreds of thousands of nodes. How can we explore such a state-space?
The solution is nothing but search algorithms. In the next chapter, we will discuss the 08 major search algorithms in Artificial Intelligence.
Search algorithms
Since the state spaces are very large in general, we employ search algorithms to navigate through the state-space effectively and efficiently. A search algorithm defines how to find the path (solution) from the initial state to the goal state. Different algorithms define different methods to move from the current state (node) to the next state (node). Some algorithms provide just the systematic ways to explore the state space while others tell how to explore effectively and efficiently.
The search algorithms are of two types as uninformed and informed search algorithms [Figure 5]. Informed search algorithms provide just a systematic way to explore the state space and no additional information are provided to support the search process. Breadth-first search, Uniform search, Depth-first search, Depth limited search, Iterative deepening search, and Bi-direction search are the 06 main uninformed search algorithms.
On the other hand, informed search algorithms such as Greedy search and A* search algorithms are based on additional information which makes the searching procedure both systematic and effective.
Note: There are some AI search algorithms that do not fall under any of the above major categories. Because, there are problems that do not need a specific path to solve but concern on whether the searching process can come to a goal state. When applying search for such problems, we just find the best available node in the vicinity (local search), or searching in competitive environment (adversarial search).
Ex:- Some games like chess, hill climbing, certain design and scheduling problems.
Search algorithm evaluating criteria:
There are 04 criteria we employ to evaluate the performance of each of those search algorithms we mentioned above. They are:
- Completeness: Ability to find a solution when there is a solution (The algorithm should not miss any node before reaching any goal node/end of the state space).
- Optimality: Ability to find the highest quality solution (The algorithm should find the goal nodes in shallower level first).
- Time complexity: How long the algorithm takes to process the nodes. (The execution time of the algorithm/ CPU time)
- Space complexity: How much memory is used by the algorithm to store nodes.
In order to understand the application above algorithm first consider the following scenario. Next, we will apply each search algorithm to find the solution and compare the performance according to the evaluating criteria mentioned.
Problem 02:
How to choose the right set of exercise equipment at the gym to save time and burn maximum calories.
“Gymnasiums are full of different exercise equipment with different calorie burn rates. When doing exercise, it is important to cover the full-body, rather than a part of the body. Selecting exercise techniques with the least recovery time can reduce the overall time taken to do the exercise as well as any damages to the body. Therefore selecting the right exercise machine to burn the target calorie, and involving the whole body in to exercise process and with least prone to cause injuries is important. The scenario is based on the information given in table 1 and state-space [Figure 6].”
Path Cost: Time taken to burn 300 Cal (minutes)
Heuristic Value: Recovery time required after burning 300 Cal (minutes)Note: the units of both path costs and heuristic values are the same.
Based on the above information the following state-space diagram is drawn [Figure 6]. This is a problem with multiple paths but a single goal node. The following diagram is drawn including path costs and heuristic values also. But note, that additional information is required for certain algorithms only. Down each path, whole-body sections (upper body, middle body and lower body) is covered.
Now we will discuss the features of uninformed and informed search algorithms while applying them to the above state-space.
Note: To implement the search, usually we use two lists to store the nodes as OPEN (nodes to be visited/fringe) and CLOSED (nodes already visited).
For the demonstration of each algorithm, I have employed an online simulation tool: AI Search (ali-elganzory.github.io)
1. Uninformed Search Algorithms
Uninformed search algorithms follow a systematic way of exploring across the state space and do not employ additional information (Heuristics)
1.1 Breadth-first Search (BFS)
As the name implies, the BFS algorithm explores the state space layer-by-layer [Figure 7]. When we explore a node, children are always added to the end of the OPEN list. When removing nodes from OPEN to be added to the CLOSED, check whether it is the goal node, if it is, then stops.
Path: 0, 1, 5, 10, 13The traversal is in the CLOSED list. But the OPEN list and CLOSED list altogether contribute to the space complexity since the total number of nodes stored in the memory is the summation of OPEN and CLOSED lists.
Since the nodes beyond the goal node in the OPEN list are not processed the time complexity of BFS is associated with the number of nodes in the CLOSE list only. Since the state-space is explored layer-by-layer, if there is a solution, it is definitely found. Hence BFS is complete. BFS is optimal because the goal nodes in the shallower level are found first.
In BFS, the space complexity for state-space with a branching factor ‘b’ and the level in which the goal node found is ‘d’, is O(bᵈ⁺¹). The time complexity is O(bᵈ) because although memory contains nods from ‘d+1’, nodes beyond ‘d’ are not processed in BFS.
1.2 Depth-First Search (DFS)
In DFS, the state space is explored along branches depthwise. It checks for the goal node along each branch.
Path: 0, 4, 9, 12, 13Since DFS identifies the deeper level goals before the shallower level ones, it is not optimal. DFS is not complete also. Because, if there is a loop in the one branch in the state space, even though we can find the goal node along another branch, still we can not go to that branch due to the loop.
Amazingly, the DFS has very low memory usage. It only stores the nodes along the branch, thus in each level minimum number of nodes are stored unlike in BFS where all the nodes get stored in each level. In the worst-case scenario, if the maximum depth of the search tree with branching factor ‘b’, is ‘m’ then the space and time complexities of DFS are O(bm) and O(bᵐ) respectively.
1.3 Depth-Limited Search (DLS)
In DFS you noticed that it is not optimal i.e.: if the goal is present at the shallower level are not found first. What if we set a limit to the depth being searched? It is DFS, where we can set a depth limit so that beyond that tree is not searched. So, if the goal is at a shallower level, then it is found quickly. But what if the goal is beyond the level we set? That’s what happened in our example scenario also [Figure 9]. Here, the depth is set to level 3, but the goal node is at level 4, so the search will never be able to find the goal node.
Path: Not foundIn DLS, it is neither complete nor optimal because not all the nodes in the graph are checked and goal nodes cannot be found effectively. If we set a depth limit of ‘l’ for state-space with branching factor ‘b’ then the space and time complexities of DLS will be O(bl) and O(bˡ), respectively.
1.4 Iterative Deepening Search (IDS)
In IDS, we increase the depth limit iteratively and execute the DFS until the goal node is found. The use of DFS helps in the lesser usage of memory to store nodes. And since the state-space is explored iteratively (layer-by-layer) if the goal node is in a shallower level (optimal), it is found first before going deeper, and all the nodes in a layer are checked completely (completeness).
Therefore IDS possesses the advantage of both DFS (by consuming less memory space) and BFS (complete and optimal) and it has eliminated the problems faced by DLS. The animation below shows the traversal through state space under IDS [Figure 10].
Path: 0, 4, 9, 12, 131.5 Bi-directional Search (BDS)
BDS is applied if we run two simultaneous BFS search algorithms: one from ‘start node’ to ‘goal node’ forward, and the other is from ‘goal’ to ‘start’ backwards, waiting for two searches to meet each other at the middle. because of this, both the time and space complexities become two times the half of that BFS (which is extremely smaller than O(bᵈ) of BFS). For a graph with branching factor ‘b’ and depth ‘d’, space and time complexities of BDS are denoted by O(bᵈ/²).
Note: Since, 2×O(bᵈ/²) ≈ O(bᵈ/²), we use O(bᵈ/²) instead of 2O(bᵈ/²)
But BDS is not applicable for situations like our example, where some children nodes have multiple parents (Ex: node-9 has node-3 and node-4 as parent nodes). Because the backward search algorithm cannot determine which node to follow from the multiple parent nodes.
1.6 Uniform Cost Search (UCS)
In UCS, each action (edge) from one node to another node is given a value. And each node is associated with a total path cost which is calculated from the ‘start node’ to the particular node. In UCS, this total path cost is considered instead of depth.
Similar to BFS, we expand the lowest cost node rather than the shallowest node in the OPEN list. Although in BFS, the cross-connections in the graph are neglected, here they are considered since each path is associated with a value.
f(n) = g(n)
= Summation(total path cost to each node from start node)
= (Node0-Node1)+(Node1-Node6)+(Node6-Node10)+(Node10-Node13)
= 10 + 15 + 10 + 11
= 46 (path cost)
Path: 0, 1, 6, 10, 13 (Path with the least path cost)According to our scenario, only the lowest costs path is calculated above. In the animation [Figure 11] you can observe the traversal is quite similar to BFS but considering the cost. Therefore UCS is complete and optimal and the time and space complexities are similar to that of BFS’s which are O(bᵈ), and O(bᵈ⁺¹), respectively.
2. Informed Search Algorithms
In informed search algorithms additional information is used to make the search more efficient and effective. That additional information is called heuristics. Heuristics are not theories but some common sense experience like information.
Ex: If you travel between two cities by car, the heuristic will be the traffic level. (Directly the path cost will be the distance between two cities. Additional information such as displacement and traffic between the cities are considered as the heuristics)
In informed search algorithms, to find the best node to be visited next, we use an evaluation function f(n) which assists the child node to decide on which node to be visited next. Then we traverse to the next node with the least f(n) value. Depending on the f(n), we have two informed search algorithms as greedy search and A* search algorithms.
2.1 Greedy Search Algorithms
In greedy search, the heuristic values of child nodes are considered. The path is determined by calculating the path with the nodes with the lowest heuristic values. Another fact to be noticed is that usually the initial node has the highest heuristic value and the goal node has the lowest. But there can be exceptions like getting a mid-range value for the initial node also.
f(n) = h(n)
= Summation(Heuristic values of nodes)
= Node0 + Node2 + Node7 + Node11 + Node13
= 5 + 10 + 8 + 5 + 0
= 28
Path: 0, 2, 7, 11, 13In greedy search, you can see we do not visit all the child nodes of a particular node. We find heuristics of each child node only the one with the lowest value is inserted to the OPEN list to be processed. Therefore greedy search is not complete. As well as this is not the best path (not the shortest path - we found this path in uniform cost search). Therefore greedy search is not optimal, also. As a solution, we should consider not only the heuristic value but also the path cost. Here, comes the A* algorithm.
2.2 A* Search Algorithms
In the A* algorithm, we consider both path cost and heuristics. In A* the f(n) function comprises two components: path cost [g(n)] and heuristic value ([h(n)]. The f(n) value for node ‘a’ can be calculated as follows:
f(n)ₐ = g(n)ₐ + h(n)ₐf(n)ₐ = Evaluation value at the particular node (node 'a')
g(n)ₐ = Total path cost from start node to particular node(node 'a')
h(n)ₐ = The heuristic value of the particular node(node 'a')
Now, we will find the best path according to the A* search algorithm for our previous problem. We have to find the f(n) value for each node and select the child node with the least f(n) value and traverse until meeting the goal node. In the example, only the f(n) values of goals in the path are mentioned.
At Node-0 :
f(n)₀ = 0 + 5 = 5
At Node-3:
f(n)₃ = 10 + 12 = 22
At Node-8:
f(n)₈ = 30 + 10 = 40
At Node-11:
f(n)₁₁ = 36 + 5 = 41
At Node-13:
f(n)₁₃ = 46 + 0 = 46
f(n)ₜₒₜₐₗ = f(n)₀ + f(n)₃ + f(n)₈ + f(n)₁₁ + f(n)₁₃ = 154Path: 0, 3, 8, 11, 13
A* algorithm is complete since it checks all the nodes before reaching to goal node/end of the state space. It is optimal as well because considering both path cost and heuristic values, therefore the lowest path with the lowest heuristics can be found with A*. One drawback of A* is it stores all the nodes it processes in the memory. Therefore, for a state space of branching factor ‘b’, and the depth ‘d’ the space and time complexities of A* are denoted by O(bᵈ). The time complexity of A* depends on the heuristic values.
Summary of The Comparison of Search Algorithms
The summary of each informed search algorithm can be summarized as follows.
Note: All BFS, IDS, BDS (if the algorithm can be applied in both directions), and UCS are complete if the branching factor of the state space graph is finite. If the algorithm can be applied in both direction and the step costs are the same, then BDS is complete.
Conclusion
In informed search algorithms the exploration across the state space is performed based on the heuristic values but in informed search, it is carried out particularly in a systematic way specific to the algorithm.
When considering uninformed search algorithms, the best search algorithm in terms of completeness, optimality, time complexity and space complexity is the Bi-directional Search algorithm if each child node in the state space has only one parent node. But if the child nodes have more than parent nodes in the state-space Bi-directional search is not applicable and it is the IDS Algorithm because it is optimal, complete, space complexity is in the order of (bm) and time complexity is the order of (bᵈ) which is similar to others.
The best search algorithm is A* because it is optimal, complete and employ additional information (heuristics), so the solution is better than that of other algorithms.
References:
https://www.cin.ufpe.br/~tfl2/artificial-intelligence-modern-approach.9780131038059.25368.pdf
http://www.ccpo.odu.edu/~klinck/Reprints/PDF/wikipediaNav2018.pdf
