Anticipating possible future deployment of connected and automated vehicles
(CAVs), cooperative autonomous driving at intersections has been studied by
many works in control theory and intelligent transportation across decades.
Simultaneously, recent parallel works in robotics have devised efficient
algorithms for multi-agent path finding (MAPF), though often in environments
with simplified kinematics. In this work, we hybridize insights and algorithms
from MAPF with the structure and heuristics of optimizing the crossing order of
CAVs at signal-free intersections. We devise an optimal and complete algorithm,
Order-based Search with Kinematics Arrival Time Scheduling (OBS-KATS), which
significantly outperforms existing algorithms, fixed heuristics, and
prioritized planning with KATS. The performance is maintained under different
vehicle arrival rates, lane lengths, crossing speeds, and control horizon.
Through ablations and dissections, we offer insight on the contributing factors
to OBS-KATS's performance. Our work is directly applicable to many similarly
scaled traffic and multi-robot scenarios with directed lanes.

通过混合多智能体路径规划和无信号交叉口有序安排算法，本研究提出了一种性能显著优于现有算法、固定启发式以及基于 ARR 实施的优先规划的优化和完整算法 (OBS-KATS)，并在不同车辆到达率、车道长度、交叉速度和控制范围下保持性能，具有直接适用于类似规模的交通和多机器人场景的特点。