基于图搜索与优化的动态非结构环境智能车辆轨迹规划

doi:10.19562/j.chinasae.qcgc.2024.09.004

Abstract

Abstract:

A trajectory planning method based on graph search and optimization is proposed for intelligent vehicle trajectory planning in dynamic unstructured environments. Firstly， the graph search method is employed to search for motion primitives for intelligent vehicles to obtain initial trajectories that conform to kinematic characteristics. Then， based on nonlinear model predictive control methods， the trajectory is optimized to obtain smoother and safer trajectories. In order to achieve rapid and secure expansion of primitives in dynamic unstructured environments， a method for primitive collision detection is proposed. This method uses obstacle expansion and grid discrete motion elements to perform static collision detection on irregular obstacles， and introduces in the concept of velocity obstacles to perform dynamic collision detection on dynamic obstacles in velocity space. The proposed algorithm is compared by simulations in ROS/Gazebo environment， and is evaluated by field tests. The results show that compared to the TEB algorithm， the proposed trajectory planning method improves the average obstacle avoidance success rate by 18% while meeting the real-time computing requirements， demonstrating higher safety obstacle avoidance ability and feasibility.

Key words: intelligent vehicle, unstructured environment, dynamic environment, obstacle avoidance

Xiujian Yang,Yongrui Bai. Trajectory Planning for Intelligent Vehicle in Dynamic Unstructured Environment Based on the Graph Search and Optimization Methods[J].Automotive Engineering, 2024, 46(9): 1564-1575.

Figures/Tables 17

References 21

1	PADEN B， CAP M， YONG S Z， et al. A survey of motion planning and control techniques for self-driving urban vehicles［J］. IEEE Transactions on Intelligent Vehicles， 2016， 1（1）： 33-55.
2	CHIANG H T， HOMCHAUDHURI B， SMITH L， et al. Safety， challenges， and performance of motion planners in dynamic environments［C］// AMATO N M， HAGER G， THOMAS S， et al. Robotics research. Cham： Springer International Publishing， 2020： 793-808.
3	WANG H， HUANG Y， KHAJEPOUR A， et al. Crash mitigation in motion planning for autonomous vehicles［J］. IEEE Transactions on Intelligent Transportation Systems， 2019， 20（9）： 3313-3323.
4	田洪清，丁峰，郑讯佳，等. 基于势能场虚拟力的智能网联车辆运动规划［J］. 汽车工程， 2021， 43（4）： 518-526.
	TIAN H Q， DING F， ZHENG X J， et al. Motion planning based on virtual force of potential field for intelligent connected vehicles［J］. Automotive Engineering， 2021， 43（4）： 518-526.
5	KIM J， KIM K， JO K. Obstacle avoidance in dynamic environment using particle swarm optimization and Kalman filter［C］. 2023 23rd International Conference on Control， Automation and Systems （ICCAS）， 2023： 1199-1203.
6	郝琨，张慧杰，李志圣，等. 基于改进避障策略和双优化蚁群算法的机器人路径规划［J］. 农业机械学报， 2022， 53（8）： 303-312.
	HAO K， ZHANG H J， LI Z S， et al. Path planning of mobile robot based on improved obstacle avoidance strategy and double optimization ant colony algorithm［J］.Transactions of the Chinese Society for Agricultural Machinery，2022，53（8）：303-312.
7	胡小建，周琼，宋旭东，等. 基于时间窗约束的多人多储位拣选路径优化模型及改进遗传算法应用研究［J］. 计算机集成制造系统， 2022， 28（11）： 3354-3364.
	HU X J， ZHOU Q， SONG X D， et al. Optimal model of multi-person and multi-location picking path based on time window constraint and application of improved genetic algorithm［J］. Computer Integrated Manufacturing System， 2022， 28（11）： 3354-3364.
8	JIAN Z， YAN Z， LEI X， et al. Dynamic control barrier function-based model predictive control to safety-critical obstacle-avoidance of mobile robot［C］. 2023 IEEE International Conference on Robotics and Automation （ICRA）. IEEE， 2023： 3679-3685.
9	李军，周伟，唐爽. 基于自适应拟合的智能车换道避障轨迹规划［J］. 汽车工程， 2023， 45（7）： 1174-1183.
	LI J， ZHOU W， TANG S. Lane change and obstacle avoidance trajectory planning of intelligent vehicle based on adaptive fitting［J］. Automotive Engineering， 2023， 45（7）： 1174-1183.
10	LI G， ZHANG X， GUO H， et al. Real-time optimal trajectory planning for autonomous driving with collision avoidance using convex optimization［J］. Automotive Innovation， 2023， 6（3）： 481-491.
11	SINTOV A， SHAPIRO A. Time-based RRT algorithm for rendezvous planning of two dynamic systems［C］. 2014 IEEE International Conference on Robotics and Automation （ICRA）， 2014： 6745-6750.
12	XIN L， KONG Y， LI S E， et al. Enable faster and smoother spatio-temporal trajectory planning for autonomous vehicles in constrained dynamic environment［J］. Proceedings of the Institution of Mechanical Engineers， Part D： Journal of Automobile Engineering， 2021， 235（4）： 1101-1112.
13	齐尧，朱彦齐，李永乐，等. 面向动静态混合环境的智能车运动规划方法［J］. 交通运输系统工程与信息， 2022， 22（4）： 293-301.
	QI Y， ZHU Y Q， LI Y L， et al. Motion planning method for intelligent vehicles under constrained dynamic and static environment［J］. Journal of Transportation Systems Engineering and Information Technology， 2022， 22（4）： 293-301.
14	胡杰，张志豪，陈瑞楠，等. 基于改进混合A*的智能汽车时空联合规划方法［J］. 汽车工程， 2023， 45（7）： 1123-1133.
	HU J， ZHANG Z H， CHEN R N， et al. Spatio-temporal joint planning method of intelligent vehicles based on improved hybrid A*［J］. Automotive Engineering， 2023， 45（7）： 1123-1133.
15	PETTI S， FRAICHARD T. Safe motion planning in dynamic environments［C］. 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE， 2005： 2210-2215.
16	AMANATIDES J， WOO A. A fast voxel traversal algorithm for ray tracing［C］. Eurographics， 1987， 87（3）： 3-10.
17	BAUTIN A， MARTINEZ-GOMEZ L， FRAICHARD T. Inevitable collision states： a probabilistic perspective［C］. 2010 IEEE International Conference on Robotics and Automation， 2010： 4022-4027.
18	LIN J， ZHOU T， ZHU D， et al. Search-based online trajectory planning for car-like robots in highly dynamic environments［C］. 2021 IEEE International Conference on Robotics and Automation （ICRA）. IEEE， 2021： 8151-8157.
19	ANDERSSON J A E， GILLIS J， HORN G， et al. CasADi-a software framework for nonlinear optimization and optimal control［J］. Mathematical Programming Computation， 2019， 11（1）： 1-36.
20	WÄCHTER A， BIEGLER L T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming［J］. Mathematical Programming， 2006， 106： 25-57.
21	YAN Z， DUCKETT T， BELLOTTO N. Online learning for 3D LiDAR-based human detection： experimental analysis of point cloud clustering and classification methods［J］. Autonomous Robots， 2020， 44（2）： 147-164.

参数	数值
车长/m	1.92
轴距L/m	1.33
车宽/m	1.02
单个栅格边长/m	0.20
剪枝网格边长/m	0.20
拓展步长τ/s	0.8
速度范围/（m·s^-1）	［-3， 3］
最大搜索时间/ms	100
离散加速度集合/（m·s^-2）	｛-0.5， -0.25， 0.0， 0.25， 0.5｝
离散前轮转角集合/（°）	｛-28， -21， -14， -7， 0， 7， 14， 21， 28｝

场景	评价过程	平均耗时/ms
仿真动态场景	TEB算法全过程	23
	本文算法初始轨迹搜索过程	8
	本文算法轨迹优化过程	50
	本文算法全过程	58
单障碍物场景	TEB算法全过程	10
	本文算法初始轨迹搜索过程	5
	本文算法轨迹优化过程	36
	本文算法全过程	41

剪枝网格边长/m	耗时	搜索过程耗时/ms	优化过程耗时/ms	全过程耗时/ms
0.4	平均耗时	4	52	56
	最大耗时	101	136	178
	最小耗时	1	20	21
0.2	平均耗时	8	50	58
	最大耗时	101	86	156
	最小耗时	1	26	27
0.1	平均耗时	14	53	67
	最大耗时	65	119	132
	最小耗时	3	27	30

参数	数值
车长/m	1.92
轴距L/m	1.33
车宽/m	1.02
单个栅格边长/m	0.20
剪枝网格边长/m	0.20
拓展步长τ/s	0.8
速度范围/（m·s^-1）	［-1.5， 1.5］
最大搜索时间/ms	100
离散加速度集合/（m·s^-2）	｛-0.5， -0.25， 0.0， 0.25， 0.5｝
离散前轮转角集合/（°）	｛-28， -21， -14， -7， 0， 7， 14， 21， 28｝

[1]	Xianghao Meng,Ling Niu,Junqiang Xi,Danni Chen,Chao Lü. Risk Prediction of Heterogeneous Traffic Participants Based on Spatio-Temporal Graph Neural Networks [J]. Automotive Engineering, 2024, 46(9): 1537-1545.
[2]	Jing Zhao,Hao Liang,Tianxiao Xu,Yayue Xiao,Bowen Jiang. Research on Domain Specific Modeling Language for Intelligent Vehicle Cyber-Physical System [J]. Automotive Engineering, 2024, 46(8): 1370-1381.
[3]	Jialiang Zhu,Qiaobin Liu,Fan Yang,Lu Yang,Weihua Li. Two-Dimensional Collision Risk Prediction for Intelligent Vehicles Considering the Influence of Heterogeneous Vehicle Types [J]. Automotive Engineering, 2024, 46(8): 1414-1421.
[4]	Xiaolin Fan,Xudong Zhang,Yuan Zou,Xin Yin,Yingqun Liu. A Mapping and Planning Method Based on Simplified Visibility Graph [J]. Automotive Engineering, 2024, 46(7): 1249-1258.
[5]	Junyu Zhou,Keqiang Li,Hanxiao Ren,Jie Yu,Yugong Luo. A Cooperative Obstacle Avoidance Lane Change Strategy for Intelligent and Connected Vehicles Based on Scene Division [J]. Automotive Engineering, 2024, 46(5): 745-753.
[6]	Jiqing Chen,Yuxiang Che,Xiaoqiang Tian,Fengchong Lan,Yunjiao Zhou. Research on Real-Time Visual SLAM Method Based on 3D Multi-Object Tracking in Dynamic Scenes [J]. Automotive Engineering, 2024, 46(5): 776-783.
[7]	Shuen Zhao,Sheng Wang,Yao Leng. Multi-objective Explicit Model Predictive Control for Intelligent Vehicle Trajectory Tracking [J]. Automotive Engineering, 2024, 46(5): 784-794.
[8]	Bing Zhu,Yinzi Huang,Jian Zhao,Peixing Zhang,Jingwei Xue. A Criticality Assessment Model for the Intelligent Vehicle Test Scenario Based on the Onboard Camera Images [J]. Automotive Engineering, 2024, 46(4): 557-563.
[9]	Ting Chikit,Yafei Wang,Yichen Zhang,Mingyu Wu,Yile Wang. Energy-Saving Planning Method for Autonomous Driving Mining Trucks Based on Composite Dynamic Sampling [J]. Automotive Engineering, 2024, 46(4): 588-595.
[10]	Xiaojian Wu,Pingwei Liao,Yao Lei,Huihua Jiang,Aichun Wang,Jiaqi Hu. Research on Consistency of Intelligent Driving Trajectory Planning for Structured Road [J]. Automotive Engineering, 2024, 46(3): 383-395.
[11]	Jianping Hao,Yanzhao Su,Zhihua Zhong,Jin Huang. Service-Oriented Architecture and Service Scheduling Mechanism for Intelligent Vehicles [J]. Automotive Engineering, 2023, 45(9): 1563-1572.
[12]	Gaoshi Zhao,Long Chen,Yingfeng Cai,Yubo Lian,Hai Wang,Qingchao Liu,Chenglong Teng. Trajectory Prediction Technology Integrating Complex Network and Memory-Augmented Network [J]. Automotive Engineering, 2023, 45(9): 1608-1616.
[13]	Lin Hu,Gen Li,Fang Wang,Miao Lin,Ning Wu. Research on Test Scenarios of Passenger Cars and Two-Wheelers at Intersections Based on CIDAS Accident Data [J]. Automotive Engineering, 2023, 45(8): 1417-1427.
[14]	Feng Gao,Defu Feng,Qiuxia Hu. Accelerating Technologies of Numerical Optimization for Motion Planning Designed by Nonlinear Model Predictive Control [J]. Automotive Engineering, 2023, 45(8): 1438-1447.
[15]	Qihui Hu,Yingfeng Cai,Hai Wang,Long Chen,Zhaozhi Dong,Qingchao Liu. Heterogeneous Multi-object Trajectory Prediction Method Based on Hierarchical Graph Attention [J]. Automotive Engineering, 2023, 45(8): 1448-1456.

Trajectory Planning for Intelligent Vehicle in Dynamic Unstructured Environment Based on the Graph Search and Optimization Methods

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 17

References 21

Related Articles 15

Metrics

Comments

Recommended 0