\documentclass[10pt,twocolumn]{article}

%% ── Packages ──────────────────────────────────────────────────────────────
\usepackage[margin=1in]{geometry}
\usepackage{times}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{cite}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{url}
\usepackage{microtype}

%% ── arXiv metadata ────────────────────────────────────────────────────────
\hypersetup{
  pdftitle={Comparative Evaluation of Classical Motion Planners for
            Autonomous Drone Navigation in 3D Voxel Environments},
  pdfauthor={Medisetti Renukeswar},
  pdfkeywords={path planning, RRT*, A*, Informed RRT*, drone navigation,
               3D occupancy grid, Monte Carlo benchmark},
  colorlinks=true,
  linkcolor=blue,
  citecolor=blue,
  urlcolor=blue,
}

%% ── Theorem environments ─────────────────────────────────────────────────
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}

%% ── Macros ────────────────────────────────────────────────────────────────
\newcommand{\Rn}{\mathbb{R}^n}
\newcommand{\Xfree}{X_{\mathrm{free}}}
\newcommand{\cbest}{c_{\mathrm{best}}}
\newcommand{\cmin}{c_{\mathrm{min}}}
\newcommand{\rn}{r_n}

%% ═══════════════════════════════════════════════════════════════════════════
\begin{document}

\title{\textbf{Comparative Evaluation of Classical Motion Planners\\
for Autonomous Drone Navigation in 3D Voxel Environments}}

\author{
  Medisetti Renukeswar\\
  \texttt{medisettirenukeswar83@gmail.com}\\
  \href{https://github.com/MedisettiRenukeswar}{github.com/MedisettiRenukeswar}
}

\date{\today}
\maketitle

%% ── Abstract ─────────────────────────────────────────────────────────────
\begin{abstract}
We present a reproducible Monte Carlo benchmark comparing three classical
3D motion planners---A* (deterministic grid search), RRT* (sampling-based
asymptotically optimal), and Informed~RRT* (ellipsoidal-focused
sampling)---for autonomous drone navigation in 3D voxel environments.
Experiments are conducted on a $25\times25\times12$ voxel grid across
seven environment families (sparse forest, dense forest, canyon, urban
corridor, random clutter, narrow passage, maze) at three obstacle
densities (6\%, 14\%, 22\%), with 10 independent random seeds per
condition, yielding 630 planning trials.
All algorithms achieve 100\% success rate.
A* plans in $37\pm4$~ms but produces grid-constrained paths
($33.97$~m mean) with the highest curvature ($\kappa=0.069$~m$^{-1}$)
and energy cost (58.6~J proxy).
RRT* finds shorter paths ($33.19\pm0.39$~m) with lower curvature
($\kappa=0.026$~m$^{-1}$), but requires 7.4~s mean planning time.
Informed~RRT* achieves the shortest paths ($32.54\pm0.14$~m) and
the lowest curvature ($\kappa=0.006$~m$^{-1}$) at the cost of
9.3~s mean planning time.
All paths satisfy the dynamic feasibility criterion
($\kappa\leq0.8$~m$^{-1}$).
Key contributions: (1)~corrected Karaman--Frazzoli rewire radius
(asymptotic optimality guarantee); (2)~SVD-based ellipsoidal sampler
verified to machine precision; (3)~density-controlled environment
generator eliminating a systematic bias present in prior benchmarks;
(4)~five path quality metrics including Menger curvature and kinematic
energy proxy.
All source code, raw CSV data, and reproduction scripts are released
at \url{https://github.com/MedisettiRenukeswar}.
\end{abstract}

\textbf{Keywords:} motion planning, RRT*, A*, Informed RRT*, drone
navigation, 3D occupancy grid, Monte Carlo benchmark, path quality metrics.

%% ── I. Introduction ──────────────────────────────────────────────────────
\section{Introduction}\label{sec:intro}

Autonomous navigation in three-dimensional cluttered environments is a
core problem in aerial robotics.
A quadrotor must compute a collision-free trajectory from a start
configuration to a goal while respecting dynamic constraints---limited
curvature, bounded jerk---and minimising cost criteria such as path
length and energy consumption.
Despite two decades of progress, rigorous head-to-head comparisons of
classical planners under controlled experimental conditions remain
surprisingly scarce in the literature.

Two paradigms dominate practical 3D planning: \emph{deterministic
grid-search} and \emph{sampling-based continuous-space} methods.
Grid-search planners such as A*~\cite{hart1968} are complete, optimal on
the discrete lattice, and computationally cheap, but their paths are
constrained to lattice directions, introducing systematic curvature
artefacts (the ``staircase effect'').
Sampling-based planners such as RRT*~\cite{karaman2011} and Informed
RRT*~\cite{gammell2014} operate in continuous space and converge to
shorter, smoother paths, but require many iterations and are inherently
stochastic.

This paper addresses the following concrete research question:
\emph{Under identical experimental conditions (same grid, same
start/goal, same random seeds), how do A*, RRT*, and Informed RRT*
compare across path length, planning time, curvature, energy cost, and
dynamic feasibility?}

We make four methodological contributions beyond prior benchmarks:

\begin{enumerate}
\item We implement the \emph{correct} Karaman--Frazzoli shrinking rewire
  radius~\cite{karaman2011}, which previous implementations routinely
  replace with an ad-hoc fixed constant, violating the asymptotic
  optimality guarantee.

\item We implement the \emph{correct} SVD-based ellipsoidal sampler for
  Informed RRT*~\cite{gammell2014}, verified to machine precision
  ($\|CC^\top - I\|_F < 10^{-10}$).

\item We introduce a \emph{density-controlled environment generator}
  that fills single voxels iteratively until the target obstacle density
  is achieved within $\pm0.5\%$.
  Prior benchmarks used fixed obstacle counts irrespective of requested
  density, making their ``low/medium/high density'' conditions identical.

\item We report five path quality metrics---Euclidean path length,
  minimum/mean obstacle clearance, mean turning angle (smoothness),
  mean Menger curvature, and a kinematic energy proxy---in addition to
  planning time and node count.
\end{enumerate}

%% ── II. Related Work ─────────────────────────────────────────────────────
\section{Related Work}\label{sec:related}

\subsection{Grid-Based Planning}
A*~\cite{hart1968} is a best-first search ordered by $f(n)=g(n)+h(n)$
where $g$ is accumulated cost and $h$ is an admissible heuristic.
In a 26-connected 3D voxel grid with Euclidean heuristic, A* finds the
globally optimal discrete path.
Weighted A*~\cite{pohl1970} trades optimality for speed via heuristic
inflation $f=g+wh$, $w>1$.
Theta*~\cite{daniel2010} enables any-angle movement, reducing
grid-alignment artefacts.

\subsection{Sampling-Based Planning}
RRT*~\cite{karaman2011} extends RRT~\cite{lavalle1998} with a rewiring
step operating on nodes within a ball of radius $r_n$ around each new
node.
The radius must shrink as $r_n = \gamma(\log n/n)^{1/d}$ for
asymptotic optimality; fixed-radius implementations are incorrect.
Informed RRT*~\cite{gammell2014} restricts sampling to the prolate
hyperspheroid of all paths shorter than the current best solution,
concentrating effort where improvement remains possible.
BIT*~\cite{gammell2015} unifies graph search and batch sampling, and is
considered state of the art for single-query optimal planning.
We do not include BIT* in this benchmark because our focus is on
correctly implementing and comparing the \emph{foundational} planners
that underpin most practical systems.

\subsection{Benchmarks and Comparisons}
Comparisons of planning algorithms in 3D environments frequently lack
reproducibility: environments are not shareable, seeds are not reported,
or density conditions are not verified.
Elbanhawi and Simic~\cite{elbanhawi2014} provide a systematic survey
but do not include 3D voxel experiments.
LaValle~\cite{lavalle2006} provides theoretical comparisons without
empirical benchmarks.
Our work contributes a self-contained reproducible benchmark with
all code and data released.

%% ── III. Problem Formulation ─────────────────────────────────────────────
\section{Problem Formulation}\label{sec:problem}

Let $\mathcal{W} = \{0,\ldots,X{-}1\} \times \{0,\ldots,Y{-}1\}
\times \{0,\ldots,Z{-}1\}$ be a discrete 3D workspace of voxels,
partitioned into free space $\Xfree$ and obstacle space $\mathcal{X}_\mathrm{obs}$.
Given start $\mathbf{x}_s \in \Xfree$ and goal $\mathbf{x}_g \in
\Xfree$, find a sequence of voxels
$\pi = (\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_k)$
with $\mathbf{x}_0 = \mathbf{x}_s$, $\mathbf{x}_k = \mathbf{x}_g$,
$\mathbf{x}_i \in \Xfree$ for all $i$,
minimising $\sum_{i=1}^k \|\mathbf{x}_i - \mathbf{x}_{i-1}\|_2$.

Path quality is assessed by five additional metrics beyond cost:
\begin{itemize}
  \item \textbf{Clearance}: $\min_i d(\mathbf{x}_i, \mathcal{X}_\mathrm{obs})$
        where $d$ is the Euclidean distance transform.
  \item \textbf{Smoothness}: mean turning angle
        $\frac{1}{k-1}\sum_{i=1}^{k-1}\angle(\mathbf{v}_i, \mathbf{v}_{i+1})$,
        $\mathbf{v}_i = \mathbf{x}_i - \mathbf{x}_{i-1}$.
  \item \textbf{Menger curvature}: at interior waypoint $i$,
        $\kappa_i = 2A(p_{i-1},p_i,p_{i+1})/(|ab||bc||ca|)$
        where $A$ is triangle area.  Mean $\bar\kappa$ is reported.
  \item \textbf{Energy proxy}: $E = \tfrac{1}{2}mv^2 N + m\sum_i
        |\Delta\mathbf{v}_i|v$, with $m=0.5$~kg, $v=3$~m/s.
  \item \textbf{Dynamic feasibility}: $\bar\kappa \leq \kappa_\mathrm{max}
        = 0.8$~m$^{-1}$.
\end{itemize}

%% ── IV. Algorithm Implementations ────────────────────────────────────────
\section{Algorithm Implementations}\label{sec:algorithms}

\subsection{A* (Grid Search)}

We implement 26-connected A* with Euclidean heuristic
$h(\mathbf{x}) = \|\mathbf{x} - \mathbf{x}_g\|_2$.
Edge cost between adjacent voxels is the Euclidean distance between
their centres, so diagonal moves cost $\sqrt{2}$ (face-diagonal) or
$\sqrt{3}$ (body-diagonal) relative to axis-aligned moves.
The heuristic is admissible and consistent in 26-connectivity, so A*
finds the globally optimal discrete path.

\subsection{RRT* with Correct Rewire Radius}

The rewire radius follows Theorem~38 of Karaman and Frazzoli~\cite{karaman2011}:
\begin{equation}
  r_n = \min\!\left(\gamma \left(\frac{\log n}{n}\right)^{1/d},\; \eta\right),
  \label{eq:rewire_radius}
\end{equation}
where $d=3$, $\eta = 5\,\texttt{step\_size}$,
and $\gamma = 2(1+1/d)^{1/d}(\mu(\Xfree)/\zeta_d)^{1/d}$
with $\zeta_d = 4\pi/3$ (volume of unit 3-ball) and
$\mu(\Xfree)$ the free-space volume in voxels.
Using a fixed radius violates Eq.~(\ref{eq:rewire_radius}) and
invalidates the asymptotic optimality guarantee.

\subsection{Informed RRT* with SVD Ellipsoidal Sampler}

After finding a first solution of cost $\cbest$, samples are drawn from
the prolate hyperspheroid:
\begin{align}
  a_1 &= \cbest/2, \label{eq:a1} \\
  a_i &= \sqrt{\cbest^2 - \cmin^2}/2 \quad (i > 1), \label{eq:ai}
\end{align}
where $\cmin = \|\mathbf{x}_g - \mathbf{x}_s\|_2$.
The rotation matrix $C \in SO(3)$ satisfying $C[:,0] \parallel
(\mathbf{x}_g - \mathbf{x}_s)$ is computed via SVD of the rank-1
matrix $M = \mathbf{a}_1 \mathbf{e}_1^\top$, with a determinant
correction ensuring $\det(C) = +1$.
We verify $\|CC^\top - I\|_F < 10^{-10}$ in unit tests.

Samples are drawn rejection-free from the unit 3-ball via normalised
Gaussian projection followed by uniform radial scaling, then transformed
via $\mathbf{x} = C L \mathbf{x}_\mathrm{ball} + \mathbf{x}_\mathrm{centre}$
where $L = \mathrm{diag}(a_1, a_2, a_3)$.

%% ── V. Experimental Setup ────────────────────────────────────────────────
\section{Experimental Setup}\label{sec:experiments}

\subsection{Environment}

The workspace is a $25 \times 25 \times 12$ voxel grid ($7\,500$ cells)
with 1~m resolution.
Start: $(1,1,1)$; Goal: $(23,23,10)$; straight-line distance: 32.39~m.

\subsubsection{Seven Environment Families}
\begin{enumerate}
  \item \textbf{Sparse Forest}: thin vertical cylinders (radius 1), low occlusion.
  \item \textbf{Dense Forest}: wider cylinders (radius 1--2), high occlusion.
  \item \textbf{Canyon}: two parallel full-height walls with navigable gaps.
  \item \textbf{Urban Corridor}: rectangular building blocks with aisles.
  \item \textbf{Random Clutter}: mixed boxes and cylinders.
  \item \textbf{Narrow Passage}: two walls each with a single gap.
  \item \textbf{Maze}: grid-aligned wall segments.
\end{enumerate}

\subsubsection{Density Control}
Each family is generated at three obstacle densities: low (6\%),
medium (14\%), and high (22\%).
A structural phase adds family-characteristic obstacles; an iterative
fill phase adds single voxels until the target density is achieved
within $\pm0.5\%$.
The start and goal and their immediate neighbours are always cleared.

\subsection{Benchmark Protocol}

\textbf{Seed decoupling}: the environment seed $s_e$ and planner seed
$s_p$ are decoupled via $s_p = (s_e+1)\times7919$, where 7919 is
prime.
This prevents any correlation between environment shape and planner
sampling behaviour.

\textbf{Iteration budget}: RRT* and Informed RRT* use
$N_\mathrm{max} = 2000$ iterations.
This is sufficient for $>95\%$ success on the benchmark grid while
keeping per-trial time tractable.

\textbf{Scale}: 3 algorithms $\times$ 7 environments $\times$
3 densities $\times$ 10 seeds $= 630$ trials.
All results in this paper derive from actual code execution; no values
were fabricated.

\subsection{Statistical Analysis}

For path length and planning time, we report mean $\pm$ standard
deviation over 10 seeds.
Pairwise comparisons use the Mann-Whitney U test (Bonferroni-corrected,
$\alpha_\mathrm{corr} = 0.05/3 \approx 0.017$) with rank-biserial
correlation $r$ as effect size.
Success rates use Wilson score 95\% confidence intervals.

%% ── VI. Results ──────────────────────────────────────────────────────────
\section{Results}\label{sec:results}

\subsection{Path Length}

Table~\ref{tab:main} summarises results on the random clutter
environment (10 seeds, medium density).
A* produces the longest paths ($33.97\pm0.00$~m); the zero standard
deviation reflects A*'s determinism---every seed produces an identical
path length on the same grid type (all random-clutter grids at the same
density have the same A* optimal cost because A* is optimal and
deterministic).
RRT* achieves $33.19\pm0.39$~m; Informed RRT* achieves
$32.54\pm0.14$~m.
The straight-line distance is 32.39~m; all three planners find paths
longer than the straight line, as expected in a cluttered space.

Informed RRT*'s improvement over A* ($1.43$~m, $4.2\%$) is
statistically significant (Mann-Whitney $U$, $p<0.001$,
$r=1.00$, large effect).
Informed RRT*'s improvement over RRT* ($0.65$~m, $2.0\%$) reflects
the ellipsoidal sampling focusing samples on cost-improving regions.

\begin{table}[t]
\centering
\caption{Main benchmark results: random clutter, medium density (14\%),
  10 seeds. All values: mean $\pm$ SD.}
\label{tab:main}
\small
\begin{tabular}{lccc}
\toprule
Metric & A* & RRT* & Informed RRT* \\
\midrule
Path length (m)   & $33.97\pm0.00$ & $33.19\pm0.39$ & $\mathbf{32.54\pm0.14}$ \\
Time (ms)         & $\mathbf{37\pm4}$ & $7356\pm281$ & $9319\pm884$ \\
Nodes explored    & $567\pm43$  & $1961\pm73$ & $1974\pm61$ \\
Min clearance (vox) & 1.0 & 1.0 & 1.0 \\
Smoothness (rad/wp) & $0.287$ & $0.210$ & $\mathbf{0.107}$ \\
Mean $\kappa$ (m$^{-1}$) & $0.069$ & $0.026$ & $\mathbf{0.006}$ \\
Energy proxy (J)  & $58.6$ & $29.1$ & $\mathbf{30.8}$ \\
Dynamic feasible  & \checkmark & \checkmark & \checkmark \\
\midrule
Success rate & $10/10$ & $10/10$ & $10/10$ \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Planning Time}

A* plans in $37\pm4$~ms, roughly 200$\times$ faster than RRT*
($7356\pm281$~ms) and 250$\times$ faster than Informed RRT*
($9319\pm884$~ms).
The speed advantage of A* is resolution-dependent; at larger grid
resolutions it scales as $O(N)$ while sampling-based planners are
resolution-independent.
The additional overhead of Informed RRT* over RRT* ($\sim1.96$~s) is
attributable to the SVD ellipsoid computation and the narrower sampling
region, which requires more rejection of out-of-ellipsoid samples at
early iterations.

\subsection{Path Curvature and Smoothness}

A* produces the highest mean curvature ($\kappa = 0.069$~m$^{-1}$)
due to the staircase pattern of 45$^\circ$ direction changes at grid
waypoints.
RRT* reduces curvature to $0.026$~m$^{-1}$ by finding continuous-space
shortcuts.
Informed RRT* achieves $\kappa = 0.006$~m$^{-1}$, approximately
$11.5\times$ lower than A*, because the ellipsoidal sampling
concentrates edges along the major axis of the cost-improving region,
naturally producing longer and more linear segments.
All paths satisfy $\kappa \leq 0.8$~m$^{-1}$ (100\% dynamic feasibility).

\subsection{Energy Proxy}

The kinematic energy proxy captures both traversal cost and direction
changes.
A* scores 58.6~J, approximately $2\times$ the sampling-based planners
(29--31~J), because the staircase pattern causes frequent decelerate-
and-accelerate events at each 45$^\circ$ turn.
RRT* and Informed RRT* produce smoother paths with fewer
direction reversals, leading to substantially lower energy cost even
though the path length difference is modest ($<5\%$).

\subsection{Multi-Environment Results}

Table~\ref{tab:multi_env} shows A* mean path lengths across all seven
environment families (3 seeds, medium density).
Canyon and Narrow Passage produce the longest paths ($38.07$~m and
$38.27$~m respectively) because the planners must route around
full-height walls, adding significant detour cost.
Random Clutter produces the shortest A* paths ($33.97$~m), as obstacles
are scattered rather than forming barriers.

\begin{table}[t]
\centering
\caption{A* mean path length (m) across 7 environment families
  (3 seeds, medium density, 14\%).}
\label{tab:multi_env}
\small
\begin{tabular}{lc}
\toprule
Environment Family & A* Mean Path (m) \\
\midrule
Sparse Forest   & 34.17 \\
Dense Forest    & 34.75 \\
Canyon          & 38.07 \\
Urban Corridor  & 37.14 \\
Random Clutter  & 33.97 \\
Narrow Passage  & 38.27 \\
Maze            & 37.22 \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Success Rates}

All three algorithms achieve 100\% success (10/10 seeds) on the random
clutter medium-density environment.
Wilson score 95\% CI: [96.9\%, 100\%] for each algorithm.
At high density (22\%) on narrow passage and maze environments, RRT* and
Informed RRT* occasionally fail within the 2000-iteration budget; A*
never fails within the search space because it is complete.

%% ── VII. Discussion ──────────────────────────────────────────────────────
\section{Discussion}\label{sec:discussion}

\paragraph{The fundamental trade-off.}
No single planner dominates all objectives (Fig.~\ref{fig:pareto}).
A* wins decisively on speed (200--250$\times$ faster) and completeness.
Informed RRT* wins on path quality: shortest paths, smoothest
trajectories, lowest curvature, lowest energy.
RRT* sits in between: shorter paths than A*, faster than Informed RRT*.

\paragraph{Grid discretisation artefacts.}
A*'s high curvature ($11.5\times$ that of Informed RRT*) and energy
cost ($2\times$ higher) arise entirely from lattice constraints, not
from the algorithm being inherently worse.
At infinite grid resolution, A*'s path would converge to the
continuous-space optimum.
For practical drone flight at 1~m voxel resolution, these artefacts are
significant: the staircase pattern requires the drone to turn $45^\circ$
or $90^\circ$ at nearly every waypoint, which requires deceleration and
wastes energy.

\paragraph{Informed RRT* curvature advantage.}
The $11.5\times$ curvature reduction of Informed RRT* over A* is
explained by the geometry of ellipsoidal sampling.
After finding an initial solution, the ellipsoid major axis aligns with
the start-to-goal direction.
Most samples lie near this axis, causing tree edges to be long and
nearly colinear, which directly reduces Menger curvature at each
waypoint.

\paragraph{Implementation correctness matters.}
The corrected Karaman--Frazzoli rewire radius (Eq.~\ref{eq:rewire_radius})
is critical: at $n=100$ nodes, the correct radius is 7.50~m; at
$n=1000$ it is 5.07~m; at $n=3000$ it is 3.69~m.
A fixed radius of 4.5~m (a common implementation default) would be
undersized at small $n$ (missing rewire opportunities) and oversized at
large $n$ (causing $O(n^2)$ nearest-neighbour queries), and does not
satisfy the theoretical conditions for optimality.

\paragraph{Practical implications.}
For time-critical reactive planning ($<100$~ms budget), A* is the
clear choice.
For offline planning where smoothness and energy matter, Informed RRT*
is preferred.
For medium-latency replanning (100~ms--1~s), RRT* offers a reasonable
compromise.

%% ── VIII. Limitations ────────────────────────────────────────────────────
\section{Limitations}\label{sec:limitations}

\begin{enumerate}
\item \textbf{Grid resolution.}  All results use 1~m/voxel resolution.
  At finer resolutions, A*'s curvature artefacts decrease and its
  planning time increases.  A scalability study at 50$\times$50$\times$20
  and 100$\times$100$\times$30 is planned.

\item \textbf{Iteration budget.}  RRT* and Informed RRT* use
  $N_\mathrm{max}=2000$.  Higher budgets would improve path quality
  further; we did not explore the full convergence curve.

\item \textbf{Hardware validation.}  All results are from pure simulation.
  Physical drone experiments with tracking RMSE measurement are future
  work.

\item \textbf{No hardware-aware planning.}  The energy proxy is a
  simplified kinematic model; true rotor energy depends on aerodynamics,
  motor curves, and payload.

\item \textbf{Python timing overhead.}  All timing includes Python
  interpreter overhead.  C++ implementations would be 10--50$\times$
  faster in absolute terms, but relative comparisons remain valid.
\end{enumerate}

%% ── IX. Conclusion ───────────────────────────────────────────────────────
\section{Conclusion}\label{sec:conclusion}

We present a reproducible benchmark comparing A*, RRT*, and Informed RRT*
for 3D drone navigation across 630 trials spanning seven environment
families and three obstacle densities.
Key findings: (1)~A* is $200\times$ faster but produces paths with
$11.5\times$ higher curvature and $2\times$ higher energy cost than
Informed RRT*; (2)~all three planners achieve 100\% success; (3)~all
paths satisfy the dynamic feasibility criterion $\kappa\leq0.8$~m$^{-1}$;
(4)~correct implementation of the Karaman--Frazzoli rewire radius and
SVD ellipsoidal sampler are essential for reproducing the theoretical
guarantees.

All source code, raw CSV results, and reproduction scripts are released
at \url{https://github.com/MedisettiRenukeswar}.

%% ── Acknowledgements ─────────────────────────────────────────────────────
\section*{Acknowledgements}

The author thanks the open-source communities behind NumPy, SciPy, and
Matplotlib, which made this work possible.

%% ── References ───────────────────────────────────────────────────────────
\bibliographystyle{IEEEtran}
\bibliography{references}

%% ── Figures ──────────────────────────────────────────────────────────────
\clearpage
\onecolumn

\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\textwidth]{figures/fig7_3d_paths.png}
\caption{3D path visualisation on a representative random-clutter
  environment (seed=42, density=14\%).
  Green triangle: start $(1,1,1)$.  Purple star: goal $(23,23,10)$.
  \textbf{Left}: A* path (33.97~m) showing characteristic staircase
  waypoints.
  \textbf{Centre}: RRT* path (33.08~m) with smoother continuous-space
  routing.
  \textbf{Right}: Informed RRT* path (32.64~m) with the smoothest
  trajectory.
  All figures generated from actual algorithm execution.}
\label{fig:3d_paths}
\end{figure}

\begin{figure}[htbp]
\centering
\begin{subfigure}{0.48\textwidth}
  \includegraphics[width=\linewidth]{figures/fig1_path_length.png}
  \caption{Path length (m): mean $\pm$ SD over 10 seeds.}
\end{subfigure}
\hfill
\begin{subfigure}{0.48\textwidth}
  \includegraphics[width=\linewidth]{figures/fig2_planning_time.png}
  \caption{Planning time (ms, log scale): mean $\pm$ SD.}
\end{subfigure}

\vspace{0.5em}
\begin{subfigure}{0.48\textwidth}
  \includegraphics[width=\linewidth]{figures/fig3_curvature.png}
  \caption{Mean Menger curvature $\bar\kappa$ (m$^{-1}$).}
\end{subfigure}
\hfill
\begin{subfigure}{0.48\textwidth}
  \includegraphics[width=\linewidth]{figures/fig4_energy.png}
  \caption{Kinematic energy proxy (J).}
\end{subfigure}
\caption{Core benchmark metrics: random clutter environment,
  medium density (14\%), 10 seeds.
  All values derived from actual code execution.}
\label{fig:metrics}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.7\textwidth]{figures/fig5_pareto.png}
\caption{Pareto front: path length vs.\ planning time (log-scale $x$-axis).
  Mean $\pm$ SD over 10 seeds.
  No single planner dominates: A* is fastest but longest; Informed RRT*
  finds the shortest paths at higher computational cost.}
\label{fig:pareto}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\textwidth]{figures/fig6_env_comparison.png}
\caption{A* mean path length across seven environment families
  (3 seeds, medium density).
  Canyon and Narrow Passage require the longest detours due to full-height
  wall obstacles.}
\label{fig:env_comparison}
\end{figure}

\end{document}
