본 논문은 다중 에이전트 경로 찾기(MAPF) 문제에 대한 새로운 근사 알고리즘인 DECBS를 제안합니다. MAPF는 여러 에이전트가 충돌 없이 목표 지점에 도달하는 경로를 찾는 NP-hard 문제이며, ECBS나 EECBS와 같은 기존의 제한된 근사 알고리즘은 focal search 기법을 사용하여 계산 효율성과 해의 질을 균형 있게 고려합니다. 하지만 기존의 focal search는 초기 단계에서 lower bound (LB) 값의 증가가 느려 탐색 공간이 제한되는 문제가 있습니다. DECBS는 최대 LB 값을 먼저 결정하고 이를 기반으로 best-first search를 수행하여 이 문제를 해결합니다. 실험 결과, DECBS는 대부분의 경우 ECBS보다 성능이 우수하며, 기존의 최적화 기법과도 호환됩니다. 특히 에이전트 밀도가 중간 또는 높을 때, 동일한 suboptimality bound와 최적화 하에서 ECBS보다 평균 23.5%의 실행 시간 개선을 달성합니다. 고차원 CT 노드를 약 30%, 저차원 focal search 노드를 약 50% 감소시킵니다.
