협업 수송 임무을 위한 분산 임무 구조

2.1. CBBA

CBBA(Consensus-Based Bundle Algorithm) 기법은 시장-기반 (market-based) 분산 경매 알고리듬이라고 할 수 있다. 본 알고리듬은 임무 할당 문제에 대해서 우수한 근사 최적해를 제공한다. 특히 최적해에 대해 최소 50%의 최적도를 보장한다. CBBA는 번들 생성 단계와 의견 일치 단계로 구성되어있다. CBBA의 가장 첫 번째 단계인 번들 생성 단계에서는 각 무인기가 번들, 즉 무인기가 수행해야하는 임무 집단을 생성한다. 각 무인기의 번들에 제한되어 있는 임무의 갯수에 다다를때까지 번들내에 임무를 지속적으로 추가하게 된다. CBBA의 두번째 단계는 의견 일치 단계로 각 무인기가 자신의 정보를 업데이트한 시간을 기준으로 하여 서로 다른 무인기간에 임무 할당에 있어 발생가능한 충돌을 방지한다.

기본적인 CBBA에서 임무특성은 [Table 1]과 같이 정의한다. 모든 임무는 time window 형식으로 정의되어 있기 때문에 각 무인기는 자신이 임무가 생성되어있는 시간내에 임무지역에 도달할 수 있는지 여부를 판단하여 임무 할당을 수행한다. 이러한 임무 특성은 CBBA의 확장형 알고리듬인 C-CBBA에서도 마찬가지로 적용된다. 이러한 형태의 임무 특성은 제한된 시간 사이에 임무가 발생하고 임무 수행시간이 명확히 나오는 무인 정찰 혹은 무인 폭격과 같은 임무를 정의하기에 적합하다.Table 2

Table 1.

Mission Characteristics in CBBA

Table 2.

Dependency structure between tasks in C-CBBA

2.2. C-CBBA^[2]

다수의 무인 시스템의 협업과정에서 필연적으로 수반되는 것 중에 하나가 바로 상호간 제한 조건(Coupled Constraint)이다. C-CBBA 란 Coupled Constraints Consensus Based Bundle Algorithm의 약자로 이름 그대로 임무간에 제한 조건이 발생하는 상위 단계의 복합 임무를 해결하기 위해 기존의 CBBA 알고리듬을 발전시킨 것이다.

협업 임무 계획에 있어 발생 가능한 주요 상호 연과적 제한 조건에는 임무 간 상관 관계 및 임무 수행 시간 제한 조건이 있다. 임무 간 상관 관계는 복잡한 임무 상황에서 임무 사이의 존재할 수 있는 상호 연관적 상관 관계를 나타낸다. 임무 사이의 상관 관계는 단방향의존(Unilateral Dependency), 상호의존(Mutual Dependency), 상호배척(Mutual Exclusive) 으로 표현이 가능하다.

또한 서로 의존적인 관계가 성립하는 임무 간에는 임무 수행 시간에 대한 제약조건이 존재할 수 있으며 시간 제약 조건의 종류는 다음과 같이 구분할 수 있다.

C-CBBA(Coupled Constraints Consensus Based Bundle Algorithm) 기법은 위와 같이 상호 간에 커플링(Coupling)이 존재하는 임무를 묶어 하나의 활동(Activity)단위로 나타냄으로서 상호간에 제약조건이 존재하는 임무 할당 문제를 해결한다.

3.1. 임무 개요

여러 대의 무인기가 협업하여 물체를 수송해야하는 수송 임무의 경우, 제약조건이 많은 임무할당 문제에 해당한다. 특히, 여러대의 무인기가 정확히 동시에 동일한 임무를 수행해야기 때문에, 기존의 C-CBBA를 운송 시나리오에 적용하기 위해서는 적절한 문제 설정 (formulation)이 필요로 하다. 특히 수송문제를 해결함에 있어, 임무 구조를 새로 정의하고, 작업 계획간 시간 동기화를 위한 단계를 추가함으로써, 협업 수송 작업 계획 문제를 해결할 수 있다. 본 연구에서 다루는 수송임무는 다음과 같은 특성을 가진다고 가정한다.

- 하나의 수송 임무를 수행하기 위해서, 두 대 이상의 무인기가 필요하다.

- 물체의 수송을 위해, 한 무리의 무인기가 물체가 위치한 기지로 귀환해야한다.

- 물체 수송을 위한 모든 무인기는 임무수행에 있어 정확한 시간 일치가 필요하다.

본 논문에서 대표적으로 고려하고 있는 임무는 위와 같이 두 대 이상의 무인기가 협업을 통해 하나의 물체를 들어올리는 임무이다. 이러한 형태의 임무는 무인기를 통한 인명 구조 활동 혹은 작전 상황에서의 물자 수송등에 유용할 것이다. 전체 작전이 물자 수송/인명 구조와 같은 협업 수송 임무와 더불어 추가적인 임무로 구성이 된다면 이를 해결하기 위한 알고리듬으로 C-CBBA 가 적합하다. 하지만 기존의 C-CBBA를 직접적으로 협업 수송 임무에 적용하는 것은 어려움이 있다. CBBA 및 C-CBBA의 특성상 모든 무인기는 임무할당에 있어 충돌이 없어야 한다. 이는 동일한 임무를 여러 무인기가 동시에 할당받지 못한다는 말과 동일하다. 따라서 수송 임무라는 하나의 임무를 수송임무를 수행하는 무인기에 수만큼 복제해야한다. 그와 더불어 정찰 임무 혹은 폭격 임무가 하나의 임무 위치로 충분히 표현 가능했다면, 수송 임무는 하나의 임무위치로 표현이 불가능하다. 이는 임무 특성상 무인기가 수송을 하기 위에 물자가 있는 위치로 먼저 이동후에 실제로 수송

이 필요한 지역으로 이동해야하기 때문이다. 위와 같은 이유로 인해 협업 수송 임무의 경우 임무 구조를 새로이 설계할 필요가 있다. 알고리듬 내 임무 구조 설계에 대한 세부 내용은 아래 절에서 다룬다.

3.2. 임무 구조 설계

임무 구조 설계는 기존의 C-CBBA알고리듬 내에 액티비티(Activity) 구성을 새로 하는 것을 의미한다. 이를 위해 먼저 기존의 정찰, 폭격 임무를 비롯하여 수송 임무에 필요한 임무 특성에 대해 분석하면 아래와 같이 나타낼 수 있다.Table 3

Table 3.

Time Constraints in C-CBBA

[Table 4]에서 정찰 임무 및 폭격 임무의 경우 임무 종료지점 및 임무의 발생 시점 및 수행 시간이 있으면 임무를 표현함에 있어서 무리가 없다. 즉 기존의 CBBA 혹은 C-CBBA 알고리듬 상의 임무 표현으로도 충분히 임무 할당 알고리듬을 적용할 수 있다. 하지만 수송임무의 경우 정찰 임무와 같이 일정 시간 동안 임무를 수행한다기 보다는 임무의 시작점에서부터 임무의 종료지점까지의 이동시간이 곧 임무의 수행시간이나 마찬가지 이다. 오히려 임무의 수행시간 보다는 임무의 시작점과 종료지점에 대한 정보가 추가적으로 더 필요한 상황이다. C-CBBA를 활용하는 범위내에서 이러한 문제를 해결하기 위한 방법으로 전체

Table 4.

Mission characteristics analysis

수송임무를 임무 시작점을 나타낼 수 있는 세부 임무와 임무 최종 지점을 나타낼수 있는 세부 임무로 나누는 방법을 제안한다. C-CBBA가 엑티비티(Activity)단위로 상위 단계의 임무 즉작전 수준의 임무에 대한 임무 할당을 고려할 수 있기 때문에 협업 수송 임무를 작전 수준의 임무로 고려하여 식 (1)과 같이 임무 구성을 할 수 있다. 이때 𝑁는 하나의 협업 수송 임무를 수행하기위해 반드시 필요한 무인기의 수이다. 즉 수송 액티비티는 임무 T_(p,q) 로 구성이 되어 있으며 p 는 세부 임무 특성을 q는 몇 번째 세부 임무인지를 나타낸다.Fig 1

Fig. 1.

Cooperative transportation mission example

이와 같은 형식으로 임무를 구성한다고 해도 추가적으로 해결해야할 문제가 남아 있다. [Fig 2]는 제안한 임무 구성으로 임무 할당을 수행한 결과이다. 본 결과에서 임무 수행시의 보상 구조 및 시간이 지남에 따라 임무 보상이 주어지는 특성 때문에 한 대의 무인기가 같은 세부 임무 특성을 지닌 임무 지역에 가서 순차적으로 임무를 수행하는 결과를 가져온다. 즉 식 (1)을 예로 들면 첫번째 무인기가 한 자리에 고정되어 있는 T_(1,1),T_(1,2),⋯,T_(1,n) 세부 임무를 모두 수행하고 두 번째 무인기가 T_(2,1),⋯,T_(2,n) 세부 임무를 모두 할당받아 수행하게 된다. 이러한 결과는 액티비티 단계의 임무가 온전히 할당되어야하는 수송 임무의 특성에 위배된다.Fig 3

Fig. 2.

cooperative transportation mission result 1

Fig. 3.

cooperative transportation mission result 2

따라서 이러한 문제를 해결 하기 위해 앞서 제안한 임무 구조에 추가적으로 임무 할당시에 얻을 수 있는 임무 보상에 대해 새로운 형태의 구조를 제안한다.

액티비티가 수송임무인 경우 즉, A_Transport 에 대해 무인기가 서로 다른 특성을 지닌 세부 임무를 할당하는 경우에 대해 임무의 보상 함수를 추가로 지급하도록 하였다.

협업 수송 임무 계획에서 마지막으로 고려해야할 상황은 임무간에 존재하는 강한 제약 조건이다. 앞서 언급했듯이 협업 수송 임무가 여러대의 무인기로 이루어지는 임무이기 때문에 임무 할당을 위해 동일한 세부 임무를 무인기의 수만큼 복제하여 임무 구조를 설계한다. CBBA 및 C-CBBA 가 모두 time window 형태의 임무구조에 기반을 두고 있기 때문에 초기 무인기의 위치에 따라 각 세부 임무의 수행시간이 달라진다. 하지만 협업 수송 임무는 정확히 같은 시간에 임무를 수행해야하는 특성을 가지고 있으며, 따라서 협업 수송 임무에 있어서 만큼은 강제적으로 시간을 조정하는 임무가 추가적으로 필요하다. 이를 위해 기지 대기(wating task) 임무를 추가한다. 본 임무의 역할을 무인기가 임무 시작점(수송할 물체가 대기하고 있는 지점)에 접근 했을 때, 본 임무를 수행해야하는 나머지 무인기가 모두 시작점에 도착할 때까지 대기 하는 임무로 실제 무인기가 이러한 임무를 수행하기 위해하는 임무로 실제 무인기가 이러한 임무를 수행하기 위해 운용이 된다면 반드시 필요한 임무라고 할 수 있다. 즉 본 단계에서 기지 대기 임무의 임무 수행 시간(duration무인기가 도착하는 시간에 맞춰서 조정이 된다.

위와 같이 무인 시스템간의 정확한 시간 동기화는 합의 과정에서 임무 수행 시간을 조정한다. 즉, 합의(Consensus)과정에서 임무간 수행시간을 비교한 후, 수송임무를 수행하는 경우에 대해서 가장 늦게 기지에 도착하는 무인 시스템을 기준으로 업데이트 함으로써 임무 수행 시간을 정확히 맞출 수 있다.

3.3. 결과

최종적으로 앞서 제안한 임무구조를 따라서 협업 수송 임무에 대해 C-CBBA를 적용하여 시뮬레이션을 돌려본 결과는 [Fig 4-5] 와 같다. 앞서 기존의 C-CBBA를 활용하여 수송 임무를 해결 할 경우 하나의 에이전트가 같은 종류의 임무를 할당받는 결과를 보았다. 반면 임무 구조를 새로이 수정한 후 C-CBBA를 활용하여 수송 임무에 대한 결과를 확인한 경우 임무 분배가 적절히 이루어져 최종적으로 모든 무인기가 동시에 수송임무를 수행함을 알 수 있다.

Fig. 4.

cooperative transportation mission result after changing structure – agents’ path

Fig. 5.

cooperative transportation mission result after changing structure – agents’ schedules