12.21 그래프 기반 임무 계획과 작업 할당

1. 임무 계획과 작업 할당의 개요

임무 계획(mission planning)과 작업 할당(task allocation)은 로봇 시스템의 고급 기능이며, 복잡한 임무를 실행 가능한 작업으로 분해하고 적절한 자원에 할당하는 과정이다. 그래프 이론은 이러한 문제를 모델링하고 풀기 위한 강력한 도구를 제공한다. 단일 로봇의 작업 시퀀스 계획에서 다중 로봇의 협력적 임무 수행까지 다양한 응용에서 그래프 기반 접근법이 활용된다. 본 절에서는 임무 계획과 작업 할당의 그래프 모델링, 알고리즘, 그리고 실제 응용을 다룬다.

2. 임무 계획의 정의

2.1 임무

임무(mission)는 로봇이 달성해야 할 고수준 목표이다. 예를 들어 “건물의 모든 방 청소”, “여러 위치의 패키지 배달”, “환경의 지도 작성” 등이다.

2.2 작업

작업(task)은 임무를 달성하기 위한 더 작은 단위의 행동이다. 예를 들어 “한 방 청소”, “한 패키지 픽업과 배달”, “한 영역 매핑” 등이다.

2.3 임무 계획의 단계

임무 계획은 일반적으로 다음의 단계로 진행된다.

1. 임무 분해: 임무를 작업으로 분해
2. 작업 시퀀싱: 작업의 실행 순서 결정
3. 작업 할당: 작업을 로봇이나 자원에 할당
4. 실행 계획: 각 작업의 구체적 실행 계획

3. 그래프 모델링

3.1 작업 의존성 그래프

작업 사이의 의존 관계는 방향 비순환 그래프(DAG)로 표현된다.

• 노드: 작업
• 엣지: 의존 관계 (A가 B 이전에 수행되어야 함)

3.2 작업-로봇 이분 그래프

작업과 로봇 사이의 가능한 할당은 이분 그래프로 표현된다.

• 한쪽: 작업
• 다른 쪽: 로봇
• 엣지: 가능한 할당
• 가중치: 할당 비용

3.3 작업 네트워크

복잡한 임무는 작업 네트워크로 표현된다. 작업과 그 사이의 다양한 관계가 그래프를 형성한다.

4. 임무 분해

4.1 계층적 분해

임무는 계층적으로 분해된다.

임무: 사무실 청소
├── 작업: 거실 청소
│   ├── 부분 작업: 가구 사이 청소
│   └── 부분 작업: 러그 청소
├── 작업: 부엌 청소
└── 작업: 침실 청소

4.2 HTN (Hierarchical Task Network)

HTN(Hierarchical Task Network) 계획은 임무의 계층적 분해를 명시적으로 다룬다. 각 작업은 부분 작업의 집합으로 분해될 수 있다.

4.3 작업 라이브러리

작업 라이브러리는 사전 정의된 작업과 그 분해 방법을 저장한다. 임무 계획 시 이를 활용한다.

5. 작업 시퀀싱

5.1 위상 정렬

작업 의존성 그래프(DAG)의 위상 정렬은 작업의 가능한 실행 순서를 제공한다.

def sequence_tasks(tasks, dependencies):
    G = build_dag(tasks, dependencies)
    return topological_sort(G)

5.2 임계 경로

임계 경로(critical path)는 프로젝트 완료에 가장 긴 시간이 걸리는 경로이다. PERT(Program Evaluation and Review Technique) 차트가 이를 시각화한다.

5.3 시간 제약

작업에 시간 제약(시작 시간, 마감 시간)이 있을 수 있다. 시간 제약을 만족하는 시퀀스를 찾는 것은 더 복잡한 문제이다.

6. 작업 할당

6.1 작업 할당 문제

작업 할당 문제는 다음과 같이 정의된다.

• 입력: 작업의 집합, 로봇의 집합, 비용 행렬
• 출력: 작업과 로봇의 매칭

6.2 단일 로봇 - 단일 작업

가장 단순한 경우는 각 로봇이 한 작업만 수행하고, 각 작업이 한 로봇에 할당되는 경우이다. 이는 이분 그래프 매칭 문제이다.

6.3 단일 로봇 - 다중 작업

각 로봇이 여러 작업을 수행할 수 있는 경우이다. 작업의 순서도 고려해야 한다.

6.4 다중 로봇 - 다중 작업

가장 일반적인 경우이며, NP-hard 문제이다. 휴리스틱이나 근사 알고리즘이 사용된다.

7. 헝가리안 알고리즘

7.1 개요

헝가리안 알고리즘(Hungarian algorithm)은 최적 이분 매칭을 다항 시간에 찾는다. 1955년 헤럴드 쿤(Harold Kuhn)이 제안하였다.

7.2 알고리즘

Hungarian(cost_matrix):
    n = size of matrix
    
    // 행과 열의 최소값 빼기
    subtract row mins
    subtract col mins
    
    while no perfect matching:
        // 0을 통한 매칭 찾기
        ...
        // 비용 행렬 조정
        ...
    
    return assignment

7.3 시간 복잡도

헝가리안 알고리즘의 시간 복잡도는 O(n^3)이며, 여기서 n은 작업/로봇의 수이다.

7.4 Python 구현

from scipy.optimize import linear_sum_assignment

cost_matrix = np.array([
    [4, 1, 3],
    [2, 0, 5],
    [3, 2, 2]
])

row_ind, col_ind = linear_sum_assignment(cost_matrix)
print(row_ind, col_ind)
print(cost_matrix[row_ind, col_ind].sum())

8. 경매 기반 작업 할당

8.1 분산 경매

경매 기반 알고리즘은 분산 환경에서 자연스럽다. 작업이 경매에 부쳐지고, 로봇들이 입찰한다.

8.2 알고리즘

for each task:
    announce task
    each robot computes its bid (cost or utility)
    robots send bids to auctioneer
    auctioneer assigns task to highest bidder

8.3 Sequential Single-Item (SSI) Auction

SSI 경매는 작업을 하나씩 경매에 부친다. 각 라운드에서 로봇이 가장 낮은 비용을 제시한 작업을 받는다.

8.4 응용

경매 기반 알고리즘은 분산 환경에서 효과적이다. 로봇들이 통신을 통해 자체적으로 작업을 분배한다.

9. 시간 의존 작업 할당

9.1 시간 제약

작업에 시간 제약이 있을 수 있다.

• 시작 시간(release time): 작업이 시작 가능한 시점
• 마감 시간(deadline): 작업이 완료되어야 하는 시점
• 지속 시간(duration): 작업의 수행 시간

9.2 스케줄링 문제

시간 제약이 있는 작업 할당은 스케줄링(scheduling) 문제이다. 일반적으로 NP-hard이다.

9.3 휴리스틱

EDF(Earliest Deadline First), SJF(Shortest Job First) 등의 휴리스틱이 사용된다.

10. 동적 작업 할당

10.1 동적 환경

작업이 시간에 따라 추가되거나 변경될 수 있다. 동적 작업 할당이 필요하다.

10.2 점진적 할당

새로운 작업이 도착하면 기존 할당을 부분적으로 갱신한다.

10.3 재할당

상황 변화에 따라 작업을 재할당한다. 부분 또는 전체 재할당이 가능하다.

11. 그래프 알고리즘의 응용

11.1 최단 경로

작업 시퀀스의 비용을 최소화하는 문제는 그래프 위의 최단 경로 문제로 변환될 수 있다.

11.2 최소 신장 트리

작업 사이의 비용을 모두 고려할 때 MST가 사용될 수 있다.

11.3 최대 흐름

자원 할당 문제는 최대 흐름(max flow) 문제로 모델링될 수 있다.

11.4 매칭

이분 매칭이 작업 할당의 표준이다.

12. 여행하는 외판원 문제

12.1 TSP

여행하는 외판원 문제(Traveling Salesman Problem, TSP)는 모든 도시를 한 번씩 방문하는 최소 비용 경로를 찾는 문제이다.

12.2 로봇 작업과의 관계

로봇이 여러 위치에서 작업을 수행할 때 TSP가 적용된다. 로봇이 모든 작업 위치를 방문하는 가장 효율적인 경로를 찾는다.

12.3 NP-hard

TSP는 NP-hard 문제이다. 정확한 해는 작은 인스턴스에서만 가능하다.

12.4 근사 알고리즘

• MST 기반: MST를 사용한 근사
• Christofides: 1.5-근사 알고리즘
• Lin-Kernighan: 휴리스틱 알고리즘
• 2-opt, 3-opt: 지역 검색

13. 차량 라우팅 문제

13.1 VRP

차량 라우팅 문제(Vehicle Routing Problem, VRP)는 TSP의 일반화이다. 여러 차량이 여러 고객을 방문한다.

13.2 변형

• CVRP (Capacitated VRP): 차량의 용량 제약
• VRPTW (VRP with Time Windows): 시간 창 제약
• DVRP (Dynamic VRP): 동적 환경

13.3 응용

VRP는 배달, 픽업, 서비스 등 다양한 로봇 응용에서 활용된다.

14. 자원 제약

14.1 자원

작업 수행에 필요한 자원이 제한적일 수 있다.

• 로봇의 수
• 도구
• 에너지
• 시간

14.2 자원 제약 작업 할당

자원 제약을 고려한 작업 할당은 더 복잡한 최적화 문제이다.

14.3 정수 프로그래밍

자원 제약 문제는 정수 프로그래밍(integer programming)으로 표현될 수 있다.

15. 응용 예시: 청소 로봇

여러 청소 로봇이 큰 건물을 청소할 때 각 방을 로봇에 할당하는 문제이다. 헝가리안 알고리즘이나 경매 기반 방법이 사용된다.

def assign_rooms_to_robots(rooms, robots):
    cost_matrix = compute_costs(rooms, robots)
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    return list(zip(row_ind, col_ind))

16. 응용 예시: 배달 로봇

여러 배달 로봇이 여러 패키지를 배달할 때 VRP가 적용된다. 각 로봇의 경로가 최적화된다.

17. 응용 예시: 매니퓰레이션

매니퓰레이터가 여러 부품을 조립할 때 작업 시퀀스가 결정된다. 부품 사이의 의존성이 DAG로 표현된다.

18. 응용 예시: 다중 드론 감시

여러 드론이 큰 영역을 감시할 때 각 영역을 드론에 할당한다. 영역 분할과 작업 할당이 결합된다.

19. 응용 예시: 창고 자동화

자동화된 창고에서 여러 로봇이 물품을 운반한다. 작업이 동적으로 추가되며, 실시간 할당이 필요하다.

20. 응용 예시: 재난 대응

재난 상황에서 여러 로봇이 협력하여 구조와 복구 작업을 수행한다. 작업 우선순위와 자원 제약이 고려된다.

21. 학습 기반 작업 할당

21.1 강화 학습

강화 학습은 작업 할당 정책을 학습할 수 있다. 환경과 보상을 통해 최적 정책을 발견한다.

21.2 그래프 신경망

그래프 신경망(GNN)은 그래프 구조의 작업 할당 문제에 적합하다.

21.3 응용

학습 기반 방법은 동적이고 복잡한 환경에서 효과적이다.

22. 분산 임무 계획

22.1 분산 환경

각 로봇이 자체적으로 결정을 내리는 분산 환경에서의 임무 계획이다.

22.2 합의 기반

합의 알고리즘을 사용한 분산 결정이 있다.

22.3 통신 비용

통신 비용을 고려한 알고리즘이 필요하다.

23. 강건성

23.1 실패 처리

작업 수행 중 로봇이 실패할 수 있다. 이러한 경우 작업이 다른 로봇에 재할당되어야 한다.

23.2 동적 재계획

상황 변화에 따라 임무를 동적으로 재계획한다.

23.3 강건 최적화

불확실성을 명시적으로 고려한 강건 최적화가 사용될 수 있다.

24. 라이브러리와 도구

24.1 Google OR-Tools

OR-Tools는 Google의 운영 연구 도구이며, 다양한 작업 할당과 라우팅 문제를 푼다.

from ortools.sat.python import cp_model

model = cp_model.CpModel()
# 변수와 제약 추가
solver = cp_model.CpSolver()
status = solver.Solve(model)

24.2 Gurobi, CPLEX

Gurobi와 CPLEX는 상업용 최적화 솔버이며, 대규모 작업 할당 문제를 푼다.

24.3 ROS 패키지

ROS의 actionlib, MoveIt 등은 로봇 작업의 실행을 지원한다.

25. 학습의 가치

그래프 기반 임무 계획과 작업 할당을 이해하는 것은 다음과 같은 이점을 제공한다.

• 로봇 시스템의 고급 기능을 학습한다.
• 다양한 그래프 알고리즘의 응용을 익힌다.
• 실제 로봇 응용을 모델링할 수 있다.
• 다중 로봇 시스템의 핵심 알고리즘을 이해한다.

26. 학습 권장사항

26.1 직접 모델링

실제 응용을 그래프로 모델링해 본다. 작업 의존성과 비용을 정의한다.

26.2 알고리즘 구현

헝가리안, 경매 기반 등의 알고리즘을 구현해 본다.

26.3 시뮬레이션

다중 로봇 시뮬레이터에서 작업 할당 알고리즘을 실험한다.

26.4 라이브러리 활용

OR-Tools 등을 사용하여 실제 문제를 푼다.

27. 본 절의 의의

본 절은 그래프 기반 임무 계획과 작업 할당을 다루었다. 이는 로봇 시스템의 고급 기능이며, 다양한 그래프 알고리즘이 활용된다. 임무 계획과 작업 할당의 이해는 복잡한 로봇 응용을 설계하고 구현하는 데 필수적이다.

28. 참고 문헌

• Gerkey, B. P., & Matarić, M. J. (2004). “A formal analysis and taxonomy of task allocation in multi-robot systems.” International Journal of Robotics Research, 23(9), 939–954.
• Khamis, A., Hussein, A., & Elmogy, A. (2015). “Multi-robot task allocation: A review of the state-of-the-art.” Cooperative Robots and Sensor Networks, 31–51.
• Korsah, G. A., Stentz, A., & Dias, M. B. (2013). “A comprehensive taxonomy for multi-robot task allocation.” International Journal of Robotics Research, 32(12), 1495–1512.
• Kuhn, H. W. (1955). “The Hungarian method for the assignment problem.” Naval Research Logistics Quarterly, 2(1-2), 83–97.
• Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM.
• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.

version: 1.0