RiskPlanning.jl

Quick Start

To run a basic planning scenario and visualize the result, you can use the following script, which is a simplified version of scripts/prova.jl:

using RiskPlanning
using GLMakie # For plotting

# 1. Load a pre-defined scenario from the paper
problem = get_paper_scenario()

# 2. Configure the RRT* planner
# We'll use a FrontierSampler and 5000 samples.
planner = RRTStar(
    n_samples=5000,
    sampler=FrontierSampler(goal_bias=0.05)
)

# 3. Run the planner
# We must specify a neighbor-finding strategy, like the Quadtree-based one.
solution = plan!(planner, problem, make_ntree_finder)

# 4. Summarize and plot the results
if is_successful(solution)
    summarize_solution(solution, problem, planner)
    fig = plot_solution(problem, solution)
    display(fig) # Show the plot
else
    @error "Planning failed to find a solution."
end

Directory Structure

The project is organized to separate concerns and facilitate modular development.

• src/: Contains all core source code.
  • planners/: The main RRT* algorithm implementation.
  • samplers/: Sampler implementations (UniformSampler, FrontierSampler, etc.).
  • finders/: Neighbor-finding strategies (KDTreeFinder, NTreeFinder).
  • risk_computation.jl: The core mathematical formulas for cost functions.
  • planning_core.jl: Defines the abstract interfaces (AbstractPlanner, PlanningProblem).
  • ...: Other core modules for geometry, dynamics, etc.
• scripts/: Executable scripts for running benchmarks and examples.
  • prova.jl: A simple script to test a single planner run.
  • sampler_finder_benchmark.jl: A comprehensive benchmark for comparing samplers and finders.
  • vsRRTinflated.jl: The script to reproduce the paper's comparison against RRT* with inflated obstacles.
• data/: Default output directory for benchmark results (managed by DrWatson.jl).
• plots/: Default output directory for saved plots (managed by DrWatson.jl).
• Project.toml: The Julia project file defining dependencies.

Key Architectural Components

The framework is built from the following orthogonal components:

• planning_core.jl: Defines the fundamental interfaces (AbstractPlanner, PlanningProblem, PlannerSolution).

• planners/RRT.jl: Contains the RRTStar algorithm. This implementation acts as a "scaffolding" that executes the sample, connect, and rewire steps. It is agnostic to the specific cost function or sampling strategy being used.

• sampling_utils.jl: Defines the AbstractSampler interface and a suite of concrete sampling strategies (e.g., UniformSampler, FrontierSampler, MahalanobisFrontierSampler). The sampler guide the search based on its specific heuristic.

• risk_costs_definitions.jl & risk_computation.jl: The mathematical core of the risk-aware functionality.

  • _definitions: Defines the cost function types (RDProb, RDRisk, etc.) and their required data structures (UncertainObstacle).
  • _computation: Implements the actual mathematical formulas for both the forward problem (calculating the cost of a given path) and the inverse problem (finding a path segment that corresponds to a given cost budget).

• neighbor_finders.jl: Provides an abstraction (NeighborFinder) for the spatial data structures (e.g., KDTreeFinder, NTreeFinder) used for efficient nearest-neighbor and range queries.

• reporting_utils.jl: (Optional) Provides utilities for summarizing and pretty-printing single-run or multi-run benchmark results.

3. Theory vs. Practice: The Asymptotic Optimality Gap

While the RRT* algorithm provides a theoretical guarantee of asymptotic optimality, our implementation, RD-RRT*, makes several practical compromises for the sake of computational feasibility. It is crucial to understand these deviations:

1. Heuristic Near Neighbor Search: The RRT* proof requires finding neighbors within a "ball" defined by the problem's cost metric. For Risk Density, this is computationally intractable. We instead use a Euclidean ball as a fast, heuristic-based filter to generate a candidate set of neighbors. The exact risk cost is then computed only for this small set.

2. Fixed Rewiring Radius: The optimality proof requires the search radius to shrink as a function of the number of samples (n). Our implementation uses a fixed Euclidean radius, which simplifies the algorithm but forgoes the guarantee of converging to the optimal path.

3. Heuristic steer Function: The theoretical steer function is assumed to be able to connect any two sufficiently close points. Our implementation is a practical heuristic that truncates motion based on both a maximum Euclidean distance and a maximum risk-cost budget.

Consequently RD-RRT* it is not guaranteed to be asymptotically optimal.

The Anatomy of a Planner Call (A High-Level Trace)

plan!(planner, problem, finder_factory)
 │
 ├─ [GENERIC RRT* LOGIC in planners/RRT.jl]
 │   The main loop iterates, performing the RRT* steps. For each iteration:
 │
 ├─ STEP 1: SAMPLE
 │   └─ sample(sampler, state, problem)
 │        │
 │        └─ [DISPATCH ON SAMPLER TYPE in sampling_utils.jl]
 │           This calls the specialized logic for `UniformSampler`,
 │           `FrontierSampler`, etc.
 │
 ├─ STEP 2: STEER
 │   └─ steer_towards(problem.bvp, x_nearest, x_rand, ...)
 │        │
 │        └─ [DISPATCH ON COST TYPE in risk_computation.jl]
 │           Julia inspects `problem.bvp.cost` and selects the appropriate
 │           `steer_towards` method (e.g., the one for `RiskCosts`).
 │           This is where the forward and inverse problems are solved.
 │
 └─ STEP 3: CHOOSE PARENT / REWIRE
     ├─ [HEURISTIC FILTERING in planners/RRT.jl]
     │   `find_neighbors_in_range!(..., finder, x_new, euclidean_radius)`
     │   This uses the geometric `finder` with a Euclidean radius.
     │
     └─ [EXACT EVALUATION in planners/RRT.jl]
        For each candidate in the small filtered set:
        └─ `cost = bvp(candidate_state, x_new)`  <-- Calls the true risk function.