Multi-Agent and Multi-Rack Path Finding in High-Density Environments
摘要
In environments with numerous automated guided vehicles, planning efficient, collision-free paths is critical. Multi-agent path finding (MAPF) addresses the challenge of planning simultaneous, collision-free paths for multiple agents. Its extension, multi-agent pickup and delivery (MAPD), integrates path planning with task assignment, where agents transport rack-type objects from pickup to delivery locations. In dense warehouse settings, a key challenge is moving the racks scheduled for shipment while treating all others as movable obstacles. We formalize this problem as multi-agent and multi-rack path finding (MARPF), which extends MAPF/MAPD by distinguishing between target and obstacle racks. Although MARPF can be formulated using integer linear programming (ILP), this approach incurs an exponential computational cost. To address this, we propose a novel multi-stage heuristic method. First, it computes a trajectory for each target rack and plans the evacuation of any obstructing racks. These rack trajectories are then decomposed into discrete tasks and assigned to agents. On grid benchmarks ranging from