Uninformed Search in Artificial Intelligence

Many tutorials and applications of A.I are dominated by Deep Learning, however, many problems in A.I are simple search problems. If you can solve the same problem quicker, with a simpler implementation and similar outcomes, than it is preferable to use it. In many domains, searching through trees and node networks has this advantage over deep learning.

This article will dive deep search in A.I as simple technique for you to use when you need to solve an unexplored A.I problem.

Problem Formulation

A search problem as 4 core components:

• STATE SPACE — the space over which to search. This involves abstracting the real problem
• INITIAL STATE — represents the agents current state
• GOAL STATE — the desired outcome
• ACTIONS — the possible moves that allow the agent to get from the initial to the goal state

Optional Components:

• COSTS — what costs of moving from moving from each state (making an action)
• HEURISTICS — guides of the search processes

Solution

A solution is the algorithm that can transform your current state to the goal state.

Example of a search problem from Arad to Bucharest

In the above depiction the state space is all the available cities, the actions are moving from one city to the next, the initial state is Arad and the goal is Bucharest.

Representation

Search problems can be represented as graphs from one node to the next with vertices and edges. They can also be represented as a tree, with attributes of depth, branching factor where the same state could be represented many times. Complex probabilistic situations apply a probability to each state under uncertainty to get to the desired state.

Properties of Search

We can evaluate a search algorithm in the following ways:

• Completeness — whether the search will find a solution
• Optimality — when the actions have costs, what is the costs of the algorithm
• Time Complexity — the number of nodes that can be expanded or generated
• Space Complexity — number of nodes that have to be stored in memory

Uninformed Search Algorithms

These are algorithms with a fixed rule and are not domain specific.

Breadth First Search

Start at the initial state and expand to all the next reachable nodes in one step. Set those to the initial state and repeat the previous process. Do this indefinitely until the goal has been reached.

Properties of Breadth First Search:

Where the time complexity is O(b^d+1)

• Where b represents the branching factor
• Where d represents the depth of the shortest solution

The space complexity is b(b^d-1), we typically run out of space before we run out of time for most problems.

This algorithm is complete as it finds a solution every time.

If it is unweighted, this algorithm will find the shortest (optimal) path.

Depth First Search

As implied by the name, the algorithm traverses the depth of the tree first and explores a branch of the tree before backtracking.

Properties:

It has time complexity of O(b^m)

• Where m is the length of the longest path

The space complexity is O(bm) which is linear space. You can only explore one branch at a time.

In most cases this algorithm is incomplete such as for infinite paths, if there are cycles in a path (duplicate states), however if it has finite space, then there always is a solution.

It is not optimal.

Depth Limited Search

A combination of the above searches where your first iterate a single branch as in depth first search, but only go to a specific depth. Truncate the search by only looking at paths d+1.

Solves the infinite path length problem, however, the solution must come before the depth to be complete.

It has similar complexities as depth first search.

Iterative Deepening Search

Iterative deepening search is an extension of the depth limited search. Starting at the depth limit, you iteratively increase the depth until a solution is found or it has failed. If no nodes were cut off in this search, than it has exhausted all available paths.

The time complexity of iterative deepening search is O(b^d)

The space complexity of iterative deepening search is O(bd) or linear

It is also complete as it finds a path is a solution exists at the iteratively defined depth, else it is not.

If the costs are uniform than it will find the optimal path. You can provide a more optimal solution with costs by setting a cost bound of less than the cost for a path and expand.

Uniform Cost Search

This search strategy is much like breadth first search as long as each path as the same cost. This search is applied to graph searching problems and it always expands to the least cost path.

It is optimal since it goes to the least cost path. It is complete since it always arrives at a solution.

Conclusion

Understanding search algorithms and applying them to problems in A.I is very important and can save a lot of time. Hopefully, this article introduced you to those algorithms and will inspire you to apply them into a decision or graph problem that you have (in games, maps, planning and so forth). Thank you.

Source: https://www.teach.cs.toronto.edu//~csc384h/winter/lectures.html