Intelligent computing budget allocation for on-road trajectory planning based on candidate curves

Xiao-xin FU; Yong-heng JIANG; De-xian HUANG; Jing-chun WANG; Kai-sheng HUANG

doi:10.1631/FITEE.1500269

Your Location：

Home >

Browse articles >

Intelligent computing budget allocation for on-road trajectory planning based on candidate curves

Regular Papers | Updated：2022-05-19

- Intelligent computing budget allocation for on-road trajectory planning based on candidate curves
- 基于候选曲线的公路轨迹规划中的智能计算量分配
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 6, Pages: 553-565(2016)
- Affiliations：
  
  1Department of Automation, Tsinghua University, Beijing 100084, China
  2Department of Automotive Engineering, Tsinghua University, Beijing 100084, China
- Author bio：
  
  E-mail:fuxx10@mails.tsinghua.edu.cn
  E-mail:jiangyh@tsinghua.edu.cn
- Funds：
- DOI：10.1631/FITEE.1500269
  CLC： TP242.6
- Received：18 August 2015，
  
  Accepted：29 January 2016，
  
  Published：2016-06
- Accepted：
Scan QR Code
Xiao-xin FU, Yong-heng JIANG, De-xian HUANG, et al. Intelligent computing budget allocation for on-road trajectory planning based on candidate curves[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(6): 553-565.
DOI：

Xiao-xin FU, Yong-heng JIANG, De-xian HUANG, et al. Intelligent computing budget allocation for on-road trajectory planning based on candidate curves[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(6): 553-565. DOI： 10.1631/FITEE.1500269.

摘要

目的

公路轨迹规划是辅助驾驶和无人驾驶领域中的关键问题。为解决该问题，作者针对传统方法（如势场法、RRT）在求解质量和求解效率方面的不足，提出基于候选曲线的规划算法OODE。OODE分轨迹曲线和加速度变化两部分规划轨迹，采用差分进化（DE）算法通过求解子问题计算各候选曲线的评价，然后通过比较曲线评价从候选者中选取最优曲线。DE的迭代次数越多，曲线评价越准确。本文考虑对不同曲线智能分配迭代计算量，以减少总计算量消耗，同时保证所选最优曲线以足够高的概率是真实最优曲线，从而提高OODE算法的效率。

创新点

提出基于智能计算量分配（ICBA）的轨迹规划算法框架；设计曲线评价预测模型和优质曲线选拔模型，提出基于ICBA的轨迹规划算法IOODE。

方法

基于对优质曲线迭代分配计算量的思想，设计智能计算量分配（ICBA）机制，提出基于ICBA的轨迹规划算法框架（图4）；设计曲线评价预测模型（EPM）和优质曲线选拔模型（CSM），提出基于ICBA的轨迹规划算法IOODE；通过仿真分析IOODE算法的轨迹规划结果（图9、10），验证所提出计算量分配机制的有效性（图12、13）和ICBA对算法效率的提升作用（图14、表5）。

结论

本文中提出的IOODE算法与OODE算法相比，求解质量没有明显区别，但求解速度提升约20%（表5）。

Abstract

In this paper

on-road trajectory planning is solved by introducing intelligent computing budget allocation (ICBA) into a candidate-curve-based planning algorithm

namely

ordinal-optimization-based differential evolution (OODE). The proposed algorithm is named IOODE with ‘I’ representing ICBA. OODE plans the trajectory in two parts: trajectory curve and acceleration profile. The best trajectory curve is picked from a set of candidate curves

where each curve is evaluated by solving a subproblem with the differential evolution (DE) algorithm. The more iterations DE performs

the more accurate the evaluation will become. Thus

we intelligently allocate the iterations to individual curves so as to reduce the total number of iterations performed. Meanwhile

the selected best curve is ensured to be one of the truly top curves with a high enough probability. Simulation results show that IOODE is 20% faster than OODE while maintaining the same performance in terms of solution quality. The computing budget allocation framework presented in this paper can also be used to enhance the efficiency of other candidate-curve-based planning methods.

关键词

Keywords

references

L Bai , , , Y Jiang , , , D Huang . . A novel two-level optimization framework based on constrained ordinal optimization and evolutionary algorithms for scheduling of multipipeline crude oil blending . . Ind. Eng. Chem. Res. , , 2012 . . 51 ( ( 26 ): ): 9078 - - 9093 . . DOI: 10.1021/ie202224w http://doi.org/10.1021/ie202224w . .

RE Bechhofer , , , TJ Santner , , , DM Goldsman . . Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons . . Wiley, New York, USA , , 1995 . . .

K Bengler , , , K Dietmayer , , , B Farber , , , 等 . . Three decades of driver assistance systems: review and future perspectives . . IEEE Intell. Transp. Syst. Mag. , , 2014 . . 6 ( ( 4 ): ): 6 - - 22 . . DOI: 10.1109/MITS.2014.2336271 http://doi.org/10.1109/MITS.2014.2336271 . .

J Branke , , , SE Chick , , , C Schmidt . . Selecting a selection procedure . . Manag. Sci. , , 2007 . . 53 ( ( 12 ): ): 1916 - - 1932 . . DOI: 10.1287/mnsc.1070.0721 http://doi.org/10.1287/mnsc.1070.0721 . .

C Chen , , , LH Lee . . Stochastic Simulation Optimization: an Optimal Computing Budget Allocation . . World Scientific, USA , , 2010 . . .

C Chen , , , E Yüesan . . An alternative simulation budget allocation scheme for efficient simulation . . Int.J. Simul. Process Model. , , 2005 . . 1 ( ( 1/2 ): ): 49 - - 57 . . DOI: 10.1504/IJSPM.2005.007113 http://doi.org/10.1504/IJSPM.2005.007113 . .

C Chen , , , J Lin , , , E Yücesan , , , 等 . . Simulation budget allocation for further enhancing the efficiency of ordinal optimization . . Discr. Event Dyn. Syst. , , 2000 . . 10 ( ( 3 ): ): 251 - - 270 . . DOI: 10.1023/A:1008349927281 http://doi.org/10.1023/A:1008349927281 . .

C Chen , , , SE Chick , , , LH Lee , , , 等 . . Ranking and selection: efficient simulation budget allocation . . In: Fu, M.C. (Ed.), Handbook of Simulation Optimization. Springer, New York, USA , , 2015 . . DOI: 10.1007/978-1-4939-1384-8_3 http://doi.org/10.1007/978-1-4939-1384-8_3 . .

SE Chick , , , K Inoue . . New two-stage and sequential procedures for selecting the best simulated system . . Oper. Res. , , 2001 . . 49 ( ( 5 ): ): 732 - - 743 . . DOI: 10.1287/opre.49.5.732.10615 http://doi.org/10.1287/opre.49.5.732.10615 . .

K Chu , , , M Lee , , , M Sunwoo . . Local path planning for off-road autonomous driving with avoidance of static obstacles . . IEEE Trans. Intell. Transp. Syst. , , 2012 . . 13 ( ( 4 ): ): 1599 - - 1616 . . DOI: 10.1109/TITS.2012.2198214 http://doi.org/10.1109/TITS.2012.2198214 . .

X Fu , , , Y Jiang , , , D Huang , , , 等 . . A novel real-time trajectory planning algorithm for intelligent vehicles . . Contr. Dec. , , 2015 . . 30 ( ( 10 ): ): 1751 - - 1758 . . . .

SK Gehrig , , , FJ Stein . . Collision avoidance for vehicle-following systems . . IEEE Trans. Intell. Transp. Syst. , , 2007 . . 8 ( ( 2 ): ): 233 - - 244 . . DOI: 10.1109/TITS.2006.888594 http://doi.org/10.1109/TITS.2006.888594 . .

S Glaser , , , B Vanholme , , , S Mammar , , , 等 . . Maneuver-based trajectory planning for highly autonomous vehicles on real road with traffic and driver interaction . . IEEE Trans. Intell. Transp. Syst. , , 2010 . . 11 ( ( 3 ): ): 589 - - 606 . . DOI: 10.1109/TITS.2010.2046037 http://doi.org/10.1109/TITS.2010.2046037 . .

J Hilgert , , , K Hirsch , , , T Bertram , , , 等 . . Emergency path planning for autonomous vehicles using elastic band theory . . Proc. IEEE/ASME Int. Conf. on Advanced Intelligent Mechatronics , , 2003 . . 1390 - - 1395 . . DOI: 10.1109/AIM.2003.1225546 http://doi.org/10.1109/AIM.2003.1225546 . .

Y Ho , , , Q Zhao , , , Q Jia . . Ordinal Optimization: Soft Optimization for Hard Problems . . Springer, New York,USA , , 2007 . . DOI: 10.1007/978-0-387-68692-9 http://doi.org/10.1007/978-0-387-68692-9 . .

S Kim , , , BL Nelson . . A fully sequential procedure for indifference-zone selection in simulation . . ACM Trans. Model. Comput. Simul. , , 2001 . . 11 ( ( 3 ): ): 251 - - 273 . . DOI: 10.1145/502109.502111 http://doi.org/10.1145/502109.502111 . .

S Köhler , , , B Schreiner , , , S Ronalter , , , 等 . . Autonomous evasive maneuvers triggered by infrastructure-based detection of pedestrian intentions . . Proc. IEEE Intelligent Vehicles Symp. , , 2013 . . 519 - - 526 . . DOI: 10.1109/IVS.2013.6629520 http://doi.org/10.1109/IVS.2013.6629520 . .

Y Kuwata , , , J Teo , , , G Fiore , , , 等 . . Real-time motion planning with applications to autonomous urban driving . . IEEE Trans. Contr. Syst. Technol. , , 2009 . . 17 ( ( 5 ): ): 1105 - - 1118 . . DOI: 10.1109/TCST.2008.2012116 http://doi.org/10.1109/TCST.2008.2012116 . .

L Ma , , , J Xue , , , K Kawabata , , , 等 . . Efficient sampling-based motion planning for on-road autonomous driving . . IEEE Trans. Intell. Transp. Syst. , , 2015 . . 16 ( ( 4 ): ): 1961 - - 1976 . . DOI: 10.1109/TITS.2015.2389215 http://doi.org/10.1109/TITS.2015.2389215 . .

M McNaughton , , , C Urmson , , , JM Dolan , , , 等 . . Motion planning for autonomous driving with a conformal spatiotemporal lattice . . Proc. IEEE Int. Conf. on Robotics and Automation , , 2011 . . 4889 - - 4895 . . DOI: 10.1109/ICRA.2011.5980223 http://doi.org/10.1109/ICRA.2011.5980223 . .

M Montemerlo , , , J Becker , , , S Bhat , , , 等 . . Junior: the Stanford entry in the urban challenge . . J. Field Robot. , , 2008 . . 25 ( ( 9 ): ): 569 - - 597 . . DOI: 10.1002/rob.20258 http://doi.org/10.1002/rob.20258 . .

I Papadimitriou , , , M Tomizuka . . Fast lane changing computations using polynomials . . Proc. American Control Conf. , , 2003 . . 48 - - 53 . . DOI: 10.1109/ACC.2003.1238912 http://doi.org/10.1109/ACC.2003.1238912 . .

JH Reif . . Complexity of the mover’s problem and generalizations . . Proc. 20th Annual Symp. on Foundations of Computer Science , , 1979 . . 421 - - 427 . . DOI: 10.1109/SFCS.1979.10 http://doi.org/10.1109/SFCS.1979.10 . .

C Urmson , , , J Anhalt , , , D Bagnell , , , 等 . . Autonomous driving in urban environments: boss and the urban challenge . . J. Field Robot. , , 2008 . . 25 ( ( 8 ): ): 425 - - 466 . . DOI: 10.1002/rob.20255 http://doi.org/10.1002/rob.20255 . .

J Ziegler , , , C Stiller . . Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios . . Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems , , 2009 . . 1879 - - 1884 . . DOI: 10.1109/IROS.2009.5354448 http://doi.org/10.1109/IROS.2009.5354448 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system

A double-layered nonlinear model predictive control based control algorithm for local trajectory planning for automated trucks under uncertain road adhesion coefficient conditions

Related Author

Pei-qiu HUANG

Yong WANG

Ke-zhi WANG

Hong-chao WANG

Wei-wei ZHANG

Xun-cheng WU

Hao-tian CAO

Qiao-ming GAO

Related Institution

School of Automation, Central South University

Department of Computer and Information Sciences, Northumbria University

College of Mechanical and Automotive Engineering, Shanghai University of Engineering Science

State Key Laboratory of Advanced Design and Manufacturing for Vehicle Body, Hunan University

College of Automobile and Transportation, Guangxi University of Science and Technology

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰