This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
Using GPU to Accelerate Backward Induction for Vehicle Speed Optimal Control
Technical Paper
2022-01-0089
ISSN: 0148-7191, e-ISSN: 2688-3627
Annotation ability available
Sector:
Language:
English
Abstract
This paper proposes a method to adapt backward induction, which is used to solve the vehicle speed optimal control problem for energy efficiency, to a computer with a GPU to accelerate the computation. A common application of this type of problem is to control a vehicle on a given route with surrounding vehicles, road grades, traffic signals, stop signs, speed limits, and other conditions. Several indicators can be used to determine the performance of the controller, including the energy consumption of the trip, the driving speed smoothness, and the traveling time to a given destination. Solving this optimization problem globally by backward induction is time-consuming, due to the large searching space of the vehicle’s distance, velocity, and acceleration. The proposed method converts the single thread implementation to a parallel process that runs on a consumer-level GPU. This is done by choosing the problem scale, separating independent sub-processes, and pruning the data to accommodate the GPU programming requirement. The method is tested on a simulated route with a leading vehicle, a traffic light, and speed limits. The historical behaviors of the leading vehicle are known, and they are used to predict its future behaviors in a stochastic way. Compared to the CPU-based backward induction, the proposed GPU-based version solves the given problem 15 to 30 times faster, depending on the preset granularities of variables.
Authors
Citation
Ma, Z. and Zeng, X., "Using GPU to Accelerate Backward Induction for Vehicle Speed Optimal Control," SAE Technical Paper 2022-01-0089, 2022, https://doi.org/10.4271/2022-01-0089.Also In
References
- Davis , S.C. and Boundy , R.G. 2021
- U.S. Energy Information Administration Annual Energy Outlook 2021 United States U.S. Energy Information Administration 2021
- Wu , L. , Ci , Y. , Chu , J. , and Zhang , H. The Influence of Intersections on Fuel Consumption in Urban Arterial Road Traffic: A Single Vehicle Test in Harbin, China PLoS One 10 9 2015 e0137477 10.1371/journal.pone.0137477
- Asadi , B. and Vahidi , A. Predictive Cruise Control: Utilizing Upcoming Traffic Signal Information for Improving Fuel Economy and Reducing Trip Time IEEE Trans. Contr. Syst. Technol. 19 3 2011 707 714 10.1109/TCST.2010.2047860
- De Nunzio , G. , Canudas de Wit , C. , Moulin , P. , and Di Domenico , D. Eco-Driving in Urban Traffic Networks Using Traffic Signal Information 52nd IEEE Conference on Decision and Control 2013 892 898 10.1109/CDC.2013.6759995
- Eckhoff , D. , Halmos , B. , and German , R. Potentials and Limitations of Green Light Optimal Speed Advisory Systems 2013, IEEE Vehicular Networking Conference 2013 103 110 10.1109/VNC.2013.6737596
- Huang , X. and Peng , H. Speed Trajectory Planning at Signalized Intersections Using Sequential Convex Optimization 2017 American Control Conference (ACC) 2017 2992 2997 10.23919/ACC.2017.7963406
- Luo , Y. , Li , S. , Zhang , S. , Qin , Z. et al. Green Light Optimal Speed Advisory for Hybrid Electric Vehicles Mechanical Systems and Signal Processing 87 2017 30 44 10.1016/j.ymssp.2016.04.016
- Miao , C. , Liu , H. , Zhu , G.G. , and Chen , H. Connectivity-Based Optimization of Vehicle Route and Speed for Improved Fuel Economy Transportation Research Part C: Emerging Technologies 91 2018 353 368 10.1016/j.trc.2018.04.014
- Wan , N. , Vahidi , A. , and Luckow , A. Optimal Speed Advisory for Connected Vehicles in Arterial Roads and the Impact on Mixed Traffic Transportation Research Part C: Emerging Technologies 69 2016 548 563 10.1016/j.trc.2016.01.011
- Hu , J. , Shao , Y. , Sun , Z. , and Bared , J. Integrated Vehicle and Powertrain Optimization for Passenger Vehicles with Vehicle-Infrastructure Communication Transportation Research Part C: Emerging Technologies 79 2017 85 102 10.1016/j.trc.2017.03.010
- Li , S.E. , Li , K. , and Wang , J. Economy-Oriented Vehicle Adaptive Cruise Control with Coordinating Multiple Objectives Function Vehicle System Dynamics 51 1 2013 1 17 10.1080/00423114.2012.708421
- Held , M. , Flärdh , O. , and Mårtensson , J. Optimal Speed Control of a Heavy-Duty Vehicle in the Presence of Traffic Lights 2018 IEEE Conference on Decision and Control (CDC) 2018 6119 6124 10.1109/CDC.2018.8619463
- Hellström , E. , Ivarsson , M. , Åslund , J. , and Nielsen , L. Look-Ahead Control for Heavy Trucks to Minimize Trip Time and Fuel Consumption Control Engineering Practice 17 2 2009 245 254 10.1016/j.conengprac.2008.07.005
- Filev , D.P. and Kolmanovsky , I. Markov Chain Modeling Approaches for on Board Applications Proceedings of the 2010 American Control Conference 2010 4139 4145 10.1109/ACC.2010.5530610
- Zeng , X. and Wang , J. A Parallel Hybrid Electric Vehicle Energy Management Strategy using Stochastic Model Predictive Control with Road Grade Preview IEEE Transactions on Control Systems Technology 23 6 2015 2416 2423 10.1109/TCST.2015.2409235
- Zhu , D. , Pritchard , E. , Dadam , S. , Kumar , V. et al. Optimization of Rule-Based Energy Management Strategies for Hybrid Vehicles using Dynamic Programming Combustion Engines 184 1 2021 3 10 10.19206/CE-131967
- Zeng , X. and Wang , J. A Two-Level Stochastic Approach to Optimize the Energy Management Strategy for Fixed-Route Hybrid Electric Vehicles Mechatronics 38 2016 93 102 10.1016/j.mechatronics.2015.11.011
- Zeng , X. and Wang , J. Globally Energy-Optimal Speed Planning for Road Vehicles on a Given Route Transportation Research Part C: Emerging Technologies 93 2018 148 160 10.1016/j.trc.2018.05.027
- Kamalanathsharma , R.K. and Rakha , H.A. Multi-Stage Dynamic Programming Algorithm for Eco-Speed Control at Traffic Signalized Intersections 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013) 2013 2094 2099 10.1109/ITSC.2013.6728538
- Ozatay , E. , Onori , S. , Wollaeger , J. , Ozguner , U. et al. Cloud-Based Velocity Profile Optimization for Everyday Driving: A Dynamic-Programming-Based Solution IEEE Transactions on Intelligent Transportation Systems 15 6 2014 2491 2505 10.1109/TITS.2014.2319812
- Xiao , S. , Aji , A.M. , and Feng , W. On the Robust Mapping of Dynamic Programming onto a Graphics Processing Unit 2009 15th International Conference on Parallel and Distributed Systems 2009 26 33 10.1109/ICPADS.2009.110
- Wu , C.-C. , Ke , J.-Y. , Lin , H. , and Jhan , S.-S. Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs International Journal of Grid and High Performance Computing 6 1 2014 1 20 10.4018/ijghpc.2014010101
- Jóhannsson , Á.Þ. 2009
- Nishida , K. , Ito , Y. , and Nakano , K. Accelerating the Dynamic Programming for the Matrix Chain Product on the GPU 2011 Second International Conference on Networking and Computing 320 326 2011 10.1109/ICNC.2011.62
- Berger , K.-E. and Galea , F. An Efficient Parallelization Strategy for Dynamic Programming on GPU 2013 IEEE International Symposium on Parallel Distributed Processing, Workshops and Ph.D. Forum 1797 1806 2013 10.1109/IPDPSW.2013.208
- Yamashita , K. , Ito , Y. , and Nakano , K. A GPU Implementation of Bulk Execution of the Dynamic Programming for the Optimal Polygon Triangulation Parallel Processing and Applied Mathematics Cham Springer International Publishing 2018 314 323 10.1007/978-3-319-78024-5_28 978-3-319-78024-5
- Steffen , P. , Giegerich , R. , and Giraud , M. GPU Parallelization of Algebraic Dynamic Programming Wyrzykowski , R. , Dongarra , J. , Karczewski , K. and Wasniewski , J. Parallel Processing and Applied Mathematics Berlin, Heidelberg Springer Berlin Heidelberg 2010 290 299 10.1007/978-3-642-14403-5_31 978-3-642-14402-8
- Aldrich , E.M. , Fernández-Villaverde , J. , Ronald Gallant , A. , and Rubio-Ramírez , J.F. Tapping the Supercomputer under Your Desk: Solving Dynamic Equilibrium Models with Graphics Processors Journal of Economic Dynamics and Control 35 3 2011 386 393 10.1016/j.jedc.2010.10.001
- Zhang , N. , Lim , E.G. , Man , K.L. , and Lei , C.-U. CPU-GPU Hybrid Parallel Binomial American Option Pricing 7 Hong Kong 2012
- Ruiz , S. and Hernández , B. A Parallel Solver for Markov Decision Process in Crowd Simulations 2015 Fourteenth Mexican International Conference on Artificial Intelligence (MICAI) 2015 107 116 10.1109/MICAI.2015.23
- Sampathirao , A.K. , Sopasakis , P. , Bemporad , A. , and Patrinos , P.P. GPU-Accelerated Stochastic Predictive Control of Drinking Water Networks IEEE Transactions on Control Systems Technology 26 2 2018 551 562 10.1109/TCST.2017.2677741
- Ortega , G. , Hendrix , E.M.T. , and García , I. A CUDA Approach to Compute Perishable Inventory Control Policies using Value Iteration J Supercomput 75 3 2019 1580 1593 10.1007/s11227-018-2692-z
- Perez , W. , Ruhela , A. , and Tulpule , P. Benchmarking Computational Time of Dynamic Programming for Autonomous Vehicle Powertrain Control SAE Technical Paper 2020-01-0968 2020 10.4271/2020-01-0968
- Puterman , M.L. Markov Decision Processes: Discrete Stochastic Dynamic Programming John Wiley & Sons 2014 978-1-118-62587-3
- CUDA 2020
- Nguyen , H. GPU Gems 3 1st Addison-Wesley Professional 2007 978-0-321-54542-8
- Chandler , R.E. , Herman , R. , and Montroll , E.W. Traffic Dynamics: Studies in Car Following Operations Research 6 2 1958 165 184 10.1287/opre.6.2.165