Iterative Deepening A*

Iterative-Deepening A* (IDA) is a variant of the A algorithm. It controls the depth of the exploration by deepening its search iteratively by increasing the threshold of cost, thus, effectively solving the problem of space growth caused by A*.

IDA* builds upon the foundation of IDS (Iterative Deepening Search), integrating heuristic search into its framework. It cleverly leverages the iterative deepening feature of IDS, replacing depth-based operations with cost-based ones. The search begins with a maximum depth set to the heuristic value of the initial state and incrementally increases this limit, enabling a heuristic-guided search. ¹

Pseudocode for Iterative Deepening A* Algorithm

1. function IDAStar(graph, start, target):
2.     threshold = heuristic(start, target)  
3.     while true:
4.         result = DFS(start, target, 0, threshold)
5.         if result is not failure, return result
6.         threshold = result  
7. end function

8. function DFS(node, target, gScore, threshold):
9.     fScore = gScore + heuristic(node, target) 
10.     if fScore > threshold, return fScore 
11.     if node == target, return path to target 
12.     for each neighbor of node:
13.         if neighbor not in visited:
14.             visited.add(neighbor)
15.             result = DFS(neighbor, target, gScore + cost(node, neighbor), threshold)
16.             if result is not failure, return result
17.     return failure

Here also, the total estimated cost of traversal is represented by the function f(n) where n is the current node. For any n, it is calculated as:

\[ f(n)= g(n)+h(n) \]

Where g(n) and h(n) carry their usual meaning. The basic implementation of IDA* is as follows:

• Set the start state as the current node and calculate the value of the function f.
• Set the initial threshold based on this f-value.
• Work on the current node’s children and calculate their f-values.
• If f > threshold, prune the node and store it for future expansion.
• When the goal state is found, return the path from start state to goal state.
• If the goal state is not found, increase the threshold on the basis of minimum pruned value and repeat the process.

Iterative Deepening A* Algorithm Implementation

This snippet defines a helper function called heuristic, which calculates the Manhattan distance between two points. It is used to estimate the cost of reaching the target from a given node in grid-based pathfinding. The heuristic is based on the sum of the absolute differences in the x and y coordinates, making it ideal for grid-like environments where diagonal movement is not allowed.

# A helper function for calculating the Manhattan distance heuristic (h) between two points
def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

The idastar function implements the Iterative Deepening A* (IDA*) algorithm. It uses a recursive search method with a depth limit, which is initially set to the heuristic distance from the start to the target. In each iteration, the limit increases if no valid path is found. The search function explores neighboring nodes, keeping track of the current path and cost, and prunes paths that exceed the current limit.

# IDA* algorithm
def idastar(grid, start, target):
    # A helper function to perform the search with a given limit
    def search(node, g, path, limit):
        f = g + heuristic(node, target)  # Calculate f = g + h

        if f > limit:
            return f  # Return the f value if it's above the limit (prune this path)

        if node == target:
            return path  # Found the target, return the path

        min_f = float('inf')
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Possible moves: up, down, left, right
        
        # Explore neighbors
        for direction in directions:
            neighbor = (node[0] + direction[0], node[1] + direction[1])

            # Ensure the neighbor is within bounds of the grid
            if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]):
                # Skip already visited nodes in the current path (to avoid cycles)
                if neighbor not in path:
                    new_path = path + [neighbor]
                    result = search(neighbor, g + grid[neighbor[0]][neighbor[1]], new_path, limit)
                    if isinstance(result, list):  # If a valid path is returned
                        return result
                    min_f = min(min_f, result)  # Otherwise, update the minimum f value

        return min_f  # Return the minimum f value encountered during the search

    limit = heuristic(start, target)  # Start with the heuristic as the initial limit
    while True:
        result = search(start, 0, [start], limit)
        if isinstance(result, list):  # Found the path
            return result
        if result == float('inf'):  # No solution found within the current limit
            return []  # No solution exists
        limit = result  # Increase the limit and try again

This snippet demonstrates the application of the IDA* algorithm on a 4x4 grid, where each cell has a movement cost. The start point is at (0, 0) and the target is at (3, 3). The function idastar() is called to find the shortest path between the two points, and the resulting path is printed, showing the optimal route considering the grid’s costs and the IDA* algorithm’s iterative deepening approach.

# Example grid (cost to move through each cell)
grid = [
    [1, 2, 1, 10],
    [1, 2, 1, 1],
    [1, 1, 1, 1],
    [10, 1, 1, 1]
]

start_node = (0, 0)  # Top-left corner
target_node = (3, 3)  # Bottom-right corner
shortest_path = idastar(grid, start_node, target_node)

print("Shortest path from", start_node, "to", target_node, ":", shortest_path)

Shortest path from (0, 0) to (3, 3) : [(0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (3, 2), (3, 3)]

Footnotes

1. Jiang, W. (2021, March). Analysis of iterative deepening a* algorithm. In IOP Conference Series: Earth and Environmental Science (Vol. 693, No. 1, p. 012028). IOP Publishing. Link