Artificial Intelligence: Iterative Deepening Search

Iterative Deepening Search (IDS) is a search strategy in artificial intelligence that combines the benefits of Depth-First Search (DFS) and Breadth-First Search (BFS). It’s particularly useful for searching large state spaces, like in puzzles or pathfinding problems, where the depth of the solution isn’t known in advance. Below, I’ll explain IDS, how it works, its properties, and provide a clear example.


What is Iterative Deepening Search?

IDS is a heuristic-uninformed search algorithm that repeatedly applies DFS with increasing depth limits until the goal is found or the entire search space is explored. It starts with a depth limit of 0, explores all nodes up to that depth, then increases the limit to 1, 2, and so on, restarting the DFS each time. This iterative process ensures that IDS finds the shallowest goal node (like BFS) while using the memory efficiency of DFS.


How IDS Works

  1. Initialize: Set the depth limit to 0.
  2. DFS with Depth Limit: Perform a DFS, but only explore nodes up to the current depth limit. If a node’s depth exceeds the limit, backtrack without expanding it.
  3. Check for Goal: If the goal is found, return the solution.
  4. Increase Depth Limit: If the goal isn’t found, increment the depth limit by 1.
  5. Repeat: Restart DFS with the new depth limit, exploring deeper nodes. Continue until the goal is found or the search space is exhausted.


Key Properties

  • Completeness: IDS is complete (will find a solution if one exists) in finite search spaces, assuming the branching factor is finite.
  • Optimality: IDS is optimal for unweighted graphs (i.e., it finds the shortest path to the goal), like BFS, because it explores nodes level by level.
  • Time Complexity: O(b^d), where b is the branching factor and d is the depth of the shallowest goal. While IDS re-explores nodes at each iteration, the overhead is manageable because deeper levels dominate the search cost.
  • Space Complexity: O(b*d), similar to DFS, as it only stores the current path and a small amount of state. This makes IDS memory-efficient compared to BFS, which has O(b^d) space complexity.
  • Trade-off: IDS sacrifices some time efficiency (due to re-exploring nodes) for low memory usage and guaranteed optimality in unweighted graphs.

Pseudo-code Example:
IterativeDeepeningSearch(root, goal)
    for depth = 0 to ∞ do
        result = DepthLimitedSearch(root, goal, depth)
        if result == found then
            return result​


Implementing Iterative Deepening Search for Complex Robot Navigation


Step 1: Import Required Libraries

We begin by importing the necessary Python libraries. We use matplotlib to visualize the grid and path, and numpy to work with the grid as a numerical array.
import matplotlib.pyplot as plt
import numpy as np​

Step 2: Define Movement Directions

We define the possible movement directions for the robot. The robot can move in four directions: up, down, left, and right. These are represented as tuples of (x, y) coordinate changes.
# Define directions for robot movement (up, down, left, right)
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]​

Step 3: Define a Function to Check Validity of a Move

The is_valid function checks if the next position in the grid is within bounds and not an obstacle. It returns True if the move is valid, otherwise False.
# Utility to check if a position is within bounds and not an obstacle
def is_valid(grid, position):
    x, y = position
    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] != 1:
        return True
    return False​

Step 4: Implement the Iterative Deepening Depth-First Search (IDDFS) Algorithm

The iddfs function performs the search. It uses a helper function dls (Depth-Limited Search) to explore the grid up to a specified depth and returns the path if the goal is found.
# Iterative Deepening Depth-First Search (IDDFS) Implementation
def iddfs(grid, start, goal):
    def dls(node, depth, path):
        if node == goal:
            return path
        if depth == 0:
            return None
        for direction in DIRECTIONS:
            new_x, new_y = node[0] + direction[0], node[1] + direction[1]
            next_node = (new_x, new_y)
            if is_valid(grid, next_node) and next_node not in path:
                result = dls(next_node, depth - 1, path + [next_node])
                if result:
                    return result
        return None

    depth = 0
    while True:
        result = dls(start, depth, [start])
        if result:
            return result
        depth += 1​

Step 5: Define the Grid with Obstacles

We create a grid where 0 represents an open path and 1 represents obstacles. The grid is more complex, which makes it a challenging navigation problem for the robot.
# Create a more complex grid (0: open space, 1: obstacle)
grid = [
    [0, 0, 1, 0, 1, 1, 0, 0, 1, 0],
    [1, 0, 1, 0, 1, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
    [1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 0, 1, 1, 1, 0, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 0]
]

start = (0, 0)  # Starting position of the robot
goal = (9, 9)   # Goal position​

Step 6: Perform the Search to Find the Path

We now call the iddfs function to perform the search from the start position to the goal position and print the found path.
# Perform IDDFS
path = iddfs(grid, start, goal)
print("Path found:", path)​

Step 7: Visualize the Path

Finally, we create a function visualize_path that uses matplotlib to visualize the grid and the robot's path. The path is drawn in red, the start position is marked in green, and the goal position is marked in blue.
# Visualization Code
def visualize_path(grid, path):
    grid_size = (len(grid), len(grid[0]))
    grid_visual = np.array(grid)
    
    # Plot grid with obstacles
    plt.imshow(grid_visual, cmap='binary', origin='upper')

    # Highlight the path with a red line
    path_x = [x for x, y in path]
    path_y = [y for x, y in path]
    plt.plot(path_y, path_x, color='red', linewidth=2, marker='o')

    # Mark start and goal
    plt.text(start[1], start[0], 'S', fontsize=12, ha='center', va='center', color='green', fontweight='bold')
    plt.text(goal[1], goal[0], 'G', fontsize=12, ha='center', va='center', color='blue', fontweight='bold')

    # Grid labels and layout
    plt.grid(True)
    plt.xticks(range(grid_size[1]))
    plt.yticks(range(grid_size[0]))
    plt.gca().invert_yaxis()  # To align origin at top-left corner like a typical grid

    plt.title("Robot Navigation using Iterative Deepening Search (IDDFS)")
    plt.show()

# Visualize the result
visualize_path(grid, path)​

Complete Code: Implementing Iterative Deepening Search for Complex Robot Navigation

import matplotlib.pyplot as plt
import numpy as np

# Define directions for robot movement (up, down, left, right)
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# Utility to check if a position is within bounds and not an obstacle
def is_valid(grid, position):
    x, y = position
    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] != 1:
        return True
    return False

# Iterative Deepening Depth-First Search (IDDFS) Implementation
def iddfs(grid, start, goal):
    def dls(node, depth, path):
        if node == goal:
            return path
        if depth == 0:
            return None
        for direction in DIRECTIONS:
            new_x, new_y = node[0] + direction[0], node[1] + direction[1]
            next_node = (new_x, new_y)
            if is_valid(grid, next_node) and next_node not in path:
                result = dls(next_node, depth - 1, path + [next_node])
                if result:
                    return result
        return None

    depth = 0
    while True:
        result = dls(start, depth, [start])
        if result:
            return result
        depth += 1

# Create a more complex grid (0: open space, 1: obstacle)
grid = [
    [0, 0, 1, 0, 1, 1, 0, 0, 1, 0],
    [1, 0, 1, 0, 1, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
    [1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 0, 1, 1, 1, 0, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 0]
]

start = (0, 0)  # Starting position of the robot
goal = (9, 9)   # Goal position

# Perform IDDFS
path = iddfs(grid, start, goal)
print("Path found:", path)

# Visualization Code
def visualize_path(grid, path):
    grid_size = (len(grid), len(grid[0]))
    grid_visual = np.array(grid)
    
    # Plot grid with obstacles
    plt.imshow(grid_visual, cmap='binary', origin='upper')

    # Highlight the path with a red line
    path_x = [x for x, y in path]
    path_y = [y for x, y in path]
    plt.plot(path_y, path_x, color='red', linewidth=2, marker='o')

    # Mark start and goal
    plt.text(start[1], start[0], 'S', fontsize=12, ha='center', va='center', color='green', fontweight='bold')
    plt.text(goal[1], goal[0], 'G', fontsize=12, ha='center', va='center', color='blue', fontweight='bold')

    # Grid labels and layout
    plt.grid(True)
    plt.xticks(range(grid_size[1]))
    plt.yticks(range(grid_size[0]))
    plt.gca().invert_yaxis()  # To align origin at top-left corner like a typical grid

    plt.title("Robot Navigation using Iterative Deepening Search (IDDFS)")
    plt.show()

# Visualize the result
visualize_path(grid, path)​


Output:
Path found: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 5), (4, 5), (4, 6), (4, 7), (5, 7), (6, 7), (6, 6), (7, 6), (8, 6), (8, 7), (8, 8), (8, 9), (9, 9)]​


Why Use Iterative Deepening Search?


IDS is designed to overcome the trade-offs between BFS and DFS. Here’s why it stands out:

* Space Efficiency: IDS requires only O(bd) space, where b is the branching factor and d is the depth of the goal node. This is because it uses DFS, which stores only the current path.

* Optimality: In uniform-cost or unweighted graphs, IDS guarantees finding the shortest path (minimum depth solution), similar to BFS.

* Completeness: If the search tree is finite, IDS guarantees that it will find the solution if one exists.


Advantages of Iterative Deepening Search

* Memory Efficiency: Since IDS utilizes DFS for each iteration, it consumes far less memory than BFS, making it suitable for problems with large search spaces.

* Optimality in Unweighted Graphs: IDS ensures finding the shallowest goal node, making it an optimal choice for certain types of problems.

* Complete Search: Like BFS, IDS ensures that if there is a solution, it will be found eventually, as long as the search space is finite.

* Effective for Deep Trees: In scenarios where the goal node lies deep within a large search tree, IDS efficiently finds the solution without excessive memory overhead.

Disadvantages of Iterative Deepening Search

* Recomputing Effort: A significant drawback is that IDS repeatedly re-explores the same nodes for increasing depth limits. For example, the root node is explored multiple times as the depth limit increases. This leads to redundant computations.

* Higher Time Complexity: Although the space complexity is low, the time complexity is higher than DFS or BFS. The time complexity of IDS is O(b^d), where b is the branching factor and d is the depth of the solution. The repeated exploration adds overhead to the total computational time.

* Inefficient for Weighted Graphs: IDS does not perform well with weighted graphs where the cost of traversing edges differs, as it focuses on uniform depth rather than path cost.

Use Cases of Iterative Deepening Search in AI


IDS is particularly useful in AI applications where both memory efficiency and finding the shortest solution path are crucial. Here are a few notable use cases:

* Game AI (Chess, Go): IDS is widely used in game AI where the search space is vast, and the solution depth is unpredictable. Game trees with millions of possible states are explored more efficiently using IDS.

* Pathfinding Algorithms: IDS can be employed in real-time pathfinding scenarios, especially in cases where the destination's depth in the search space is unknown, such as robot navigation.

* Search Engines: IDS can be applied in crawling strategies for search engines, where it’s essential to balance memory consumption while ensuring all relevant results are discovered.

* Puzzle Solving (e.g., 8-puzzle): In AI, solving puzzles where the optimal solution requires traversing multiple states can benefit from IDS, as it efficiently handles the exponential growth of possible states.