Combinatorial Design of Key-Lock Systems

This is a contractual research project conducted with the major European key maker Assa Abloy. The Intelligent Data Analysis (IDA) lab at the department solves a task that is easy to state: given a set of a large number of planned keys and locks (say, at a large airport, hotel, etc.), propose the structure (pins and holes) of the keys and locks so that only the right keys open the right doors. Depending on the consumer's plan, some keys open multiple locks and some locks are opened by multiple keys. This is almost a textbook example of a combinatorial problem but the problem lies in its size (e.g. thousands or more keys and locks) which renders it beyond the reach of straightforward brute-force approaches even on high-performance computers. This is why several European projects aiming at full automation of the key/lock design failed and the human intuition has never been avoided from the design loop. We try to decompose the problem in ways enabling to leverage AI heuristics (mimicking human intuition) and to transform the subproblems into analogical kinds of problems which have been tackled for decades by artificial intelligence researchers, namely the logical satisfiability problem (SAT) and the maximum independent set problem. Our intermediary results raise the hope that we be the first to automate the design process successfully.

Involved: Filip Železný, Radomír Černoch, Jiří Matas (Department of Cybernetics), Jiří Vyskočil (Department of Cybernetics)

Former collaborators: Ondřej Kuželka, Matěj Holec, Josef Hájíček