EigenFan

Deterministic trajectory planning from semidefinite relaxations to collision-free paths.

EigenFan composes Shor SDP relaxation, geometry-aware EigenFan rounding, roadmap shortest-path search, and optional convex smoothing into a deterministic planning pipeline for cluttered environments.

Figure 1. EigenFan pipeline on the Enclosed Circle Maze (clockwise from top-left): Semi-Definite Program Relaxed Trajectory, EigenFan Sampled Roadmap, EigenFan Polyline, and EigenFan Smooth Trajectory.

Highlights

• Deterministic core pipeline: identical inputs produce identical relaxation, rounding, and graph-search outputs.
• Applicable to N-dimensional planning formulations; the codebase includes visualization tooling for 2D and 3D formulations.
• Robust retry ladder for hard scenes: adaptive waypoint density, fan rays, and free-space seed augmentation.
• Reproducible benchmark and media scripts for end-to-end figure generation.

Method Overview

1. Solve a Shor semidefinite relaxation for a coarse trajectory estimate.
2. Build obstacle connected components and generate EigenFan edge candidates per waypoint.
3. Prune and merge edge candidates into robust roadmap nodes.
4. Build roadmap connectivity (Delaunay + bridge KNN fallback) and run Dijkstra.
5. Resample the polyline to a stable smoothing reference.
6. Optionally run corridor-constrained QP smoothing.

Architecture and Mathematical Details

Notation

• d: state dimension.
• N: target final waypoint count; N_s: Shor-relaxation waypoint count.
• M: number of spherical obstacles.
• x_i ∈ R^d: waypoint i.
• Obstacle j: center c_j ∈ R^d, radius r_j.
• V, E: roadmap nodes and edges.

1) Shor SDP Relaxation

The base nonconvex trajectory objective is

min over {x_i}:  Σ_{i=0}^{N_s-2} ||x_{i+1} - x_i||_2^2

with fixed endpoints x_0 = x_init, x_{N_s-1} = x_goal.

EigenFan lifts this into an SDP with X_i ≈ x_i x_i^T, Y_i ≈ x_{i+1}x_i^T, and per-segment block PSD constraints:

[ 1      x_i^T      x_{i+1}^T ]
[ x_i    X_i        Y_i^T     ]  ⪰ 0
[ x_{i+1} Y_i       X_{i+1}   ]

Obstacle avoidance for sphere j at waypoint i is linear in lifted variables:

tr(X_i) - 2 c_j^T x_i + ||c_j||_2^2  ≥  r_j^2

Complexity profile:

• Variable dimension scales as Θ(N_s d^2).
• PSD constraints: N_s-1 blocks of size 1+2d.
• Full obstacle constraints would be Θ((N_s-2)M), but active-set constraint generation reduces this to Θ((N_s-2)K) with K << M in practice.
• Dominant solve cost is the SDP interior-point solve (superlinear/cubic in cone-variable scale; practically the largest term in hard scenes).

2) Connected Components + EigenFan Edge Generation

Obstacles are grouped by overlap graph connectivity:

||c_a - c_b||_2  ≤  r_a + r_b + ε

This identifies obstacle components that are rounded independently around each waypoint.

For waypoint i, local covariance surrogate:

Σ_i = X_i - x_i x_i^T

From stabilized principal axes (v_1, v_2) and eigenvalues (λ_1, λ_2), fan rays are generated in a bounded angular aperture. Candidate edge points are extracted from ray-obstacle intersection intervals with padding/latching rules.

Complexity profile:

• Current component construction is pairwise overlap: O(M^2).
• Per waypoint fan generation is small in 2D/3D but interval intersection scans scale with obstacle count.
• Approximate stage runtime: O((N_s-2) · R_f · M), where R_f is effective fan rays per waypoint (including re-entry handling).

3) Candidate Pruning and Edge-Set Fusion

Candidates are keyed by (i,k) = (waypoint, component). Each bucket is binned by obstacle index and direction signature, then up to two representatives are kept:

• nearest to path waypoint x_i,
• most aligned with local normal direction.

This preserves directional diversity while reducing graph size.

Complexity profile:

• Linear in number of generated candidates K_cand: O(K_cand) expected.
• Memory also O(K_cand) prior to pruning.

4) Roadmap Construction + Shortest Path

Roadmap nodes combine:

• safe path nodes from relaxed path,
• pruned edge nodes,
• optional retry seed nodes in free space.

Primary wiring is Delaunay triangulation plus collision-filtered edges. If disconnected, bridge-KNN adds collision-free cross-component edges until start-goal connectivity or budget exhaustion.

Shortest path is solved with Dijkstra over weighted Euclidean edges.

Complexity profile:

• Delaunay (for d≤3): average O(V log V), worst-case higher.
• Collision filtering: O(E_Δ (log M + h)) with broad-phase index; h = local candidate obstacles.
• Bridge-KNN: KD-tree + heap candidate processing, roughly O(Vk log(Vk)) plus collision checks up to bridge budget.
• Dijkstra: O((V+E) log V).

5) Reference Resampling and Clearance Validation

Dijkstra polyline is converted to a smoothing reference with vertex-preserving resampling to target N, then validated by point and segment clearance. Unsafe resampled references automatically fall back to raw Dijkstra.

Complexity profile:

• Resampling: linear in path vertices.
• Clearance validation: O(N_ref M) for points plus segment checks over obstacles.

6) Corridor QP Smoothing

Given reference x_ref, solve a convex QP over X ∈ R^(N_ref × d):

min over X:
  w_t ||X - x_ref||_F^2
+ w_v ||ΔX||_F^2
+ w_a ||Δ^2 X||_F^2
+ w_j ||Δ^3 X||_F^2

subject to endpoint equality, trust-region bounds, and half-space corridor constraints:

a^T X_i ≥ b
a^T ((1-τ)X_i + τX_{i+1}) ≥ b

The solver runs sequential convex updates with adaptive trust region expansion/shrink and global collision validation after each candidate.

Complexity profile:

• Per QP solve (dense worst case): roughly cubic in decision dimension (N_ref d).
• Total smoothing runtime: O(I · T_QP), where I is accepted/retry iterations.

End-to-End Runtime Model

With retry ladder attempts a = 1..A:

T_total ≈ Σ_{a=1..A} (
  T_SDP^(a) +
  T_fan^(a) +
  T_prune^(a) +
  T_roadmap^(a) +
  T_dijkstra^(a) +
  T_smooth^(a)
)

In hard 3D scenes, dominant terms are typically SDP and roadmap connectivity; smoothing can dominate when N_ref is large and corridor constraints are dense.

Core implementation:

• src/eigenfan/pipeline.py
• src/eigenfan/relaxations/shor.py
• src/eigenfan/rounding/eigenfan.py
• src/eigenfan/roadmap/
• src/eigenfan/smoothing/

Quickstart

Run from repository root.

# 1) (Recommended) local environment
python3.12 -m venv .venv
source .venv/bin/activate

# 2) Core deps (adjust as needed for your machine)
pip install numpy scipy matplotlib cvxpy plotly

# 3) Prevent matplotlib cache permission warnings on macOS
export MPLCONFIGDIR=/tmp/mplconfig

List available generators:

python3.12 src/scripts/list_generators.py --dim all

Run EigenFan on one environment:

PYTHONPATH=src python3.12 -m eigenfan.main --generator requires_bridge_knn --N 80

Export interactive 3D home media:

python3.12 src/scripts/export_3d_media.py \
  --generator home_compound_enclosed_3d \
  --html media/readme_suite_10trials/figures/interactive_home_compound_enclosed_3d.html \
  --skip-animation \
  --no-smoothing

Results

Across 8 benchmark environments and 10 trials per planner/environment, EigenFan’s deterministic pipeline is most compelling in cluttered, bottlenecked scenes where clearance-aware structure matters. In this setting, the EigenFan Polyline stage is reliably collision-free, and the smooth stage improves geometric quality while preserving feasibility.

Where EigenFan is strongest:

• Deterministic repeatability: identical inputs produce identical Polyline/Smooth outputs.
• Strong path quality in maze-like and narrow-passage environments.
• Robust behavior in scenes where stochastic planners often show higher trial-to-trial variance.

Where baseline planners can beat EigenFan:

• In easier/open scenes, first-feasible planners (especially RRT-Connect) can return a valid path faster.
• If runtime-only latency is prioritized over path quality, stochastic planners can be preferable.
• Smoothing adds useful quality, but it is additional compute compared with a raw first-feasible path.

Environments represented in Figure 2 (8 total):

• Classic Bugtrap Standard (classic_bugtrap_standard)
• Enclosed Circle Maze Bottom Left To Top Right (enclosed_circle_maze_bottom_left_to_top_right)
• Enclosed Double Bugtrap Cathedral (enclosed_double_bugtrap_cathedral)
• Enclosed Heterogeneous Asteroid Field (enclosed_heterogeneous_asteroid_field)
• Enclosed Serpentine Stunnel (enclosed_serpentine_stunnel)
• Maze Circular Labyrinth Center Goal (maze_circular_labyrinth_center_goal)
• Narrow Passage (narrow_passage)
• Requires Bridge KNN (requires_bridge_knn)

Figure 2. Per-environment path comparison on all 8 benchmark scenes in a 2×4 grid. Each panel overlays EigenFan Polyline, EigenFan Smooth, and the best stochastic planner selected by path distance for that environment (planner identity appears in the panel legend).

Figure 3. Aggregated benchmark matrix across 8 environments and 10 trials per planner. Left: mean runtime (s). Right: mean path length for successful runs. Lower is better in both panels.

Figure 4. Speed-quality-success tradeoff across planners. Each point aggregates all environments and trials in the combined suite.

Benchmark Suite (Reproducibility)

This repository includes:

• readme_suite_10trials: core 2D benchmark set + 3D assets.
• readme_suite_hard2d_10trials: three hard 2D environments.
• readme_suite_combined_10trials: merged benchmark matrix/Pareto over all 8 environments.

Generate core suite (default benchmark environments):

python3.12 src/scripts/generate_readme_figures.py generate \
  --out-dir media/readme_suite_10trials \
  --solver MOSEK \
  --trials 10 \
  --planner-timeout-s 900 \
  --seed 0 \
  --visual-n-override 100 \
  --overwrite

Generate hard 2D suite:

python3.12 src/scripts/generate_readme_figures.py generate \
  --out-dir media/readme_suite_hard2d_10trials \
  --solver MOSEK \
  --trials 10 \
  --planner-timeout-s 900 \
  --seed 0 \
  --visual-n-override 100 \
  --benchmark-envs enclosed_heterogeneous_asteroid_field enclosed_serpentine_stunnel enclosed_double_bugtrap_cathedral \
  --gallery-envs enclosed_heterogeneous_asteroid_field enclosed_serpentine_stunnel enclosed_double_bugtrap_cathedral \
  --pipeline-hero-env enclosed_double_bugtrap_cathedral \
  --bridge-showcase-env enclosed_serpentine_stunnel \
  --home-html-env "" \
  --best-overlay-env enclosed_double_bugtrap_cathedral \
  --overwrite

Merge both suites into one benchmark matrix + one Pareto plot:

python3.12 src/scripts/merge_benchmark_suites.py \
  --suite-json \
    media/readme_suite_10trials/data/benchmark_suite.json \
    media/readme_suite_hard2d_10trials/data/benchmark_suite.json \
  --out-dir media/readme_suite_combined_10trials

N-D EigenFan

EigenFan’s planning core is dimension-agnostic: states are vectors in R^d, obstacles are spherical constraints (the type alias Circle is used for backward compatibility).

N-D status:

• Shor relaxation, EigenFan rounding, collision checks, and roadmap search support general d.
• Seed-node strategy includes a random PRM-style fallback for d > 3.
• Built-in visualization is intentionally limited to 2D/3D.
• Included obstacle generators are mostly 2D/3D, but custom N-D scenes are supported through the API.

Figure 5. 3D N-D EigenFan example in the enclosed home environment (interactive HTML rendered to GIF), showing relaxation, EigenFan Polyline (computed via Dijkstra), and smoothed trajectory behavior.

Interactive home scene (HTML):
media/readme_suite_10trials/figures/interactive_home_compound_enclosed_3d.html

Minimal custom N-D usage:

import numpy as np
from eigenfan.pipeline import plan
from eigenfan.config import PlannerConfig

d = 6
x_init = np.array([0, 0, 0, 0, 0, 0], dtype=float)
x_goal = np.array([8, 7, 6, 2, 2, 1], dtype=float)
spheres = [
    (np.array([3, 3, 3, 1, 1, 0.5], dtype=float), 1.8),
    (np.array([5, 4, 4, 1.5, 1.2, 0.8], dtype=float), 1.6),
]

res = plan(x_init, x_goal, spheres, N=70, config=PlannerConfig(), do_smoothing=False)
print(res.stats["solve_success"], res.stats["path_length"])

Appendix: Reproducing Figures and Results

A.1 Benchmark + Figure Suites

Core 2D + 3D media suite:

python3.12 src/scripts/generate_readme_figures.py generate \
  --out-dir media/readme_suite_10trials \
  --solver MOSEK \
  --trials 10 \
  --planner-timeout-s 900 \
  --seed 0 \
  --visual-n-override 100 \
  --overwrite

Hard 2D suite:

python3.12 src/scripts/generate_readme_figures.py generate \
  --out-dir media/readme_suite_hard2d_10trials \
  --solver MOSEK \
  --trials 10 \
  --planner-timeout-s 900 \
  --seed 0 \
  --visual-n-override 100 \
  --benchmark-envs enclosed_heterogeneous_asteroid_field enclosed_serpentine_stunnel enclosed_double_bugtrap_cathedral \
  --gallery-envs enclosed_heterogeneous_asteroid_field enclosed_serpentine_stunnel enclosed_double_bugtrap_cathedral \
  --pipeline-hero-env enclosed_double_bugtrap_cathedral \
  --bridge-showcase-env enclosed_serpentine_stunnel \
  --home-html-env "" \
  --best-overlay-env enclosed_double_bugtrap_cathedral \
  --overwrite

Merge both benchmark JSONs into combined snapshot figures:

python3.12 src/scripts/merge_benchmark_suites.py \
  --suite-json \
    media/readme_suite_10trials/data/benchmark_suite.json \
    media/readme_suite_hard2d_10trials/data/benchmark_suite.json \
  --out-dir media/readme_suite_combined_10trials

A.2 3D Interactive HTML and Rotating GIF

Export interactive home HTML:

python3.12 src/scripts/export_3d_media.py \
  --generator home_compound_enclosed_3d \
  --html media/readme_suite_10trials/figures/interactive_home_compound_enclosed_3d.html \
  --skip-animation \
  --no-smoothing

Convert Plotly HTML to rotating GIF:

pip install playwright
python3.12 -m playwright install chromium

python3.12 src/scripts/html_to_rotating_gif.py \
  --html media/readme_suite_10trials/figures/interactive_home_compound_enclosed_3d.html \
  --gif media/readme_suite_10trials/figures/home_compound_enclosed_3d_rotating.gif \
  --seconds 25 \
  --fps 60 \
  --width 800 \
  --height 450 \
  --start-elev 30 \
  --top-elev 88

A.3 Other Figure/Result Entry Points

• Environment inventory: python3.12 src/scripts/list_generators.py --dim all
• Single environment visualization: python3.12 src/scripts/visualize_environment.py --generator <name>
• Full planner run for one scene: PYTHONPATH=src python3.12 -m eigenfan.main --generator <name> --N 80

License

This project is released under the Apache License 2.0 (Apache-2.0). See LICENSE.