1. 서 론
무인항공기술이 발전함에 따라 다분야에서 무인항공기 의 활용도가 높아지고 있다. 특히, 최근들어 무인기의 활 용이 정찰, 감시 임무와 같은 군사적 임무에 국한되지 않 고 물자 수송 및 인명 구조 활동등 다양한 분야로 확대되 는 추세이다. 뿐만 아니라, 개별 무인기가 수행하던 임무 를 벗어나 다수의 무인기가 협업을 통해 하나의 목적을 지닌 임무를 수행하는 추세로 변화하고 있다. 복수/다수의 무인기가 협업함에 따라 중앙 집중식 의사결정 시스템보 다 변화하는 환경에 맞춰서 의사결정을 할 수 있는 분산 의사 결정 알고리듬에 대한 연구가 지속적으로 이루어지
고 있다[1,4-6]. 그 예로 경매 알고리듬을 활용한 CBBA
(Consensus-Based Bundle Algorithm) 알고리듬이 있다. CBBA 알고리듬은 하지만 실제적으로 무인 시스템이 수행해야하 는 임무는 단일 임무가 아닌 여러 임무가 복합적으로 엮 여 임무 간에 제약조건이 존재한다. 따라서 이러한 제약조
건을 가진 임무 상황에서 임무를 분배하는 알고리듬에 대 한 연구가 필요하다. 이러한 요구 사항에 맞춰 C-CBBA라 는 알고리듬을 활용할 수 있다. C-CBBA는 CBBA 알고리 듬을 발전시킨 알고리듬으로 상호간에 제약조건이 있는 문제들을 다룰 수 있다는 장점이 있다.
본 논문에서는 실제 발생 가능한 여러 복함 입무 중에 서 임명 구조 및 군사 작전에 활용도가 높은 협업 수송 임 무를 분산 협업 알고리듬으로 해결 하기 위해 C-CBBA알 고리듬을 활용하였다. 협업 수송 임무의 특성상 임무간에 시공간적으로 강한 제약 조건이 생기게 된다. 기존의 C- CBBA가 임무간에 제약조건을 다루고 있으나, 시공간적 제약조건이 매우 강하게 걸릴경우에 대해 다루고 있는 것 은 아니다. 따라서 기존의 C-CBBA 혹은 CBBA를 활용하 여 이러한 문제를 해결하기 위해서는 알고리듬 내에 임무 구조에 대해 새로이 고찰해봐야할 필요가 있다.
2장에서는 본 논분의 배경이 되는 CBBA와 C-CBBA 알 고리듬에 대해서 간략히 다룬다. 이후 3장에서는 본 논문 에서 다루고자하는 협업 수송 임무에 대해 설명하고, 이를 C-CBBA 알고리듬을 적용하여 문제를 해결하기 위해 어떤 임무 구조를 적용해야하는지에 대해 논한다.
Received : Dec. 12. 2014; Reviewed : Mar. 25. 2015; Accpeted : Apr. 17. 2015
※ This work was supported in part by Cooperative System of Heterogeneous Unmanned Intelligence Aerial Vehicle Project funded by Agency for Defense Development under the contract number UE124026JD.
† Corresponding author: Aerospace engineering, KAIST, Guseong-dong, Yuseong-gu, Daejeon, Korea ([email protected])
1 Department of Aerospace engineering, KAIST([email protected])
Copyright KROSⓒ
협업 수송 임무을 위한 분산 임무 구조
A Decentralized Task Structure for Cooperative Transportation Missions
김 금 성1, 최 한 림†
Keum-Seong Kim1, Han-Lim Choi†
Abstract This paper presents a modified task structure of coupled-constraints consensus based bundle algorithm especially to resolve the cooperative transportation problem. The cooperative transportation mission has various types of constraints. A modified framework to generate activities and subtasks to solve time and task constraints of the transportation mission by using coupled-constraints consensus based bundle algorithm is suggested. In this paper modifications on task structure, reward function and arrival time calculation are suggested to handle the constraints of cooperative transportation mission.
Keywords: Task structure, cooperative transportation, coupled-constraints cbba
2. Co
먼저, 이 장 협업 수송 임무 고리듬에 대해
2.1 CBBA CBBA(Cons 반 (market-bas 본 알고리듬은 적해를 제공한 를 보장한다.
구성되어있다 계에서는 각 무 무 집단을 생 임무의 갯수에 추가하게 된다 각 무인기가 하여 서로 다른 충돌을 방지한
기본적인 C 한다. 모든 임 때문에 각 무 에 임무지역에 할당을 수행한 고리듬인 C-C 태의 임무 특 임무 수행시간 격과 같은 임무
Table 1. Mission
task.type task.value task.position task.start task.end task.duration task.lamba
nsensus base
장에서는 본 논문 무 구조를 적용 해 설명한다.[3]
sensus-Based Bun sed) 분산 경매 은 임무 할당 문 한다. 특히 최적해
CBBA는 번들 다. CBBA의 가장
무인기가 번들, 생성한다. 각 무
에 다다를때까지 다. CBBA의 두번
자신의 정보를 다른 무인기간에
한다.
CBBA에서 임무 임무는 time win 무인기는 자신이 에 도달할 수 있 한다. 이러한 임무 CBBA에서도 마 특성은 제한된 시
간이 명확히 나오 무를 정의하기에
n Characteristics
Task types(transp Score function th Task position Time that task ca Time that task is Processing time Reduction rate o
ed bundle alg
문에서 제안하는 용하게될 CBBA
undle Algorithm) 알고리듬이라고 문제에 대해서 우 해에 대해 최소 생성 단계와 의 장 첫 번째 단계인
즉 무인기가 수 인기의 번들에 지 번들내에 임무
번째 단계는 의 를 업데이트한 시
임무 할당에 있
무특성은 [Table ndow 형식으로 임무가 생성되 있는지 여부를
무 특성은 CBB 마찬가지로 적용된
시간 사이에 임 오는 무인 정찰 에 적합하다.
in CBBA
portation, surveillanc hat can be obtain by a
an be performed in a expired in a scenario for tasks
f a score function as
gorithm
는 새로운 형태의 및 C-CBBA 알
기법은 시장-기 라고 할 수 있다
우수한 근사 최 소 50%의 최적도 의견 일치 단계로 인 번들 생성 단 수행해야하는 임 제한되어 있는 무를 지속적으로 견 일치 단계로 시간을 기준으로 있어 발생가능한
1]과 같이 정의 정의되어 있기 되어있는 시간내 판단하여 임무 BA의 확장형 알 된다. 이러한 형 임무가 발생하고 찰 혹은 무인 폭
ce, strike,…etc) agent
scenario o
time passes
의 알
기 다.
최 도 로 단 임 는 로 로 로 한
의 기 내 무 알 형 고 폭
2.2 C- 다수의 는 것 중 Constraint Based Bu 한 조건이 위해 기존 협업 임 제한 조건 조건이 있 임무 사이 타낸다. Dependen (Mutual E 또한 서 수행 시간 약 조건의 C-CBB Algorithm 존재하는 으로서 상 해결한다
Table 2. D Unilatera Depende
Mutual Depende
Mutual Exclusive
Table 3. T
Simultane Before After During Not durin Between
-CBBA[2]
무인 시스템의 중에 하나가 t)이다. C-CBBA undle Algorithm의 이 발생하는 상 존의 CBBA 알고 임무 계획에 있 건에는 임무 간 있다. 임무 간 상 이의 존재할 수
임무 사이의 상 ncy), 상호의존 Exclusive) 으로 표 서로 의존적인 관 간에 대한 제약조 의 종류는 다음과 BA(Coupled Con m) 기법은 위와 는 임무를 묶어 하
상호간에 제약조 다.
Dependency struct al
ency
ency
e
Time Constraints i
neous Task A an Task A m Task A is Task A is ng Task A is Task A is
의 협업과정에서 바로 상호간 A 란 Coupled C 의 약자로 이름 상위 단계의 복합
고리듬을 발전시 어 발생 가능한 상관 관계 및 임 상관 관계는 복
있는 상호 연관 상관 관계는 단 존(Mutual Depe
표현이 가능하다 관계가 성립하는 약조건이 존재할
과 같이 구분할 nstraints Consen
같이 상호 간에 하나의 활동(Ac 조건이 존재하는
ture between tas T t
T m
T m
n C-CBBA
nd B must be perform must be perfumed bef
performed after task performed during ta performed before or performed between
필연적으로 수 제한 조건(Co Constraints Cons 그대로 임무간 합 임무를 해결 시킨 것이다.
한 주요 상호 연 임무 수행 시간 복잡한 임무 상황
관적 상관 관계를 단방향의존(Unil endency), 상호 다.
는 임무 간에는 수 있으며 시간 수 있다.
ensus Based B 에 커플링(Coupli ctivity)단위로 나 는 임무 할당 문
sks in C-CBBA Task B is dependent task A
Task A and B are mutually dependent
Task A and B are mutually exclusive
med at the same time fore task B perfume k B
ask B is on the proces r after task B
task A and C
수반되 oupled sensus 간에 제 결하기
연과적 제한 황에서 를 나 lateral 호배척
임무 간 제
Bundle ing)이 나타냄 문제를
on
e.
ss
3.1 임무 개 여러 대의 송 임무의 경우 다. 특히, 여러 를 수행해야기 에 적용하기 위 요로 하다. 특 새로 정의하고 추가함으로써, 다. 본 연구에 가진다고 가정
- 하나의 수송 인기가 필요 - 물체의 수송 기지로 귀환 - 물체 수송을 한 시간 일치
본 논문에서 이 두 대 이상 어올리는 임무 인명 구조 활 용할 것이다.
업 수송 임무 이를 해결하기 하지만 기존의 적용하는 것은 상 모든 무인 이는 동일한 다는 말과 동 수송임무를 수 더불어 정찰 충분히 표현 표현이 불가능 기 위에 물자가
3. 협업
개요
무인기가 협업 우, 제약조건이 러대의 무인기가 기 때문에, 기존 위해서는 적절한 특히 수송문제를
고, 작업 계획간 , 협업 수송 작 에서 다루는 수송 정한다.
송 임무를 수행하 요하다.
송을 위해, 한 무 환해야한다.
을 위한 모든 무 치가 필요하다.
서 대표적으로 고 상의 무인기가 협 무이다. 이러한 활동 혹은 작전 전체 작전이 물 무와 더불어 추가
기 위한 알고리듬 의 C-CBBA를 직 은 어려움이 있다 인기는 임무할당
임무를 여러 무 일하다. 따라서 수행하는 무인기 임무 혹은 폭격 가능했다면, 수 능하다. 이는 임무
가 있는 위치로
수송 임무
하여 물체를 수 많은 임무할당 가 정확히 동시에 존의 C-CBBA를
한 문제 설정 (fo 를 해결함에 있어
간 시간 동기화를 작업 계획 문제를
송임무는 다음과
하기 위해서, 두
무리의 무인기가
무인기는 임무수
고려하고 있는 협업을 통해 하
형태의 임무는 상황에서의 물자 물자 수송/인명
가적인 임무로 듬으로 C-CBBA 직접적으로 협업 다. CBBA 및 C 당에 있어 충돌이
무인기가 동시에 수송 임무라는 기에 수만큼 복제
격 임무가 하나의 수송 임무는 하나
무 특성상 무인 로 먼저 이동후에
수송해야하는 수 당 문제에 해당한 에 동일한 임무 운송 시나리오 formulation)이 필 어, 임무 구조를 를 위한 단계를 를 해결할 수 있 과 같은 특성을
두 대 이상의 무
가 물체가 위치한
수행에 있어 정확
임무는 위와 같 하나의 물체를 들 는 무인기를 통한 자 수송등에 유 구조와 같은 협 구성이 된다면 A 가 적합하다 업 수송 임무에 C-CBBA의 특성 이 없어야 한다 할당받지 못한 는 하나의 임무를 제해야한다. 그와 의 임무 위치로 나의 임무위치로 인기가 수송을 하 에 실제로 수송
수 한 무 오 필 를 를 있 을
무
한
확
같 들 한 유 협 면 다.
에 성 다.
한 를 와 로 로 하
Fig
이 필요한 유로 인해 계할 필요 부 내용은
3.2 임 임무 구 티(Activity 먼저 기존 요한 임무 있다.
[Table 지점 및 표현함에 CBBA 알 알고리듬을 임무와 같 임무의 시 이 곧 임무 수행시간 가 추가적 범위내에
Table 4. M 임무 종류 개별 수송
임무 협업 수송
임무 정찰 임무 폭격 임무
g. 1. Cooperative
한 지역으로 이동 해 협업 수송 임 요가 있다. 알고 은 아래 절에서
무 구조 설계 구조 설계는 기존
ty) 구성을 새로 존의 정찰, 폭격 무 특성에 대해
4]에서 정찰 임 임무의 발생 시 있어서 무리가 알고리듬 상의 임 듬을 적용할 수 있 같이 일정 시간 시작점에서부터
무의 수행시간이 간 보다는 임무의
적으로 더 필요한 서 이러한 문제
Mission characteris 임무 시작점 (출발지)
임 종료 (목표
√
√
transportation m
동해야하기 때문 임무의 경우 임무 리듬 내 임무 구 다룬다.
존의 C-CBBA알 로 하는 것을 의 격 임무를 비롯하 분석하면 아래
무 및 폭격 임무 시점 및 수행 시
가 없다. 즉 기존 임무 표현으로도 있다. 하지만 수 간 동안 임무를 임무의 종료지 이나 마찬가지 의 시작점과 종료
한 상황이다. C 제를 해결하기 위
stics analysis 임무
료점 표지)
임무 발생시간
√ √
√ √
√ √
√ √
mission example
문이다. 위와 같은 무 구조를 새로이 구조 설계에 대한
알고리듬 내에 액 의미한다. 이를 하여 수송 임무에 래와 같이 나타낼
무의 경우 임무 간이 있으면 임 존의 CBBA 혹은 도 충분히 임무 수송임무의 경우 수행한다기 보 지점까지의 이동 이다. 오히려 임 료지점에 대한 C-CBBA를 활용
위한 방법으로
임무 수행시간
임 수행
√
√
은 이 이 설 한 세
액티비 위해 에 필 낼 수
종료 임무를 은 C- 할당 정찰 보다는 동시간 임무의 정보 용하는 전체
임무 행자
수송임무를 임 임무 최종 지 법을 제안한다 단계의 임무 려할 수 있기 로 고려하여
는 하나의 협 무인기의 수이 되어 있으며 p 지를 나타낸다
이와 같은 로 해결해야할 성으로 임무 수행시의 보상 주어지는 특성 특성을 지닌 는 결과를 가져 가 한 자리에 무를 모두 수행 임무를 모두 할 티 단계의 임무 위배된다.
따라서 이러 무 구조에 추 보상에 대해 새
Fig. 2.
임무 시작점을 점을 나타낼수 다. C-CBBA가
즉작전 수준의 때문에 협업 수 식 (1)과 같이 협업 수송 임무를 이다. 즉 수송 액
p 는 세부 임무 특 다.
, , , ,
형식으로 임무 할 문제가 남아
할당을 수행한 상 구조 및 시간 성 때문에 한 대 임무 지역에 가 져온다. 즉 식 ( 고정되어 있는 행하고 두 번째 할당받아 수행하 무가 온전히 할당
러한 문제를 해 추가적으로 임무 새로운 형태의
cooperative trans
나타낼 수 있는 있는 세부 임무 엑티비티(Activ
임무에 대한 수송 임무를 작
임무 구성을 할 를 수행하기위해 액티비티는 임무
특성을 q는 몇 번
⋯ , , , , ,
무를 구성한다고 있다. [Fig 2]는 한 결과이다. 본
간이 지남에 따라 대의 무인기가 같 가서 순차적으로
(1)을 예로 들면 는 , , , , ⋯ 무인기가 ,
하게 된다. 이러한 당되어야하는 수송
결 하기 위해 할당시에 얻을 구조를 제안한다
sportation mission
는 세부 임무와 무로 나누는 방 vity)단위로 상위 임무 할당을 고 작전 수준의 임무 할 수 있다. 이때 해 반드시 필요한
, 로 구성이 번째 세부 임무인
, ⋯ , , (1)
해도 추가적으 제안한 임무 구 결과에서 임무 라 임무 보상이 같은 세부 임무 로 임무를 수행하 면 첫번째 무인기
⋯ , , 세부 임 , ⋯ , , 세부 한 결과는 액티비 송 임무의 특성에
앞서 제안한 임 을 수 있는 임무
다.
n result 1 와 방 위 고 무 때 한 이 인
으 구 무 이 무 하 기 임 부 비 에
임 무
Fig
액티비 기가 서로 해 임무의 협업 수 은 임무간 이 협업 수 이기 때문 기의 수만 CBBA 가 고 있기 의 수행시 같은 시간 따라서 협 을 조정하 대기(watin 기가 임무 접근 했을 모두 시작 인기가 이 인기가 이 시 필요한 기 임무의 에 맞춰서
위와 같
g. 3. cooperative
티가 수송임무인 로 다른 특성을 지 의 보상함수를 추가
수송 임무 계획 간에 존재하는 강
수송 임무가 여 문에 임무 할당을 만큼 복제하여 임 가 모두 time win
때문에 초기 무 시간이 달라진다 간에 임무를 수행 협업 수송 임무에 하는 임무가 추가 ing task) 임무를 무 시작점(수송할 을 때, 본 임무를 작점에 도착할 이러한 임무를 수 이러한 임무를 수 한 임무라고 할 의 임무 수행 시 서 조정이 된다.
같이 무인 시스템
e transportation m
인 경우 즉, 지닌 세부 임무를
가로 지급하도록 에서 마지막으로 강한 제약 조건 여러대의 무인기 당을 위해 동일한
임무 구조를 설계 ndow 형태의 임 무인기의 위치에 다. 하지만 협업
행해야하는 특성 에 있어서 만큼 가적으로 필요하 를 추가한다. 본
할 물체가 대기 를 수행해야하는 때까지 대기 하 수행하기 위해하 수행하기 위해
수 있다. 즉 본 시간(duration무인
, 템간의 정확한
mission result 2
에 대해 를 할당하는 경우 록 하였다.
로 고려해야할 이다. 앞서 언급
로 이루어지는 한 세부 임무를 계한다. CBBA 임무구조에 기반을 에 따라 각 세부
수송 임무는 정 성을 가지고 있 큼은 강제적으로
하다. 이를 위해 임무의 역할을 기하고 있는 지 는 나머지 무인 하는 임무로 실제
하는 임무로 실제 운용이 된다면 본 단계에서 기지 인기가 도착하는
1, … ,
시간 동기화는 무인 우에 대
상황 급했듯 임무 무인 및 C- 을 두 임무 정확히 있으며, 시간 기지 무인 점)에 인기가 제 무 제 무 반드 지 대 시간
(2)
합의
과정에서 임무 과정에서 임무 하는 경우에 스템을 기준으 확히 맞출 수
3.3 결과 최종적으로 임무에 대해 C 과는 [Fig 4-5 수송 임무를 해 임무를 할당받 수정한 후 C- 확인한 경우 임 무인기가 동시
Fig. 4. coopera structur
Fig. 5. coopera structur
무 수행 시간을 무간 수행시간을
대해서 가장 늦 으로 업데이트 함
있다.
앞서 제안한 C-CBBA를 적용 5]와 같다. 앞서
해결 할 경우 하 받는 결과를 보았 -CBBA를 활용하 임무 분배가 적절 시에 수송임무를
ative transportatio re – agents’ path
ative transportatio re – agents’ sche
조정한다. 즉, 을 비교한 후, 수
늦게 기지에 도착 함으로써 임무
임무구조를 따라 용하여 시뮬레이 서 기존의 C-CBB
하나의 에이전트 았다. 반면 임무 하여 수송 임무 절히 이루어져 최
수행함을 알 수
on mission result h
on mission result edules
합의(Consensus 수송임무를 수행
착하는 무인 시 수행 시간을 정
라서 협업 수송 이션을 돌려본 결 BA를 활용하여 트가 같은 종류의 무 구조를 새로이 무에 대한 결과를 최종적으로 모든 수 있다.
after changing
after changing s) 행 시 정
송 결 여 의 이 를 든
본 논문 송해야하는 조 형태를 시했다. 수 당하며, 특 무를 수행 오에 적용 필요로 하 조를 새로 계를 추가 수 있다.
[1] Pon M., com con 201 [2] Wh (201 con Con [3] Cho base Rob [4] Cho Dec with Con [5] John
Dec distr (CD 470 [6] Pond
& H ensu team on,
문에서는 여러 대 하는 수송 임무를
를 수송 임무에 수송임무는 제약 특히 여러대의 무 행해야기 때문에 용하기 위해서는 하다. 이를 위해 로 정의하고, 작 가함으로써, 협업
nda, S., Redding,
& Vian, J. (20 mplex missions nstraints. In Am 0 (pp. 3998-400 hitten, A. K., Cho
11, June). Decen nstraints in comp nference (ACC), oi, H. L., Brunet, ed decentralized botics, IEEE Tran oi, H. L., Whitte centralized task h cooperation nference (ACC), nson, L., Choi, H cember). Allowin ributed task al DC), 2012 IEEE 02-4708). IEEE.
da, S. S., Johnson How, J. P. (201
ure network con ms. Selected Are 30(5), 861-869.
R
4. 결 론
대의 무인기가 를 해결 하기 위
적합하도록 변 약조건이 많은
무인기가 정확히 에, 기존의 C-CB 는 적절한 문제 해 임무 구조 및 작업 계획간 시간
업 수송 작업 계
, J., Choi, H. L., 10, June). Decen s with dynam merican Control
3). IEEE.
oi, H. L., Johnson ntralized task all plex missions. I 2011 (pp. 1642- , L., & How, J. P d auctions for ro nsactions on, 25(
en, A. K., & How allocation for constraints. In 2010 (pp. 3057- H. L., Ponda, S., ng non-submodu llocation. In D E 51st Annual
n, L. B., Kopeik 2). Distributed p nnectivity for dy eas in Communic References
협업하여 물체를 위해 기존의 임무 변형시키는 방안을 임무할당 문제에 히 동시에 동일한 BBA를 운송 시
설정 (formulati 임무 보상 지금 간 동기화를 위한 계획 문제를 해
, How, J. P., Vav ntralized plannin mic communic Conference (A
n, L. B., & How location with co In American Co -1649). IEEE.
P. (2009). Conse obust task alloc (4), 912-926.
w, J. P. (2010, J heterogeneous t n American Co
-3062). IEEE.
, & How, J. P. ( ular score functio
ecision and Co Conference on
kin, A. N., Choi, H planning strateg ynamic heterogen
cations, IEEE Jo 를 수 무 구 을 제 에 해 한 임 시나리 ion)이 금 구 한 단 해결할
avrina, ng for cation ACC),
w, J. P.
oupled ontrol
ensus- cation.
June).
teams ontrol
(2012, ons in ontrol n (pp.
H. L., ies to neous ournal
2010 K (공 2012 K
(공 2012년~
학
김 금 성 KAIST 항공우주공
공학사)
KAIST 항공우주공 공학석사)
~현재 KAIST 항 학전공 박사과정
공학전공
공학전공
항공우주공 재학중
2010 KAI 2014~현재
20
20
20
IST 항공우주공학 재 KAIST 항공우
최 한 000 KAIST 항공
(공학사) 002 KAIST 항공
(공학석사) 009 MIT, PhD in A
Astronautics) 학전공 조교수 우주공학전공 부
한 림 공우주공학전공
공우주공학전공
Aeronautics and
부교수
