Deriving generalised stochastic Petri net performance models from high-precision location tracking data

Nikolas Anastasiou, Tzu-Ching Horng, William J. Knottenbelt

Abstract

Optimizing complex physical systems such as hospitals or factories requires accurate performance models, traditionally built through intrusive manual observation. This paper introduces an automated pipeline that transforms raw Real-Time Location System (RTLS) data into Generalised Stochastic Petri Net (GSPN) models. By employing velocity-based filtering and density-based spatial clustering (DBSCAN), the system identifies service areas and fits timing data to hyper-Erlang distributions. Experimental results using synthetic datasets show high spatial precision and statistical fidelity, offering a non-intrusive alternative to manual time-and-motion studies.

Introduction

Building performance models for systems like airports or assembly lines is essential for simulation and optimization. However, the traditional "model construction" phase—involving manual video analysis and questionnaires—is slow, expensive, and disruptive. While modern RTLS technologies (e.g., UWB, RFID) provide high-precision $(x, y, t)$ coordinates, converting this raw data into a structured mathematical model like a Petri Net is non-trivial. The primary challenge lies in automatically identifying service locations, sojourn times, and the statistical distributions governing system delays.

Methodology

The authors propose a four-stage automated pipeline to bridge the gap between raw tracking data and formal performance models.

The four-stage data processing pipeline for GSPN model generation.
  1. Data Filtering: Raw RTLS data is cleaned to remove noise and erroneous readings.
  2. Service Area Inference: A key innovation of this work is identifying service zones without pre-defined maps. The system detects "velocity minima"—where agents slow down or stop—and applies the DBSCAN algorithm to group these points into circular service areas.
  3. Structural Extraction: These zones are mapped to Petri Net "places" and "transitions." The system calculates "sojourn times" (duration within a zone) and "travelling times" (duration between zones).
  4. Distribution Fitting: To ensure the model is stochastic and realistic, the G-FIT tool fits hyper-Erlang distributions to the timing data. These distributions capture complex real-world delay patterns while remaining mathematically tractable.
Detailed process for inferring server locations using velocity/density filters and DBSCAN.

The final output is a Petri Net Markup Language (PNML) file, compatible with standard modeling tools like PIPE2.

Evaluation and Results

The pipeline was evaluated using synthetic data from the LocTrackJINQS simulator, allowing for comparison against a known "ground truth." Two scenarios were tested: a 3-server system with varying distributions and a complex 5-server system with diverse travel velocities.

The system demonstrated remarkable spatial accuracy, with a maximum inferred location error of only 0.139 meters and a radius estimation error of 0.289 meters. Statistical validity was confirmed via Kolmogorov-Smirnov tests, showing that the inferred timing distributions were highly compatible with the actual data at significance levels of 0.1 and 0.05.

Discussion and Future Work

While the current pipeline successfully automates GSPN generation, it currently assumes a single customer class and single-server semantics. Future work will focus on extending the tool to support Coloured Petri Nets for multiple agent types, multi-server queuing rules, and more robust filtering for real-world signal interference. Despite these limitations, the method provides a powerful framework for non-intrusive, data-driven system analysis.

Summary updated

Abstract

Stochastic performance models have been widely used to analyse the performance and reliability of systems that involve the flow and processing of customers and/or resources with multiple service centres. However, the quality of performance analysis delivered by a model depends critically on the degree to which the model accurately represents the operations of the real system. This paper presents an automated technique which takes as input high-precision location tracking data -- potentially collected from a real life system -- and constructs a hierarchical Generalised Stochastic Petri Net performance model of the underlying system. We examine our method's effectiveness and accuracy through two case studies based on synthetic location tracking data.
BibTeX
@inproceedings{anastasiou2011deriving,
  author = {Nikolas Anastasiou and Tzu-Ching Horng and William J. Knottenbelt},
  title = {{Deriving generalised stochastic Petri net performance models from high-precision location tracking data}},
  booktitle = {VALUETOOLS},
  year = {2011},
  doi = {10.4108/icst.valuetools.2011.245715},
}
Figure