Autonomous Motion Planning: Comparing A* Grid Search with Continuous RRT

Autonomous Motion Planning: Comparing A* Grid Search with Continuous RRT

When developing autonomous delivery rovers, drones, or automated logistics carts for Kone Warp, navigation is divided into two primary tiers:

1. Global Planning: Finding the shortest collision-free topological path across known city streets or warehouse maps.
2. Local Motion Planning: Steering safely through continuous space around dynamic obstacles (pedestrians, vehicles, unexpected roadblocks) while adhering to non-holonomic vehicle kinematics.

Two foundational algorithmic families dominate this domain: Discrete Heuristic Search ($A^*$) and Sampling-Based Motion Planning (RRT).

🧭 1. Discrete Heuristic Search: $A^*$ and Jump Point Search

$A^*$ evaluates nodes on a discretized graph (such as a 2D occupancy grid) using the cost evaluation function:

$$f(n) = g(n) + h(n)$$

Where:

• $g(n)$ is the exact cost from the start node to node $n$.
• $h(n)$ is an admissible heuristic (e.g., Euclidean or Manhattan distance) that never overestimates the true remaining cost to the goal.

Strengths of $A^*$:

• Resolution Completeness: If a path exists on the discretized grid, $A^*$ is mathematically guaranteed to find it.
• Optimality: It discovers the lowest-cost path with respect to the heuristic.

Limitations of $A^*$:

• The Curse of Dimensionality: A 2D grid with $1000 \times 1000$ cells has $10^6$ states. A 6-DOF robotic manipulator discretized at 100 steps per joint explodes to $10^{12}$ states—making grid search computationally intractable.
• Kinematic Infeasibility: $A^*$ produces jagged, piecewise-linear paths that physical vehicles with minimum turning radii (Ackermann steering) cannot execute smoothly without post-processing spline smoothing.

🌲 2. Sampling-Based Planning: RRT and RRT*

Instead of discretizing space into uniform grids, Rapidly-exploring Random Trees (RRT) (LaValle, 1998) sample points randomly from the continuous configuration space $\mathcal{C}$:

1. Sample a random configuration $q_{\text{rand}} \in \mathcal{C}_{\text{free}}$.
2. Find the nearest existing tree node $q_{\text{near}} \in T$.
3. Extend a new node $q_{\text{new}}$ from $q_{\text{near}}$ toward $q_{\text{rand}}$ by a fixed step size $\Delta q$.
4. Check collision validity along the trajectory segment. If clear, add $q_{\text{new}}$ and the edge $(q_{\text{near}}, q_{\text{new}})$ to the tree.
5. Repeat until $q_{\text{new}}$ is within reach of the goal $q_{\text{goal}}$.

import random
import math

class RRTPlanner:
    def __init__(self, start, goal, obstacles, step_size=5.0):
        self.start = start
        self.goal = goal
        self.obstacles = obstacles # List of (x, y, radius)
        self.step_size = step_size
        self.tree = [start]
        self.parents = {start: None}

    def plan(self, max_iters=5000):
        for _ in range(max_iters):
            # Goal biasing: 10% chance to sample exact goal directly
            q_rand = self.goal if random.random() < 0.1 else (random.uniform(0, 100), random.uniform(0, 100))
            
            # Find nearest node in tree
            q_near = min(self.tree, key=lambda n: math.dist(n, q_rand))
            
            # Step toward sample
            angle = math.atan2(q_rand[1] - q_near[1], q_rand[0] - q_near[0])
            q_new = (q_near[0] + self.step_size * math.cos(angle),
                     q_near[1] + self.step_size * math.sin(angle))
            
            if self.is_collision_free(q_near, q_new):
                self.tree.append(q_new)
                self.parents[q_new] = q_near
                
                if math.dist(q_new, self.goal) <= self.step_size:
                    self.parents[self.goal] = q_new
                    return self.reconstruct_path(self.goal)
        return None

⚖️ 3. Head-to-Head Comparison

| Metric | $A^$ Search | RRT / RRT |

|---|---|---|

| Space Representation | Discretized Grid / Graph | Continuous Configuration Space $\mathcal{C}$ |

| High Dimensions (D > 3) | Fails due to state space explosion | Excels; scales smoothly into high dimensions |

| Completeness | Resolution Complete | Probabilistically Complete |

| Optimality | Optimal for grid graph | RRT: Suboptimal; RRT*: Asymptotically Optimal |

| Kinodynamic Constraints| Hard to incorporate | Naturally supports differential equations in edge generation |

🎓 Applied Autonomous Engineering at Kone Warp

In the Kone Warp Autonomous Fleet curriculum, our engineers combine both paradigms: using hierarchical coarse $A^$ or H3-hexagonal routing for strategic route assignment, coupled with kinodynamic RRT and Model Predictive Control (MPC) for obstacle avoidance in physical transit.