Search papers, labs, and topics across Lattice.
This paper introduces Task Assignment and Path Finding with Precedence Constraints (TAPF-PC), a novel problem formulation extending MAPF-PC by jointly optimizing task assignment, precedence satisfaction, and routing cost. To solve TAPF-PC, the authors propose a large neighborhood search (LNS) approach that iteratively improves a feasible MAPF-PC seed solution through reassignment-based neighborhood repair. Empirical results demonstrate that LNS significantly outperforms fixed-assignment seed solutions, improving 89.1% of instances across various benchmark families.
Freeing robots from pre-assigned tasks slashes completion times in multi-agent settings, with a new algorithm improving performance on almost 90% of tested scenarios.
Many multi-robot applications require tasks to be completed efficiently and in the correct order, so that downstream operations can proceed at the right time. Multi-agent path finding with precedence constraints (MAPF-PC) is a well-studied framework for computing collision-free plans that satisfy ordering relations when task sequences are fixed in advance. In many applications, however, solution quality depends not only on how agents move, but also on which agent performs which task. This motivates the lifted problem of task assignment and path finding with precedence constraints (TAPF-PC), which extends MAPF-PC by jointly optimizing assignment, precedence satisfaction, and routing cost. To address the resulting coupled TAPF-PC search space, we develop a large neighborhood search approach that starts from a feasible MAPF-PC seed and iteratively improves it through reassignment-based neighborhood repair, restoring feasibility within each selected neighborhood. Experiments across multiple benchmark families and scaling regimes show that the best-performing configuration improves 89.1% of instances over fixed-assignment seed solutions, demonstrating that large neighborhood search effectively captures the gains from flexible reassignment under precedence constraints.