On-road trajectory planning based on optimal computing budget allocation

FU Xiaoxin; JIANG Yongheng; HUANG Dexian; WANG Jingchun; HUANG Kaisheng

doi:10.16511/j.cnki.qhdxxb.2016.21.024

PDF(1167 KB)

Journal of Tsinghua University(Science and Technology) ›› 2016, Vol. 56 ›› Issue (3) : 273-280. DOI: 10.16511/j.cnki.qhdxxb.2016.21.024

AUTO MATION

On-road trajectory planning based on optimal computing budget allocation

{{article.zuoZhe_EN}}

Author information +

History +

Abstract

This paper presents an algorithm named OCBA_OODE for on-road trajectory planning by using optimal computing budget allocation (OCBA) in a candidate-curve-based planning algorithm named OODE. OODE picks the best trajectory by comparing rough (biased but computationally inexpensive) evaluations of a set of candidate curves. The curve evaluation converges to the real value as the computing budget increases. OODE allocates the equal parts of the computing budget to each curve, while OCBA_OODE repeatedly allocates the budget according to the latest curve evaluations to improve the planning efficiency. OCBA_OODE is 20% faster than OODE while maintaining the same solution quality.

Key words

optimal computing budget allocation / trajectory planning / intelligent vehicles / ordinal optimization

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

FU Xiaoxin, JIANG Yongheng, HUANG Dexian, WANG Jingchun, HUANG Kaisheng. On-road trajectory planning based on optimal computing budget allocation[J]. Journal of Tsinghua University(Science and Technology). 2016, 56(3): 273-280 https://doi.org/10.16511/j.cnki.qhdxxb.2016.21.024

References

[1] Karaman S, Frazzoli E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7):846-894.
[2] Gehrig S K, Stein F J. Collision avoidance for vehicle-following systems[J]. Intelligent Transportation Systems, IEEE Transactions on, 2007, 8(2):233-244.
[3] Brandt T, Sattel T, Wallaschek J. Towards vehicle trajectory planning for collision avoidance based on elastic bands[J]. International Journal of Vehicle Autonomous Systems, 2007, 5(1-2):28-46.
[4] McNaughton M, Urmson C, Dolan J M, et al. Motion planning for autonomous driving with a conformal spatiotemporal lattice[C]//Robotics and Automation (ICRA), 2011 IEEE International Conference on. Shanghai, China:IEEE Press, 2011:4889-4895.
[5] Ziegler J, Stiller C. Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios[C]//Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on. IEEE Press, 2009:1879-1884.
[6] Ma L, Xue J, Kawabata K, et al. Efficient sampling-based motion planning for on-road autonomous driving[J]. Intelligent Transportation Systems, IEEE Transactions on, 2015, 16(4):1961-1976.
[7] Kuwata Y, Karaman S, Teo J, et al. Real-time motion planning with applications to autonomous urban driving[J]. Control Systems Technology, IEEE Transactions on, 2009, 17(5):1105-1118.
[8] Lin C F, Juang J C, Li K R. Active collision avoidance system for steering control of autonomous vehicles[J]. Intelligent Transport Systems, IET, 2014, 8(6):550-557.
[9] Papadimitriou I, Tomizuka M. Fast lane changing computations using polynomials[C]//American Control Conference, 2003. Proceedings of the 2003. Denver, CO, USA:IEEE Press, 2003:48-53 vol.1.
[10] 付骁鑫, 江永亨, 黄德先, 等. 一种新的实时智能汽车轨迹规划方法[J]. 控制与决策, 2015, 30(10):1751-1758. FU Xiaoxin, Jiang Yongheng, Huang Dexian, et al. A novel real-time trajectory planning algorithm for intelligent vehicles[J]. Control and Decision, 2015, 30(10):1751-1758. (in Chinese)
[11] Chen C, Lin J, Yücesan E, et al. Simulation budget allocation for further enhancing the efficiency of ordinal optimization[J]. Discrete Event Dynamic Systems, 2000, 10(3):251-270.
[12] Ho Y, Zhao Q, Jia Q. Ordinal Optimization:Soft Optimization for Hard Problems[M]. New York:Springer US, 2007.
[13] Bai L, Jiang Y, Huang D. A novel two-level optimization framework based on constrained ordinal optimization and evolutionary algorithms for scheduling of multipipeline crude oil blending[J]. Industrial & Engineering Chemistry Research, 2012, 51(26):9078-9093.