Lexicographic A*: Hierarchical Distance and Turn Optimization for Mobile Robots

Autonomous mobile robots require efficient path planning algorithms for navigation in grid-based environments. While the A* algorithm guarantees optimally short paths using admissible heuristics, it exhibits path degeneracy: multiple geometrically distinct paths often share identical length. Classical A* arbitrarily selects among these equal-cost candidates, frequently producing trajectories with excessive directional changes. Each turn induces deceleration–acceleration cycles that degrade energy efficiency and accelerate mechanical wear. To address this, we propose Turn-Minimizing A* (TM-A*), a lexicographic optimization approach that maintains distance optimality while minimizing cumulative heading changes. Unlike weighted-cost methods that require parameter calibration, TM-A* applies a dual-objective framework: distance takes strict priority, with turn count serving as a tie-breaker among equal-length paths. A key contribution of this work is the explicit guarantee that the generated path has the minimum number of turns among all shortest paths. By formulating path planning as a lexicographic optimization problem, TM-A* strictly prioritizes path length optimality and deterministically selects, among all equal-length candidates, the one with the fewest directional changes. Unlike classical A*, which arbitrarily resolves path degeneracy, TM-A* provably eliminates this ambiguity. As a result, the method ensures globally shortest paths with minimal turning, directly improving trajectory smoothness and operational efficiency. We prove that TM-A* preserves the O(|E|log|V|) time complexity of classical A*. Validation across 30 independent Monte Carlo trials at resolutions from 200 × 200 to 1000 × 1000 demonstrates that TM-A* reduces turn count by 39–43% relative to baseline A* (p < 0.001). Although the inclusion of orientation expands the search space four-fold, the computation time increases by only a factor of approximately 3 (≈200%), indicating efficient scalability relative to problem complexity. With absolute latency remaining below 3300 ms for 1000 × 1000 grids, the approach is highly suitable for static global planning. Consequently, TM-A* provides a deterministic and scalable solution for generating smooth trajectories in industrial mobile robot applications.