다중 로봇 작업 할당을 위한 성능 보장을 갖춘 간단한 경매

우리는 탐사 작업을 모바일 로봇 팀에 할당하는 문제를 고려합니다. 각 작업은 로봇이 방문해야 하는 목표 위치로 구성됩니다. 할당의 목표는 모든 목표를 방문하는 모든 로봇의 이동 비용의 합으로써 총 비용을 최소화하는 것입니다. 우리는 최적 할당을 찾는 것이 알려진 환경에서도 NP-난해한 문제임을 보여줍니다. 이 논문의 주요 기여는 PRIM ALLOCATION이라는 간단하고 빠른 근사 알고리즘으로, 목표를 로봇에 할당하는 알고리즘으로 총 비용이 최적 총 비용의 최대 두 배에 불과한 할당을 계산하는 것을 증명합니다. 그런 다음 우리는 로봇이 목표에 입찰하는 다중 라운드 단일 항목 경매 측면에서 PRIM ALLOCATION을 제시하여 탈중앙화된 구현이 가능합니다. 우리의 아는 한, PRIM ALLOCATION은 할당의 품질에 대한 보장을 제공하는 첫 번째 경매 기반 할당 알고리즘입니다. 다중 로봇 시뮬레이터에서의 실험 결과는 PRIM ALLOCATION이 빠르며 단순성과 탈중앙화된 특성에도 불구하고 거의 최적의 할당 결과를 나타냄을 보여줍니다. 특히, 조합 경매에 기반한 계산 집약적인 할당 알고리즘보다 한 차원 더 적은 입찰이 필요하지만, 그 할당은 최소한 유사하게 좋습니다.