Verification of Steering Angle Safety for Self-driving Cars Using Convex Optimization
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [67]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Providing formal guarantees for self-driving cars is a challenging task, since input-output space (i.e., all possible combinations of inputs and outputs) is too large to explore exhaustively. This paper presents an automated verification technique ensuring steering angle safety for self-driving cars by incorporating convex optimization and deep learning verification (DLV). DLV is an automated verification framework for safety of image classification neural networks. The DLV is extended by convex optimization technique in fail-safe trajectory planning to solve the judgement problem of predicted steering angle, and thus, to achieve verification of steering angle safety for self-driving cars. The benefits of the proposed approach are demonstrated on the NVIDIA's end-to-end self-driving architecture, which is a crucial ingredient in many modern self-driving cars. The experimental results indicate that the proposed technique can successfully find adversarial misclassifications (i.e., incorrect steering decisions) within given regions and family of manipulations if they exist. Therefore, the safety verification can be achieved (if no misclassification is found for all DNN layers, in which case the network can be said to be stable or reliable w.r.t. steering decisions) or falsification (in which case the adversarial examples can be used to fine-tune the network).

    Reference
    [1] Google's self-driving car caused its first crash. 2016. https://www.wired.com/2016/02/googles-self-driving-car-may-caused-first-crash/
    [2] Uber driver charged in fatal 2018 autonomous car crash. 2018. https://www.autoweek.com/news/technology/a34039541/uber-driver-charged-in-fatal-2018-autonomous-car-crash/
    [3] NHTSA probing 16 deadly Tesla highway crashes. 2023. https://www.kron4.com/news/bay-area/nhtsa-probing-16-deadly-tesla-autopilot-highway-crashes/
    [4] Biggio B, Corona I, Maiorca D, Nelson B, Srndic N, Laskov P, Giacinto G, Roli F. Evasion attacks against machine learning at test time. In: Proc. of the Joint European Conf. on Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2013. 387-402.
    [5] Szegedy C, Zaremba W, Sutskever I, Bruna J, Erhan D, Goodfellow I, Fergus R. Intriguing properties of neural networks. In: Proc. of the 2nd Int'l Conf. on Learning Representations. 2014. 14-16.
    [6] Althoff D, Althoff M, Scherer S. Online safety verification of trajectories for unmanned flight with offline computed robust invariant sets. In: Proc. of the 2015 IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems (IROS). IEEE, 2015. 3470-3477.
    [7] Kalra N, Paddock SM. Driving to safety: How many miles of driving would it take to demonstrate autonomous vehicle reliability. Transportation Research Part A: Policy and Practice, 2016, 94: 182-193.
    [8] Pek C, Koschi M, Althoff M. An online verification framework for motion planning of self-driving vehicles with safety guarantees. In: Proc. of the AAET-Automatisiertes und vernetztes Fahren. Braunschweig, 2019.
    [9] Damm W, Peter HJ, Rakow J, Westphal B. Can we build it: Formal synthesis of control strategies for cooperative driver assistance systems. Mathematical Structures in Computer Science, 2013, 23(4): 676-725.
    [10] Hilscher M, Linker S, Olderog ER. Proving safety of traffic manoeuvres on country roads. In: Proc. of the Theories of Programming and Formal Methods. Berlin, Heidelberg: Springer, 2013. 196-212.
    [11] Loos SM, Platzer A, Nistor L. Adaptive cruise control: Hybrid, distributed, and now formally verified. In: Proc. of the Int'l Symp. on Formal Methods. Berlin, Heidelberg: Springer, 2011. 42-56.
    [12] Mitsch S, Loos SM, Platzer A. Towards formal verification of freeway traffic control. In: Proc. of the IEEE/ACM 3rd Int'l Conf. on Cyber-physical Systems. IEEE, 2012. 171-180.
    [13] Pek C, Althoff M. Fail-safe motion planning for online verification of autonomous vehicles using convex optimization. IEEE Trans. on Robotics, 2020, 37(3): 798-814.
    [14] Althoff M. Reachability analysis of nonlinear systems using conservative polynomialization and non-convex sets. In: Proc. of the 16th Int'l Conf. on Hybrid Systems: Computation and Control. 2013. 173-182. [doi: 10.1145/2461328.2461358]
    [15] Herbert SL, Chen M, Han SJ, Bansal S, Fisac JF, Tomlin CJ. FaSTrack: A modular framework for fast and guaranteed safe motion planning. In: Proc. of the 56th IEEE Annual Conf. on Decision and Control (CDC). IEEE, 2017. 1517-1522.
    [16] Mitchell IM. Comparing forward and backward reachability as tools for safety analysis. In: Proc. of the 10th Int'l Workshop on Hybrid Systems: Computation and Control. Pisa, 2007. 428-443.
    [17] Althoff D, Buss M, Lawitzky A, Werling M, Wollherr D. On-line trajectory generation for safe and optimal vehicle motion planning. In: Proc. of the Autonomous Mobile Systems 2012. Berlin, Heidelberg: Springer, 2012. 99-107. [doi: 10.1007/978-3-642-32217-4_11]
    [18] Martinez-Gomez L, Fraichard T. An efficient and generic 2D inevitable collision state-checker. In: Proc. of the 2008 IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems. IEEE, 2008. 234-241.
    [19] Petti S, Fraichard T. Safe motion planning in dynamic environments. In: Proc. of the 2005 IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems. IEEE, 2005. 2210-2215.
    [20] Berntorp K, Weiss A, Danielson C, Kolmanovsky IV, Cairano SD. Automated driving: Safe motion planning using positively invariant sets. In: Proc. of the 20th IEEE Int'l Conf. on Intelligent Transportation Systems. 2017. 1-6.
    [21] Jalalmaab M, Fidan B, Jeon S, Falcone P. Guaranteeing persistent feasibility of model predictive motion planning for autonomous vehicles. In: Proc. of the 2017 IEEE Intelligent Vehicles Symp. (Ⅳ). IEEE, 2017. 843-848.
    [22] Fraichard T. A short paper about motion safety. In: Proc. of the IEEE Int'l Conf. on Robotics and Automation. IEEE, 2007. 1140-1145.
    [23] Althoff D, Kuffner JJ, Wollherr D, Buss M. Safety assessment of robot trajectories for navigation in uncertain and dynamic environments. Autonomous Robots, 2012, 32(3): 285-302. [doi: 10.1007/s10514-011-9257-9]
    [24] Söntges S, Althoff M. Determining the nonexistence of evasive trajectories for collision avoidance systems. In: Proc. of the 18th Int'l Conf. on Intelligent Transportation Systems. IEEE, 2015. 956-961. [doi: 10.1109/ITSC.2015.160]
    [25] Söntges S, Althoff M. Computing the drivable area of autonomous road vehicles in dynamic road scenes. IEEE Trans. on Intelligent Transportation Systems, 2018, 19(6): 1855-1866.
    [26] Wu H, Lv D, Cui T, Hou G, Watanabe M, Kong W. SDLV: Verification of steering angle safety for self-driving cars. Formal Aspects of Computing, 2021, 33(3): 325-341. [doi: 10.1007/s00165-021-00539-2]
    [27] Huang X, Kwiatkowska M, Wang S, Wu M. Safety verification of deep neural networks. In: Proc. of the Int'l Conf. on Computer Aided Verification. Cham: Springer, 2017. 3-29. [doi: 10.1007/978-3-319-63387-91]
    [28] Pei K, Cao Y, Yang J, Jana S. Deepxplore: Automated whitebox testing of deep learning systems. In: Proc. of the 26th Symp. on Operating Systems Principles. 2017. 1-18. [doi: 10.1145/3132747.3132785]
    [29] Bojarski M, Testa DD, Dworakowski D, Firner B, Flepp B, Goyal P, Jackel LD, Monfort M, Muller U, Zhang JK, Zhang X, Zhao J, Zieba K. End to end learning for self-driving cars. arXiv: 1604.07316, 2016.
    [30] Rambo model. 2017. https://github.com/udacity/self-driving-car/tree/master/steering-models/community-models/rambo
    [31] Koopman P, Wagner M. Challenges in autonomous vehicle testing and validation. SAE Int'l Journal of Transportation Safety, 2016, 4(1): 15-24. [doi: 10.4271/2016-01-0128]
    [32] Tian Y, Pei K, Jana S, Ray B. DeepTest: Automated testing of deep-neural-network-driven autonomous cars. In: Proc. of the 40th Int'l Conf. on Software Engineering. 2018. 303-314. [doi: 10.1145/3180155.3180220]
    [33] Zhang M, Zhang Y, Zhang L, Liu C, Khurshid S. DeepRoad: Gan-based metamorphic testing and input validation framework for autonomous driving systems. In: Proc. of the 33rd ACM/IEEE Int'l Conf. on Automated Software Engineering (ASE 2018). Montpellier, 2018. 132-142. [doi: 10.1145/3238147.3238187]
    [34] Althoff M, Dolan JM. Online verification of automated road vehicles using reachability analysis. IEEE Trans. on Robotics, 2014, 30(4): 903-918.
    [35] Majumdar A, Tedrake R. Funnel libraries for real-time robust feedback motion planning. The Int'l Journal of Robotics Research, 2017, 36(8): 947-982. [doi: 10.1177/0278364917712421]
    [36] Vaskov S, Kousik S, Larson H, Bu F, Ward J, Worrall S, Johnson-Roberson M, Vasudevan R. Towards provably not-at-fault control of autonomous robots in arbitrary dynamic environments. In: Bicchi A, Kress-Gazit H, Hutchinson S, eds. Proc. of the Robotics: Science and Systems XV. Freiburg im Breisgau: University of Freiburg, 2019.
    [37] Wu H, Lyu D, Zhang Y, Hou G, Watanabe M, Wang J, Kong W. A verification framework for behavioral safety of self-driving cars. IET Intelligent Transport Systems, 2022, 16(5): 630-647.
    [38] Luckcuck M, Farrell M, Dennis LA, Dixon C, Fisher M. Formal specification and verification of autonomous robotic systems: A survey. ACM Computing Surveys (CSUR), 2019, 52(5): 1-41. [doi: 10.1145/3342355]
    [39] Lefèvre S, Vasquez D, Laugier C. A survey on motion prediction and risk assessment for intelligent vehicles. ROBOMECH Journal, 2014, 1(1): 1-14.
    [40] Kim B, Park K, Yi K. Probabilistic threat assessment with environment description and rule-based multi-traffic prediction for integrated risk management system. IEEE Intelligent Transportation Systems Magazine, 2017, 9(3): 8-22.
    [41] Annell S, Gratner A, Svensson L. Probabilistic collision estimation system for autonomous vehicles. In: Proc. of the 19th IEEE Int'l Conf. on Intelligent Transportation Systems (ITSC). IEEE, 2016. 473-478.
    [42] Lambert A, Gruyer D, Pierre GS, Ndjeng AN. Collision probability assessment for speed control. In: Proc. of the 11th Int'l IEEE Conf. on Intelligent Transportation Systems. IEEE, 2008. 1043-1048.
    [43] Reschka A, Böhmer JR, Nothdurft T, Hecker P, Lichte B, Maurer M. A surveillance and safety system based on performance criteria and functional degradation for an autonomous vehicle. In: Proc. of the 15th Int'l IEEE Conf. on Intelligent Transportation Systems. IEEE, 2012. 237-242.
    [44] Stahl T, Eicher M, Betz J, Nothdurft T, Diermeyer F. Online verification concept for autonomous vehicles–illustrative study for a trajectory planning module. In: Proc. of the IEEE 23rd Int'l Conf. on Intelligent Transportation Systems (ITSC). IEEE, 2020. 1-7. [doi: 10.1109/ITSC45102.2020.9294703]
    [45] Schürmann B, Heß D, Eilbrecht J, Stursberg O, Koster F, Althoff M. Ensuring drivability of planned motions using formal methods. In: Proc. of the IEEE 20th Int'l Conf. on Intelligent Transportation Systems (ITSC). IEEE, 2017. 1-8.
    [46] Kane A, Chowdhury O, Datta A, Koopman P. A case study on runtime monitoring of an autonomous research vehicle (ARV) system. In: Proc. of the Runtime Verification. Cham: Springer, 2015. 102-117. [doi: 10.1007/978-3-319-23820-3_7]
    [47] Feth P, Schneider D, Adler R. A conceptual safety supervisor definition and evaluation framework for autonomous systems. In: Proc. of the 36th Int'l Conf. on Computer Safety, Reliability, and Security (SAFECOMP 2017). Trento, 2017. 135-148. [doi: 10.1007/978-3-319-66266-4_9]
    [48] Shalev-Shwartz S, Shammah S, Shashua A. On a formal model of safe and scalable self-driving cars. arXiv: 1708.06374, 2017.
    [49] Idriz AF, Abdul Rachman AS, Baldi S. Integration of auto-steering with adaptive cruise control for improved cornering behaviour. IET Intelligent Transport Systems, 2017, 11(10): 667-675. [doi: 10.1049/iet-its.2017.0089]
    [50] Rachman ASA, Idriz AF, Li S, Baldi S. Real-Time performance and safety validation of an integrated vehicle dynamic control strategy. IFAC-PapersOnLine, 2017, 50(1): 13854-13859.
    [51] Liu BB, Liu WW, Mao XG, Dong W. Correctness verification of rules for unmanned vehicles's decision system. Computer Science, 2017, 44(04): 72-74, 113 (in Chinese with English abstract). 刘斌斌, 刘万伟, 毛晓光, 董威. 无人驾驶汽车决策系统的规则正确性验证. 计算机科学, 2017, 44(4): 72-74+113.
    [52] Cho DS, Yun S, Kim H, Kwon J, Kim W. Autonomous driving system verification framework with FMI co-simulation based on OMG DDS. In: Proc. of the IEEE Int'l Conf. on Consumer Electronics (ICCE). IEEE, 2020. 1-6.
    [53] Zhu Y, Zhao XM, Li CY, Li Y, Wang RM. Design and verification of virtual-real interaction system for automatic driving virtual- real combined test. In: Proc. of the 2022 World Transportation Conf. (Transportation Planning and Interdisciplinary) (WTC 2022). 2022. 910-918 (in Chinese). [doi: 10.26914/c.cnkihy.2022.019368] 朱宇, 赵祥模, 李春银, 李妍, 王润民. 面向自动驾驶虚实结合测试的虚实交互系统设计与验证. 见: 2022世界交通运输大会(WTC 2022)论文集(运输规划与交叉学科篇). 2022. 910-918. [doi: 10.26914/c.cnkihy.2022.019368]
    [54] Long X, Gao JB, Wei HB. Development and test validation of a systematic architecture for autonomous vehicle. Journal of Chongqing University of Technology (Natural Science), 2019, 33(12): 45-54 (in Chinese with English abstract). 龙翔, 高建博, 隗寒冰. 一种自动驾驶汽车系统架构开发与测实验证. 重庆理工大学学报(自然科学版), 2019, 33(12): 45-54.
    [55] Rumelhart DE, Hinton GE, Williams RJ. Learning representations by back-propagating errors. Nature, 1986, 323(6088): 533-536.
    [56] Goodfellow I, Bengio Y, Courville A. Deep Learning. MIT Press, 2016.
    [57] Nair V, Hinton GE. Rectified linear units improve restricted Boltzmann machines. In: Proc. of the ICML. 2010.
    [58] Pek C, Althoff M. Computationally efficient fail-safe trajectory planning for self-driving vehicles using convex optimization. In: Proc. of the 21st Int'l Conf. on Intelligent Transportation Systems (ITSC). IEEE, 2018. 1447-1454.
    [59] Koschi M, Althoff M. SPOT: A tool for set-based prediction of traffic participants. In: Proc. of the IEEE Intelligent Vehicles Symp. (Ⅳ). IEEE, 2017. 1686-1693.
    [60] Boyd S, Boyd SP, Vandenberghe L. Convex Optimization. Cambridge University Press, 2004.
    [61] Paden B, Čáp M, Yong SZ, Yershov D, Frazzoli E. A survey of motion planning and control techniques for self-driving urban vehicles. IEEE Trans. on Intelligent Vehicles, 2016, 1(1): 33-55.
    [62] Diamond S, Boyd S. CVXPY: A Python-embedded modeling language for convex optimization. The Journal of Machine Learning Research, 2016, 17(1): 2909-2913.
    [63] SullyChen. Driving dataset.
    [64] Z3. 2019. http://rise4fun.com/z3
    [65] Keras. 2019. https://keras.io
    [66] Theano. http://deeplearning.net/software/theano/
    [67] Papernot N, McDaniel P, Goodfellow I, Jha S, Celik ZB, Swami A. Practical black-box attacks against deep learning systems using adversarial examples. arXiv: 1602.02697, 2016.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

吴慧慧,张亚楠,侯刚,渡边政彦,王洁,孔维强.基于凸优化的无人驾驶汽车转向角安全性验证.软件学报,2023,34(6):2586-2605

Copy
Share
Article Metrics
  • Abstract:1109
  • PDF: 3393
  • HTML: 2714
  • Cited by: 0
History
  • Received:September 05,2022
  • Revised:October 10,2022
  • Online: January 13,2023
  • Published: June 06,2023
You are the first2041549Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063