Симулятор на основе сетей Петри для подготовки водителей (стр. 1 )

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет компьютерных наук

Симулятор на основе сетей Петри для подготовки водителей

Группа 21м ПИ

Выпускная квалификационная работа - МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

по направлению 09.04.04 «Программная инженерия»

Программа: Системная и программная инженерия

Рецензент ___________________	Научный руководитель к-т технических наук, проф. ִ
Москва 2015

FEDERAL STATE AUTONOMOUS EDUCATIONAL INSITUTION FOR HIGHER PROFESSIONAL EDUCATION NATIONAL RESEARCH UNIVERSITY

«HIGHER SCHOOL OF ECONOMICS»

Faculty of Computer Science

Pavel A. Shilov

Petri Nets Based Simulator for Driving Training

Group 21m SE

Qualification paper – Master of Science Dissertation

Field of study 09.04.04 «Software engineering»

Program: System and Software Engineering

Reviewer ___________________ Initials, Surname	Supervisor PhD, professor E. M. Grinkrug ִ Initials, Surname
Moscow 2015

Аннотация

В дипломной работе представлены исследования по применимости сетей Петри для симуляции дорожно-транспортных ситуаций. Данная работа включает анализ различных методов и расширений сетей Петри для верификации действий водителя согласно правилам дорожного движения. Предложены подходы к интерпретации и представлению правил для сопоставления дорожных ситуаций с разрабатываемой формальной моделью. Приведено описание главных аспектов верификации и программной реализации симулятора, основанных на записи логов с действиями водителя и событиями эмулируемой внешней среды. Изложенная архитектура, основанная на вложенных сетях Петри, может обеспечить проверку правильности действий относительно дорожных знаков, светофоров, сигналов поворотов и правила проезда нерегулируемого перекрёстка с различными приоритетами дорог, включая взаимодействие с другими участниками дорожного движения.

правила дорожного движения, сети Петри, цветные сети Петри, вложенные сети Петри, дорожно-транспортная модель, формальные методы

Abstract

This paper gives a particular research work on applicability using Petri Nets for simulation of road-traffic situations. It includes the analysis of different methods and extensions of Petri Nets for drivers’ actions verification according to the road traffic rules. This work contains approaches to interpretation and representation of rules for reflecting road situations on the designed formal model. The description of main aspects of verification and program simulator implementation, which are based on driver’s actions and emulated environment’s events logging, is introduced. The defined architecture of Nested Petri Net model can provide checking the propriety of actions by road signs, traffic-lights, signal turn lights and rules of driving through uncontrolled junctions with different road priorities including road users’ interactions.

traffic rules, Petri Nets, Colored Petri Nets, Nested Petri Nets, road-transport model, formal methods

Contents

Introduction. 5

Background. 7

Overview of Petri Nets Approaches. 9

Classic Petri Nets. 9

Colored Petri Nets. 13

Nested Petri Nets. 14

The NPN Architecture. 16

Junction structure. 18

Road Sector nested PN structure. 20

Rules’ Nets Structure. 22

Direction Rules Structure. 22

Road Priority Rules Structure: 25

Rules’ Violation Structure: 34

Car Net Structure. 35

Model Implementation Analysis. 39

Rules Exceptions. 39

Examples of rules applying. 40

Basic Net Properties. 42

Conclusion. 43

References. 44

Introduction

This document provides analysis of verification techniques in simulation of road-transport situations. The paper covers the approaches for checking drivers’ activity on the road according to traffic rules. The knowledge domain is connected with passing theoretical examination in State Motor Vehicle Inspectorate (SMVI) for taking out driving license in Russian Federation. In most cases there are a number of predefined question cards with images of junctions or some other road situations and list of answers.

For these kinds of tests there are important drawbacks. First one they are static and there is no random new question or factor in tasks. Another one is that test question with image doesn’t check real-time decision-making before student driver begin to pass the exam on the road. They don’t take into account the surrounding situation and movement, but only checks the rule without relations to the variable life processes.

As a result this leads to offer new type of theoretical driving examination with real-time 3D simulation. The idea of test question is concluded in creating by SMVI any possible road situation. At this stage the configuration of the street is produced. It includes the installation different signs, setup the amount of lanes and road marking and also determined the traffic on the sides of the road. Also there are start and end points for the driver where he should start or finish correspondingly. When the situation is initialized, it can be simulated for start the examination. The student-driver should pass (or virtually drive) this situation in real-time 3D domain. During the test all events of the driver are logged. In the end point the data from log are used for verification. So the model should check the driver’s action according violations by road rules. And after verification has passed the result of the test will appeared.

In current work the task of verification is decided to be solved by formal methods with using Petri Nets (PN). PN supports such approaches by abstraction techniques that are inherently compatible with the structure of the model. The logged driver’s data would be passed through the PN model to determine the legal actions. At this case model should have the covering graph of all possible physical drivers’ events.

From the point of examination term and its wide applicability for PN we will produce research of verification firstly for the complex concurrent tasks. The most difficult examination questions for testing road rules are tasks with unregulated junctions. The pass-through these junctions is regulated by the sings or by the basic traffic law of the right-side hindrance. Regulated junctions have traffic lights, which excludes from driver active behavior understanding what kind of sign for the junction he sees. It includes is the driver has the priority to pass the junction and in what direction he can legally to go. So for the obvious application of PN for verification driver’s activity we should take into account the importance of unregulated junctions.

The objective of the work is to implement the appropriate PN model for verification driver’s behavior during passing the exam in 3D simulator of driving training.

Background

There are different works using PN models in the road-transport knowledge domain. One the widest variant of them is modeling traffic networks for control purposes [1]. This work based on using colored timed Petri nets which is proposed to model the dynamics of signalized traffic network systems: places represent link cells and crossing sections, tokens are vehicles and token colors represent the routing of the corresponding vehicle. In addition, ordinary timed Petri nets model the signal timing plans of the traffic lights controlling the area. A discrete event simulation of the controlled intersection validates the model and tests the signal timing plan obtained by an optimization strategy. So this work covers signalized traffic system.

Another work [2] also covers the modeling responsive traffic signals designed with Petri Nets. The research is based on using traffic-responsive techniques of real-time measurements acquired with sensors to calculate in real-time suitable settings for traffic flow. In this paper, with the help of PN complex discrete event system is modeled which represented as the dynamic behavior of a group of traffic signals controlling a network of intersections. The work observe a mechanism based on PN with time interval associated to places to extend the green time to a main road depending on the demand of non-priority roads. The research doesn’t cover more detail aspects of modeling junction of PN according traffic rules.

One more paper [3] is the closest for our task. In this paper a road traffic model based on Petri nets and min-plus algebra in order to study the fundamental traffic diagram of regular city. For modeling junction authors use sectoring methods of creating representation of road. Each sector on the road is a material point. In this work uses three elementary PN that are combined together to form such sectors of the junction: entry, center and exit of junction. Authors use this PN to obtain the fundamental traffic diagram of a regular city which links the average flow to the density of vehicles.

To sum up all these works doesn’t fully intersect with our task. There are two modeling approaches of road traffic can be distinguished [3]. The first one is the macroscopic point of view where the traffic is seen as a gas with a comportment law given by a diagram called the fundamental traffic diagram. First two works are referred to this approach. The second one is the microscopic point of view where each individual vehicle with a specific comportment is distinguished. And this approach referred to the last work.

But all observed works doesn’t take into account the representing road rules and signs on the PN model without traffic lights. The reason is in choosing point of view at the stage of using formal methods. At most works PN modeling regulated-junction behavior as a whole. These approaches exclude the fact that a driver can depart from a rule and cross the junction under the red light. Consequently, there is own approach to verify individually driver’s behavior.