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

Research output: Working paperWorking papers

Authors

  • Marius Merschformann
  • Lin Xie
  • Daniel Erdman
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.
Original languageEnglish
PublisherarXiv
Number of pages38
Publication statusPublished - 2018

Links