ABSTRACT
Vision-based control systems are key enablers of many autonomous vehicular systems, including self-driving cars. Testing such systems is complicated by complex and multidimensional input spaces. We propose an automated testing algorithm that builds on learnable evolutionary algorithms. These algorithms rely on machine learning or a combination of machine learning and Darwinian genetic operators to guide the generation of new solutions (test scenarios in our context). Our approach combines multiobjective population-based search algorithms and decision tree classification models to achieve the following goals: First, classification models guide the search-based generation of tests faster towards critical test scenarios (i.e., test scenarios leading to failures). Second, search algorithms refine classification models so that the models can accurately characterize critical regions (i.e., the regions of a test input space that are likely to contain most critical test scenarios). Our evaluation performed on an industrial automotive automotive system shows that: (1) Our algorithm outperforms a baseline evolutionary search algorithm and generates 78% more distinct, critical test scenarios compared to the baseline algorithm. (2) Our algorithm accurately characterizes critical regions of the system under test, thus identifying the conditions that are likely to lead to system failures.
- Ethem Alpaydin. 2010. Introduction to Machine Learning (2nd ed.). MIT Press, Cambridge, Massachusetts, USA. Google ScholarDigital Library
- Andrea Arcuri and Lionel Briand. 2014. A hitchhiker's guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability 24, 3 (2014), 219--250. Google ScholarDigital Library
- Andrea Arcuri and Gordon Fraser. 2011. On Parameter Tuning in Search Based Software Engineering. In Proceedings of the International Symposium on Search Based Software Engineering (SSBSE'11). Springer, Berlin, Heidelberg, 33--47. Google ScholarDigital Library
- Assia Belbachir, Jean-Christophe Smal, Jean-Marc Blosseville, and Dominique Gruyer. 2012. Simulation-driven validation of advanced driving-assistance systems. Procedia-Social and Behavioral Sciences 48 (2012), 1205--1214.Google ScholarCross Ref
- Raja Ben Abdessalem, Shiva Nejati, Lionel C. Briand, and Thomas Stifter. 2016. Testing advanced driver assistance systems using multi-objective search and neural networks. In Proceedings of the International Conference on Automated Software Engineering (ASE'16). IEEE, Singapore, 63--74. Google ScholarDigital Library
- Hans-georg Beyer and Kalyanmoy Deb. 2001. On self-adaptive features in real-parameter evolutionary algorithms. IEEE Transactions on Evolutionary Computation 5, 3 (2001), 250--270. Google ScholarDigital Library
- Bosch. 2017. Driving safety systems for passenger cars. (Aug. 2017). Retrieved August 24, 2017 from https://goo.gl/4LSl3HGoogle Scholar
- Leo Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. 1984. Classification and Regression Trees. Wadsworth, Belmont, CA, U.SA.Google Scholar
- Oliver Buehler and Joachim Wegener. 2005. Evolutionary functional testing of a vehicle brake assistant system. In Proceedings of the Metaheuristics International Conference (MIC'05).-, Vienna Austria, 157--162.Google Scholar
- Oliver Bühler and Joachim Wegener. 2004. Automatic testing of an autonomous parking system using evolutionary computation. Technical Report. SAE Technical Paper.Google Scholar
- Oliver Bühler and Joachim Wegener. 2008. Evolutionary functional testing. Computers & Operations Research 35, 10 (2008), 3144--3160. Google ScholarDigital Library
- J. Anthony Capon. 1991. Elementary Statistics for the Social Sciences: Study Guide. Wadsworth Publishing Company, Belmont, CA, USA.Google Scholar
- Experiments data. 2017. Experiments data. (aug 2017). https://sites.google.com/site/adasexperimentsdata/Google Scholar
- Kalyanmoy Deb and Ram Bhushan Agrawal. 1995. Simulated binary crossover for continuous search space. Complex systems 9, 2 (1995), 115--148.Google Scholar
- Kalyanmoy Deb and Hans-georg Beyer. 2001. Self-Adaptive Genetic Algorithms with Simulated Binary Crossover. Evolutionary Computation 9, 2 (2001), 197--221. Google ScholarDigital Library
- Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182--197. Google ScholarDigital Library
- Object Management Group. 2017. Object Constraint Language (OCL). (Aug. 2017). Retrieved August 24, 2017 from http://www.omg.org/spec/OCL/Google Scholar
- Mark Harman, S. Afshin Mansouri, and Yuanyuan Zhang. 2012. Search-based software engineering: Trends, techniques and applications. Comput. Surveys 45, 1 (2012), 11. Google ScholarDigital Library
- Christopher Henard, Mike Papadakis, Gilles Perrouin, Jacques Klein, and Yves Le Traon. 2013. PLEDGE: a product line editor and test generation tool. In Proceedings of the International Software Product Line Conference co-located workshops (SPLC'13). ACM, New York, NY, USA, 126--129. Google ScholarDigital Library
- IEE. 2017. International Electronics & Engineering. (aug 2017). Retrieved August 24, 2017 from https://www.iee.lu/Google Scholar
- TASS International. 2017. PreScan simulation of ADAS and active safety. (Aug. 2017). Retrieved August 24, 2017 from https://www.tassinternational.com/prescanGoogle Scholar
- Joshua D. Knowles, Lothar Thiele, and Eckart Zitzler. 2006. A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers. Technical Report. Computer Engineering and Networks Laboratory of Zurich.Google Scholar
- Philip Koopman and Michael Wagner. 2016. Challenges in autonomous vehicle testing and validation. SAE International Journal of Transportation Safety 4, 1 (2016), 15--24.Google ScholarCross Ref
- D. Richard Kuhn, Dolores R. Wallace, and Albert M. Gallo. 2004. Software Fault Interactions and Implications for Software Testing. IEEE Transactions on Software Engineering 30, 6 (2004), 418--421. Google ScholarDigital Library
- Sean Luke. 2013. Essentials of Metaheuristics (second ed.). Lulu, Fairfax, Virginie, USA. Available for free at http://cs.gmu.edu/~sean/book/metaheuristics/.Google Scholar
- Phil McMinn. 2004. Search-based software test data generation: a survey. Software Testing Verification and Reliability Journal 14, 2 (2004), 105--156. Google ScholarDigital Library
- Ryszard S Michalski. 2000. Learnable evolution model: Evolutionary processes guided by machine learning. Machine learning 38, 1 (2000), 9--40. Google ScholarDigital Library
- Anirban Mukhopadhyay, Ujjwal Maulik, Sanghamitra Bandyopadhyay, and Carlos Artemio Coello Coello. 2014. A Survey of Multiobjective Evolutionary Algorithms for Data Mining: Part I. IEEE Transactions on Evolutionary Computation 18, 1(2014), 4--19. Google ScholarDigital Library
- Vasanth Philomin, Ramani Duraiswami, and Larry Davis. 2000. Pedestrian tracking from a moving vehicle. In Proceedings of the IEEE Intelligent Vehicles Symposium (IV'2000). IEEE, Dearborn, MI, USA, 350--355.Google ScholarCross Ref
- Mugur Tatar. 2016. Test and Validation of Advanced Driver Assistance Systems Automated Search for Critical Scenarios. ATZelektronik worldwide 11, 1 (2016), 54--57.Google Scholar
- Richard van der Horst and Jeroen Hogema. 1993. Time-to-collision and collision avoidance systems. In Proceedings of the workshop of the International Cooperation on Theories and Concepts in Traffic Safety (ICTCT'93).-, Salzburg, Austria, 109--21.Google Scholar
- David A. Van Veldhuizen and Gary B. Lamont. 1998. Multiobjective evolutionary algorithm research: A history and analysis. Technical Report. Air Force Institute of Technology.Google Scholar
- András Vargha and Harold D. Delaney. 2000. A critique and improvement of the CL common language effect size statistics of McGraw and Wong. Journal of Educational andBehavioral Statistics 25, 2 (2000), 101--132.Google Scholar
- Shuai Wang, Shaukat Ali, Tao Yue, Yan Li, and Marius Liaaen. 2016. A Practical Guide to Select Quality Indicators for Assessing Pareto-Based Search Algorithms in Search-Based Software Engineering. In Proceedings of the International Conference on Software Engineering (ICSE' 16). ACM, New York, NY, USA, 631--642. Google ScholarDigital Library
- Ian H. Witten, Eibe Frank, and Mark A. Hall. 2011. Data Mining: Practical Machine Learning Tools and Techniques (3rd ed.). Morgan Kaufmann Publishers Inc., USA. Google ScholarDigital Library
- Claes Wohlin, Per Runeson, Martin Höst, Magnus C Ohlsson, Björn Regnell, and Anders Wesslén. 2012. Experimentation in software engineering. Springer-Verlag, Berlin Heidelberg. Google ScholarDigital Library
- Janusz Wojtusiak and Ryszard S Michalski. 2004. The LEM3 implementation of learnable evolution model: user's guide. In Proceedings of the Machine Learning and Inference Laboratory, George Mason University, (MLI'04). Citeseer, Fairfax, Virginie, USA, 04--05.Google Scholar
- Andreas Zeller. 2017. Search-Based Testing and System Testing: A Marriage in Heaven. In Proceedings of the International Workshop on Search-Based Software Testing (SBST'17). IEEE, Piscataway, NJ, USA, 49--50. Google ScholarDigital Library
- Eckart Zitzler and Lothar Thiele. 1999. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation 3, 4 (1999), 257--271. Google ScholarDigital Library
Index Terms
- Testing vision-based control systems using learnable evolutionary algorithms
Recommendations
Object-Oriented Evolutionary Testing: A Review of Evolutionary Approaches to the Generation of Test Data for Object-Oriented Software
In Object-Oriented Evolutionary Testing, metaheuristics are employed to select or generate Test Data for Object-Oriented software. The application of search-based strategies to the Software Testing of Object-Oriented Software is fairly recent and is yet ...
Evolutionary functional testing
The development and testing of software-based systems is an essential activity for the automotive industry. The 50-70 software-based systems with different complexities and developed by various suppliers are installed in today's premium vehicles, ...
Fault-based test suite prioritization for specification-based testing
Context: Existing test suite prioritization techniques usually rely on code coverage information or historical execution data that serve as indicators for estimating the fault-detecting ability of test cases. Such indicators are primarily empirical in ...
Comments