Informed and Uninformed Search Strategies in Artificial Intelligence

Introduction to Artificial Intelligence Search

Search is a fundamental concept in Artificial Intelligence (AI) used to solve automated problem-solving tasks. As outlined in the core textbook Artificial Intelligence: A Modern Approach (3rd edition, 2010) by S. Russell and P. Norvig, search problems involve finding a sequence of actions that transform an initial state into a desired goal state.

Unified Abstraction via Graphs

Many diverse real-world problems can be abstracted as graphs consisting of nodes (vertices) and edges:

• Social Networks: Connections between individuals.

• Transportation Routes: Mapping paths between geographic locations.

• Puzzle-State Spaces: The different configurations possible within a game or puzzle.

Graph-based abstraction allows for specialized measurements such as:

• Time: Duration to traverse an edge.

• Distance: Physical length between nodes.

• Fuel Efficiency: Measurement such as Miles Per Gallon ($MPG$).

Specific Examples of Search Problems

1. Revenue-Maximizing Tour Agent

Design an agent that, given a road network, per-edge revenues, and constraints, outputs a non-cyclic route that maximizes total revenue.

• State: A weighted directed graph.

• Nodes: Cities in Florida (e.g., Orlando, Tampa, Tallahassee, Miami, Jacksonville).

• Edges: Directed roads between cities.

• Weights: Revenue earned from taking a specific road.

• Example Data:

  • Orlando to Tampa: $3$

  • Tampa to Tallahassee: $4$

  • Tallahassee to Jacksonville: $4$

  • Jacksonville to Tallahassee: $5$

  • Tallahassee to Orlando: $2$

  • Jacksonville to Miami: $2$

  • Miami to Orlando: $3$

  • Miami to Jacksonville: $6$

2. Smart Change-Making Agent

Given a set of coin denominations (e.g., $[1, 2, 5]$) and a target amount (e.g., $11$), the agent must find the minimum number of coins to reach the exact amount.

• Input: $coins = [1, 2, 5]$, $amount = 11$.

• Output: $3$ (e.g., $5 + 5 + 1$).

• Failure Case: If no combination exists, return $-1$.

3. Rescue Robot Path Planning

In disaster response, a robot navigates a discrete environment to reach survivors, avoiding obstacles.

• Initial Location: Green square.

• Goal Location: Red flag.

• Obstacles: Blue cells (Value $1$ in a binary grid).

• Optimal Path: Shortest number of steps.

4. Intelligent Puzzle Solver (8-Puzzle)

A $3 \times 3$ grid contains 8 numbered tiles and one empty space. The agent slides tiles into the empty space to transform an initial configuration into a target goal configuration in the fewest possible moves.

Environment Properties

When designing search agents, the environment must be characterized based on several properties:

• Fully vs. Partially Observable: Does the agent see everything or only its immediate surroundings?

• Stochastic vs. Deterministic: Are action results predictable or random?

• Continuous vs. Discrete: Is the state space a grid/finite set or an uncountable range?

• Sequential vs. Episodic: Does the current action affect all future decisions?

• Static vs. Dynamic: Do obstacles/states move or change while the agent is searching?

• Single agent vs. Multi-agent: Is the robot acting alone or competing/collaborating?

Problem-Solving Agent Architecture

Agent Definition

An agent is defined by the following equation: $\text{agent} = \text{architecture} + \text{program}$

• Agent Function: A mathematical mapping of perception sequences to actions (the search strategy).

• Agent Program: The software implementation of the agent function running on the hardware.

Core Components

• Sensor: Hardware for perception (e.g., Camera).

• Actuator: Hardware for taking actions (e.g., Mechanical arms).

• Architecture: The physical infrastructure comprising sensors and actuators.

Behavioral Characteristics

• Goal-Oriented: Deliberate (not reactive) planning to reach a specific state.

• Deliberative Reasoning: Plans a sequence of steps rather than reacting to stimuli.

• Performance Measure: Success is calculated based on efficiency (time and space complexity) and solution quality (optimality).

Fundamentals of Graph Theory for Search

Definitions and Graph Types

• Graph ($G$): Defined as $G = (V, E)$, where $V$ is a set of vertices and $E$ is a set of edges.

• Edge ($E$): Represented as $(u, v)$ or $u \rightarrow v$.

• Undirected Graph: Edges do not imply direction.

• Directed Graph (Digraph): Edges are one-directional.

• Connected vs. Disconnected: A graph is connected if every pair of nodes has a path between them.

• Tree: A connected graph with no loops (cycles).

• Weighted Graph: A graph where values (costs, distances) are associated with edges.

Node Density

• Sparse Graph: The number of edges is proportional to the number of vertices ($O(V)$).

• Dense Graph: The number of edges is on the order of the square of the number of vertices ($O(V^2)$).

Complete Binary Trees

• Complete Tree: All levels are filled except possibly the last, which is filled from left to right.

• Level-Complexity Relationship: For a tree with $n$ nodes and $L$ levels:

  • $|V| = 2^L - 1$

  • $L = \log_2 |V|$

• Visiting Complexity:

  • Level by level: $O(\log_2 n)$.

  • Node by node: $O(n)$.

  • Edge by edge: $O(E)$.

Successor Functions and Search Space

Successor Function

Given a current state, a successor function returns a set of valid next states (successor states).

• Components: Current State, Actions, and Resulting Successor States.

• Cost: Each successor can be associated with an action cost.

• Pruning: In implementation, we ignore redundant states (e.g., previously visited states).

Space Distinction

• State Space: The set of all possible configurations reachable from the initial state.

• Search Space: The specific subset of the state space that the agent actually explores/traverses while trying to reach the goal. This is often represented as a Search Tree constructed dynamically during the search process.

Uninformed (Blind) Search Algorithms

Uninformed search algorithms explore the state space without any domain-specific knowledge about the location of the goal.

Search Hardness

Search is difficult because the tree size grows exponentially. Given a constant branching factor ($b$) and a goal at depth ($d$), the tree can have $b^d$ branches in the worst case.

• Example 1: $b = 2, d = 10 \rightarrow 2^{10} = 1024$ states.

• Example 2: $b = 10, d = 10 \rightarrow 10^{10} = 10,000,000,000$ states.

Breadth-First Search (BFS)

• Strategy: Level-by-level exploration.

• Data Structure: Queue (First-In, First-Out / FIFO).

• Logic: Dequeue a node, check if it's the goal; if not, enqueue all valid, unvisited neighbors.

• Pros:

  • Guarantees the shortest path in unweighted graphs.

  • Systematic exploration; does not miss closer solutions.

• Cons:

  • High memory usage (must store all nodes at the current level).

  • Inefficient for very deep goals.

• Complexity: $O(b^d)$.

Depth-First Search (DFS)

• Strategy: Branch-by-branch exploration (explores deep into one path before backtracking).

• Data Structure: Stack (First-In, Last-Out / FILO).

• Logic: Pop a node, mark as visited, explore neighbors by pushing them onto the stack.

• Pros:

  • Low memory usage (only stores the current path and siblings of nodes on the path).

  • Can find deep solutions faster if they exist on the explored branch.

• Cons:

  • Does not guarantee the shortest path.

  • Can get stuck in infinite loops in graphs with cycles (requires a visited list).

  • May waste time in deep, irrelevant branches.

Informed (Heuristic) Search Algorithms

Informed search uses a Heuristic Function $h(n)$ to estimate the cost from node $n$ to the goal.

1. Greedy Best-First Search (GBFS)

• Strategy: Always expands the node with the lowest estimated future cost ($h(n)$).

• Risk: It can be "lucky" and find a quick solution, but more often, it fails to find the optimal path or finds no path at all because it ignores the cost already incurred ($g(n)$).

2. Dijkstra's Algorithm

• Strategy: Focuses on the past cost ($g(n)$), which is the exact cost incurred from the start to the current node.

• Implementation: Uses a Priority Queue (Min-Heap) to expand the node with the smallest total incurred cost.

• Relaxation: The process of updating the shortest known distance to a node if a better path is found through a neighbor.

• Pros: Guaranteed optimality if edge weights are non-negative.

• Cons: Slows down as it expands outward in all directions like BFS.

3. A* Search

• Total Cost Function: $f(n) = g(n) + h(n)$.

  • $g(n)$: Actual cost from start to node $n$.

  • $h(n)$: Estimated cost from node $n$ to the goal.

• Strategy: Combines the accuracy of Dijkstra's with the guidance of Greedy search.

• Optimality: Guaranteed to find the shortest path if the heuristic is Admissible (never overestimates) and Consistent (satisfies the triangle inequality).

• Pros: Highly efficient; prunes paths that cannot possibly be optimal.

• Cons: Memory-intensive (stores all explored nodes).

• Admissible: Never overestimates the true remaining cost, where h(n) ≤ h*(n) and guarantees A* optimality.

• Consistent: Satisfies triangle inequality where h(n) ≤ c(n, n’) + h(n’), so consistent → admissible.

• Dominance: If$h_2\left(n\right)\ge h_1\left(n\right)$ for all n, and both are admissible, then $h_2$ dominates $h_1$ and $h_2$ becomes more informed, therefore, A* expands fewer or equal nodes.

Heuristic Measurement Tools

Manhattan Distance

Used for grid-based movement where only horizontal and vertical steps are allowed. $d = |x_2 - x_1| + |y_2 - y_1|$

• Property: Always admissible in grid worlds because an agent must move at least that many steps to reach the target.

Euclidean Distance

Used for continuous space or when movement in any direction is allowed. $d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

• Application: Robot/Drone navigation.

Chebyshev Distance

Used when diagonal movement has the same cost as horizontal/vertical movement. $d = \text{max}(|x_2 - x_1|, |y_2 - y_1|)$

• Application: Eight Queens problem, Chess movements.

Hamming Distance / Misplaced Tiles

The number of positions where the current state differs from the goal state.

• Hamming Formula: $d(X, Y) = \sum_{i=1}^n \delta(X[i], Y[i])$, where $\delta$ is $1$ if the items at index $i$ differ, and $0$ otherwise.

• 8-Puzzle Limitation: While easy to calculate, it does not account for the actual physical distance tiles must travel.

Summary Checklist for Search Formulation

To solve a search problem, one must decide:

1. State Representation: How to represent initial, goal, and intermediate states.

2. Action Set: Valid moves and their restrictions.

3. Successor Function: Mapping current states to next states.

4. Path Cost Function: Calculating weights/costs ($g(n)$).

5. Heuristic Selection: Choosing a function ($h(n)$) that is admissible and consistent to ensure optimality.