본 논문은 다중 에이전트 경로 찾기(MAPF) 문제를 위한 계산적으로 가벼운 알고리즘인 PIBT(Prioritized Interleaved Best-First Search)의 성능 향상을 다룹니다. PIBT는 에이전트의 다음 충돌 없는 위치를 생성하는데, 단순성과 확장성으로 인해 수백 또는 수천 개의 에이전트를 포함하는 최근 대규모 MAPF 방법의 기반 체계로 널리 사용되고 있습니다. 기존 PIBT는 에이전트가 목표를 향해 탐욕적으로 행동하지만, 최단 경로가 항상 유일하지 않기 때문에 여러 최적 행동을 가질 수 있습니다. 따라서, 이러한 행동 중 선택하는 방법에 대한 동점 해결(tiebreaking)은 결과 해결책에 상당한 영향을 미칩니다. 본 논문은 PIBT의 계산적 이점을 훼손하지 않으면서 두 가지 간단하지만 효과적인 동점 해결 기법을 연구합니다. 첫 번째 기법은 에이전트가 각 행동이 다음 시간 단계의 진행을 방해할지 여부를 고려하여 다른 에이전트를 지능적으로 피하도록 합니다. 두 번째 기법은 여러 번의 PIBT 실행을 통해 어떤 행동이 다른 에이전트에게 어떤 후회(regret)를 야기하는지 학습하고 이 정보를 사용하여 집단적으로 후회를 최소화합니다. 실험 결과, 이러한 기법들이 일회성 MAPF의 해결 비용을 줄이고 평생 MAPF의 처리량을 향상시킬 수 있음을 보여줍니다. 예를 들어, 밀집된 일회성 경우에, 이러한 동점 해결 기법을 결합하여 사용하면 속도 저하 없이 합계 비용을 약 10-20% 개선할 수 있습니다.
