A-Star

A* Search

A* is a variant of informed beast-first search, which balances the cost accumulated thus far with the predicted cost.

Definition

A* Search is obtained from best-first search by choosing

where is the path-cost from root the , and is the heuristic cost-to-go estimate.

Analysis

Completeness

On infinite graphs with a finite branching factor and edge costs that are bounded by for some fixed , A* is guaranteed to terminate only if there exits a solution.

Admissibility

Definition (Admissible Heuristic)

A heuristic is admissible if it never overestimates the true cost-to-go, i.e. for all , where is the true minimal cost to a goal node starting in node .

When is admissible, A* is guaranteed to return an optimal solution (for nonnegative step costs), provided it terminates.

Caution

If an admissible but not consistent heuristic is being used, and an optimal solution is required, additional checks need to be done when generating nodes in the best-first search framework. When a node is generated, it may represent a state of a previously generated and/or expanded state, but it has a lower cost. To guarantee optimality, nodes in closed may need to be reopened.

Algorithm 13 Node Consideration during Generation

procedure Consider(node $n$)

if node $m$ with state $n\mathrm{.state}$ in CLOSED then

if $m\mathrm{.g} \le n\mathrm{.g}$ then

return // Previous expanded node is better

end if

remove $m$ from CLOSED

end if

if node $m$ with state $n\mathrm{.state}$ in OPEN then

if $m\mathrm{.g} \le n\mathrm{.g}$ then

return // Previous generated node is better

end if

remove $m$ from OPEN

end if

add $n$ to OPEN

end procedure

Consistency

Definition (Consistent Heuristic)

A heuristic is consistent (or monotone) if for all goal nodes , and for every node and its child , where is the transition cost for transitioning from to .

When is consistent, A* only expands nodes it has found an optimal path to, thus never needing to reopen a closed node.

Complexity

The performance of A* is heavily influenced by the quality of the heuristic. In the worst case, A* expands all nodes for which where is the cost of the optimal goal node.

Implementation

template <typename Env>
struct AStarNode {
    auto compute_heuristic(const Node ) -> double;
    
    auto generate_child(int action) -> BFSNode {
        auto child = *this;
        child.parent = this;
        auto step_cost = child.state.apply_action(action);
        child.g += step_cost;
        child.h = compute_heuristic(child);
        return child;
    }
 
    Env state;
    BFSNode *parent = nullptr;
    double g = 0;
    double h = 0;
    double cost = 0;
    int generated_step = 0;
    int expanded_step = 0;
};
 
template <typename Env>
auto astar_eval_func(const AStarNode<Env> &node) -> double {
    return node.g + node.h;
}
 
template <typename Env>
auto astar(Env initial_state) {
    AStarNode root_node = {
        .state=initial_state, 
        .parent=nullptr,
        .g=0,
        .h=0
    }
    return best_first_search(root_node, astar_eval_func);
}