V*: An Efficient Motion Planning Algorithm for Autonomous Vehicles

Autonomous vehicle navigation in structured environments requires planners capable of generating time-optimal, collision-free trajectories that satisfy dynamic and kinematic constraints. We introduce V*, a graph-based motion planner that represents speed and direction as explicit state variables within a discretised space-time-velocity lattice. Unlike traditional methods that decouple spatial search from dynamic feasibility or rely on post-hoc smoothing, V* integrates both motion dimensions directly into graph construction through dynamic graph generation during search expansion. T o manage the complexity of high-dimensional search, we employ a hexagonal discretisation strategy and provide formal mathematical proofs establishing optimal waypoint spacing and minimal node redundancy under constrained heading transitions for velocity-aware motion planning. We develop a mathematical formulation for transient steering dynamics in the kinematic bicycle model, modelling steering angle convergence with exponential behaviour, and deriving the relationship for convergence rate parameters. We further demonstrate V*'s performance in simulation studies with cluttered and dynamic environments involving moving obstacles, showing its ability to avoid conflicts, yield proactively, and generate safe, efficient trajectories with temporal reasoning capabilities for waiting behaviours and dynamic coordination. Autonomous navigation requires planning algorithms that can compute time-efficient and dynamically feasible trajectories. Among the diverse approaches to motion planning, optimal pathfinding algorithms are recognized for their ability to guarantee high-quality solutions by minimizing path costs under strict constraints. This makes them particularly valuable in environments where precision and efficiency are critical. Classical pathfinding methods such as the Dijkstra ( 1) and A* ( 2) algorithms have been widely adopted for solving shortest path problems on graphs due to their efficiency.