[benthebear93]Multi-Robot Dyanmic Task Allocation for Exploration and Destruction(1)

Multi-Robot Dyanmic Task Allocation for Exploration and Destruction

Abstract

Foraging(수렵)이라고 불리는 환경 탐색은 로보틱스에서 자주 등장하는 주제중 하나이다. 이 논문에서는 멀티로봇의 임무 할당에 중점을 두어 설명한다. 여기서의 임무이라 함은 다수의 로봇이 특정 환경에 투입되서 파괴하는 것을 말한다. 임무의 경우 환경에 대한 탐색 임무와 같이 수행될 수 밖에 없으며, 파괴 임무에 대해서는 타켓과 로봇간의 차이로 인해 수행의 결과가 달라질 수 있다. 이와 같은 변수는 임무들의 수행에 대한 복잡도를 증가시키며 이를 해소하기 위해 3가지 접근 방법을 사용한다.

1. auction based approach

2. vacancy chain approace

3. deep Q-learning approach

 

논문에서는 위 3개의 전략선택 접근 방식을 가제보 가상환경에서 분석하여 그들의 장단점에 대해 이야기한다.

Multi-Robot system은 병렬시스템과 같이 다수의 로봇이 임무를 수행한다는 점에서 맵핑이나, 탐색등에 좋은 성능일 보인다. 또한 한대가 실패한다고 하여도 각각 로봇은 중앙통제가 아닌 로컬측정과 컨트롤로 임무를 수행하기에 실패에 대한 tolerance도 높다.

 

다수의 로봇의 경우 싱글로봇과 다르게 각 로봇에게 어떤 임무를 수행하도록 하는지가 관건이다. 이를 Multi-Robot Task Allocation(MRDT)라 하며 수행에 중요한 역활을 한다. 임무 할당의 경우 환경의 변화에 따라 정적이 아닌 동적으로 진행되어야 하는 경우가 많다. 많은 경우의 임무는 주변 탐색, 우편 배달 등과 같은 로봇과 대립 상황이나 문제가 되지 않는 경우이다. 하지만 그와 반대로 로봇의 파괴까지도 야기될 수 있는 임무들도 있다. 이와 같은 임무들은 기존의 임무 할당 방식으로 접근할 수 없다.

Centralized vs Distributed model

Centralized model의 경우 모든 시스템의 상황을 알 수 있지만, 변화가 많고 스케일이 큰 환경에서는 모든 데이터를 실시간으로 업데이트 하기는 어렵다. 이와 반대로 Distributed model은 task allocation을 바탕으로 개별로 데이터를 수집한 로봇들이 각자 임무를 수행할 수 있도록 한다. 단, 로봇의 임무 할당의 불안전성으로 인해 시스템 전체의 효율을 낮출 수도 있다. 따라서 임무할당은 distributed model에 매우 중요한 요소이다.

Auction Based

옥션기반 임무할당 접근 방식은 실제 옥션과 비슷한 방식으로 이루어진다. 특정 임무에 대한 옥션을 시작하여 각각 개별의 로봇들이 입찰(bid)를 시작한다. 입찰 과정에서 로봇의 위치, 보유한 자원 등이 고려요소로 작용된다. 각 로봇이 계산한 입찰가를 브로드캐스팅으로 로봇들과 공유하여, 그 중 입찰가가 높은 로봇이 임무를 받아 수행하게 된다. 이런 과정으로 임무를 할당하기에 중앙통제형이 아닌 로컬에서 임무 할당이 이루어질 수 있다.

 

로보틱스에 경제개념에서 가져온 개념들이 종종 보인다. 옥션 기반 임무할당 외에도 resource welfare이라 사회복지(social welfare) 개념에서 따온 로봇의 보유 자원 척도 판단 개념도 있다. 경제 개념에서는 평균 소득수준과 소득 불균등 분포와 사회복지함수를 사용하여 정량적으로 측정하며, 이를 비슷하게 로봇에도 적용시킬 수 있다.

침고논문 : “탐지 및 공격 임무 수행하는 로봇팀의 효율적 자원관리릍 통한 작업할당방식” - 김민혁, 육군 분석평가단

Vacancy Chain

Vacancy란 공백이라는 의미로 임무할당에 있어서는 특정 로봇이 임무를 할당받지 못한 상태를 의미한다. 임무 할당에 있어 공백이 생기면 임무를 다시 할당하게 된다. 동적 환경에서 이는 연속적인(Chain) 재임무할당(task reallocation)을 야기한다. 이런 연속적인 임무할당과 강화학습을 접목시켜 전체 시스템에 대한 최적의 할당 방식이 사용되기도 한다.

Learning-based

MRS이 발전하면서 미지의 동적인 환경에서 시스템을 구동해야되게 되었다. 따라서 예측하기 더욱 어려운 경우들이 많아졌고, 이를 해소하기 위해 학습기반 알고리즘들이 적용되기 시작했다. Kapetanakis 와 Kudenko가 만든 두개의 학습 기법이 있다.

1. Multi single-agent learning
2. Social multi-agent learning

두 방식의 차이는 동료의 학습데이터를 사용하는지에 있다. 이에 따라 학습 된 데이터를 전달하는 방식에 대한 논문도 존재한다.

참고논문 : “Behavior Transfer for Value-Function-Based Reinforcement.”

Task Allocation for Exploration and Destruction

일반적인 MRTA 문제에서는 로봇과 임무 2가지의 요소가 고려된다. 이 논문에서는 탐색과 파과에 중점을 두고 있기에 이에 맞는 모델 설정을 하게 된다.

 

1. r_i : 로봇

2. P̃_i(Strike ability) : 로봇이 타켓을 파괴할 수 있는 능력

3. P_i(Anti-Strike ability) : 타켓이 반대로 로봇을 파괴할 수 있는 능력

4. O_i(로봇이 파괴하려는 타켓들)

임무를 수행하는 과정에서 로봇(r_i)자체는 피해를 입을 수 있지만 P_i와 P̃_i 자체는 변하지 않는다.

 

2편에서 계속