Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming
Traffic systems, where human and autonomous drivers interact, are a very relevant instance of complex systems and produce behaviors that can be regarded as trajectories over time. Their monitoring can be achieved by means of carefully stated properties describing the expected behavior. Such properti...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-11-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/11/22/10573 |
| _version_ | 1797511353927204864 |
|---|---|
| author | Federico Pigozzi Eric Medvet Laura Nenzi |
| author_facet | Federico Pigozzi Eric Medvet Laura Nenzi |
| author_sort | Federico Pigozzi |
| collection | DOAJ |
| description | Traffic systems, where human and autonomous drivers interact, are a very relevant instance of complex systems and produce behaviors that can be regarded as trajectories over time. Their monitoring can be achieved by means of carefully stated properties describing the expected behavior. Such properties can be expressed using Signal Temporal Logic (STL), a specification language for expressing temporal properties in a formal and human-readable way. However, manually authoring these properties is a hard task, since it requires mastering the language and knowing the system to be monitored. Moreover, in practical cases, the expected behavior is not known, but it has instead to be inferred from a set of trajectories obtained by observing the system. Often, those trajectories come devoid of human-assigned labels that can be used as an indication of compliance with expected behavior. As an alternative to manual authoring, automatic mining of STL specifications from unlabeled trajectories would enable the monitoring of autonomous agents without sacrificing human-readability. In this work, we propose a grammar-based evolutionary computation approach for mining the structure and the parameters of an STL specification from a set of unlabeled trajectories. We experimentally assess our approach on a real-world road traffic dataset consisting of thousands of vehicle trajectories. We show that our approach is effective at mining STL specifications that model the system at hand and are interpretable for humans. To the best of our knowledge, this is the first such study on a set of unlabeled real-world road traffic data. Being able to mine interpretable specifications from this kind of data may improve traffic safety, because mined specifications may be helpful for monitoring traffic and planning safety promotion strategies. |
| first_indexed | 2024-03-10T05:44:09Z |
| format | Article |
| id | doaj.art-62a80a53101049e0b56cae4509bdf4ab |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T05:44:09Z |
| publishDate | 2021-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-62a80a53101049e0b56cae4509bdf4ab2023-11-22T22:15:45ZengMDPI AGApplied Sciences2076-34172021-11-0111221057310.3390/app112210573Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic ProgrammingFederico Pigozzi0Eric Medvet1Laura Nenzi2Department of Engineering and Architecture, University of Trieste, 34127 Trieste, ItalyDepartment of Engineering and Architecture, University of Trieste, 34127 Trieste, ItalyDepartment of Mathematics and Geosciences, University of Trieste, 34127 Trieste, ItalyTraffic systems, where human and autonomous drivers interact, are a very relevant instance of complex systems and produce behaviors that can be regarded as trajectories over time. Their monitoring can be achieved by means of carefully stated properties describing the expected behavior. Such properties can be expressed using Signal Temporal Logic (STL), a specification language for expressing temporal properties in a formal and human-readable way. However, manually authoring these properties is a hard task, since it requires mastering the language and knowing the system to be monitored. Moreover, in practical cases, the expected behavior is not known, but it has instead to be inferred from a set of trajectories obtained by observing the system. Often, those trajectories come devoid of human-assigned labels that can be used as an indication of compliance with expected behavior. As an alternative to manual authoring, automatic mining of STL specifications from unlabeled trajectories would enable the monitoring of autonomous agents without sacrificing human-readability. In this work, we propose a grammar-based evolutionary computation approach for mining the structure and the parameters of an STL specification from a set of unlabeled trajectories. We experimentally assess our approach on a real-world road traffic dataset consisting of thousands of vehicle trajectories. We show that our approach is effective at mining STL specifications that model the system at hand and are interpretable for humans. To the best of our knowledge, this is the first such study on a set of unlabeled real-world road traffic data. Being able to mine interpretable specifications from this kind of data may improve traffic safety, because mined specifications may be helpful for monitoring traffic and planning safety promotion strategies.https://www.mdpi.com/2076-3417/11/22/10573context-free grammar genetic programminggrammatical evolutiontraffic monitoringformal methods |
| spellingShingle | Federico Pigozzi Eric Medvet Laura Nenzi Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming Applied Sciences context-free grammar genetic programming grammatical evolution traffic monitoring formal methods |
| title | Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming |
| title_full | Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming |
| title_fullStr | Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming |
| title_full_unstemmed | Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming |
| title_short | Mining Road Traffic Rules with Signal Temporal Logic and Grammar-Based Genetic Programming |
| title_sort | mining road traffic rules with signal temporal logic and grammar based genetic programming |
| topic | context-free grammar genetic programming grammatical evolution traffic monitoring formal methods |
| url | https://www.mdpi.com/2076-3417/11/22/10573 |
| work_keys_str_mv | AT federicopigozzi miningroadtrafficruleswithsignaltemporallogicandgrammarbasedgeneticprogramming AT ericmedvet miningroadtrafficruleswithsignaltemporallogicandgrammarbasedgeneticprogramming AT lauranenzi miningroadtrafficruleswithsignaltemporallogicandgrammarbasedgeneticprogramming |