Planning and control of autonomous mobile robots for intralogistics: Literature review and research agenda

ContentslistsavailableatScienceDirect

European Journal of Operational Research

journalhomepage:www.elsevier.com/locate/ejor

Invited Review

Planning and control of autonomous mobile robots for intralogistics:

Literature review and research agenda

Giuseppe Fragapane

, René de Koster

, Fabio Sgarbossa

, Jan Ola Strandhagen

aDepartment of Mechanical and Industrial Engineering, Norwegian University of Science and Technology, Trondheim, Norway

bRotterdam School of Management, Erasmus University Rotterdam, the Netherlands

a rt i c l e i nf o

Article history:

Received 12 June 2020 Accepted 8 January 2021 Available online 17 January 2021 Keywords:

Logistics

Autonomous mobile robots Planning and control Literature review Research agenda

a b s t r a c t

Autonomousmobilerobots(AMR)arecurrentlybeingintroducedinmanyintralogisticsoperations,like manufacturing,warehousing,cross-docks,terminals,andhospitals.Theiradvancedhardwareandcontrol softwareallowautonomousoperationsindynamicenvironments.Comparedtoanautomatedguidedve- hicle(AGV)systeminwhichacentralunittakescontrolofscheduling,routing,anddispatchingdecisions forallAGVs,AMRscancommunicateandnegotiateindependentlywithotherresourceslikemachinesand systemsand thus decentralizethe decision-makingprocess.Decentralizeddecision-makingallows the systemtoreactdynamicallytochangesinthesystemstateandenvironment.Thesedevelopmentshave influencedthetraditionalmethods anddecision-makingprocessesforplanningandcontrol.Thisstudy identifiesandclassifiesresearchrelatedtothe planningand controlofAMRsinintralogistics.Wepro- videanextendedliteraturereviewthathighlightshowAMRtechnologicaladvancesaffectplanningand controldecisions.WecontributetotheliteraturebyintroducinganAMRplanningandcontrolframework toguidemanagersinthedecision-makingprocess,therebysupportingthemtoachieveoptimalperfor- mance.Finally,weproposeanagendaforfutureresearchwithinthisfield.

© 2021TheAuthors.PublishedbyElsevierB.V.

ThisisanopenaccessarticleundertheCCBYlicense(http://creativecommons.org/licenses/by/4.0/)

1. Introduction

Inrecentdecades,thetechnologyinmaterialshandlinghasad- vanced rapidly. One major development is the evolution of au- tomated guided vehicles (AGV) into autonomous mobile robots (AMR). Since 1955, when the first AGV was introduced (Muller, 1983), the guiding system that forms the corepart of AGV ma- terial handling systems has evolved along various stages of me- chanical,optical,inductive,inertial,andlaserguidanceintotoday’s vision-basedsystem(Fig.1).Thisvision-basedsystemusesubiqui- tous sensors, powerfulon-board computers, artificial intelligence (AI) and simultaneous location and mapping (SLAM) technology, enablingthe device tounderstand its operatingenvironment and tonavigateinfacilitieswithouttheneedtodefineandimplement referencepointsinadvance.Thishasopenedanewdimension in navigationalflexibility.

Conventional AGVs can only follow fixed paths and move to predefined pointson the guide path (Fig. 1(a)–((f)). By contrast, AMRs can move to anyaccessible andcollision-free point within

∗Corresponding author.

E-mail address: [email protected] (G. Fragapane).

agivenarea (Fig.1(g)).Smallchangesdueto,forexample,a ma- chinelayoutchangewouldtypicallytakesubstantialtimeformost AGV guidance systems,cause periods of inactivity, andrisk eco- nomic losses and decreases in productivity. AMRs, however, can adaptquicklytochangesintheoperatingenvironment.

The need for more flexibility has driven the development of AMRs,notonlyinnavigationalabilitybutalsointheservicesthey can provide. Compared to AGVs, which have been characterized as computer-controlled, wheel-based load carriers for horizontal transportationwithouttheneedforanonboardoperatorordriver (Le-Anh&DeKoster,2006)tobeusedforrepeatedtransportpat- terns,AMRscanprovidemanyservicesbeyondmeretransportand materialhandlingoperations, such aspatrollingandcollaborating with operators. Combined with the ability to take autonomous decisions,thesemobile platformscan offerflexible solutions. The autonomy of AMR vehicles implies continuous decision-making about how to behave in an operating environment consistent withprevailing rules andconstraints.A substantial challenge lies in the complete absence of a human supervisor who knows the system’s limits. An AMR must, therefore, monitor its own state autonomously,spotpotentialsystemfaultsandreactappropriately.

The AMR’s hardware and control software facilitate advanced capabilitiesforautonomousoperation,notonlyfornavigationand

https://doi.org/10.1016/j.ejor.2021.01.019

0377-2217/© 2021 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )

Fig. 1. Guiding systems for AGVs and AMRs (top view of the system).

objectrecognitionbutalsoforobjectmanipulationinunstructured anddynamicenvironments (Hernández etal.,2018). Thesedevel- opments haveledtothedecentralization ofdecision-makingpro- cesses. Comparedto anAGV systeminwhicha centralunit takes control decisions such as routing and dispatching for all AGVs, AMRs can communicate and negotiate independently with other resources like machinesandsystems such asenterprise resource planning or material handling assessment and control software (Fig. 2), andtake decision themselves. Thisreduces the need for centralized, external control (Furmans & Gue,2018). The goal of theAMR decentralizeddecision-makingisto reactdynamicallyto demand or changes andallow each vehicle tocontinuously opti- mizeitself.

TheAMRconceptisnotnew.ThefirstgenericAMRpatentwas issuedin1987(Mattaboni,1987).Sincethen,ithasbeendiscussed mainlyinthefieldsofroboticsandinformationtechnology,butit hasrecentlyemergedinlogisticsapplicationsanditsimportanceis expectedtoincreasesignificantlyinthenearfuture.Infact,ithas beenestimatedthatmorethan13,000AGVandAMRsystemshave been installed globally(Bechtsis etal.,2017). Currently, hundreds of suppliers worldwide supply autonomous robots. Through the use ofgenericcomponents,e.g. sensors,driving andsteeringsys- tems, batteries, manipulating equipment and processing devices, basicvehicles canbe assembledatafairly lowcost.Traditionally, the main sectorswithAGV applicationswere manufacturing sys- tems, warehouses and container terminals (Le-Anh et al., 2006),

but their areas of applicationand the services they can provide have increased significantly. AMRs can now be found in indus- trial,healthcare,hotel,securityanddomesticsettings,performing awiderangeoftasks.

Besides machine loading and transportation tasks, AMRs can beused asassistive systemsasthey caninteractwithhumansas coworkers(Fig.3(c)).Inautomotivecarassembly,AMRswithma- nipulatorscanassistworkersandtogethermountheavypartsofa carbodyatdifferentstagesalongtheassemblyline(Angereretal., 2012),thusincreasingbothproductivityandqualitywhilesimulta- neouslyreducingfatiguelevelsamongworkers.

Inwarehouses,AMRscollaboratewithoperators inorderpick- ing(Fig.3(p)).AMRscarryafew smallcontainersinsidethepick- ingareasandstopinfrontofthelocationwheretheoperatormust pickthenextitem.Theythen movetothenextlocationindepen- dently. When all itemsin a givenorder havebeen collected, the AMR autonomouslytravelsto thepackingandconsolidation area, whereitisemptiedandreassignedtoanewsetoforders(Meller etal.,2018; Azadehetal.,2019a). Thistechniqueenablesa zone- pickingstrategythatoptimizesoperatorandAMRpickingandtrav- elingefficiency.

The strength of AMRs is especially well demonstrated in narrow-aisle,high-traffic environments like those found in ware- houses and hospitals. AGVs do not enter wards or departments forsafetyanddelivery performance reasons;instead,they deliver goodsclosetotheentrance.AMRs,bycontrast,havegreateraccess

Fig. 2. Centralized AGV control and decentralized AMR control.

Fig. 3. Types of AMRs and examples of applications.

to nearly all departments and can be used for critical and just- in-timedeliverieslikecancermedicines orradioactivetherapeutic anddiagnosticmedicinesofwhichthecorrectdosedecaysrapidly (Fig. 3(q)). In addition to transport tasks, they can provide ser- vices, such asdisinfectingrooms,telemedicineorguidance assis- tance(Fig.3(s,t,x))(Fragapaneetal.,2020a).AMRscaneffectively reducemanualmaterialhandlinginhospitals,providingmoretime for patient-related activities andincreasing value-added time for direct-carestaff.

The activities performed characterize and divide AMRs into three main groups. They provide (I) material handling (retrieve, move,transport,sort,etc.),(II)collaborativeandinteractive activi- tiesand(III)full-serviceactivities(Fig.3).Theycomewiththefol- lowingattributes(Hernándezetal.,2018;Indrietal.,2019):

• Decentralized control: applying methodologies and technolo- giesofintelligent,cognitiveandbehavior-basedcontroltomax- imizeflexibilityandproductivityperformance.

• Platformoperation: providing a platform to extend an AMR’s capabilitiesandapplicationpossibilitiesbeyondcommonmate- rialhandlingactivities.

• Collaborative operation: working together with humans or otherAMRsinaswarm.

• Easeofintegration:integratingfastandcost-efficientAMRsinto afactoryorotherfacility.

• Scalability:increasingordecreasingthenumberofAMRswith- outbeinghinderedbystructuralchange.

• Robustness: providing resilience, i.e.systems that can recover afterfailure.

Tosummarize,theauthorsproposeandusethefollowingdefi- nitioninthisstudy:

Autonomousmobilerobotsareindustrialrobotsthatusea decen- tralizeddecision-making process for collision-freenavigation to pro- videaplatformformaterialhandling,collaborativeactivities,andfull serviceswithinaboundedarea.

Theincreasing abilityofAMRstotake overtasksandactivities andthefactthatAMRsnavigate,operateandinteractwithhumans andmachinesdifferentlythanAGVsrequiresanewdecisionstruc- ture. Managersneedguidanceduringdecisionmakinginorderto achieveoptimalperformance.Forinstance,atthestrategicdecision level, it is essential to define the degree of control decentraliza- tionofassistivematerialhandlingactivitiesforAMRsincarman- ufacturing. At the tactical level in warehouses, work zonesmust be determined forcollaborativeAMRs.Atthe operationallevel in hospitals, safeand low contagion-risk AMR travel paths must be planned.

The literature on AMRs is fragmentedand hasa largely tech- nological focus. The lack of a unified, accepted definition among practitioners andresearchers has also hampered research in this field. AGVshavedominatedtheliteratureonvehicleplanningand control systems. Vis (2006) andLe-Anh et al. (2006) distinguish key decision areas, such as guide path design and determining the number and locations of pick-up and delivery points, while Bechtsis etal. (2017) providea literature reviewfocusing on sus- tainabilityaspectsinAGVplanningandcontrol.Thegreaterdegree ofautonomy,applicability,andflexibilityprovidedbyAMRsresult in alarge numberof differentdecisions onstrategic,tactical and operational level that must be taken, and thisnumbercontinues to grow. However, since their applications are not yet abundant, AMRs have not been investigated sufficiently from an academic perspective.ThecurrentmethodsofAGVplanningandcontrolre- mainto beanalyzed,anditisworthwhile toassesswhetherthey canbetransferred,extended,ormodifiedforAMRs.

Starting withtheliterature onAGVs,thepresentstudyidenti- fies andclassifiesresearch relatedto the planningandcontrol of AMRsandproposesanagendaforfutureresearchinthisfield.The focusisonthemainelementsofautonomy(i.e.decision-making), mobility(i.e.freenavigation)androbotics(i.e.providingservices).

Weexaminethefollowingresearchquestions:

• HowdothetechnologicaladvancesofAMRsaffectplanningand controldecisions?

• Whatare thedominantapproachesandmethodsinthelitera- tureonAMRplanningandcontrol?

• WhatfutureresearchisneededinAMRplanningandcontrol?

To answer these questions, we carried out a literature study that inventoried articles in refereed journals; English-language sources from online databases like ScienceDirect, Web of Sci- ence and Google Scholar were included. The following keywords (and their variants) were used: ‘Automated Guided Vehicle’, ‘Au- tonomous IntelligentVehicle’,‘AutonomousMobileRobot’,‘Mobile Robotic Fulfilment’, ‘Collaborative Mobile Robot’, ‘Mobile Service Robot’and‘PuzzleBasedStorageSystem’.Wethennarroweddown oursearch.First,wefocusedonlyonarticlespublishedinthelast 15 years. Older material on AGVs has been adequately covered in two literature reviewsby Le-Anhetal. (2006) andVis (2006), which describe the main methods and approaches before 2006.

Second,weexcludedconferenceproceedings,professionaljournals, book chapters and doctoral dissertations, since we assume that important research haseventually appeared inrefereedacademic journals.Third, we focused onhigh-impactjournalsandincluded only articles published in journals with a Scimago Journal Rank higher than 0.5. Next, we manually screened the titles and ab- stractsofall302remaining articles.Onlypaperswithfulltextsin EnglishandrelatedtoeitherAMRsorAGVs(ifrelevantandappli- cableforAMRs)wereincluded.Inthefinalstep,alltheremaining articles were full-textscreened to confirm their relevance to the planningandcontrolofAMRs.Examiningthereferencelists,some highlyrelevantarticles,citedmultipletimesbutnotidentifiedpre- viously,havealsobeenadded.Atotalof108articleswereincluded inthefinalreview.

Therestofthepaperisorganizedasfollows.Section2presents thecrucialtechnologicaladvancesofAMRsandexplainshowthey haveaffected theAGV decision areasanddecisions. InSection 3, we introduce a decision-making framework for AMRs indicating themainchangescomparedtoAGVdecisions.Section4describes the planning and control decisions and the operational research methodsapplied.InSection5,wequantifyandsummarizethecur- rentapproachestoidentifythegapsinliterature,andpresentde- tailedrecommendationsforfutureresearch areas.Weconcludein Section6.

2. TechnologicaladvancesimpactingAMRs

The evolutionofAGVs intoAMRshas becomepossible dueto new hardware(Section 2.1) and software (Section 2.2) technolo- gies.

2.1. Hardware

2.1.1. Sensors

AMRsare typically equippedwitha widearray of small,low- cost,andpower-efficientsensingtechnologiesprovidinginputdata forautonomousnavigation.IntegratedlaserscannerssuchasLight DetectionandRanging(LiDAR),3Dcameras,accelerometers,gyro- scopes,andwheelencoders, whichprovideinformationonwheel positions to calculate the distance that the robot has driven or turned,andcaptureandtransmitenormousamountsofdataabout the AMR’s immediate, extended and anticipated environments, along with its internal condition (De Silva et al., 2018). While LiDAR laser scanners provide a very precise distancepoint cloud relativetotheAMRinitsenvironment,3Dcamerasprovidewide- angle support that enables the visual recognition of obstacles.

These technologies have become popular due to their easy dy- namicusage andspeedyrenderingof results.ComparedtoAGVs, AMRsarenot‘blind’,buthavefullrecognitionoftheenvironment.

Thisaffectsdecisionsaboutguidepathchoice,collisionanddead- lock prediction and avoidance, and failure management. Sensing theenvironmentallowsan AMRtoassist,collaborateandinteract withhumansandmachines,whichmeansmoredecisionstomake.

2.1.2. Robotlocomotionmechanism

The locomotion mechanism of a robot has a strong impact onits stability, manoeuvrability,andkinematics. MostAGVshave either one steerable traction wheel in the front with support- ing wheels in the back or two independently driven wheels with several, omnidirectional supporting wheels, thus providing a cost-efficient and low complexity trade-off against the above- mentionedfactors. Differentcombinations,configurations, andar- rangementsofAMRwheelsorlegsexist.Ahighlevelofmanoeu- vrabilitycanbeachievedbypoweringSwedishorsphericalwheels orincreasingthenumberoflegs,thusallowingtherobottomove atanytime inanydirectionalong thegroundplane regardlessof theorientationoftherobot (Siegwartetal.,2011).Sincemanyin- tralogisticsactivitiesrequireahighlevelofstability,wheeledAMRs aretypicallythefirstchoice.However, movementinrough terrain istypically attemptedwithlegged AMRs.Severalcompanies have presented legged AMRs for activities in intralogistics; examples include SPOT by Boston Dynamics (https://www.bostondynamics.

com/) andANYmalC by ANYbotics(https://www.anybotics.com/).

TheincreasedflexibilityinthemovementandpositioningofAMRs requiresappropriatepathplanningmethods,andtheservicepoints shouldbecorrectlydetermined.

2.1.3. Batteries

Higher energy capacity and improvements in charging meth- ods, rangingfromconventional plug-in connector powersupplies

to wireless powertransfer, have a significant impact on the bat- tery management of AMRs.Studies indicate that wireless power transfer can be applied in manycases, eliminating the need for wired connections(Huangetal.,2018).Alimitedbatterycapacity andlongchargingtimeswereweakpointsofAGVsandreduceper- formance, utilization, and computational power. In addition, tra- ditionallead-acidhigh-capacity batteries requiredincreasedvehi- cle size. The newhigh-capacity batteries (e.g.lithium-ion) enable longer operational time andprovidemore powerfor thecalcula- tionsneededforautonomousnavigationandoperations.Theyalso allowtheAMRstobesmaller(thisalsoholdsforthenewestAGVs) andthustobedeployedinnarrow-aisleareas,orevendirectlyun- derneath multiple loads storedclosely in deep lanes (Lamballais et al., 2017). With these technological improvements, the impor- tanceofbatterymanagement hasdeclined somewhat,althoughit maystillberelevantin24/7operations(Zouetal.,2018).Bycon- trast, reliable system operations, including battery management, have gained research interest. In addition, the increased battery powerencouragesmoreintensiveschedulingdecisions.

2.1.4. Manipulatingequipment

By combining AMRs with different manipulating equipment into a singleunit,newservices andmaterial handlingoperations can beperformed. RoboticmanipulatorsenableAMRsnotonlyto liftunitloadsbutalsotopicksingleitems(Shahetal.,2018).AMRs can collaboratewithhumansandotherAMRs,tocarry out trans- portationtasksjointly(Lee&Murray,2019;Machadoetal.,2019).

TheextendedrangeofoperationsthatAMRsoffermustbeplanned overboth theshortandlongterm.Thisincludesmakingnewde- cisionson howto providetheseservices, developingmethodson how AMRs cancollaborate, andintegratingtheir scheduling with productionschedulestoensurecollaborationattherighttimeand place.

2.1.5. Processingdevices

The AMR’sability to navigate andoperate ina dynamicenvi- ronmentresultsfromitscapacitytomakereal-timedecisions.Pre- viously, intelligent decision-making capabilities in mobile robots were limited because ofthe significant computational power re- quired. With the introduction of ultra-low-power AI processors, real-time decision-making for AMRsbecame possible (Kim et al., 2017).Today,powerful AI-focusedprocessor architecturessuch as the Intel Nervana, NVIDIA Xavier and Kneron AI SoC are widely available for vision recognition of face, body, gesture, object, or scene.Thisdevelopmentespecially affectstheoperationallevelof decision-making in AMRs.Enabling calculationsof complex deci- sions allows newwaysof dynamicrouting andscheduling,navi- gatingandclassifying,andreactingtoobstaclesappropriately.

2.2. Software

2.2.1. Simultaneouslocalizationandmapping

SLAM, which is a supportive technology forreal-time naviga- tion,encompassesthetwoactivitiesofcreatingdetailedareamaps of the environmentand calculatingthe position ofan AMR on a map (Bloss,2008).Themappingprocess converts3D pointclouds retrieved fromthe scanningsensorstoa referencemapwhilefil- tering the dynamicobstacles. Combining thesensinginformation toaccuratelydeterminetheAMR’slocationatanytimehasproven to be a difficult challenge. In recent years, a breakthrough was made through the application of Kalman filter technology. Esti- mationsfromdifferent sensorsources mustbe combinedto gen- erate a probability distribution over all possible robot locations and to predict a robot’s position and orientation (Bloss, 2008).

TheKalmanfilterusesarecursivealgorithmtocorrectthepredic- tion overtime.Using severalmeasurement sources,measurement

noiseandsensorinaccuracyissuescanbeovercome(Pratamaetal., 2016). For high accuracy and reliability, SLAM can be supported indoorsby real-time locationsystems usingultra-widebandtech- nology,andoutdoorsbyglobalpositioningsystemsusingnetwork satellitesplacedinorbit.Applyingtrilaterationandmultilateration allowstheidentificationoftheexactpositionsoftheAMRs.

2.2.2. Motionplanning

Motionplanningis an essentialpart ofthevision-based guid- ance systems and manipulation of equipment. Using the input of the environmental representation, the motion planner can calculate the robot’s size and dynamics anda feasible, collision- free path fromthe initial point to the final position (Karaman &

Frazzoli, 2011). Further, the motion planning algorithms provide speed and turning commands to the vehicle actuators such as wheels ormanipulator to reach theset of guidancepoints along the path. Sensors and the SLAM technology allow the AMR tra- jectorytobe trackedandprovidefeedbacktocorrectitsposition.

In dynamic environments, the motion planner allows the AMR to adapt to traffic or congestion by reducing speed, or even by stoppingthevehicle.Ifplannedpathsarenolongerfeasibledueto anemergingobstacle,anewcollision-freepathwillbegenerated.

Decisions that must be made aboutthe guide path,routing, and obstacle avoidance are all taken by the AMR itself. Severalopen sourceplatformsprovidecodesforthecontrolofAMRs(andother robots). Examples include Robotics and Autonomous Systems by Intel (https://01.org/robotics-autonomous-systems), the RobotOp- eratingSystem(https://www.ros.org/),YetAnotherRobotPlatform (https://www.yarp.it/) andtheMobile Robot ProgrammingToolkit (https://www.mrpt.org/).

2.2.3. Artificialintelligence

Facilitatedbyhardwaredevelopments,AItechniquescanbeap- pliedto supportAMRsin bothnavigation andprovidingservices.

Comparedto AGVs,for whichmost situations andtasks are pre- dictableandthereforesolvablebypredefineddecisionrules,AMRs navigate autonomously in a dynamic andunpredictable environ- ment. AI techniques such as vision systems and machine learn- ing (ML) enablethe identification and classification of obstacles.

Fuzzy logic, neural networks and neuro-fuzzy and genetic algo- rithms are examples of well-known fusion techniques that help movetherobotfromthestartingpointtothetarget,whileavoid- ing collisions with any obstacles along its path (Almasri et al., 2016;Diasetal.,2018).Thesetechniquesareinspiredbytheability ofthehumanbraintoperformcomplextasksbyreasoningabout, andadaptingandrespondingtochangesintheenvironment.Such behavior-based learning methods can be used to solve complex control problems that autonomous robots encounter in an unfa- miliar, real-world environment. Without these techniques, AMRs wouldreactto allobstacles inthesame way.Theintroductionof AIaffectsalldecisionareasbyopeningnewapproachestomaking decisions.The AIbranchesof vision,MLandplanning,havebeen foundtobeverypromising.AsAIcontinuestoadvance,theability tointeractandcollaboratewithAMRswill increase.Forexample, inwarehousesinwhichahumaninthepickingroleandanAMR inthefetchingrolecollaborateinorderpicking(Fig.3(i)),thehu- manpickercanusespeechorgestureinsteadoftactilecommuni- cationtoconfirmthatpickingtaskshavebeencompletedortoask forhelpinfindingitems.

3. PlanningandcontrolframeworkforAMRs

ThenewdevelopmentsandpossibilitiesofAMRs,comparedto AGVsystems,requireanewdecision-makingframeworkforplan- ningandcontrol.

Fig. 4. Impact of technological developments on planning and control decision areas for AMRs.

The central hierarchical system has been challenged by large fleet sizesorfleet swarms,collaborative robots,andan increased variety of services provided. System performance is reduced by a centralized control hierarchysince it musttake and simultane- ouslycommunicatemanydecisionsinashortperiod.Forinstance, in roboticmobile fulfilment(RMF) systems(Fig.3 (g)),there can behundredsofmobilerobotsformingalargesystem(Wangetal., 2020). The largestAmazon warehouses control thousandsof mo- bilerobots.Suchsystemsareoftendividedintomodulesthatcon- sistofpods positioned ina gridstructure, pickingandreplenish- ment stations, andvehicles (Lamballais et al.,2020). The system caneasilybescaledupbyaddingvehiclesormodules.Insuchin- tralogistics environments, decentralized control ofnavigation and taskallocationcanhelptohandlethehighnumberanddensityof vehicles byreducing elevated levelsoftraffic andcongestion. The degree of decentralization ofoperations andthe responsibility of theAMRsmustbedecidedatthestrategiclevel.

Depending on specific tasks and applications, the number of AMRs,includingequipment such asmanipulators,must bedeter- mined.Methodsneedtobedevelopedfordecidingandevaluating the fleet’ssize andequipment intermsofflexibility,productivity, quality,andcosts.However,duetotheshortimplementationtimes ofsystems,once theyare available,vehicles canbe addedonthe spot.

AMR vehicles arenolonger tiedtoafixed guidepath,butin- stead can plan their path themselves andso freely move inpre- defined travel zones. The design of a guidepath is thereforeno longer necessary, but new decisions such as defining zones in which AMRs can operate autonomously must be taken (Fig. 2).

Thesezonescanbedefinedandchangedonadailyorweeklyba- sis, or dynamically in a decentralized manner by the AMR. The speedy establishment and easy change of zones enables opera- tionalflexibilitythatkeepsAMRresponsivenesshigh.Withinthese zones,servicepositionsfortaskssuchaspickingitemsorcollabo- ratingwithhumans cansimplybe added,assigned,orconfigured onashort-termbasis.Thezonescanprovidetraveldirections,traf- ficlevelsandotherrelevantinformationtoreducecongestionand the risk ofaccidents. Boththe servicezone andservicepoint lo- cations havea strongimpact ontravel timesandleadtimes.The increasedflexibilityrequiresnewprinciplesforschedulinganddis- patchingandhowtoallocateidleAMRsformaximumresponsive- ness.

The robot’s locomotionmechanismandequipment enablethe AMRs to follow paths and handle materials that AGVs cannot.

AMRs can coordinate with multiple robots to reduce traffic (e.g.

inaRMFsystem),toclimbshelves(e.g.insome AutonomousVe- hicleStorageandRetrieval(AVS/R)systems,seeFig.6(o)),ortore- move blocking loads (e.g. inPuzzle-Based Storage (PBS) systems, seeFig.3(n))toretrieveorstore unitloads.Thisnavigationflexi- bilitymustbeincorporatedinpathplanningapproaches.

Like all intralogistics vehicles, AMRs must adhere to many standards, e.g. safety standards, before they can be brought to market. They must also be robust and reliable. Currently, AGV systems cannot work without human surveillance and support.

Their sensitivity to a dynamic environment forces strong focus onerror andfailuremanagement by humans. AIcansupport the recovery of AMRs after failures and find strategies to overcome sucherrors,makingthemmorerobust.

Changes inthe planning and control environment from hard- wareandsoftwaredevelopmentshavechangedthetraditionalAGV decisionareastothefollowingonesforAMRs(Fig.4):(i)thecon- troldecentralizationlevel,(ii)thenumberandtypeofvehicles,(iii) zoningandservicepoints,(iv)resourcemanagement,(v)schedul- ing,(vi) dispatching,(vii)pathplanningand(viii)robustnessand resilience.

Theemergingplanningandcontrolframeworkwithitsdecision areasispresentedinthenextsection.Ineachsection,first,weex- plaintheshiftfromAGVstoAMRsandthecorrespondingdecision problem.Second,wepresentanddiscussthemodelingapproaches forAMRsandtheAGVmethodsapplicableforAMRsasperthelit- erature.

4. MethodsforplanningandcontrollingAMRs 4.1. Controldecentralizationlevel

Problem

Thelevelofcontroldecentralization isafundamentalstrategic decision.Determiningwhichpartsofasystemshouldbecontrolled in a centralized or decentralized manner plays a crucial role in definingtheinterfacesbetweenAMRsandtheiroperatingenviron- ment.

Centralized control structures are deeply rooted in the in- dustry and can access global information to achieve optimal single-objective performance for small-scale,simple systems. De- centralizedcontrolcanoftenaccessonlylocalinformationandfind localoptimal solutions forsystems withmultiple objectives,that

Fig. 5. Centralized versus decentralized control in small and large systems (partly based on Fauadi 2012 ).

are globally suboptimal (Fig. 5a). However, large-scale, complex systemsrequiredecentralizedsystems(DeRycketal.,2020a).

With a greatervariety of operationsanda more unstructured environment,decentralizedcontrol canachievehighperformance, since multiplecriteria are included in theoptimization (Fig.5b).

Large systemswithmanyvehicles imply alarge numberof deci- sion states to be considered in theoptimization approaches.The computation time is significantly lower in decentralized than in centralizedcontrol,sincethedecisionmakingisdistributedamong multipleAMRstakingonlylocalfactorsintoconsideration(Fig.5c).

This alsoallows furtherreduction ofthe recovery time afterfail- ure(Fig.5d).Centralizedcontrolontheotherhandrequiresalong time toevaluatethestateofeverysingleAMRafterfailureandto coordinate the entire fleet to recovery. Therefore,it is crucial, at the strategic decisionlevel,to providemethods to determinethe mostsuitable control decentralizationlevel forthe differentdeci- sionsareasuchasscheduling,zoningorpathplanning.

Methods

AMRs with varying degrees of decentralization have been in- troduced anddiscussed in existing studies. Wan etal. (2017) in- troduce a cloud-based decision-making engine with centralized scheduling (i.e. task allocation) and decentralizednavigation (i.e.

map processing) thatcan beshared amongAMRs.Thesmallsys- temsizefacilitatesmorecentralcontrolofAMRsanddecisionscan be made by the cloud-based system. The studyemphasizes that applyingsimpleAMRs,andoutsourcingthedecisionmakingtothe cloud cankeepoverallcostslow,whilesimultaneouslyusingsim- ulation modeling based on the AMRs’ statuses and locationscan improvetheirenergyperformance.

Simulations and computational experiments have been used to analyze the pertinence and feasibility of hierarchical control of AMRs (Demesure et al., 2017; Zhang et al., 2017). Kousi et al.

(2019)applydiscreteeventsimulationtoanalyzetheperformance of an assembly line in the automotive industry. Under their ap- proach,centralizedcloud-basedsystemscandetectmaterialsupply requirements, trigger material supply operations, schedule them, and communicate schedules to the AMRs. This reduces the fre- quencyofparts depletionandlimitsvehicletraveldistance,lead- ing to increasedassembly lineproductivityandefficientresource utilization. In high-density, PBS systems, mobile robots can au- tonomously move storage loads frominput points to the storage area orretrievalloads fromstorageto outputpoints(Gue&Kim, 2007; Alfieriet al., 2012; Gueet al., 2014). Thesesystems donot have travelaisles:the robotsmust collaborateto moveloads out of the way to create paths. The robots negotiate and divide the transportationtaskstomoveitemsquicklyanddeadlock-free.

Afew studieshaveinvestigatedthedecentralization ofcontrol areasbeyondpathplanning.AMRscanbeacost-effectivealterna- tivecomparedtoothermaterialhandlingsystemsandallowquick implementations. De Ryck et al. (2020a)describe a decentralized task allocation in which AMRscan negotiate with or bidagainst other machinesfortaskassignments.Fragapaneetal.(2020b) use

mathematicalmodelingandparametricalanalysistodetermineop- timal configurations and the associated throughput performance impactoftheAMRinproductionnetworkswhencomparedtotra- ditionally balanced lines. The control of connecting workstations duringworkstation downtimewithin aproductionnetwork relies onAMRs.

The studies by Maniya and Bhatt (2011) and Hellmann et al.

(2019) offerfurther supportby usingnewmethodologies tocon- sider and select centralized or decentralized control systems.

Maniya et al. (2011) propose a modified grey relational analysis methodcombinedwithananalyticalhierarchyapproachformulti- attribute selection processes. Hellmann et al. (2019) introduce a novel framework that integrates failure modesand effectsanaly- sisandanalytichierarchyprocessestosupportdecision-makingfor AMRdesign,operation,andcontrolpolicies.

In the analysisof centralized and decentralizedcontrol struc- tures, the prime objectives are to maximize resource utilization andthroughputwhile reducingcosts. The mostcommontrendis to decentralize decision-making for navigation, butseveral other decisionareascanalsobedecentralizedandthusincreasetheau- tonomyofAMRs.Everyapplicationareahasuniqueneeds andre- quiresatailoredmixofcentralizedanddecentralizedcontrol.The degreeofautonomyinAMRsmustbeanalyzedanddeterminedat the strategiclevel to establish areliable basis forthe numberof vehiclesandotherrelevantrequirements.

4.2. Numberandtypeofvehicles

Problem

Combiningtheanalysisofboththedistancesinthefixedguide path andthe numberof trips with AGV characteristics tradition- ally supported decisions on fleet size. However, due to the nav- igational flexibility of AMRs, travel distances and times between service points are highly variable or even uncertain. While AGV routing onlyhasalimitednumberofpossibilitiestoconnect two pointswithintheguidepath,theautonomouspathfindingmecha- nismthatAMRsusemeansthepossibilitiesareeffectivelyendless.

AMRscurrentlyoperateinapplicationareasinwhichhumans,such ashospitalvisitors,maybeunfamiliarwithAMRtasks.Congestion and high traffic are unavoidable, which will hinder AMR perfor- manceandincreasetraveltime.Thus,newmethodsareneededto calculatethe rightnumber ofvehicles. The flexible platform also enablesdifferent typesof AMRsthat vary by equipment, size,or functionwithinasinglefleet.Thenumberofvehiclesandthetype ofequipmentmustalsobedeterminedatthetacticallevel.

Methods

Mathematicalmodelingandsimulation

Simulation andmathematical modeling can be used to deter- minetheoptimalnumberofvehiclesinmanufacturing. JiandXia (2010)applydiscreteeventsimulationtofindthenumberofvehi- clesrequiredforhighutilizationandtoguaranteethestabilityofa systemwith a varying number ofdepots. Singhet al. (2011) use

discrete event simulation to find the minimum number of vehicles neededto meet the entirematerial distribution require- ment in a manufacturing system. To investigate different layout configurations in warehouses, Vivaldini et al. (2016) and Ribino et al. (2018) employ discrete event simulation and agent-based simulation to analyze throughput performance andto derive the optimalnumberofvehicles.Gharehgozlietal.(2017)applysimula- tioninagametheoreticsettingtoallowdecisionmakerstounder- standtherelationshipbetweencosts,throughputtime,andwaiting time whendeterminingtheoptimalnumberofautonomousvehi- clesfortransportbetweencontainerterminals.

Toensurelowtraffic volumes,Małopolski(2018) andLyuetal.

(2019)modelmanufacturingenvironmentsandapplysimulationto determinetheoptimalnumberofvehicles bysimultaneouslycon- sideringscheduling,path planning,andconflict-free vehiclerout- ing. Draganjac et al. (2020) analyze the impact of traffic conflict negotiationinindustriallogisticsonthroughput performanceina simulationmodeltodeterminetherightnumberofvehicles.

A differentapproach isoffered by mathematical programming models. Pjevcevic et al. (2017) propose adata envelopmentanal- ysis decision-makingapproachto simultaneouslydetermine vehi- cle numbers, reduce operating delay costs, and increase equip- ment utilization rates in container terminals. Most studies focus on homogenousfleets, butthe AMR’sflexibleplatform allows for heterogenous fleets in which AMRs have different or exchange- able equipment. Collaborating pickers and fetchers (mounted on the samevehicle base)in awarehouse contextoffer an example.

A recentstudyby Leeet al. (2019)proposesa mixed-integer lin- ear programming(MILP) approach and numericalanalysis to de- terminethenumberandtype ofvehicles neededtominimizethe time requiredto pickand transport all itemson a picklist from thewarehousetothepackingstation.

Queuingnetworkmodeling

In queuing network modeling, a customer arrives in a queue andgoesthroughseveralserviceprocessesinanetwork,according to somerouting mechanism, untilheexitsthesystem. The AMRs can bemodelledasaserver(openqueuingnetwork)orcustomer (closed queuingnetwork)ortoconnect toacustomerforspecific tasks(semi-openqueuingnetwork).Thedifferentmodelshavedif- ferent applicationpossibilities. Whileopen queuingnetworkscan be used attheoperationaldecisionlevel toestimate waitingand throughputtimes.Closed queuingnetworksassume thesystemis thebottleneckandassuchtheyarefittoestimatethroughputca- pacityofagivenconfigurationatdesigndecisionlevel.Semi-open queuing networkscan do both, butthe (approximate)analysisis somewhatmoreinvolved.

Fukunari andMalmborg (2008)use an open queuingnetwork modeltoestimatethecycletimeandresourceutilizationforAVS/R systems.Performanceisestimatedusinganiterativecomputational scheme considering randomstorageassumptions. YuanandGong (2017) determine theoptimal numberandvelocity ofrobots and provide designrules forRMF. Wangetal. (2020) apply analytical models, including a bottleneck-based model and an open queu- ing networkmodel, to simulaterobotic mobile fulfilment system layout configurationsandtoidentifytheoptimalnumberofvehi- cles. Zhangetal. (2020) useopen queuingnetworksanddiscrete eventsimulation toinvestigatetheinfluence ofrobotcapacityon the performance of a flexible flow shop withrandom andstate- dependent batchtransport.Open queuingnetworkscannotmodel a jointcapacity constraint set by the AMRs involved inmultiple processes.

Limiting the number of resources, as in closed queuing net- work, allows to focuson the populationconstraint. Fukunari and Malmborg(2009)propose aclosedqueuingnetwork approachfor estimating resource utilization in AVS/R systems. Hoshino et al.

(2007) propose using closed queuing network model and simu-

Fig. 6. Semi-open queuing network model with AMRs.

lation to analyzethe transportation systemwithin container ter- minals. The suitable number of vehicles can be determined that minimizestotal investment cost. Choobineh etal. (2012) propose ananalyticalmulti-classclosedqueuingnetworkmodel,extended withsimulation,todeterminetheoptimalnumberofvehiclesand theratiobetweenloadedandemptytraveltimestomaximizesys- tem throughput in a manufacturing or distribution environment.

Royetal.(2016) alsoapply aclosedqueuingnetwork modelwith simulationtoinvestigatetheeffectoftrafficonthenumberofve- hicles in container terminals. Roy et al. (2020) use open, closed, andsemi-openqueuestodeterminethenumbersofvehicleswith differentcapabilitiesinautomatedcontainerterminals.Theresults ofthesestudiesindicatethatvehiclecongestionandspeeddepend heavilyonthenumberandtypeofvehiclesandthroughput.

Semi-openqueuingnetworkmodelingcombinestheadvantages of open queuing networks(external queue to accommodate jobs whose entrance is delayed) and closed queuing networks (inner network with a population constraint). Using a synchronization station,incoming customerswaitingatan externalqueue canbe pairedwithavailableresourcesintheresourcequeue(Fig.6).

Thismodelingapproachallowstocapturetheexternalwaiting time andprecisely estimate thethroughput time.The network is typically aggregated to a singlesynchronization station plus one station with queue, representing the remaining network, with a loaddependentservicerate.Thecontinuous-timeMarkovchainof thisnetworkisanalyzed.Afterdeterminingthegeneratormatrix

Q=

⎧ ⎪

⎪ ⎪

⎪ ⎨

⎪ ⎪

⎪ ⎪

⎩

B0 C0 0 0 ... A₁ B₁ C₁ 0 ...

0 A2 B1 C1 ...

0 0 A2 B1 ...

..

. ... ... ... ...

⎫ ⎪

⎪ ⎪

⎪ ⎬

⎪ ⎪

⎪ ⎪

⎭

which isnearly block-tridiagonalandwhich includes a repetitive patternofthematricesA,B,andC,thematrix-geometricmethod can be applied to solve for the state probability vector

π

system (solving for

π

π

π

ratematrixRmustbecalculatedfromtheequation C1+ RB1+R²A2=0,

whichincludestherepetitivepartofthegeneratormatrixQ.Rcan be calculatediteratively (Neuts,1981), andtheratematrixatthe n-thiterationisgivenbyR_(n)=−(^C1+R²_(n−1)A₂)^B−₁^{1.Theiteration} process stops when the difference of two consecutive iterates is lessthanagiventoleranceof

| |

| |

ε

Rallowsonetoobtainallthestationaryprobabilityvectors,facili- tatingthenetworkanalysiswithrelativehighaccuracy.

ThestudiesbyEkrenetal.(2013,2014)demonstratethatAVS/R systemscan be modelledefficiently asa semi-openqueuingnet- work.Theperformanceoftheexternalqueuelengthaswellasthe average number of transactions in the network (including wait- ing for service, average number of vehicles in the vehicle pool, andaveragewaitingtimeintheexternalqueue)canbeevaluated by applying the matrix-geometric method and the proposed ex- tendedalgorithm(EkrenandHeragu2010).ThestudybyZouetal.

(2016)appliessemi-openqueuingnetworkstoestimatethesystem throughput time and cost and determines the number of robots whichhavetransportandliftingcapabilitiesandcanmoveonthe gridroofofacompactwarehouse.

In sum, mathematical optimization, simulation, and queuing networks have all shown to be suitable methods to model the industrial environment with its specific constraints, to analyze operating systems and to evaluate the number of vehicles, with maximizing system throughput as main objective and workload distribution,minimizingthroughputtime,traveltime,andcostsas additionalobjectives.

4.3. Zoningandservicepoints

Problem

The transitionfromprovidingservices alongfixed guidepaths to flexible areas requires decisions to be made regarding the design of zones and service points. In some AMR application areas, the numberand location of servicepoints can be decided dynamically. Examples include guidance assistance in hospitals or shopping malls and RMFsystems or collaborating fetchers in warehouses. Dividing the service areas into several zones with singleormultiplevehiclescanimprovecostandproductivityper- formance. Limiting the operating area for each vehicle improves theoverallresponsivenessofthesystem,sinceonlyshorttripsare performed,andvehiclesareavailablemorequickly.Therefore,zon- ing comprises the activities and decisions involving (I)analyzing the area in which the service must be provided, (II) determin- ing fixed and/or dynamic service points, (III) configuring zones (adding,removing,dividingoroverlayingzones, anddefiningflow direction) and (IV) determining the number of vehicles in each zone.Thesequenceofthesestepscanvary.

Methods

Severalstudiessuggest designingzonesinloopsorblocksand co-locating picking and delivery points to improve performance within manufacturing systems. Shalaby et al. (2006) investigate zone partitioning and the selection of a tandem transportation system, using a heuristic algorithm to meet several objectives:

minimizing total flow distance and total handling cost, achiev- ing maximum workload, and limiting the number of between- zonetrips.Asef-Vazirietal.(2007)developexactoptimization,de- composition, and heuristic procedures to design a unidirectional flow loop. A binaryinteger programming modeland a neighbor- hood search heuristicmethod supportmaximizing loaded-vehicle trips andminimizing empty vehicle tripdistances. Farahani etal.

(2007) investigatetheflow pathlayout anddevelop agenetic al- gorithm to determine the optimal location of the loop and the picking anddelivery stations,withthegoalofminimizingtheto- tal distancetravelled. ElMekkawyand Liu (2009) use a memetic algorithm ina computational experiment techniquesto optimize thepartitioningprobleminatandemAGV system, byminimizing overall workload, balancing the workload across zones, and pre- ventingbottlenecks.Hamzeeietal.(2013)proposeacutting-plane algorithm tomodel anddesigntheflow path andthelocation of pickup anddeliverypoints. Asef-VaziriandKazemi(2018)investi- gate thetravelingsalesmanproblemoftheshortestloopcovering at leastone edge of each workstation. Theirproposed evolution- aryalgorithmachievesrobustloopdesignsolutionsthatmaximize loadedandminimizeemptyvehicletravel.

Analyzing different layouts and zone configurations simulta- neously can yield additional performance improvements. Using a simulated annealing approach, Tubaileh (2014) analyzes different manufacturing systems with simulations to find the optimal lo- cations for machines in all feasible layouts. The objective of the study is to minimize travel times ina material handling system.

Qi et al. (2018) investigate warehouse layoutsanddevelop zones

according to task density. Their simulation supports minimizing totaltravelingtime,totaldistancetraveled,andtotalwaitingtime.

They recommend an even storage distribution of fast-selling or frequently transported goods to improve system performance.

According to Lee et al. (2019),zoning in warehouses can signifi- cantlyreduce costs.Differentwarehouselayouts,zoneandservice point configurations for order-picking robots are analyzed using MILPandnumericalanalysiswiththegoalofminimizingthetime neededtodeliverallitemsfromapicklisttothepackingstation.

Lamballaisetal.(2017)andRoy etal. (2019)usequeuingnetwork models and simulation to analyze zone assignment strategies in RMF systemsto improve system throughput,average order cycle time, and robot utilization. To analyze the preferred number of servicepointsinsuchsystems,Lamballaisetal.(2020)useasemi- openqueueingnetworkwithsimulationtodeterminetheoptimal number of pods, and picking and replenishment stations. With regard to AVS/R systems, Roy et al. (2012) propose a semi-open queueing network approach to investigate the impact of vehicle locations and zones within a tier using multiple vehicle classes and class switching probabilities in terms of throughput perfor- mance.Azadehetal.(2020)useaclosedtwo-phaseserverqueuing network,embeddedina Markovdecisionprocess,to dynamically adjustthenumberofzonesinahuman-robotcollaborativepicking system. They show that dynamically adjusting the number of zones can lead to higher throughput capacity in multichannel warehouseswithvaryingnumbersoflargeandsmallorders.

Differencesin zoning andinthe numberof vehicles per zone caninfluenceoveralltraffic.Reducingcongestionbetweenvehicles – by reducing the time that vehicles spend negotiating complex traffic situations andremoving bottlenecksin high-trafficareas – helpstodecreaseoverall traveltime andincreasesystemrespon- siveness. Ho and Liao (2009) propose a dynamic zone strategy that includes zone partition design and dynamic zone control.

Their simulation results show a reduction in vehicle congestion and an increase in load balance between vehicles in different zones. Azadeh et al. (2019b) use closed-queuing network models to compare differentzoning schemes and accesscontrol rules to estimatethethroughputimpact onvehicleblocking.Tomaximize throughput,Singhetal.(2011)suggest usingdiscreteeventsimu- lationandaschemeforpartitioningtheentireareaintoexclusive zones for individual vehicles in an automotive manufacturing plant. Małopolski (2018) offers a method that divides the layout into a rectangular grid and then uses both linear programming andsimulation to improve transportation performance forunidi- rectional, bidirectional, andmultiple-lane flow path systems in a manufacturingenvironment.

The main objectiveswhen designing zones andservicepoints aretominimizetraveldistance,traffic,andthroughputtimewhile distributingtheworkload throughoutthesystem, toincrease and – ideally - maximize system throughputand resourceutilization.

Dynamiczoneswithmultipleandvaryingservicepointsincreases the AMR modeling complexityand limits the applicationof ear- lier AGV-based approaches.When servicepoint positions change dynamically,they impacttheworkloadandservicedemands.This increases the number of variables in mathematical models, with negative consequences for feasibility and on computation time.

Evolutionary approaches and simulation seem to be most suit- ableinthesecases.Anotherpromisingapproachhasbeenusedto modelthe assignmentof mobilerobots inwarehousing.In ware- houses, the service points (picking locations) are numerous and they changeaccording tothe orders to be fulfilled.Queuingnet- work modeling (to estimate performance) and Markov decision processes(toassignvehicles dynamically)are apromisingcombi- nationofmethodsabletosolvecomplexanddynamicproblemsin anaccurate wayandwithacceptablecomputationtime.Theycan beapplied alsoinotherapplicationareas,suchasmanufacturing,

hospitalsorshoppingmalls,adjustingthedefinitionoftheservice pointstotheapplicationcontext.Thesemethodsarealsosuitable todynamicallymanagelargeamountsofinputdata.Furtherexten- sions willbe tointegratethe trafficmodelingintothesemethods inorderto considerblockingandcongestionandtheir impacton theperformanceofthesystem.

4.4. Resourcemanagement

Problem

CurrentAGVscanonlyprovidefewhandlingactivities(e.g.lift- ing andmoving),sincethey areequippedwithonlyasinglehan- dlingunit(e.g.liftingunit).However,inroboticsandflexibleman- ufacturing, itiscommon toexchange equipment.AMRscan load, use,unload, exchangeequipment, andcharge orexchange batter- ies. The AMR’s platform allows a wide range of resources to be used andshared.The decision-makingprocessesoflocationplan- ning, scheduling,anddispatching theseresources areessential to theiroptimalutilizationandthustohighAMRproductivityperfor- mance.

Methods

Eventhough theenergydensityofbatteriesis increasing,itis stillnecessarytodecidewherechargingstationsshouldbelocated.

Boysen et al. (2018) investigatethe influence of battery capacity, the numberand location ofchargingstations, andchargingperi- ods on makespanperformance. Theyproposea geneticalgorithm and computational experiments to identify the optimal charging locations in terminals. A study by Kabir and Suzuki (2019) ex- plores howthe fourheuristicsof(I)selectingthe nearest battery station, (II) selecting a battery station that will cause minimum delay considering both travel time and waitingtime in a queue, (III)selectingthenearest batterystationonthecurrentrouteand (IV) selectingthefarthestreachablebatterystationonthecurrent route,canaffectperformanceintermsoftotaltraveldistanceand waiting time ata battery station.Their simulation revealsthat a higherfrequencyofdecision-makingaboutbatteryswappinghelps to increasethe productivityofa manufacturingsystem. Zouetal.

(2018) evaluate battery charging and swapping strategies in an RMF system. Applying a semi-open queuing network and simu- lation allows the comparison of different strategies in terms of costandthroughputtimeperformance.Thestudyemphasizesthat throughput timeperformance can be significantlyaffected bythe batteryrecovery policy that isselected,andthatinductive charg- ing offersthe bestperformance.DeRycket al.(2020b) proposea decentralized charging approach in which an AMR can indepen- dently choose when to visit a chargingstation and how long to charge.Theirapproachismodeledasanextensionofthetraveling salesmanprobleminmanufacturingsystemsandsolved byagen- eralconstrainedoptimizationalgorithm.Theyinvestigatedifferent chargingschemesandchargingstationchoicestoincreaseresource efficiency.

In thenearfuture, theefficientmanagement ofresources will play agreaterrole inplanningandcontrollingAMRs.While AGVs employanarrowrangeofhandlingequipment,AMRswillhaveac- cessto andusea widevariety ofequipment,whichrequireseffi- cient managementanduse.Fullydecentralizingresourcemanage- menttotheAMRs,withoutsomeformofcoordination,willleadto suboptimal resultsatthe systemlevel.Iterating thedecentralop- timizationdecisionsforallAMRsandsharingtheresultsbetween multipleunitsareessentialtoachieveanearglobaloptimum.Us- ing the resultsof thedecentralized decisionsin operationallevel to taketacticaldecisionssuchaslocationplanningofbatterysta- tionsorequipmentstorageareascanyieldinperformancesuchas shorttraveltime.NewmodelingapproachforAMRsareneededto solve thesedecisionssimultaneouslyoriteratively.Predictiveana- lytics canfurthersupportindecidingwhentochargebatteries or

whentoexchange themountedequipmenttoa timeperiodwith lowest risk of conflict.None of thecurrent studies are providing methodswhichconsidertheoperationalinformationexchangefor suchdecisions.

4.5. Scheduling

Problem

A substantial body of literature has been developed to sup- port thedecision-makingprocessin schedulingmaterialhandling systemssimultaneouslywithmachines,humans,equipment,parts, and containers. In manufacturing, most studies consider a low number(fewerthan50)ofvehiclesundercentralized,hierarchical controlapplyingmixedintegerprogrammingmodelswithheuristic algorithms. Mathematical modeling and optimization approaches havebeenwidelydevelopedtosolveschedulingproblems,mostly inmanufacturingsincethenumberandtypeoftasksaretypically higher than in a warehouse. Some of the papers have also inte- grated simulationmodels to validate andgeneralize their results.

AnewstreamofresearchusesAItechniques,suchasevolutionary algorithms,whichisnowpossibleduetotheadvancesincomputa- tionalpower.However,decentralizedschedulingmethodsinwhich AMRsnegotiateorbidfortasksarestillscarce.

Methods

Mathematicalmodelingforschedulingoftransportationactivities The scheduling of‘only’ vehicles has been studied by analyz- ing theimpact onthe performance ofthe manufacturingsystem.

Few papers have focused on container terminals and warehous- ing,since solving dispatchingproblemsseems tobe predominant intheseapplicationareas.

In manufacturing systems, decomposition methods (Corréa et al., 2007) and mathematical and statistical models (Ghasemzadeh et al., 2009) have been used to solve and ana- lyze the interaction between conflict-free vehicle routing and scheduling policies and the impact on the production delays.

Other authors have studied the impact on makespan, cycletime deviations, andvehicle earliness andtardiness, through two-step algorithms to cluster the solution space and next to find the optimal solution (Fazlollahtabar et al., 2015; Bakshi et al., 2019).

For more complex problems with heterogeneous and multiple- loadvehicles, simulationis used to evaluate different scheduling policies (Ho & Chien, 2006; Bocewicz et al., 2019). In container terminals, scheduling transportation activities has been modeled by a minimum cost flow model solved by an extended simplex algorithm and greedy vehicle search (Rashidi & Tsang, 2011).

Polten and Emde (2020) focus on warehouses with very narrow aisles and address the multi-aisle access scheduling problem by proposing two access policies: exclusive and parallel access. A MILP and a large neighborhood search algorithm analyze and optimizetherobottaskallocationproblem.

Methodsforjointschedulingofvehiclesandmachines

Thesimultaneousschedulingofjobsinmachinecentersandve- hiclesisrelevanttoobtainhighoverallefficiencyinthemanufac- turingsystem.Themainobjectivesaretominimizethemakespan, waitingtimes,andtransportationcosts. Dueto thecomplexityof the problem, generalheuristics, decomposition algorithms, adap- tive genetic ormemetic algorithms, andsimulated annealing ap- proaches are mainly applied (Jerald et al., 2006; Deroussi et al., 2008; Nishi et al., 2011; Lacomme et al., 2013; Zheng et al., 2014; Baruwa, 2016; Lei et al., 2019). Fazlollahtabar (2016) and FazlollahtabarandHassanli (2018)applyamathematicalcostflow model andmodified network simplex algorithm, whileLyu etal.

(2019)usesimulationtoinvestigatetheimpactofschedulingpoli- ciesonmakespanandvehiclesutilization.Inthecontextofacon- tainerterminal,Yangetal.(2018)analyzesimultaneousscheduling ofmultiplecranesandvehiclesatacontaineryardtominimizethe

makespan of container loading andunloading by using a genetic algorithm. Chenet al.(2020) propose a multicommoditynetwork flowmodeltodealwithinter-robotconstraintsthataccuratelyre- flect the complex interactions among container terminal agents.

Usingageneticalgorithm,theaveragemakespanofthesystemand theaverageresourcetransfertimesofallrobotscanbeminimized.

AI-basedmethodsformulti-objectivesorconstraintproblems Due to advances in computational power and the applica- tion of AI techniques, the use of multi-objective or constraint schedulingmodelshasbecomemorefeasible,inparticularincom- plex environments,such asmanufacturingwithmultiplejobsand machine centers. Some authors have developed genetic and ant colony optimization algorithms (Udhayakumar & Kumanan, 2010; Saidi-Mehrabad et al., 2015), ora sheep flock heredity algorithm (Anandaraman et al., 2012), hybrid evolutionary or genetic algo- rithms, particle swarm optimization (Gen et al., 2017; Mousavi et al.,2017; Rahmanetal.,2020),andawhaleoptimizationalgo- rithm (Petrovi´c etal.,2019).The whale optimizationalgorithm is inspired by humpbackwhalehunting.It firstexploresthe‘ocean’

looking for ‘prey’(exploration phase). This corresponds to agents searching the state space by changing their locations while at- temptingtofindglobaloptima.Whenalocationnearaglobalop- timum is found,they stop. After thefirst phase,the whalesstart divinginaspiralshapeinordertotraptheprey.Thisiscalledex- ploitationphase.Inthealgorithm,theagentsfollowa‘leader’and change their locationsaccordingtoa shrinkingencircling mecha- nism, while updating their location data, until the final location.

Thesemethodsperformwellforsolvingmulti-objectiveproblems, combining e.g. minimization ofmakespan,travel time, andtardi- ness,withmaximizationofbatterychargingefficiencyandvehicle utilization.

Methodsfordecentralizedschedulingandtaskallocation

Current informationsharing andcomputing technologies pro- videanewinformationprocessingmethodforonlinemachineand vehicle scheduling, enablingnewdimensions ofagility and flexi- bility. High levels ofconnectivityand communicationare needed when decentralizing taskallocation. Zeng et al. (2018) propose a collaborative and distributed scheduling approach for decentral- izing task allocation, based on dynamic communication between vehicles andmachines,usingahormone-regulationmechanism.A newpromisingapproachindecentralizedschedulingisofferedby auction-basedmethodswhereanannouncer(machine)andbidder (AMR) cooperate to achieve high performance in taskallocation.

DeRycketal.(2020a)classifydifferentauction-basedmethodsfor taskallocationinsingle,bundled,andcombineditemsofferedand bidontheseinsequentialorparallelauctions.Thebidcalculation is acrucialelement since itreflects thecostforthe AMR toper- formthespecific task,andthereforeforschedulingandtaskallo- cation. Evenwhile executing agiven task,AMRscan bidon new tasksandthuslocallyoptimizethetasklistandusethisinforma- tiontocalculatethenextbid.Bidscanbecalculatedbasedonthe cost to perform the tasks by the AMRs,or on the marginal cost considering also the other tasks inthe list.Each type ofcalcula- tion hasits mostsuitable biddingalgorithm. Forthefirst type of cost CNET, OCA-Alloc, CBAA and CBBA are used, while marginal costisusedinPrimAllocation,SIT-andSET-MASRalgorithms(see DeRycketal.2020aforanoverview).Theseaction-basedmethods overcome the limitations of previous OR approaches, and extend to largevehiclefleets, whileintroducingflexibility andscalability.

The computationisdistributed,soitcan beappliedto verycom- plex problemswith manyconstraints. The collateral effect isthe increaseindemandforcomputationalpowerforeachsingleAMR, withnegativeimpacton batteryconsumption.Furtheropportuni- tiesforimprovingthesemethodswillbeintheintegrationofthis decisionareawithresourcemanagementanddispatching.

4.6. Dispatching

Problem

Smart dispatching methods, that allow AMRs to be close to thepoint ofdemandbeforean actualneedis announced,canin- creaseperformance. The increasedflexibility ofaccessing a wide areaandoffreepositioningduetoautonomousnavigation,enable newopportunitiesforpositioningandforcruisingwhileanAMRis idle.Centralizingthedecision-makingprocessesofdistributingand dispatchingAMRs requiresa systemthat analyzes theAMR posi- tions andthe demanddata.ML andbig dataanalysis ofdemand cansupport theoptimizationofvehicledistributionover thesys- tem. However, large-scale AMR systems needhighcomputational power to analyze and communicate in real time. Decentralizing thisprocesswilldecreasetheneedforhigh-powercloud comput- ing.EachAMRwilloptimizeits availabletime basedonhistorical dataandondatasharedwithneighboringAMRs.Continuouscom- municationandnegotiationswilloptimizetheAMR’sabilitytore- actquicklytodemand.

Methods

Variousmulti-attribute dispatchingrules havebeen developed toallocatetaskstotheappropriateAMRs,usingmainlymathemat- icalmodeling,queuingnetworks,andsimulationtoevaluatethem.

Theyhavebeenmostlyappliedinmanufacturing,andonlyfewim- plementationscanbe found inwarehousingandcontainer termi- nals.

Several mathematical approaches have been developed to model the dispatching problem in its complexity, including path layouts,vehiclecapacityandrestrictionsasconstraints,andsingle ormultipleobjectives,such asminimizing makespan,travel time, anddelay.VenturaandRieksts(2009)developadynamicprogram- ming algorithm to solve idle vehicle positioning in a single loop AGVsystem.Venturaetal.(2015)extendtheproblemtoageneral guide-pathlayout,solved bya geneticalgorithm.BozerandEam- rungroj(2018)presentan analyticmodeltoassessthethroughput performance and device utilization of various dispatching rules, by varying layout configurations in trip-based systems. In case ofmore complex problems,withmulti-objectives andmore con- straints, heuristics like genetic and evolutionary algorithms have beenimplemented(Linetal.,2006;Umaretal.,2015;Miyamoto&

Inoue,2016;Genetal.,2017).

Whilequeuingnetworkmodelingislessoftenappliedtoman- ufacturing systems,it is commonly used in warehousing, inpar- ticular for RMF systems. An extended review of closed queuing network models by Smith (2015) analyzes optimal workload al- location in manufacturing systems with multiple transportation servers, infinite-capacity workstations, anda finitecapacity state.

Zou et al. (2017) apply semi-openqueuing networks anda two- phaseapproximateapproachto estimatethe performanceofRMF systemsintermsofretrievalthroughputtime.Anassignmentrule based on the handling speeds of workstations is proposed and managedbyaneighborhoodsearchalgorithmtofindanearlyop- timalassignment.Heetal.(2018)introduceadifferentiatedproba- bilisticqueuingpolicyanduseanalternatingminimizationmethod withsimulatedannealingto minimizetheweightedlatencyofall customerorders.

Simulation has been used to explore various scenarios to ex- tractgeneralguidelinesandresultstosupportdecisionmakers,es- peciallyinmanufacturing wheretheproblemsare complex.Some authorsfocusonevaluatingthe impactofseveralmulti-attributes dispatchingrules(Bilgeetal.,2006;Guan&Dai,2009;Singhetal., 2011; Confessore et al., 2013; Zamiri & Choobineh, 2014). These rules can typically include attributes such as travel time or dis- tancetopickuplocation,inputandoutputbuffersize,useofsin- gle or multiple-load vehicles, and waitingtime. Demandcharac- teristics and constraints from the operating environment have a

significant impacton theresponsivenessofAMRs.Simulation has shown to be apowerful tool formulti-scenario analysisthat can beintegratedwithbigdataanalyticsandMLtechniques.

4.7. Pathplanning

Problem

Pathplanningisthetaskoffindingacontinuous,deadlock-free path, with little congestion delay forthe AMR from the start to thegoalpositionsothatitcannavigateautonomouslybetweenlo- cations, potentiallywithin alargeswarm. ComparedtoAGVrout- ing, which uses a guide path as input, path finding for AMRs uses a representation of the environment to mathematicallyfind theshortestandconflict-freepath.AnAMRalways createsa new, unique pathwhenmoving fromonepointto another.Constraints ofstaticanddynamicobstacles,feasiblecurvature,robotsize,lane dimensions, andspeed maybe includedto findtheoptimalpath with single or combined objectives. In static environments, the pathplanningisoftenperformedonlyonce,butdynamicenviron- ments canrequirerepeatingtheprocessoffindingacollision-free path multipletimes,formultiplevehicles tobypass ortoremove theobstacles.

Methods

The methods for path finding can be grouped into those for a single vehicle, for multiple vehicles, and for multiple vehicles with unit load accessibility constraints (i.e. obstacles need to be removed).

Methodsforasinglevehicle

DeRycketal. (2020a)explainthegraphrepresentationsofthe environment andgraphsearch algorithms fora singleAMR. Their studyhighlightsthattheA^∗andD^∗Litealgorithms,modificationsof Dijkstra’salgorithm,arethemostpopulargraphsearchalgorithms tofindashortestpath.

ComparedtoDijkstra’salgorithmwhichallows toprioritizedi- rections (favoringlower costpaths, e.g. lower costs to encourage movingalongstraightlines,orhighercoststoavoidU-turns)toex- ploreandfindtheshortestpath,theA^∗algorithmusesaheuristic thatprioritizespathsthatseemtoleadclosertoagoal.A^∗ selects thepaththatminimizes

f

(

)

(

)

(

)

where g(ⁿ) ^{is the length ofthe path fromthe start node to the} node n, andh(ⁿ) ^{is the heuristic cheapest distance} (Manhattan, Euclidean, orChebyshev)of thecurrentnode n tothe goalstate.

Comparedtotheprevious mentionedapproaches,theD^∗Litealgo- rithm worksin the opposite direction whichis from the goalto thestartandisespeciallyusefultofindtheshortestpathinlarge andcomplexareas.

AccordingtoLiaqatetal.(2019),simulationiscurrentlynotable toproperlyreproducetheAMRpathsandbehaviorindynamicen- vironments. In a dynamicenvironment, manysituations occur in whichmoving obstacles cantemporarilyblock theAMR’spath.In their study,experimentssupport the AMR motionplanningreac- tion to avoid obstacles. They provide protocols that improvethe accuracyandqualityofpathplanningsimulationindynamicenvi- ronments.

Methodsformultiplevehicles

In intralogistics systems with multiple vehicles, the shortest path does not necessarily result in the shortest travel time due to constraintssuchascongestionordeadlock.Severalstudies use mathematical modelingtointroduceconflict-free ordeadlock-free strategies to find the shortest path (Wu & Zhou, 2007; Saidi- Mehrabad et al., 2015; Yang et al., 2018), and to solve combina- torial scheduling (Corréa et al., 2007; Ghasemzadeh et al., 2009; Nishietal.,2011),dispatching (Miyamotoetal.,2016), numberof vehicles(Vivaldinietal.,2016),androutingproblem.Thestudyby

Nishietal.(2009)appliesLagrangianrelaxationtosolvetherout- ing problem. It enables the inclusion of various constraints such asloading,unloading,buffering, orcoordinationwithother mate- rialhandlingmachines.Accordingto JosephandSridharan(2011), routing flexibilityhas astrongimpact onthe overallflexibility of a manufacturing system. The study applies simulation andfuzzy logic toanalyze therouting flexibility andits effect onefficiency andversatilityfora manufacturingsystem. Theyprovidedecision support methods to improve the vehicle routing. The studies by Zhangetal.(2018)andLyuetal.(2019)applyanimprovedDijkstra algorithmtopredeterminetheinitialrouteofeachtask.Comparing every routeofeach vehicletothe giventransportation time win- dow,potential congestioncan bedetected andpreventedby sug- gestingalternativepaths.Diganietal. (2019)presentanoptimiza- tionstrategytocoordinateavehiclefleetinautomatedwarehouses to reduce the time mobile robots spend negotiating in complex traffic patterns.A quadraticoptimization program,representing a centralized coordination strategy is compared with a decentral- izedstrategythatreliesonlocalnegotiationsforsharedresources.

Thesimulationshowsthatthecoordinationstrategycanmaximize vehicle throughput and minimize the time vehicles spend nego- tiating traffic under different scenarios. Mohammadi and Shirazi (2020)introduceatandem-queue-linkwithalook-aheadapproach toenableflexible,collision-free routinginmanufacturingsystems.

Applying simulation,differentscenarios areevaluated forconges- tion, travel time, utilization, and system throughput. Draganjac et al. (2020) propose a decentralized control algorithm that al- lows each vehicle to plan its own shortest feasible path and to resolve conflict situations withother vehicles by negotiating pri- ority. Theyusesimulationtoanalyze theintralogisticssystemfor traveldistance,systemthroughput,andenergycosts.Fransenetal.

(2020)propose adynamicapproachtoavoidcongestionforlarge, densegrid-basedvehiclesystems.Sincemostapproachesinthelit- eraturearenotrapidenoughforreal-time control,theintroduced methodcansolvethisissuebyusingagraphrepresentationofthe gridsystemlayoutwithvertexweightsthatareupdatedovertime.

An extensive discrete eventsimulation allows the proposed path planningapproachtosignificantlyincreasethethroughputanden- ablerecoveryfromdeadlocksituations.

Methodsformultiplevehicleswithobstacleremoval

Obstacles (e.g. storedunit loads) can block the AMR paths to fulfillthematerialhandlingtask.ComparedtoAGVs,AMRsarenot helplessindeadlocksituations.Forinstance,toobtainaccesstoa specificpalletinatrucktrailerortoretrievea unitloadinaPBS system,theAMR canmovetheunitloadsthatareinfrontofitor canrequestsupportfromotherAMRs.

Forsuchcases,Gue etal.(2007)investigatethe sequencingof movementsforretrievingan item fromaPBS systemwitha sin- gle ‘escort’ (i.e. a singleopen storagespace: all other spaces are occupied). Each load has its own vehicle that can lift and move it toa neighboringescort. At each time step,it must be decided whichloadtomoveandinwhichdirection.Thepresentedsingle- escortalgorithmfindstheoptimalpathtomoveanitemtothere- trievalpoint,minimizingretrievaltime.Alfierietal.(2012)extend theworkofGueetal.(2007)tosystemswithmultipleemptyslots, wheremultiplevehicles(butfewerthanthenumberofloads)per- formthetransportationtasks.Theproposedheuristicalgorithmfor conflict avoidance regulates how vehicles should behave in dif- ferent traffic situations. Mirzaei et al. (2017) extend this to sys- temswheremultipleloadsmustberetrievedandmultiplevehicles mustbecoordinated,withasingleescort.Theyprovideanoptimal methodfortwoloadsanda heuristicmethodforretrievingmore than two loads.Yalcinet al. (2019) propose an exactandheuris- ticsolutionalgorithmforthesingle-itemretrievalprobleminPBS systemswithmultipleescorts.TheiralgorithmisbasedontheA^∗ algorithm andcan be used toplan minimum energymovements