[논문리뷰]Sold!: Auction methods for multirobot coordination

요즘 멀티로봇 시스템의 임무/작업할당(Task allocation)에관한 옛날 논문들을 고대유적 발굴하듯이 읽고 있습니다. 이 연구가 생각보다 오래전부터 시작되어 왔다는 것에 놀랐고, 그때 제시한 임무할당에 대한 근본적인 challenge들이 아직까지도 연구되고 있는 듯한 느낌을 받았습니다. 임무할당 옛 논문의 흐름을 보면 1992년 부터 시작이 되는 것으로 보입니다.

ACTRESS(1992)→ALLIANCE(1998)→MURDOCH(2002)→...

저는 그 중에서 가장많이 인용이 된 MURDOCH 논문을 오늘 정리해볼까 합니다. 논문이나온지 오래된 것이라 그것을 감안하고 보는 것이 좋을 듯 합니다. 사실 정리를 깔끔하게 한게 아니라 읽으면서 기록한 note정도로 봐주시면 감사하겠습니다. ㅠㅠ

---

기본적으로 임무할당은 여러가지 임무(방문, 배달, 감시 등)가 주어졌을때 어떤 로봇이 어떤 작업을하는 것이 전체 팀에게 가장 이로울지 결정하는 것을 말함

Sold!: Auction methods for multirobot coordination

Sold!: auction methods for multirobot coordination

Introduction

MURDOCH은 로봇들이 서로 통신하며 임무할당을 진행하는 분산 시스템(decentralized/distributed system)에서의 운용을 위한 알고리즘임

robot cooperation model의 종류

1. Emergent cooperation
   • 군집(swarm) 시스템과 같이 이웃 개체와의 상호작용만으로도 전체 시스템의 변화를 일으키는 행동
   • 적용할 수 있는 응용분야가 제한적임
   • 보통 같은 종류의 로봇들을 운용하는 것을 가정 (homogeneous robots)
2. Intentional cooperation
   • 명시적(explicit)으로 서로 어떻게 협력할 것인지 규칙을 통해 협력

본 논문은 intentional cooperation에대해 다룸

 

사용한 기법

1. Fitness-based auction
   • 로봇-작업 쌍이 주어졌을 때 누가 더 작업이 어울리는지(fitness)를 계산하고 서로 경매(auction)과정을 통해 작업을 낙찰 받는 방식을 사용 (매우 흥미로움)
2. Simple negotiation protocol
   • 각자가 계산한 낙찰가를  비교하는 간단한 방법(추후 설명)을 제시

시험 환경

1. Tightly coupled multirobot physical manipulation task
   • 서로 긴밀한 협력이 있어야 가능한 작업 (예: box pushing)
2. Loosely coupled multirobot experiment in long-term autonomy
   • 작업 자체는 coupling 정도가 작지만 오랜 시간 자율적으로 잘 협해야하는 환경(예: foraging/cleaning)

주 contribution

Distributed negotiation mechanism을 실제 멀티로봇 시스템에 적용하여 성능을 검증

Problem Definition

Assumption

1. 물리적인 멀티로봇 시스템 (그동안의 임무할당은 컴퓨팅시스템의 소프트웨어적 적용이 주됐음)
2. 이종(heterogeneous) 로봇(서로 다른 스킬을 보유)
3. 서로 통신 할 수 있으나 메시지 손실가능성 존재
4. 서로 협력적인 로봇들 (적대적으로 방해하는 존재는 없음)
5. 작업에 대한 실패가능성 존재
6. 자신의 실패를 알아차리지 못함
7. 다목적 로봇(한 개체가 여러 스킬 보유)
8. 작업 생성에 대해 정해진 규칙이 없음
9. 작업이 할당되면 로봇은 스스로 그 작업을 처리할 수 있음 (능력 보유)

마지막 3가지 조건은 멀티로봇시스템이 일반적으로 유용해지기위해 갖춰져야할 조건이기도 함

문제를 dynamic resource-allocation problem으로 정의 (NP-complete conjunctive planning problem). 즉 여러 작업을 한번에 할당시키는 것이 아니라 한번에 한 작업씩 할당시키겠다는 뜻. planning을 미리해놓는건 만일의 사태에 대응하기 위해 좋지 않다. 특히 작업이 랜덤하게 생성되는 지금 같은 경우에서는 작업 생성에 대한 모델이 없을 것이고 플래닝은 그닥 효과적이지 않음

objectives

1. resource usage (예: minsum) 전체 연료 사용량 최소화
2. task completion time (예: minmax) 전체 임무 완수 시간 최소화
3. communication overhead 통신 오버헤드 최소화

3가지 objective는 서로 tradeoff가 존재. 3번은 무슨 tradeoff인지 약간 헷갈렸으나 1,2번을 잘할라면 communication bandwidth가 더 확장되어야 한다는 뜻이었음

Related works

• Unembodied task allocation
  • database system 같이 physical robot이 아닌 시스템들에서 많이 사용되는 contract network protocol. 대표적 구조로 Open Agent Architecture, RETSINA가 있음. 두 구조 모두 central broker가 필요하지만 MURDOCH은 완전 분산적으로 matchmaking을 진행함
  • Condor, Challenger 같은 distributed 시스템도 존재하지만 network의 모든 agent들의 정보가 필요하다. 얘네로 로봇시스템에 적용한 사례가 있긴한데 MURDOCH은 Auction기반으로는 최초임
• Embodied task allocation
  • ALLIANCE 라는 프레임워크가 기존에 존재했음.(foraging, box pushing, target tracking 수행) 자기자신과 모든 팀메이트의 fitness와 progress를 추적하고 이를 기반으로 task를 수행함
  • BLE라는 추가적인 distributed 모델이 있는데, 얘네는 communication을 지속적으로 하면서 task allocation을 수행함으로써 dynamic environment에 좀 더 잘 대응함
  • MURDOCH은 BLE와 ALLIANCE와 달리 behavior suppress에 대한 가정이 없음

MURDOCH

• Publish/Subscribe Messaging
  • Resource들을 Topic 이름으로 구성한다.
  • Topic 이름 구성: (physical device, higher level capability, abstracted notions of current state)
    • ex) (camera/gripper/sonar, mobile/door-opener, idle/have-puck/currently-pushing-box)
• Auction Protocol
  • First-price-one-round auction
    • Task announcement
      • 한 agent가 ‘auctioneer’처럼 task에 대한 message를 뿌린다. message에는 task의 자세한 정보(이름, 길이, topic name 등)가 기록됨
      • 생성된 task message는 해당하는 topic에 대해 뿌려짐
    • Metric evaluation
      • 로봇의 task에대한 적합도(fitness) 계산을 위한 metric (거리, 연료 등 고려 가능)
    • Bid submission
      • metric 계산을 통해 각 로봇은 자신이 task에 얼마나 적합한지에 대한 fitness를 계산한 score를 bid message로 publish.
    • Close of auction
      • 특정 시간이 지난 후 auctioneer는 bid를 통해 winner를 선정하고 bidder 들에게 close message를 보냄. 이때 winner는 task에 대한 계약을 따내고 나머지 로봇들은 새로운 task가 생기길 대기함
      • 이떄 time limitation을 건 이유는 timeout을 감지해서 fault recovery를 돕기 위해서이다.
    • Progress monitoring/contract renewal
      • winner가 task를 수행하는 중엔 auctioneer가 task 상황을 모니터링함.
      • task가 충분히 진행되었다고 여겨지면 auctioneer는 task가 끝날 때 까지 winner와 주기적으로 renewal/acknowledgement message를 주고받는다.

task를 순차적으로 할당시키기 때문에 greedy algorithm의 문제를 내포하고 있지만(task에 대한 auction 순서에 대해 결과가 non optimal일 수 있음) task가 확률적으로 발생하고 있는 상황에선 나름 괜찮음

 

Experimental Validation

1) Loosely coupled task

물체 추적(object-tracking), 보초(sentry-duty), 청소(cleanup), 물체 감시(monitor-object)가 가능한 이종의 로봇들이 존재할때, 무작위의 작업을 임무 공간에 던져주고 어떻게 잘 일들을 처리하는지 검증

실험 결과

 

2) Tightly coupled task

상자를 goal까지 옮겨야하는데 watcher는 goal, box등의 치 정보를 pusher들에게 제공 가능, pusher들은 둘이 협력하여 goal까지 상자를 밀어옮겨야함. 상자 크기,모양,무게 때문에 pusher하나로는 옮기는것이 어려움. 중간에 pusher 중하나가 실수해서 상자를 옮기는 루트에서 벗어나도라도 watcher에 의해서 다시 상자로 recovery함.

실험결과

---

여기서 사용된 Auction 기법은 현재까지도 임무 할당 분야에서는 main stream인 기법중 하나로 꼽히고 있습니다. 다만 이 기법은 향후 auctioneer가 따로 존재해야해서 distributed system에 적용될 때, 로봇들의 network topology에 따른 영향을 많이 받는다고 평가되고 있습니다. 그래서 요즘엔 여러 통신 topology에도 잘 적용되고, 수렴할 수 있는 것을 수학적으로 증명할 수 있는 기법들이 연구되는 중 입니다.