{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:08:19Z","timestamp":1750219699951,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,11,23]],"date-time":"2023-11-23T00:00:00Z","timestamp":1700697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Knowledge Foundation (KKS) in the framework of \u201cSafety of Connected Intelligent Vehicles in Smart Cities \u2013 SafeSmart\u201d project","award":["2019\u20132023"],"award-info":[{"award-number":["2019\u20132023"]}]},{"name":"UKRI Trustworthy Autonomous Systems Node in Verifiability","award":["EP\/V026801\/2"],"award-info":[{"award-number":["EP\/V026801\/2"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>Automatic generation of random test inputs is an approach that can alleviate the challenges of manual test case design. However, random test cases may be ineffective in fault detection and increase testing cost, especially in systems where test execution is resource- and time-consuming. To remedy this, the domain knowledge of test engineers can be exploited to select potentially effective test cases. To this end, test selection constraints suggested by domain experts can be utilized either for filtering randomly generated test inputs or for direct generation of inputs using constraint solvers. In this article, we propose a domain specific language (DSL) for formalizing locality-based test selection constraints of autonomous agents and discuss the impact of test selection filters, specified in our DSL, on randomly generated test cases. We study and compare the performance of filtering and constraint solving approaches in generating selective test cases for different test scenario parameters and discuss the role of these parameters in test generation performance. Through our study, we provide criteria for suitability of the random data filtering approach versus the constraint solving one under the varying size and complexity of our testing problem. We formulate the corresponding research questions and answer them by designing and conducting experiments using QuickCheck for random test data generation with filtering and Z3 for constraint solving. Our observations and statistical analysis indicate that applying filters can significantly improve test efficiency of randomly generated test cases. Furthermore, we observe that test scenario parameters affect the performance of the filtering and constraint solving approaches differently. In particular, our results indicate that the two approaches have complementary strengths: random generation and filtering works best for large agent numbers and long paths, while its performance degrades in the larger grid sizes and more strict constraints. On the contrary, constraint solving has a robust performance for large grid sizes and strict constraints, while its performance degrades with more agents and long paths.<\/jats:p>","DOI":"10.1145\/3624736","type":"journal-article","created":{"date-parts":[[2023,9,30]],"date-time":"2023-09-30T08:04:43Z","timestamp":1696061083000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Automated and Efficient Test-Generation for Grid-Based Multiagent Systems: Comparing Random Input Filtering versus Constraint Solving"],"prefix":"10.1145","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8929-1750","authenticated-orcid":false,"given":"Sina","family":"Entekhabi","sequence":"first","affiliation":[{"name":"Halmstad University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7054-9985","authenticated-orcid":false,"given":"Wojciech","family":"Mostowski","sequence":"additional","affiliation":[{"name":"Halmstad University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4869-6794","authenticated-orcid":false,"given":"Mohammad Reza","family":"Mousavi","sequence":"additional","affiliation":[{"name":"King\u2019s College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,11,23]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94144-8_9"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2771783.2771802"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1159789.1159792"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST49551.2021.00050"},{"key":"e_1_3_2_6_2","unstructured":"Oliver Carsten Natasha Merat Wiel Janssen Emma Johansson Mark Fowkes and Karel Brookhuis. 2005. Human Machine Interaction and Safety of Traffic in Europe . HASTE Final Report European Commission."},{"key":"e_1_3_2_7_2","volume-title":"Erlang Programming: A Concurrent Approach to Software Development","author":"Cesarini Francesco","year":"2009","unstructured":"Francesco Cesarini and Simon Thompson. 2009. Erlang Programming: A Concurrent Approach to Software Development. O\u2019Reilly Media, Inc."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46681-0_25"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593097"},{"key":"e_1_3_2_10_2","unstructured":"Wayne W. Daniel. 1990. Spearman Rank Correlation Coefficient. Applied Nonparametric Statistics (2nd ed.). PWS-Kent 358\u2013365."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17071-3_13"},{"key":"e_1_3_2_12_2","first-page":"1","volume-title":"Proceedings of the 1st Annual Conference on Robot Learning","author":"Dosovitskiy Alexey","year":"2017","unstructured":"Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun. 2017. CARLA: An open urban driving simulator. In Proceedings of the 1st Annual Conference on Robot Learning. 1\u201316."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180248"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.8208127"},{"key":"e_1_3_2_15_2","first-page":"73","volume-title":"ICTSS 2021: Testing Software and Systems","author":"Entekhabi Sina","year":"2022","unstructured":"Sina Entekhabi, Wojciech Mostowski, Mohammad Reza Mousavi, and Thomas Arts. 2022. Locality-based test selection for autonomous agents. In ICTSS 2021: Testing Software and Systems. D. Clark, H. Menendez, A.R. Cavalli (Eds.), Springer International Publishing, Cham, 73\u201389."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2016.33"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0080456800012163"},{"key":"e_1_3_2_18_2","volume-title":"ASAM OpenSCENARIO v2.0.0","author":"Automation Association for Standardization of","year":"2022","unstructured":"Association for Standardization of Automation and Measuring Systems. 2022. ASAM OpenSCENARIO v2.0.0. ASAM e.v."},{"key":"e_1_3_2_19_2","article-title":"Statistics (International Student Edition)","author":"Freedman David","year":"2007","unstructured":"David Freedman, Robert Pisani, and Roger Purves. 2007. Statistics (International Student Edition) (4th ed.). WW Norton & Company, New York, NY .","journal-title":"(4th ed.). WW Norton & Company, New York, NY"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314633"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE-Companion.2019.00119"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE-Companion.2019.00030"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2015.7102580"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2884781.2884791"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382025.3414951"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2019.2942921"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2771783.2771806"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/b137241"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2017.08.014"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2004.1389727"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2018.8569682"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1952.10483441"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2018.8569938"},{"key":"e_1_3_2_34_2","article-title":"OpenDS: A New Open-Source Driving Simulator for Research","author":"Math Rafael","year":"2013","unstructured":"Rafael Math, Angela Mahr, Mohammad M. Moniri, and Christian M\u00fcller. 2013. OpenDS: A New Open-Source Driving Simulator for Research. GMM-Fachbericht-AmE 2013, VDE-Verlag.","journal-title":"GMM-Fachbericht-AmE 2013"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_2_36_2","volume-title":"The Art of Software Testing (3rd ed.)","author":"Myers Glenford J.","year":"2011","unstructured":"Glenford J. Myers, Corey Sandler, and Tom Badgett. 2011. The Art of Software Testing (3rd ed.). Wiley Publishing."},{"key":"e_1_3_2_37_2","volume-title":"Description of Light-vehicle Pre-crash Scenarios for Safety Applications based on Vehicle-to-vehicle Communications","author":"Najm Wassim G.","year":"2013","unstructured":"Wassim G. Najm, Raja Ranganathan, Gowrishankar Srinivasan, John D. Smith, Samuel Toma, Elizabeth Swanson, and August Burgett. 2013. Description of Light-vehicle Pre-crash Scenarios for Safety Applications based on Vehicle-to-vehicle Communications. Technical Report. National Highway Traffic Safety Administration."},{"key":"e_1_3_2_38_2","volume-title":"Depiction of Priority Light-vehicle Pre-crash Scenarios for Safety Applications based on Vehicle-to-vehicle Communications","author":"Najm Wassim G.","year":"2013","unstructured":"Wassim G. Najm, Samuel Toma, and John Brewer. 2013. Depiction of Priority Light-vehicle Pre-crash Scenarios for Safety Applications based on Vehicle-to-vehicle Communications. Technical Report. National Highway Traffic Safety Administration."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v28i3.2052"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336294.3342359"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3273934.3273944"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/IVS.2019.8814107"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2016.7795734"},{"key":"e_1_3_2_44_2","volume-title":"Artificial Intelligence a Modern Approach","author":"Russell Stuart J.","year":"2021","unstructured":"Stuart J. Russell and Peter Norvig. 2021. Artificial Intelligence a Modern Approach. Pearson Education, Inc."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.2307\/2333709"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/RO-MAN50785.2021.9515560"},{"key":"e_1_3_2_47_2","first-page":"1","article-title":"The probable error of a mean","year":"1908","unstructured":"Student. 1908. The probable error of a mean. Biometrika 6 (1908), 1\u201325.","journal-title":"Biometrika"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/OJITS.2021.3058449"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4380-9_16"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3624736","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3624736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:35:44Z","timestamp":1750178144000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3624736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,23]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3624736"],"URL":"https:\/\/doi.org\/10.1145\/3624736","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"type":"print","value":"1049-331X"},{"type":"electronic","value":"1557-7392"}],"subject":[],"published":{"date-parts":[[2023,11,23]]},"assertion":[{"value":"2022-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}