Srujit Biradawada

Artificial Intelligence and Machine Learning Search Techniques – Part 1

Srujit Biradawada

Introduction

Search algorithms form the backbone of many artificial intelligence (AI) and machine learning (ML) applications. These techniques enable AI agents to navigate complex problem spaces, find optimal solutions, and make intelligent decisions. This article provides a comprehensive exploration of various search algorithms used in AI and ML, including their theoretical foundations, practical implementations, and real-world applications.

Fundamentals of Search in AI

At its core, a search problem in AI consists of several key components:

  1. Agent: The entity performing the search
  2. Initial State: The starting point of the search.
  3. Actions: Possible moves or decisions the agent can make
  4. Transition Model: Describes how actions change the state
  5. Goal Test: Determines if a given state is the desired outcome
  6. Path Cost: Assigns a numeric cost to each action sequence

The general approach to solving search problems follows this pattern:

  1. Start with the initial state
  2. Repeat until a solution is found or the frontier is empty:
    a. If the frontier is empty, return failure (no solution)
    b. Choose and remove a node from the frontier
    c. If the node is a goal state, return the solution
    d. Expand the node and add resulting nodes to the frontier

A revised approach that avoids revisiting states includes an explored set:

  1. Start with the initial state
  2. Initialize an empty explored set
  3. Repeat until a solution is found or the frontier is empty:
    a. If the frontier is empty, return failure (no solution)
    b. Choose and remove a node from the frontier
    c. If the node is a goal state, return the solution
    d. Add the node to the explored set
    e. Expand the node and add resulting nodes to the frontier if they are not already in the frontier or explored set

Data Structures and Object-Oriented Implementation

To implement search algorithms effectively, we need appropriate data structures. Let’s define some basic classes in Python to represent our search problem:

class State:
    def __init__(self, data):
        self.data = data

    def __eq__(self, other):
        return isinstance(other, State) and self.data == other.data

    def __hash__(self):
        return hash(self.data)

class Action:
    def __init__(self, name, cost=1):
        self.name = name
        self.cost = cost

class SearchProblem:
    def __init__(self, initial_state, goal_state):
        self.initial_state = initial_state
        self.goal_state = goal_state

    def actions(self, state):
        raise NotImplementedError

    def result(self, state, action):
        raise NotImplementedError

    def goal_test(self, state):
        return state == self.goal_state

    def path_cost(self, path):
        return sum(action.cost for action in path)

class Node:
    def __init__(self, state, parent=None, action=None, path_cost=0):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost

    def expand(self, problem):
        return [self.child_node(problem, action)
                for action in problem.actions(self.state)]

    def child_node(self, problem, action):
        next_state = problem.result(self.state, action)
        return Node(next_state, self, action,
                    self.path_cost + action.cost)

    def solution(self):
        return [node.action for node in self.path()[1:]]

    def path(self):
        node, path_back = self, []
        while node:
            path_back.append(node)
            node = node.parent
        return list(reversed(path_back))

These classes provide a foundation for implementing various search algorithms. The State class represents a state in the search space, Action represents possible actions, SearchProblem defines the problem structure, and Node represents a node in the search tree.

Uninformed Search Strategies

Uninformed search strategies do not use any information about the goal state to guide the search process. They systematically explore the search space without considering how “close” a given state might be to the goal.

Depth-First Search (DFS)

Depth-First Search explores as far as possible along each branch before backtracking. It uses a stack (Last-In-First-Out) data structure to manage the frontier.

def depth_first_search(problem):
    frontier = [Node(problem.initial_state)]
    explored = set()

    while frontier:
        node = frontier.pop()
        if problem.goal_test(node.state):
            return node.solution()
        explored.add(node.state)
        frontier.extend(child for child in node.expand(problem)
                        if child.state not in explored and
                        child.state not in (n.state for n in frontier))
    return None

DFS is memory-efficient but may not find the optimal solution and can get stuck in infinite loops in infinite search spaces.

Breadth-First Search (BFS)

Breadth-First Search explores all the neighbor nodes at the present depth before moving to nodes at the next depth level. It uses a queue (First-In-First-Out) data structure for the frontier.

from collections import deque

def breadth_first_search(problem):
    node = Node(problem.initial_state)
    if problem.goal_test(node.state):
        return node.solution()
    frontier = deque([node])
    explored = set()

    while frontier:
        node = frontier.popleft()
        explored.add(node.state)
        for child in node.expand(problem):
            if child.state not in explored and child.state not in (n.state for n in frontier):
                if problem.goal_test(child.state):
                    return child.solution()
                frontier.append(child)
    return None

BFS is guaranteed to find the optimal solution in terms of the number of steps, but it can be memory-intensive for large search spaces.

Uniform-Cost Search (UCS)

Uniform-Cost Search expands the node with the lowest path cost. It’s similar to BFS but considers the cost of actions.

import heapq

def uniform_cost_search(problem):
    node = Node(problem.initial_state)
    frontier = [(node.path_cost, id(node), node)]
    explored = set()

    while frontier:
        _, _, node = heapq.heappop(frontier)
        if problem.goal_test(node.state):
            return node.solution()
        explored.add(node.state)
        for child in node.expand(problem):
            if child.state not in explored and child.state not in (n.state for _, _, n in frontier):
                heapq.heappush(frontier, (child.path_cost, id(child), child))
            elif child.state in (n.state for _, _, n in frontier):
                if child.path_cost < node.path_cost:
                    frontier = [(c, i, n) if n.state != child.state else (child.path_cost, id(child), child)
                                for c, i, n in frontier]
                    heapq.heapify(frontier)
    return None

UCS is optimal and complete, finding the least-cost path to the goal.

Informed Search Strategies

Informed search strategies use problem-specific knowledge to guide the search process, often leading to more efficient solutions.

Greedy Best-First Search

Greedy Best-First Search expands the node that appears to be closest to the goal, as estimated by a heuristic function.

def greedy_best_first_search(problem, h):
    node = Node(problem.initial_state)
    frontier = [(h(node.state), id(node), node)]
    explored = set()

    while frontier:
        _, _, node = heapq.heappop(frontier)
        if problem.goal_test(node.state):
            return node.solution()
        explored.add(node.state)
        for child in node.expand(problem):
            if child.state not in explored and child.state not in (n.state for _, _, n in frontier):
                heapq.heappush(frontier, (h(child.state), id(child), child))
    return None

The heuristic function h(n) estimates the cost from the current state to the goal. A common heuristic for grid-based problems is the Manhattan distance:

def manhattan_distance(state, goal):
    return abs(state[0] - goal[0]) + abs(state[1] - goal[1])

A* Search

A* Search combines the benefits of Uniform-Cost Search and Greedy Best-First Search. It uses both the path cost and a heuristic estimate.

def a_star_search(problem, h):
    node = Node(problem.initial_state)
    frontier = [(node.path_cost + h(node.state), id(node), node)]
    explored = set()

    while frontier:
        _, _, node = heapq.heappop(frontier)
        if problem.goal_test(node.state):
            return node.solution()
        explored.add(node.state)
        for child in node.expand(problem):
            if child.state not in explored and child.state not in (n.state for _, _, n in frontier):
                heapq.heappush(frontier, (child.path_cost + h(child.state), id(child), child))
            elif child.state in (n.state for _, _, n in frontier):
                if child.path_cost < node.path_cost:
                    frontier = [(c, i, n) if n.state != child.state 
                                else (child.path_cost + h(child.state), id(child), child)
                                for c, i, n in frontier]
                    heapq.heapify(frontier)
    return None

A* is optimal if the heuristic function h(n) is admissible (never overestimates the cost to the goal) and consistent (for every node n and successor n’ with step cost c, h(n) ≤ h(n’) + c).

Heuristic Functions

Heuristic functions estimate the cost from the current state to the goal state. A common heuristic for grid-based problems is the Manhattan distance.

def manhattan_distance(state, goal):
return abs(state[0] - goal[0]) + abs(state[1] - goal[1])

Adversarial Search

Adversarial search algorithms are used in competitive scenarios where two or more agents have opposing goals, such as in game playing.

Minimax Algorithm

The Minimax algorithm is used in two-player zero-sum games, where one player tries to maximize their score, and the other tries to minimize it.

def minimax(state, depth, maximizing_player):
    if depth == 0 or is_terminal(state):
        return evaluate(state)

    if maximizing_player:
        max_eval = float('-inf')
        for move in get_possible_moves(state):
            eval = minimax(make_move(state, move), depth - 1, False)
            max_eval = max(max_eval, eval)
        return max_eval
    else:
        min_eval = float('inf')
        for move in get_possible_moves(state):
            eval = minimax(make_move(state, move), depth - 1, True)
            min_eval = min(min_eval, eval)
        return min_eval

def get_best_move(state, depth):
    best_move = None
    best_eval = float('-inf')
    for move in get_possible_moves(state):
        eval = minimax(make_move(state, move), depth - 1, False)
        if eval > best_eval:
            best_eval = eval
            best_move = move
    return best_move

Alpha-Beta Pruning

Alpha-Beta pruning is an optimization technique for the Minimax algorithm that reduces the number of nodes evaluated in the search tree.

def alpha_beta(state, depth, alpha, beta, maximizing_player):
    if depth == 0 or is_terminal(state):
        return evaluate(state)

    if maximizing_player:
        max_eval = float('-inf')
        for move in get_possible_moves(state):
            eval = alpha_beta(make_move(state, move), depth - 1, alpha, beta, False)
            max_eval = max(max_eval, eval)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break
        return max_eval
    else:
        min_eval = float('inf')
        for move in get_possible_moves(state):
            eval = alpha_beta(make_move(state, move), depth - 1, alpha, beta, True)
            min_eval = min(min_eval, eval)
            beta = min(beta, eval)
            if beta <= alpha:
                break
        return min_eval

def get_best_move_alpha_beta(state, depth):
    best_move = None
    best_eval = float('-inf')
    alpha = float('-inf')
    beta = float('inf')
    for move in get_possible_moves(state):
        eval = alpha_beta(make_move(state, move), depth - 1, alpha, beta, False)
        if eval > best_eval:
            best_eval = eval
            best_move = move
        alpha = max(alpha, eval)
    return best_move

Example: Pathfinding in Grid-Based Environments

Consider a grid-based environment with obstacles, where an agent needs to find the shortest path from a start position to a goal position.

class GridWorld:
    def __init__(self, grid):
        self.grid = grid
        self.rows = len(grid)
        self.cols = len(grid[0])

    def is_valid(self, x, y):
        return 0 <= x < self.rows and 0 <= y < self.cols and self.grid[x][y] == 0

    def get_neighbors(self, x, y):
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        neighbors = []
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if self.is_valid(nx, ny):
                neighbors.append((nx, ny))
        return neighbors

def astar_grid(grid, start, goal):
    def heuristic(a, b):
        return abs(b[0] - a[0]) + abs(b[1] - a[1])

    world = GridWorld(grid)
    frontier = [(0, start)]
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while frontier:
        current = heapq.heappop(frontier)[1]

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]

        for neighbor in world.get_neighbors(*current):
            tentative_g_score = g_score[current] + 1

            if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                heapq.heappush(frontier, (f_score[neighbor], neighbor))

    return None

# Example usage
grid = [
    [0, 0, 0, 0, 1],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0]
]
start = (0, 0)
goal = (4, 4)

path = astar_grid(grid, start, goal)
print("Path found:", path)

Conclusion

Search algorithms form the backbone of many AI and ML applications. By understanding and implementing these techniques, developers can create intelligent systems capable of solving complex problems efficiently. As the field of AI continues to evolve, new search algorithms and optimizations will undoubtedly emerge, further enhancing our ability to tackle challenging computational problems.

Sources

  • [PDF] Fundamentals of Artificial Intelligence https://web.cs.hacettepe.edu.tr/~ilyas/Courses/VBM688/lec03_search.pdf
  • State Space Search in AI – GeeksforGeeks https://www.geeksforgeeks.org/state-space-search-in-ai/
  • How can I remember which data structures are used by DFS and BFS? https://stackoverflow.com/questions/3929079/how-can-i-remember-which-data-structures-are-used-by-dfs-and-bfs
  • Search Algorithms in Artificial Intelligence – Scaler Topics https://www.scaler.com/topics/artificial-intelligence-tutorial/search-algorithms-in-artificial-intelligence/
  • State Space Search in Artificial Intelligence – Applied AI Course https://www.appliedaicourse.com/blog/state-space-search-in-artificial-intelligence/
  • Search Algorithms in AI – GeeksforGeeks https://www.geeksforgeeks.org/search-algorithms-in-ai/
  • [PDF] AI: Solving problems by searching https://web.pdx.edu/~arhodes/ai7.pdf
  • [PDF] 3 SOLVING PROBLEMS BY SEARCHING https://www.pearsonhighered.com/assets/samplechapter/0/1/3/6/0136042597.pdf
  • Intro to AI with Python – Unit 0, Part 1: Basic Search – LinkedIn https://www.linkedin.com/pulse/intro-ai-python-unit-0-part-1-basic-search-hitesh-shah-qbvxe
  • [PDF] Problem Solving Agents and Uninformed Search http://www.cs.csi.cuny.edu/~imberman/ai/Uninformed%20Search%20chap3.pdf
  • Breadth First Vs Depth First – algorithm – Stack Overflow https://stackoverflow.com/questions/687731/breadth-first-vs-depth-first
  • Searching in AI ~ DFS & BFS – LinkedIn https://www.linkedin.com/pulse/searching-ai-dfs-bfs-dilli-hang-rai-nzzmf
  • [PPT] Uninformed Search – UMBC https://courses.cs.umbc.edu/undergraduate/CMSC100/Fall09/slides/c21_ai_search.ppt
  • All You Need to Know About Breadth-First Search Algorithm https://www.simplilearn.com/tutorials/data-structure-tutorial/bfs-algorithm
  • Tree Traversal: Breadth-First Search vs Depth-First … – Codecademy https://www.codecademy.com/article/tree-traversal
  • Graph searching: Breadth-first vs. depth-first https://cs.stackexchange.com/questions/298/graph-searching-breadth-first-vs-depth-first
  • Search Algorithms in AI – GeeksforGeeks https://www.geeksforgeeks.org/search-algorithms-in-ai/
  • Lecture 0 – CS50’s Introduction to Artificial Intelligence with Python https://cs50.harvard.edu/ai/2024/notes/0/
  • [PDF] Artificial Intelligence – UCSD CSE https://cseweb.ucsd.edu/~yuxiangw/classes/AICourse-2022Spring/Lectures/Lecture-search3.pdf
  • [PDF] Foundations of Artificial Intelligence Adversarial Search – CS@Cornell https://www.cs.cornell.edu/courses/cs472/2007fa/lectures/06-adversarial_search.pdf
  • A Comprehensive Overview of Search Algorithms in Artificial … https://www.linkedin.com/pulse/comprehensive-overview-search-algorithms-artificial-harsh-kalburgi-gcczc