In previous lessons you have seen discrete planning formulations, heuristic search, and lattice planners for robots with many degrees of freedom. In all of these, we ultimately search on a graph \( G = (V, E) \) whose nodes represent robot configurations or short kinematic motions, and whose edges encode feasible transitions with cost \( c:E → \mathbb{R}_{\ge 0} \).

For algorithm design and safety-critical reasoning, we need precise answers to:

• Will the planner find a solution whenever one exists? — search completeness.
• When the physical world is continuous, does the discrete planner converge as resolution improves? — resolution completeness.
• Is the returned path the best possible with respect to a cost functional? — optimality and bounded-suboptimality.

Let a planning problem be \( \mathcal{P} = (G, v_{\mathrm{start}}, V_{\mathrm{goal}}, c) \), where \( G = (V, E) \) is a directed graph, \( v_{\mathrm{start}} \in V \) is the start node, \( V_{\mathrm{goal}} \subseteq V \) is the set of goal nodes, and \( c:E → \mathbb{R}_{\ge 0} \) is a non-negative cost. For a path \( \pi = (v_0, \dots, v_k) \) with \( v_0 = v_{\mathrm{start}} \) and \( v_k \in V_{\mathrm{goal}} \), the path cost is

\[ J(\pi) = \sum_{i=0}^{k-1} c(v_i, v_{i+1}). \]

The optimal cost is

\[ J^{\star} = \inf \{ J(\pi) \;\vert\; \pi \text{ is a start-to-goal path in } G \}. \]

A planner's theoretical guarantees are then stated in terms of \( J^{\star} \) and the structure of \( G \).

flowchart TD
  P["High-DOF planning problem"] --> D["Discretize to graph or lattice"]
  D --> A1["Choose search algorithm"]
  A1 --> C1["Search completeness?"]
  A1 --> R1["Resolution completeness?"]
  A1 --> O1["Optimality / \nbounded-suboptimality?"]
  C1 --> OUT1["Guarantees about \nfinding a path"]
  R1 --> OUT2["Guarantees as grid \nresolution decreases"]
  O1 --> OUT3["Guarantees on path \ncost vs J*"]
        

Let \( \mathcal{C} \) be a class of planning problems (for example, all finite graphs with non-negative edge costs and finite branching). A graph search algorithm \( A \) is said to be search-complete for \( \mathcal{C} \) if:

\[ \forall \mathcal{P} \in \mathcal{C}: \begin{cases} \text{if a finite-cost solution path exists, then } \\ \quad A(\mathcal{P}) \text{ returns a solution after finitely many expansions}, \\ \text{if no solution path exists and the reachable subgraph is finite, then } \\ \quad A(\mathcal{P}) \text{ terminates with failure}. \end{cases} \]

Completeness depends on both the algorithm and the class \( \mathcal{C} \). For example, depth-first search (DFS) is complete on finite graphs but not on infinite graphs with cycles and unbounded depth.

We use the standard graph parameters:

• \( b \) — maximal branching factor.
• \( d \) — depth of the shallowest goal node.
• \( c_{\min} > 0 \) — minimal strictly positive edge cost.

For breadth-first search (BFS) on an unweighted graph (all edges have unit cost), the search tree is layered by distance. The number of nodes at depth \( k \) is at most \( b^k \), and the total number of generated nodes up to depth \( d \) is bounded by a finite geometric sum.

\[ N_{\mathrm{BFS}}(d) \le \sum_{k=0}^{d} b^k = \begin{cases} d + 1 & \text{if } b = 1, \\ \dfrac{b^{d+1} - 1}{b - 1} & \text{if } b \ne 1. \end{cases} \]

On finite graphs (and more generally, when the shallowest goal depth \( d \) is finite and \( b \) is finite), BFS expands a finite number of nodes before reaching depth \( d \). Hence BFS is complete for this class.

For weighted graphs we consider uniform-cost search (UCS), which is essentially Dijkstra's algorithm applied to the reachable subgraph from \( v_{\mathrm{start}} \). Assume:

• The branching factor \( b \) is finite.
• Every edge cost satisfies \( c(e) \ge c_{\min} > 0 \).
• For every goal node reachable from \( v_{\mathrm{start}} \), the optimal cost \( J^{\star} \) is finite.

UCS maintains an open set keyed by \( g(v) \) (cost from start). At each iteration it removes the node with minimal \( g \)-value.

Theorem (Completeness of UCS). Under the above assumptions, UCS is complete for this class of problems.

Proof (sketch).

1. Because \( c(e) \ge c_{\min} > 0 \), any path of cost at most \( J^{\star} \) has length at most \( \lfloor J^{\star} / c_{\min} \rfloor \).
2. The number of distinct simple paths of length at most this bound is finite when the branching factor is finite. Therefore there are only finitely many distinct nodes whose optimal \( g \)-values are at most \( J^{\star} \).
3. UCS always expands the unexpanded node with lowest \( g \)-value. Before it can expand any node whose optimal cost exceeds \( J^{\star} \), it must have already expanded all nodes whose optimal cost is at most \( J^{\star} \), including a goal node on an optimal path.

Hence a goal node on an optimal path is expanded after finitely many iterations, and UCS is complete. The same argument applies to Dijkstra on directed graphs with non-negative weights.

For UCS, optimality is straightforward: nodes are expanded in order of non-decreasing \( g \), so when a goal is removed from the open set, it has minimal cost among all goal nodes.

A* introduces a heuristic \( h:V → \mathbb{R}_{\ge 0} \) and uses the evaluation function

\[ f(v) = g(v) + h(v). \]

We say that \( h \) is admissible if it never overestimates the optimal cost-to-go:

\[ \forall v \in V: \quad h(v) \le J^{\star}(v), \]

where \( J^{\star}(v) \) denotes the optimal cost from \( v \) to any goal node.

We say that \( h \) is consistent (or monotone) if

\[ \forall (v, v') \in E: \quad h(v) \le c(v, v') + h(v'), \]

and \( h(v_{\mathrm{goal}}) = 0 \) for all goal nodes. Consistency implies that \( f \)-values are non-decreasing along any path, which in turn guarantees that nodes need not be re-opened once expanded.

Theorem (Optimality of A*). Assume that:

• Edge costs satisfy \( c(e) \ge c_{\min} > 0 \),
• The branching factor \( b \) is finite and \( J^{\star} \) is finite,
• Heuristic \( h \) is admissible.

Then the first goal node removed from the A* open set has cost \( J^{\star} \), i.e., the returned path is optimal.

Proof (standard argument).

1. Let \( v_{\mathrm{goal}}^{\star} \) be a goal node on an optimal path with cost \( J^{\star} \). Admissibility implies \( f(v_{\mathrm{goal}}^{\star}) = g(v_{\mathrm{goal}}^{\star}) + h(v_{\mathrm{goal}}^{\star}) \le J^{\star} \).
2. Suppose A* selects some goal node \( v_g \) with cost \( J(v_g) > J^{\star} \) before selecting \( v_{\mathrm{goal}}^{\star} \). At that moment, \( v_{\mathrm{goal}}^{\star} \) is either still in the open set or has not been generated yet. In both cases its current \( f \)-value satisfies \( f(v_{\mathrm{goal}}^{\star}) \le J^{\star} < J(v_g) = f(v_g) \).
3. Because A* always removes the node with smallest \( f \)-value, it cannot choose \( v_g \) with strictly larger \( f \) before \( v_{\mathrm{goal}}^{\star} \). This contradiction shows that the first goal removed must lie on an optimal path.

With consistent heuristics, the same proof applies and additionally guarantees that each node need only be expanded once, simplifying implementation and proofs about completeness.

In robotic motion planning, the true configuration space \( \mathcal{X} \) is often continuous: \( \mathcal{X} \subset \mathbb{R}^n \) for an \( n \)-DOF manipulator. Obstacles define the free space \( \mathcal{X}_{\mathrm{free}} \subset \mathcal{X} \). Lattice planners approximate \( \mathcal{X}_{\mathrm{free}} \) by a finite set of nodes (grid points or discrete poses) and edges (motion primitives).

Let \( \delta > 0 \) denote a resolution parameter (grid spacing or maximum length of a motion primitive). A planner is resolution-complete if:

\[ \text{For any fixed } \delta, \text{ if there exists a path in } \mathcal{X}_{ \mathrm{free} } \text{ that is representable on the } \delta\text{-lattice,} \\ \text{ then the planner finds a path after finitely many expansions.} \]

In other words, resolution completeness is search completeness applied to the discrete graph induced by a particular resolution. It does not guarantee that the discrete path is close to the truly optimal continuous path, but it guarantees that the discretization does not miss a path that is representable at that resolution.

Under additional regularity assumptions on \( \mathcal{X}_{\mathrm{free}} \) (e.g., mild clearance conditions), one can show that as \( \delta \rightarrow 0 \), the best discrete paths converge in cost to the optimal continuous path. This provides a bridge between graph-search guarantees and continuous-space motion planning.

flowchart TD
  CSPACE["Continuous free space X_free"] --> GRID["Discretized grid or lattice (delta)"]
  GRID --> GRAPH["Graph G_delta of nodes and edges"]
  GRAPH --> SEARCH["Run complete graph search (e.g. A* or BFS)"]
  SEARCH --> GUAR["Resolution-complete: if path exists in G_delta, it is found"]
        

Exact optimality may be too expensive in high-dimensional planning. Bounded-suboptimality relaxes the requirement: we accept a path whose cost is within a factor \( w \ge 1 \) of optimal:

\[ J(\pi_{\mathrm{alg}}) \le w \, J^{\star}. \]

Weighted A* uses the evaluation function

\[ f_w(v) = g(v) + w \, h(v), \]

where \( h \) is an admissible heuristic and \( w \ge 1 \) is a user-chosen inflation factor.

Theorem (Bounded-suboptimality of Weighted A*). Suppose \( h \) is admissible and edge costs satisfy \( c(e) \ge c_{\min} > 0 \). Then the solution returned by Weighted A* satisfies \( J(\pi_{\mathrm{WA*}}) \le w \, J^{\star} \).

Proof (sketch).

1. For any node \( v \) on an optimal path, admissibility implies \( h(v) \le J^{\star}(v) \), so \( f_w(v) = g(v) + w h(v) \le g(v) + w J^{\star}(v) \le w J^{\star} \).
2. When Weighted A* terminates, it has chosen a goal node \( v_g \) whose \( f_w \) satisfies \( f_w(v_g) = g(v_g) \) (since \( h(v_g) = 0 \)). All nodes remaining in the open set have \( f_w \ge f_w(v_g) \).
3. In particular, every node on an optimal path must have \( f_w \ge f_w(v_g) \). From step (1), all nodes on an optimal path have \( f_w \le w J^{\star} \). Hence \( g(v_g) = f_w(v_g) \le w J^{\star} \).

Weighted A* is generally no longer optimal (\( w > 1 \)), but its search efforts are focused in a smaller region, making it attractive for large high-DOF planning problems where a small suboptimality factor is acceptable.

On a tree of branching factor \( b \) and goal depth \( d \), BFS explores \( \mathcal{O}(b^d) \) nodes in the worst case (both time and space). UCS and A* have similar asymptotic complexity in the worst case because they may need to expand all nodes with \( f(v) \le J^{\star} \).

The effective complexity of A* depends strongly on heuristic quality. A heuristic \( h_1 \) is said to be more informed than \( h_2 \) if

\[ \forall v \in V: \quad h_1(v) \ge h_2(v), \]

while both remain admissible. In this case A* with \( h_1 \) expands no more nodes than with \( h_2 \), a useful design principle for high-DOF planning: more accurate admissible heuristics reduce the effective search space without sacrificing optimality.

For high-DOF manipulators, the branching factor and depth are heavily influenced by lattice structure and motion primitive design (previous lesson). Completeness and optimality theorems remain valid as long as the discrete graph assumptions (finite branching, positive costs) hold.

The following Python implementation of A* is complete and optimal on finite graphs with non-negative edge costs and an admissible (optionally consistent) heuristic. The graph is given by successor and cost callback functions so that the same code can be used for grid worlds, joint-space lattices, and graph abstractions of high-DOF manipulators.

import heapq
from typing import Any, Callable, Dict, Iterable, List, Optional, Tuple, Set

State = Any
Cost = float

def astar(
    start: State,
    is_goal: Callable[[State], bool],
    successors: Callable[[State], Iterable[Tuple[State, Cost]]],
    heuristic: Callable[[State], Cost],
) -> Optional[List[State]]:
    """
    A* search with admissible heuristic.

    Args:
        start: initial state (node in the graph).
        is_goal: predicate to test whether a state is goal.
        successors: function mapping state -> iterable of (next_state, edge_cost).
        heuristic: admissible heuristic h(x) estimating remaining cost.

    Returns:
        A list of states from start to a goal if found, otherwise None.
    """
    # g-values: known best cost to reach each state
    g: Dict[State, Cost] = {start: 0.0}
    parent: Dict[State, Optional[State]] = {start: None}

    counter = 0  # tie-breaker to keep heapq stable
    open_heap: List[Tuple[Cost, int, State]] = []
    heapq.heappush(open_heap, (heuristic(start), counter, start))

    closed: Set[State] = set()

    while open_heap:
        f, _, s = heapq.heappop(open_heap)
        if s in closed:
            continue
        closed.add(s)

        if is_goal(s):
            # reconstruct path
            path: List[State] = []
            cur: Optional[State] = s
            while cur is not None:
                path.append(cur)
                cur = parent[cur]
            path.reverse()
            return path

        g_s = g[s]
        for s_next, c in successors(s):
            if c < 0.0:
                raise ValueError("Edge cost must be non-negative for A* guarantees.")
            new_g = g_s + c
            if s_next not in g or new_g < g[s_next]:
                g[s_next] = new_g
                parent[s_next] = s
                counter += 1
                f_next = new_g + heuristic(s_next)
                heapq.heappush(open_heap, (f_next, counter, s_next))

    return None

# Example: 2D grid with 4-connected moves
def grid_successors(pos):
    x, y = pos
    steps = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for dx, dy in steps:
        nxt = (x + dx, y + dy)
        # Here we could check obstacles or bounds
        yield nxt, 1.0

def manhattan_heuristic(goal):
    gx, gy = goal
    def h(state):
        x, y = state
        return abs(x - gx) + abs(y - gy)
    return h

if __name__ == "__main__":
    start = (0, 0)
    goal = (5, 7)
    h = manhattan_heuristic(goal)
    path = astar(start, lambda s: s == goal, grid_successors, h)
    print("Path:", path)
      

In a manipulator lattice planner, the State would be a joint configuration vector and grid_successors would enumerate feasible motion primitives. As long as all edge costs are non-negative and the heuristic is admissible, this implementation is complete and optimal on the discrete graph.

The C++ skeleton below follows the same structure using std::priority_queue. It assumes that a State type and a successors function exist, compatible with your manipulator or mobile base representation.

#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <functional>
#include <limits>

struct StateHash {
    std::size_t operator()(const State& s) const noexcept {
        // Provide a proper hash for your State type
        return s.hash();
    }
};

struct StateEqual {
    bool operator()(const State& a, const State& b) const noexcept {
        return a == b;
    }
};

struct Node {
    State s;
    double f;
    double g;
};

struct NodeCompare {
    bool operator()(const Node& a, const Node& b) const noexcept {
        // priority_queue in C++ is max-heap by default, so invert comparison
        return a.f > b.f;
    }
};

std::vector<State> reconstruct_path(
    const State& goal,
    const std::unordered_map<State, State, StateHash, StateEqual>& parent)
{
    std::vector<State> path;
    State cur = goal;
    auto it = parent.find(cur);
    while (it != parent.end()) {
        path.push_back(cur);
        auto it2 = parent.find(cur);
        if (it2 == parent.end() || it2->second == cur) {
            break;
        }
        cur = it2->second;
    }
    std::reverse(path.begin(), path.end());
    return path;
}

template <typename SuccessorFunc, typename HeuristicFunc, typename GoalPredicate>
bool astar(
    const State& start,
    GoalPredicate is_goal,
    SuccessorFunc successors,
    HeuristicFunc heuristic,
    std::vector<State>& out_path)
{
    using Map = std::unordered_map<State, double, StateHash, StateEqual>;
    using ParentMap = std::unordered_map<State, State, StateHash, StateEqual>;

    Map g;
    ParentMap parent;
    g[start] = 0.0;
    parent[start] = start;

    std::priority_queue<Node, std::vector<Node>, NodeCompare> open;
    open.push(Node{start, heuristic(start), 0.0});
    std::unordered_set<State, StateHash, StateEqual> closed;

    while (!open.empty()) {
        Node cur = open.top();
        open.pop();

        if (closed.find(cur.s) != closed.end()) {
            continue;
        }
        closed.insert(cur.s);

        if (is_goal(cur.s)) {
            out_path = reconstruct_path(cur.s, parent);
            return true;
        }

        double g_s = g[cur.s];
        for (const auto& [s_next, cost] : successors(cur.s)) {
            if (cost < 0.0) {
                throw std::runtime_error("Negative edge cost not allowed");
            }
            double new_g = g_s + cost;
            auto it = g.find(s_next);
            if (it == g.end() || new_g < it->second) {
                g[s_next] = new_g;
                parent[s_next] = cur.s;
                double f_next = new_g + heuristic(s_next);
                open.push(Node{s_next, f_next, new_g});
            }
        }
    }
    return false; // no solution
}
      

This implementation preserves the same completeness and optimality guarantees as the Python version, provided the assumptions on edge costs, branching factor, and heuristic admissibility are satisfied by the underlying robot-specific graph.

Below is a Java-style implementation using PriorityQueue and a generic State type (you may replace it with a specific configuration or node class for your robot).

import java.util.*;
import java.util.function.Function;
import java.util.function.Predicate;

public class AStar<State> {

    public interface SuccessorFunction<State> {
        List<Transition<State>> successors(State s);
    }

    public static class Transition<State> {
        public final State next;
        public final double cost;
        public Transition(State next, double cost) {
            this.next = next;
            this.cost = cost;
        }
    }

    private static class Node<State> {
        State state;
        double g;
        double f;
        Node(State s, double g, double f) {
            this.state = s;
            this.g = g;
            this.f = f;
        }
    }

    public List<State> search(
            State start,
            Predicate<State> isGoal,
            SuccessorFunction<State> successors,
            Function<State, Double> heuristic) {

        Map<State, Double> g = new HashMap<>();
        Map<State, State> parent = new HashMap<>();
        g.put(start, 0.0);
        parent.put(start, null);

        PriorityQueue<Node<State>> open = new PriorityQueue<>(
            Comparator.comparingDouble(n -> n.f)
        );
        open.add(new Node<>(start, 0.0, heuristic.apply(start)));

        Set<State> closed = new HashSet<>();

        while (!open.isEmpty()) {
            Node<State> cur = open.poll();
            State s = cur.state;
            if (closed.contains(s)) continue;
            closed.add(s);

            if (isGoal.test(s)) {
                return reconstructPath(s, parent);
            }

            double g_s = g.get(s);
            for (Transition<State> tr : successors.successors(s)) {
                if (tr.cost < 0.0) {
                    throw new IllegalArgumentException("Negative edge costs not allowed");
                }
                double newG = g_s + tr.cost;
                Double oldG = g.get(tr.next);
                if (oldG == null || newG < oldG) {
                    g.put(tr.next, newG);
                    parent.put(tr.next, s);
                    double f = newG + heuristic.apply(tr.next);
                    open.add(new Node<>(tr.next, newG, f));
                }
            }
        }
        return null; // failure
    }

    private List<State> reconstructPath(State goal, Map<State, State> parent) {
        List<State> path = new ArrayList<>();
        State cur = goal;
        while (cur != null) {
            path.add(cur);
            cur = parent.get(cur);
        }
        Collections.reverse(path);
        return path;
    }
}
      

As in the other implementations, assuming non-negative edge costs and an admissible heuristic, this Java A* is complete and optimal on finite graphs.

MATLAB is widely used in control and robotics. The following script implements a basic A* search over a 2D grid. For manipulator planning, you can replace the grid state with joint vectors and compute collision checks inside successorsAStar.

function path = astar_grid(start, goal, isFree)
% A* on a 2D grid with 4-connected moves.
% start, goal: [x; y]
% isFree(x, y): function handle returning true if cell is free

    start = start(:).';
    goal  = goal(:).';

    g = containers.Map();
    parent = containers.Map();
    keyStart = key(start);
    g(keyStart) = 0.0;
    parent(keyStart) = '';

    % open list: [f, x, y]
    open = [heuristic(start, goal), start];
    closed = containers.Map();

    while ~isempty(open)
        % pop node with minimal f
        [~, idx] = min(open(:,1));
        node = open(idx,:);
        open(idx,:) = [];

        s = node(2:3);
        k = key(s);
        if isKey(closed, k)
            continue;
        end
        closed(k) = true;

        if isequal(s, goal)
            path = reconstruct_path(parent, s);
            return;
        end

        g_s = g(k);
        nbrs = successorsAStar(s);
        for i = 1:size(nbrs,1)
            sn = nbrs(i,:);
            if ~isFree(sn(1), sn(2))
                continue;
            end
            kn = key(sn);
            c = 1.0; % uniform edge cost
            new_g = g_s + c;
            if ~isKey(g, kn) || new_g < g(kn)
                g(kn) = new_g;
                parent(kn) = k;
                f = new_g + heuristic(sn, goal);
                open = [open; f, sn];
            end
        end
    end

    path = []; % no solution
end

function h = heuristic(s, goal)
    dx = abs(s(1) - goal(1));
    dy = abs(s(2) - goal(2));
    h = dx + dy; % Manhattan distance
end

function nbrs = successorsAStar(s)
    steps = [1 0; -1 0; 0 1; 0 -1];
    nbrs = bsxfun(@plus, steps, s);
end

function k = key(s)
    k = sprintf('%d_%d', s(1), s(2));
end

function path = reconstruct_path(parent, s)
    seq = s;
    k = key(s);
    while parent.isKey(k) && ~isempty(parent(k))
        k = parent(k);
        tokens = sscanf(k, '%d_%d');
        seq = [tokens.'; seq];
    end
    path = seq;
end
      

In Simulink, one can encapsulate the A* update step inside a MATLAB Function block, with the open list, parent map, and cost arrays stored in persistent variables. Each simulation step would perform a bounded number of expansions, allowing you to couple search with continuous-time plant models.

Mathematica provides symbolic and numeric tools that are convenient for prototyping planners, particularly when you want to reason about cost functions analytically and verify properties like admissibility.

Clear[AStarSearch]

AStarSearch[start_, goalQ_, successors_, h_] := Module[
  {g, f, parent, open, closed, current, s, sNext, c, newG},
  
  g = <| start -> 0.0 |>;
  parent = <| start -> None |>;
  f = <| start -> h[start] |>;
  
  open = {start};
  closed = <||>;
  
  While[open =!= {},
    (* pick node with minimal f *)
    current = First@SortBy[open, f[#] &];
    open = DeleteCases[open, current];
    s = current;
    
    If[KeyExistsQ[closed, s], Continue[]];
    closed[s] = True;
    
    If[goalQ[s],
      (* reconstruct path *)
      Return[
        Reverse@FixedPointList[
          If[parent[#] === None, #, parent[#]] &,
          s
        ]
      ];
    ];
    
    Do[
      {sNext, c} = sn;
      If[c < 0, Return[$Failed]];
      newG = g[s] + c;
      If[!KeyExistsQ[g, sNext] || newG < g[sNext],
        g[sNext] = newG;
        parent[sNext] = s;
        f[sNext] = newG + h[sNext];
        If[!MemberQ[open, sNext], AppendTo[open, sNext]];
      ],
      {sn, successors[s]}
    ];
  ];
  $Failed
]

(* Example: grid world with admissible heuristic *)
Clear[gridSuccessors, manhattanH]
gridSuccessors[{x_, y_}] := Module[{steps, nbrs},
  steps = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
  nbrs = ({x, y} + #) & /@ steps;
  Thread[{nbrs, ConstantArray[1.0, Length[nbrs]]}]
]

manhattanH[goal_] := Function[{s}, Total@Abs[s - goal]]

start = {0, 0};
goal = {5, 7};
path = AStarSearch[start, (# === goal) &, gridSuccessors, manhattanH[goal]];
Print[path];
      

With symbolic reasoning, you can for example prove that manhattanH is admissible for a grid with unit edge costs by checking that it underestimates all analytically derived shortest-path distances on the grid graph.

Problem 1 (Completeness of BFS): Consider a finite directed graph with maximal branching factor \( b \), and suppose a goal node exists at depth \( d \) from the start. Prove rigorously that breadth-first search is complete on this class of problems.

Solution.

At depth \( k \) in the BFS tree, there are at most \( b^k \) nodes. Summed over all depths \( 0, \dots, d \), we obtain the finite upper bound

\[ N_{\mathrm{BFS}}(d) \le \sum_{k=0}^{d} b^k = \begin{cases} d + 1 & \text{if } b = 1, \\ \dfrac{b^{d+1} - 1}{b - 1} & \text{if } b \ne 1. \end{cases} \]

BFS expands nodes in non-decreasing order of depth. Hence, before expanding any node at depth \( d + 1 \), it must have exhausted all nodes at depths up to \( d \). Because a goal exists at depth \( d \), BFS will encounter a goal after at most \( N_{\mathrm{BFS}}(d) \) expansions. Therefore BFS is complete for this class.

Problem 2 (Non-completeness of DFS on Infinite Graphs): Construct an example of a graph with finite branching factor and a reachable goal such that depth-first search is not complete. Explain why DFS fails.

Solution.

Consider a root node with two children: left and right. The left child leads to an infinite chain with no goal; the right child leads to a goal at depth 1 (one step from the root). Depth-first search that always visits the left child first will descend the infinite left branch and never backtrack to the right child. Thus, even though a goal exists, DFS never finds it and is not complete on this class of infinite graphs.

Problem 3 (Inconsistent Heuristic and Re-expansions): Provide an example of a small graph and a heuristic function that is admissible but inconsistent. Show that A* must re-expand at least one node to preserve optimality.

Solution.

Consider three nodes: start \( s \), intermediate \( u \), and goal \( g \), with edges: \( s \rightarrow g \) of cost \( 10 \) and \( s \rightarrow u \rightarrow g \) with each edge cost \( 4 \). Hence \( J^{\star} = 8 \).

Define heuristic values \( h(g) = 0 \), \( h(u) = 2 \), \( h(s) = 7 \). This heuristic is admissible because:

• \( h(g) = 0 \le 0 = J^{\star}(g) \),
• \( h(u) = 2 \le 4 = J^{\star}(u) \),
• \( h(s) = 7 \le 8 = J^{\star}(s) \).

However, it is inconsistent because \( h(s) = 7 \not\le 4 + h(u) = 6 \). A* may first expand \( s \), then generate \( g \) directly with \( f(g) = 10 \) and \( u \) with \( f(u) = g(u) + h(u) = 4 + 2 = 6 \). After expanding \( u \), it discovers the cheaper path to \( g \) of cost \( 8 \). To maintain optimality, it must effectively reconsider \( g \) with a reduced \( f \)-value. This behaviour can be phrased as re-expanding or updating nodes already seen, showing that inconsistent heuristics may require re-expansions to preserve optimality.

Problem 4 (Bound on Weighted A* Suboptimality): Complete the missing details in the proof that Weighted A* with inflation factor \( w \ge 1 \) and admissible heuristic returns a solution with \( J(\pi) \le w J^{\star} \).

Solution.

Let \( v_{\mathrm{goal}}^{\star} \) be a goal on an optimal path. For any node \( v \) on this path, admissibility implies \( h(v) \le J^{\star}(v) \), hence \( f_w(v) = g(v) + w h(v) \le g(v) + w J^{\star}(v) \le w J^{\star} \). Thus all nodes on the optimal path have \( f_w \le w J^{\star} \).

Let \( v_g \) be the goal node returned by Weighted A*. Because all remaining nodes in the open list have \( f_w \ge f_w(v_g) = g(v_g) \), we must have

\[ g(v_g) \le w J^{\star}, \]

otherwise some node on the optimal path with \( f_w \le w J^{\star} \) would have been preferred by the priority queue. Therefore the returned solution cost \( J(\pi) = g(v_g) \) is bounded by \( w J^{\star} \).

Problem 5 (Resolution Completeness in a 2D Grid): Let \( \mathcal{X}_{\mathrm{free}} \subset \mathbb{R}^2 \) be a polygonal environment with obstacles that are closed sets. Consider a uniform grid with spacing \( \delta > 0 \) and 4-connected edges. Assume there exists a continuous path from start to goal that remains at least clearance \( \varepsilon > 0 \) away from obstacles. Show that if \( \delta \le \varepsilon / 2 \), then there exists a collision-free path on the grid connecting discrete start and goal nodes, and that BFS or A* will find it (resolution completeness).

Solution.

The clearance condition ensures that an open tube of radius \( \varepsilon \) around the continuous path lies entirely in \( \mathcal{X}_{\mathrm{free}} \). When \( \delta \le \varepsilon / 2 \), every grid point within distance \( \delta \) of the path is also at distance at least \( \varepsilon - \delta \ge \varepsilon / 2 > 0 \) from obstacles, hence collision-free.

By approximating the continuous path with a sequence of neighbouring grid cells whose centers lie inside this tube, we obtain a discrete start-to-goal path on the grid that is collision-free. This path is representable in the discrete graph induced by the grid and 4-connected edges. BFS or A*, being complete on finite graphs, will eventually find such a path. Therefore the planner is resolution-complete under these conditions.

In this lesson we formalized search completeness, resolution completeness, optimality, and bounded-suboptimality for graph search in high-DOF robotic planning. We proved completeness and optimality properties of BFS, UCS, and A*, and characterized how admissible and consistent heuristics affect guarantees. We also introduced weighted A* and its suboptimality bound, and linked these notions to discretized configuration-space lattices. Multi-language implementations illustrated how to realize theoretically sound planners for manipulators and mobile robots in practice.

These notions underpin the analysis of sampling-based planners in the next chapter, where completeness becomes probabilistic or asymptotic optimality rather than deterministic search completeness.