—We describe a decentralized routing algorithm with physical time windows for modular conveying systems. Existing routing algorithms for modular conveyors are already capable of bi-directional conveying while avoiding conﬂicts such as collisions, deadlocks, livelocks and starvation effects. In addition to avoiding conﬂicts, routing algorithms must also select routes that reduce the travel time. No existing algorithm for modular conveyors bases this decision on the expected physical lead time, even though physical lead time directly affects the system throughput. In this publication, we present an algorithm that uses the physical lead time to select routes while avoiding conﬂicts. Note to Practitioners —Conventional automated conveying sys- tems are inﬂexible to layout changes. Modular conveying systems have been developed that address this issue. Their layout can be changed within minutes with no manual conﬁguration necessary. This ﬂexibility is enabled by decentralized routing algorithms. In this publication, we present a novel decentralized routing algorithm that selects routes based on the physical lead time. Since the throughput is a result of the physical lead time, the throughput is optimized. Index Terms —Modular conveyors, Multi-agent system, Decen- tralized control, Conﬂict-free, Bi-directional routing I. I NTRODUCTION TODAY’S material ﬂow is handled by a combination of conventional automated conveying systems and manual labor. On one hand, conventional conveying systems have a high throughput but are inﬂexible to layout changes. On the other hand, manual labor has the opposite characteristics. Flexible automated conveying systems combine the best of both worlds: having a high throughput and having high layout ﬂexibility. According to Furmans et al. [1] a system has a high layout ﬂexibility, if the layout can be changed within minutes or at most a few hours. Furmans et al. [1] also identiﬁed design patterns of ﬂexible conveying systems – the conveying system must consist of identical modules with de- centralized controls. These modules have wheels underneath, and thus, they can be quickly rearranged into a new layout. When the modules have been rearranged, the decentralized controls conﬁgure themselves by exchanging messages with their neighboring modules. Thus, no manual conﬁguration of the system is necessary. In addition to having a modular design and decentralized control, all conveying systems must avoid conﬂicts to ensure the conveying of packages. The most critical conﬂicts are: 1)Collisions occur when two packages collide with each other and interlock, and thus, are no longer conveyed. S. Sohrt and L. Overmeyer are with the Institute for Transport and Automa- tion, Leibniz University Hannover, Hannover, Germany (simon.sohrt@ita.uni- hannover.de; ludger.overmeyer@ita.uni-hannover.de) Fig. 1. Intersection consisting of four modular conveyors (based on [4]) 2)Deadlocks occur when at least two occupied conveyors are cyclically waiting on each other to become available [2]. 3)Livelocks occur when a package performs the same cycle of movements over and over again [3]. 4)Starvation occurs when two packages from different directions compete at an intersection for right of way. If one direction has high throughput and is always prioritized, the packages from the other direction will never get closer to their destination [4]. Conﬂict-avoidance is handled by routing algorithms. The need for routing algorithms is depicted in Fig. 1. In this example, four modular conveyors form an intersection. The intersection is surrounded by source and destination modules through which packages may enter and leave. In this example, the conveying of packages A, B, and C has already begun, while package D just entered the system. The shortest path for every package is depicted by arrows. If package D enters the intersection immediately and follows the shortest path, a conﬂict occurs (either a collision or a deadlock). Several routing algorithms have been developed that prevent conﬂicts (see Section II). In addition to avoiding conﬂicts, routing algorithms must also select routes that positively affect the throughput. Existing routing algorithms have used different methods of selecting routes, but no algorithm has selected routes based on the expected travel time. In this paper, we propose a novel routing IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2 Fig. 2. The GridSorter systems is made up of several large-scaled conveying modules [4] algorithm that selects routes based on the expected travel time by utilizing physical time windows. Since the throughput is a result of the travel time, the throughput is optimized by basing the selection of routes on the expected travel times. Our proposed routing algorithm is designed for decentral- ized controlled modular conveyors. Every conveyor has a schedule and a clock which is synchronized through the net- work. The synchronized clocks are needed to reserve physical time windows on the schedules. The conveyors reserve routes by exchanging messages: when a conveyor receives a request, it checks its schedule. If the request can be accepted, it sends a request to the next conveyor. If the request can not be accepted, a new time is proposed to the requesting conveyor. The rest of this paper is organized as follows. In Section II, we present state-of-the-art routing algorithms for modular conveying systems and for automated guided vehicles (AGV). We chose to include AGV routing algorithms because they can be modiﬁed to work in modular conveyors. In Section III, we describe our algorithm, and subsequently, in Section IV, we give an application example of the system behavior. Finally, we present our conclusion and outlook in Section V. II. R ELATED RESEARCH A. Modular Conveying Systems We divide modular conveying systems into two classes – large-scaled modules and small-scaled modules. If a single module can carry a package, the module is large-scaled in relation to the package size. If multiple modules are necessary to carry a package, it is small-scaled in relation to the package size. We will ﬁrst present the state-of-the-art of large-scaled modules followed by small-scaled modules. An example for a conveying system that is made up of large- scaled modules is shown in Fig. 2 – the GridSorter system. The prototypes of the GridSorter modules have been described in [2] and [4] and are now manufactured by ﬂexlog GmbH [5]. The footprint of a GridSorter module is 500 mm x 500 mm allowing packages to be conveyed into all four cardinal di- rections. Every module has four sensors at the sides to detectincoming packages and a dedicated control. Communication is only possible with its four direct neighbors. All modules have wheels underneath and four standardized connections on every side, which are used to transmit information and power from one module to another. Due to the wheels and the standardized connections, the modules can be rearranged into a new layout within minutes. If multiple modules are combined to form a layout, no single control has an overview of the whole system. Instead, the modules exchange messages and decide the conveying of packages on their own. Thus, the modules are software-agents as deﬁned by Franklin and Graesser [6] with decentralized and distributed controls. Large-scaled modules have also been manufactured by other companies. Two exam- ple systems are the XPlanar system [7] and the Motion Cube system [8], but no control algorithms have been published for these systems. We will only consider algorithms that can potentially fulﬁll our requirements, which are: conﬂict-free, work for any bi- directional conveyor layout, and select routes based on the expected travel time. We use a classiﬁcation to ﬁlter out all algorithms that do not fulﬁll our requirements. Different clas- siﬁcations are available (see [9]–[11]), but in this publication, we use the classiﬁcation by Seibold [4]. Only algorithms from Seibold’s class of “Time-window based Route Reservation” are able to fulﬁll all our requirements. Algorithms from this class reserve routes, from source modules to destination mod- ules, for individual packages. Every module keeps a schedule, which are used to reserve time windows for the individual packages. Even though we will not consider algorithms from other classes, we still want to mention the algorithms for modular conveying systems by Gue et al. [12], [13], by Mayer et al. [2], [14] and by Kr ¨uhn et al. [15], [16]. Seibold described a routing algorithm [4] that belongs to the class of “Time-window-based Route Reservation”. This algorithm is conﬂict-free and works for any bi-directional layout, selecting routes based on the expected logical lead time. One downside of utilizing logical time is that it does not progress unless a package is conveyed from one module to the next. The route with the shortest logical lead time is not necessarily the route with the shortest physical lead time. After presenting the algorithms for large-scaled modules, we will now present state-of-the-art small-scaled modules. An example depicting a conveying system that is made up of small-scaled modules is shown in Fig. 3 – the netkoPs system. The prototypes of the netkoPs modules are described in greater detail in [17]–[19]. The netkoPs modules are based on the cogniLog modules that have been described in [15], [16], [20]. Every netkoPs module has a sensor to detect packages, can convey in any direction, and has its own dedicated control. The footprint of a module is 60 mm x 60 mm. These modules can only communicate with their four direct neighbors and can be freely arranged into the slots of a matrix mounting. Prototypes of matrix mountings with different dimensions have been manufactured, and slots can be left unoccupied. Every matrix mounting has wheels underneath, and thus, can be freely positioned within a warehouse. Another example of a small-scaled conveyor system is the Celluveyor from Uriarte et al. [21]–[23]. None of the published control algorithms for IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 3 Fig. 3. The netkoPs system is made up of several small-scaled conveying modules (based on [17]) small-scaled modules belong to the class of “Time-windows based Route Reservation”, and therefore, are not presented. Kr¨uhn has shown that an algorithm that works for large- scaled modules can be modiﬁed to also work for small-scaled modules [15], [16]. B. Automated Guided Vehicles Both the hardware and the algorithms for automated guided vehicles (AGV) are much more advanced than their modular counterparts. The following overview publications describe state-of-the-art AGV routing algorithms: [9]–[11], [24]. As with the modular conveying systems, we will only focus on algorithms from the class of “Time-window-based Route Reservation.” Most algorithms from this class are based on the algorithm described by Kim and Tanchoco [25]. This algorithm is conﬂict-free, works for any bi-directional layout, and selects routes based on the physical travel time. Un- fortunately, all routes are sequentially planned by a central control that has a complete overview of the system. After a route has been planned, it is uploaded to the respective AGV . Kim and Tanchoco even explicitly stated that the algorithm cannot be used in a decentralized controlled system: “Parallel Fig. 4. The KARIS system can operate both as a single module, as a discontinuous cluster or as a continuous cluster [28] execution of the routeing algorithm may result in conﬂicting travel schedules or gridlocks in a bidirectional network.” [25] We want to highlight two publications regarding Kim and Tanchoco’s algorithm. The original algorithm neglected the problem of unexpected delays that can occur in real-world systems, during transport execution. Maza and Castagna [26] presented a modiﬁcation that prevents conﬂicts even when the previously reserved time windows are missed. This is accomplished by monitoring intersections: if a package misses its time window on the intersection, no other AGV must enter the intersection until the delayed AGV has passed the intersection. M¨ohring et al. [27] tested the practicality of the algorithm for real-world use-cases. Their algorithm is implemented to route vehicles at a Container Terminal in the Hamburg Harbor. Beforehand, they simulated different scenarios with up to 48 vehicles on a computer with an AMD-Athlon 2100+ (1,7 Mhz) processor and 512 MB Ram. Even for worst-case scenarios (new routes must be calculated for all vehicles at the same time), the computation took less than half a second. We believe that these fast computation times are the reason why Kim and Tanchoco’s algorithm was never modiﬁed extensively. It is already efﬁcient enough for real-world use-cases even in its basic form. Before we conclude the related research section, we want to mention the KARIS vehicles [28], [29]. The vehicles cannot only individually transport single items, but are also able to form two different functional clusters, as shown in Fig. 4. As a discontinuous cluster, KARIS vehicles connect to each other to transport items that are larger than a single module. As a continuous cluster, several KARIS vehicles form a conveyor line to realize high throughput of goods. To our knowledge, no detailed routing algorithms for KARIS vehicles have been published. To summarize, we identiﬁed two algorithms that are IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 4 conﬂict-free and work in any bi-directional layout – Seibold’s algorithm and Kim and Tanchoco’s algorithm. Seibold’s algo- rithm is decentralized, but routes are selected by using logical lead time and not physical lead time. Kim and Tanchoco’s algorithm, and its modiﬁcations, use physical lead time to select routes but are designed for a centrally controlled system. As a result of our literature review, we identiﬁed the following research question: Is it possible to create a decentralized routing algorithm that selects routes based on the physical lead time in any bi- directional layout while avoiding conﬂicts? We believe that by utilizing physical time windows we can answer this question. III. T HEALGORITHM A. Clock Synchronization A prerequisite for our algorithm is the synchronization of clocks in all conveyors. The clocks need not be synchronized perfectly, but the timing differences of neighboring conveyors must be small enough that the conveying process is not affected in a meaningful way. The synchronization of clocks is a well-researched ﬁeld [30], and many cheap technical solutions exist. We would like to point out the Precision Time Protocol (PTP), which was deﬁned in the IEEE 1588-2008 standard [31]. PTP was designed for local systems requiring high accuracy that can not bear the cost of a GPS receiver at each node, or for which GPS signals are inaccessible [32]. It can be used within a standard ethernet-network, and thus, is cost-effective. The accuracy of PTP time signals is in the sub-microsecond range, and thus, is sufﬁcient for the conveying of packages which rarely exceeds 10 m/s. B. Algorithm for Large-scaled Modules We will ﬁrst present our algorithm for large-scaled modules, and subsequently, a modiﬁcation for small-scaled modules. As previously mentioned in Section III-A, we assume that the clocks of every module are sufﬁciently synchronized. The algorithm is depicted in ﬂowchart-form in Fig. 5, and an application example for further clariﬁcation is given in Section IV. A short overview of the algorithm: the modules reserve a route from source to destination by exchanging messages. Every module along a route stores a routing entry on its schedule. Routing entries include an arrival and a departure time. Every route reservation has two phases: the request phase and the conﬁrmation phase. In the request phase the route is planned from source to destination. During this phase, the modules have to select a path, and they have to negotiate the arrival and the departure times. After the request has reached the destination module, the route is conﬁrmed from destination to source. The presented algorithm ignores the effects of acceleration, deceleration, and slippage that occur in real-world conveying systems. All three effects can be accounted for by adding a safety allowance to the time windows. In the following para- graphs, we will not explicitly mention this safety allowance for the sake of simplicity.Before route reservations can be created, the modules must be initialized. During this initialization, every module generates a routing table by communicating with its direct neighbors. Hereupon, this information is propagated through the system. This process is similar to creating metric tables in computer networks using the distance-vector routing protocol [33]. For every destination, the modules determine the ID of the neighboring module that is closest to this destination, the distance to the destination, and the number of intersections between the source module and the destination. Routing entries store the following data: unique request ID, physical time window (arrival time and departure time), priority, time-to-live (TTL), ID of the preceding module, ID of the succeeding module, and state (the two states are “requested” and “conﬁrmed”). The TTL is the maximum time a routing request may “live” before it is discarded and a new request is created by the source. Consequently, every module periodically checks the TTL for routing entries and deletes expired ones. The introduction of TTL was necessary to take into account the uncertainty of a decentralized controlled system with physical time windows. Since no module has a complete overview of the system, the source module can only estimate how long the route reservation process takes. Estimating the TTL, choosing time windows, and selecting routes are intertwined problems we will explain in detail after we overview the algorithm. Modules can send the following four messages types which must be processed in the following sequence: OBSOLETE, DENIAL, REQUEST, CONFIRMATION. The processing of messages in this sequence positively affects the throughput. Both OBSOLETE and DENIAL messages delete routing en- tries on the schedule. By processing them ﬁrst, the schedule opens up. Then, the REQUEST and CONFIRMATION mes- sages are processed, which either create or change the state of routing entries. By processing the REQUEST and CONFIR- MATION messages, previously unavailable time windows can be reserved, and thus, the chance of reserving a well-ﬁtting time window is increased, positively affecting the throughput. In the following paragraphs, we will explain how an initial request is started, how each message type is processed, how time windows are chosen, how the TTL is calculated, and how routes are selected. Initial creation of a REQUEST message: When a package enters the conveying system on a source module, the schedule of this source module becomes blocked indeﬁnitely until the route reservation is conﬁrmed. This source module estimates the TTL and the desired arrival time, and subsequently, sends a REQUEST message to the neighboring module with the shortest lead time. Every REQUEST message includes a unique request ID, the priority, the destination ID, the desired arrival time, and the TTL. Receiving a REQUEST message: When a module receives a REQUEST message, it tries to reserve an entry with the requested arrival time. If the newly created time window does not overlap with any previously created time window, an entry is created on the schedule, and a REQUEST message is sent to the neighboring module with the shortest lead time. Livelocks are prevented by excluding the possibility of sending IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 5 Fig. 5. Flowchart of the algorithm IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 6 a REQUEST message to the predecessor. When a REQUEST message reaches the destination module, a CONFIRMATION message is sent back to the requesting module. If a module receives a REQUEST message with an arrival time that overlaps with a previously created routing entry, it ﬁrst checks the state of the previously created entry. If the previously created entry is already in the state conﬁrmed, the module determines the next available time window and sends back a DENIAL message to the requesting module. If the previously created entry is in the state requested, the module compares the priority of the REQUEST message with the previously created entry. If the priority of the REQUEST message is lower, a DENIAL message is sent to the requesting module. If the priority of the REQUEST message is higher, the previously created time window is deleted, and a new routing entry is created. A DENIAL message is sent to the preceding module of the deleted routing entry, and an OBSOLETE message is sent to the succeeding module. Receiving a CONFIRMATION message: When a module receives a CONFIRMATION message, it changes the state of the corresponding routing entry to the state conﬁrmed and sends a CONFIRMATION message to its preceding module. When a CONFIRMATION message reaches the source mod- ule, the actual conveying of the package can start. Receiving a DENIAL message: A DENIAL message includes the unique request ID and the proposed time. When a DENIAL message is received, the receiving module attempts to alter the departure time of the corresponding routing entry. If this altered entry does not overlap with other entries, a REQUEST message is sent to the succeeding module. If overlap occurs, the same overlap resolution is used when receiving a REQUEST message. Receiving an OBSOLETE message: When a module receives an OBSOLETE message, the corresponding routing entry on is deleted even when it is already in the state conﬁrmed. Choosing time windows: The goal of the algorithm is to choose time windows that are as short as possible (as soon as a package leaves a module, another one can enter). If the time windows are as short as possible, the system utilization is higher, and thus, the throughput is positively affected. The length of the time windows is determined by arrival and departure time. The arrival time is based on the arrival of the package: when the package enters, the source is blocked indeﬁnitely until the route reservation process has been com- pleted. The blockage of the source does not negatively affect the throughput, because we only allow sources to exist at the border of our system (only one neighboring module is allowed). The reservation of the time window on the succeeding module is more complex: when the source sends a REQUEST message, it must include a desired arrival time. This arrival time must be far enough into the future that the route reserva- tion process is most likely completed by then. The completion time depends on the number of modules between the source and the destination and the number of overlaps that will likely occur, which need to be resolved. Since the source has nocomplete system overview, it can only estimate the number of overlaps. Because the number of overlaps can only be estimated, the arrival time can only be estimated. When a module receives a REQUEST message, it computes the earliest possible departure time, based on the arrival time and the conveying speed of the module. The routing entry is created, and a new REQUEST message is sent to the succeeding module. The arrival time of this new REQUEST message is based on the departure time that has just been computed. If the succeeding module sends a DENIAL message back, the departure time is altered to the proposed time of the DENIAL message. If this altered time window overlaps with other time windows, the overlap is resolved according to the previously presented overlap resolution method. If more overlaps occur than estimated, the CONFIRMA- TION message will reach the source after the estimated arrival time. Thus, it would become physically impossible for the package to arrive at the estimated arrival time. Because the ﬁrst time window is missed, all subsequent time windows may also be missed. A mismatch would have occurred between the projected movement of the package and the actual movement. As already mentioned in Section II-B Maza and Castagna [26] have proven that even when a mismatch occurs, conﬂicts can still be avoided by following the sequence of the previously negotiated time windows. Even though no conﬂict occurs due to the mismatch, it is still advantageous to avoid such a mismatch because the se- lection of routes depends on accurate schedules. The selection of routes is based on the lead time, which itself, is based on the projected movement. If the mismatch becomes too great, sub-optimal routes might be chosen. To avoid a mismatch between projected movement and actual movement, we introduce the concept of TTL. Before a source sends the ﬁrst REQUEST message, it estimates how long the route reservation will most likely take. A safety margin is added to increase the chance of completing the route reservation within the TTL. If the TTL is estimated too conservatively and the route reservation is conﬁrmed faster than estimated, the packet cannot start earlier, as this would also cause a mismatch between projected movement and actual movement. Therefore, the packet has to wait, and thus, the throughput is negatively affected. If the estimate is too optimistic and the route reservation is not conﬁrmed within the TTL, the source module has to start a new request. Since the packet has to wait until this new request has been conﬁrmed, the throughput is once again negatively affected. Thus, the next paragraphs, we present our approaches for estimating the TTL. Estimating the TTL: We developed two approaches for estimating the TTL. If the operating conditions remain ap- proximately constant, the ﬁrst approach estimates the TTL optimally. Operating conditions in this context are the rates at which packages enter and leave the system. When using the ﬁrst approach, the TTL is calculated as follows: TTL =tavg;dest nsafe (1) Every source module stores how long each route reservation took to reach its destination, and an average is calculated. This IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 7 average is multiplied by a safety factor – nsafe. This safety factor takes into account that the operating conditions remain only approximately constant. While testing the ﬁrst approach on different layouts, we achieved satisfactory throughputs by picking a value in a range from 1 to 2 for nsafe. If the operating conditions are constant, nsafe can be set to 1. Since route reservations which were not conﬁrmed within the TTL, increase the value of tavg;dest , this approach is self-correcting. If the layout of the conveying system changes, all previously calculated averages become invalid. Since packages still need to be conveyed during this start-up phase, a second approach for estimating the TTL is needed: TTL =nmodule tcom 2 +ninter ndenial tcom (2) The ﬁrst term nmodule tcom 2takes into account the communi- cation delay between source and destination module: nmodule is the number of modules between source and destination andtcom is the time for one module to receive and process a message. The 2is needed because all modules along a route have to receive and process at least two messages. First, a REQUEST message and a subsequent CONFIRMATION message. The second term ninter ndenial tcom takes into account the possibility that an intersection rejects the ﬁrst REQUEST message by sending a DENIAL message. ninter is the number of intersections between source and destination andndenial is the number of denials that are likely sent before the request is accepted. When we tested our algorithm on rectangular layouts, we discovered that ndenial = 2 leads to satisfactory throughputs. Selecting a route: Routes are selected based on the physical lead time. The base lead time for every neighboring module is computed by dividing the destination’s distance (which was determined during the initialization phase) by the uniform conveying speed of the modules. If a module received a DENIAL message beforehand, it adds the proposed delay to the base lead time. Thus, the modules do not select the neighboring module with the shortest distance to the destination, but the neighboring module with the shortest projected lead time. Livelocks are avoided by never choosing the preceding module, even if it has the lowest lead time. C. Modiﬁed Algorithm for Small-scaled Modules When the algorithm is modiﬁed for small-scaled modules, the concept of module neighborhoods is used [15]: the RE- QUEST message must be extended by adding the package dimensions. If a module receives a REQUEST message, it becomes the master module of the neighborhood for this time step. The master module uses the package dimensions from the REQUEST message to check the schedules of every slave module within the neighborhood. If every module within the neighborhood can reserve a time window for the REQUEST, a REQUEST message is sent to the optimal neighbor by the master module. If a single module within the neighborhood cannot accept the routing entry, a DENIAL message is sent to the preceding module. The process is depicted in Fig. 6 for a package that has the dimensions of 3 x 3 modules. Successfully reserved neighborhoods are shown for t=10 and t=11. Fig. 6. Neighborhoods during route reservation (based on [15]) Fig. 7. Deadlock situations that must not occur [4] D. Proof of Conﬂict Absence Conﬂicts include collisions, livelocks, starvation effects and deadlocks. We avoid livelocks by omitting the requesting module, when searching for a new optimal module. Starvation is avoided by partly basing the priority of requests on the creation time. In the following paragraphs, we will prove the absence of collisions and deadlocks. Seibold identiﬁed two possible deadlock situations that can occur in large-scaled modular conveying systems [4]: deadlocks caused by opposing routes and deadlocks caused by packages waiting in a loop (see Fig. 7). In both cases, the packages are deadlocked because the time window on the succeeding module overlaps with the time window of another package. Thus, deadlocks and collisions are avoided by guaranteeing that no time windows overlap. Since the arrival and departure times of packages on every module are solely determined by either accepting or denying REQUEST messages, we must only examine this phase. The following proof works for both small-scaled and large-scaled modules. In the case of large-scaled modules, only the sched- ule of the neighboring module must be checked for overlaps. In the case of small-scaled modules, an additional step is needed: When a module receives a REQUEST message, it must check the schedules of all modules within the neighborhood before either a REQUEST or a DENIAL can be sent (see also Section III-C). To keep this publication concise, we omit this additional step in the following paragraphs. We ﬁrst prove the absence of overlapping time windows for the case of opposing routes by proof of exhaustion. The following cases can occur: 1. Both entries are in the state requested: Both modules IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 8 send REQUEST messages to the other module. The requested time window will overlap on both modules with the already existing routing entries. Therefore both modules will compare the priority of the entry with the priority of the REQUEST message and delete the one with the lower priority. As a result, both modules will end up with only the entry for the package with the higher priority and thus no deadlock occurs. 2. One entry is in the state conﬁrmed, the other is in the state requested: Only the module with the requested entry sends a message. The module with the already conﬁrmed entry receives the REQUEST, but immediately sends back a DENIAL, because already conﬁrmed requests must not be deleted by a REQUEST message (even if it has a higher priority). Thus, no deadlock occurs. 3. Both entries are in the state conﬁrmed: This case cannot occur, and thus, no deadlock occurs. Prior to having conﬁrmed entries, every entry has to be in the requested state. If both neighboring modules were in the state requested at the same time, the rules for case 1 avoid the creation of two opposing entries with the state conﬁrmed. If one of the entries was in the state conﬁrmed and the other was in the state requested, the rules from case 2 avoid the creation of two opposing entries with the state conﬁrmed. In contrast to deadlocks caused by opposing routes, dead- locks in loops are caused by non-opposing routes. Once again, we will prove the absence of overlapping time windows by proof of exhaustion. In the following, we examine a module in a loop that receives a request from a module outside the loop. The module within the loop can be in two different states: 1. The entry of the receiving module is in the state conﬁrmed: The receiving module rejects the REQUEST and sends back a DENIAL with a new proposed time, and thus, no deadlock occurs. 2. The entry of the receiving module is in the state requested: The module that receives the request compares the priorities of the REQUEST message with the priority of the routing entry, deleting those with lower priority. Thus, no deadlock occurs. IV. A PPLICATION EXAMPLE In the following ﬁgures, the system behavior is shown for large-scaled modules. In every ﬁgure, the layout is shown on the top, and the schedules of the modules are shown on the bottom. No module has this complete overview of the system - every module can only access their own schedules. The layout consists of ﬁve modules. The unique identiﬁca- tion number (ID) of every module is in their top left corner. Two source modules exist in this layout: source I has the ID 2 and is at the left-most of the layout, and source II has the ID 5 and is at the bottom-most of the layout. There is only one destination module in the layout: it has the ID 1 and is at the top-most of the layout. Routing entries that are in the state requested are displayed as a single arrow on a conveyor. Routing entries in the state conﬁrmed are displayed with two arrows on the conveyor. Routing entries are assigned to their packages in two ways: the ﬁrst arrow originates at their respective package, and the arrows have the same color as the packages. Fig. 8. Application example at t=10 The schedules of all modules are depicted on the right side: the horizontal axis displays the time, while the schedules of the individual modules are arranged on the vertical axis. The states of the time windows are denoted by one of three possible letters: fmeaning the time window is not assigned to any routing entry, rmeaning the time window is assigned to a routing entry that is in the state requested and cmeaning the time windows is assigned to a routing entry that is in the state conﬁrmed. Every time window has two indexes: the lower index is used to denote the module ID, and the upper index is used to number the time windows. In this application example, the communication speed is unrealistically slow - sending a message from one module to another module takes one full second. We have chosen to use this slow communication speed in this example for two reasons. Firstly, the conveying speed and the communication speed are now within the same magnitude, which makes it possible to display both in the same ﬁgures. Secondly, we wanted to show that even when the communication speed becomes low, the algorithm still works. IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 9 Fig. 9. Application example at t=11 At t=10, package A has entered the system through source I, and its request has reached destination I, which sends back a CONFIRMATION message to module 4. At the same time, package B enters the system through source II. A REQUEST message for package B is sent to module 4. Package B has a higher priority than package A. At t=11, module 4 receives both the CONFIRMATION message and the REQUEST message. The REQUEST mes- sage is processed ﬁrst: since the requested arrival times for package A and package B overlap, the module compares the priorities, and subsequently, deletes the routing entry for package A before creating a new entry for package B. This causes the creation of the following three messages. Firstly, an OBSOLETE message is sent to module 1 to inform it that the already conﬁrmed routing entry for package A must be deleted. Secondly, a DENIAL message is sent to module 3 with a new proposed arrival time. Finally, a new REQUEST message for package B is sent to module 1. After processing the REQUEST message, the CONFIRMATION message is processed. Since the routing entry for package A no longer Fig. 10. Application example at t=12 exists, the CONFIRMATION message is discarded. At t=12, module 1 receives the OBSOLETE message for package A and the REQUEST message for package B. The reception of the OBSOLETE message causes the deletion of the previously conﬁrmed time window for package A. Caused by the reception of the REQUEST message, module 1 creates a routing entry for package A. This routing entry is in the state conﬁrmed, because the request has reached its destination. Subsequently, a CONFIRMATION message is sent back to module 4. At the same time, module 3 receives the DENIAL message from module 4, and subsequently, alters the time windows for the routing entry for package A. A new REQUEST message with an altered arrival time is sent to module 4. At t=13, module 4 receives two messages: the CONFIRMA- TION message for package B and the new REQUEST message for package A. Since the requested arrival time for package A does not overlap with the time window of package B, a routing entry for package A is created. Subsequently, a REQUEST message is sent to module 1. Next, the CONFIRMATON mes- IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 10 Fig. 11. Application example at t=13 sage is processed: the state for the routing entry for package B is set to conﬁrmed, and a CONFIRMATION message is sent to module 5. At t=14, module 1 receives a REQUEST message for package A: it checks its schedule and creates a routing entry for package A. This routing entry is in the state conﬁrmed, because the request has reached its destination. Subsequently, a CONFIRMATION message is sent back to module 4. At the same time, module 5 receives the CONFIRMATION message for package B. The state of the corresponding is altered to conﬁrmed and the reservation process for package B has successfully ended. The schedule of module 5 is no longer blocked indeﬁnitely by package B. To show the effects of a sub-optimal calculation of the TTL, the TTL is calculated conservatively in this example. Every source module calculates the TTL by adding 10 seconds to the creation time of a request. Because of this sub-optimal TTL calculation, package B has to wait for 6 more seconds after the CONFIRMATION message has reached source module 2 before the conveying can start. Fig. 12. Application example at t=14 V. C ONCLUSION AND OUTLOOK In this publication, we have presented an algorithm that can be used for both small-scaled and large-scaled modular conveyors. The algorithm fulﬁlls the ﬂexibility properties that have been deﬁned by Furmans et al. [1]. We have also proven the absence of any conﬂicts in our algorithm. Unlike all previously published algorithms for modular conveyors, physical lead time is used to select routes. Two important aspects of our algorithm still need to be investigated further: the ﬁrst aspect is determining the optimal operating parameters for different layouts, and the second is conducting a throughput analysis. Since both aspects are intertwined, the investigation of the optimal operating pa- rameters must be conducted ﬁrst. Two parameters must be investigated: ndenial as deﬁned in formula 2 and nsafe as deﬁned in formula 1. Both parameters can be determined by simulating different layouts. The following parameters will have the biggest inﬂuence on ndenial andnsafe: number of modules within the system, number of source modules, number of intersections, and package arrival rate at source IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 11 modules. After determining optimal operating parameters, a throughput analysis must be conducted. We are currently investigating both aspects and will publish the results at a later time. ACKNOWLEDGMENT This publication was done within the scope of the research project “Vernetzte, kognitive Produktionssysteme (netkoPs)”, which was funded by the German Federal Ministry of Ed- ucation and Research. The authors would like to thank the staff of the Logistics and Distribution Institute (LoDI) at the University of Louisville for their constructive comments on the manuscript.