Journal Home > Volume 22 , Issue 1
Tsinghua Science and Technology 2017, 22(1): 62-72 https://doi.org/10.1109/TST.2017.7830896
Open Access | Issue | Published: 26 January 2017

Trajectory Planning for Automated Driving Based on Ordinal Optimization

Show Author's Information Xiaoxin Fu,  Yongheng Jiang( ),  Dexian Huang,  Kaisheng Huang,  Jingchun Wang
Department of Automation, Tsinghua University, Beijing 100084, China.
Department of Automobile Engineering, Tsinghua University, Beijing 100084, China.
Keywords:
ordinal optimization, trajectory planning, automated driving, autonomous vehicle, rough evaluation
Cite this article:
Fu X, Jiang Y, Huang D, et al. Trajectory Planning for Automated Driving Based on Ordinal Optimization. Tsinghua Science and Technology, 2017, 22(1): 62-72. https://doi.org/10.1109/TST.2017.7830896
Download citation
EndNote(RIS)
BibTeX

385

Views

9

Downloads

Citations

7

Crossref

N/A

WoS

8

Scopus

0

CSCD

Abstract Full text About this article

This paper proposes an approach based on Ordinal Optimization (OO) to solve trajectory planning for automated driving. As most planning approaches based on candidate curves optimize the trajectory curve and the velocity profile separately, this paper formulates the problem as an unified Non-Linear Programming (NLP) model, optimizing the trajectory curve and the acceleration profile (acceleration is the derivative of velocity) simultaneously. Then a hybrid optimization algorithm named OODE, developed by combining the idea of OO and Differential Evolution (DE), is proposed to solve the NLP model. With the acceleration profile optimized “roughly”, OODE computes and compares “rough” (biased but computationally-easier) curve evaluations to select the best curve from candidates, so that a good enough curve can be obtained very efficiently. Then the acceleration profile is optimized again “accurately” with the selected curve. Simulation results show that good enough solutions are ensured with a high probability and our method is capable of working in real time.


menu
Abstract
Full text
Outline
About this article

Trajectory Planning for Automated Driving Based on Ordinal Optimization

Show Author's information Xiaoxin Fu, Yongheng Jiang( ), Dexian Huang, Kaisheng Huang, Jingchun Wang
Department of Automation, Tsinghua University, Beijing 100084, China.
Department of Automobile Engineering, Tsinghua University, Beijing 100084, China.

Abstract

This paper proposes an approach based on Ordinal Optimization (OO) to solve trajectory planning for automated driving. As most planning approaches based on candidate curves optimize the trajectory curve and the velocity profile separately, this paper formulates the problem as an unified Non-Linear Programming (NLP) model, optimizing the trajectory curve and the acceleration profile (acceleration is the derivative of velocity) simultaneously. Then a hybrid optimization algorithm named OODE, developed by combining the idea of OO and Differential Evolution (DE), is proposed to solve the NLP model. With the acceleration profile optimized “roughly”, OODE computes and compares “rough” (biased but computationally-easier) curve evaluations to select the best curve from candidates, so that a good enough curve can be obtained very efficiently. Then the acceleration profile is optimized again “accurately” with the selected curve. Simulation results show that good enough solutions are ensured with a high probability and our method is capable of working in real time.

Keywords: ordinal optimization, trajectory planning, automated driving, autonomous vehicle, rough evaluation

References(22)

[1]
Bengler K., Dietmayer K., Farber B., Maurer M., Stiller C., and Winner H., Three decades of driver assistance systems: Review and future perspectives, IEEE Intelligent Transportation Systems Magazine, vol. 6, no. 4, pp. 6-22, 2014.
DOI Google Scholar
[2]
Urmson C., Anhalt J., Bagnell D., Baker C., Bittner R., Clark N. N., Dolan J., Duggins D., Galatali T., Geyer C., et al., Autonomous driving in urban environments: Boss and the urban challenge, Journal of Field Robotics, vol. 25, no. 8, pp. 425-466, 2008.
DOI Google Scholar
[3]
Nothdurft T., Hecker P., Ohl S., Saust F., Maurer M., Reschka A., and Böhmer J. R., Stadtpilot: First fully autonomous test drives in urban traffic, in 2011 14th International IEEE Conference on Intelligent Transportation Systems, Washington DC, USA, 2011, pp. 919-924.
DOI
[4]
Broggi A., Buzzoni M., Debattisti S., Grisleri P., Laghi M. C., Medici P., and Versari P., Extensive tests of autonomous driving technologies, IEEE Transactions on Intelligent Transportation Systems, vol. 14, no. 3, pp. 1403-1415, 2013.
DOI Google Scholar
[5]
Ma L., Xue J., Kawabata K., Zhu J., Ma C., and Zheng N., Efficient sampling based motion planning for on-road autonomous driving, IEEE Transactions on Intelligent Transportation Systems, vol. 16, no. 4, pp. 1961-1976, 2015.
DOI Google Scholar
[6]
Hesse T. and Sattel T., An approach to integrate vehicle dynamics in motion planning for advanced driver assistance systems, in Proceedings of the 2007 IEEE Intelligent Vehicles Symposium, Istanbul, Turkey, 2007, pp. 1240-1245.
DOI
[7]
Hilgert J., Hirsch K., Bertram T., and Hiller M., Emergency path planning for autonomous vehicles using elastic band theory, in Proceedings of the 2003 IEEE/ASME International Conference on Advanced Intelligent Mechatronics, Duisburg, Germany, 2003, pp. 1390-1395.
[8]
Gong Q., Lewis L. R., and Ross I. M., Pseudospectral motion planning for autonomous vehicles, Journal of Guidance, Control, and Dynamics, vol. 32, no. 3, pp. 1039-1045, 2009.
DOI Google Scholar
[9]
Anderson S. J., Peters S. C., and Pilutti T. E., Design and development of an optimal-control-based framework for trajectory planning, threat assessment, and semiautonomous control of passenger vehicles in hazard avoidance scenarios, in Robotics Research: The 14th International Symposium ISRR, C. Pradalier, R. Siegwart, and G. Hirzinger, eds. Springer, 2011, pp. 39-54.
DOI
[10]
McNaughton M., Urmson C., Dolan J. M., and Lee J. W., Motion planning for autonomous driving with a conformal spatiotemporal lattice, in 2011 IEEE International Conference on Robotics and Automation, Shanghai, China, 2011, pp. 4889-4895.
DOI
[11]
Ziegler J. and Stiller C., Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios, in The 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, St Louis, MO, USA, 2009, pp. 1879-1884.
DOI
[12]
Kuwata Y., Teo J., Fiore G., Karaman S., Frazzoli E., and How J. P., Real-time motion planning with applications to autonomous urban driving, IEEE Transactions on Control Systems Technology, vol. 17, no. 5, pp. 1105-1118, 2009.
DOI Google Scholar
[13]
Papadimitriou I. and Tomizuka M., Fast lane changing computations using polynomials, in Proceedings of the American Control Conference, Denver, CO, USA, 2003, pp. 48-53.
[14]
Köhler S., Schreiner B., Ronalter S., Doll K., Brunsmann U., and Zindler K., Autonomous evasive maneuvers triggered by infrastructure-based detection of pedestrian intentions, in 2013 IEEE Intelligent Vehicles Symposium (IV), Gold Coast, Australia, 2013, pp. 519-526.
DOI
[15]
Montemerlo M., Becker J., Bhat S., Dhlkamp H., Dolgov D., Ettinger S., Haehnel D., Hilden T., Hoffmann G., Huhnke B., et al., Junior: The stanford entry in the urban challenge, Journal of Field Robotics, vol. 25, no. 9, pp. 569-597, 2008.
DOI Google Scholar
[16]
Glaser S., Vanholme B., Mammar S., Gruyer D., and Nouvelière L., Maneuver based trajectory planning for highly autonomous vehicles on real road with traffic and driver interaction, IEEE Transactions on Intelligent Transportation Systems, vol. 11, no. 3, pp. 589-606, 2010.
DOI Google Scholar
[17]
Kelly A. and Nagy B., Reactive nonholonomic trajectory generation via parametric optimal control, The International Journal of Robotics Research, vol. 22, nos. 7&8, pp. 583-601, 2003.
DOI Google Scholar
[18]
Ho Y., Zhao Q., and Jia Q., Ordinal Optimization: Soft Optimization for Hard Problems. Springer, 2007.
DOI
[19]
Dai L., Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems, Journal of Optimization Theory and Applications, vol. 91, no. 2, pp. 363-388, 1996.
DOI Google Scholar
[20]
Lee L. H., Lau T. W. E., and Ho Y. C., Explanation of goal softening in ordinal optimization, IEEE Transactions on Automatic Control, vol. 44, no. 1, pp. 94-99, 1999.
DOI Google Scholar
[21]
Price K. V., Storn R. M., and Lampinen J. A., Differential Evolution: A Practical Approach to Global Optimization. Springer, 2005.
[22]
Bai L., Jiang Y., and Huang D., A novel two-level optimization framework based on constrained ordinal optimization and evolutionary algorithms for scheduling of multipipeline crude oil blending, Industrial & Engineering Chemistry Research, vol. 51, no. 26, pp. 9078-9093, 2012.
DOI Google Scholar
Publication history
Copyright
Rights and permissions

Publication history

Received: 17 December 2015
Accepted: 22 March 2016
Published: 26 January 2017
Issue date: February 2017

Copyright

© The author(s) 2017

Rights and permissions

Return