Search Algorithms in AI
- [Search Algorithms in AI - Javatpoint]
Artificial Intelligence (AI) is the study of building agents that act rationally. Most of the time, these agents perform some kind of search algorithm in the background in order to achieve their tasks. Search algorithms are one of the most important areas of AI. In AI, search techniques are universal problem-solving methods. Rational agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve a specific problem and provide the best result.
- What is a Search Algorithm in AI?
Search in AI is the process of navigating from a starting state to a goal state by transitioning through intermediate states.
Almost any AI problem can be defined in these terms.
- State - A potential outcome of a problem
- Transition - The act of moving between states.
- Starting State - Where to start searching from.
- Intermediate State - The states between the starting state and the goal state that we need to transition to.
- Goal State - The state to stop searching.
- Search Space - A collection of states.
The simple reflex agents don’t specifically search for best possible solution, as they are programmed to perform a particular action for a particular state. On the contrary, the AI agents that work towards a goal, identify the action or series of actions that lead to the goal. The series of actions that lead to the goal becomes the solution for the given problem. Here, the agent has to consider the impact of the action on the future states. Such agents search through all the possible solutions to find the best possible solution for the given problem.
- Defining the Problem
The agent should be clear about the goal. This means we need to program the agent, such that it can clearly classify a state as goal. Since there are many ways to reach that goal, the agent should also be able to evaluate a solution and determine its preference for a solution. Let’s look at the factors that need to be defined for formulation of a problem.
- Search: Searching is a step by step procedure to solve a search-problem in a given search space. A search problem can have three main factors:
- Search Space: Search space represents a set of possible solutions, which a system may have.
- Start State: It is a state from where agent begins the search.
- Goal test: It is a function which observe the current state and returns whether the goal state is achieved or not.
- Search tree: A tree representation of search problem is called Search tree. The root of the search tree is the root node which is corresponding to the initial state.
- Actions: It gives the description of all the available actions to the agent.
- Transition model: A description of what each action do, can be represented as a transition model.
- Path Cost: It is a function which assigns a numeric cost to each path.
- Solution: It is an action sequence which leads from the start node to the goal node.
- Optimal Solution: If a solution has the lowest cost among all solutions.
- A State Space. Set of all possible states where you can be.
- A Start State. The state from where the search begins.
- A Goal Test. A function that looks at the current state returns whether or not it is the goal state.
The Solution to a search problem is a sequence of actions, called the plan that transforms the start state to the goal state. This plan is achieved through search algorithms.
Problem formulation provides an easy way to design a rational agent.
- Search Algorithms Terminology
Search algorithms help find the correct sequence of actions in a search space, to reach a goal state. The sequence of actions might be:
- Sequence in which cities are to be visited to travel from a source to a destination under a given cost function (shortest path, cheapest fare etc.)
- Sequence in which an agent should play moves in a game (chess, tic tac toe, pacman etc.) to win a board game
- Sequence in which a robot arm should solder components on a PCB under a given cost function (e.g. shortest time)
They are mostly implemented as graphs, where the node once visited is not expanded again if revisited during traversal (as against tree, where there is a possibility of a node getting expanded repeatedly if revisited during traversal - leading to recursion).
In the AI algorithm, to solve the problem we use the searching technique. The search algorithms help you to search for a particular position in such games.
- Problem Space: Basically, it is the environment in which the search takes place. (A set of states and set of operators to change those states)
- Problem Instance: It is a result of Initial state + Goal state.
- Problem Space Graph: We use it to represent problem state. Also, we use nodes to show states and operators are shown by edges.
- The depth of a problem: We can define a length of the shortest path.
- Space Complexity: We can calculate it as the maximum number of nodes that are stored in memory.
- Time Complexity: It is defined as the maximum number of nodes that are created.
- Admissibility: We can say it as a property of an algorithm that is used to find always an optimal solution.
- Branching Factor: We can calculate it as the average number of child nodes in the problem space graph.
- Depth: Length of the shortest path from an initial state to the goal state.
- Search Space
Unlike state space, which is a physical configuration, the search space is an abstract configuration represented by a search tree or graph of possible solutions.
A search tree is used to model the sequence of actions. It is constructed with initial state as the root. The actions taken make the branches and the nodes are results of those actions. A node has depth, path cost and associated state in the state space.
The search space is divided into 3 regions, namely, Explored, Frontier, Unexplored.
Search involves moving the nodes from unexplored region to the explored region. Strategical order of these moves performs a better search. The moves are also known as node expansion. Picking the order of node expansion has provided us with different search strategies that are suited for different kind of problems.
Different search strategies are evaluated along completeness, time complexity, space complexity and optimality. The time and space complexity are measured in terms of:
- b: maximum branching factor of the search tree (actions per state).
- d: depth of the solution.
- m: maximum depth of the state space (may be ∞).
- Two Types of AI Search Algorithms
There are two kinds of search, based on whether they use information about the goal. Based on the search problems we can classify the search algorithms into uninformed (Blind search) search and informed search (Heuristic search) algorithms.
- Uninformed: In which the algorithm does not have any additional information about the search space other than what has been provided in the problem statement (e.g. start node, end node, nodes and edges of the graph, weights etc.)
- Informed: In which the algorithm has additional information other than the problem statement (e.g. euclidean distance between any node and the destination node)
