{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T01:12:21Z","timestamp":1780708341688,"version":"3.54.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,2]],"date-time":"2019-11-02T00:00:00Z","timestamp":1572652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Cyber-Phys. Syst."],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>The trend of connected\/autonomous features adds significant complexity to the traditional automotive systems to improve driving safety and comfort. Engineers are facing significant challenges in designing test environments that are more complex than ever. We propose a test framework that allows one to automatically generate various virtual road environments from the path and behavior specifications. The path specification intends to characterize geometric paths that an environmental object (e.g., a roadway or a pedestrian) needs to be visualized or move over. We characterize this aspect in the form of constraints of 3-Dimensional (3D) coordinates. Then, we introduce a test coverage, called an area coverage, to quantify the quality of the generated paths in terms of how diverse of an area the generated paths can cover. We propose an algorithm that automatically generates such paths using an SMT (Satisfiability Modulo Theories) solver. However, the behavioral specification intends to characterize how an environmental object changes its mode over time by interacting with other objects (e.g., a pedestrian waits for a signal or starts crossing). We characterize this aspect in the form of timed automata. Then, we introduce a test coverage, called an edge\/location coverage, to quantify the quality of the generated mode changes in terms of how many modes or transitions are visited. We propose a method that automatically generates many different mode changes using a model-checking. To demonstrate the test framework, we developed the right-turn pedestrian warning system in intersection scenarios and generated many different types of pedestrian paths and behaviors to analyze the effectiveness of the system.<\/jats:p>","DOI":"10.1145\/3311954","type":"journal-article","created":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T14:04:16Z","timestamp":1572876256000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Test Specification and Generation for Connected and Autonomous Vehicle in Virtual Environments"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7892-5191","authenticated-orcid":false,"given":"Baekgyu","family":"Kim","sequence":"first","affiliation":[{"name":"Toyota InfoTechnology Center, U.S.A."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Takato","family":"Masuda","sequence":"additional","affiliation":[{"name":"Toyota InfoTechnology Center, U.S.A."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shinichi","family":"Shiraishi","sequence":"additional","affiliation":[{"name":"Toyota InfoTechnology Center, U.S.A."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90010-8"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 33rd International Conference on Software Engineering (ICSE\u201911)","author":"Godefroid Patrice","year":"2011","unstructured":"ristian Cadar, Patrice Godefroid , Sarfraz Khurshid , Corina S. P\u0103s\u0103reanu , Koushik Sen , Nikolai Tillmann , and Willem Visser . 2011 . Symbolic execution for software testing in practice: Preliminary assessment . In Proceedings of the 33rd International Conference on Software Engineering (ICSE\u201911) . ristian Cadar, Patrice Godefroid, Sarfraz Khurshid, Corina S. P\u0103s\u0103reanu, Koushik Sen, Nikolai Tillmann, and Willem Visser. 2011. Symbolic execution for software testing in practice: Preliminary assessment. In Proceedings of the 33rd International Conference on Software Engineering (ICSE\u201911)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2002.1049402"},{"key":"e_1_2_1_4_1","first-page":"429","article-title":"Procedural generation of roads","volume":"29","author":"Galin Eric","year":"2010","unstructured":"Eric Galin , Adrien Peytavie , Nicolas Mar\u00e9chal , and Eric Gu\u00e9rin . 2010 . Procedural generation of roads . Comput. Graph. For. 29 , 2 (2010), 429 -- 438 . Eric Galin, Adrien Peytavie, Nicolas Mar\u00e9chal, and Eric Gu\u00e9rin. 2010. Procedural generation of roads. Comput. Graph. For. 29, 2 (2010), 429--438.","journal-title":"Comput. Graph. For."},{"key":"e_1_2_1_5_1","volume-title":"SAGE: Whitebox fuzzing for security testing. Queue 10, 1, Article 20 (Jan.","author":"Godefroid Patrice","year":"2012","unstructured":"Patrice Godefroid , Michael Y. Levin , and David Molnar . 2012 . SAGE: Whitebox fuzzing for security testing. Queue 10, 1, Article 20 (Jan. 2012), 8 pages. Patrice Godefroid, Michael Y. Levin, and David Molnar. 2012. SAGE: Whitebox fuzzing for security testing. Queue 10, 1, Article 20 (Jan. 2012), 8 pages."},{"key":"e_1_2_1_6_1","volume-title":"Testing real-time systems using UPPAAL. Formal Methods and Testing","author":"Hessel Anders","year":"1806","unstructured":"Anders Hessel , Kim G. Larsen , Marius Mikucionis , Brian Nielsen , Paul Pettersson , and Arne Skou . 2008. Testing real-time systems using UPPAAL. Formal Methods and Testing . Springer-Verlag , Berlin , 77--117. Retrieved from: http:\/\/dl.acm.org\/citation.cfm?id&equals; 1806 209.1806212. Anders Hessel, Kim G. Larsen, Marius Mikucionis, Brian Nielsen, Paul Pettersson, and Arne Skou. 2008. Testing real-time systems using UPPAAL. Formal Methods and Testing. Springer-Verlag, Berlin, 77--117. Retrieved from: http:\/\/dl.acm.org\/citation.cfm?id&equals;1806209.1806212."},{"key":"e_1_2_1_7_1","unstructured":"Texas Transportation Institute and Southwest Region University Transportation Center (U.S.). 2011. Automated Generation of Virtual Scenarios in Driving Simulator from Highway Design Data. https:\/\/rosap.ntl.bts.gov\/view\/dot\/23113.  Texas Transportation Institute and Southwest Region University Transportation Center (U.S.). 2011. Automated Generation of Virtual Scenarios in Driving Simulator from Highway Design Data. https:\/\/rosap.ntl.bts.gov\/view\/dot\/23113."},{"key":"e_1_2_1_8_1","unstructured":"ISO15622. 2018. Intelligent transport systems\u2014Adaptive Cruise Control systems\u2014Performance requirements and test procedures. https:\/\/www.iso.org\/standard\/71515.html.  ISO15622. 2018. Intelligent transport systems\u2014Adaptive Cruise Control systems\u2014Performance requirements and test procedures. https:\/\/www.iso.org\/standard\/71515.html."},{"key":"e_1_2_1_9_1","unstructured":"ISO17387. 2008. Intelligent transport systems\u2014Lane change decision aid systems (LCDAS)\u2014Performance requirements and test procedures. https:\/\/www.iso.org\/standard\/43654.html.  ISO17387. 2008. Intelligent transport systems\u2014Lane change decision aid systems (LCDAS)\u2014Performance requirements and test procedures. https:\/\/www.iso.org\/standard\/43654.html."},{"key":"e_1_2_1_10_1","unstructured":"ISO19237. 2017. Intelligent transport systems\u2014Pedestrian detection and collision mitigation systems (PDCMS)\u2014Performance requirements and test procedures. https:\/\/www.iso.org\/standard\/64111.html.  ISO19237. 2017. Intelligent transport systems\u2014Pedestrian detection and collision mitigation systems (PDCMS)\u2014Performance requirements and test procedures. https:\/\/www.iso.org\/standard\/64111.html."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/IVEC.1999.830704"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2008.10.004"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 14th Conference on Winter Simulation\u2014Volume 1.","author":"Kavanagh R. J.","unstructured":"R. J. Kavanagh and R. Ramanathan . 1982. Computer simulation of road surface profiles for a four-wheeled vehicle . In Proceedings of the 14th Conference on Winter Simulation\u2014Volume 1. R. J. Kavanagh and R. Ramanathan. 1982. Computer simulation of road surface profiles for a four-wheeled vehicle. In Proceedings of the 14th Conference on Winter Simulation\u2014Volume 1."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Conference on Embedded Software (EMSOFT\u201916)","author":"Kim B.","unstructured":"B. Kim , A. Jarandikar , J. Shum , S. Shiraishi , and M. Yamaura . 2016. The SMT-based automatic road network generation in vehicle simulation environment . In Proceedings of the International Conference on Embedded Software (EMSOFT\u201916) . 1--10. DOI:https:\/\/doi.org\/10.1145\/2968478.2968498 10.1145\/2968478.2968498 B. Kim, A. Jarandikar, J. Shum, S. Shiraishi, and M. Yamaura. 2016. The SMT-based automatic road network generation in vehicle simulation environment. In Proceedings of the International Conference on Embedded Software (EMSOFT\u201916). 1--10. DOI:https:\/\/doi.org\/10.1145\/2968478.2968498"},{"key":"e_1_2_1_15_1","first-page":"1","article-title":"Testing autonomous vehicle software in the virtual prototyping environment","volume":"9","author":"Kim B.","year":"2017","unstructured":"B. Kim , Y. Kashiba , S. Dai , and S. Shiraishi . 2017 . Testing autonomous vehicle software in the virtual prototyping environment . IEEE Embed. Syst. Lett. 9 , 1 (Mar. 2017), 5--8. DOI:https:\/\/doi.org\/10.1109\/LES.2016.2644619 10.1109\/LES.2016.2644619 B. Kim, Y. Kashiba, S. Dai, and S. Shiraishi. 2017. Testing autonomous vehicle software in the virtual prototyping environment. IEEE Embed. Syst. Lett. 9, 1 (Mar. 2017), 5--8. DOI:https:\/\/doi.org\/10.1109\/LES.2016.2644619","journal-title":"IEEE Embed. Syst. Lett."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24732-6_8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31848-4_6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100090050010"},{"key":"e_1_2_1_19_1","volume-title":"Larsen and Wang Yi","author":"Kim","year":"1994","unstructured":"Kim G. Larsen and Wang Yi . 1994 . Time Abstracted Bisimulation: Implicit Specifications and Decidability. Springer Berlin , 160--176. DOI:https:\/\/doi.org\/10.1007\/3-540-58027-1_8 10.1007\/3-540-58027-1_8 Kim G. Larsen and Wang Yi. 1994. Time Abstracted Bisimulation: Implicit Specifications and Decidability. Springer Berlin, 160--176. DOI:https:\/\/doi.org\/10.1007\/3-540-58027-1_8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370036.2145844"},{"key":"e_1_2_1_21_1","volume-title":"The Atlantic","author":"Madrigal A.","year":"2017","unstructured":"A. Madrigal . 2017 . Inside Waymo\u2019s secret world for training self-driving cars . The Atlantic , Aug. 23 (2017). Retrieved from: https:\/\/www.theatlantic.com\/technology\/archive\/ 2017\/08\/inside-waymos-secret-testing-and-simulation-facilities\/537648\/. A. Madrigal. 2017. Inside Waymo\u2019s secret world for training self-driving cars. The Atlantic, Aug. 23 (2017). Retrieved from: https:\/\/www.theatlantic.com\/technology\/archive\/2017\/08\/inside-waymos-secret-testing-and-simulation-facilities\/537648\/."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-009-0118-1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20398-5_22"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183278.1183282"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference.","author":"Zhao S.","unstructured":"S. Zhao and J. A. Farrell . 2011. Optimization-based road curve fitting . In Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference. S. Zhao and J. A. Farrell. 2011. Optimization-based road curve fitting. In Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference."}],"container-title":["ACM Transactions on Cyber-Physical Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3311954","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3311954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:12Z","timestamp":1750204392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3311954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,2]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3311954"],"URL":"https:\/\/doi.org\/10.1145\/3311954","relation":{},"ISSN":["2378-962X","2378-9638"],"issn-type":[{"value":"2378-962X","type":"print"},{"value":"2378-9638","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,2]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}