A Two-Stage Search Framework for Formation Transition of Vehicle Platoons under Dynamic Traffic

In the era of intelligent transportation systems (ITS), autonomous vehicle platooning offers substantial potential to enhance road safety, improve traffic efficiency, and reduce emissions. However, existing research is largely confined to fixed formation control and relies on simplified disturbance models for dynamic traffic environments, limiting real-world adaptability. To address these gaps, we propose a two-stage grid-based formation transition framework tailored for dynamic traffic scenarios with external vehicle disturbances, designed to minimize transition steps while ensuring real-time adaptability and safety. In the first stage, we formalize the formation transition problem as a shortest-path search in a discrete grid context and develop an A*-based offline algorithm to generate an optimal sequence of intermediate formations, enabling simultaneous vehicle movements to reduce total transition steps. In the second stage, to handle dynamic EV disturbances in the context of grid-based formulation, we design a Discrete Grid-Based Dynamic Spatiotemporal Occupancy Model for External Vehicles (DGSOM-EV) that proactively forecasts EV grid occupancy over multiple time steps. Leveraging this model, we further modify the D* Lite algorithm with four modifications to integrate grid-specific spatiotemporal conflict detection and high-risk grid marking mechanisms, enabling real-time incremental adjustment of the offline-generated formation sequence to avoid dynamic EVs. Simulations validate the framework’s robustness at maximum 100% external vehicle penetration, reducing transition steps by 38–56% against baselines while maintaining ≤ 146.2 ms planning time and ≥ 97.5% grid conflict avoidance across small and large-scale scenarios, demonstrating superior real-time adaptability, safety, and practical viability for dynamic traffic environments.