mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Formal verification of an Autonomous Wheel Loader by model checking
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-7663-5497
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0003-2870-2680
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0003-0904-3712
2018 (English)In: Proceedings - International Conference on Software Engineering, IEEE Computer Society , 2018, p. 74-83Conference paper, Published paper (Refereed)
Abstract [en]

In an attempt to increase productivity and the workers' safety, the construction industry is moving towards autonomous construction sites, where various construction machines operate without human intervention. In order to perform their tasks autonomously, the machines are equipped with different features, such as position localization, human and obstacle detection, collision avoidance, etc. Such systems are safety critical, and should operate autonomously with very high dependability (e.g., by meeting task deadlines, avoiding (fatal) accidents at all costs, etc.). An Autonomous Wheel Loader is a machine that transports materials within the construction site without a human in the cab. To check the dependability of the loader, in this paper we provide a timed automata description of the vehicle's control system, including the abstracted path planning and collision avoidance algorithms used to navigate the loader, and we model check the encoding in UPPAAL, against various functional, timing and safety requirements. The complex nature of the navigation algorithms makes the loader's abstract modeling and the verification very challenging. Our work shows that exhaustive verification techniques can be applied early in the development of autonomous systems, to enable finding potential design errors that would incur increased costs if discovered later.

Place, publisher, year, edition, pages
IEEE Computer Society , 2018. p. 74-83
Keywords [en]
Autonomous Vehicle, Collision Avoidance, Formal Verification, Model Checking, Timed Automata, UPPAAL, Accident prevention, Automata theory, Construction equipment, Construction industry, Loaders, Mining machinery, Motion planning, Obstacle detectors, Wheels, Autonomous constructions, Autonomous Vehicles, Construction machines, Navigation algorithms, Safety requirements, Verification techniques
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:mdh:diva-40747DOI: 10.1145/3193992.3193999Scopus ID: 2-s2.0-85059102764ISBN: 9781450357180 (print)OAI: oai:DiVA.org:mdh-40747DiVA, id: diva2:1246513
Conference
6th ACM/IEEE Conference on Formal Methods in Software Engineering, FormaliSE 2018, co-located with International Conference on Software Engineering, ICSE 2018, 2 June 2018
Available from: 2018-09-07 Created: 2018-09-07 Last updated: 2020-05-07Bibliographically approved
In thesis
1. Automatic Model Generation and Scalable Verification for Autonomous Vehicles: Mission Planning and Collision Avoidance
Open this publication in new window or tab >>Automatic Model Generation and Scalable Verification for Autonomous Vehicles: Mission Planning and Collision Avoidance
2020 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Autonomous vehicles such as mobile driver-less construction equipment bear the promise of increased safety and industrial productivity by automating repetitive tasks and reducing manual labor costs. These systems are usually involved in safety- or mission-critical scenarios, therefore they require thorough analysis and verification. Traditional approaches such as simulation and prototype testing are limited in their scope of verifying a system that interacts autonomously with an unpredictable environment that assumes the presence of humans and varying site conditions. Methods for formal verification could be more suitable in providing guarantees of safe operation of autonomous vehicles within specified unpredictable environments. However, employing them entails addressing two main challenges: (i) constructing the models of the systems and their environment, and (ii) scaling the verification to the incurred model complexity. We address these two challenges for two essential aspects of autonomous vehicle design: mission planning and collision avoidance. Though inherently different, communication between these two aspects is necessary, as the information obtained from verifying collision avoidance can help to improve the mission planning and vice versa. Finding a solution that addresses both mission planning and collision avoidance modeling and verification, while decoupling them for solution maintainability is one crux of this study. Another one deals with demonstrating the applicability and scalability of the proposed approach on complex and industrial-level systems.

In this thesis, we propose a two-layer framework for mission planning and verification of autonomous vehicles. The framework separates the modeling and computing mission plans in a discrete environment, from the vehicle movement within a continuous environment, in which collision avoidance algorithms based on dipole fields are proven to ensure safe behavior. We call the layer for mission planning, the "static layer", and the other one the "dynamic layer". Due to the inherent difference between the layers, we use different modeling and verification approaches, namely: (i) the timed automata formalism and the UPPAAL model checker to compute mission plans for the autonomous vehicles, and (ii) hybrid automata and statistical model checking using UPPAAL Statistical Model Checker to verify collision avoidance and safe operation. We create model-generation algorithms, based on which we develop tool support for the static layer, called TAMAA (Timed-Automata-Based Planner for Autonomous Agents). The tool enables the designers to configure their systems and environments in a graphical user interface, and utilize formal methods and advanced path-planning algorithms to generate mission plans automatically. TAMAA also integrates reinforcement learning with model checking to alleviate the state-space explosion problem when the number of vehicles increases. We create a hybrid model for the dynamic layer of the framework and propose a pattern-based modeling method for the embedded control systems of the autonomous vehicles to ease the design and facilitate reuse. We validate the proposed framework and design method on an industrial use case involving autonomous wheel loaders, for which we verify invariance, reachability, and liveness properties.

Place, publisher, year, edition, pages
Västerås: Mälardalen University, 2020
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 291
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-47918 (URN)978-91-7485-469-5 (ISBN)
Presentation
2020-06-15, Västerås Campus (+ Online/Zoom), Mälardalen University, Västerås, 09:00 (English)
Opponent
Supervisors
Projects
DPAC
Funder
Knowledge Foundation, 20150022
Available from: 2020-05-08 Created: 2020-05-07 Last updated: 2020-05-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Gu, RongMarinescu, RalucaSeceleanu, CristinaLundqvist, Kristina

Search in DiVA

By author/editor
Gu, RongMarinescu, RalucaSeceleanu, CristinaLundqvist, Kristina
By organisation
Embedded Systems
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 64 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf