After a small break in the AI article series, let’s move forward to understanding the next phase of problem solving through searching. Hope our readers can remember the article that appeared in diGIT’s February issue titled ‘Problem solving through Searching’. In that article, I presented the main ideas behind how problem solving in AI. There we went through steps required in problem solving, problem and solution formulation and some real world problems. In today’s article we would look at different ways in which searching can be used to solve problems. We would also look different search strategies available and discuss in detail about one such strategy.
Once we have formulated the problem (as discussed in February article), we have to decide how to find the solutions to those problems. This could be done by searching the state space. If you refer to the section titled ‘Defining Problems and Solution’ in the AI article in February issue, you would be able to refresh your memory about these terms.
When searching for a solution, you have start at the initial state of the search tree/graph and expand each state and visit connected states until the goal state has been reached. There are many ways to determine which state to expand in order to get to the goal state, which are known as ‘Search strategies’. These strategies can be mainly divided in to two groups known as ‘Uninformed search’ and ‘Informed search’ which are described in detail as follows.
- 1. Uninformed Search – This is also known as ‘Blind Search’. This type of search means that they have no additional information about the states other than the information provided by the problem definition. This type of search can generate successor states and also make a distinction between a goal state and a non-goal state.
- 2. Informed Search – This type of search strategy is more advanced than uninformed search. It is also known as ‘heuristic search’. This strategy has the ability to determine whether a non-goal state is much better than another non-goal state in arriving at the goal state effectively and efficiently, thus it uses heuristics based information on top of the information provided by the problem definition about the states in the state space.
In today’s article we will focus on uninformed search strategies and then move on to informed search strategies in the next article.
As explained above, in this type of search strategy we only have access to information given by the problem definition and there are no additional cues provided. One has to search the given state space expanding on each traversed state until the goal state has been reached. There are many different variations of how uninformed search can be achieved and some of those are explained as follows.
In this type of search, the main idea is that the root node is expanded first and then all the successor states of the root node are expanded afterwards. In the next step the rest of the successor states of the states traversed first would be explored. This activity is continued until the goal state for that specific problem is reached. So, at each state, it is checked whether it is the goal state or not. If we explain the breadth-first search in more specific terms, it requires all the nodes at a given depth of the search tree/graph to be expanded before going to the next depth level of the tree. Following search tree shows how breadth-first traversal works.
Figure 1 – Breadth-first traversal on the state space denoted by a search tree. The root node is ‘A’ and the goal node is ‘F’.
The breadth-first traversal searches the tree in this order as depicted by the red arrows.
It is also important to identify the pros and cons of BFS strategy.
- This uninformed search strategy can find the goal node where ever it is located in the search tree since it traverses the each node in a breadth-first manner until the goal node is reached. So we call this search strategy to be ‘Complete’ since it always guarantees that it finds the goal node at some level.
- This finds the goal node is an optimal manner if each of the costs of traversing one node to the other is similar for the entire search tree.
- Consumes lot of time – For example if the goal node is located at a depth of say 1000 in the tree, it has to traverse all the nodes until the depth 1000 to reach at that goal node which would be computationally very expensive. So BFS is not suitable for complex and large problems with a high order search tree.
- Consumes lot of space – At each node it expands the nodes connected to it in the next depth level. Therefore, at each iteration it has to keep in memory all the nodes that have visited so far leading to a high requirement of memory. Therefore we can conclude that BFS has a high time complexity and space complexity.
As the name implies, this search strategy assumes that each of the path costs are equal. This is a simple extension to the BFS search algorithm that we discussed above on a special case when all of the path costs are equal. If the path costs are unequal, then this is exactly identical to BFS.
UCS expands the node with the lowest path cost at each iteration.
In the depth-first search (DFS) strategy, there is a clear distinction from the BFS. This always expands the deepest node in the search tree and goes along the depth of each node rather than across the breadth. In figure 2, we have shown how DFS would work on the same search tree as used in illustrating the behavior of BFS.
Figure 2 – Depth-first traversal on the state space denoted by a search tree. The root node is ‘A’ and the goal node is ‘F’.
The depth-first traversal searches the tree in this order as depicted by the blue arrows.
In this particular scenario, it can be clearly seen that DFS find the goal node in less number of steps when compared to BFS (There can be situations where this would not hold as well).
Let’s now take a look at the advantages and disadvantages of the DFS search strategy.
- Better memory requirements – It only needs to store as single path from the root to leaf node, along the remaining unexpanded sibling nodes for each node in the path. Once a node has been traversed, it can be removed from the memory as soon as all its descendent nodes (immediate child and all other descendent nodes from that particular node – for example node B can be removed from memory once nodes E and F are traversed).
- Does not give an optimal solution – This search strategy might make a wrong choice in the earlier stages of the searching and keep on moving along a very deep path (or even an infinite path) for a long time never realizing that the goal node is not in that path because it does not have heuristics to understand that. Therefore, DFS does not give an optimal solution.
- Does not give a complete solution – If there is a left sub-tree with no goal node, which spans in depth for a long path, DFS would keep on going down and down never terminating leading to an incomplete solution.
This is a small variation to the general DFS search explained above. Since the DFS search can lead to incomplete solutions due to depth unbounded trees (going down a path forever), depth-limited search ensures that the traversal along the depth of a path is limited to a certain pre-determined depth limit. For example, if we can assume that the goal node should be found within the depth limit of 5 from root node, in this case DLS would go down each path up to depth=5 only and search the tree until it finds the goal node eliminating the infinite-path problem found in general DFS search strategy. The problem with DLS is that it is hard to assume a best pre-determined depth-limit without affecting the solution. A way of finding the nest depth-limit is addressed below in no:5.
This is another search strategy usually used as a combination with DFS which helps in finding the best depth-limit (which can be useful for applying depth-limited search). It starts off with depth=0 (only having the root node) and then gradually increasing the depth at each iteration until the goal node has been reached. This strategy tries to combine the good features of both BFS and DFS. As in DFS, its memory requirements are less and like BFS it is a complete algorithm given the branching factor from each node is a finite number and the path cost is a non-decreasing function of the depth of the node. This method is preferred for large search problems since it combines all the goodness of both BFS and DFS and tries to strike a balance between them allowing for better memory requirements and complete and optimal solution finding.
Another type of uninformed search is called ‘bidirectional search’. As the name implies, it means running two simultaneous searches one starting from the root node (initial state) and the other starting from the goal node. In this case, the search starting from the initial state moves forward along the search tree while the other starting from the goal node moves backward until both the search runs meet at a single node in the middle.
The following table shows a comparison between all the uninformed search strategies that we discussed throughout this article in terms of time and space complexities and also in terms of solution optimality and completeness. It would give you a clear idea as to how comparable each search strategy is to the others and also you can get the feeling that Iterative deepening and bidirectional search has goodness of all, although in practice they are hard to be implemented.
b – Branching factor of each node (how many branches are created from each node of the search tree) For example, if the search tree is a binary tree, then the branching factor of each node is equal to 2.
d – Depth of the shallowest solution (the depth of the place where the goal node is located form the root node)
m – Maximum depth of the search tree
l – Limited depth of the search tree used in depth-limited search
C* – Cost of the optimal solution (based on path cost)
E – Cost of every action
Today we looked different search strategies used in problem solving in AI. We focused on understanding various methods used in uninformed search strategies and discusses the pros and cons, features of each approach and they time and space complexities. In the next article, I would be explaining about the other main search strategy which is called the informed search based on additional heuristics.
Artificial Intelligence – A modern Approach, Second edition, Stuart Russell & Peter Norvig