기술 요약: 다중 로봇 작업 할당 및 경로 계획을 위한 이중 계층 개미 군집 최적화 (Bi-Layer Ant Colony Optimization)

문제 정의

본 논문은 배송 및 물류 응용 분야의 맥락에서 다중 로봇 작업 할당(MRTA) 문제를 다룹니다. 핵심 과제는 각 작업이 특정 픽업 위치와 드롭오프(하차) 위치로 구성된 일련의 배송 작업을 실행하기 위해 모바일 로봇 함대를 조정하는 것입니다.

최적화 문제는 두 가지 동시 출력을 요구하는 결합된 결정 프로세스로 정의됩니다:

1. 작업 할당 (Task Assignment): 어떤 로봇이 각 특정 작업을 수행할지 결정합니다.
2. 작업 순서 결정 (Task Sequencing): 로봇이 할당된 작업을 수행하는 최적의 순서를 결정합니다.

목표는 모든 작업이 단일 로봇에 의해 정확히 한 번씩 실행되도록 보장하면서 전체 함대의 총 이동 거리를 최소화하는 것입니다. 저자들은 기존 방식들이 할당, 순서 결정, 실행을 별도로 최적화하는 독립적인 단계로 취급하는 경우가 많다고 지적합니다. 이러한 분리는 전역적 협업의 저하, 중복된 움직임, 그리고 시스템 효율성 감소를 초축할 수 있습니다. 본 논문은 MRTA를 할당과 순서 결정이 상호 의존적인 단일 최적화 문제로 공식화합니다.

방법론: 이중 계층 개미 군집 최적화 (Bi-Layer ACO)

이 최적화 문제를 해결하기 위해, 저자들은 이중 계층 개미 군집 최적화 (Bi-Layer ACO) 알고리즘을 제안합니다. 순차적으로 계층을 해결하는 전통적인 계층적 방법과 달리, 이 접근 방식은 두 개의 상호 의존적인 결정 계층을 하나의 군집 프로세스 내에 통합합니다.

핵심 프레임워크

알고리즘은 개미의 먹이 찾기 행동에서 영감을 받은 인구 기반 메타휴리스틱을 채택합니다. 군집 내 각 "개미"는 두 개의 결정 계층을 동시에 탐색하며 완전한 솔루션을 구축합니다:

1. 작업 할당 계층 (Task Assignment Layer):

   • 로봇에 대한 작업 할당($x_{i,j}$)을 결정합니다.
   • 작업 $j$를 로봇 $i$에 할당하는 것에 대한 학습된 바람직함을 나타내는 페로몬 행렬 $\tau_{assign} \in \mathbb{R}^{m \times n}$ (작업 $\times$ 로봇)을 활용합니다.
   • 휴리스틱 정보($\eta_{assign}$)는 로봇의 시작 위치와 작업의 픽업 위치 사이 거리의 역수로부터 도출됩니다.

2. 작업 순서 결정 계층 (Task Sequencing Layer):

   • 각 로봇에 할당된 작업의 방문 순서($\pi_i$)를 결정합니다.
   • 동일한 로봇의 경로 내에서 작업 $j$에서 작업 $k$로의 전이에 대한 바람직함을 나타내는 페로몬 행렬 $\tau_{seq} \in \mathbb{R}^{m \times m}$를 활용합니다.
   • 휴리스틱 정보($\eta_{seq}$)는 현재 작업의 드롭오프 위치와 다음 작업의 픽업 위치 사이 거리의 역수로부터 도출됩니다.

알고리즘 실행

알고리즘은 반복적인 주기를 통해 진행됩니다:

1. 구성 (Construction): 각 개미는 할당 계층의 페로몬 및 휴리스틱 값을 기반으로 확률적으로 작업을 로봇에 할당합니다. 할당이 완료되면, 순서 결정 계층이 각 로봇의 경로를 구성합니다. 첫 번째 작업은 로봇의 시작점과의 근접성을 기준으로 선택되며, 이후의 작업들은 순서 결정 페로몬과 휴리스틱 값을 기반으로 샘플링됩니다.
2. 평가 (Evaluation): 구성된 솔루션에 대한 총 이동 거리가 계산됩니다. 이는 모든 로봇의 이동 거리(시작-픽업, 픽업-드롭오프, 드롭오프-다음 픽업)를 합산한 값입니다.
3. 페로몬 업데이트 (Pheromone Update): 모든 개미가 솔루션을 구성한 후, 두 행렬의 페로몬 경로가 업데이트됩니다. 여기에는 다음 과정이 포함됩니다:
   • 증발 (Evaporation): 정체를 방지하기 위해 기존 페로몬 수준을 감소시킵니다.
   • 강화 (Reinforcement): 솔루션의 품질($Q/C(a)$)에 비례하여 새로운 페로몬을 증착합니다. 여기서 더 좋은 솔루션(낮은 비용)이 더 많은 페로몬을 증착합니다. 업데이트 방정식은 할당 쌍과 경로 내의 특정 작업 전이 모두가 강화되도록 보장합니다.

주요 기여

본 논문은 다음과 같은 주요 기여를 식별합니다:

• 통합 목적 함수 (Unified Objective Function): MRTA를 전역적 작업 분포와 국부적 경로 계획 사이의 상호 의전성을 명시적으로 포착하는 결합된 최적화 문제로 변환하는 새로운 비용 함수를 공식화했습니다.
• 이중 계층 ACO 아키텍처 (Bi-Layer ACO Architecture): 두 개의 구별되고 상호 연결된 페로몬 행렬을 사용하여 할당과 순서 결정을 단일 군집 프로세스로 통합하는 새로운 알고리즘 프레임워크를 도입했습니다. 이를 통해 작업 할당과 경로 계획의 동시 최적화가 가능해집니다.
• 성능 검증 (Performance Validation): 혼합 정수 선형 계획법(MILP) 및 입자 군집 최적화(PSO)에 대해 제안된 방법의 효능을 입증하는 종합적인 비교 실험을 수행했습니다.

실험 결과

제안된 방법은 세 대의 TurtleBot3 로봇을 사용하여 ROS 2 Humble 및 Gazebo 시뮬레이션 환경에서 평가되었습니다. 실험은 5, 10, 20개의 작업을 가진 세 가지 시나리오에서 수행되었습니다.

성능 지표:

• 총 이동 거리 (Total Travel Distance): Bi-Layer ACO는 모든 작업 규모에서 지속적으로 가장 낮은 평균 총 이동 거리를 달s성했습니다.
  • MILP와 비교했을 때, ACO는 총 이동 거리를 약 17.7% 단축했습니다 (5개 작업 시).
  • PSO와 비교했을 때, ACO는 총 이동 거리를 약 9.8% 단축했습니다.
• 완료 시간 (Completion Time): 제안된 방법은 또한 더 빠른 작업 완료 시간을 보여주었습니다.
  • 베이스라인 방법들과 비교하여, ACO는 완료 시간을 거의 20% 단축했습니다.
• 안정성 및 확장성 (Stability and Scalability):
  • ACO는 PSO 및 MILP에 비해 거리와 시간 모두에서 더 낮은 표준 편차를 보였으며, 이는 더 안정적인 수렴을 나타냅니다.
  • 작업 복잡성이 증가함에 따라 (최대 20개 작업), MILP와 PSO는 분산과 높은 비용이 증가한 반면, ACO는 우수한 성능을 유지했습니다.

의의 및 주장

본 논문은 제안된 Bi-Layer ACO 프레임워크가 기존 MRTA 접근 방식의 한계인 작업 할당과 경로 계획의 분리 문제를 효과적으로 해결한다고 주장합니다. 이러한 결정들을 공동으로 최적화함으로써, 이 방법은 중복된 움직임을 줄이고 전반적인 미션 효율성을 향상시킵니다.

저자들은 Bi-Layer ACO가 다중 로봇 배송 작업에 대해 확장 가능하고 신뢰할 수 있는 솔루션이며, 전통적인 정확한 방법(MILP)이나 다른 메타휴리스틱(PSO)보다 더 짧고 일관된 경로를 생성하는 탐색(exploration)과 이용(exploitation) 사이의 균형을 제공한다고 결론짓습니다. 이 연구는 이러한 통합적 접근 방식이 실제 물류 및 배송 시스템의 효율성을 높이는 데 특히 가치 있음을 시사합니다. 향후 연구는 동적 환경, 이기종 로봇 함대 및 통신 제약 조건으로 확장하는 데 중점을 둘 것임을 언급했습니다.