Abstract In this work, we present an industrial case study of deadlock avoidance in the context of automated warehouse logistics. In particular, we consider systems of Automated Guided Vehicles (AGVs) in which semi-autonomous robots move inside a facility along a predefined set of paths. The paper introduces a novel formalization of AGV systems that models the physical setup of the AGV system more accurately compared to previous approaches. In particular, our modeling approach captures movement restrictions due to physical proximity of vehicles regardless of the logical connectivity of the guide path network. The paper provides and compares three different encodings of such models as transition systems, which enable symbolic analysis of the system via Binary Decision Diagrams (BDDs). Based on these encodings we perform deadlock avoidance for warehouse layouts of both synthetic and real-world origin.

Abstract Active automata learning enables model-based testing and verification of black-box systems by automatically constructing models from observations via interactions with the system. As interactions are usually expensive, active algorithms attempt to perform as few interactions as possible to learn a given system. However, many such algorithms struggle when confronted with noise, such as message loss, when learning otherwise deterministic systems. We investigate and adapt different algorithms to learn deterministic automata in a noisy setting. One of these is a novel active algorithm based on our previous passive Partial Max-SAT algorithm. In our analysis, we demonstrate techniques to lower the required number of interactions and order the evaluated algorithms accordingly. Finally, we show that the necessary interactions can be further reduced when leaving the classical active learning framework.

Abstract AALpy is a well-established open-source automata learning library written in Python with a focus on active learning of systems with IO behavior. It provides a wide range of state-of-the-art algorithms for different automaton types ranging from fully deterministic to probabilistic automata. In this work, we present the recent addition of a generalized implementation of an important method from the domain of passive automata learning: state-merging in the red-blue framework. Using a common internal representation for different automaton types allows for a general and highly configurable implementation of the red-blue framework. We describe how to define and execute state-merging algorithms using AALpy, which reduces the implementation effort for state-merging algorithms mainly to the definition of compatibility criteria and scoring. This aids the implementation of both existing and novel algorithms. In particular, defining some existing state-merging algorithms from the literature with AALpy only takes a few lines of code.