Design of Deadlock Prevention Supervisor in Waterway with Multiple Locks and Canals

Kezić, Danko; Bogdan, Stjepan; Kasum, Josip · 2012 · Crossref

DOI: 10.7225/toms.v01.n01.004

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of preventing deadlocks and conflicts in complex waterway systems (CWS) characterized by multiple locks, canals, and basins. Safe navigation in such environments requires precise coordination between vessels and traffic management staff to avoid situations where vessels block each other’s paths, particularly in dense traffic. The authors propose a formal method for designing a deadlock prevention supervisor using discrete event theory, specifically employing the multiple reentrant flowlines class of Petri nets (MRF1PN). The motivation is to create a computer-based traffic management system that ensures maximally permissive control, minimizing vessel stops while guaranteeing safety. The methodology involves modeling the waterway traffic as a discrete event system using MRF1PN, where locks, canals, and basins are treated as resources. The authors utilize matrix algebra to analyze the structural characteristics of the Petri net, identifying two types of deadlocks. First-level deadlocks are associated with critical subsystems and circular waits, while second-level deadlocks involve "key resources" that could become the last available resources in a cyclic circular wait. The design process uses P-invariants to calculate control places, which are added to the process Petri net to form a supervisor. This supervisor restricts the system’s reachable states to a safe subset by enforcing linear inequality constraints on the number of tokens (vessels) in critical areas. The approach is structured into steps involving the identification of resource loops, critical siphons, and key resources through matrix operations. The study demonstrates that first-level deadlocks can be prevented by maintaining the number of vessels in critical subsystems below the capacity of critical circuits. For second-level deadlocks, the supervisor ensures that key resources are never the sole remaining available resources in the system. The functionality of this supervisor is verified through computer simulations using Matlab software with the Petri net toolbox. A case study resembling the Panama Canal is presented to illustrate the application of the matrix-based approach for designing the supervisor. The results confirm that the proposed method effectively prevents both types of deadlocks by blocking specific transitions (events) that would lead to forbidden states, such as entering a lock when it would cause a deadlock. The significance of this work lies in providing a rigorous, mathematically grounded framework for supervisory control in maritime traffic management. By treating waterway infrastructure as shared and non-shared resources within a Petri net model, the authors offer a scalable solution for managing complex, multi-resource systems. The proposed supervisor allows for real-time monitoring and control, advising traffic management staff on how to resolve conflicts and avoid dangerous situations. This approach enhances the safety and efficiency of waterway navigation, particularly in systems with high traffic density, by ensuring that the control policy is both safe and maximally permissive.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• dual task multitasking