Push, Stop, and Replan: An Application of Pebble Motion on Graphs to Planning in Automated Warehouses
This work addresses pathfinding challenges for robots in automated warehouses, offering a practical solution, though it is incremental as it builds on existing theoretical algorithms.
The paper tackled the problem of adapting pebble-motion algorithms for multi-agent pathfinding in automated warehouses by relaxing impractical assumptions like discrete, non-simultaneous movements, and demonstrated through experiments that their modified algorithm is applicable in this real-world setting.
The pebble-motion on graphs is a subcategory of multi-agent pathfinding problems dealing with moving multiple pebble-like objects from a node to a node in a graph with a constraint that only one pebble can occupy one node at a given time. Additionally, algorithms solving this problem assume that individual pebbles (robots) cannot move at the same time and their movement is discrete. These assumptions disqualify them from being directly used in practical applications, although they have otherwise nice theoretical properties. We present modifications of the Push and Rotate algorithm [1], which relax the presumptions mentioned above and demonstrate, through a set of experiments, that the modified algorithm is applicable for planning in automated warehouses.