The present disclosure refers to a method of operating a laboratory sample distribution system. Further, the present disclosure refers to a laboratory sample distribution system. In addition, it is referred to a laboratory automation system.

Background

Laboratory automation systems are applied, in particular, for determining samples, for example samples of a bodily fluid, essentially automatically. The sample is typically received in a sample vessel or container which is processed via a laboratory automation system.

Such laboratory automation systems can comprise a plurality of units. A laboratory automation system usually comprises a plurality of laboratory stations or devices such as, for example, a pre-analytical, an analytical and / or a post-analytical station or device. Typically, the containers are transported between different stations of the system via a sample distribution or transportation system. The sample vessels carriers with or without samples may be moved along a line for processing the samples, wherein the sample vessel carriers are moved by means of a transport device having one or more actuators and actuator drivers or driving devices for driving the carriers. For example, the sample vessels may be moved or relocated from a first working station to a second working station provided in the line of processing in the system. The working stations or devices may also be referred to as working locations.

At present, only transport systems inside the laboratories are fully automated. The designs for those transport systems, however, are mostly rather simple, comprising conveyor systems, wherein samples and sample containers I carriers, respectively, are moved along fixed routes. Usually, a set of routes along different analyzers I laboratory stations is defined via the hardware design (placement of rails I tracks) and I or electronics (dip switch configurations, preprogrammed turn-table logic, etc.) (e.g., a belt-drive transport system). Hence, a specific sample I container/ carrier can be assigned to a specific fixed route. The specific sample I container I carrier can be transported along this specific fixed route, can “step off’ the route in proximity to a specific analyzer to be processed by the analyzer, and can “step on" the route again to be further transported along the specific fixed route until the end of the route is reached. The sample can then be, e.g., stored or wasted. Typically, these routes are designed in a manual process by “brain power", i.e., for a specific order situation, for example the laboratory designer defines the routes such that a reference set of orders is processed efficiently and predefined requirements are met.

For complex transport systems, however, such a design may reach its limits.

Document WO 2016 / 188752 A1 discloses a laboratory automation system, which comprises: a number of laboratory stations, and a number of sample container carriers (e.g. 10 to 10000), wherein the sample container carriers are adapted to carry one or more sample containers. The sample containers comprise samples to be processed by means of the laboratory stations. A transport plane is provided, wherein the transport plane is adapted to support the sample container carriers. The transport plane comprises a number of transfer areas, wherein a transfer area of the number of transfer areas is assigned to a corresponding laboratory station of the number of laboratory stations. Samples are transferred to the laboratory stations by moving the corresponding sample container carrier to the assigned transfer area. Drive means are provided, wherein the drive means are adapted to move the sample container carriers on the transport plane simultaneously and independent from one another along individual transport paths.

More complex transport systems may require a more sophisticated operation method, especially to better harness their potential.

Document EP 3 095 739 A1 discloses a method of operating a laboratory sample distribution system comprising a number of sample container carriers adapted to carry one or more sample containers, wherein the sample containers comprise samples to be analyzed by means of a number of laboratory stations. A transport plane is provided, wherein the transport plane is adapted to support the sample container carriers. The transport plane comprises a number of transfer locations assigned to corresponding laboratory stations. Drive means are provided adapted to move the sample container carriers on the transport plane. The method comprises steps of, during an initialization of the laboratory sample distribution system, pre-calculating routes depending on the transfer locations, and after the initialization of the laboratory sample distribution system, controlling the drive means such that the sample container carriers move along the pre- calculated routes. During the initialization (start, booting) of the laboratory sample distribution system fixed routes extending over the transport plane are pre-calculated depending on (between) the different transfer locations. The pre-calculated routes are provided on the transport plane between the transfer locations. The transfer locations represent initial or goal nodes in the sense of Graph theory. The routes are calculated using an informed search algorithm, i.e. an A*-algorithm or a D*-algorithm. The A*-algorithm is an algorithm that is used in path finding and graph traversal, to efficiently calculate a traversable path between different nodes, e.g. in the form of the transfer locations.

Document EP 3 410 123 A1 refers to a method of operating a laboratory sample distribution system, wherein the laboratory sample distribution system comprises a number of sample container carriers, wherein each of the sample container carriers comprises at least one magnetically active device and wherein each of the sample container carriers is adapted to carry at least one sample container, and a number of interconnected transport plane modules, wherein each of the transport plane modules is adapted to support a number of said sample container carriers. A number of electro-magnetic actuators is provided, wherein below each transport plane module a number of said electro-magnetic actuators is stationary arranged in rows and columns. The electro-magnetic actuators are adapted to move a sample container carrier of said sample container carriers on top of said transport plane modules along a row of said rows or along a column of said columns by applying a magnetic move force to said sample container carrier. The method comprises the steps as follows: a) assigning at least one transport plane module of said transport plane modules to a route category, wherein at least two traffic lanes are formed on the route categorized transport plane module, wherein said sample container carriers are moved within each traffic lane in a given transport direction, wherein the transport directions of the at least two traffic lanes are opposite to each other and wherein a change from one transport direction to the opposite transport direction is not possible for said sample container carriers moved on the route categorized transport plane module, and b) assigning at least one another transport plane module of said transport plane modules to a waypoint category, wherein a change from one transport direction to the opposite transport direction is enabled for said sample container carriers moved on the waypoint categorized transport plane module.

Document US 9 835 637 B2 relates in general to an automation system for use in a laboratory environment and, more particularly, to systems and methods for scheduling samples within the automation system by providing queuing logic.

An analysis system for analyzing biological samples is disclosed in document US 2019 / 0 120 866 A1 . Document US 10668622 B2 refers in general to an automation system for use in a laboratory environment and, more particularly, to systems and methods for use in a clinical analyzer.

In document US 9 315 334 B2 an automation system for an in vitro diagnostics environment is disclosed. The system includes a plurality of intelligent carriers that include onboard processing and navigation capabilities. The carriers control local motion and navigate at decision points, such as forks in the track, to reach the appropriate testing station independently.

With complex transport systems, route calculation for the carriers also becomes more complex. The size of the possible route sets grows exponentially both in the number of carriers and in the number of transportation fields of the transport plane I transport plane modules. Even for a single carrier, there is a huge number of routes connecting its current position to the aimed destination. However, in typical use cases (with a large number of transportation fields and carriers), the optimal routing should consider simultaneously routes for hundreds of carriers.

Summary

It is an object to provide an improved method of operating a laboratory sample distribution system and a laboratory sample distribution system. In particular, it is an object to provide technology for improved determining of routes for carriers for laboratory sample distribution systems. Specifically, it is an objective to avoid one or more deadlock situations in the laboratory sample distribution system as _? such a deadlock situation disturbs and interferes with sample distribution. Carriers involved in a deadlock situation will get stuck on the transport system such that they cannot reach their destination anymore. Furthermore, the routes involved in a deadlock situation and possibly also a part or all of the carriers on those routes cannot be used anymore.

For solving the problem, a method of operating a laboratory sample distribution system according to the independent claim 1 is provided. Further, a laboratory sample distribution system according to the independent claim 16 is provided. Moreover, a laboratory automation system according to claim 17 is provided. Further embodiments are disclosed in dependent claims.

According to one aspect, a method of operating a laboratory sample distribution system is provided. The laboratory sample distribution system comprises a plurality of carriers having a number of n (n>3) carriers each configured to carry one or more sample containers containing a sample to be analyzed by laboratory devices (wherein the plurality of carriers may be a subset of a total plurality of carriers comprised by the laboratory sample distribution system); a transport plane assigned to the laboratory devices and configured to support to the plurality of carriers, wherein the transport plane comprises a plurality of interconnected transport modules comprising a plurality of plane fields (wherein at least one of the plane fields (each plane field) may only accept one carrier at a time and I or at least one of the plane fields (each plane field) may accept more than one carrier at a time); and a driving device configured to control movement of the plurality of carriers along individual routes between the plurality of plane fields, the movement comprising moving, in response to driving control signals, the plurality of carriers between neighboring plane fields of the plurality of plane fields along the individual routes.

The method is comprising (i) moving the plurality of carriers along the individual routes on the transport plane, wherein the moving, for each carrier, comprises executing at least once steps of reserving a route segment along the individual route, the route segment being provided by one or more plane fields of the plurality of plane fields, and moving the carrier along the route segment; and (ii) preventing, for the plurality of carriers, a deadlock arrangement on the transport plane in which the plurality of carriers block each other from further movement along the individual routes (wherein the prevention of the deadlock arrangement on the transport plane may take place off run-time, e.g. via simulations and I or calculations, in particular when designing routes or sections of the routes, and I or in runt-time).

The preventing is further comprising (in the driving device) steps of: determining, at a present operation time, a potential deadlock arrangement for the plurality of carriers on the transport plane at a future operation time, wherein the potential deadlock arrangement is assigned a number of n deadlock plane fields occupied by the plurality of carriers in case of the potential deadlock arrangement; for a first carrier from the plurality of carriers moving along a first individual route, reserving a first route segment ending with a first end plane field; and assigning a non-reserve flag to a next plane field which is next to the first end plane field along the first individual route.

Further, the following is provided: the first end plane field provides for a first deadlock plane field of the n deadlock plane fields; the next plane field provides for a second deadlock plane field of the n deadlock plane fields; and the assigning of the non-reserve flag to the next plane field is preventing all remaining carriers from the plurality of carriers from reserving, along a second individual route, a second route segment which is assigned the next plane field as a second end plane field to be occupied by one of the remaining carriers at least a the future operation time.

According to another aspect, a laboratory sample distribution system is provided. The laboratory sample distribution system comprises a plurality of carriers having a number of n (n>3) carriers each configured to carry one or more sample containers containing a sample to be analyzed by laboratory devices; a transport plane assigned to the laboratory devices and configured to support to the plurality of carriers, wherein the transport plane comprises a plurality of interconnected transport modules comprising a plurality of plane fields; and a driving device configured to control movement of the plurality of carriers along individual routes the plurality of plane fields, the movement comprising moving, in response to driving control signals, the plurality of carriers between neighboring plane fields of the plurality of plane fields along the individual routes.

The system is configured to (i) move the plurality of carriers along the individual routes on the transport plane, wherein the moving, for each carrier, comprises executing at least once steps of reserving a route segment along the individual route, the route segment being provided by one or more plane fields of the plurality of plane fields, and moving the carrier along the route segment; and (ii) prevent, for the plurality of carriers, a deadlock arrangement on the transport plane in which the plurality of carriers block each other from further movement along the individual routes. With respect to preventing (in the driving device) the following is further provided: determining, at a present operation time, a potential deadlock arrangement for the plurality of carriers on the transport plane at a future operation time, wherein the potential deadlock arrangement is assigned a number of n deadlock plane fields occupied by the plurality of carriers in case of the potential deadlock arrangement; for a first carrier from the plurality of carriers moving along a first individual route, reserving a first route segment ending with a first end plane field; and assigning a non-reserve flag to a next plane field which is next to the first end plane field along the first individual route.

Further, the following Is provided: the first end plane field provides for a first deadlock plane field of the n deadlock plane fields; the next plane field provides for a second deadlock plane field of the n deadlock plane fields; and the assigning of the non-reserve flag to the next plane field is preventing all remaining carriers from the plurality of carriers from reserving, along a second individual route, a second route segment which is assigned the next plane field as a second end plane field to be occupied by one of the remaining carriers at least a the future operation time.

According to still another aspect, a laboratory automation system is provided, the system comprising the laboratory sample distribution system according to the aforementioned aspect and a plurality of laboratory devices.

Steps provided or conducted for data processing related to the operation of the laboratory sample distribution system such as preventing a deadlock arrangement may be performed in at least one of the driving device controlling the movement of the plurality of carriers along individual routes and a data processing device separated from the driving device, but functionally connected to the driving device and comprising one or more data processors (e.g., comprising a computer, a microcontroller, a CPU, a data storage, and I or communication interfaces).

A deadlock situation in which the carriers block each other from further movement along the individual routes is avoided efficiently by the technology provided.

For example, 10 to 10 000 sample container carriers may be provided. The laboratory sample distribution system may process 2 000 to 200 000 samples per day. In an embodiment, 2 to 50 of laboratory stations or devices may be provided. The transport plane may be planar, in particular completely planar.

A first and a second (sub-)transport plane may be provided, wherein the first and second transport plane may be provided at different levels. The carriers may be transported from the first to the second transport plane (and vice versa) via a lift (e.g., a paternoster lift) and I or ramps. The transport plane may comprise the first and the second (sub-)transport plane and optionally further (sub-)transport planes. Accordingly, routes can also comprise routes that extend over both the first and the second and optionally further transport planes, each of which is provided on different levels.

In this regard, a route connecting segment of a route that extends over multiple transport planes, each provided on different levels, may connect a route section on one of these planes, e.g., the first transport plane, with a route section on another of these planes, e.g., the second transport plane, wherein the route segment connecting route sections on the different levels will be part of the route. This route-connecting segment may be comprised by a transport system such as the ramp or the lift.

In the present application, in general, the term “transport plane” refers to a two-dimensional and / or a three-dimensional surface, i.e. , both a planar plane and / or a surface that extends not only in two spatial dimensions but also in a third spatial dimension. Such a three-dimensional surface in the sense of this application can be, for example, a surface with one or more curvatures, a ramp and I or lift between (sub-)planes.

The (sample container) carriers can be placed on top of the transport plane. The carriers can be moved on top of and over the transport plane. The transport plane may comprise 2 to 100 transfer locations or fields. The transfer locations (fields) may be assigned to corresponding laboratory stations or devices. For example, each laboratory device may have a single corresponding transfer location (field) configured to transfer a sample carrier and / or a sample from the transport plane to the laboratory device or back. Alternatively, more than one transfer location (field) may be assigned to a corresponding laboratory station, in particular an output transfer location and an input transfer location. The transfer locations may be statically or dynamically assigned to the laboratory stations. In other words, during operation I at run-time, the transfer locations may be changed, if necessary.

Although the carriers are primarily configured to carry one or more sample containers containing a sample, the carriers (or at least one of them) can carry one or more empty sample containers, can be unloaded (empty), and I or may transport other goods, for example, reagent cassettes and I or consumables, for example, disposable pipette tips and I or reaction cells. The carriers (or at least one of them) may be configured to carry waste, for example, used tips, reaction cells, and I or empty reagent cassettes. The waste may be transported from the instrument to a waste disposal unit. The empty carrier(s) may be used for cleaning, maintaining, and I or repairing the transport surface (plane).

A transport module can comprise one or more plane fields. A plane location can comprise one or more plane fields. Plane fields may define respective plane locations. Plane locations can correspond to transport modules. Plane fields assigned to the same transport module do not have to be assigned to the same plane location. Each plane field I location I position can correspond to a certain area I logical field on the transport plane. In particular, the plane fields may be the logical fields on the transport plane. The transport plane can be segmented into several logical fields, e.g. square shaped logical fields of identical size and outline. The logical fields may form a regular grid, wherein each cell of the grid may correspond to a logical field, each cell of the grid may be a square of identical size (identical in X- and Y-direction), and I or the grid may (exactly) cover the transport plane. One or each transport module (TM) may comprise one or more logical fields (e.g., a subset of the logical fields forming the transport plane). A set of (interconnected) transport modules may form the transport plane. Pitches be-tween adjacent transport modules (TMs) may form pitches in the regular grid. The logical fields can be provided in such a way that each logical field can accommodate only one carrier. For example, 10 to 10 000 plane locations or fields may be provided. Each plane field I logical field can correspond to a transport module.

From each plane position or logical field, the carriers may generally be able to move in the two X- and the two Y-directions (left I right and up I down). Alternatively, the carriers may be restricted to only move in one X-direction and one Y-direction from each plane position or logical field. However, the permitted directions of movement do not have to be the same for each plane position I logical field. For example, at a first plane position or logical filed, the carriers can only move up and to the right, and at a second plane position I logical field, the carriers can only move down and to the left. The restriction may be provided to prevent 2x1 (1x2) deadlocks.

The individual routes can be determined prior to running the laboratory sample distribution system which may also be referred to as pre-determining of individual routes and I or at runtime of the laboratory sample distribution system. The individual routes can be used as or represented by lookup table. Each time a carrier needs to travel or move from a starting field to a destination, a corresponding route can be selected from the lookup table. Based on information comprising routing data indicative of the individual routes the potential deadlock arrangement may be determined.

In the deadlock arrangement a set of carriers is prevented or blocked from making the next move because other carriers already occupy the plane fields and cannot move either. The smallest deadlock situation, if field-to-field (logical field I plane position) moves are possible for each field in only one X- and one Y-direction, comprises four carriers. In this case, the four carriers are located in an area of 2x2 plane fields. Each plane location or filed is occupied by one carrier. At each plane field in the area of 2x2 plane fields, a clockwise or counterclockwise movement to the next plane location or field within the area of 2x2 plane fields is allowed and intended. However, due to the occupation, such a movement is not possible as the possibility of each carrier’s movement depends on the other carrier’s possibility to move. Hence, a circular dependency of the carriers and their next movements exists. Bigger dead-lock situations, caused by the same mechanism but involving more carriers, can exist as well.

The smallest deadlock situation, if field-to-field (logical field I plane position) moves are possible for each field in each horizontal direction, comprises two carriers. In this case, analogously to the 2x2 deadlock, the two carriers are located in an area of 2x1 (1x2) fields. The carriers involved in a larger deadlock might be placed on all the transport locations of a rectangular (n x m) region of the transport plane. Besides this situation, deadlocks may involve arbitrary closed sequences of plane locations each containing a carrier that cannot move due to a circular dependency. Deadlocks may even involve plane locations of different planes and ramps I lifts. The embodiments presented here analogously apply.

Deadlocks may be detected. Deadlocks may be detected by detecting cycles in the graph’s incidence matrix. A list of carriers that at the end of the current move are not going to be able to reserve the next field because another carrier is sitting there is (regularly) updated. A list of plane corresponding to the carriers that cannot reserve the next field because another carrier is sitting there (at the end of the planned moves) is (regularly) updated. Determining a corresponding adjacency matrix M. The elements of the matrix M indicate whether plane position corresponding to the carriers that cannot reserve the next field because another carrier is sitting there are adjacent (connected via arcs) or not in the graph. Through matrix multiplications, it can be determined whether plane position corresponding to the carriers that cannot reserve the next field because another carrier is sitting there form one or more cycles. Detected cycles may be indicative of (potential) deadlocks.

For all identified deadlocks, the sizes (number of positions that need to be occupied to form a deadlock) may be computed. Small deadlocks like 2x2 deadlocks may occur more easily than larger deadlocks. Also, larger deadlocks may be frequently caused by smaller deadlocks. Avoiding small and large deadlocks may comprise reducing the solution space for finding optimized routes. Eliminating the chance on creating small deadlocks may be prioritized. A deadlock size threshold may be provided. The calculating of the optimized set of individual routes may avoid the creation of routes that may result into deadlocks with a size smaller or equal to the deadlock size threshold. Deadlocks may be prevented by moving rules for the carriers. Each carrier may reserve a corresponding track segment. A first carrier may reserve a first track segment. The first track segment may comprise one or more subsequent plane positions on the route of the first carrier starting from the current plane position of the carrier. The positions of the reserved first track segment may be blocked for other carriers. The first plane position on the route of the first carrier subsequent the reserved first track segment may be flagged. The flagged plane position may not be blocked for other carriers. A second carrier may not reserve a second track segment that ends on the flagged plane position, i.e. the last plane position, starting from the current position of the second carrier, of the second track segment of the second carrier may not be the flagged plane position. Track segments may comprise a fixed number of plane positions, e.g. one, two, or more. Alternatively, different carriers may reserve track segments with a different number of plane position.

The determining of the potential deadlock arrangement may comprise determining a potential closed sequence deadlock arrangement in which the plurality of carriers are provided on plane fields arranged in a closed sequence of plane fields. In such deadlock arrangement the carriers are occupying plane fields provided along a closed line. For each of the carriers the next field of movement along the closed line is blocked by another one of the carriers. Such deadlock arrangement, if not avoided, may be solved by re-determining at least one of the individual routes including change of direction of movement (different next field). In an embodiment, four carriers (n=4) may be determined to potentially entering into a deadlock arrangement (2x2 arrangement).

The moving of the plurality of carriers may comprise restricting movement for each carrier from the plurality of carriers to only a single vertical direction and a single horizontal direction of the transport plane.

A specific pattern for allowed field-to-filed (location-to-location) movements on the transport plane may be provided, e.g. to avoid 2x2 deadlocks. At each plane location or filed, the carriers can exclusively move in one X- and one Y-direction. The plane may be rectangular. In this or other embodiments, the plane may be divided in quadratic areas of n x n plane locations or fields. The carriers may be allowed, in the upper part (half) of each of the quadratic areas, to move in a first X-direction and, in the lower part (half) of each of the quadratic areas of the transport plane, to move in a second X-direction being different from the first direction, i.e. the first and second directions lead in opposite directions. The carriers may be allowed, in the left part (half) of each of the quadratic areas, to move in a first Y-direction and, in the right part (half) of each of the quadratic areas of the transport plane, to move in a second Y-direction being different from the first vertical direction, i.e. the first and second Y-directions lead in opposite directions. Each quadratic area may comprise one area of 2x2 plane locations or fields in which a circular movement is allowed. In addition, areas of 2x2 plane fields comprised by four of such quadratic areas may allow circular movement. In these areas of 2x2 plane locations or fields, four allowed movements may define the allowed circular movement. One of the four allowed movements can be removed. Alternatively, more than one, preferably two, of the four allowed movements can be removed. Preferably, the one or more removed allowed movements are ones that would not be expected to be used frequently. In particular, the one or more removed allowed movements are ones that lie perpendicular to the main transportation flow.

There can be two ways to obtain routes where 2x2 deadlocks are avoided: (1) the allowed directions for determining routes are defined according to the above specific pattern and I or (2) when calculating the optimized set of off-line routes, the rule is added to avoid that any subset of field-to-field movements involved in the set of routes define an area of 2x2 plane locations in which a circular movement is allowed.

The preventing of the deadlock arrangement on the transport plane may comprise providing flag data in the driving device indicative of the next plane field assigned the non-reserve flag, and updating the flag data in case one of the following is provided: assigning the next plane field the non-reserve flag, and terminating assignment of the non-reserve flag for the next plane field. In response to the terminating, a record provided the plane field assigned the non-reserve flag may be deleted from flag data. The flag data may be provided with a lookup table in a data memory provided, for example, in the driving device or separated from the driving device in a central memory device accessible by the driving device.

The reserving of the second route segment may comprise looking up the flag data, and verifying the second end field of the second route segment being not assigned a non-reserve flag. Otherwise, in case the second end plane field cannot be verified as being free of a non-reserve flag, an alternative second route segment different from the second route segment may be determined. Following, for the alternative second route segment, again it is verified that the end field is not assigned a non-reserve flag. Such steps may be repeated until some second route segment is found for which the end plane field is verified to have not assigned a nonreserve flag.

In the method, the moving of the plurality of carriers along the individual routes may comprise the following: determining a model representing the transport plane with plane locations and location-to-location movements between plane locations associated to the plurality of carriers; calculating an optimized set of individual routes between pairs of plane locations from the plurality of plane locations using the model, the calculating comprising solving an optimization problem in which routes between the pairs of plane locations are simultaneously optimized; and providing the optimized set of individual routes as individual routes on the transport plane. In this context, the plane locations may be plane fields. Such determining of the individual routes may be provided as pre-determining of individual routes prior to moving the carriers on the transport plane in at least one of the driving device and data processing device separated from the driving device. The pre-determining may be conducted, for example, prior to initializing the laboratory sample distribution system.

For example, 5 to 10 routes between the pairs of plane locations may be simultaneously optimized. The pairs of plane locations may be 5 to 10 pairs. Routes between the 5 to 10 pairs of plane locations may be simultaneously optimized.

The calculating of the individual routes between pairs of plane locations from the plurality of plane locations may further comprise: determining a plurality of individual routes between pairs of plane locations from the plurality of plane locations (e.g., in the directed graph model), and determining an optimized set of individual routes from the plurality of routes, comprising solving an optimization problem (e.g., a mixed-integer optimization problem) for the plurality of individual routes.

The model may be a directed graph model of the transport plane, wherein nodes of the directed graph model are assigned plane locations and arcs connecting the nodes of the directed graph model are assigned location-to-location movements between two plane locations. The calculating of an optimized set of individual routes in the directed graph model can comprise finding an optimal multi-commodity flow in this directed graph. The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different sources and sink nodes. The endpoint locations / pairs of locations or fields can define the source and sink nodes. Alternatively, the model can be a numerical model and / or a simulation. However, the model can also be another model, e.g. a combination of aforementioned models.

Merely field-to-field (location-to-location) movements between two neighboring plane fields (locations) may be allowed. Merely location-to-location movements between two neighboring groups of logical fields I plane positions may be allowed. The arcs may merely connect neighboring nodes of the directed graph model.

In case of predetermining individual routes, the method may further comprise determining a re-optimized set of individual routes from the individual routes, for example, at a time of initializing the laboratory sample distribution system. The determining of the re-optimized set of individual routes may depend on the expected carrier traffic on the transport plane. For example, the individual routes pre-determined may comprise two sets of individual routes, a first set for high traffic and second set for low traffic. If low traffic is expected, the second set of optimized routes is selected when determining the re-optimized set of individual routes and vice versa. The optimized set of individual routes may alternatively comprise several sets of optimized individual routes for several traffic scenarios. When determining the re-optimized set of individual routes, in this case, depending on the expected traffic, the corresponding set of optimized routes is selected from the several sets of optimized routes.

In the different alternative embodiments, the plurality of individual routes between pairs of plane fields I locations from the plurality of plane fields I locations in the directed graph model can be selected form a plurality of possible routes connecting the pairs of plane fields. The possible routes can be located (directly) on the transport plane, preferably can be entirely located (directly) on the transport plane. Each pair of plane fields I locations may be indicative of a pair of a start field I location I node and a destination field I location I node of one of the routes. Start and destination location or field of a certain individual route may constitute endpoint locations or fields of this individual route. The pairs of plane locations or fields may correspond to pairs of transfer locations or fields assigned to one or more laboratory stations or devices and configured to transfer sample container to or from the laboratory station(s) or device^).

In the method, the pre-determining of (e.g. offline) individual routes may further comprise: determining a first optimized set of individual routes; assigning the first optimized set of individual routes a first application parameter; determining a second optimized set of individual routes which is different from the first optimized set of individual routes; and assigning the second optimized set of individual routes a second application parameter. Further, the controlling of the driving device may further comprise receiving application information indicative of a current application parameter, and selecting one of the first optimized set of individual routes and the second optimized set of individual routes for controlling the driving device, if it is determined that the current application parameter matches the first application parameter or the second application parameter. The first and second application parameter can be indicative of a first and a second date, time period, traffic situation (e.g. high or low traffic), operation mode, and I or orders.

The (expected) carrier traffic (carrier traffic intensity) may depend on several factors. The throughputs can be higher at working days than in the weekend and can be higher between 8:00 and 18:00 than during the night. The types of ordered tests can be different at certain days or hours if, for example, glucose screening is carried out on a batch of samples or clinical studies are carried out. Thus, an endpoint assigned to a corresponding laboratory device may serve as an endpoint more frequently. The corresponding routes comprising this endpoint may have higher carrier traffic (carrier traffic intensity). Likewise, due to seasonal effects or pandemic situations, some tests are ordered much more frequently for a longer period of time.

The application parameters may correspond to a KPI (Key Performance Indicator) of the laboratory automation system. Examples for application parameters may be the traffic data, the constraints, the weightings of the constrains, etc., or combinations thereof.

The optimization problem, which may be model-related, can be one of the following: a multicommodity flow problem, in particular a multi-commodity flow problem in a directed graph, a shortest path problem, and a minimum flow problem.

The calculation of the optimized set of off-line routes between pairs of plane locations from the plurality of plane locations can comprise, for example, finding an optimal multi-commodity flow in the directed graph. The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes. The endpoint locations / pairs of locations can define the source and sink nodes.

The optimization problem may be solved, for example, by applying a MIP-solver (Mixed-lnte- ger-Programming-solver). A generic solver for MIP problems can be used. The MIP-solver can be one of the following: Gurobi, IBM ILOG Cplex, and Coin-OR CBC, i.e. solutions for the mixed-integer optimization problem can be found with software products like Gurobi, IBM ILOG Cplex, and Coin-OR CBC. There are additional solvers known as such that are capable of solving this kind of optimization problem. In general, mixed-integer optimization problems deal with mathematical optimization problems with two types of variables: variables taking values in an integer domain, and variables taking values in a continuous domain.

First, an optimization problem may be defined, e.g. a multi-commodity flow problem, i.e. the problem of interest is modeled. The problem of interest may be to find a set of routes on a transport plane that is optimal with respect to one or more given criteria (constraints). Then, a solution approach, e.g. a MIP-solver, for the defined optimization problem may be selected to solve the optimization problem.

Examples of possible solution approaches are presented in paper P. FESTA, “A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems", 16th International Conference on Transparent Optical Networks (ICTON), 2014, pages 1 to 20, doi: 10.1109 / ICTON.2014.6876285. The optimization problem can be solved by an exact optimization method, an approximation of the original problem by a simpler one and solving the simpler problem, and I or heuristics and I or metaheuristics. The exact optimization method can be a (i) branch and bound method, (ii) a dynamic programming method, or (iii) a solver (also other exact optimization methods can be used). The solver may comprise multiple algorithms (not only exact ones). The exact optimization method can also comprise combinations of aforementioned methods. Solving the approximated simpler problem may comprise applying (i) one or more greedy algorithms, (ii) a local search, (iii) one or more relaxation-based algorithms, or (iv) one or more random algorithms (also other methods for solving the approximated simpler problem may be used). Solving the approximated simpler problem may also comprise combinations of aforementioned methods. Heuristics and I or metaheuristics may be (i) a simulated annealing, (ii) one or more evolutionary algorithms, (iii) a tabu search, or (iv) one or more Greedy Randomized Adaptive Search Procedures (GRASP). The heuristics and I or metaheuristics may also comprise combinations of aforementioned methods.

The method may further comprise: (i) providing first frequent endpoint location data indicative of a first selection of plane locations (or fields) most frequently providing for an endpoint of an individual route; and (ii) determining the directed graph model of the transport plane, wherein first nodes of the directed graph model are assigned the plane locations (or fields) from the first selection of plane locations (or fields) and first arcs starting and I or ending at the first nodes of the directed graph model are assigned location-to-location (field-to-field) movements from and I or to plane locations (or fields) from the first selection of plane locations (or fields).

Alternatively or in addition, the method may comprise, in the data processing device, providing first frequent endpoint location (field) data I data on first frequent pairs of endpoint locations (fields) indicative of a first selection of plane locations most frequently providing for an endpoint I a first selection of plane location (field) pairs most frequently providing for a pair of endpoints (start and destination) of a route of traveling for the carriers. The first selection of plane location (field) pairs may correspond to 5 to 10 pairs of endpoints, i.e. the first selection of plane location (field) pairs may correspond to 5 to 10 routes of traveling for the carriers.

The pairs of plane fields or locations can comprise the first selection of plane fields (most frequently providing for an endpoint of a route of traveling or moving for the carriers) and I or the first selection of plane location (field) pairs. In particular, the first selection of plane fields (most frequently providing for an endpoint of an individual route of moving for the carriers) and I or the first selection of plane location (field) pairs can define the pairs of plane fields I locations. The first selection of plane locations (or fields) (most frequently providing for an endpoint of a route of traveling for the carriers) and I or the first selection of plane location (field) pairs can correspond to the transfer locations (or fields) and I or pairs of the transfer locations (but is not limited thereto). However, the first selection of plane locations (fields) may correspond to all endpoints and I or the first selection of plane location (field) pairs can correspond to all pairs of endpoints (start and destination) for travel routes for carriers.

Alternatively or in addition, the method may comprise, in the data processing device, providing data on first endpoint locations (fields) and I or first pairs of endpoint locations (fields) indicative of a first selection of plane locations (fields) and / or a first selection of plane location (field) pairs located in a first area, corresponding to a first workflow, and I or corresponding to high- priority samples (time-critical tests).

One transfer field or location may correspond to one or more than one laboratory devices or stations such as, for example, analyzers. For the one or more than one laboratory devices a plurality of plane fields (each) can define the one transfer field. A first plane field of the plurality of plane fields can define the one transfer field. Alternatively, a second plane field of the plurality of plane fields can define the one transfer field. Whether the first or second plane field defines the one transfer field can be swapped. In particular, whether the first or second plane field defines the one transfer field can be swapped during the determining of individual (e.g. off-line) routes, in particular during determining a plurality of routes between pairs of plane fields from the plurality of plane fields in the directed graph model and I or during determining an optimized set of routes. The laboratory devices can comprise an input (assigned to a first transfer field) for the carriers and an output (assigned to a second transfer field) for the carriers. In particular, the input and output can be swapped during determining the individual routes. In particular, the swapping can take place in one or more of the optimization steps. Merely pairs of input and outputs may correspond to the pairs of plane fields. However, input and output can correspond to the same plane field.

The method may further comprise: (i) providing second frequent endpoint location data indicative of a second selection of plane locations (or fields) less frequently providing for an endpoint of an individual route, wherein the second selection of plane locations (or fields) is different from the first selection of plane locations (or fields); and (ii) determining the directed graph model of the transport plane, wherein second nodes of the directed graph model are assigned the plane locations (or fields) from the second selection of plane locations (or fields) and second arcs starting and I or ending at the second nodes of the directed graph model are assigned location-to-location (field-to-field) movements from and I or to plane locations (or fields) from the second selection of plane locations (or fields).

Alternatively or in addition, the method may comprise, in the data processing device, providing second frequent endpoint location (field) data I data on second frequent pairs of endpoint locations (fields) indicative of a second selection of plane locations (fields) less frequently providing for an endpoint I a second selection of plane location (field) pairs less frequently providing for a pair of endpoints (start and destination) of a route of traveling for the carriers. The second selection of plane location (field) pairs may correspond to 5 to 10 pairs of endpoints, i.e. the second selection of plane location (field) pairs may correspond to 5 to 10 routes of traveling for the carriers. The second selection of plane locations (fields) may differ (completely I in pairs) from the first selection of plane locations (fields). The second selection of plane location (field) pairs may differ (completely I in pairs) from the first selection of plane location (field) pairs. The pairs of plane fields or locations can comprise the second selection of plane locations (or fields) and I or the second selection of plane location (field) pairs. In particular, the second selection together with the first selection of plane locations (or fields) and I or plane location (field) pairs can define the pairs of plane locations (or fields). The second selection of plane locations (or fields) and I or the second selection of plane location pairs can be non-transfer locations (or fields), i.e. the second selection of plane fields and I or the second selection of plane location pairs may not comprise transfer locations (or fields) (but is not limited thereto).

Alternatively or in addition, the method may further comprise, in the data processing device, providing data on second endpoint locations (fields) and I or second pairs of endpoint locations (field) indicative of a second selection of plane locations (fields) and / or a second selection of plane location (field) pairs located in a second area, corresponding to a second workflow, and I or corresponding to samples with a lower priority.

The first selection of plane locations (or fields) I plane location (field) pairs may define a first set of pairs of plane locations (or fields). The second (and first) selection of plane locations (or fields) I plane location (field) pairs may define a second set of pairs of plane locations (or fields). The first and second set of pairs of plane locations (or fields) may be made of (may define) the pairs of plane locations (or fields). The determining of routes which may be, for example, conducted as the pre-determining of individual routes may comprise a first determining of routes, wherein the first set of pairs of plane locations (or fields) defines the pairs of plane locations (or fields), and a second determining of individual routes, wherein the second set of pairs of plane locations (or fields) defines the pairs of plane locations (or fields). The first and second determining of routes may take place independently of each other. First and second (optimized) routes may correspond to the first and second determining of individual routes. The determining of routes may comprise a third determining of routes. The third determining of routes may correspond to third (optimized) routes. The third determining of routes may comprise determining an optimized set of routes between a third selection of plane locations (fields) I plane location (field) pairs. Analogously, fourth, fifth and further optimized individual routes can also be calculated in groups (5 to 10 routes and / or 5 to 10 plane location pairs). The second determining of routes may take place subsequent the first determining of routes. The second determining of routes may depend on the first (optimized) routes determined via the first determining of routes. The expected traffic load from the first set of routes may be considered during the second optimization. During the second determining of routes, the first (opti- mized) routes may be fixed. The second determining of routes may comprise single-route algorithms, e.g. A*-algorithm. The first and second determining of routes may correspond to determining the plurality of routes between pairs of plane locations (or fields) from the plurality of plane locations (or fields) in the directed graph model. The third determining of routes may correspond to determining the optimized set of routes from the plurality of routes.

A pair of the first set of pairs of plane locations (or fields) may comprise two plane locations (or fields) from the first selection of plane locations (or fields). A pair of the second set of pairs of plane locations (or fields) may comprise two plane locations (or fields) from the second selection of plane locations (or fields). However, additionally or alternatively, a pair of the second set of pairs of plane locations (or fields) may comprise one plane locations (or fields) from the first selection of plane locations (or fields) and one plane locations (or fields) from the second selection of plane locations (or fields).

The method may still further comprise the following: providing traffic data indicative of a predicted number of carriers moving between the pairs of plane locations (or fields) in a time interval; and calculating the optimized set of individual routes between pairs of plane locations from the plurality of plane locations in dependence on the predicted number of carriers travelling between the pairs of plane locations. In addition or alternatively, the traffic data may be indicative of an actual I recent number of carriers travelling between the pairs of plane locations in a time interval.

The providing of traffic data may further comprise at least one of: providing traffic data determined from a sample order listing; providing traffic data determined from historical data indicative of historical operation of the laboratory sample distribution system; and providing traffic data determined from workflow data indicative of a workflow for the one or more sample containers to be carried by the plurality of carriers; providing traffic data determined from a measured current and I or recent number of carriers transported; and providing traffic data determined from a simulation. The traffic data may correspond to empty as well as to filled (routed) carriers.

The calculating of the optimized set of individual routes between pairs of plane locations from the plurality of plane locations may further comprise applying at least one constraint selected from the following group: minimizing a route length of each individual route; minimizing a weighted route length of each of the individual routes; minimizing a number of route curves for each individual route; minimizing a number of individual routes by joining another individual route; uniformly distributing carrier traffic per plane field; limiting field-to-field movements between two plane fields to movement between adjacent plane fields only; excluding plane fields reserved for carrier queuing; uniformly distributing predicted wear of plane fields over the plurality of plane fields of the transport plane; minimizing the energy consumption of the laboratory sample distribution system; and minimizing I avoiding areas of 2x2 plane positions (logical fields) with four crossings. An area of 2x2 plane positions with four crossings may be indicative of one potential deadlock situation. Analogously, further potential deadlock situations may be defined. An additional or alternative constraint may be the minimization or avoidance of one or more further potential deadlock situations.

The constraints can have weightings. Routes with higher expected traffic may be higher weighted. The more highly weighted route may be prioritized over the less highly weighted route in minimizing the respective route length, number of route curves, and I or number of crossings and I or overlaps with other routes. The first and second pre-determining of individual routes may comprise applying different constraints.

The constraints can have weightings. The weightings can be set empirically. The constraints can be hard (e.g., can have an “infinite weight’) or soft (e.g., can have a finite weight). Constraints relating to routes with high traffic can have higher ratings than routes with lower traffic. According to one example, which refers to a route with low traffic intensity, the following weights are applied in the optimization: (i) route length: 2 penalty points per field (plane location or plane position) used in the route; (ii) route joining: 80 penalty points for route joining another one. According to another example, which refers to a route with higher traffic intensity, the following weights are applied in the optimization: (i) route length: 3 penalty points per field (plane location or plane position) used in the route; (ii) route joining: 120 penalty points for route joining another one.

The preventing of the deadlock arrangement on the transport plane may further comprise preventing moving a carrier along a corresponding route segment in case a last field of the fields of the corresponding route segment is comprised by the individual route of another carrier.

With respect to the laboratory automation system, the plurality of laboratory devices (stations) may comprise one or more laboratory devices selected from the following: laboratory device for pre-analytics, laboratory device for sample analysis, and laboratory device for post-analytics. A pre-analytical station or device may be adapted to perform any kind of pre-processing of samples, sample containers and I or sample container carriers. Analytical stations may be adapted to use a sample or part of the sample and a reagent to generate a measuring signal, the measuring signal indicating if and in which concentration, if any, an analyte is existing. Post-analytical stations may be adapted to perform any kind of post-processing of samples, sample containers and I or sample container carriers.

Controlling of the driving device may comprise the following: (i) in the driving device, receiving a reservation request from a carrier traveling on a selected individual route from the pre-determined individual routes and being located on a present route location or field along the selected individual route, the reservation request indicating a request for reserving a following route field along the selected individual route, (ii) verifying whether the following route field is free for travelling by the driving device, and (iii) moving the carrier from the present route field to the following route field along the selected individual route, if it is verified by the driving device that the following route field is free for travelling.

After verifying that the following route field is free for travelling and prior to moving the carrier, the following route field can be reserved for this carrier, i.e. the following route field can be blocked for other carriers. In particular, the following route field can be blocked for other carriers until the carrier in question has reached and subsequently left the following route field. The above may analogously apply for n following route fields. The n following route fields may correspond to a subset of locations I fields (e.g., logical fields I plane positions) along the selected individual route. In this case, the n following route fields can be unlocked for other carriers one after the other after they have been passed through by the carrier.

The determining of individual routes which may be conducted as the pre-determining may further comprise, in the data processing device, receiving first route traffic information indicative of high carrier traffic for a first individual route, and splitting the at least one individual route into two or more different individual routes. The first route traffic information may be derived by the traffic (intensity) data indicative of the predicted number of carriers travelling between the pairs of plane fields in a time interval. A (traffic-)threshold may be predefined. If the number of carriers travelling between the (corresponding) pair of plane fields in a time interval is greater than the threshold, the traffic may be identified as high (high traffic). If the number of carriers travelling between the (corresponding) pair of plane fields in a time interval is lower than the threshold, the traffic may be identified as low (low traffic).

Several (traffic-)thresholds of different sizes can be defined. The more (traffic-)thresholds are exceeded, the more often the at least one individual route can be split. The at least one individual route can be split into as many different individual routes as thresholds have been exceeded. The (traffic-)threshold can be indicative of the maximum capacity of a route. In case of several thresholds, the first I smallest threshold may be indicative of the maximum capacity of a route and the subsequent threshold may be indicative of twice the maximum capacity of a route.

The different individual routes may comprise a first and a second individual route being different from each other. The first and second individual routes may have overlap-sections and spaced sections. For example, the spaced sections may comprise parallel sections. Carriers that originally followed the at least one individual route prior to the splitting of this route may follow one of the two or more different individual routes into which the at least one individual route has been split. The carriers can be divided equally between the two or more different individual routes. Thus, in case of two different individual routes, 50 % of the carriers may follow the first of the two different individual routes and 50 % of the carriers may follow the second of the two different individual routes. Alternatively, the loads of the different individual routes may be different. For example, the shortest of the different individual routes may have the highest load. If one of the different individual routes is the best with respect to the optimization (e.g., is the shortest and I or has the fewest crossings with other routes), this route can have the highest load of the different individual routes. Alternatively, one route of the different individual routes can be loaded with traffic until the (traffic-)threshold is reached and all traffic exceeding this threshold can be sent to a further route of the different individual routes.

A traffic intensity matrix or list of two dimensions can be indicative of the (expected) traffic intensity for each pair of plane locations (start-point/ end-point combination) (cf. Table 1). Each pair of plane locations can correspond to a certain (needed) traffic intensity.

Table 1 : Example of traffic intensity matrix with start-points in the columns and end-points in the rows. Each table entry represents an expected traffic intensity for the corresponding pair of start-point and end-point.

The method may further comprise providing traffic intensity data indicative of a predicted number of carriers travelling between each of the pairs of plane fields in a time interval. The traffic intensity data may be comprised by the traffic data. The traffic intensity may comprise the traffic intensity matrix or the list of two dimensions.

The traffic data may be determined based on the traffic intensity data and I or the traffic intensity for each pair of plane locations. The traffic intensity data and I or the traffic intensity for each pair of plane locations may be calculated on a total accumulated traffic between each pair of plane locations, a peak traffic between each pair of plane locations, and I or capacities of the laboratory devices assigned to each pair of plane locations. For determining the total accumulated traffic, all moves between each pair of plane locations can be calculated, e.g. from order lists, e.g. for a specific time interval. For instance, the number of carriers being moved I estimated to be moved within 24 hours between each pair of plane locations can be indicative of the total accumulated traffic between each pair of plane locations. For determining the peak traffic, a time-window (e.g., a moving time window) or fixed time intervals of, e.g. 15 or 30 minutes over 24 hours, may be defined, in which the maximum traffic intensities can be identified for each pair of plane locations. The peak traffic can correspond to a global or a local peak traffic. The global peak traffic corresponds to the traffic intensities for each pair of plane locations when the traffic between all pairs of plane locations is maximum. The local peak traffic corresponds to the maximum traffic intensities for each pair of plane locations. The maximum traffic intensities for different pairs of plane locations can be present at different times. The capacities of the laboratory devices can be considered to avoid queues in the proximity of the laboratory devices. The sum of the traffic (intensities) (for each route) can correspond to the transport capacity of the system (for each route). The transport capacity can be matched (for each route) to the capacities of the laboratory devices (for each route). The above (traffic-)threshold may be compared to traffic intensity data for each pair of plane fields or locations to decide whether the traffic is high.

The first selection of plane fields may be indicative of frequent pairs of plane fields (endpoints of carrier routes). The second selection of plane fields may be indicative of less-frequent pairs of plane fields (endpoints of carrier routes). The first selection of plane fields may correspond to high entries in the traffic intensity matrix. The second selection of plane fields may correspond to lower entries in the traffic intensity matrix.

The determining of individual routes may comprise a first determining of individual routes, wherein the first selection of plane fields defines the pairs of plane fields, and a second predetermining of individual routes, wherein the second selection of plane fields defines the pairs of plane fields. The first determining of individual routes may be prioritized. The first determining of individual routes may take place prior to the second determining of individual routes. During the second determining of individual routes, the first determined individual routes may be fixed I “frozen”. The first and second determining of individual routes may be provided analogously to the determining of individual routes.

In an optimization, the traffic intensities can be used to weight the importance of each of the pairs of plane fields. For instance, for a pair of plane fields with high traffic intensity, it is more important to reduce the number of bends or crossings of the corresponding route connecting the pair of plane fields than for pairs of plane fields with less traffic intensities.

The determining of individual routes may further comprise receiving second route traffic information indicative of high carrier traffic (intensity) for a second individual route, and preventing the second individual route from route adjustment while determining one of the plurality of individual routes and I or determining the optimized set of individual routes. This step may alternatively or additionally be comprised by the step of calculating the optimized set of individual routes.

The determining I calculating of the individual routes between the pairs of plane fields from the plurality of plane fields (e.g., in the directed graph model) may further comprise: receiving first carrier traffic information indicative of a first carrier traffic scenario for the plurality of individual routes; determining a first plurality of individual routes between the pairs of plane fields from the plurality of plane fields (e.g., in the directed graph model); receiving second carrier traffic information indicative of a second carrier traffic scenario for the plurality individual routes, wherein the second carrier traffic scenario is different from the first carrier traffic scenario; and determining a second plurality of individual routes between the pairs of plane fields from the plurality of plane fields (e.g., in the directed graph model). This step may alternatively or in addition be comprised by the pre-determining step.

The first plurality of individual routes between the pairs of plane fields may comprise a first number of plane fields comprised I traversed by the first plurality of individual routes. The second plurality of individual routes between the pairs of plane fields may comprise a second number of plane fields comprised I traversed by the second plurality of individual routes. The first and second number of plane fields may be different. Each plane field may correspond to a respective module of the transport plane. Modules corresponding to I comprising only plane fields not comprised I traversed by the (first and I or second plurality of) individual routes may be switched off.

For the laboratory sample distribution system, the embodiments described above in connection with the method of operating a laboratory sample distribution system may be provided accordingly.

According to another aspect, a method of operating a laboratory sample distribution system is provided. The laboratory sample distribution system comprises a plurality of carriers having a number of n (n>3) carriers each configured to carry one or more sample containers containing a sample to be analyzed by laboratory devices (wherein the plurality of carriers may be a subset of a total plurality of carriers comprised by the laboratory sample distribution system); a transport plane assigned to the laboratory devices and configured to support to the plurality of carriers, wherein the transport plane comprises a plurality of interconnected transport modules comprising a plurality of plane fields (wherein at least one of the plane fields (each plane field) may only accept one carrier at a time and I or at least one of the plane fields (each plane field) may accept more than one carrier at a time); and a driving device configured to control movement of the plurality of carriers along individual routes between the plurality of plane fields, the movement comprising moving, in response to driving control signals, the plurality of carriers between neighboring plane fields of the plurality of plane fields along the individual routes.

The method is comprising (i) providing a plurality of route segments to be traveled, wherein for each of the plurality of carriers, a respective route segment to be traveled is provided along respective routes on the transport plane, each route segment being provided by one or more plane fields of the plurality of plane fields; and (ii) preventing, for the plurality of carriers, a deadlock arrangement on the transport plane in which the plurality of carriers block each other from further movement along the individual routes (wherein the prevention of the deadlock arrangement on the transport plane may take place off run-time, e.g. via simulations and I or calculations, in particular when designing routes or sections of the routes, and / or in runt-time). The preventing is further comprising (in the driving device): determining, at a present operation time, whether a deadlock arrangement for the plurality of carriers on the transport plane will (potentially or is likely to) occur at a future operation time in case the plurality of carriers are moved along the plurality of route segments. When it is determined that no deadlock will occur, moving the plurality of carriers along the plurality of route segments (each such moving may define a move). When it is determined that a deadlock will (potentially or is likely to) occur, moving the plurality of carriers in a supervised manner for avoiding the deadlock. Alternatively, the carriers can be moved in any case in a supervised manner.

Moving the plurality of carriers in a supervised manner for avoiding the deadlock may comprise moving the carriers one by one (along their respective route segments), checking each time whether moving the next carrier will cause the deadlock, and skipping moving a certain carrier or reducing its move length (e.g., number fields of the corresponding route segment) if it is determined that this moving will cause the deadlock.

The preventing may comprise determining a (minimum) number of (empty) fields that would complete a deadlock if they were occupied by carriers. Moving the plurality of carriers in a supervised manner for avoiding the deadlock may comprise, if the number of (empty) fields that would complete a deadlock if they were occupied by carriers is below a threshold (e.g., 2 or 3), skipping (preventing) moves of carriers that would end on one of the fields from the number of (empty) fields that would complete a deadlock (situation) (e.g., the last field of the fields of the respective route segment corresponds to one of the fields from the number of (empty) fields that would complete a deadlock). Alternatively or in addition, the move length (e.g., number of fields of the corresponding route segment) may be reduced.

Moving the plurality of carriers in a supervised manner for avoiding the deadlock may comprise preventing moving a carrier along its route segment in case this move ends up crossing a route of another carrier (e.g., the last field of the fields of the route segment is comprised by another carrier’s route). Alternatively or in addition, the move length (e.g., number of fields of the corresponding route segment) may be reduced or increased.

According to another aspect, a laboratory sample distribution system is provided that is configured to execute at least some of the above-mentioned method steps.

For the laboratory sample distribution system, the embodiments described above in connection with the method of operating a laboratory sample distribution system may be provided accordingly.

Moreover, embodiments described above in connection with the different methods of operating a laboratory sample distribution system can be combined with each other.

Description of further embodiments

In the following, embodiments, by way of example, are described with reference to figures. In the figures, show:

Fig. 1 a graphical representation of a laboratory sample distribution system;

Fig. 2 a graphical representation of a flow diagram of a method of operating a laboratory sample distribution system;

Fig. 3A a graphical representation of an example of a smallest deadlock;

Fig. 3B a graphical representation of an example of allowed movements for a carrier at a given plane field;

Fig. 3C a graphical representation of an example of carrier movements at a given plane field or location that are not allowed;

Fig. 3D a graphical representation of a specific pattern for allowed field-to-field (location-to- location) movements on the transport plane;

Fig. 4 a graphical representation of a reserved track segment and a subsequent flagged plane field for a first carrier;

Fig. 5 a graphical representation of a split route;

Fig. 6A a graphical representation of a situation which can lead to a deadlock;

Fig. 6B a graphical representation of the situation shown in Fig. 6A after carrier movants are performed; and

Fig. 7 illustrates a strategy for avoiding a deadlock. Fig. 1 shows a graphical representation of a laboratory sample distribution system. The laboratory sample distribution system comprises a plurality of carriers 4 configured to carry one or more sample containers containing a sample to be analyzed by laboratory devices 3, a transport plane 1 assigned to the laboratory devices 3 and providing support to the sample container carriers 4, and a driving device 13 configured to move, in response to driving control signals, the plurality of carriers 4 between plane fields or locations 5 provided on the transport plane 1.

The transport plane 1 is provided by a plurality of transport modules 12. The transport plane 1 may comprise a plurality of plane positions I logical fields 5. In the illustrated case, one plane position I logical field 5 defines one plane location 5’. Each transport module 12 is assigned a respective plane field or location 5. Each laboratory devices 3 is assigned one or more (local or adjacent) plane fields or locations 5.

Fig. 1 also shows a representation of a directed graph model 8 which is provided in an example for determining individual routes for the carriers 4 for travelling or moving between the plane fields or locations 5 (start plane field to end plane field). Alternative methods for determining individual routes for the carriers 4 in a given arrangement of plane fields, such methods known as such, may be applied.

In the example shown, the directed graph model 8 comprises a plurality of nodes 9 and a plurality of arcs 10 connecting the nodes 9. Each of the nodes 9 of the directed graph model 8 may correspond to a respective plane field 5. Alternatively, for a subset of the nodes 9, each node 9 may correspond to a respective plane field 5. Each of the arcs 9 of the directed graph model 8 may correspond to a movement between two respective plane fields 5. Alternatively, for a subset of the arcs 9, each arc 9 may correspond to a movement between two respective plane fields 5.

A laboratory device 3 is assigned one or more plane fields 5. One of these plane fields 5 (plane locations 5’) can be a transfer field or location 16. Each laboratory device 3 is assigned to one or more transfer fields 16. Carriers 4 being located on a first transfer field assigned to a laboratory device can be transferred from this transfer field to the laboratory device. Alternatively, if carriers 4 with a sample are located on the first transfer field assigned to the laboratory device 3, the sample can be transferred from the first transfer field to the laboratory device 3. Carriers 4 being located in the laboratory device 3 can be transferred to a second transfer field assigned to the laboratory device 3. Alternatively, if carriers 4 without a sample are located on the second transfer field assigned to the laboratory device 3, a sample can be transferred from the laboratory device 3 to the carrier 4 on the second transfer field. The first and second transfer field may be assigned to the same laboratory device 3. The first and second transfer field may correspond to an input and an output of the laboratory device 3 (input plane field and output plane field). The first and second transfer field may correspond to the same or to different plane fields 5 assigned to the laboratory device 3. It is noted that only one carrier 4 can be provided on one plane field.

Via the transport plane 1 , carriers 4 are moved between different plane fields 5. In particular, carriers 4 may be moved between pairs of plane fields 11 . The movements may correspond to individual routes 6 for the carriers 4. A first plane field of the individual route 6 may provide for a start plane field and a last plane field of the individual route 6 for a destination plane field and vice versa. Start plane fields and destination plane fields may correspond to endpoint fields and I or pairs of plane fields 11. For each pair of plane fields 11 , different individual routes 6 may be provided. Each pair of plane fields 11 may comprise two plane fields 5, e.g. a start plane field 1 T and a destination plane field 11”, i.e. two endpoint fields. First frequent endpoint field data indicative of a first selection of plane fields 14 most frequently providing for an endpoint of a route 6 of traveling for the carriers 4 may be determined. This first selection of plane fields 14 may correspond to a first set of pairs of plane fields 11 . The first set of pairs of plane fields 11 may correspond to transfer fields, in particular to transfer fields 16 frequently visited by carriers. Second frequent endpoint field data indicative of a second selection of plane fields 15 less frequently providing for an endpoint of a route 6 of traveling for the carriers 4 may be determined. This second selection of plane fields 15 may correspond to a second set of pairs of plane fields 11 . The second selection 15 may not correspond to transfer fields 16. The second set of pairs of plane fields 11 may not correspond to transfer fields 16. The second set of pairs may comprise pairs 11 that do not correspond to the first selection 14 and I or pairs 11 in which one field of each pair 11 corresponds to the first selection 14 and the other field of each pair 11 corresponds to the second selection 15. The second set of pairs of plane fields 11 may correspond to transfer fields 16 less frequently visited by carriers 4. An alternating sequence of nodes 9 and arcs 10 can form a route 6, wherein the first and the last element is a node 9, these nodes 9 corresponding to a pair of plane fields 11. Fig. 1 shows four endpoints. The four endpoints may correspond to a selection of plane fields 14, 15. Between these four endpoints more than twelve possible connection routes exist. However, for sake of simplification, Fig. 1 merely shows two routes. Each endpoint can form a pair of plane fields 11 with any of the other endpoints. Accordingly, these four endpoints can define twelve different pairs of plane fields 11. In general, m endpoints can define 2 ■ b(m, 2) = m ■ (m - 1) different pairs of plane fields 11 (here, b() is the binomial coefficient). However, according to the Fig. 1 , two first endpoints 1 T, 11” correspond to the first selection of plane fields 14 and two other endpoints (second endpoints) correspond to the second selection of plane fields 15. The first endpoints may define a first pair of plane fields. The second endpoints may define a second pair of plane fields. A first traffic corresponding to the first pair of plane fields may be higher than a second traffic corresponding to the second pair of plane fields. Thus, the number of carriers 4 traveling between the first pair of plane fields may be higher than the number of carriers 4 traveling between the second pair of plane fields, e.g. in a given time interval.

Fig. 2 shows a graphical representation of a flow diagram of a method of operating a laboratory sample distribution system. The method according to Fig. 2 comprises determining the individual routes 6 on the transport plane (step 20), e.g. depending on transfer fields, by one or more processors of a data processing device. Such determining may be conducted at runtime of the laboratory sample distribution system and I or prior to moving the carriers 4 on the transport plane 1 , thereby, pre-determining (individual) off-line routes for the carriers 4 on the transport plane 1.

In the embodiment shown, the determining of the individual routes 6 comprises determining a directed graph model of the transport plane (step 21), wherein nodes 9 of the directed graph model 8 are assigned plane fields 5, and arcs 10 connecting the nodes 9 of the directed graph model 8 are assigned field-to-field movements between two plane fields 5. Further, a plurality of individual (e.g. off-line) routes 6 between pairs of plane fields from the plurality of plane fields 5 in the directed graph model is determined in step 22. The individual routes 6 determined may be applied for moving the carriers 4 on the transport plane 1 .

As an option, an optimized set of individual routes may be determined from the plurality of individual routes 6 (step 23), such determining further comprising solving a mixed-integer optimization problem for the plurality of individual routes 6. Following, the driving device 30 may be controlling movement of the carriers 4 along the (optimized) individual routes 6 on the transport plane 1.

The pairs of plane fields 11 may comprise the first and second set of pairs of plane fields 11 . The determining of the individual routes can comprise two runs, a first and a second determining. In the first determining, routes 6 for the first set of pairs of plane fields 11 may be determined, and in the second pre-determining, routes 6 for the second set of pairs of plane fields 11 may be determined. Alternatively, the determining of the plurality of individual routes between pairs of plane fields from the plurality of plane fields in the directed graph model 22 can comprise two runs, one for the first and one for the second set of pairs of plane fields 11 . Alternatively, the determining of the optimized set of individual routes from the plurality of individual routes 6 can comprise two runs, one for the first and one for the second set of pairs of plane fields 11. In each case, the first run may be prioritized. The first run can be performed prior to the second run. During the second run, the routes determined via the first run may be fixed. In Fig. 1 , the first route 6’ may be calculated via a first run and the second route 6” may be calculated via a second run.

For example, the determining of the plurality of individual routes 6 between pairs of plane fields 11 from the plurality of plane fields 5 in the directed graph model can comprise a first run for determining first routes 6, and, independently therefrom, the determining of the plurality of individual routes between pairs of plane fields from the plurality of plane fields in the directed graph model 8 can comprise a second run for determining second individual routes. Subsequently, the first and second routes can be re-optimized depending on the first and second routes together and I or depending on (all) the pairs of plane fields 11 . This subsequent step can correspond to the determining of the optimized set of individual routes from the plurality of individual routes 6.

Fig. 3A shows a graphical representation of an example of a smallest deadlock if field-to-field (logical field I plane position) moves are possible for each field in only one X- and one Y- direction. In this case, four of the plurality of plane fields 5 of an area of 2x2 plane fields are occupied by four carriers 4. Thus, each of the four plane fields or locations is occupied by one carrier 4. For each plane field, with respect to the area of 2x2 plane fields, counterclockwise movements 31 to another plane field of the area of 2x2 plane fields are allowed. Furthermore, for each of the four carriers 4, such a movement is also intended. However, since each of the four plane fields is occupied, none of the four carriers 4 can reserve the following plane field and / or can perform the intended movement. This results in a deadlock.

Analogously, although not shown, other deadlock arrangement for more than four carriers may potentially happen at runtime of the laboratory sample distribution system. For example, a number of n (n>4) carriers 4 may be provided on a number of n plane fields, the plane fields arranged along a closed line or circle, thereby all carriers blocking each other from further movement to a next plane field already occupied by another one from the n carriers. An adjacency matrix corresponding to blocked carriers 4 may be provided in such alternative embodiments as well. Through matrix multiplications, it can be determined via the adjacent matrix if blocked carriers 4 form a circle, i.e. if blocked carriers form a deadlock.

Fig. 3B shows a graphical representation of an example of allowed movements 32 for a carrier 4 at a given plane field. At the given plane field, the carrier 4 may be allowed to move only in one X- and in one Y-direction. In Fig. 3B, the embodiment is shown that the carrier 4 is allowed to move in the X-direction left and in the Y-direction up. Fig. 3C, on the other hand, additionally illustrates carrier movements 33 at a given plane field 5 that are not allowed.

Fig. 3D shows a graphical representation of a specific pattern for allowed field-to-field movements 32 on the transport plane 1. In Fig. 3D, the transport plane 1 is divided in quadratic areas of 6x6 plane fields 35. Each area of 6x6 plane positions 35 corresponds to one transport module 12. The quadratic areas 35 can be cut at the edge of the transport plane 1. In the upper half of each quadratic area 35, the carriers 4 are allowed to move in the X-direction left, and in the lower half of each quadratic area 35, the carriers 4 are allowed to move in the X-direction right (only). In the left half of each quadratic area 35, the carriers 4 are allowed to move in the Y-direction down, and in the right half of each quadratic area 35, the carriers 4 are allowed to move in the Y-direction up (only). In this pattern, each quadratic area 35 comprises one area of 2x2 plane locations 34 in the center that can result in a deadlock. In this area of 2x2 plane fields 34, clockwise carrier movements are allowed. Moreover, the pattern comprises additional such areas of 2x2 plane fields 34, wherein each plane field 5 of each of the additional such areas of 2x2 plane fields 34 corresponds to a corner location 5 of a quadratic area 35. In Fig. 3D, each such area of 2x2 plane fields 34 (potentially forming a deadlock) is marked with an exclamation mark. The four plane positions involved in this 2x2 plane positions come from the 4 adjacent corners of 4 areas. There is one 6x6 area fully represented and 8 parts of 6x6 areas (only in part represented in Fig. 3D). Fig. 4 shows a graphical representation of a reserved track segment 42 and a subsequent flagged plane position 43 for a first carrier 4’. Fig. 4 illustrates a method for preventing deadlocks. The first carrier 4’ reserves a track segment 42 of plane position 5 along its route 41 . The first plane position 5 of the segment 42 corresponds to the plane position 5 that the first carrier 4’ would enter next, starting from its current plane position 5. Starting from the first plane position 5, the track segment 42 comprises of one or more immediately adjacent further plane positions 5 up to a last plane position 5 of the track segment 42. In Fig. 4, the track segment 42 comprises two plane positions 5, i.e. a first and a last. The plane positions 5 of the track segment 42 of the first carrier 4’ may be reserved for the first carrier 4’, i.e. these plane positions 5 may be blocked for carriers 4 other than the first carrier 4’. The plane position 5 on the route 41 of the first carrier 4’ that follows directly after the last field of the segment 42 of the first carrier 4’ can be flagged for the first carrier 4’. The flagged plane position 43 of the first carrier 4’ may not be reserved by other carriers 4, i.e. the flagged plane position 43 may not be comprised by segments 42 of other carriers 4. In Fig. 4, in particular the fourth carrier 4” is thus not allowed to reserve the next two plane positions to the right of its current position, since it is not allowed to reserve the flagged plane position 43.

Fig. 5 shows a graphical representation of a split route 51. If the traffic of a determined route 51 has a high traffic, e.g. if the traffic exceeds a threshold, the route 51 may be divided in several sub routes 52, 53. In the case of Fig. 5, the route 51 with high traffic is divided in two sub routes 52, 53. The sub routes 52, 53 comprise overlapping sections, separating I merging sections and parallel sections. The traffic of the route 51 with high traffic may be divided 50 % to the upper route 52 and 50 % to the lower route 53. Alternatively, the traffic of the route 51 with high traffic may be distributed to the sub routes 52, 53 in a different weighting. For example, the shortest of the sub routes 52, 53 of the split route 51 may be provided with the highest percentage of the traffic. To avoid collisions at the crossings 54 of routes, the carriers 4 assigned to the split route 51 may alternatively follow one of the sub routes 52, 53.

Fig. 6A shows a graphical representation of a situation which can lead to a deadlock. 1 Below, an example of an algorithm that avoids running into a deadlock is explained with respect to Fig. 6A. In a first step, the next set of moves for a subset (plurality) of carriers 4, namely carriers 4 ¹ , 4 ² , 4 ³ , and 4 ⁴ , are planned. In a next step, it is checked if these moves could end up in a deadlock. If this is not the case, the planned moves can be executed. If these moves could end up in a deadlock, the list of planned moves is worked down, checking one by one if it the next move would create a deadlock. A move that would create a deadlock is prevented. Alternatively, the move length can be reduced in such a way that no deadlock is caused. Referring to the example of Fig. 6A, it is noted that the move of carrier 4 ¹ can be safely executed. Moving carrier 4 ² will cause a deadlock. Hence, the move for carrier 2 can either be skipped or the move length can be reduced in such a way that is does not cause a deadlock. The move of carrier 4 ³ can be safely executed. The move of carrier 4 ⁴ can also be safely executed and would even reduce the deadlock risk. Fig. 6B shows a graphical representation of the situation shown in Fig. 6A after carrier movements are performed.

In the case shown in Fig. 6A, the situation depicted is only one position away from a deadlock, i.e. there is only one (empty) field 5 that would complete a deadlock if it were occupied by a carrier 4.

There may be one or more (empty) fields 5 that would complete a deadlock if occupied by carriers 4 (remaining open “side"). It may be forbidden to move a carrier 4 onto such a remaining open “side". In this case, for instance, a route from left to right for carrier 4 ⁴ is prohibited. If it is determined that only n (or less) free positions are remaining until a deadlock occurs, where n is configurable (n > 0), movements of carriers 4 ending at one of these positions may be prohibited.

Fig. 7 illustrates a strategy for avoiding a deadlock. In this case, carrier moves that end on a crossing with other routes 6 are prohibited. Hence, the moves of carriers 4 ¹ and 4 ² on the left side of Fig. 7 are not allowed as they would end on a crossing with vertical routes 6. However, their moves can be shortened or lengthened to put them in a condition of allowance (cf. right side of Fig. 7).