Rapidly-exploring Random Tree (RRT)

RRT is probabilistically complete, meaning the probability of finding a feasible path, if one exists, approaches 1 as the number of samples (tree nodes) goes to infinity. This is a key guarantee for planners in complex, high-dimensional spaces.

• Contrast with Resolution Completeness: Unlike grid-based A* search, which is resolution-complete (guaranteed to find a path at a fine enough grid resolution), RRT does not require discretization of the state space.
• Implication for Practice: Given sufficient runtime, the algorithm will almost surely find a solution, making it reliable for difficult problems like non-holonomic or kinodynamic planning where other planners may get stuck.

The algorithm's growth is biased toward large, unexplored regions of the configuration space, causing the tree to rapidly expand. This is achieved by sampling random states and extending the tree toward them.

• Voronoi Bias: The probability of expanding a particular branch is proportional to the volume of its Voronoi region (the set of points in space closer to that node than to any other tree node). Larger regions are more likely to be selected for expansion.
• Efficiency in High Dimensions: This bias allows RRT to efficiently cover vast, multidimensional spaces without the exponential memory cost of a full grid, making it practical for robots with many degrees of freedom.

RRT naturally accommodates non-holonomic constraints (e.g., a car cannot move sideways) and kinodynamic constraints (e.g., acceleration limits) through its steering function.

• Steering Function (Local Planner): The EXTEND operation uses a local planner to generate a feasible trajectory segment from the nearest tree node toward the random sample. This function encodes the vehicle's dynamics.
• Collision Checking: Each new segment is validated by a feasibility checker to ensure it lies within free space. This decoupling of global exploration from local constraint satisfaction is a major architectural strength.
• Application: This makes RRT the algorithm of choice for planning for wheeled vehicles, drones, and manipulators where dynamics are critical.

RRT is an anytime algorithm—it can return a solution as soon as one is found, with quality improving over time. It is also inherently incremental; the tree can continue to grow and improve even after an initial path is found.

• Real-Time Replanning: This property is crucial for real-time replanning engines. If the environment changes, the existing tree can be used as a warm start, and exploration can continue from its current state to find a new path without starting from scratch.
• Connection to RRT*: The optimal variant RRT* leverages this incremental nature by adding a rewiring step that continuously improves the tree's cost-to-come values, asymptotically converging toward an optimal path.

RRT is designed as a single-query planner. It builds a tree specifically for one start-goal pair, unlike multi-query methods like the Probabilistic Roadmap (PRM) which builds a reusable map of the entire space.

• Advantage in Dynamic Environments: For real-time applications where the environment or goal changes frequently, the single-query approach is often more efficient than maintaining and querying a global roadmap.
• Computational Trade-off: The tree is discarded after use. This is ideal for replanning triggers where a new plan must be generated from the agent's current state in response to a new obstacle or task.

While powerful, standard RRT has known limitations that influence its application in heterogeneous fleet orchestration.

• Non-Optimal Paths: The basic algorithm does not optimize path length or cost; it merely finds a feasible path. This is addressed by variants like RRT*.
• Poor Convergence Rate: The purely random sampling can be inefficient in cluttered environments or narrow passages. Heuristics like goal biasing or intelligent sampling can improve performance.
• Deterministic Execution: For safety-critical systems, the stochastic nature can be a concern. Seeding the random number generator ensures repeatable plans for testing and validation.
• Integration with Local Planners: In practice, RRT is often used to generate a global, coarse path, which is then tracked and refined by a local controller like Model Predictive Control (MPC) or the Dynamic Window Approach (DWA).

RRT* is an asymptotically optimal variant of the basic RRT algorithm. It introduces a rewiring step in the tree growth process: after adding a new node, the algorithm checks if connecting it to different nearby nodes in the tree would yield a lower-cost path to those nodes. This continuous optimization allows RRT* to converge towards the globally optimal path given sufficient samples, whereas standard RRT only finds a feasible path.

A Probabilistic Roadmap is a sampling-based motion planning method that operates in two distinct phases. First, in a learning phase, it randomly samples collision-free configurations (nodes) in the workspace and connects nearby nodes to form a graph, or 'roadmap'. Second, in a query phase, it uses this pre-computed roadmap to find paths between specific start and goal states. Unlike RRT, which builds a tree from a start point, PRM builds a more general network, making it efficient for solving multiple queries in the same static environment.

D Lite* is a focused incremental search algorithm designed for replanning in unknown or dynamic environments. It is based on Lifelong Planning A* (LPA*) and is simpler to implement than the original D* algorithm. Its core strength is efficiency: when the cost map changes (e.g., a new obstacle is detected), D* Lite reuses information from the previous search to repair the cost map and path, rather than replanning from scratch. This makes it a cornerstone algorithm for real-time navigation where the environment is partially observable.

Kinodynamic planning is the problem of finding a trajectory that satisfies both kinematic constraints (e.g., non-holonomic restrictions like a car's turning radius) and dynamic constraints (e.g., limits on acceleration, torque, or velocity). Standard RRT operates in the configuration space (position/orientation). Kinodynamic RRT variants sample in the full state space (which includes velocity) and use a forward simulation step that respects the system's dynamics to grow the tree, making the resulting paths immediately executable by the physical system.

Model Predictive Control is an advanced online optimization-based control method. At each control time step, MPC:

• Uses a dynamic model of the system to predict its future behavior over a finite prediction horizon.
• Solves an optimization problem to find a sequence of control actions that minimizes a cost function (e.g., tracking error, energy use) while satisfying constraints.
• Executes only the first control action from the optimized sequence.
• Repeats the process at the next time step with updated state feedback (receding horizon control). It is highly effective for real-time trajectory tracking and obstacle avoidance.

Conflict-Based Search is a two-level, optimal algorithm for Multi-Agent Path Finding (MAPF). It operates by:

1. Planning an initial, potentially conflicting path for each agent independently.
2. Detecting the first spatio-temporal conflict (e.g., two agents occupying the same location at the same time).
3. Resolving the conflict by creating two new search nodes, each adding a constraint to one of the agents involved.
4. Recursively searching this constraint tree until a conflict-free set of paths is found. CBS is a fundamental high-level planner for coordinating multi-agent fleets, whose output can be passed to low-level planners like RRT for each agent.