CBS( Conflict-Based Search )multi-agent path finding문제에서 자중 사용되는 최적화 알고리즘이다. 각각의 로봇이 서로 충돌 없이 목표 지점까지 도달하게 경로를 찾는 문제여기서 충돌이란 롯봇이 간은 간선을 서로 다른 방향으로 지나는 경우와 서로 같은 시간에 서로 같은 위치에 도착하는 경우이다.CBS의 아이디어각각의 로봇이 개별로 최단 경로를 찾게한다.만약 경로들간에 충돌conflict가 발생하며, 해당 충돌을 해결하는 새로운 경로를 찾는다.이를 위해서 search tree를 생성하고 분할,정복방식으로 문제를 해결한다.장점최적해를 보장충동 햐결 방식의 직관적필요한 경우에만 탐색을 수행하며 경로 계산 속도가 빠름단점경로가 많아지면 탐색 공간이 증가한다.제약이 늘어날수록 ..
