Calculation of Large Industrial Lock Systems
The goal of this CTI-project was to develop a software tool for the automatic calculation of lock systems.
While electronic locks become more available, mechanical lock systems remain an actual standard. Modern cylinder locks are precision manufactured with tolerances in the micron range.
Mechanical locks face a number of constraints. The most obvious one is a dimensional constraint limiting for example the number of pins inside a cylinder. Another one is a security constraint limiting the freedom in distributing pins on the available positions, e.g. there must be at least one pin on each side.
Thus, the number of cylinders that can be manufactured is limited. A KESO customer specifies which key opens which door, i.e. cylinder. This can be represented by a lock matrix. This matrix is usually complex and large, e.g. for a hospital, large enterprise or the like.
Alternatively, the lock system matrix can be represented as a directed acyclic graph. A key opens a cylinder if there exists a path connecting the cylinder and the key. Note that for a given choice of cylinders the keys can be constructed from the lock graph, but for most choices of cylinders there will be at least one key violating a must not open relation.
The difficulty is to determine a subset of the ca. 600’000 KESO cylinders that can be manufactured such that the correct lock system structure is obtained. This is a very difficult problem, which cannot be solved deterministically. We therefore used a stochastic method based on principles drawn from statistical physics combined with some deterministic ingredients.
The developed software tool was tested using 22 lock systems provided by KESO. The benchmark data consisted of a cross-section of eight representative core problems supplemented by a selection of problems collected during one working day at the KESO facility. The tool successfully computed all the benchmark cases, most within a few seconds. The largest problem consisting of 3114 cylinders and 3688 keys was computed in less than an hour.