Conflict-directed Temporal-geometric LaCAM for Multi-agent Path Finding With Disc Robots

Conventional multi-agent path finding (MAPF) models agents as points and validates only vertex and edge-swap conflicts. When the same plan is executed by disc robots, geometrically close following turns can collide despite a valid discrete joint action. This paper presents conflict-directed Temporal Geo-LaCAM (Temporal-CD), which integrates finite-disc geometry and continuous-time safety into LaCAM. We precompute an exact squared-clearance profile of every local action pair as a function of the relative start-time offset. When d/D > √2/2, unsafe synchronous turns induce forced temporal precedence constraints. We show that the resulting scheduling problem is a simple temporal problem and extract the agents on each positive cycle to modify only LaCAM's low-level branching order . Temporally infeasible joint actions are rejected exactly, whereas conflict-directed branching changes only variable ordering and never prunes a feasible successor, preserving completeness under the stated motion model. With paired scenarios and random seeds, it solved all 300 MovingAI instances within 5s . On den520d with 1,000 agents, success was 99% and 84% at diameter ratios 0.80 and 0.95, versus 12% and 6% without mixed-sign-cycle branching. Independent continuous-time validation identified no infeasible transitions.