Projektbeispiel: Calculation of Mechanical Lock System
Calculation of Mechanical Lock Systems
Mechanical cylinder locks possess a number of important design constraints that uniquely distinguish them from their electronic counterparts. Apart from manufacturing costs, a cylinder's most significant limitations are the upper bound on its outer dimensions as well as the lower bound on the size of its internal mechanical security features (pins). Cylinders cannot be very large as to still fit into doors and avoid the need for large keys. Pins cannot be too small in order to withstand wear and tear and provide appropriate physical security.
Even more complex than a single cylinder is the design of an ensemble of `related' locks as it may occur in an apartment or office building, a factory, or a hospital, for example. Instead of controlling access to one resource, the set of open/not-open relationships
between all the keys and locks of such a \textit{lock system} may encode a complex and diverse hierarchy of privileges for each individual key, from the benign opening of the front entrance by all staff to heavily restricted access of confidential documents or hazardous materials by selected personnel only.
For the mathematician or computer scientist, lock system design poses a fascinating array of theoretical and computational challenges. Abstraction via an algebraic model shows that cylinders and keys of a lock system can be represented within an upper semilattice, where the induced partial ordering establishes the must open/must not open functions. Finding an `equivalent' sub-semilattice within the semilattice over the set of those cylinders that are mechanically realizable then embodies the heart of the lock system calculation problem.
From the graph-theory point of view, finding such a sub-semilattice is exactly the famous graph subgraph isomorphism problem which is known to be NP hard. As problem size increases, the solution via deterministic algorithms from combinatorial optimization quickly becomes intractable. In particular, conventional branch-and-bound strategies such as pruning designed to limit systematic examination of the full search space are ineffective for the graphs arising from lock systems.
For this reason, a pragmatic approach has to resort to randomized search space exploration via probabilistic heuristics that are by their very nature not guaranteed to work in all cases but do yield results for many relevant practical cases quickly enough to be useful. Among the class of randomized optimization algorithms, simulated annealing proves to be particularly relevant for our setting. However, the vast available search space makes a vanilla algorithm impractical and adaptations are necessary. Parameters such as the cooling strategy have to be carefully tuned and the design of the error function for evaluating the quality of the tentative isomorphisms must weigh the tradeoff between expressiveness and runtime costs. Finally, in order to steer the algorithm towards promising choices in the search space, we combine annealing with a pre-filter that guides selection based on an encoding computed in a pre-processing step.