Research on decentralized control strategies for automated vehicle-based in-house transport systems: A survey

Schmidt, Thorsten; Reith, K.-B.; Klein, Nils; Däumler, M. Article Research on decentralized control strategies for automated vehicle-based in-house transport systems: A survey Logistics Research Provided in Cooperation with: Bundesvereinigung Logistik (BVL) e.V., Bremen Suggested Citation: Schmidt, Thorsten; Reith, K.-B.; Klein, Nils; Däumler, M. (2020) : Research on decentralized control strategies for automated vehicle-based in-house transport systems: A survey, Logistics Research, ISSN 1865-0368, Bundesvereinigung Logistik (BVL), Bremen, Vol. 13, Iss. 1, pp. 1-27, https://doi.org/10.23773/2020_10 This Version is available at: https://hdl.handle.net/10419/297186 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:09July2019/Accepted:19October 2020/Publishedonline: 26 November 2020 ©The Author(s)2020 This articleispublishedwithOpenAccessatwww.bvl.de/lore Research on DecentralizedControl Strategies for AutomatedVehicle-basedIn-houseTransport Systems–aSurvey T. Schmidt1,K.-B. Reith1,N.Klein1,M.Däumler2 ABSTRACT Withthe applicationofin-houselogisticsautomated guided vehicle(AGV) systemsfor transportation three differentcontrol problemsarise:taskassignment, empty vehiclebalancingand routing. Withanincreasingfleet size andespeciallywhenconsidering requirements like flexibility andadaptivitythese controlproblemsoften become complextosolve usingacentral controller. Themainreasons arethe increasing problemsize andamountofinformation.Decentralized controlof logisticssystems hasreceivedalot of attention during thelastyears andmay help to remedy theshortcomings of centralsolutions.Decentralized solutionsrelyona distributed implementation fordecisionmakingand make useoflocal information. This survey describesbasicsaswellasgeneral categorizationsand reviews existing decentralized controlstrategiesfor thementionedcontrol problems of automatedin-houselogisticsvehicle systems. If existing,decentralized solvingapproachesfor the controlstrategyproblemsinvestigated by thescientific communityare listed.Additionally, thesecontrol strategies areevaluated to whichextendtheyfulfill the requirements of thedecentralized paradigm. KEYWORDS: automated guided vehicle(AGV) · decentralizedcontrol ·dispatching·empty vehicle balancing·load-vehicleassignment·routing ·task assignment 1. INTRODUCTION 1.1. Motivation In-house logistics deals with logisticalchallenges withinthe facilities alongsupplychains.Itemploys manual or automated material handling systemsfor carryingout thecorelogistical tasksonthe operational level. Storagesystems,transport systemsorsorting systemsare examples forthe most relevant system types. Logisticsingeneraland therebythe in-house logisticalsystems face new challenges whichare drivenbyglobalization of companyoperations, mass customization, shorter product life cycles and consequently lead to rising complexity anddynamics. Depending on theapplication,logisticssystems should have specifications, as follows[see51, 96] •flexibility(e.g. modulardesign) •(re)configurability&reusability •highavailability •plug&play configurability (standardization of interfaces andcommunication) •scalability &adaptivity •energy-efficiencyand resource-efficiency Intuitively, manual or semi-automated systems wouldbethe most suitable choice forfulfilling theserequirementsastheyshowahigh degree of freedom regardingchangeability.But usuallyinhouse logistical systemsalsohavetofulfillhigh throughput requirements andhavetocopewithhigh laborcosts as well as specialproduct characteristics. Especiallycompanies in industrial nationsare faced with increasing health andsafetyregulations andhave to counteractthe demographicchangewithtechnical, automatedsolutions [57, 88]. Automatedmaterialhandlingsystems however, cannot fullycopewiththe described requirements [34, 81]. Centralizedstructuresincontrol systems, especiallycustomerspecific hardwareconfigurations andtailoredalgorithmsleadto LogisticsResearch(2020)13:10 DOI_10.23773/2020_10 Thorsten Schmidt1(Corresponding Author) Karl-Benedikt Reith1 Nils Klein1 Martin Däumler2 1Technische Universität Dresden Dresden, GERMANY 2FabmaticsGmbH Dresden, GERMANY 2 practicalapplicationsinfullextent. As areason Schreiber mentions thequalitative advantages of decentralizedsystems, whichare hard to measure andcompare.Uptonow,the number of real-world applications is stilllow.Flämig[49]mentionsfor examplethatevennewly builtvehicle systemsare usuallycentrally controlledand decentralizedsystem arestill in research. However, in thescientific communitythere is an increasing number of decentralizedapproacheson controllingin-house vehicletransportsystems.We feel that it is thereforenecessary to review these decentralizedcontrol strategies andcategorizethem by thevehicle controlproblems. On theone hand this survey givesanoverview about availabledecentralized concepts in thefield of in-house vehicletransportsystems andthereby enhances the developmentprocess in otherprojects. On theother hand,the survey helpstoidentifyquestions whichhave notbeenansweredyet andareas wherefutureresearch in this field is required. Similarsurveys on decentralizedcontrol strategies canbefoundfor exampleinthe sectorsoffreight transport[102] anddistributionlogistics[53]. As it is impossible to include allin-house logistical system types in this survey thenextsection provides aclear definitionofourscope.Itwillalsoclarify the understandingofdecentralized controlthatweuse in this paper. 1.2. Scopeofthe survey In this publicationwefocus on vehicle-basedin-house transportsystems.Examplesfor this kind of transport system arecarrier-based systemslikeautomated guided vehicle(AGV) systemsand overheadhoist transport (OHT) systems. In thefollowing thescope of this survey is described regarding(a) controlstrategyproblems(b) type of informationand implementation (c) considered vehicles &layoutrestrictionsaswellas(d) relevant literature. Controlstrategyproblems AccordingtoSinriechand Tanchoco [98] thedesign of vehiclebased materialhandlingsystemscovers theunitloadsizing, thelayoutdevelopment,selection of vehicles in type andquantity andthe design of an appropriatecontrol system.Withinacontrol system, specificcontrol strategies areresponsible forsolving acontrol problem. Forthe defined classofautomated in-house logistics transportsystems threedifferent controlstrategy problems canbedistinguished: (1)load-vehicle assignment (see section2.1)asapartofdispatching, (2)empty vehiclebalancing (see section2.2), also apart of dispatchingand (3)routing (see section2.3). These controlstrategyproblemswillbeanalyzedindetailin theliteraturereviewinsection 2. Theassignmentofloads andvehiclestoeachother is themaintaskofthe load-vehicle assignment.Inour •hugeefforts formodifications •increasingtestefforts forupdateprocedures •limitedflexibility •costly hotorwarmstand-bysystemsasthe central controlsystem is asinglepoint of failure •restriction to hardwarefromthe manufacturer Acontrol unit that relies on global informationfor decision making requiresongoing status updatesof varioussystem units. Dependingonthenumberof unitsinasystem theresulting communicationoverhead mightbearestriction forthe system performance. But notonlythe amount of data andinformation is challenging. Gareyand Johnson[54]and terMors[107] pointout that thecomplexityofthe controlstrategy problems (see 1.2) forexample in vehicletransport systemsmakethem NP-hard. Generally speaking, centrallycontrolledsystems often reachtheir limits withregardtocomputing capacity when usingreal worldproblem sizes. Knowingabout theweaknessesofstate-of-the-art centrallycontrolledsystems andhavingthe increasing challenges of dynamiccomplexityinlogisticalsystems in mind theconcept of “decentralized control” has gained more andmoreattention in materialhandling literature during thelastyears.Decentralized control systemsare saidtooffer anumberofadvantages compared to centrallycontrolledsystems[45,89, 105]. Decentralizedsystemsshould be easier to implement andconfigure, duetotheir modularstructure. System changesdonot automaticallyresultinhigh costs. Excellentflexibility, (re)configurability and expandabilitycan be achieved.The systemsought to showabetterrobustness regardingdisturbances. There is no single pointoffailure andafter adisruption the systemscan return quicklytoworking conditions. Generallyspeaking,incomplex systemsoptimal decision making is hard to achieve. However, decentralizedsystemstry to uselocal informationand rather decentralizeddecisionrules.Due to multiple independententitiesinteracting with each otherand reactingonthesystem status,itisverycomplex to predict theoverall system behavior that emerges from decentralizedsystems. As aconsequence the performancereached by adecentralized system can hardly be predicted [97].Optimalityiseitherexpected to arise automaticallyfromthe localinteractionsor traded explicitly forthe advantages of decentralized controlsystems whichwerementionedabove.Atbest thesimplicityofdecisionmakingmay leadtoahigher efficiencythanincentral systems[91]. Thedecentralized approaches differ in thelevel of implementation as we will showlater.While some of them seem to be applicable in real-worldmaterial handling systems, others stillneed some research. However, many of theapproachescould cope with requirementsoffuturein-house logistical systems. Schreiber [93] pointed outthatdecentralized control systemshavenot made thestepfromresearchto 3 Research on Decentralized ControlStrategiesfor Automated Vehicle-basedIn-houseTransport Systems–aSurvey implemented in adecentralized wayand onlyuse localinformation fordecisionmaking. Despitehaving afocus on decentralizedapproaches, in thefollowing literaturereviewthere is notastrict limitation to trulydecentralized solutionsonly. Aclarificationof thescope of regardedsystems with different typesof implementation andlevelsofinformation is visualized in figure1. Thecombination of decision making leveland type of informationdeterminesthe characteristicsof thesystem.Almostany kind of system is possible. However, some of thecombinationsare notreasonable, like acentrally implementeddecisionmakingbased on localinformation only. Vehicle&layoutrestrictions We only consider systemswithahomogeneous fleet of vehicles.So, each vehiclehas thesametechnical parameters,likemaximum speed andhandlingtime. Themajorityofvehicle transportsystemsinindustrial applications arepathguided. Therepresentationofthe path canbeeitherphysicalorvirtual.Freeranging vehicles arerarelymentioned forbig real world applications.Therefore,these systems arenot in our scope. Themostimportant layout components of such an in-house logisticstransportsystem is thepathlayout itself,which consistsofloading andunloading stations, merges andswitches. In addition,weconsiderstorage locations, alsocalled“dwellpoint”, “depots” or “home locations”,where vehicles canpark. In theregardedcontext thenumberofvehicles can usuallybeseenasthe limitingfactor. Opposedto vehicle-basedsystemscarrier-based systemsasused understandingitisapartofthe vehicledispatching process. Theempty vehiclebalancing deals with the assignment of idle vehicles to aparking location with thegoalofpositioning theidlevehicle in aforwardlookingmanner. If done correctlyfutureresponsetimes of thetransport system on new arriving transportation tasksare minimized. As will be shown, thiscontrol problemisoften closelylinkedtothe load-vehicle assignment.Therefore,weconsiderthe emptyvehicle balancingasthe second part of thevehicle dispatching process. Generallyspeaking, therouting is required to define an appropriateroute from source (current location)to sink (destination location). “Appropriate” mayrefer to theshortestroute or furthercriteriaasthe shortest routeisnot necessarily thefastest.1 Type of informationand implementation Thekey limitation of scopeisthe focusondecentralized controlstrategies. Foraclear definition of decentralized controltwo differentaspects have to be distinguished [69]. On theone hand,there is theinternalstructure and implementation of thecontrol system.Conventional controlsystems have ahierarchicalstructure.This meansthere is one centralcontrollerwhich collects informationfromthe system andisresponsiblefor decisionmaking. In adecentralized implementation thecentral decision making unit is replaced by severalsmaller,distributed unitsthatmakedecisions autonomously.Theycan be called decentralizedor heterarchical units. On theother hand,the term decentralizedcan be used to describethe type of informationthatisused fordecisionmaking. It canbedistinguishedwhether a(decentralized) controller uses global system knowledge or locallyavailable informationonly. In ourdefinition,adecentralizedimplementationrelies on localinformation. Nevertheless,itisworth mentioning that thereis no strict line (ordistinction) between centraland decentralizedsystemswithregardtothe structureof implementation andthe informationused. Forexample, asystemcanconsistof multiple heterarchicalunitswhich make almost allnecessary decisionsautonomouslyand asinglecentral unit whichisonlyresponsible fora minor task.Analogue theseentitiescan rely on local informationmainlybut stillhaveknowledge about waitingtransportationtasks,which is some kind global information. Furthermore, thereisnoclear definition in literature of what canberegardedaslocal information. To sumup, thereisnostrict categorization of systems as either centralordecentralized. Insteadtendencies towardsone or theother paradigmare illustrated in this survey.Inthe following, this paper uses theterm “trulydecentralized”for controlsystemsthatare 1Inthispublication “route” is used as asynonym for“path”. Aroute or apathconsistsatleast of one path element. Figure 1: Matrix of decision makingand type of information according to [69].The main focus lies on thedecentralized decision makingbased on localinformation (black area). As thereisno strict distinctionpartlydecentralized approaches(lighter gray area)are touchedaswell. Type of information local Focus of this paper global decentralized central Decision making 4 production planning. Consequently,the meaning of thetermdiffers andconfusion canarise quickly. In thecontext of in-house vehicletransportation systemswesee dispatchingasanumbrellaterm whichincludesthe morespecific controlproblems “load-vehicleassignment” sometimes alsoknown as task assignment, and“emptyvehicle balancing”.In spiteofsimilarities between thecontrol strategies of load-vehicle assignment andempty vehiclebalancing theliteratureonvehicle-based transportsystems distinguishesbothquestions.While thesecondone isusually calledempty vehiclepositioning or empty vehiclebalancing,the first one is usuallyreferred to as dispatching. In ouropinion thedefinition of dispatchingshouldinclude both activities as both deal with asimilarquestion: howshould avehicle behave after it hascompleted ajob.Furthermore,bothofthese sub-tasksneed to be considered subsequentlyinarealworldimplementation. Once ataskisassignedtoacertain vehicle(or vice versa),discovering afeasibleroute andselecting “the best”route from agiven source to agiven destination is part of therouting process.Furthermore,the subproblem of routeexecution is responsible for operationallyguiding avehicle andfor theavoidance of conflicts.All aspectsofrouting aredescribed in detailinsection 2.3. In order to characterizean approach as decentralizedinour understanding,we evaluate theentityofadecision making process and thetypeofinformation this entity is usingfor its decision.Itisimportant to understand that thereisnot astrict“blackand white”-likeseparationofwhatcan be regardedascentral or decentralized. Insteadthere aremanylevelsbetween complete centrality andtrue decentrality,ashas alreadybeendiscussedinsection 1.2. This becomesespeciallyevident regardingthe informationusedtomakeadecision.Moreinformation in generaland especiallynon-local informationusually leadstoahighergradeofcentralityand thereforea higher levelofcomplexity.The following static and dynamicinformation is more or less relevant forthe aforementionedvehicle controlstrategies: •layoutspecific information(most of thetime static): –pathlayout –sinks andsourcesinthe layout –parking locations •vehicle specific information(dynamic, but only oneentity): –current position –velocity, acceleration,deceleration –current status –idleorbusy –other relevant information, like batterylevel •system specificinformation (dynamic,multiple entities,aggregated information): –positionofother vehicles (trafficjams, closed paths) –destination –paths of othervehicles in baggagehandlingsystems (BHS)atairportsusually behave differently duetoahighernumberofcarriers compared to thenumberoftransportrequests. The limitingfactorincarrier-basedconveyor systemsis usuallythe trackcapacity.Therefore,the focusofthis paper does notlie on carrier-basedconveyorsystems. However, they arerarelymentioned, when thereisan approach that in generalfits to thescope of this paper andservesasasupplementexample. Relevant literature In this survey we mainly consider theimplementations accordingtothe describedscope.Nevertheless, we will make referencetoimportant publications that areout of thescope andtostrategiesthatwould notfitexactly in ourdefinition of true decentrality,e.g.because the decentralizeddecisionunits stillmakeuse of global informationtosome extent. Theinitial impulsefor this survey wasthe dissertation of co-authorKlein [69].Thiswas alsothe basisfor some partsofthiswork. 2. CONTROLSTRATEGY PROBLEMS Having introduced theexact scopeofthispaper,this sectionreviews thethree differentcontrol strategy problems,namely(1) load-vehicle assignment,(2) emptyvehicle balancing, as well as (3)routing witha decentralized-focus(seefigure 2). Foreachcontrol strategy problem we analyzeif decentralizedapproachesare availableand to which extenttheyfulfillthe requirementofusingonly localinformation,i.e.iftheycan be considered to be trulydecentralized. Furthermore, thechronological developmentfor popularapproachesisalsotaken into account. Figure 2: Classificationofcontrol strategy problems Load-vehicle assignment is thechallenge of assigningvehiclestonew transportrequestsorvice versaassigning transportrequeststovehicles, see section2.1.The emptyvehicle balancingdescribed in section2.2 is aboutchoosingavehicle’s destination when it hasjustcompleted ajob andnomoretasks are available. Theterm“dispatching” is widely used in many contexts,e.g.the controlofpowersystemsor Dispatching Control strategy problems Load-vehicle assignment Routing Empty vehicle balancing 5 Research on Decentralized ControlStrategiesfor Automated Vehicle-basedIn-houseTransport Systems–aSurvey system –for thefirsttimeorafter aprocessingstep –itisthe loadsorits correspondingworkstations responsibility to select avehicle fortransportation. In order to findthe “best” vehiclefor thetransport, all availablevehiclesneed to be ranked accordingtoone or multiple criteria.The logic forprioritizingthe vehicles is essentiallythe assignment rule. Thelasttwo triggers on thelist –avehicle finishesa task or reachesaparking location –can be linked to the vehicle-initiated assignment rules. Insteadofaload/ workstationchoosinganidlevehicle,itisthe vehicles responsibilitytoapplyalogic in ordertochoose its next load or task.For afurther comparisonofthe two perspectives seealso[70]. Though thetwo perspectives seem to be based on adifferent approach,bothperspectivesare usually combined in real-world applications.Incasean arriving load cannot findanidlevehicle at once (load initiated rule), it should notcontinuouslybesearching forvehicles. Theseongoing calculations couldslow down thesystem.However,the simplerapproachisto keep theloadasanopentaskand offerittothenext vehiclethatbecomesidle(vehicleinitiated rule). Variouscentralized approaches forthe load-vehicle andtaskassignmenthavebeendeveloped overthe past years. Thereisawhole rangefromsimpleto complexrules.Le-Anh anddeKoster [8] andVis [108]provide excellentoverviews aboutdesignand controlofautomated guided vehicle(AGV) systems, includingsectionsabout vehicledispatching rules. Fazlollahtabar andSaidi-Mehrabad[46]provide an overview of variousassignmentmethods,which they call scheduling. Theseapproachesall have –bydefinition–acentral instance whichperformsthe assignment.Generally this centralcontrollerhas access to global information, i.e. thecentral instance hasacompleteimage of thesystem status.However,depending on thecomplexityofthe approach,the problem size andthe performancethat should be reacheddifferent quantitiesofinformation aretaken into account. AccordingtoLeAnh [74] centralassignment strategies canbeclassified accordingto(a) thenumber of attributes takenintoconsiderationfor adecision (single-attribute rulesormulti-attributerules), (b)the existenceofalook-ahead period (dynamic rules),(c) the possibilityfor jobreassignmentand (d)the possibility of asequentialdecisionprocedure (hierarchical rules). Duetothecomplexityofthe assignment problem, centralcontrol strategies areusually heuristics. Instead of aglobaloptimum,heuristicsmakeareasonable decision in ashort time.Inorder to findasuitable solution withincreasingproblem size,limits in the amount of necessary communicationand computing times arereached as problemsrelated to theareaof load-vehicle assignment areoften NP-hardasshown by Gareyand Johnson[54]. This becomesespecially evidentinaso-called on-lineassignmentwithan ongoingarrival of new loads or tasks. This often leads –queuessizes at sourcesand waitingtimes –(set of)opentasks After thisbrief introduction thefollowing sections review thementionedcontrol strategy problemsalways in thesameorder: (1)basics, (2)literaturereviewon solvingapproachesand methods,followedbya(3) summary. Theliteraturereviewisfurther grouped by topics or rather solvingapproacheswhich in turn are arranged chronologically. 2.1. Load-vehicle assignment 2.1.1. Basics Thefirstaspectofdispatching is thetaskassignment. Oneormultiplevehicles(often alsoreferredtoas robots)need to getassignedtomultiplelocations. Thetaskthe vehicles perform canfor examplebea surveillance task or just achargingprocess.Khamiset al.[66]provide ageneral overviewofthe multi-robot- task-assignment(MRTA). Furthermorethe assigned task canalsoconsist of atransportationjob.Inthis case theproblem is usuallyreferredtoasload-vehicle assignment or transportassignment. Oneormore loadsneed to be transferredbetween twodifferent locationsand one or morevehicle areabletoperform thetransports. In theload-vehicleassignmentthe destinationof atransport canbetaken into consideration, which is especiallyimportantwhenvehicleswithhigher capacities areused. However, theload-vehicle assignment andthe task assignment mainly deal withthe similarcontrol problemofcreatingafeasibleprocedure to matchall queuedtransport requestsortasks to specificvehicles. Theassignmentmethodneedstotake thecharacteristicsofthe vehiclesystem into account andusually solves theassignmentproblem withregard to acertain objective, like minimal response time or maximumthroughputfor thetransportationproblem. Duetothe similarproblem structurebetween theloadvehicleassignmentand thegeneral task assignment both problems will be considered simultaneously in theliteraturesection. Whileoperating amaterialflow system thereare three different events whichcan triggeranew dispatching decision andinconsequencethe assignmentprocess [see 74]: •Arrival of anew load/taskinthe system •avehicledeliversaloadtoits destinationor finishesits task •avehiclereaches itsparking location Thesetriggersreflecttwo generalperspectivesonthe controlproblem whichEgbeluand Tanchoco [36] define forclassifying dispatchingrules in general: (a)load or workstation-initiated rulesand (b)vehicle-initiated rules. Thefirsttrigger is linked to load-initiated or workstation-initiated rules. When aloadentersthe 6 hasespeciallyturnedtocontainerportterminals.In recent yearsthe topic of load-vehicle assignment gains moreattention duetoanincreasing amount of AGVs in intralogisticssystems.Another importantareaof research is overheadhoist transport (OHT)systems in semiconductorwafer fabrication[seee.g.71]. Twomajor approaches couldbeidentified in literaturethatwhere labeled as decentralized: (1) layout transformation to enhancethe performanceof decentralizedcontrol strategies and(2) multi-agent systems. Whereasthe layout transformation were the first approaches foradecentralized assignmentthe vast majority of nowadays approaches aresomehowrelated to theideaofagent-basedsystems. Layout transformation Thefirstapproacheswhich appliedadecentralized load-vehicle or task assignment focusedonsingle-loop layouts. Bartholdiand Platzman [12] analyzed asingleloop system andevaluated theperformance of afirst encountered first served (FEFS) rule forthisscenario. Usingthisruleeachvehicle circulates in agiven path loop.Wheneveraloadisencountered by avehicle at itscurrent location andthe vehiclestatusisidlethe load gets picked up andgetsdelivered as soon as the vehiclereaches theload’sdestination location.Only localinformation is used forthisapproachand therule is performedbyeachvehicle individually.Therefore, this approachcan be regardedastruly decentralized. TheFEFSrulecan be regardedasagreedyrulefrom avehicle’s individual view.Opposedtothat, thefirst come first serve (FCFS) rule is agreedyrulewhich takesinformation about thearrivingtimeofmultiple loadsintoaccount. Theauthorswereabletoderivean expected performancelevel analytically andtoverifyit with asimulationstudy.Asaresult, thedescribed FEFS rule outperformedother simple (but less decentralized) ruleslikeFCFSorlongest queuefirst(LQF). Inspired by theseresults severalauthorstried to developnew approachesduringthe followingyears. Theideawas to developextremelysimplelayoutsor to transformconventionallayoutsintocombinations of simple,i.e.single-loop layouts. Theresulting layout is fareasiertocontroland should achievethe same performanceasthe more complexconventionallayout. Sinriech andTanchoco[98]develop methodswhich canhelptoconstruct asingle-loop system foracertain givenenvironment or cutanexistingsingle-loop into segments whichare served by only one bidirectional vehicle[99]. Although theauthors do notexplicitly statethis, they usesome kind of sequential dispatching whichissimilartothe FEFS rule. Bozerand Srinivasan [15]and Ross et al.[85]alsofollowasimplification approach when they introducetheir idea of tandem layouts. Although allthose authorsspend alot of effort on measuring theperformance andcomparing their systemstothe conventional version, it needstobe to less complexapproachesorcalculationsconcerning aloweramountofinformation,resulting in alower system performance. Opposedtothat, adecentralized load-vehicle or task assignment is able to remedy some shortcomings of centralizedapproaches,especiallythe overall complexity in huge systems. Decentralizedapproaches arecharacterized through(a) adecentralized implementation fordecisionmaking, i.e. each vehicle or each load calculates independentlywhich task to performnextand (b)the decisionsare made basedon local(or at leastlessglobal) informationprimarily. Generallyspeaking, decentralizeddispatching andthus adecentralized assignment is discussedlessfrequently in literaturethancentral dispatching. Additionally,the literaturediscusses decentralizeddispatching usually in very simple systemswhich canbecategorized in threedifferent vehicle-based transportsystem types duetotheir path layout: (1)single-loop systems, (2)tandemsystems and(3) conventional systems2 accordingtoLeAnh [74] In thefollowing we will limitour attention to assignment strategies that work withoutpre-arrival informationand that arecommonly used in in-house logistics environments.These strategies areused becauseoftheirsimplicityand theireasyadaptability to dynamicand stochastic situations.But they are mostly heuristics. Nevertheless, thereare also authors that evaluate,whether assignmentrules canbereplaced by dynamicschedulingalgorithms, whichinour definitioninclude pre-arrivalinformation.Le-Anhet al.[7] provideagood introduction to thesetechniques that arenot subject of this survey. Aliteraturereviewofexistingdecentralized approaches forthe task andload-vehicleassignment underconsideration of theinformation types used andthe levelofdecisionmakingcan be foundinthe following section. 2.1.2. Literature review on solving approachesand methods Themajor research activities on thetopic of loadvehicleand task assignment started in the1980s [see e.g. 79]and many of thefundamental classifications whichare stillvalid have been developed during the last twodecades of the20th century. Starting with manufacturingsystems andwarehouses, attention 2Asingle-loop systemsconsist of one guidepathloopwhere severalloading andunloading stations arelocated.One or more vehicles travel in this loop whichleads to simple traffic controland dispatchingrequirements. Atandemsystemscan be regardedasmultiplesingle-loop systems. Onlyone vehicle is used in each loop andloads canbepassedvia transfer points between thesingle-loops. Conventional systemscan referto virtuallyany real-world transportsystem.Comparedtothe othertwo system setups thedispatching andtrafficcontrol requirementsinconventionalsystemsare farmorecomplex. Multiple vehicles have to be controlled andthere is ahigh probability of congestions. 7 Research on Decentralized ControlStrategiesfor Automated Vehicle-basedIn-houseTransport Systems–aSurvey thetask, howavehicle finally receives thepermission forthe task,etc.The CNET protocolwas extended withvarious ideas, f.e. thepossibility forvehiclesto return previouslyassignedtasks andinconsequence to reassign tasks. Generallyspeaking, auction-based approachesare robust to inconsistencies between multiple agents regardingthe awarenessofthe system status [22].Therefore auctionsare especiallysuitable fordistributed anddecentralized approaches.Inthe following decentralizedagent-based approaches with relationtoauctionsand CNET arepresented. Fayand Fischer[44]develop acontrol system for destination-codedvehiclesinabaggagehandling application. They propose amulti-agent load-vehicle assignment based on theCNETprotocol. Loading stations offertheir waitingloads on avirtual market. Avehicle canevaluatethese offers basedonits current position andthe pick-up location.The distance figure is combined withthe currentutilization of theroute to prioritizeand select one of theoffers. Fayand Fischer carry out asimulationstudy whichusesasection of areal-world baggagehandling system andhistorical inputdata. However, theexperimentalsimulation settingsremainunclear andthe system does notcontain morethan15vehicles. Thecontrol methodologydeveloped by Weynsand Holvoet[115] andWeyns et al.[116] alsomakes useof themulti-agent perspective. Theaim of theauthorsis to testthe feasibilityofdecentralized controlsystems forAGVs. They refertotheload-vehicleassignment as “transportassignment” anddevelop twodifferent ruleswhich they call FiTA andDynCNET whichare discussedinthe following.The first approach is based on theideathattransport agents of loads whichare waitingtobepicked up andthe AGVagentsbothemit fieldsintheirlocal virtualenvironment.The field of a transportagentsattractsidlevehicleswhereas AGVs repulsethemselves. Thevehiclescombine theeffects of thefields they receivetocalculate some kind of field gradient whichtheyfollowalong predefinedpaths. TheDynCNET is an adaption of theCNETProtocol, wheretransport agents andAGV agents both have a certainradiusinwhichtheysearchfor each other. The transportpriorityand thedistancebetween vehicle andloadare used as criteria forproviding proposals. Compared to thestandardCNETprotocola significant modificationhas been made:The vehicles areallowed to switch tasksafter theinitial assignment.Weyns and Holvoetuse simulation experimentstoanalyze the performanceofthe describedrules.Inareal-world layout with 56 loadingand 50 unloading stations they use14AGVstoshowthattheirtwo approaches perform better than theoriginalCNETprotocolregarding to theaverage waitingtimes.Bothrules of [115] have adistributed implementation of control, hence usingthe FiTa rule some centralcontrol entities are necessary,f.e.acontroller, whichcalculates thefiled in everypoint of themap.Obviously,bothrules do notrelyonlocal informationonly. Weynsand Holvoet mentionedthatthe considered conventional layouts often have averysimplestructure themselves with only afew vehicles used in each of thesystems. Multi-agentsystems (MAS) Besides thementioneddecentralized approacheswhich arebased on layouttransformationthe conceptsof agents andmulti-agent systemsstarted toinfluence thecontrol literature in thelate1990s.Generally speaking,amulti-agent systems(MAS) consists of twoormoreagents whointeractwitheachother to achieveacollectivegoal. Usuallythisinteraction is reachedusing either direct communicationorindirect communicationvia storinginformation somewhere. With theagentshavingthe abilitytocooperateand to go forsome individual or even global goals areasonable behavior of theentiresystem should arise from their interaction.General advantages areamong others the lack of asinglepoint of failureand the“plug andplay”- principle. Furtheradvantagesand generalfeaturescan be foundin[92]. Foramoredetailedstudy on collective behavior of mobile agents see[117]. MASusually offeraflexiblebehavior. As each agentinterfereswiththe (changing) environment independentlythere is no need foraglobalstrategy tackling each specialcase. Especiallyincomplex systemsitisalmost impossible to reachsucha flexiblebehaviorwithacentralcontrol unit.The maindisadvantageofMAS is that theexact system behavior is almost unpredictableand usuallynot optimal. Examples foragentsinour contextare vehicles,source anddestination nodes, or even path segments.According to Weynsetal. [116]“Applying amulti-agent system opensperspectivestoimprove flexibility andopennessofthe system:the AGVs canadapt themselves to thecurrent situation in their vicinity,order assignmentisdynamic, thesystem candealautonomously withAGVsleaving andreentering thesystem.” Severalauthors developed agent-basedsystemsinorder to exploitthe advantages of thedecentralized paradigm.Opposedtothe layout transformation approaches,agent-based strategies for theload-vehicleand task assignment were alsoapplied on morecomplex,conventionalpathlayouts. Generallyspeaking, many decentralizedapproaches basedonthe conceptofmulti-agent-systemsmakeuse of so-calledauction algorithms.The basic idea is that theassignmentbetween vehicles andloads/stations aredeterminedusing an auction based on certain criteria,e.g.the nearestvehicle getsatransportation task etc. Many of theseauction procedures arebased on theso-calledcontractnet (CNET) protocol. CNET is an importantprinciple regardingcommunication of entities in adistributed problem forcooperative task executionand wasoriginallypresented by Smith[100]. This protocoldescribesanegotiationsequencethat serves as abasis forall auction-based controlstrategies, i.e. theprotocolregulates howatask is announced in a network, howand when avehicle canmakeits offerfor 8 In addition to thedescribedapproaches, various furtherexamplesfor theusage of bidding algorithms in adecentralized load-vehicle assignmentare givenin literature [see e.g. 25,37, 42,43, 94]. Allinall, it canbestatedthatauction-based approaches areonlypartlydecentralized.Aseachagent is doingits calculationindependently,the described approachescan be regarded as ausually completely decentralizedimplementationofthe decision making process.However, agents do usuallyhaveaccessto non-localinformation:vehiclesneed to know thestatus of multiple workstations or workstations receiveoffers from thevehicles. As aconsequence in most auction based approaches informationisexchanged and aggregated in awidelymanner. Onlyfew publications combineacommunicationconstraintwithauctionbasedapproaches. Having described agent-basedassignment approaches with relation to auctions andCNETinthe following furtheragent-based approaches forthe loadvehicleand thetaskassignmentare presented. In 2002 Bermanand Edan [13] proposed theusage of decentralizedcontrol systemsinacomputerintegrated manufacturingenvironment.Theyfavor theusage of vehicle-initiated dispatchingrules compared to workstation-initiated rulesastheyjudge thelattertohave higher requirements regardingthe communicationoverhead.The concentrationonto vehicle-initiated rulesisconsideredtobesufficient as in themanufacturing contextthe vehicles arehighly utilized andthe system is rarely in an idle state. They implementamulti-attributedispatchingrulebased on thedistance to theworkstation andthe duetime of theproduct. No centralcontroller(or instance)is implemented.Instead,eachAGV collects information from allworkstations. Then,itcalculates adecision accordingtoadescribed dispatchingruleand informs theworkstation.Incombination withrouting rules, a conceptual testenvironment with up to twovehicles wasdeveloped. Though having adecentralized decision making andnocentral unit whichaggregates all thesysteminformation,eachAGV collects the status from multiple workstations andtherefore uses non-local information. Consequently,thisapproachcan only be seen as partly decentralized. Arsieand Frazzoli [10] andArsie et al.[9] present anocommunicationalgorithm foraproblem similar to ataskassignment: mobile agents have to visit target points that aregenerated in astochastic manner.The authorssee theirmaincontributionin aso-calledmotioncoordinationstrategythatdoes notrelyoncommunication between thedifferent agents.Nonetheless,optimalityisreached under certainconditions. Even though ahigherlevel of communicationwillnot decrease theperformance of asystem, theauthors showthatahigherlevel is notalwaysnecessary.Theypropose thefollowing algorithm: each agentindependently calculates itsnext action andalwaysvisitsthe target nearesttohis current calculatethe totalnecessary communicationloadfor theirproposedrules,which is about twiceashigh as thecommunication levelfor amoredecentralized dispatchingstrategylikethe CNET protocol. InChoi et al.[22]two decentralizedapproachesfor the task assignment includingacommunication constraint arepresented:the consensus-basedauction algorithm, whereasingletaskgetsassignedindependently to an agentand theconsensus-based bundle algorithm, where asequence of tasksare combined andassignedtoan agentatonce. Both algorithms rely on twophases. In theauction phaseeachvehicle canbid on specifictasks. In theconsensus phasethe vehicles receiveinformation about theresults of theauction processvia alist of winningbidsthatgetspassedbetween neighboring vehicles.Asaconsequence thesamesituational awarenessofthe vehicleagentsisreachedevenwithout acentral entity whichmonitorsthe system status. Schwarz et al.[95]alsouse amulti-agent system foraload-vehicleassignmentvia abidding procedure basedonthe Foundation forIntelligent PhysicalAgents (FIPA) Contract NetInteraction Protocol 3,avariation of theoriginalCNETprotocol. Vehicles areabletobid forordersput outbythe stations.Anoffer is calculated underconsideration of thedeliverytimeofthe current joband thefutureposition. Avehicle canbid in multiple auctionsbut canonlyaccept asinglejob. Giordani et al.[55]present atwo-level multi-agent systemframework.Inthe first levelthe number of necessary robots foragivennumberoftasks is calculated basedonaniterativeauction based negotiationalgorithm.Inthe second leveltasks are assigned to certainrobotsineachtimeperiod. The so-calledtaskallocationproblem is solved usinga distributed versionofthe HungarianMethod4.The decisions aremadebyagentsand thecommunication constraintsonlyallow communicationbetween neighboring agents.Withthe help of asimulationstudy theresults of this decentralizedapproachare compared to acentralized approach.Whereas thepresented decentralizedsolutiontends to higher costsdue to a worseutilization of resources,italsoresults in amore robust solution. Anotherdecentralized approach forthe load-vehicle assignment basedonthe CNET protocolispresented by [78].Machinesoffer taskstovarious AGVs which calculatecosts forthe transportconsidering the distance to themachine, thecurrent batterylevel and even theirphysicalsuitability forthe giventask. A machineisabletocontracttwo vehicles forthe same task.The secondaryAGV will replacethe first vehicle in theevent of afailure.Cloud communicationisused forsending andreceiving information. 3For moreinformation about theFIPAContractNet Interaction Protocol seetheirspecification [48]. 4The HungarianMethodisanoptimization algorithmdeveloped by Kuhn in 1955 that solves theassignmentproblem [72]. 15 Research on Decentralized ControlStrategiesfor Automated Vehicle-basedIn-houseTransport Systems–aSurvey usingpredenedzones. Reactive routingisusedfor finding routes to remote nodes[seee.g.23, 56]. Themainfocus of thispaper aredecentralized control strategies.Accordingtothe classification schemeinfigure 4the weaker term“distributed”was used insteadof“decentralized”.Lau andWoo [73] have chosenthistermfor non-centralrouting approaches, becausewithout acquiringadditionalknowledge about thenetwork from othernodes at allnomeaningfullocal routingdecisioncan be made. We will show belowthatsuchdistributed implementationsdoexist. Acompletelydecentralized routing withoutany non-localinformation cannot guarantee that adestination will be reached. In this case at leastaminimum amount of aggregationof informationisrequired. This limitation of thedefinition of decentrality hastobe kept in mind when assessing thecontributions of theauthors below. Although these authorsmight usethe conceptof“decentralized” routing,theyrefer to adistributed implementation structure, but generallydonot fulfill therequirement of purely usinglocal information. Route selectionasapartofroute planning If thereisonlyasinglepossibleroutebetween agiven source-sinkrelation, therouteselection will obviously be trivial.Inconventionallayouts usuallymultiple feasible routes or even multiple equivalent routes with regard to thedecisioncriterion (f.e.distance)exist and aspecific routeneedstobeselected.Thisdecisionis dependingonthe objectiveofthe selection. Theproblem of load balancing (spreadingthe vehicles)indecentralized systemshas been recognized by severalauthors andaddsanew challengetothe developmentofsuchalgorithms. Theshortestroute is notnecessarily thebestchoiceascongestionmight occurand in theworst case deadlocksendangerthe system functionality. Theserisks canbemitigated by acentral controller withglobalsystem view that redistributes thetrafficflow if necessary.But in a decentralizedsystems new approaches arerequired becausethe overallsystemstatusisby definition unknown. Ng et al.[80]propose aload-scattering algorithmbased on theaverage flowonthe different alternative pathstoadestination.Theydividethe total load alongacertain path by thenumberoflinks and therebyderiveanaverage flowfigure.Fromall possible pathsatraveling load selectsthe routewiththe lowest averageflow.Other inspirations forthistopic can be foundinurban traffic networks [e.g.4]orad-hoc mobile networks [e.g.119]. AccordingtoWardrop[112] theselection decision canbemadechoosingone of twodifferent principles: •Goalrouting: Foreachvehicle thebest(usuallyshortestor fastest) routeisselected. predefined,e.g.after aspecific time span,after layout changes or dependingontraffic patterns. Therefore, generalknowledge about thetrafficflow andpossible future system behavior is required,todetermine these points in time. With real-timeevent-dependent andstate-dependent approaches updates of therouting tables do notjust happenatspecific pre-plannedtime-points butmay happencontinuously. Usinganevent-dependent approach, multiple alternativeroutes aredeterminedfor agiven source-destination constellationand depending on thecurrent networkstatusone of theroutes is chosen. Forexample,avehiclewould always take theshortest routeunlessthe utilizationofthis routeisabove a certainthreshold or apathsegment breaksdown, etc. In contrast, real-timestate-dependent routingusesno predefinedrouting tables or sets of suitable routes.The routeiscalculated basedonthe currentnetwork status, e.g. theutilization of single pathsorrecentlyfinished transports aretaken into consideration. Dependingon theentitywhich makesdecisions andthe information that is used forthe decision making this strategy caneitherbeseen as centralizedordistributed. In acentralized versionofstate-dependent routinga centralunithas global knowledgeofthe networkand in consequenceisextremelyresponsive. In amore distributed algorithmthe routingtablesare notkeptby one centralunit. Insteaddistributed units, e.g. nodes in thegraph have distributedversionsofthe routing tables.Distributedalgorithmsrequire ahigherdegree of informationexchangebut aresaidtobemorerobust to disturbances [see 73]. An alternative to adistributed storageofsystem informationinnodes is aggregating informationabout thecurrent system status viaintervehiclecommunication.Vehiclescan sharetheir plannedroutes with theentirefleetoratleast with other vehicles near-by. As aresult, theknowledge is more distributed. Threedifferent formsofdistributed state-dependent routingcan be distinguished[see3,73]: •Global/proactiverouting: Global/proactiverouting enablesanup-to-date view of thenetwork with periodic updates. Examples forthiskindofroutingare theoptimized link staterouting (OLSR) or theglobalstate routing(GSR) [see 21,62]. •On-demand/reactiverouting: Insteadofproactively creating an up-to-date view,these routingapproachesare only executed when arouting requestisreceived. Examples of this algorithmtypeare adaptive distance vector routing(ADVR)and dynamicsource routing (DSR)[see14, 111]. •Hybridrouting: Hybrid routingisacombinationoffeaturesof proactiveand reactive protocols. It reducesthe overall effort forproactive routingbylimitingthe regardedareafor updates to near-bynodes,often 16 consideringthe currentutilization of thenextpath segment Theformertwo methodsput moreemphasisona planningaspectwhile thelatterone is amorereactive approach. Theapproacheswhich focusonplanningcan be appliedinrathersmall layoutswithfew vehicles and stable demands. But conventional networks with many vehicles make it hard or impossible to pre-calculate allroutes. However, complexlayouts canbedivided in less complexsub-layouts andthe planningmethods canbeapplied independentlyfor each part.Incaseof conflicts,the priority on thelimitingpathsegment can be regulated by variousstrategies, like afirstcome first serve(FCFS)strategy, by astrategydependent on thepriorityofthe transported loadsorthe vehicle destination. Furthermore, global informationorsome otherinformation exchange is necessary forthe static andthe time-windowbased approach [see 74,83]. In contrast, localinformation is sufficientfor the dynamicmethods.Ateachdecisionpoint (usually a switch)adecisionismadeifthe next path segmentcan be traveled,orifsome blockingsoccur.Thismethodis even capable of incrementallyconstructingaroute to a givendestination,iftherewas no initalroute planning. Globalinformation about shortestpaths or even the currentsystem status canbestoredinthe nodesand cantherefore be provided forpassing vehicles. Anotheraspectthatisrelevantfor thedynamic decision is theright of wayatmerges. Especiallyin systemswithahighnumberofvehicles, like carrierbasedsystemsatairportsthisdecisioncan have a huge impact on thesystem performance. Even though intersectioncontrol couldbetheoretically categorized as apartofdynamic routingexecution we consider the field of intersectioncontrol notasapartofour scope. 2.3.2. Literature review on solvingapproaches and methods Thereare multiple approaches formoreorless distributedrouting algorithms,e.g.the sub-problems of routeplanningand routeexecution.The next paragraphs illustratethe most influential ideaswefound in literature.Atfirstpublicationsthatfollowthe idea of multi-agentsystems(MAS) foradistributedrouting arepresented.Afterwards, we discuss swarm-based approachesfor examplebyreviewing themainideas of antalgorithms. Finally, we take alookatapproaches that transfer ideasand protocolsfromrouting in ad-hoc communicationnetworkstologistics. Multi-agentsystems (MAS) Forashort introduction to multi-agentsystemswerefer to chapter 2.1.2or[116]. Oneofthe first attempts to come up with a decentralizedrouting algorithmusing theconceptof agent-basedsystems wasmadebyTaghaboni-Dutta andTanchoco[103].Theydeveloped an incremental routeplanner forautomated guided vehicle(AGV) •Route balancing: Foreachvehicle theroute,which resultsinaglobal system optimum in thesense of minimaltotal travel time, is selected. As it resultsinaglobaloptimum thesecond principle is more favorablebut alsothe morecomplicated goal. This is only possible forsmall layoutsand usually requiresextensive pre-calculation–see thealready mentioneddefinition of scheduling accordingto[74]. Underincomplete informationinadecentralized/ distributedsystem,usually thefirstprincipleis reachable. Either with or withoutknowledge aboutthe currentsystem status asinglevehicle always selectsthe routethatispresumablybestfor itself. Anotherstrategywhich wasnot discussedbyLau andWoo [73] consistsofskippingthe entire route planning(discovery andselection)process.Lost results canbereplacedeitherwithdynamic route executionapproaches(seenextsubsection) or leads to arandomvehicle routingprocess with completely local information. Route execution After afeasibleroute wasfoundand selected usingany approachofthe routeplanningthe vehiclecan start executingthe chosen route. Theproblem arisingat this pointisthe avoidanceofblockings anddeadlocks withother vehicles.Blockings occurwhentwo or more vehiclewanttoclaimthe same physical spot at thesametime. Somehowadecisionhas to be made, whichvehicle is allowedtogofirst. This is especially importantatintersections.Adeadlockoccurswhen agroup of tasksorprocesses is waitingfor an event whichcan only be triggeredbyone of themembers of this group. In this situationthe system locksitself andcannotproceed.Inlogisticssystemsthissituation usuallyoccurs when twoormorevehiclesblock each otherand none of them cancontinue. To avoidblockings anddeadlocks,eachvehicle has to somehow spread informationabout itsintendedpath. This informationcan be shared forexample withother vehicles,withsinglepathsegmentsand nodesorwith acentral entity. Sticking to therequirementsofproviding conflictfree routes,several types of approacheshavebeen developed [see e.g. 83]: •Staticmethods: Theentireroute is blockedfor thetimeavehicle is moving •Time-window-based methods: Only single path segments areblocked in thetime window thevehicle is expected to travel on them •Dynamic methods: Pathsare blockedincrementally from path segment to path segment7whilethe vehicleistraveling and 7Inliteraturethistypeofroute executionissometimes also knownas“forwarding”. 17 Research on Decentralized ControlStrategiesfor Automated Vehicle-basedIn-houseTransport Systems–aSurvey agentisresponsible forroute selectionwhenaroute is requested by anotheragent in thesystem.The cost factors, whichrepresent the“virtuallenght” of apath areupdated constantly accordingtothe currenttraffic andthe Dijkstra algorithmisusedfor computingthe resultingshortestpath. This meansthatthere is still global informationaggregated andinconsequence the approachdoesnot completely followadecentralized pattern. Theauthordescribes astaticrouting strategy andanincremental routechoiceapproach.But theexact functionalityaswellasthe logic of theroute agentfor choosing one of theavailable routes remainsunclear. Hofmeister et al.[60]develop aconcept forarouting strategy whichusesalabel correction algorithm fordecentralized routeupdates.The authorsclaim that this reducesthe communicationoverhead.The routingalgorithm is to acertain extentbased on ideas from AGVliterature. It pre-plansroutes andusesthis informationtoconsiderfuturepathutilization in its routeselection.However, thewhole paper is conceptual andnoperformance evaluationispresented. Amongother strategies,Klein [69] proposesand evaluates astrategythataimstobetruly decentralized. As allagentsrelyexclusively on localinformation the vehicles andnodes do nothaveinformation about the global topologyorthe system status at all. Apath planningfor agiven source destinationcombination is thereforenot possible andevenadynamic route executiondepends on informationaggregation in the nodes. Consequently,ateachswitchavehiclechooses randomly what path to take next.Adestination is only reachedbychance. Having obviousdisadvantages, Kleincalls this a“worstcasestrategy”,withthe only advantageofreducingthe routingdecisions to a minimum.Asalready mentionedinsection 2.2Klein uses this random routinginsomecases forunladen vehicles.All in all, thisapproachcan be seen as a rudimental MAS. Schwarz et al.[95]convert thealgorithm of ter Mors et al.[106],which is based on agraph networktoa decentralizedalgorithm forvehicle routing. Avehicle that wantstoreach adestination searches forthe fastestway withinthe graph.Afterwardsitreserves correspondingtimeslots on each path segment. Other vehicles calculatingtheir routes,takethe reservation into accountand in case of aconflict have to either take adifferent wayorwaitfor theedgetobefreed.The calculationistherefore done in adecentralized manner, but withglobalinformation aboutall reservations in thegraph. Schwarz[94]proposesanegotiation method between twovehiclesinthe phaseofrouteexecution, which is appliedwhenavehiclewants to travel on an alreadyblocked path segment. Thefirstvehicle with the reservationchecksfor alternative routes. In case thelossoftakinganalternative routefor the first vehicleislowerthanthe benefit forthe second vehicle, thereservation is canceled.However, this may lead to many negotiations in crowdedareas or even systemswhich does notselectarouteatthe starting node,but rather decidesthe next node to travel to during thejourney.Accordingtothe categorizationsin figures 3and 4the routeplanningstrategycan be seen as areactiverealtimestate dependent approach,which is executed dynamically. Thekey of theapproachis aprocedure,Taghaboni-Dutta andTanchococall “selectnextnode”,which is incrementally executed by avehicle that decideswhich path segmenttotake next withrespect to aconflict-freejourney.The input to this procedureconsistsoflocal information, like thepossible next nodes, but alsoofglobalinformation like theestimated waitingtimes on subsequentnodes, whichare calculated usingqueuing theory.Asthe vehiclecalculates thedecisionindependently,their conceptual system canbeseen as one of thefirst agent-based routingsystems.The authorsevaluatethe performanceoftheir strategy in twosimplelayouts andcompare theresults with acomplete-route-planner, whichplans theentireconflict-freeroute before a vehiclestartstraveling.Theycome to theconclusion that acomplete-route-plannerworks better in complex layoutswhereas theincremental routeplanner is equallysuitablefor simple layouts. However, the incremental routeplanningislessfailure-prone and achieves significantly shorter responsetimes.The incremental routeplanner combines localand global informationtomakethe routingdecisions.Thus, this approach is notcompletelydecentralized. Nishietal. [82] have theirfocus on real-time systemsconsidering ause case of an AGVsystem in a semiconductorfab.Inadistributed manner each AGV calculates itsown initialroutingplanindependently.In asubsequentstepthese initialplans aresharedbetween thevehiclesand arechecked forfeasibility.Aslongas theplans arenot feasible,penaltiesare updatedand thereforethe routingdecisiongetschanged. This socalledreschedulinghas to be performed, whenever a new transportation requestentersthe system. Lauand Woo[73]explicitlyadoptthe concept of MAS, wherethe nodesofanetworkworkas cooperating agents.Theyintroduce ahybriddistributed routeplanningalgorithm forautomated material handling systems. Thealgorithm uses azone control logic andcomprises aroute discovery processwhich discovers feasible routes basedonmessage broadcast, amulti-attribute routeselection function andafault management function in case thechosenroute is blocked. Thedeveloped routingstrategyoutperforms severalother strategies whichthe authorscompare in asimulationstudy of ageneric loop-based layout. Theimplementationofthe approach canberegarded as decentralized. However, as thenodeagentsare able to shareinformation,the used informationisnot exclusivelylocal. Hallenborg [58] developaMAS foraconveyor-based baggagehandlingsystem.The idea canbetransferred to vehiclesystems. Theauthor focusesespeciallyonthe design of theagentsand theircommunication.Aroute 18 routingplans.Usually thevehicle withthe longestpath hasahigher priority.Inthe second subunitthe vehicles areactuallymoving. RuleslikeanAGV always hasto complete apass, before anotherAGV canenter thepass prevent deadlocks. Without anyspecific mentioning of theroute planning process andthe method used,Zhang et al. [118]propose acyber-physicalsystem based control approachfor adynamic routeexecution of multiple vehicles.The vehicles areabletointeractwitheach otherwithinagiven distance.The authorsdevelop acar-following method,where AGVs followother vehicles if thereare no intersections.Furthermore, they present amethodfor overtaking, if avehicle with ahigherpriorityisfollowing alow priority vehicle. Aconflict warningmethodand an avoidancestrategy aredeveloped forintersections,where decentralized basestationsmonitor thetrafficflow.Information is only exchangedwithinacertain radius.Therefore,this approach canberegardedasalmostdecentralized. Swarm-basedapproaches Swarm-based approaches arethe second type of approachesdiscussedfor decentralizedrouting. Withinswarm-based approachesespeciallyantbased algorithms or antcolonyoptimization(ACO) areoften saidtobeusefulfor decentralizedcontrol systems. Theirdevelopment started in the1990s and they useananalogytoreal-worldant colonies in trying to imitate theirindirectcommunication behavior via pheromone concentration. Theideaofcommunicating indirectlybymodifying theenvironment hasbeen named“stigmergy” in thescientific community[see 28]. Although thereare differentversionsofACO,they allsomehow rely on thestigmergy concept. In logisticsliterature, it is often argued that ideas of swarmintelligenceand antbehaviorshould be used forrouting in logistics networks.Two different representations of real worldsystem entitiesasants canbedistinguished. On theone hand artificialants canbeusedinanetwork to exploreitand findthe shortestpaths.Any vehiclecould ownanumberofants whichhelpthemtogatherand spread information. The AntNet algorithm[29]willbepresented as an example forthiskindofalgorithm.AnITinfrastructure would be required to runthe antalgorithm foreachvehicle in adecentralized system.These optimization runs arecomputationally expensive. This canbeespecially problematicwhenonlylimited planning datais available andthe real-timerequirementsare very high.Due to theselimitationsasecondlineofthought is possible. Deviatingfromthe initialintention of thealgorithm the vehicles couldalsobedirectlyrepresented by theants. As thevehiclesare notasnumerousasthe artificial ants theywould discoverthe network much slower. However, theresults of this routingstrategycannotbe expected to reachthe same performanceasthe first implementation opportunity. circle negotiations,asthe first vehiclemight have to negotiatewithfurther vehicles forits alternative route. To avoidtoo many negotiations specificrequirements aredefinedwhenanew negotiationisallowedatall. Duetothe long-distanceinformation exchange this approach is partly decentralized. An analytical approach is presentedbyDiganietal. [32].The authorsintroduce apathplanningalgorithm on atwo layerarchitecture.The first layer(topological layer) consistsofmultiplesectors (macro-cells), representing an entire vehiclelayoutinanabstract manner.The algorithmfor global path planningon this layercalculates themacro-cellsthatneed to be crossedonthe routetothe destinationsector. The calculationisdonebyeachvehicle separately using theD*-algorithm8.Thislayer of thealgorithm canbe categorizedasdistributed real-timestate dependent. Thesecondlayer (routemap layer) represents the actual path segments within each sector.Onthislayer theactualroute on thepathsegmentsiscalculated usinganA*-algorithm9andexecutedwithafocus on conflictand deadlock avoidance. This is reached in adecentralized solution withfocus on thecurrent sector only andthe differentprioritiesofthe vehicles in this sector.Therefore,the AGVs only sharelocal informationwithneighboring vehicles.SoDiganiet al.use adecentralized implementation whichrelies on global andlocal information, dependingonthe levelofcalculations to be done.Eventhough not stated explicitly,the approach is close to agent-based methods. Theapproachisfurther refined in Digani et al.[31]and Digani et al.[30]. Abdenebaouiand Kreowski[1, 2] introducegraphtransformational swarms to modeland routeina dynamicallychanginglogistical network. Theapproach hastwo phases.Inthe first phasethe layout is prepared in away that each node iscapable of indicating the shortestway to agiven destination. Therefore, AGVs cansolelyfollowlocal information. In thesecondphase theAGVsare following theshortestpaths avoiding collisions. As thevehiclesinthe routingphase rely on decentralizedinformation only andeachvehicle has itsown calculationunitthe approach canberegarded as decentralized. In Fantietal. [39] each vehiclecalculates theroute to itsdestination usingcommon algorithms,likethe A*- algorithm. Consequently,the vehiclehas information about thelayout includingcost factors. They propose an approach to avoidcollisionsand deadlocks, whichthey call coordinationproblem.Eachtimeunitisdivided into twosub units. In thefirstsub unit vehicles areable to communicatewithneighboring AGVs abouttheir 8The D*-algorithmdeterminesthe shortestpathbetween two nodesinadynamic network. Originally it wasdescribed by [101]. 9The A*-algorithmisapopular algorithmthatdeterminesthe shortestpathbetween twonodes in astaticnetwork.Itisthe basis forthe D*-algorithmand wasoriginallydescribed by [59]. 19 Research on Decentralized ControlStrategiesfor Automated Vehicle-basedIn-houseTransport Systems–aSurvey each vehiclehas multiple ants canbeseenaseither localorglobal. On theone hand,avehicle gets global informationvia explorationants. On theother hand, theseantsare spread andonlyaggregate information that is stored locallyinthe edges. As no centralunitis calculatingany solutions, theimplementationcan be regardedasdecentralized. Even though theapproach wasoriginallydesignedfor road traffic,the concept canbeapplied forvehicle transportsystems as well. Kanamori et al.[65]developed asimilarapproachin thefieldoftrafficmanagementwhich is alsoapplicable forin-house logistical systems. Theirapproach is based on theanticipatorystigmergy model. Having identified thedrawbackthatthe stigmergyconceptonlydisplays past information, theanticipatorystigmergy concept shares informationabout future intentions. Allrouting decisionscan be madetakingthese intentionsinto consideration. Ideasfromad-hocnetworks Thefollowing twoexamplesfromFay et al.[45]and ten Hompel et al.[105] show concepts that trytotransfer theideas of routinginmobile ad-hoc networks to logisticssystems, whichisthe thirdapproachpresented fordecentralized routing. Ad-hoc communication networks whichchangetheir configuration quickly andconstantlyare importantareas of research.There arehugestructuraland behavioral similarities between logisticsnetworksand communicationnetworks. As alot of research hasalready been accomplishedon routingincomplex communicationnetworksthe idea of transferring theseinsightstologisticsnetworksis extremelyappealing.Theyprovide analogiestothe dynamics in complexlogistics systems. Logistics entities travel in logisticsnetworkslikedatapackets in communicationnetworks. But besides allsimilarities,there arealsoseveral distinctivecharacteristicswhich need to be considered anddonot make thedevelopment of decentralized logisticsrouting protocolsaneasytask[see90, 105]. Johnstoneetal. [64],who developadynamic routing policy based on learning agents,orScholz-Reiter et al.[90], whopropose aconceptfor ageneral logistics routingprotocolare examples forthe transfer of communicationprotocols to thelogistics domain. We usethe work of Fayetal. [45] andten Hompel et al.[105] as afurther examplebecause they contain more detailed descriptions.Asthe knowledge of the communicationprotocols OLSR andDSR is essential forunderstandingthe twoexamples, we will give an extremelybrief andsimplified descriptionoftheir functionality. Theinterested reader is referred to the initial publications of Jacquetetal. [62] andJohnson andMaltz [63]. •optimizedlinkstate routing(OLSR): Thebasic idea of link stateprotocols is network nodesexchanginginformation abouttheir neighbors.Eachnodesensesits currentneighbors andusesamessagetobroadcast this information Generally, theapplicabilityofthe algorithmalso dependsonthe networkstructure.For example, baggagehandlingsystemshavearatherlow densityof connectionswhenbeing comparedtocommunication networks.The usageofthe ant-basedrouting is thereforelessappropriate[58]. AntNet wasdeveloped toapply ACOfor routingin communicationnetworks. SeeDiCaroand Dorigo [29] foradetaileddescription of theAntNetalgorithm.In thefollowing itsprocedure is explainedbriefly, however otherversionsofant-based routingexist. (1)Artificial ants startatregular intervals from each node in the network. Each anttries tofind theshortestpathtoa randomly assigned destinationnode. (2)Ateachswitch theant selectsits next node basedonlocal, privateand heuristic information. Theantsdonot communicate witheachother butuse theinformation that hasbeen stored in theenvironment,i.e.based on stigmergy. Theant stores itschosenroute nodesand additional information, e.g. thetraveltime. (3)Onceitarrives at itsdestination theant travelsbacktothe starting point of itsjourney.Ittakes theexact same path back.During thejourney thelocal knowledge of each visited node is updatedbased on informationwhich theant collected andthe qualityofthe followedpath. (4)The artificial antdiesonceitreturns to thesource node. Thecoreelementsfor routingthe artificialantsand formakingthe directiondecision(step 2) areprobability tables at each switch.Theycontain aprobability for choosing oneofthe neighbornodes dependingonthe currentdestination to be reached. Theseprobability tables representthe pheromoneconcentration. A directionistaken basedonacombination of this probabilityand thequeuelengthofthe nextlink. Once an anttravels backwardstoits initial starting pointitgives feedback about thequality of the foundsolutionand theprobability tables areupdated accordingly. Variousdifferent feedback functions have been developed andtested. It should be noted that theartificialantsare complementarytothe data packages whichare routedthrough acommunication network[seee.g.110]. But it needstobe considered that theAntNetalgorithm hasbeendeveloped as an optimizationalgorithm. Claeset al.[24]propose analgorithmfor decentralized anticipatory routinginroadtrafficwhich is basedon theACO.Eachvehicle lookingfor aroute in thetraffic networkhas differentkinds of artificialantsashelpers. Theso-calledexploration ants are“asking”eachedge aboutassumeddurations forcrossing on acertain time pointand cantherefore calculated thefastestpathto thedestination.Ifsuchapath is defined, theintention ants will inform thesingleedges about thearrival of thevehicle in acertain time span enabling theedgeto present thisinformation forfurther explorationants. This implementation is close to thetime-window based routeexecution andthe statedependent distributed routeplanning, we definedabove.The information levelinthisimplementationofanant algorithm, where 20 routingthanfor thedecentralized routingstrategy. ten Hompel et al.[105] also useabaggagehandling system simulation to testtheir routingstrategies. They developamulti-agent controlsystem based on theconcepts of theDSR algorithm. Butasseveral adjustmentstothe initialbaggagehandlingsystems arerequiredtoensureanimplementation, they do not analyzethe logistical performanceasthe results could notbetransferred to areal-world scenario. They focus rather on theamount of messages whichistransmitted during thesimulationruntime.Bothauthors realize that besides finding acertain routewiththe help of the adjusted communicationprotocols,itisalsonecessary to balance theloadifthereexist several routes to one destination. ten Hompel et al.[105] implement atrafficcount methodology. They propose usinga utilityfunctionwhich models thetrade-offbetween the standardtraveltimeonaroute andthe currenttraffic on this route. Thefunctionisnot explicitly stated. Fayetal. [45] useaprobabilityfunction. It uses the expected travel timesonalternative pathstothe current destinationasadecision criterion. Theaim is to usethe fastestpathasthe preferred solution,i.e.withhighest probability. If multiple routes with moreorlessequal travel time areavailable,the load should be distributed equally to them andevenroutes with rather long travel time have to be chosenonceinawhile in orderto collectinformation aboutthe currentnetwork status, i.e. thecurrent travel time. Formakingthisroutechoice decision theoverall travel time from thecurrent node to thedestination viathe differentalternative pathshas to be known. This meanslocal informationhas to be aggregated. Excursus:Freeranging vehicles Acurrent trendinthe sector of AGVrouting are so-calledfreerangingvehicles, whichmeans that vehicles do notfollowaphysicalorvirtual guidance. This leadstoabetter spaceutilization andahigher layout flexibility,but morecomplex controlstrategies areneeded.Asfree-rangingvehiclesdonot exactly fit thescope of this survey only asingleexample is mentioned. Demesureetal. [27] propose an agentbasedapproach forrouting free-rangingvehicle in areaswithout predefined path.The approach is based on twosteps.Inthefirststep, acentral controller uses global informationtocalculate thetrajectoryfor a specificAGV.Thistrajectoryshows theintention of thevehicle andissharedwiththe environment, e.g. the othervehicle. In thesecondstepofthe approach,the trajectory of neighboring vehicles arecoordinated in a distributed/decentralized manner.Ifconflictsbetween multiple vehicles areexpected, theirtrajectorieswill be updatediterativelyaccording to transportpriorities. Thesecondsteptherefore serves as adecentralized collision avoidanceand leads to ahugecomplexity reduction. Regarding theinformation used,the approach is based on global andlocal information– dependingonthe step of theapproach. in thewhole network. Having received this informationfromall networknodes,eachnodeis able to maintain itsown graphofthe networkand calculates arouting tablewiththe shortestpaths. Theneighborinformation is updated periodically to keep thelocal routingtablesuptodate. The optimized link stateprotocolusesthe conceptof multipoint relays to reduce thecommunication overheadfor theinformation broadcast.Asstated above, theOLSRcan be categorizedasaproactive distributedreal-time statedependent method for routediscovery. •dynamic source routing(DSR): This routingstrategyhas been used in various wiredand wireless environments.Toimplement dynamicsource routingtwo differentroutinesare required:route discoveryand routemaintenance. Each source node keepsacache of known routes (withanexpirationdate).Whenaknown routeexpires or apacketneedstobesenttoan unknowndestination,the source triggersthe route discovery process. Aroute requestisbroadcasted andforwardedfromnodetonodeaccordingtoa certainset of rules. Once theroute requestreaches itstarget, thelatter returnsaroute replywhich contains allthe nodesthatneedtobevisited. In communicationnetworksthe hopcount is more relevant than thedistance10.Whenusing dynamic source routing, thereare no periodic updates of the routes as in otherrouting protocols. Therefore, a routineisrequiredwhich checks if theroutes in thecache arestill valid. This routemaintenance is implementedasahop-by-hopacknowledgment or an end-to-end acknowledgment.Ifthe acknowledgment process fails, an errormessage will be returnedtothe source andthe routes in thecache will have to be updated.Asstated above,the DSRcan be categorizedasareactive distributedreal-time statedependent method for routediscovery. Allinall,the proactiveprotocolhas theadvantage that aroute is immediatelyavailable when required. On theother hand DSRcreates less communication overhead. Fayetal. [45] transfer theideas of OLSR to a baggagehandlingapplication.Theyapply arealworldsimulationmodel to testthe functionalityof theiralgorithm.Asthe computationalperformance is notsufficient forsimulatingthe complete baggage handling system,theyonlyconsideracertainsection. This reducesthe number of vehicles in thesystem from 400to14. Theonlyresults whichare shownconsider adisturbancescenario. Theperformance loss afterthe breakdown of apathsegment is bigger forthe central 10 This canalsobeaninteresting aspect forvehicle-based transport systems. Depending on thenetwork topology, a(virtual) path layout canalsoconsist of equidistant pieces. 21 Research on Decentralized ControlStrategiesfor Automated Vehicle-basedIn-houseTransport Systems–aSurvey Nevertheless, trulydecentralized approaches were mentionedrarelyasmostapproachesuse some kind of communicationand thereforedonot rely on local informationonly. However, theamount of data that needstobeexchanged foraload-vehicleassignment seemstobemanageablein(partly)centralized systems. Theliteratureabout emptyvehicle balancing was less extensive.The approaches canbedivided into aplaning andcontrolling aspect,which arelinked closely. Avariety of publications dealtwiththe balancingofempty vehicles in overhead hoisttransport (OHT)systems. Allinall,some of theapproachescan be regardedastruly decentralized. It couldbeseen that most publications on decentralizedcontrol of vehicle-based transport systemsdealwithrouting.Thisisalogical consequence, sincethe effort in communicationand complexity of therouting problemsolutioncan be very high.Approachesare either basedonthe multi-agent or swarm-based paradigm or trytotransfer ideasfrom ad-hoc communicationnetworkstologistical systems. Decentralized routingconcepts generallymakeuse of adistributed implementation,but usuallyrelyatleast to acertain extentoninformation sharingorglobal information. In general, many of thementionedpublications areofarather conceptual nature,which meansitis only described howasystemshould work.Aprove offeasibility or advanced performancemeasuring e.g. in comparisontoacentral benchmark strategy is often lacking. Furthermore,the complexity of the regarded(simulation) models is often very low. As a consequence, thefeasibilityofthe proposed control strategies in real-world applications oftenremains unclear. Thereisadefinitelackofcontributionsthatmention andanalyze emergent system characteristics. Based on thedecentralized paradigm, theseshould be observable. This seemstobe an importanttopic,as emergent behavior is notnecessarily beneficialfor the system performance. It rather makesasystem harder to control. Theidentified shortcomings lead to thefollowing directions forfutureresearch: •Further analysis of decision making basedonlocal information: In general, it needstobeevaluated in detail if the pure usageoflocal informationcan be meaningful. Hence,the trade-offbetween communication overhead forinformation exchange andsystem efficiencyneedstobeanalyzedwhenusing different amountsofinformation. •Detailedperformance analysis: It canbestated that typical characteristicsofrealworldapplication areusually notsufficiently taken into account. Examples arespecific transport patternorvarious path networks.Consequently, decentralizedconceptsneedtobeanalyzedin more realistic testorsimulationsystemsinorder 2.3.3. Summary Table3shows theoverviewofthe literatureconcerning thischapter.MAS arethe mostwidelyusedand promising approachesconcerningdecentralized routingimplementations. Table3:Literature overview ordered by topicsfor routing Topic Correspondingliterature Multi-agentsystems[30–32, 58,60, 69,73, 82, 94,95, 103, 106, 118] Swarm-based[24,28, 29,58, 65,110] Ad-hoc networks [45, 64,90, 105] Other [1, 2, 27,39] Allinall,itcan be stated that trulydecentralized approaches includingadecentralized implementation andlocal informationdoalmostnot existinrouting literature. Enabling asensitive routediscovery, at leastthe path layout needstobe knowneitherby thevehicle or by path nodes. Advanced tasks, like a conflictavoidance or some kind of routebalancing relies on adirectorindirectcommunication between differententitiesfurther violatingthe decentralized concept. Nevertheless,some approaches rely on some kind of compromise usingonlyregionalinformation forroute discoveryand vehiclecommunication. As aconsequence advantages of non-decentralized approaches areachievedand thecommunication effort is stilllimited. 3. CONCLUSION ANDFUTURE RESEARCH In this paper theavailable scientificliteratureonthe decentralizedcontrol of vehiclesystemsinin-house logisticshas been reviewed.The focuswas on online systemsthatworkwithout anypre-arrival information aboutfuturetransportrequests.The main objective wastoanalyze existingdecentralized concepts and identify fieldsfor future research.Inadditionto providing ageneral overview, it wasinvestigated if existing decentralizedconceptstruly basetheir decision making processonlocal informationonly. Threedifferent controlstrategyproblemsfor vehiclebasedin-housetransport systemswereanalyzedin detail: (1)load-vehicleassignment, (2)empty vehicle balancing and(3) routing. Thefirsttwo problems aremergedtothe dispatchingproblem.Eachcontrol problem wasanalyzedinasubsectionconsidering basicsand majorcategorizations as well as asegment on relevant literature. Regardingthe load-vehicle assignment the approachescould be dividedintolayouttransformation approachesand multi-agentsystems(MAS) witha majority of publications in thefield of thelatterone. 22 SymposiumonTransportationAnalysis,(Phuket, Thailand).2007(cit. on p. 21). 5. Aeschbach, P. et al.“Balancingbikesharing systemsthrough customercooperation –acase study on London’s Barclays CycleHire”.In: 2015 54th IEEE Conference on Decision and Control (CDC).201554thIEEE ConferenceonDecision andControl (CDC). 2015,pp. 4722–4727. doi: 10.1109/CDC.2015.7402955 (cit.onp.17). 6. Le-Anh,T.and de Koster,M.Multi-attribute dispatchingrules forAGV systemswithmany vehicles. 2004 (cit.onpp. 15,17). 7. Le-Anh,T., de Koster,M., andYu, Y. “Performance evaluation of dynamicscheduling approaches in vehicle-basedinternaltransport systems”.In: InternationalJournal of Production Research 48.24(2010), pp.7219–7242.doi: 10.1080/00207540903443279 (cit.onp.7). 8. Le-Anh,T.and de Koster,M.“Areviewof design andcontrol of automated guided vehicle systems”.In: European Journal of Operational Research 171.1(2006),pp. 1–23.doi:10.1016/j. ejor.2005.01.036(cit. on p. 7). 9. Arsie, A.,Savla,K., andFrazzoli, E. “Efficient RoutingAlgorithmsfor Multiple Vehicles WithnoExplicitCommunications”.In: IEEE Transactions on Automatic Control 54.10(2009), pp.2302–2317.doi:10.1109/TAC.2009. 2028954 (cit.onpp. 11,13). 10.Arsie,A.and Frazzoli,E.“Efficient routingofmultiplevehicleswithnoexplicit communications”. In: InternationalJournal of Robust andNonlinear Control 18.2 (2007),pp. 154–164. doi: 10.1002/rnc.1258 (cit.onpp. 11, 13). 11.Ayanian,N., Rus, D.,and Kumar, V. “Decentralized Multirobot ControlinPartially KnownEnvironmentswithDynamic Task Reassignment”. In:IFAC Proceedings Volumes 45.26 (2012),pp. 311–316.doi: 10.3182/20120914- 2-US-4030.00029 (cit.onpp. 12,13). 12.Bartholdi,J.J.and Platzman,L.K.“Decentralized ControlofAutomated Guided Vehicles on a Simple Loop”. In: IIETransactions 21.1 (1989), pp.76–81.doi:10.1080/07408178908966209 (cit. on pp.8,13). 13.Berman, S. andEdan, Y. “Decentralized autonomous AGVsystem formaterialhandling”. In: InternationalJournal of Production Research 40.15(2002), pp.3995–4006.doi: 10.1080 /00207540210146990(cit. on pp.11, 13). 14.Boppana,R.V.and Konduru, S. P. “A nadaptive distance vector routingalgorithm formobile, ad hocnetworks”.In: ConferenceonComputer Communications.Vol.3.2001, 1753–1762vol.3. doi: 10.1109/INFCOM.2001.916673 (cit.onp. 20). 15.Bozer,Y.A.andSrinivasan, M. M.“Tandem AGVsystems: apartitioningalgorithm and to broadly verify theirfunctionality andassess whethertheyare applicable in real-world transport systems. In this contextthe emergent system behavior canbeanalyzedand comparisons with othercontrol systems, e.g. acentral benchmark approach arepossible. Therefore, it is important to define objectivelyclear standardproblemsfor assessingvehicle controlstrategiesonthe basisof typical real worldsystems. •Basis of decision-making: Implementing decentralizedsystemsinrealworld scenarios is challengingasthere is alack of methodsfor applying thedesignofthe control system andchoosingthe levelof(de)centrality. Furthermore, some of thebenefits of decentralized systemsare alsodifficulttoquantify andmeasure like robustness,scalability or redundancy. However, thesecharacteristicscan have adecisive impact on theperformance of adecentralized system andasaconsequencetheyinfluencethe decision foramorecentralized or decentralized controlsystem architecture.Aprocedure (design of experiments) foranextensive comparison of qualitativeand quantitativeindicatorsfor variouscontrol approaches need to be developed. Additionally,thisprocedure canbeapplied forthe standardproblem mentionedabove. •Mixed operations scenarios: As vehiclesystemsare flexiblebynaturetheyare often appliedincombination with othersystems andconsequentlywithvarious paradigms of controls.Asdifferent connectedsystemswill strongly affect each other, this raisesthe question of strategies formixed systems. REFERENCES 1. Abdenebaoui, L. andKreowski, H.-J. “Decentralized RoutingofAutomated Guided Vehicles by MeansofGraph-Transformational Swarms”. In: DynamicsinLogistics.Ed. by M. Freitag, H. Kotzab,and J. Pannek.Cham: Springer InternationalPublishing, 2017, pp.457– 467. doi: 10.1007/978-3-319-45117-6_40 (cit.on pp.24, 28). 2. Abdenebaoui, L. andKreowski, H.-J.“Modeling of decentralizedprocesses in dynamiclogistic networks by meansofgraph-transformational swarms”. In: LogisticsResearch 9.1(2016). doi: 10.1007/s12159-016-0147-6(cit. on pp.24, 28). 3. Abolhasan, M.,Wysocki,T., andDutkiewicz, E. “A review of routingprotocols formobileadhoc networks”. In: Ad HocNetworks 2.1(2004), pp. 1–22.doi: 10.1016/S1570–8705(03 )00043-X (cit.onpp. 19,20). 4. Adacher, L.,Flamini,M., andNicosia,G. “Decentralizedalgorithmsfor multiple path routinginurban transportation networks”. In: 23 Research on Decentralized ControlStrategiesfor Automated Vehicle-basedIn-houseTransport Systems–aSurvey of Public Transportation 12.4 (2009),pp. 41–56. doi: 10.5038/2375-0901.12.4.3(cit. on p. 17). 27.Demesure, G. et al.“DecentralizedMotion Planningand Scheduling of AGVs in an FMS”. In: IEEE Transactions on Industrial Informatics 14.4 (2018),pp. 1744–1752. doi: 10.1109/ TII.2017.2749520(cit. on pp.27, 28). 28. Dhillon, S. andVan Mieghem, P. “Performance analysis of theAntNetalgorithm”. In: Computer Networks 51.8 (2007),pp. 2104–2125. doi: 10.1016/j.comnet.2006.11.002(cit. on pp.24, 28). 29.DiCaro, G. andDorigo, M. “AntNet: Distributed stigmergetic controlfor communications networks”. In: JournalofArtificialIntelligence Research 9(1998), pp.317–365 (cit.onpp. 25, 28). 30.Digani, V.,Sabattini,L., andSecchi, C. “A Probabilistic Eulerian Traffic Modelfor the Coordination of Multiple AGVs in Automatic Warehouses”.In: IEEE Robotics andAutomation Letters 1.1(2016), pp.26–32.doi: 10.1109/ LRA.2015.2505646 (cit.onpp. 24,28). 31.Digani, V. et al.“Ensemble Coordination ApproachinMulti-AGV SystemsApplied to Industrial Warehouses”.In: IEEE Transactions on AutomationScience andEngineering 12.3 (2015),pp. 922–934. doi: 10.1109/ TASE.2015.2446614(cit. on pp.24, 28). 32.Digani, V. et al.“Hierarchical traffic controlfor partiallydecentralized coordinationofmulti agvsystems in industrial environments”. In: Robotics and Automation(ICRA), 2014 IEEE InternationalConferenceon. IEEE,2014, pp. 6144–6149(cit. on pp.24, 28). 33.Dijkstra, E. W. “A note on twoproblemsin connexionwithgraphs”.In: Numerische mathematik 1.1(1959), pp.269–271 (cit.onp. 19). 34.Draganjac,I.etal. “Decentralized Control of Multi-AGVSystemsinAutonomous Warehousing Applications”. In: IEEE Transactions on AutomationScience and Engineering 13.4 (2016),pp. 1433–1447. doi: 10.1109/TASE.2016.2603781(cit. on p. 2). 35.Egbelu, P. J. “Positioningofautomated guided vehicles in alooplayouttoimprove response time”. In: European JournalofOperational Research 71.1 (1993),pp. 32–44(cit. on pp.14, 17). 36.Egbelu, P. J. andTanchoco, J. M. A. “Characterization of automaticguidedvehicle dispatchingrules”. In: InternationalJournal of Production Research 22.3 (1984),pp. 359–374. doi: 10.1080/00207548408942459(cit. on p. 6). 37.Erol, R. et al.“Amulti-agent basedapproach to dynamicschedulingofmachinesand automated guided vehicles in manufacturingsystems”.In: Applied Soft Computing 12.6 (2012),pp. 1720– performancecomparisonwithconventionalAGV systems”.In: European JournalofOperational Research 63.2 (1992),pp. 173–191(cit. on pp.8, 13). 16.Bruno,G., Ghiani,G., andImprota,G.“Dynamic positioning of idle automatedguidedvehicles”. In: JournalofIntelligent Manufacturing 11.2 (2000), pp.209–215 (cit.onpp. 15,17). 17. Caraballo, L. et al.“Theblock-information- sharingstrategyfor task allocation:A case study forstructure assembly withaerialrobots”.In: European JournalofOperational Research 260.2(2017), pp.725–738.doi: 10.1016/j. ejor.2016.12.049 (cit.onpp. 12,13). 18.Chaabane, A. B. et al.\Analyzingthe impact of keyparametersofvehicle management policies in aunifiedAMHS”.In: 2013 Winter Simulations Conference(WSC).2013, pp.3818–3828.doi: 10.1109/WSC.2013.6721741 (cit.onpp. 16,17). 19.Chang,S.-H. andEgbelu, P. J. “Dynamic relative positioning of AGVs in alooplayouttominimize mean system response time”. In: International JournalofProduction Research 34.6 (1996),pp. 1655–1673. doi: 10.1080 /00207549608904989 (cit.onpp. 14,17). 20.Chemla, D.,Meunier,F., andWolflerCalvo, R. “Bikesharing systems: Solvingthe static rebalancingproblem”. In: Discrete Optimization 10.2 (2013),pp. 120–146. doi: 10.1016/j. disopt.2012.11.005(cit. on p. 17). 21.Chen, T.-W.and Gerla, M. “Globalstate routing: anew routingschemefor ad-hoc wireless networks”. In: IEEE InternationalConference on Communications (ICC).Vol.1.1998, 171–175 vol.1. doi: 10.1109/ICC.1998.682615(cit. on p. 20). 22.Choi, H.-L., Brunet,L., andHow,J.“Consensus- BasedDecentralized Auctions forRobust Task Allocation”. In: IEEE Transactions on Robotics 25.4 (2009),pp. 912–926. doi: 10.1109/ TRO.2009.2022423 (cit.onpp. 9, 10,13). 23.Choudhury, R. R.,Paul, K.,and Bandyopadhyay, S. “MARP: aMulti-Agent RoutingProtocol forMobileWirelessAdHoc Networks”. In: AutonomousAgentsand Multi-Agent Systems 8.1(2004), pp.47–68. doi: 10.1023/B: AGNT.0000009410.57024.9a(cit. on p. 20). 24.Claes,R., Holvoet, T.,and Weyns, D. “A Decentralized Approach forAnticipatoryVehicle RoutingUsing Delegate Multiagent Systems”.In: IEEE Transactions on Intelligent Transportation Systems 12.2 (2011),pp. 364–373. doi: 10.1109/ TITS.2011.2105867(cit. on pp.25, 28). 25.Colling, D. et al.“Dezentrale Auftragserzeugung und-vergabefür FTF”.In: LogisticsJournal: Proceedings 2016.10(2016)(cit. on pp.10, 13). 26. DeMaio, P. “Bike-sharing: History, Impacts, Models of Provision, andFuture”.In: Journal 24 48.FIPAProtokoll.url:http://www.fipa.org/specs/ fipa00029/SC00029H.pdf (visited on 12/12/2018) (cit.onp.10). 49.Flämig, H. “Autonome Fahrzeugeund autonomes Fahren im Bereichdes Gütertransportes”. In: AutonomesFahren.Ed. by M. Maurer et al. Berlin,Heidelberg: Springer Berlin Heidelberg, 2015,pp. 377–398. doi: 10.1007/978-3-662- 45854-9_18 (cit.onp.2). 50.Floyd,R.W.“Algorithm97: ShortestPath”. In: Commun.ACM 5.6(1962), pp.345–. doi: 10.1145/367766.368168(cit. on p. 19). 51.Furmans,K., Nobbe, C.,and Schwab,M. “FutureofMaterialHandling–modular, flexible andefficient”.In: IEEE/RSJ International ConferenceonIntelligentRobotsand Systems. 2011 (cit.onp.1). 52.Gademann,A.J.R.M.and vandeVelde,S.L. “Positioning automatedguidedvehiclesinaloop layout”. In: European Journal of Operational Research 127.3(2000), pp.565–573 (cit.onpp. 15,17). 53.Gansterer,M.and Hartl, R. F. “Collaborative vehiclerouting:asurvey”.In: European Journal of OperationalResearch 268.1 (2018),pp. 1–12. doi: 10.1016/j.ejor.2017.10.023 (cit.onp.3). 54.Garey,M.R.and Johnson, D. S. Computersand intractability. 29th ed.New York:whfreeman, 2002 (cit.onpp. 2, 7). 55.Giordani, S.,Lujak,M., andMartinelli,F.“A distributed multi-agentproductionplanningand scheduling frameworkfor mobile robots”. In: Computers&Industrial Engineering 64.1 (2013), pp.19-30.doi: 10.1016/j.cie.2012.09.004(cit. on pp.10, 13). 56.Haas, Z. J. andPearlman, M. R. “The performanceofquery controlschemes for thezone routingprotocol”.In: IEEE/ACM Transactions on Networking 9.4(2001), pp.427– 438. doi: 10.1109/90.944341(cit. on p. 20). 57.Hahn-Woernle, C. “NeueAnforderungen für dieLogistik des21. Jahrhunderts”. In: Internet derDinge in derIntralogistik. Ed.byW. Günthner andM.ten Hompel.VDI-Buch. Berlin, Heidelberg:SpringerBerlinHeidelberg, 2010, pp.9–13. doi: 10.1007/978-3-642-04896-8_2 (cit. on p. 2). 58.Hallenborg, K. “Decentralized scheduling of baggagehandlingusing multi-agent technologies”. In: Multiprocessor scheduling theory and applications. Vienna: I-Tech Educationand Publishing, 2007 (cit.onpp. 15, 17,23, 25,28). 59.Hart, P. E.,Nilsson,N.J.,and Raphael, B. “A formal basisfor theheuristic determination of minimum cost paths”. In: IEEE transactions on SystemsScience andCybernetics 4.2(1968), pp. 100–107(cit. on p. 24). 1732.doi: 10.1016/j.asoc.2012.02.001 (cit.onpp. 10,13). 38.Fanti,M.P.et al.“Discrete consensusin networks withconstrained capacity”. In: 52nd IEEE Conference on Decision and Control. 52nd IEEE Conference on Decision andControl.2013, pp.2012–2017. doi: 10.1109/CDC.2013.6760177 (cit.onpp. 12,13). 39.Fanti,M.P.etal. “A decentralizedcontrol strategy forthe coordination of AGVsystems”. In: ControlEngineering Practice 70 (2018),pp. 86–97. doi: 10.1016/j.conengprac.2017.10.001 (cit. on pp.12, 13,24, 28). 40.Fanti,M.P.etal. \Assignmentofelectrical vehicles to charging stations by adistributed approach”.In: ControlConference(ECC),2014 European. IEEE,2014, pp.1888–1893(cit. on pp. 12,13). 41.Fanti, M. P. et al.“Discreteconsensus for asynchronousdistributedtaskassignment”.In: Decision and Control(CDC),2016IEEE 55th Conferenceon. IEEE,2016, pp.251–255 (cit.on pp.12, 13). 42.Fauadi, M. H. F.,Yahaya, S. H.,and Murata, T. “Intelligent combinatorialauctionsof decentralizedtaskassignmentfor AGVwith multiple loadingcapacity”. In: IEEJ Transactions on Electrical and Electronic Engineering 8.4 (2013),pp. 371–379.doi: 10.1002/tee.21868 (cit. on pp.10, 13). 43.Fauadi, M. H. F. M. “Agent-based material transportation scheduling of AGVsystemsand itsmanufacturing applications”. PhDthesis. Waseda University, 2012 (cit.onpp. 10,13). 44.Fay,A.and Fischer, I. “Dezentrale Automatisierungsstrategien fürGepäckbeförderungssysteme(DecentralizedAutomation Strategiesfor BaggageTransportationSystems)”. In: at –Automatisierungstechnik/Methoden und Anwendungender Steuerungs-, Regelungs-und Informationstechnik 52.7 (2004),pp. 335–341 (cit.onpp. 9, 13). 45. Fay, A.,Jerenz, S.,and Seitz,N.“Dezentrale Steuerungvon Transportsystemen in Analogie zumRouting in Datennetzen (Decentralized ControlofTransport Systems basedonDataRouting Mechanisms)”. In: at –Automatisierungstechnik 56.6 (2008).doi: 10.1524/auto.2008.0708 (cit.onpp. 2, 26–28). 46.Fazlollahtabar, H. andSaidi-Mehrabad, M. “MethodologiestoOptimize AutomatedGuided VehicleSchedulingand RoutingProblems: a Review Study”. In: JournalofIntelligent & RoboticSystems 77.3 (2015),pp. 525-545. doi: 10.1007/s10846-013-0003-8(cit. on p. 7). 47.Ferrero,F.etal. “Car-sharing services:An annotatedreview”.In: Sustainable Cities and Society 37 (2018),pp. 501–518. doi: 10.1016/j. scs.2017.09.020 (cit.onp.17).