{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T03:27:09Z","timestamp":1752982029175,"version":"3.40.4"},"reference-count":44,"publisher":"MIT Press","issue":"1","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Describing the properties of complex systems that evolve over time is a crucial requirement for monitoring and understanding them. Signal Temporal Logic (STL) is a framework that proved to be effective for this aim because it is expressive and allows state properties as human-readable formulae. Crafting STL formulae that fit a particular system is, however, a difficult task. For this reason, a few approaches have been proposed recently for the automatic learning of STL formulae starting from observations of the system. In this paper, we propose BUSTLE (Bi-level Universal STL Evolver), an approach based on evolutionary computation for learning STL formulae from data. BUSTLE advances the state of the art because it (i) applies to a broader class of problems, in terms of what is known about the state of the system during its observation, and (ii) generates both the structure and the values of the parameters of the formulae employing a bi-level search mechanism (global for the structure, local for the parameters). We consider two cases where (a) observations of the system in both anomalous and regular state are available, or (b) only observations of regular state are available. We experimentally evaluate BUSTLE on problem instances corresponding to the two cases and compare it against previous approaches. We show that the evolved STL formulae are effective and human-readable: the versatility of BUSTLE does not come at the cost of lower effectiveness.<\/jats:p>","DOI":"10.1162\/evco_a_00347","type":"journal-article","created":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T22:57:11Z","timestamp":1708469831000},"page":"91-114","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":2,"title":["BUSTLE: A Versatile Tool for the Evolutionary Learning of STL Specifications from Data"],"prefix":"10.1162","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3315-6768","authenticated-orcid":true,"given":"Federico","family":"Pigozzi","sequence":"first","affiliation":[{"name":"Department of Engineering and Architecture, University of Trieste, Trieste, Italy federico.pigozzi@phd.units.it"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2263-9342","authenticated-orcid":true,"given":"Laura","family":"Nenzi","sequence":"additional","affiliation":[{"name":"Department of Engineering and Architecture, University of Trieste, Trieste, Italy lnenzi@units.it"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5652-2113","authenticated-orcid":true,"given":"Eric","family":"Medvet","sequence":"additional","affiliation":[{"name":"Department of Engineering and Architecture, University of Trieste, Trieste, Italy emedvet@units.it"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2025,3,15]]},"reference":[{"key":"2025042916155998400_B1","first-page":"547","article-title":"Time-incremental learning of temporal logic classifiers using decision trees","volume-title":"Learning for Dynamics and Control Conference","author":"Aasi","year":"2023"},{"key":"2025042916155998400_B2","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/978-3-642-29860-8_12","article-title":"Parametric identification of temporal properties","author":"Asarin","year":"2012","journal-title":"Runtime Verification: Second International Conference, Revised Selected Papers 2"},{"key":"2025042916155998400_B3","first-page":"186","article-title":"The best things don't always come in small packages: Constant creation in grammatical evolution","volume-title":"European Conference on Genetic Programming","author":"Azad","year":"2014"},{"key":"2025042916155998400_B4","doi-asserted-by":"publisher","DOI":"10.1016\/j.nahs.2022.101254","article-title":"Adaptive testing for specification coverage and refinement in CPS models","volume":"46","author":"Bartocci","year":"2022","journal-title":"Nonlinear Analysis: Hybrid Systems"},{"key":"2025042916155998400_B5","first-page":"417","article-title":"MoonLight: A lightweight tool for monitoring spatio-temporal properties","volume":"12399","author":"Bartocci","year":"2020","journal-title":"Proceedings of the 20th International Conference"},{"key":"2025042916155998400_B6","first-page":"23","article-title":"Data-driven statistical learning of temporal logic properties","author":"Bartocci","year":"2014","journal-title":"Proceedings of FORMATS"},{"key":"2025042916155998400_B7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-319-75632-5_5","article-title":"Specification-based monitoring of cyber-physical systems: A survey on theory, tools and applications","volume":"10457","author":"Bartocci","year":"2018","journal-title":"Lectures on Runtime Verification"},{"key":"2025042916155998400_B8","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2022.104957","article-title":"Survey on mining signal temporal logic specifications","author":"Bartocci","year":"2022","journal-title":"Information and Computation"},{"key":"2025042916155998400_B9","first-page":"614","article-title":"A language and an inference engine for Twitter filtering rules","author":"Bartoli","year":"2016","journal-title":"IEEE\/WIC\/ACM International Conference on Web Intelligence"},{"key":"2025042916155998400_B10","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2019.105599","article-title":"Multi-level diversity promotion strategies for grammar-guided genetic programming","volume":"83","author":"Bartoli","year":"2019","journal-title":"Applied Soft Computing"},{"key":"2025042916155998400_B11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3433994","article-title":"Offline and online learning of signal temporal logic formulae using decision trees","volume":"5","author":"Bombara","year":"2021","journal-title":"ACM Transactions on Cyber-Physical Systems"},{"key":"2025042916155998400_B12","first-page":"1","article-title":"A decision tree approach to data classification using signal temporal logic","author":"Bombara","year":"2016","journal-title":"Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control"},{"key":"2025042916155998400_B13","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.eswa.2019.04.007","article-title":"Learning of complex event processing rules with genetic programming","volume":"129","author":"Bruns","year":"2019","journal-title":"Expert Systems with Applications"},{"key":"2025042916155998400_B14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-10575-8","volume-title":"Handbook of model checking","author":"Clarke","year":"2018"},{"issue":"1","key":"2025042916155998400_B15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1504\/IJICA.2007.013399","article-title":"Constant creation in grammatical evolution","volume":"1","author":"Dempsey","year":"2007","journal-title":"International Journal of Innovative Computing and Applications"},{"key":"2025042916155998400_B16","first-page":"264","article-title":"Efficient robust monitoring for STL","author":"Donz\u00e9","year":"2013","journal-title":"Proceedings of Computer Aided Verification"},{"issue":"1","key":"2025042916155998400_B17","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10009-017-0447-4","article-title":"Mining parametric temporal logic properties in model-based design for cyber-physical systems","volume":"20","author":"Hoxha","year":"2018","journal-title":"International Journal on Software Tools for Technology Transfer"},{"key":"2025042916155998400_B18","first-page":"186","article-title":"One-shot learning of ensembles of temporal logic formulas for anomaly detection in cyber-physical systems","author":"Indri","year":"2022","journal-title":"European Conference on Genetic Programming"},{"key":"2025042916155998400_B19","first-page":"1","article-title":"TeLEx: Learning signal temporal logic from positive examples using tightness metric","author":"Jha","year":"2019","journal-title":"Formal Methods in System Design"},{"issue":"11","key":"2025042916155998400_B20","doi-asserted-by":"publisher","first-page":"1704","DOI":"10.1109\/TCAD.2015.2421907","article-title":"Mining requirements from closed-loop control models","volume":"34","author":"Jin","year":"2015","journal-title":"IEEE Transactions on CAD of Integrated Circuits and Systems"},{"volume-title":"Genetic programming: On the programming of computers by means of natural selection","year":"1992","author":"Koza","key":"2025042916155998400_B21"},{"volume-title":"Essentials of metaheuristics","year":"2009","author":"Luke","key":"2025042916155998400_B22"},{"key":"2025042916155998400_B23","first-page":"152","article-title":"Monitoring temporal properties of continuous signals","volume":"3253","author":"Maler","year":"2004","journal-title":"Proceedings of FORMATS"},{"issue":"3","key":"2025042916155998400_B24","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s10009-012-0247-9","article-title":"Monitoring properties of analog and mixed-signal circuits","volume":"15","author":"Maler","year":"2013","journal-title":"International Journal on Software Tools for Technology Transfer"},{"year":"2018","author":"Marcus","article-title":"Deep learning: A critical appraisal","key":"2025042916155998400_B25"},{"key":"2025042916155998400_B26","first-page":"173","article-title":"Road traffic rules synthesis using grammatical evolution","author":"Medvet","year":"2017","journal-title":"European Conference on the Applications of Evolutionary Computation"},{"key":"2025042916155998400_B27","doi-asserted-by":"crossref","first-page":"2009","DOI":"10.1145\/3520304.3533960","article-title":"JGEA: A Modular Java framework for experimenting with evolutionary computation","author":"Medvet","year":"2022","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference Companion"},{"key":"2025042916155998400_B28","first-page":"9:1","article-title":"Interpretable classification of time-series data using efficient enumerative techniques","author":"Mohammadinejad","year":"2020","journal-title":"23rd ACM International Conference on Hybrid Systems: Computation and Control"},{"key":"2025042916155998400_B29","article-title":"Interpretable classification of time-series data using efficient enumerative techniques","author":"Mohammadinejad","year":"2020","journal-title":"Proceedings of the 23rd International Conference on Hybrid Systems: Computation and Control"},{"issue":"1","key":"2025042916155998400_B30","article-title":"A logic for monitoring dynamic networks of spatially-distributed cyber-physical systems","volume":"18","author":"Nenzi","year":"2022","journal-title":"Logical Methods in Computer Science"},{"key":"2025042916155998400_B31","first-page":"1","article-title":"MoonLight: A lightweight tool for monitoring spatio-temporal properties","author":"Nenzi","year":"2023","journal-title":"International Journal on Software Tools for Technology Transfer"},{"key":"2025042916155998400_B32","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/978-3-319-99154-2_20","article-title":"A robust genetic algorithm for learning temporal specifications from data","author":"Nenzi","year":"2018","journal-title":"International Conference on Quantitative Evaluation of Systems"},{"key":"2025042916155998400_B33","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/3049797.3049809","article-title":"Abnormal data classification using time-frequency temporal logic","author":"Nguyen","year":"2017","journal-title":"Proceedings of Hybrid Systems, Computation, and Control"},{"key":"2025042916155998400_B34","first-page":"95","article-title":"Active protocol discoverer based on grammatical evolution","author":"Pa\u0142ka","year":"2017","journal-title":"International Conference on Information Systems Architecture and Technology"},{"issue":"22","key":"2025042916155998400_B35","doi-asserted-by":"publisher","DOI":"10.3390\/app112210573","article-title":"Mining road traffic rules with signal temporal logic and grammar-based genetic programming","volume":"11","author":"Pigozzi","year":"2021","journal-title":"Applied Sciences"},{"key":"2025042916155998400_B36","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3206.001.0001","volume-title":"Gaussian processes for machine learning (adaptive computation and machine learning)","author":"Rasmussen","year":"2005"},{"key":"2025042916155998400_B37","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2021.109781","article-title":"Data-driven verification of stochastic linear systems with signal temporal logic constraints","volume":"131","author":"Salamati","year":"2021","journal-title":"Automatica"},{"key":"2025042916155998400_B38","doi-asserted-by":"publisher","first-page":"782","DOI":"10.1016\/j.ins.2015.09.056","article-title":"Divergence of character and premature convergence: A survey of methodologies for promoting diversity in evolutionary optimization","volume":"329","author":"Squillero","year":"2016","journal-title":"Information Sciences"},{"key":"2025042916155998400_B39","doi-asserted-by":"publisher","first-page":"3250","DOI":"10.1109\/TIT.2011.2182033","article-title":"Information-theoretic regret bounds for Gaussian process optimization in the bandit setting","volume":"58","author":"Srinivas","year":"2012","journal-title":"IEEE Transactions on Information Theory"},{"key":"2025042916155998400_B40","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2019.100640","article-title":"On explaining machine learning models by evolving crucial and compact features","volume":"53","author":"Virgolin","year":"2020","journal-title":"Swarm and Evolutionary Computation"},{"key":"2025042916155998400_B41","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-3-030-58115-2_6","article-title":"Learning a formula of interpretability to learn interpretable formulas","author":"Virgolin","year":"2020","journal-title":"Parallel Problem Solving from Nature"},{"year":"2022","author":"Virgolin","article-title":"Less is more: A call to focus on simpler models in genetic programming for interpretable machine learning","key":"2025042916155998400_B42"},{"key":"2025042916155998400_B43","first-page":"461","article-title":"Inductive bias and genetic programming","author":"Whigham","year":"1995","journal-title":"First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications"},{"issue":"1","key":"2025042916155998400_B44","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1109\/TASE.2016.2611536","article-title":"Census signal temporal logic inference for multiagent group behavior analysis","volume":"15","author":"Xu","year":"2018","journal-title":"IEEE Transactions on Automation Science and Engineering"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/1\/91\/2468778\/evco_a_00347.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/1\/91\/2468778\/evco_a_00347.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:16:11Z","timestamp":1745957771000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/33\/1\/91\/119669\/BUSTLE-A-Versatile-Tool-for-the-Evolutionary"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":44,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,3,15]]},"published-print":{"date-parts":[[2025,3,15]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00347","relation":{},"ISSN":["1530-9304"],"issn-type":[{"type":"electronic","value":"1530-9304"}],"subject":[],"published-other":{"date-parts":[[2025]]},"published":{"date-parts":[[2025]]}}}