TY - UNPB

T1 - Multi-Agent Path Finding with Kinematic Constraints for Robotic Mobile Fulfillment Systems

AU - Merschformann, Marius

AU - Xie, Lin

AU - Erdman, Daniel

PY - 2018

Y1 - 2018

N2 - This paper presents a collection of path planning algorithms for real-time movement of multiple robots across a Robotic Mobile FulfillmentSystem (RMFS). In such a system, robots are assigned to move storageunits to pickers at working stations instead of requiring pickers to go to thestorage area. Path planning algorithms aim to find paths for the robotsto fulfill the requests without collisions or deadlocks. The robots are fullycentralized controlled. The traditional path planning algorithms do notconsider kinematic constraints of robots, such as maximum velocity lim-its, maximum acceleration and deceleration, and turning time. This workaims at developing new multi-agent path planning algorithms by consider-ing kinematic constraints. Those algorithms are based on some exisitingpath planning algorithms in literature, including WHCA*, FAR, BCP,OD&ID and CBS. Moreover, those algorithms are integrated within asimulation tool to guide the robots from their starting points to their des-tinations during the storage and retrieval processes. Ten different layoutswith a variety of numbers of robots, floors, pods, stations and the sizesof storage areas were considered in the simulation study. Performancemetrics of throughput, path length and search time were monitored. Sim-ulation results demonstrate the best algorithm based on each performancemetric.

AB - This paper presents a collection of path planning algorithms for real-time movement of multiple robots across a Robotic Mobile FulfillmentSystem (RMFS). In such a system, robots are assigned to move storageunits to pickers at working stations instead of requiring pickers to go to thestorage area. Path planning algorithms aim to find paths for the robotsto fulfill the requests without collisions or deadlocks. The robots are fullycentralized controlled. The traditional path planning algorithms do notconsider kinematic constraints of robots, such as maximum velocity lim-its, maximum acceleration and deceleration, and turning time. This workaims at developing new multi-agent path planning algorithms by consider-ing kinematic constraints. Those algorithms are based on some exisitingpath planning algorithms in literature, including WHCA*, FAR, BCP,OD&ID and CBS. Moreover, those algorithms are integrated within asimulation tool to guide the robots from their starting points to their des-tinations during the storage and retrieval processes. Ten different layoutswith a variety of numbers of robots, floors, pods, stations and the sizesof storage areas were considered in the simulation study. Performancemetrics of throughput, path length and search time were monitored. Sim-ulation results demonstrate the best algorithm based on each performancemetric.

KW - Informatics

KW - Business informatics

M3 - Working papers

T3 - ArXiv.org

BT - Multi-Agent Path Finding with Kinematic Constraints for Robotic Mobile Fulfillment Systems

PB - arXiv

ER -