Modeling and Optimizing the Provisioning of Exhaustible Capabilities for Simultaneous Task Allocation and Scheduling

1. 문제 정의 (Problem Statement)

이 논문은 이질적인 (heterogeneous) 로봇 팀이 제한된 시간과 배터리 제약 하에서 여러 작업을 동시에 수행해야 하는 다중 로봇 작업 할당 및 스케줄링 (MRTA) 문제를 다룹니다. 기존 연구들은 주로 로봇의 능력 (traits) 을 고정된 값으로 간주하거나, 자원의 소모 (exhaustibility) 와 공급 속도 (provisioning rate) 를 고려하지 않았습니다.

주요 해결해야 할 핵심 문제들은 다음과 같습니다:

• 소모성 능력 (Exhaustible Traits) 의 고려: 로봇이 가진 자원 (예: 화학 물질, 배터리) 은 사용 시 소모되지만, 기존 모델들은 이를 무시하여 비현실적인 계획 (과도한 작업 할당) 을 수립하는 경향이 있습니다.
• 공급 속도 (Provisioning Rates): 일부 작업은 자원을 즉시 공급할 수 없으며, 특정 속도로 점진적으로 공급해야 합니다 (예: 소화용수 분사). 이를 고려하지 않으면 작업 수행 시간 추정이 부정확해집니다.
• 배터리 및 에너지 제약: 로봇의 이동과 작업 수행 시 소모되는 전력을 고려하지 않으면, 배터리 용량을 초과하는 비현실적인 계획이 생성됩니다.
• 복잡한 제약 조건: 작업 간 선행 관계 (precedence), 상호 배타성 (mutex), 절대/상대 마감 시간 (deadlines) 등을 동시에 만족시키면서 최적의 할당을 찾는 것은 NP-hard 문제입니다.

2. 방법론 (Methodology: TRAITS Framework)

저자들은 TRAITS (Trait Throughput and Allocation Informed Team Scheduling) 라는 새로운 오프라인 이질적 다중 로봇 작업 할당 프레임워크를 제안합니다. 이 프레임워크는 네 가지 주요 계층으로 구성됩니다.

2.1 새로운 특성 (Trait) 분류 체계

기존의 단순한 능력 분류를 넘어, 다음 세 가지 차원을 정의하여 특성을 모델링합니다:

1. 소모성 (Exhaustibility):
   • 비소모성 (IET): 사용해도 줄지 않는 능력 (예: 센서 범위).
   • 소모성 (ET): 사용 시 고갈되는 자원 (예: 배터리, 화학 물질).
2. 공급 방식 (Provisioning):
   • 비공급 (NPT): 공급 자체가 불가능한 속성.
   • 즉시 공급 (IPT): 순간적으로 전달 가능한 것 (예: 토큰 전달).
   • 점진적 공급 (GPT): 시간에 따라 점진적으로 공급되는 것 (예: 유체 분사).
3. 누적성 (Aggregation):
   • 비누적 (NCT): 각 로봇이 개별적으로 최소 능력을 갖춰야 함.
   • 누적 (CT): 팀 전체의 합계로 능력을 충족하면 됨.

2.2 배터리 소비 모델링

단순한 에너지 소모가 아닌, 전류 (Current) 와 전력의 비선형 관계를 고려합니다.

• 로봇이 특성을 공급할 때 소모되는 전류는 특성 양과 공급 속도에 비례한다고 모델링합니다.
• Peukert 의 법칙을 적용하여, 전류가 증가할수록 배터리 방전 속도가 가속화되는 현상을 반영합니다.
• 이를 통해 작업 시간과 이동 속도를 배터리 용량과 연계하여 최적화합니다.

2.3 최적화 계층 구조

TRAITS 는 다음과 같은 계층적 접근을 통해 해를 탐색합니다:

1. 작업 할당 계층 (Heuristic-based Task Allocation): 휴리스틱 (APR, NSQ, TETAQ) 을 사용하여 로봇을 작업에 점진적으로 할당합니다.
2. 특성 분배 계층 (Nonlinear Programming, NLP): 할당된 로봇 - 작업 쌍에 대해 특성 공급량과 속도를 결정합니다. 배터리 제약과 소모성 자원의 한계를 만족하면서 작업 시간을 최소화하는 비선형 프로그래밍 문제를 풉니다.
3. 스케줄링 계층 (Mixed-Integer Linear Programming, MILP): 작업 간 시간 제약 (선행, 상호 배타, 마감 시간) 을 고려하여 전체 작업 완료 시간 (Makespan) 을 최소화하는 스케줄을 생성합니다.
4. 모션 플래닝 계층: 충돌 회피는 저수준 제어 계층으로 위임하고, TRAITS 는 이동 시간 하한을 계산합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 모델링 프레임워크: 소모성 특성과 공급 속도를 공식화하여, 기존 방식과 호환되면서도 더 정교한 자원 관리가 가능하도록 했습니다.
2. 시간 확장 (Time-extended) 할당 알고리즘: 소모성, 공급 속도, 다양한 누적 형태를 모두 처리할 수 있는 포괄적인 알고리즘을 개발했습니다.
3. 배터리 최적화 프레임워크: 특성 공급과 전류 소모를 연결하고 Peukert 의 법칙을 도입하여, 로봇의 배터리 수명을 고려한 현실적인 할당 계획을 수립합니다.
4. 성능 검증: 기존 최첨단 (SOTA) 프레임워크 대비 복잡한 제약 조건 하에서도 실행 가능한 계획을 생성함을 증명했습니다.

4. 실험 결과 (Results)

시뮬레이션 창고 환경에서 400 회 이상의 무작위 실험을 수행하여 TRAITS 를 기존 프레임워크 (ITAGS, CTAS) 와 비교했습니다.

• 계획 실행 가능성 (Plan Feasibility): TRAITS 는 **100%**의 실행 가능성을 보인 반면, ITAGS 는 51.7%, CTAS 는 63.6% 에 그쳤습니다. 기존 방법들은 배터리 용량 초과, 특성 부족, 공급 속도 미달 등의 제약 위반으로 인해 많은 계획을 폐기했습니다.
• 자원 부족 로봇 (Under-resourced Robots): TRAITS 는 로봇의 능력 한계를 초과하는 작업을 할당하지 않아 자원 부족 로봇 비율이 0% 였으나, 기존 방법들은 높은 비율로 할당했습니다.
• 배터리 및 C-레이팅 위반: TRAITS 는 배터리 용량 및 최대 전류 (C-rating) 위반이 전혀 없었으나, 기존 방법들은 20~47% 의 위반률을 보였습니다.
• 계산 시간: TRAITS 는 복잡한 모델링 (비선형 프로그래밍, 배터리 고려) 으로 인해 계산 시간이 다소 길었으나 (평균 약 200 초), 이는 더 정확하고 실행 가능한 계획을 얻기 위한 필수적인 트레이드오프였습니다.
• 확장성: 작업 수 ($K$) 가 증가할수록 계산 시간이 급격히 증가하는 경향을 보였으며, 이는 문제의 NP-hard 성질 때문입니다.

5. 의의 및 결론 (Significance & Conclusion)

이 논문은 다중 로봇 시스템의 작업 할당 분야에서 **자원의 시간적 동역학 (소모성, 공급 속도)**과 에너지 제약을 통합적으로 다루는 최초의 프레임워크 중 하나입니다.

• 실용성: 실제 로봇 시스템 (배터리, 화학 물질 등) 에 적용 시 발생할 수 있는 비현실적인 계획을 방지하고, 로봇이 실제로 임무를 완수할 수 있는 계획을 보장합니다.
• 정확도: 작업 수행 시간과 전체 완료 시간 (Makespan) 을 더 정확하게 추정할 수 있게 하여, 로봇 팀의 운영 효율성을 극대화합니다.
• 한계 및 향후 과제: 현재는 특성 공급 속도가 일정하다고 가정하고 있으며, 충돌 회피를 저수준으로 위임하고 있습니다. 향후 연구에서는 동적인 공급 속도와 충돌 회피를 통합하는 방향으로 발전시킬 예정입니다.

요약하자면, TRAITS 는 복잡한 제약 조건 하에서 이질적인 로봇 팀이 자원을 효율적으로 관리하며 작업을 수행할 수 있도록 하는 강건하고 최적화된 의사결정 프레임워크를 제공합니다.