A* 3D

Problem Statement

A* provides deterministic, optimal graph search for 3D occupancy grids when an admissible heuristic is available.

Model and Formulation

Node selection minimizes:

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

with path cost g and heuristic h to goal (typically Euclidean distance in 3D).

Practical Notes

• Heuristic admissibility preserves optimality guarantees.
• Performance depends on branching factor and map resolution.
• Path smoothing is often needed post-search for flyability.

Implementation and Execution

python -m uav_sim.simulations.path_planning.astar_3d

Evidence

References

• Hart, Nilsson, Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths (1968)
• LaValle, Planning Algorithms

Related Algorithms

• RRT* 3D
• Costmap Navigation