This article explains what is AI search, types of AI search techniques and the problem space
SEARCH IN ARTIFICIAL INTELLIGENCE
Search plays a major role in solving many Artificial Intelligence (AI) problems. Search is a universal problem-solving mechanism in AI. In many problems, sequence of steps required to solve is not known in advance but must be determined by systematic trial-and-error exploration of alternatives.
The problems that are addressed by AI search algorithms fall into three general classes:
single-agent path-finding problems, two-players games, and constraint-satisfaction problems
SINGLE-AGENT PATH-FINDING PROBLEMS
Classic examples in the AI literature of path-finding problems are sliding-title puzzles, Rubik’s Cube and theorem proving. The single-title puzzles are common test beds for research in AI search algorithms as they are very simple to represent and manipulate. Real-world problems include the traveling salesman problem, vehicle navigation, and the wiring of VLSI circuits. In each case, the task is to find a sequence of operations that map an initial state to a goal state.
TWO-PLAYERS GAMES
Two-players games are two-player perfect information games. Chess, checkers, and othello are some of the two-player games.
CONSTRAINT SATISFACTION PROBLEMS
Eight Queens problem is the best example. The task is to place eight queens on an 8*8 chessboard such that no two queens are on the same row, column or diagonal. Real-world examples of constraint satisfaction problems are planning and scheduling applications.
PROBLEM SPACE
Problem space is a set of states and the connections between to represent the problem. Problem space graph is used to represent a problem space. In the graph, the states are represented by nodes of the graph, and the operators by edges between nodes. Although most problem spaces correspond to graphs with more than one path between a pair of nodes, for simplicity they are often represented as trees, where the initial state is the root of the tree.
The cost of the simplification is that any state that can be reached by two different paths will be represented by duplicate nodes thereby increasing the tree size. The benefit of using tree is that the absence of cycles greatly simplifies many search algorithms.
One feature that distinguishes AI search algorithms from other graph-searching algorithms is the size of the graph involved. For example, the entire chess graph is estimated to contain over 10^40 nodes. Even a simple problem like twenty-four puzzle contains almost 10^25 nodes. As a result, the problem-space graphs of AI problems are never represented explicitly by listing each state, but rather are implicitly represented by specifying an initial state and a set of operators to generate new states from existing states.
Moreover the size of an AI problem is rarely expressed as the number of nodes in its problem-space graph. The two parameters of a search tree that determine the efficiency of various search algorithms are its branching factor and its solution depth. The branching factor is nothing but average number of children of a given node. For example in eight-puzzle problem, the average branching factor is square-root(3) or about 1.732. The solution depth of a problem instance is the length of a shortest path from the initial state to a goal state or the length of a shortest sequence of operators that solve the problem.