Variable differential neighborhood-based dynamic trajectory planning for automated vehicles

Yide QIAN, Yulin MA, Yicheng LI, Jiabao PAN, Shucai XU

Journal of Tsinghua University(Science and Technology) ›› 2026, Vol. 66 ›› Issue (8) : 1611-1624.

PDF(1968 KB)
PDF(1968 KB)
Journal of Tsinghua University(Science and Technology) ›› 2026, Vol. 66 ›› Issue (8) : 1611-1624. DOI: 10.16511/j.cnki.qhdxxb.2026.27.033
Vehicle and Traffic

Variable differential neighborhood-based dynamic trajectory planning for automated vehicles

Author information +
History +

Abstract

Objective: Aiming at the problems of low convex quality in single-neighborhood search, insufficient adaptability to dynamic obstacles, and poor controllability in multi-convex region switching for autonomous vehicle trajectory planning, this paper proposes a dynamic trajectory planning method based on Variable Differential Neighborhood Search (VDNS). The core objectives are to improve the coverage and quality of drivable convex space, enhance the smoothness of trajectory under neighborhood switching, and ensure the stability and convergence of multi-convex shape transition, so as to provide a safe, efficient and robust trajectory planning solution for autonomous driving in dynamic urban traffic scenarios. Methods: Firstly, a differential neighborhood model integrating vehicle kinematics and real-time environmental perception is established. By embedding the Maximum Volume Inscribed Ellipse method into the differential neighborhood search framework, the maximum differential neighborhood at the current moment is generated, which provides a strict lower bound of safe convex polyhedron space and balances the quality and efficiency of neighborhood generation. Secondly, a comprehensive evaluation function considering longitudinal driving distance, lateral deviation and safety margin is constructed, and an adaptive weight adjustment mechanism based on scene risk and motion urgency is introduced to realize the dynamic optimization of the next moment differential neighborhood. Then, the logarithmic barrier function is adopted to transform the trajectory smoothness optimization with inequality constraints into an unconstrained quadratic programming problem, and the Newton iteration method is used to solve it, which suppresses trajectory oscillation and meets vehicle dynamics constraints. Finally, the average dwell-time method is applied to establish the switching stability index of variable differential neighborhood search. Each differential neighborhood is regarded as an independent subsystem, and the sufficient conditions for exponential convergence of the switched system are derived to guarantee the controllability of multi-convex shape transition. Results: The joint simulation based on PreScan, Simulink and CarSim shows that: 1) Compared with the single-neighborhood search (NS) algorithm and iterative regional inflation (IRIS) algorithm, the proposed VDNS algorithm improves the coverage of drivable convex space by 20% in dynamic obstacle environment and 7% in static obstacle environment, with significantly enhanced heuristic search performance. 2) In two consecutive obstacle avoidance maneuvers, the convergence time of neighborhood switching stability is controlled within 0.6 s and 0.4 s, and the maximum velocity overshoot is only 1.00% and 2.94%, showing strong switching stability. 3) The trajectory generated by VDNS is continuous and smooth without oscillation, which overcomes the shortage of poor smoothness in traditional IRIS algorithm. 4) With the increase of obstacle number, the single-step time complexity of VDNS is lower than that of IRIS, and the computational efficiency is higher in complex environments. 5) The adaptive weight mechanism achieves better balance among safety, efficiency and smoothness, which is superior to the fixed weight strategy in trajectory quality and obstacle avoidance performance. Conclusions: The VDNS-based dynamic trajectory planning method effectively improves the convex quality of neighborhood search and the controllability of multi-convex region switching. It not only expands the drivable convex space and enhances the dynamic adaptability to obstacles, but also ensures the smoothness of trajectory and the stability of neighborhood switching. This method can be applied to urban dynamic traffic scenarios with static and dynamic obstacles, and provides a new technical approach for real-time, safe and reliable trajectory planning of autonomous vehicles.

Key words

planning and control for automated vehicles / variable differential neighborhood / maximum volume inscribed ellipse / average dwell time / trajectory smoothness

Cite this article

Download Citations
Yide QIAN , Yulin MA , Yicheng LI , et al . Variable differential neighborhood-based dynamic trajectory planning for automated vehicles[J]. Journal of Tsinghua University(Science and Technology). 2026, 66(8): 1611-1624 https://doi.org/10.16511/j.cnki.qhdxxb.2026.27.033

References

1
孙航, 张路, 季国田. 智能网联汽车标准体系及重点标准研究与展望[J]. 汽车安全与节能学报, 2024, 15(6): 795- 812.
SUN H, ZHANG L, JI G T. Research and prospect of intelligent and connected vehicles standard system and key standards[J]. Journal of Automotive Safety and Energy, 2024, 15(6): 795- 812.
2
王星, 赵海良, 王志刚. 基于邻域系统的智能车辆最优轨迹规划方法[J]. 智能系统学报, 2019, 14(5): 1040- 1047.
WANG X, ZHAO H L, WANG Z G. Optimal trajectory planning method of intelligent vehicles based on neighborhood system[J]. CAAI Transactions on Intelligent Systems, 2019, 14(5): 1040- 1047.
3
张雪莉. 基于邻域系统的室内移动机器人路径规划方法[D]. 成都: 西南交通大学, 2020.
ZHANG X L. Path planning method of indoor mobile robot based on neighborhood system[D]. Chengdu: Southwest Jiaotong University, 2020. (in Chinese)
4
周兴珍, 裴晓飞, 张鑫康. 基于可达集优化的智能汽车轨迹规划研究[J]. 武汉理工大学学报, 2022, 44(6): 39- 48.
ZHOU X Z, PEI X F, ZHANG X K. Trajectory planning of intelligent vehicle based on reachable set and optimization[J]. Journal of Wuhan University of Technology, 2022, 44(6): 39- 48.
5
ZHANG Z W, YANG R C, WU K, et al. Drive in corridors: Enhancing the safety of end-to-end autonomous driving via corridor learning and planning[J]. IEEE Robotics and Automation Letters, 2025, 10(7): 6728- 6735.
6
WANG W J, ZHANG T T, SONG Z H, et al. Trajectory optimization with dynamic drivable corridor-based collision avoidance[J]. Applied Sciences, 2025, 15(13): 7051.
7
WANG Q H, WANG Z P, WANG M Y, et al. Fast iterative region inflation for computing large 2-D/3-D convex regions of obstacle-free space[J]. IEEE Transactions on Robotics, 2025, 41, 3223- 3243.
8
WERNER P, COHN T, JIANG R H, et al. Faster algorithms for growing collision-free convex polytopes in robot configuration space[EB/OL]. (2024-10-18) [2025-06-16]. https://doi.org/10.48550/arXiv.2410.12649.
9
HUBMANN C, SCHULZ J, BECKER M, et al. Automated driving in uncertain environments: Planning with interaction and uncertain maneuver prediction[J]. IEEE Transactions on Intelligent Vehicles, 2018, 3(1): 5- 17.
10
李振璧, 贾汉坤, 李学洋. 切换系统有限时间稳定的事件触发滑模控制[J]. 华中科技大学学报(自然科学版), 2020, 48(2): 109- 114.
LI Z B, JIA H K, LI X Y. Event-triggered sliding control of finite-time stability for switched systems[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2020, 48(2): 109- 114.
11
史爽, 费中阳, 赵旭东. 基于时间依赖切换信号的切换系统稳定性分析研究进展[J]. 信息与控制, 2021, 50(1): 34- 42.
SHI S, FEI Z Y, ZHAO X D. Advances on stability analysis for switched systems with time-dependent switching signals[J]. Information and Control, 2021, 50(1): 34- 42.
12
高娟, 李同彬. 非线性扰动的切换系统的异步控制: 模态依赖的平均驻留时间方法[J]. 工程数学学报, 2022, 39(6): 899- 909.
GAO J, LI T B. Asynchronous control of switched systems with nonlinear perturbation: A mode-dependent average dwell time approach[J]. Chinese Journal of Engineering Mathematics, 2022, 39(6): 899- 909.
13
LIN C H, WU R Y, MA W K, et al. Maximum volume inscribed ellipsoid: A new simplex-structured matrix factorization framework via facet enumeration and convex optimization[J]. SIAM Journal on Imaging Sciences, 2018, 11(2): 1651- 1679.
14
PETERSEN M, TEDRAKE R. Growing convex collision-free regions in configuration space using nonlinear programming[EB/OL]. (2023-03-26) [2025-06-16]. https://arxiv.org/abs/2303.1473.
15
LI B, OUYANG Y K, LI L, et al. Autonomous driving on curvy roads without reliance on Frenet Frame: A Cartesian-based trajectory planning method[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(9): 15729- 15741.
16
MA Y L, LI Z X, MALEKIAN R, et al. A novel multimode hybrid control method for cooperative driving of an automated vehicle platoon[J]. IEEE Internet of Things Journal, 2021, 8(7): 5822- 5838.
17
ZOU T, LI H Q, ZHANG X X, et al. Complexity simulation of DMC based on quadratic programming[C]//Proceedings of the 30th Chinese Control Conference. Yantai, China: IEEE, 2011: 335–339.

RIGHTS & PERMISSIONS

All rights reserved. Unauthorized reproduction is prohibited.
PDF(1968 KB)

Accesses

Citation

Detail

Sections
Recommended

/