Decentralized routing algorithm with physical time windows for modular conveyors

Sohrt, Simon; Overmeyer, Ludger Article Decentralized routing algorithm with physical time windows for modular conveyors Logistics Research Provided in Cooperation with: Bundesvereinigung Logistik (BVL) e.V., Bremen Suggested Citation: Sohrt, Simon; Overmeyer, Ludger (2020) : Decentralized routing algorithm with physical time windows for modular conveyors, Logistics Research, ISSN 1865-0368, Bundesvereinigung Logistik (BVL), Bremen, Vol. 13, Iss. 1, pp. 1-16, https://doi.org/10.23773/2020_8 This Version is available at: https://hdl.handle.net/10419/297184 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Received: 14 January 2020 / Accepted: 17 July 2020 / Published online: 25 August 2020 © The Author(s) 2020 This article is published with Open Access at www.bvl.de/lore DecentralizedRoutingAlgorithmwith PhysicalTime Windows forModularConveyors SimonSohrt, Ludger Overmeyer ABSTRACT We describe adecentralizedroutingalgorithm with physical timewindowsfor modularconveying systems. Existingroutingalgorithms for modular conveyors arealreadycapable of bi-directional conveyingwhileavoiding conflicts such as collisions, deadlocks,livelocksandstarvation effects. In addition to avoiding conflicts,routingalgorithms must also select routes that minimize thetransport time. No existingalgorithmfor modularconveyorsbases this decision on theexpected physical lead time, even though physical lead timedirectlyaffectsthe system throughput. In this publication, we present an algorithmthat uses thephysical lead time to select routes whileavoiding conflicts.Theavoidanceof conflicts is mathematically proven andthealgorithm’s computationalcomplexity is calculated. We presentthe system behavior of an exemplarylayout whichconsists of nine modularconveying modules that arecontrolled by ouralgorithm. With only nine modules, thepackage throughput is on thesame levelas thepackage throughputof conventional sortingsystems. Dueto its modulardesign,additional modulescanbe addedto further increase thethroughput,thus surpassing the throughputof conventional sortingsystems. KEYWORDS: Modularconveyors · Multi-agent system ·Decentralizedcontrol · Conflict-free · Bidirectionalrouting 1.INTRODUCTION Conventional material flowsystemsexcel at achieving ahigh packagethroughput, butlack flexibility.Once installedin awarehouse,changing their configuration is expensiveandimpractical. Dueto theincrease of mass-customizationande-commerce,material flow systemsmust become more flexible to ensure quick response times to fast changing demands [1, 2, 3]. Modularconveyingsystemsachieve high throughput whileallowing for fastandflexibleconfiguration changes. Thelayout canbe changedwithin minutes or at most afewhoursby adding more modules or by rearrangingexisting modules. Consequently, modularconveyingsystemscanautomate use-cases in warehouses that have been hard to automate with conventional systems. Automating theseuse-cases drivesdown costswhilesimultaneously increasing packagethroughput. Furmanset al.[3]identified design patterns of modularconveyingsystems. The modulesmust have wheels underneath so that they canbe quickly rearranged into a new layout. A decentralizedcontrolis needed to enablethe modulesto configure themselves by exchanging messageswith their neighboring modules. No manual configuration of thesystem is necessary.In addition to being movableandhaving adecentralizedcontrol, all conveyingsystemsmust avoidconflicts to ensure theconveyingof packages. The most critical conflicts are: 1. Collisions occurwhen twopackages collide with each other andinterlock. 2. Deadlocksoccurwhen at leasttwooccupied conveyors arecyclically waiting on each other to become available[4]. 3. Livelocks occurwhen apackageperforms the same cycleof movementsoverandoveragain [5]. 4. Starvation occurs when twopackages from differentdirections compete at an intersection forrightof way. If one directionhashigh LogisticsResearch (2020) 13:8 DOI_10.23773/2020_8 SimonSohrt CorrespondingAuthor E-Mail:[email protected] Ludger Overmeyer Instituteof TransportandAutomation Technology, LeibnizUniversity Hannover,Germany 2 Fig.1: Intersection consisting of four modularconveyors(based on [6]) 2. RELATEDRESEARCH In this Sectionwe will first present thestate-of-theartforlarge-scaled modules, followedby small-scaled modulesand at last automatedguided vehicles. We divide modularconveyingsystemsinto two classesbased on their size in relation to thepackage size.If thelargestpackageof apackagespectrum is smallerthan asingle module,the modulesarelargescaledin relationto thepackage size.Subsequently, if even thesmallest packageof apackagespectrum is larger than a single module,the modules aresmallscaledin relation to thepackagesize.Themajority of packages in atypicalwarehouse have awidthbetween 100mm and600mm and a length between 200mm and1000 mm [7]. Accordingly, in atypical warehouse, modulesmust be at leastsmallerthan 100mm × 200mm to be considered small-scale. We will only consider algorithms that canpotentially fulfill ourrequirements,whichare: conflict-free,work foranybi-directional conveyorlayout,andselect routes basedontheexpected travel time. We usea classificationto filter outall algorithms that do not fulfill ourrequirements.Differentclassifications are available(see [8,9, 10]),but in thispublication, we usethe classificationby Seibold [6]. Onlyalgorithms from Seibold’sclassof “Time-window basedRoute Reservation” areable to fulfill allourrequirements. Algorithms from this classreserveroutes,from source modulesto destination modules,forindividual packages.Every module keeps a schedule,which areused to reservetimewindowsfortheindividual packages.Even though we will notconsider algorithms from other classes, we stillwant to mentionthe algorithms for modularconveyingsystemsby Gueet al.[11, 2],by Mayeret al.[4,12]andby Krühnet al. [13, 1]. throughput andis always prioritized,the packages from theother directionwill never getcloserto their destination[6]. Conflict-avoidanceis handledby routingalgorithms. The need forroutingalgorithms is depictedin Fig. 1. In thisexample, four modularconveyors form an intersection. Theintersectionis surrounded by source anddestination modulesthrough whichpackages may enter andleave. In this example, theconveyingof packages I, II,andIII hasalreadybegun, whilepackage IV just enteredthesystem.Theshortestpath for every packageis depicted by arrows. If packageIV enters theintersectionimmediatelyandfollows theshortest path, a conflictoccurs (either a collision or a deadlock). Several routingalgorithms have been developed that prevent conflicts as describedin Section2. In addition to avoiding conflicts,routingalgorithms must also select routes that positively affect the throughput. Existing routingalgorithms have used different methodsof selectingroutes,but no algorithm hasselected routes basedontheexpected travel time. In this paper,we propose a novelroutingalgorithm that selectsroutes based on theexpected travel time by utilizingphysical time windows. Since thethroughput is aresult of thetravel time, thethroughput is optimized by basing theselectionof routes on theexpected travel times. Ourproposedroutingalgorithmis designed fordecentralizedcontrolled modularconveyors. Everyconveyor has a schedule and a clockwhichis synchronized through the network. Thesynchronized clocks are necessary to reserve physical time windows on theschedules. Theconveyorsreserveroutes by exchanging messages: When aconveyor receives a request, it checks itsschedule. If therequestcanbe accepted,it sends arequestto the next conveyor. If the request cannot be accepted, a new time is proposedto therequesting conveyor. This paper is organizedas follows. In Section2, we present state-of-the-art routingalgorithms for modular conveyingsystemsandforautomatedguided vehicles (AGV). The modularconveyors aredevidedinto largescaledandsmall-scaled modules. We chose to include AGVroutingalgorithms becausethey canbe modified to work in modularconveyors. Before describing theroutingalgorithm, we present ourpreliminary considerations regardingthesynchronizationof theconveyors’ clocks in Section3. In Section4, we describe ouralgorithmforlarge-scaled modules. Based on thealgorithmforlarge-scaled modules, we presenta modifiedalgorithmforsmall-scaled modulesin Section 5. Thecharacteristics of both algorithms areanalyzed in Section6. We give an applicationexamplein Section7. Thesystem behavior of aconveyingsystem controlled by ouralgorithmis presented in Section8. Finally, we present ourconclusion andoutlook in Section9. 3 DecentralizedRoutingAlgorithmwithPhysicalTime WindowsforModularConveyors Fig.3: ThenetkoPssystem is made up of several small-scaled conveyingmodules(based on [18]) 2.2. Small-ScaledModules An exampledepicting aconveying system that is made up of small-scaled modulesis shown in Fig. 3 – the netkoPssystem.Theprototypes of the netkoPs modules aredescribedin greaterdetail in [18, 19,20]. The netkoPs modules arebasedon thecogniLog modules that have been describedin [1, 13,7].We have chosen the netkoPs modules as ourexamplesystem becauseit is well documented by scientificpublications. Every netkoPs module has a sensor to detect packages,canconvey in anydirection, andhasitsown dedicatedcontrol. Thefootprintof a moduleis 60 mm ×60 mm.These modules canonly communicate with their four direct neighbors andcanbe freely arranged into theslotsof amatrix mounting.Prototypes of matrix mountingswith differentdimensions have been manufactured,andslotscanbe left unoccupied. Everymatrix mounting haswheels underneath and canbe freely positioned within awarehouse.Other examples of small-scaled conveyor systemsinclude theCelluveyor from Uriarteet al.[21, 22,23]andthe “Magic Carpet System”presented by Itoh DenkiLtd. [24]. None of thepublishedcontrolalgorithms forsmallscaled modules belong to theclassof “Time-windows basedRouteReservation”,andtherefore, are not presented.An importantcontribution wasmade by Krühnby introducingtheconceptof “module neighborhoods” forcontrollingsmall-scaled modules [13, 1].By utilizingthe“module neighborhoods” conceptKrühnwasable to modify an controlalgorithm originally designed forlarge-scaled modulesto work on small-scaled modules. 2.3. Automated Guided Vehicles Both thehardwareandthealgorithms forautomated guided vehicles (AGV)aremuch moreadvanced than their modularcounterparts. Thefollowingoverview publications describe state-of-the-art AGVrouting algorithms:[9,10,25,8].As with themodularconveying Fig. 2: TheGridSorter system ismade up of several large-scaled conveyingmodules[6] 2.1. Large-ScaledModules An examplefor a conveyingsystem that is made up of large-scaled modulesis shown in Fig. 2–theGridSorter system.Theprototypes of theGridSorter moduleshave been describedin [4]and [6]andarenow manufactured by flexlog GmbH [14].Thefootprintof aGridSorter module is 500mm × 500mm allowing packages to be conveyed into allfourcardinal directions.Every module hasfour sensors at thesidesto detectincoming packages and a dedicated control. Communication is only possible with itsfour direct neighbors.All moduleshave wheels underneath andfour standardized connections on everyside, whichareused to transmit informationandpowerfrom one module to another. Dueto thewheels andthestandardized connections, themodulescanbe rearranged into a new layout within minutes.If multiple modulesarecombined to form a layout, no single controlhasan overview of thewhole system.Instead, the modulesexchange messages anddecide theconveyingof packages on their own. Thus,the modulesaresoftware-agents as defined by Franklin andGraesser[15]with decentralizedand distributedcontrols.Large-scaled moduleshave also been manufactured by other companies. Twoexample systemsaretheXPlanarsystem [16] andtheMotion Cube system [17],but no controlalgorithms have been publishedforthesesystems. Seibolddescribed a routingalgorithm[6]that belongsto theclassof “Time-window-basedRoute Reservation”.This algorithmis conflict-free andworks foranybi-directional layout, selectingroutes based on theexpected logical lead time. Onedownsideof utilizinglogical time is that it does notprogress unless apackageis conveyed from one module to thenext. Theroutewith theshortestlogicallead time is not necessarily theroutewith theshortestphysical lead time. 4 Is it possible to create adecentralizedrouting algorithmthat selectsroutes basedonthephysical lead time in anybidirectional layout whileavoiding conflicts?We will tackle thisquestion by utilizing physical time windows. 3PRELIMINARYCONSIDERATION: CLOCKSYNCHRONIZATION Sincewe want to reserveroutes withphysicaltime windows, we must first make sure that theclocks of all conveyors aresynchronized.Theclocks must notbe synchronized perfectly, but thetiming differencesof neighboringconveyors must be smallenough that the conveyingprocessis notaffected in a meaningful way. Thesynchronizationof clocks is awell-researched field [31],andmany cheaptechnical solutionsexist. We wouldlike to pointout thePrecisionTime Protocol (PTP), whichwasdefined in theIEEE 1588-2008 standard [32].PTPwasdesigned forlocalsystems requiring high accuracy that cannot bear thecost of a GPS receiver at each node, or forwhichGPS signals areinaccessible [33].It canbe used within astandard ethernet-network andis therefore cost-effective.The accuracy of PTPtimesignals is in thesub-microsecond rangewhichis sufficientaccurate fortheconveyingof packages whichrarely exceeds10 m/s. systems, we will only focus on algorithms from the classof “Time-window-based Route Reservation.” Most algorithms from thisclassarebasedon the algorithmdescribedby KimandTanchoco [26]. This algorithmis conflict-free,worksforanybi-directional layout, andselectsroutes basedon thephysical travel time. Unfortunately, allroutes aresequentially planned by acentralcontrolthat has a complete overviewof the system.After aroutehasbeen planned, it is uploaded to therespective AGV. KimandTanchoco even explicitly stated that thealgorithmcannot be used in a decentralizedcontrolled system:“Parallelexecutionof therouteing algorithmmayresult in conflicting travel schedules or gridlocks in abidirectional network.”[26] We want to highlight twopublications regarding KimandTanchoco’s algorithm. The originalalgorithm neglected theproblemof unexpected delays that can occur in real-worldsystems, during transport execution. Maza andCastagna [27] presented a modificationthat preventsconflicts even when the previouslyreserved time windowsaremissed. This is accomplished by monitoring intersections: If apackagemisses itstime window on theintersection, no other AGVmust enter theintersectionuntilthedelayedAGVhaspassed the intersection. Möhringet al.[28] testedthepracticality of the algorithmforreal-world use-cases.Their algorithmis implementedto routevehicles at a Container Terminal in theHamburg Harbor. Beforehand,they simulated different scenarioswith up to 48 vehicles on a computer with an AMD-Athlon 2100+(1,7 GHz) processorand 512MB RAM. Even forworst-case scenarios (new routes must be calculated forallvehicles at thesame time),thecomputationtook less than half asecond. We believe that these fast computationtimes arethe reason whyKimandTanchoco’s algorithm was never modifiedextensively. It is already efficient enough for real-worlduse-cases even in itsbasic form. Before we conclude therelated research section, we want to mentiontheKARISvehicles [29, 30]. The vehicles cannot only individually transport single items, but arealso able to form twodifferentfunctional clusters. As adiscontinuouscluster,KARISvehicles connectto each other to transport itemsthat arelarger than asingle module. As acontinuous cluster, several KARISvehicles form aconveyor line to realizehigh throughput of goods. To ourknowledge, no detailed routingalgorithms forKARIS vehicleshave been published. To summarize, we identifiedtwoalgorithms that areconflict-free andwork in anybi-directional layout – Seibold’s algorithmandKimandTanchoco’s algorithm. Seibold’s algorithmis decentralized, but routes areselected by usinglogicallead time and not physical lead time. KimandTanchoco’s algorithm, and itsmodifications,usephysical lead timeto select routes but aredesigned for a centrallycontrolled system. As aresult of ourliterature review, we identifiedthe following research question: Algorithm1: ProcessMessages Input: Receivedmessages Result: Sent messages, modified schedule 1delete routing entries with expired TTL; 2if source module then 3StartNewRoute; 4foreach unprocessed OBSOLETE message do 5delete affected entry from schedule; 6send OBSOLETE to succeeding module; 7foreach unprocessed DENIAL message do 8modify affected entry according to DENIAL; 9delete affected entry from schedule; 10 InsertIntoSchedule(modifiedentry); 11 foreach unprocessed REQUEST message do 12 create newentry according to REQUEST; 13 InsertIntoSchedule(newentry); 14 foreach unprocessed CONFIRMATION message do 15 mark the affected entry as confirmed; 16 if CONFIRMATION reaches source module then 17 if iteration counter >maximum iteration then 18 send RESERVE-UNLOCK with local package ID; 19 set iteration counter to 0; 20 else 21 send CONFIRMATION to preceding module; 5 DecentralizedRoutingAlgorithmwithPhysicalTime WindowsforModularConveyors Thepresented algorithmignores theeffectsof acceleration,deceleration, andslippagethat occurin real-world conveyingsystems. Allthreeeffectscan be accounted forby adding asafety allowanceto the timewindows. In thefollowing paragraphs,we will not explicitly mentionthis safety allowanceforthesake of simplicity. Before routereservations canbe created, the modules must be initialized. During this initialization, every module generates a routingtableby communicating with itsdirect neighbors.Hereupon,thisinformationis propagatedthroughthesystem.This process is similar to creating metric tables in computer networks using thedistance-vectorroutingprotocol[34].For every destination, the modulesdeterminetheID of the neighboring module that is closestto this destination, thedistance to thedestination, andthenumber of intersections between thesource module andthe destination. Routingentriesstore thefollowing data:unique requestID,physical timewindow (arrival timeand departuretime), priority,time-to-live (TTL), ID of the preceding module,ID of thesucceeding module,and state (the twostates are “requested” and“confirmed”). Theunique requestID,thepriority andthe TTLareset by thesource module at thecreation of therequestand arenotaltered by theother modulesalongtheroute. Modern warehouseshave alreadyassigned aunique ID to everypackage, whichthesource modulesreuse. If an external process does notset apriority, thesource module generates a priority instead. This generated priority is basedon thetimestamp at which thepackagewas first introduced to thesource module. Routingentrieswith earliertimestamps have ahigher priority than entries with later timestamps.Basing the priority on theintroductory timehastheadvantage that starvation effectsareavoided. We describe the avoidance of starvation effectsin more detailin Section 4.2. TheTTLis the maximumtimearoutingrequest may“live” before it is discarded and a new request is createdby thesource.Consequently, every module periodically checks theTTLforroutingentriesand deletes expiredones.Theintroduction of TTLwas necessary to take into accounttheuncertaintyof a decentralizedcontrolled system with physical time windows. Since no module hasacomplete overview of thesystem,thesource module can onlyestimate howlong theroutereservationprocesstakes. We will present howtheTTLis estimatedin Section4.3, after we overview thealgorithm. Modulescansend thefollowingsix message types whichmust be processed in thefollowing sequence:OBSOLETE, DENIAL,REQUEST, CONFIRMATION,RESERVE-LOCK,RESERVEUNLOCK.Theprocessing of messages in this sequence positively affectsthethroughput.Both OBSOLETE andDENIAL messages delete routingentries on the schedule. By processing them first,theschedule opens 4ALGORITHM FOR LARGE-SCALED MODULES As previously mentioned in Section3, we assume that theclocks of everymodule aresufficiently synchronized.Themain algorithmis described in pseudocodein Alg. 1, anditstwosubroutines are describedin Alg. 2andAlg. 3. Forfurther clarification an applicationexampleis givenin Section7. 4.1Overview of theAlgorithm Ashort overviewof thealgorithm: The modules reserve aroutefrom source to destinationby exchanging messages.Every module along a routestores arouting entry on itsschedule. Routingentriesinclude an arrival and a departuretime. Everyroutereservationhastwo phases:therequestphaseandtheconfirmationphase. In therequestphasetherouteis planned from source to destination. During this phase, the moduleshave to select apath,andthey have to negotiate thearrival andthedeparturetimes. After therequesthasreached thedestinationmodule,theroute is confirmed from destinationto source. Algorithm2: StartNewRoute Input: Receivedmessages Result: Sent messages, modified schedule 1foreach unprocessed RESERVE-LOCK do 2add to list of receivedlocks; 3foreach unprocessed RESERVE-UNLOCK do 4remove from list of receivedlocks; 5if local package without routing entry then 6if priority of local package higher than priority of received locks then 7if iteration counter >maximum iteration then 8send RESERVE-LOCK with package ID and priority; 9create routing entry for local package; 10 calculate TTL for newly created routing entry; 11 InsertIntoSchedule(newly created entry); Algorithm3: InsertIntoSchedule Input: Routing entry Result: Sent messages, modified schedule 1filter out all requested entries with alower priority; 2insert routing entry into filtered schedule; 3if insertion successful then 4if REQUEST reached destination then 5send CONFIRMATION to predecessor; 6else 7send REQUEST to neighbor with shortest lead time; 8foreach overwritten entry do 9send DENIAL to the precedingmodule; 10 send OBSOLETE to the succeedingmodule; 11 else 12 send DENIAL to preceding module; 6 occurandtherefore thethroughput will be notaffected at allin most conveyingsystems. In Section8we analyzethesystem behaviorof asimulated conveying system controlled by ouralgorithm. No RESERVELOCK message wassent. If thesource module is notlocked,it estimates the TTLandthedesiredarrivaltime, andsubsequently, sends a REQUEST messageto the neighboring module with theshortestlead time. EveryREQUEST messageincludes a unique requestID,thepriority,the destinationID,thedesiredarrivaltime, andtheTTL. This desired arrival time of theREQUESTmust be far enough into thefuture that theroutereservationprocess is most likelycompletedby then.Thecompletion time depends on thenumber of modulesbetween thesource andthedestinationandthenumber of overlapsthat will likelyoccur, which need to be resolved.Since the source has no complete system overview, it canonly estimate thenumber of overlaps. Becausethenumber of overlaps canonly be estimated, thearrivaltime can only be estimated. If more overlapsoccurthan estimated,the CONFIRMATION message will reachthesource after theestimatedarrivaltime andit wouldbecome physically impossible forthepackageto arrive at the estimatedarrivaltime. Because thefirst time window is missed,allsubsequent time windowsmay alsobe missed. A mismatch wouldhave occurred between theprojected movement of thepackageandtheactual movement.As already mentioned in Section2.3 Maza andCastagna [27] have proven that even when amismatch occurs,conflicts can stillbe avoidedby followingthesequence of thepreviously negotiated time windows. Even though no conflictoccursdueto themismatch, it is stilladvantageous to avoidsuch amismatch becausetheselectionof routes depends on accurate schedules. Theselectionof routes is basedonthelead time, whichitself,is basedon theprojected movement. If themismatch becomes toobig, sub-optimal routes mightbe chosen. To avoid a mismatch betweenprojected movement andactual movement,we introducetheconceptof TTL. Before asource sends thefirst REQUEST message, it estimates howlong theroutereservationwill most likelytake. A safetymargin is addedto increase the chance of completing theroutereservationwithin the TTL. If theTTLis estimated tooconservatively andthe routereservationis confirmed faster than estimated, thepackagecannotstartearlier, as this wouldalso causeamismatch between projected movement and actual movement.Therefore, thepackagehasto wait andthethroughput is negatively affected.If the estimate is toooptimisticandtheroutereservationis notconfirmed within theTTL, the source module has to start a new iteration attempt. Sincethepackage has to wait untilthis new iteration attemptis completed, thethroughput is once again negatively affected.In up. Then,theREQUESTandCONFIRMATION messagesareprocessed,whicheither create or change thestate of routingentries. By processing the REQUEST andCONFIRMATION messageslast, previouslyunavailabletime windowscanbe reserved andthechance of reserving a well-fittingtime window is increased, positively affectingthethroughput.The LOCK-RESERVEandtheUNLOCK-RESERVE messagesare only sent andprocessed by thesource modules. Their meaning will be explained when describing theinitial creation of aREQUEST message at a source module in the next Section. 4.2Initial Creationof aREQUESTMessageat aSource When apackageenters theconveyingsystem on a source module,theschedule ofthissource module becomes blockedindefinitely untiltheroutereservation is confirmed.Dueto thedecentralizednature of the system,thesource modulesare not synchronized. Caused by this lack of synchronization, it is possible, yetvery unlikely, that a source module may never finish a routereservationandstarves. An example: The module mnsends aREQUEST to itsoptimal neighbor mn+1.Since mn+1 hasalready a confirmed routingentry at therequestedtime, a DENIAL is sent back to mn. mnmust now alter thetimewindow of thecorresponding entry. This altered time window now overlaps with a confirmed routingentry. Consequently,mnmust send a DENIAL back to itspreceding module mn−1.This chain of events mayrepeatitself,untiltheTTLexpires. Since thereis no mechanism foravoiding thesame chainof events in the next iteration attempt, thesource module starves. To prevent this starvation, a synchronization lock is introduced:Everysource module keepstrack of thenumber of failed reservation attempts. If a user-specifiedmaximumnumber of iteration attempts is exceeded,thesource module sends aRESERVELOCK to allother source modules. This RESERVELOCK includesthepackageID andthepriority of the package. Allsource moduleskeep alist of thereceived RESERVE-LOCKS. Source modules only startnew route reservations,if thelocalpackagehas a higher priority than allof their received RESERVE-LOCKS. Thealgorithmforstarting a new route is shown in Alg. 2. When amatching CONFIRMATION message reaches asource module,theiterationcounter for thenumber of failed attempts is reset back to 0. If thesource module haspreviouslysent aRESERVELOCK, a RESERVE-UNLOCK is sent. Dueto theintroduction of synchronizationlocks, the conveyingsystem maytemporally become centrally controlled,because everysource module mayhave to wait on a single source module to finishitsreservation process.Since everysource module hasto wait,the throughput of theconveyingsystem is negatively affected. However, the circumstances underwhich asynchronizationlock areused arevery unlikelyto 7 DecentralizedRoutingAlgorithmwithPhysicalTime WindowsforModularConveyors 4.4 Selectingaroute Routes areselected basedon thephysical lead time. Thephysical lead time is thesumof thebase lead timeandtemporaryincreasescaused by previously received DENIAL messages. Thebase lead time for every neighboring module is computed by dividingthe destination’sdistance (which wasdetermined during theinitialization phase) by theuniform conveying speed of the modules. EveryDENIAL message includes a proposed time, when thesending module is readyto accept apackage. This proposedtime causes atemporaryincrease of thelead time. Modulesalways send REQUESTS to the neighboring module with the lowest lead time. Dueto temporary lead time increases, theREQUESTS are not necessarily sent alongthe shortestpath.Livelocksareavoidedby never choosing theprecedingmodule, even if it hasthelowest lead time. 4.5Processing Messages When a module receives aREQUEST message,it creates a routingentrywith therequested arrival time. Next,allpreviously createdrequests with a lowerpriority arefilteredout from theschedule. The module then attempts to addthe newly createdentry to thefiltered schedule withoutcreating overlaps. Testingforoverlapsis done by usingthealgorithm describedin [35].If the newlycreatedentrycannot be inserted into theschedule, a DENIAL is sent back to thepreceding module that includesthe next available arrivaltime. If the newly created entryis successfully inserted into theschedule andreacheditsdestination, aCONFIRMATION is sent back to thepreceding module. If the newly createdentryis successfully inserted,butdidnotreachitsdestination, aREQUEST is sent to the neighboring module with theshortest lead time. Livelocks areprevented by excludingthe possibilityof sending a REQUEST message to the predecessor. For everyentrythat hasbeen overwritten by the newly createdroutingentry, aDENIAL message is sent to itspreceding module andan OBSOLETE message is sentto itssucceedingmodule. Thealgorithmfor insertinginto theschedule is shownin Alg. 3. When amodule receives aCONFIRMATION message, it changesthestate of thecorresponding routing entryto thestate confirmed andsends a CONFIRMATION message to itspreceding module. When aCONFIRMATION message reaches thesource module,theactual conveyingof thepackagecanstart. Thesource module alsosends aRESERVE-UNLOCK, if it haspreviously sent aRESERVE-LOCK.The iterationcounterforthenumber that tracks thenumber of failed attempts is reset back to 0. ADENIAL message includes theunique request ID andtheproposed time. When aDENIAL message is received,thereceivingmodule first deletesthe correspondingentryfrom itsschedule. A new entryis created with a modifieddeparturetime. This modified the next paragraphs,we presentourapproaches for estimating theTTL. 4.3EstimatingtheTTL We developed two methodsforestimating theTTL. The first method basestheestimate mainly on theaverage time previous routereservations took before they were confirmed andis depictedin Eq.1. Consequently, every source must store theaveragetimeof allpreviously confirmed routereservations for everydestination. The averagetime of previousroutereservations is thefirst termin theequation andis written as t ˉ dest.Since route reservations whichwere not confirmed within theTTL, increase thevalueof t ˉ dest,this estimation method is self-correcting. Thesecond termnsafe ·itakesinto accountthat the number of packages within thesystem canrandomly peak.This packagepeakincreasesthechance of routes conflicting with each other. Dueto conflicting routes, routereservations take longer than average, since conflictavoidancerequires thesendingof additional messages.To avoid a source from starving, every source increasesan iterationcounteriby 1for every failed attempt. This iterationcounter starts at 1 for every newly started requestandis reset back to 1 once thereservationhasbeen successfully completed. i is then multiplied with thesafety factor nsafe.While testing on differentlayouts, we achieved satisfactory throughputs by picking a valuein therangefrom 1 to 2fornsafe.In Section8.2we present theresulting conveyingtimes fornsafe = 1 foran exemplarylayout. Theformulain itsentirety is as follows: (1) If thelayout of theconveyingsystem changes, all previouslycalculated averages become invalid. Since packages still need to be conveyed during this startup phase,asecond method forestimating theTTLis needed: (2) wherendest is thenumber of modulesbetween source anddestinationandtcom is thetime for one module to receiveandprocess a messagefrom a neighboring module.Thefactor 2is needed becauseall modules along a routehave to receiveandprocess at leasttwo messages –the REQUEST messageandsubsequently the CONFIRMATION message.iis once again the iterationcounter that starts at 1 andis increasedby 1untiltheroutereservationhasbeen successfully confirmed.After completingtheroutereservation, i is resetted.Thesystem switches from TTLsto TTLmas soon as t ˉ dest canbe computed. TTLm(tdest ,i)=t dest +nsa fe·i TTLs(ndest ,i)=2·t com ·ndest ·i 8 After receivingtheSCHEDULE-ACKNOWLEDGE message, themaster module sends aREQUEST to the optimal neighbor. Asuccessfulinsertionis depicted in Fig. 4for a packagethat hasthedimensions of 3 × 3 modules. Thereserved neighborhoodsareshown for t = 10 ms and t = 11 ms. When aroutingentryis deleted on aslave moduleby aREQUEST with ahigher priority,theslave modules informsthemaster module by sending a SCHEDULE message.Themaster module then sends aDENIAL messageto allother slave modules in theneighborhood andan OBSOLETE messageto itssucceedingmaster module and a DENIAL messageto itspreceding module. Fig.4: Neighborhoods duringroutereservation (based on [13]) Fig.5: Deadlock situations that must notoccur[6] 6CHARACTERISTICSOF THE ALGORITHMS In this Sectionwe provetheabsence of conflicts andcalculate thecomputationalcomplexity of the algorithms. 6.1Proofof ConflictAbsence Conflicts include collisions, livelocks, starvation effectsanddeadlocks.We avoidlivelocksby omitting therequesting module,when searchingfor a new optimal module. Starvation at sourcesis avoidedby usingREVERSE-LOCK messages. In thefollowing paragraphs,we will prove theabsenceof collisions and deadlocks. entryis then addedto theschedule usingthealgorithm describedin Alg. 3. 5MODIFIED ALGORITHM FOR SMALLSCALED MODULES Thealgorithmis modifiedforsmall-scaled modules by introducingtheconceptof module neighborhoods describedby Krühnin [13].Every messagemust be extended to include thepackagedimensions,which is used to determine thesize of the neighborhood. Neighborhoodsaremade up of one master module andseveralslave modules. Routingentriesmust be extendedby includingtheID of the module which created theentry(the module itself or a remote master module). Furthermore, threemore messagesmust be introduced:SCHEDULE-REQUEST,SCHEDULE, andSCHEDULE-ACKNOWLEDGE.To keep this paper concise,we will only demonstrate theusageof thesethree new messages when amaster module must process a REQUEST message. If asmall-scaled module receives a REQUEST messagefrom a precedingmaster module,it becomes themaster module for a new neighborhood. The master module now sends aSCHEDULE-REQUEST message to allslave modules. TheSCHEDULEREQUEST message consists of theID of themaster module,thepriority of theREQUEST message,and thepackageID.All moduleskeep alist of allreceived SCHEDULE-REQUEST messages.The modules always processtheSCHEDULE-REQUEST message with thehighestpriority first.Processing is doneby sendingtheir ownschedule to themaster module via a SCHEDULE message. Afterreceivingtheschedulesof all modules within the neighborhood,themaster module attempts to insert the newlycreatedroutingentryinto allschedules. If theinsertion failson only one schedule,themaster module sendsthe unmodifiedschedulesback to the slavemodulesviaSCHEDULE messagesandsends aDENIAL messageto thepreceding master module. If theinsertionis successful, themaster module sends back the modifiedschedulesto allslave modules. When theslave modulesreceivethe modifiedschedule they first check, if their scheduleshave been altered in the meantime by either themselves or another master module. If this is thecase,they re-sendtheir schedule via a SCHEDULE message to themaster module. The master module must now tryonce again to insert the newlycreatedroutingentryinto allschedules. If the scheduleshave not been changed, theslavemodules send back aSCHEDULE-ACKNOWLEDGE message to themaster module,indicating that they have accepted the modificationof their schedule. After the SCHEDULE-ACKNOWLEDGE messagehasbeen sent,thecorrespondingSCHEDULE-REQUEST messageis removedfrom theSCHEDULE-REQUEST list of theslave module. 15 DecentralizedRoutingAlgorithmwithPhysicalTime WindowsforModularConveyors 21.C. Uriarte, A.-K. Rohde, andS. Kunaschk, “Celluveyor – Einhochflexibles und modulares FörderundPositioniersystem aufBasis omnidirektionalerAntriebstechnik,” 18. MagdeburgerLogistiktage –Sichere und nachhaltige Logistik,2013.[Online].Available: https://www.iff.fraunhofer.de/content/dam/iff/de/ dokumente/publikationen/iff-wissenschaftstage2013-logistik-tagungsband-fraunhofer-iff. pdf 22.C. Uriarte, H. Thamer,andM.Freitag, “Fördertechnik ausderZelle,” Hebezeuge und Fördermittel 10,2015.[Online].Available: https://www.technische-logistik.net/sites/default/ files/Fachartikel/HF1015Thamer 0.pdf 23. H. Thamer,C. Uriarte, andA. Y. Benggolo, “IntelligenteFörderzelle: Start-up ausBremen entwickelt flexibelnutzbare undraumsparende Module,” Hebezeuge und Fördermittel,Vol. 1-2, No.ISSN:0017-9442, pp.56–59, 2018. 24. Itoh DenkiLtd.,“Nouveau: MCSUnit, Sorter Module Multidirectional andMulti-Format,” 2017. [Online].Available: http://www.itoh-denki. com/en/les-modules-2/mcs 25.K. C. T. Vivaldini,L. F. Rocha, M. Becker,and A. P. Moreira, “ComprehensiveReview of the Dispatching, Scheduling andRoutingof AGVs,” A.P. Moreiraet al. (eds.),CONTROLO’2014 –Proc. of the11th Port. Conf. on Autom. Control, 2015.[Online].Available: https://doi. org/10.1007/978-3-319-10380-8 48 26. C. W. KimandJ. M. A. Tanchoco,“Conflict-free shortest-time bidirectional AGVrouteing,” The InternationalJournalofProduction Research, Vol. 29,No.12,pp.2377–2391, 1991. 27.S. Maza,P. Castagna,andIEEE, “Conflictfree AGVroutingin bidirectional network,” in ETFA 2001:8THIEEE INTERNATIONAL CONFERENCE ON EMERGING TECHNOLOGIES ANDFACTORYAUTOMATION,VOL 2, PROCEEDINGS,2001,pp.761–764. 28. R. H. Möhring, E. Köhler,E. Gawrilow,andB. Stenzel, “Conflict-freeReal-timeAGVRouting,” Operations Research Proceedings 2004,Vol. 2004,2005.[Online].Available: https://link. springer.com/chapter/10.1007/3-540-27679-3 3 29.T. Stoll, “Dezentral gesteuerter Aufbau vonStetigförderernmittelsautonomer Materialflusselemente,” Dissertation, Institut für FördertechnikundLogistiksysteme, Karlsruhe, 02.05.2012.[Online].Available: http://dx.doi. org/10.5445/KSP/1000028697 30.Institut fürFördertechnikundLogistiksysteme, “KARIS PRO – AutonomerMaterialtransport fürflexibleIntralogistik,” Karlsruhe. [Online]. Available: http://karispro.de/Abschlussbericht% 20KARIS%20PRO.pdf 31.A. S. Tanenbaumand M. vanSteen,Distributed systems: Principlesandparadigms, 2nd ed. Leiden:Maarten vanSteen,2016. European JournalofOperational Research,Vol. 171, No.1, pp.1–23,2006.[Online].Available: https://ssrn.com/abstract=594969 10.L. Qiu, W.-J.Hsu,S.-Y.Huang, andH. Wang, “Schedulingandroutingalgorithms forAGVs asurvey,” Internationaljournal of production research: American Institute of Industrial Engineers; Society of ManufacturingEngineers, Vol. 40,No.3, pp.745–760, 2002. 11.O. Uludağ, “GridPick: AHigh DensityPuzzle BasedOrderPickingSystem with Decentralized Control,”Dissertation, Auburn University, Auburn,Alabama,USA,2014.[Online].Available: https://etd.auburn.edu/handle/10415/3984 12.S. MayerandK. Furmans, “Deadlockprevention in acompletely decentralizedcontrolled materials flowsystems,”LogisticsResearch,Vol. 2, No. 3-4, pp.147–158, 2010. 13.T. Krühn, “Dezentrale, verteilteSteuerung flächiger Fördersystemefürdeninnerbetrieblichen Materialfluss,”Dissertation, Leibniz UniversitätHannover,Hannover,16.04.2015. [Online].Available: http://www.tewiss-verlag.de/ katalog/details/ ?isbn=978-3-95900-014-7 14.flexlog GmbH,“Dezentral steuerbar – Modulbaukasten mitFlexTechnology,”2019. [Online].Available: www.flexlog.de/ 15.S. Franklin andA. Graesser,“IsIt an agent, or just a program?: A taxonomyforautonomous agents,” in Intelligent Agents III AgentTheories, Architectures,andLanguages,J. P. Müller, M. J. Wooldridge, andN. R. Jennings,Eds. Berlin, Heidelberg:Springer Berlin Heidelberg,1997,pp. 21–35. 16.Beckhoff Automation GmbH &Co.KG,“Flying Motion: XPlanar,”2019.[Online].Available: https://www.beckhoff.de/xplanar/ 17. WEKA BUSINESS MEDIEN GmbH,“Festo – Palettiersystem Motion Cube,” 2017. [Online]. Available: https://www.handling.de/video---festo ---palettiersystem-motion-cube.htm 18.L. Overmeyerand H. Stichweh, Vernetzte, kognitiveProduktionssysteme:Abschlussbericht, ser. Berichte desTEWISS Verlags.Garbsen: TEWISS –TechnikundWissen GmbH, 12.12.2017. 19. H. Stichweh, M. Theßeling, S. Sohrt, A. Heinke, andL. Overmeyer, “Intelligent routen,fördern undverteilen: DieConveyor Matrixfürdie kognitiveProduktion derZukunft.”25.Deutscher Materialfluss-Kongress mit VDI-Konferenz Routenzugsysteme,TU München, Garching,17. und 18.März 2016,pp.127–142, 2016. 20.S. Sohrt, N. Shchekutin,andL. Overmeyer, “Steuerung vonkleinskaligenFördermodulen,” LogisticsJournalProceedings,Vol. 2016,No.10, 2016.[Online].Available: http://nbn-resolving. de/urn:nbn:de:0009-14-44516 16 36.S. Luke,C. Cioffi, L. Panait,K. Sullivan,and G. Balan, “MASON: A Multiagent Simulation Environment,”Simulation,Vol. 81,No.7, pp.517– 527, 2005.[Online].Available: https://journals. sagepub.com/doi/10.1177/0037549705058073 37.Gebhardt Intralogistics Group, “GEBHARDT GridSorter –ModularerPlug&Play Sorter für dieIntralogistik–FitfürIndustrie4.0,” 16.05.2014.[Online].Available: https://youtu.be/- -oA-V6emRI 38.D. Jodinand M. ten Hompel,Sortierund Verteilsysteme:Grundlagen,Aufbau,Berechnung und Realisierung, 2nd ed., ser. VDI-Buch.Berlin: Springer Vieweg, 2012. 32.IEEE, “IEEE Standardfor a PrecisionClock SynchronizationProtocol forNetworked MeasurementandControlSystems,”2008. [Online].Available: https://standards.ieee.org/ standard/1588-2008.html 33.J. C. Eidson, Measurement, Control, and CommunicationUsingIEEE 1588. Berlin/ Heidelberg:Springer-Verlag, 2006. 34.A. S. Tanenbaum andD. Wetherall,Computer networks,5thed.Boston, Mass.: Pearson, 2011. 35.J. F. Allen, “Maintainingknowledgeabout temporal intervals,”Communications of theACM, Vol. 26,No.11,pp.832–843, 1983.[Online].Available: https://doi. org/10.1145%2F200836.200848