Draft:Iterative Budgeted Exponential Search

Iterative Budgeted Exponential Search

Class	Search algorithm
Data structure	Tree, Graph
Worst-case performance	${\mathcal {O}}(n\log C^{*})$, where $C^{*}$ is the optimal solution cost
Worst-case space complexity	${\mathcal {O}}(d)$

Iterative Budgeted Exponential Search (IBEX) is a framework for heuristic search algorithms that addresses two long-standing efficiency problems in artificial intelligence search: re-expansions in graph search with inconsistent heuristics and inefficient tree search with linear memory requirements. IBEX combines principles from exponential search with controlled node expansion budgets to achieve near-linear performance in scenarios where traditional algorithms like A* and IDA* can have quadratic or worse performance.

Background

Traditional heuristic search algorithms — A* for graph search and IDA* (Iterative Deepening A*) for tree search — face specific efficiency challenges:

• Graph search with inconsistent heuristics: While A* with consistent heuristics is optimally efficient, it may perform exponentially more state expansions ($\Omega (2^{n})$) with inconsistent heuristics compared to more cautious algorithms.
• Tree search with linear memory: IDA* uses iterative deepening with f-cost bounds to achieve linear memory usage, but in worst-case scenarios where only one new node is added per iteration, it may require $\Omega (n^{2})$ node expansions, resulting in quadratic overhead.

IBEX mitigates these issues by managing node expansions with controlled budgets and carefully increasing cost limits, thus achieving near-linear expansions relative to the number of nodes within the optimal cost bound.

Core Concepts

IBEX introduces two key ideas to improve heuristic search efficiency:

1. Expansion budgeting: IBEX limits the number of node expansions in each search iteration to control computational resources.
2. Exponential search for f-cost limits: It uses a variant of exponential search to efficiently find appropriate f-cost limits that allow exhaustive search within the given expansion budget.

This combination allows IBEX to prove either that no solution exists within the current budget (prompting a budget increase) or that it has found an optimal solution. The framework increases the budget exponentially between iterations, ensuring that the final budget is at most twice the minimum required budget while amortizing the work done in earlier iterations.

Algorithm

The following pseudocode describes the core IBEX framework:

IBEX Framework Pseudocode

function IBEX(initialState, goalTest, heuristic, successors, initialBudget, growthFactor)
    // Initialize parameters
    budget ← initialBudget
    minF ← heuristic(initialState)
    maxF ← minF
    solution ← null
    
    while solution = null do
        // Phase 1: IDA*-like search with current bound
        result ← SearchWithinBound(initialState, goalTest, heuristic, successors, minF, budget)
        
        if result.type = "SOLUTION_FOUND" then
            solution ← result.solution
            break
        
        if result.type = "BUDGET_EXHAUSTED" then
            // Phase 2: Exponential search to find appropriate cost limit
            lowerF ← minF
            upperF ← maxF
            
            // Double the f-cost limit until we exceed budget
            while true do
                maxF ← max(maxF * 2, lowerF + 1)
                result ← SearchWithinBound(initialState, goalTest, heuristic, successors, maxF, budget)
                
                if result.type = "SOLUTION_FOUND" then
                    solution ← result.solution
                    break
                
                if result.type = "COMPLETE" then
                    // Search was complete under maxF, but no solution found
                    return "NO_SOLUTION"
                
                if result.type = "BUDGET_EXHAUSTED" then
                    upperF ← maxF
                    break
            
            if solution ≠ null then
                break
            
            // Phase 3: Binary search to find precise cost limit
            while upperF - lowerF > 1 do
                midF ← (lowerF + upperF) / 2
                result ← SearchWithinBound(initialState, goalTest, heuristic, successors, midF, budget)
                
                if result.type = "SOLUTION_FOUND" then
                    solution ← result.solution
                    break
                
                if result.type = "COMPLETE" then
                    lowerF ← midF
                else // BUDGET_EXHAUSTED
                    upperF ← midF
            
            if solution ≠ null then
                break
        
        // Increase budget for next iteration
        minF ← result.nextF
        budget ← budget * growthFactor
    
    return solution

function SearchWithinBound(initialState, goalTest, heuristic, successors, fLimit, budget)
    // Initialize search structures
    expansions ← 0
    openList ← PriorityQueue()
    openList.insert(initialState, heuristic(initialState))
    
    nextF ← ∞  // Will track minimum f-value exceeding fLimit
    
    while not openList.isEmpty() and expansions < budget do
        node ← openList.pop()
        
        if goalTest(node) then
            return {type: "SOLUTION_FOUND", solution: extractPath(node)}
        
        expansions ← expansions + 1
        
        for each child in successors(node) do
            childF ← g(child) + heuristic(child)
            
            if childF <= fLimit then
                openList.insert(child, childF)
            else
                nextF ← min(nextF, childF)
        
    if openList.isEmpty() then
        return {type: "COMPLETE"}
    else
        return {type: "BUDGET_EXHAUSTED", nextF: nextF}

Algorithm Details

IBEX operates by controlling two parameters iteratively:

1. Expansion Budget: Limits the number of node expansions per iteration.
2. Solution Cost Limit: Limits the maximum allowable path cost explored during search iterations.

The IBEX algorithm comprises three key phases:

Initial IDA*-like Phase

The initial phase performs iterations similarly to IDA*, incrementing the f-cost minimally. If node expansions exceed a predefined growth threshold, IBEX continues directly into the next iteration, ensuring minimal overhead in exponentially growing domains.

Exponential Search Phase

If the tree growth is sub-exponential, IBEX initiates an exponential search phase. In this phase, the algorithm exponentially increases the cost limit until reaching the node expansion budget, ensuring the growth rate is bounded within a specified exponential factor.

Binary Search Phase

After the exponential search phase, if no suitable cost limit is found, IBEX performs a binary search to precisely identify a cost limit within the node expansion budget.

Variants and Enhancements

Two primary variants of IBEX have been developed:

• Budgeted Tree Search (BTS): Optimized for tree search scenarios, significantly reducing the re-expansion overhead typical of IDA*.
• Budgeted Graph Search (BGS): A graph search variant, addressing inefficiencies caused by inconsistent heuristics in traditional graph search algorithms like A*.

Enhancements to IBEX include:

• Early stopping conditions to skip unnecessary iterations.
• Additive exponential increments to efficiently handle linearly scaling search spaces.

Time Complexity

IBEX provides significant theoretical improvements over previous algorithms:

• Worst-case expansions are bounded by ${\mathcal {O}}(n\log {\frac {C^{*}}{\epsilon }})$ expansions, where $C^{*}$ is the optimal solution cost and $\epsilon$ is the granularity of action costs.
• Near-linear expansion guarantees, significantly improving upon quadratic complexities of classical algorithms.

Applications

IBEX has demonstrated superior performance in practical applications, including:

• Puzzle-solving (e.g., sliding-tile puzzles such as the 15-Puzzle).
• Optimal planning and pathfinding tasks with varying edge costs.
• Graph search problems with inconsistent heuristics.

See also

• A* search algorithm
• Iterative deepening A*
• Iterative deepening depth-first search
• Exponential search
• Heuristic (computer science)
• Pathfinding
• Binary search algorithm