Artificial Intelligence Search Algorithms and Agent Fundamentals

Posted on Oct 26, 2025 in Computer Engineering

AI Agents and Architecture

Agents perceive their environment using sensors and act rationally upon that environment using effectors.

Agent Architecture

Agent → Actions (with effectors) → Environment → Percepts → Agent

Key Agent Features

• Situatness: The agent’s direct connection to its environment through percepts and effectors.
• Autonomy: The agent acts without intervention by humans or other agents. (Preprogramming does not count.)
• Adaptivity: The ability to react flexibly to changes in its environment.
• Sociability: The capability of interacting with humans and other agents.

Uninformed Search Strategies

Uninformed Search is a search performed without specific information about the goal location. We generate all successor states (children) for a current state and check if a goal is among them. If not, we continue generating children.

Types of Uninformed Search

Breadth-First Search (BFS)

Expands the shallowest unexpanded node. It uses a FIFO queue (Open List). If repeated states are encountered, do not add the parent of a node as a leaf. New successors go at the end of the queue.

Depth-First Search (DFS)

Expands the deepest unexpanded node. It uses a LIFO queue. If repeated nodes are encountered, do not add a state as a leaf if that state is already on the path from the root to the current node. New successors go at the beginning of the queue.

Depth-Limited Search (DLS)

Same as DFS, but the tree is not explored below a previously defined depth limit (L).

Iterative Deepening Search (IDS)

Runs multiple DFS searches with increasing depth limits (e.g., L=1, L=2, L=3…). Although it re-explores nodes, it is often efficient in practice.

Uniform Cost Search (UCS)

Finds the optimal path based on cost. This strategy is used when costs are associated with actions, and the least expensive solution is desired. The algorithm always expands the node n that minimizes g(n), where g(n) is the cost of the path from the initial state to state n.

Informed Search (Heuristic Search)

Informed Search uses heuristic information to choose the next state based on cost and an evaluation function.

Key Informed Search Algorithms

Best-First Search

Uses an evaluation function f(n) for each node. It expands the most desirable unexpanded node. Here, f(n) = h(n), where h(n) provides information about the closeness to the final state. The node with the lowest f(n) is expanded first.

Greedy Best-First Search

A special case of Best-First Search. It uses a heuristic function h(n) to estimate the cost from node n to the goal. It expands the node with the lowest h(n). If h(n)=0, the goal is found. This method does not keep track of the total cost of the route.

A* Search Algorithm

Expands the node based on the estimate of the total path cost through that node. The evaluation function is f(n) = g(n) + h(n).

• g(n): The cost incurred so far to reach n (total path cost).
• h(n): The estimated cost from n to the goal (heuristic).
• f(n): The estimated total cost of the path through n to the goal.

The efficiency depends on the quality of the heuristic h(n). The heuristic h(n) is admissible if, for every node n, h(n) ≤ h*(n), where h*(n) is the real cost to reach the goal.

Recursive Best-First Search (RBFS)

Similar to DFS, but it keeps track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds the f-limit, the algorithm backtracks to the alternative path.

Simplified Memory Bounded A* (SMA*)

Similar to A*, but when memory is full, the algorithm deletes the worst node (the one with the largest f-value). Like RBFS, it remembers the best descendant in the branch it deletes. SMA* finds the optimal reachable solution given the memory constraint, though time complexity can still be exponential.

Local Search and Optimization Techniques

Local Search algorithms start from a prospective solution and move to a neighboring solution. They keep track of a single current state and ignore the paths taken, thus using very little memory. These are often used for “pure optimization” problems where all states have an objective function (measuring how good the state is). The goal is to find the state with the maximum or minimum objective value.

Optimization Algorithms

Hill Climbing Search

An iterative algorithm that starts with an arbitrary solution and attempts to find a better solution by incrementally changing a single element. If the change produces a better solution, it is taken as the new current solution. This is repeated until no further improvements are found.

int initialState;
int currentState;
currentState = initialState;
loop:
  successor = currentState.generateSuccessor();
  if (successor.isBetter(currentState)):
    currentState = successor;
  end loop;

Local Beam Search

Keeps track of K states instead of just one.

Algorithm:

1. Initially: Select K randomly selected states.
2. Next: Determine all successors of the K states.
3. If any successor is the goal, finish.
4. Else, select the K best states from all successors and repeat.

Genetic Algorithms

A successor state is generated by combining two parent states. The process starts with K randomly generated states (the population). It uses an evaluation function (or fitness function), where higher values indicate better states (this differs from heuristic functions).

Search Environment Types

Online Search

The environment can change while the algorithm is searching for the solution. When a solution is found, the agent must check if the environment has changed. If it has, the algorithm may need to run again. Example: Routing, where traffic conditions change the connections between cities.

Offline Search

The environment does not change while the algorithm is running. Example: The 8-Puzzle, where the board state only changes when the agent makes a move.

Reversible/Irreversible State Spaces

• Reversible: Actions can be undone.
• Irreversible: Actions cannot be undone. Example: In Chess, once a move is made, it cannot be undone.

Exploration Problem

A problem where the agent does not know the state space or the actions available beforehand.