AI Search Techniques

Types of AI Search Techniques

AI search techniques are broadly classified into two categories:

1. Uninformed (Blind) Search Techniques

Uninformed search techniques do not use domain-specific knowledge. They only use the information provided in the problem definition to explore the search space.

Key Methods:

Breadth-First Search (BFS):

• Explores all nodes at the current depth before moving to the next level.Ensures finding the shortest path if all actions have the same cost.Example Use Case: Finding the shortest path in an unweighted graph.

Code Example:

from collections import deque

def bfs(graph, start, goal):
    queue = deque([start])
    visited = set()

    while queue:
        node = queue.popleft()
        if node == goal:
            return f"Goal {goal} found!"

        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])

    return "Goal not found."

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

print(bfs(graph, 'A', 'E'))

1. Depth-First Search (DFS):
   • Explores as far as possible along a branch before backtracking.
   • Can be memory efficient but may not find the shortest path.
   • Example Use Case: Solving a maze where path cost is irrelevant.
   Key Differences Between BFS and DFS:
   • BFS: Explores level-by-level.
   • DFS: Explores one branch to the deepest level first.

2. Informed (Heuristic) Search Techniques

Informed search techniques use domain knowledge (heuristics) to guide the search process, making them more efficient.

Key Methods:

Greedy Best-First Search:

• Prioritizes exploring nodes that appear to be closest to the goal based on a heuristic.
• May not guarantee the optimal solution.
• Example Use Case: Navigation systems estimating the shortest driving distance.

1. A (A-Star) Search:*
   • Combines the strengths of uniform-cost search and greedy best-first search.Uses the formula:
     f(n)=g(n)+h(n)f(n) = g(n) + h(n)f(n)=g(n)+h(n)
     where g(n)g(n)g(n) is the cost to reach node nnn, and h(n)h(n)h(n) is the heuristic estimate from nnn to the goal.Example Use Case: Robot pathfinding in a grid.
   Code Example:

from queue import PriorityQueue

def a_star_search(graph, start, goal, h):
    pq = PriorityQueue()
    pq.put((0, start))
    cost_so_far = {start: 0}

    while not pq.empty():
        _, current = pq.get()

        if current == goal:
            return f"Goal {goal} reached with cost {cost_so_far[goal]}."

        for neighbor, weight in graph[current]:
            new_cost = cost_so_far[current] + weight
            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                cost_so_far[neighbor] = new_cost
                priority = new_cost + h(neighbor)
                pq.put((priority, neighbor))

    return "Goal not found."

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('D', 1), ('E', 4)],
    'C': [('F', 5)],
    'D': [],
    'E': [('F', 1)],
    'F': []
}

h = lambda x: {'A': 6, 'B': 4, 'C': 2, 'D': 4, 'E': 2, 'F': 0}[x]

print(a_star_search(graph, 'A', 'F', h))

Applications of AI Search Techniques

1. Game Development:
   • Example: Chess engines use minimax algorithms with alpha-beta pruning to decide the best moves.
2. Pathfinding:
   • Example: Autonomous vehicles use A* or Dijkstra’s algorithm for navigation.
3. Robotics:
   • Example: Robots use BFS or A* for obstacle avoidance and optimal pathfinding.
4. Optimization Problems:
   • Example: Scheduling tasks efficiently in manufacturing.

Advantages and Disadvantages of Search Techniques

Uninformed Search:

• Advantages:
  • Simple and straightforward.
  • Guarantees a solution if one exists (BFS).
• Disadvantages:
  • Can be computationally expensive.
  • Does not consider efficiency.

Informed Search:

• Advantages:
  • Uses heuristics to make the search process efficient.
  • Finds optimal solutions faster in many cases.
• Disadvantages:
  • Relies on the quality of heuristics.
  • May be more complex to implement.

Key Takeaways

1. Uninformed search explores blindly, while informed search leverages heuristics for efficiency.
2. BFS is ideal for shortest-path problems, while DFS is suitable for deep exploration.
3. A* search is the most versatile technique, balancing cost and heuristic estimation.

Mastering search techniques equips you with powerful tools to solve complex AI problems, from game development to robotics.