<재단 제25기 해외유학장학생 University of Illinois at Urbana-Champaign. 2009년 졸업(Computer Science), 현 삼성전자 DMC연구소 책임연구원>

이 논문은 완전히 분산되고 (fully-distributed) 많은 수의 (large-scale) 이기적인 (self-interested) 로봇들로 이루어진 다중 로봇 시스템으로 (multi-robot system) 지속적인 변화가 있고 실시간 제약을 (real-time constraints) 가진 환경 내에서 여러 로봇 에이전트들의 동기화된 협력이 (synchronized coordination) 필요한 복잡한 작업들을 로봇들에게 분배하는 시장경제 기반의 협력 작업 배분 메커니즘(market-based coordinated task allocation mechanism)과 에이전트간의 활동을 검증하여 각 로봇 에이전트가 규칙을 위배하지 않는 행동을 하는지 확인하는 감사 메커니즘(auditing mechanism)을 제안한다. 이 논문에서 논의되는 협력 작업 배분 메커니즘에는 순경매 (forward auction), 역경매 (reverse auction), 양방향경매 (forward/reverse auction), 봉인경매 (sealed-bid auction) 들과 함께 효용함수(utility function)로 표현되는 여러가지 입찰 전략들이 (bidding strategy) 포함되어 있다. 또한, 변화하는 환경에 실시간으로 적응하기 위해 이미 경매로 할당된 작업을 서로 교환하여 재할당 하는 1대1 물물교환방식도 (1-to-1 task exchange) 협력 작업 배분 메커니즘에 포함되어 실험된다. 로봇 에이전트들이 이기적이기 때문에, 각각의 에이전트는 더 적은 비용으로 더 많은 이득을 취하기 위하려 무임승차(free-riding)나 위반행위(cheating)를 할 가능성이 있다. 무임승차와 위반행위는 정직하게 공헌하는 에이전트가 적절한 보상이나 서비스를 받지 못하게 하여서 각 에이전트가 더더욱 무임승차와 위반행위에 이끌리도록 하여 시스템의 전반적인 성능을 저해할 수 있다. 전체 시스템에 대한 공헌을 촉진하고 공헌의 정도가 적절히 측정됨을 확인하기 위해서 앞에서 언급한 협력 작업 배분 메커니즘과 결합되어 사용될 수 있는 감사 메커니즘을 크레딧 시스템(credit system)과 함께 제시한다.

협력 작업 배분 메커니즘의 실험을 위하려 실제 로봇을 이용한 실험과 가상의 로봇을 사용하는 시뮬레이션을 모두 수행하였다. 실험결과는 본 논문에서 제안된 메커니즘이 규모가 큰 시스템에서도 동작하며 (scalability), 실제 로봇을 사용할 경우 고장 방지 (fault-tolerance) 능력도 있음을 보여준다. 제안된 메커니즘들은 여러 성능 평가 기준을 (performance metrics) 가지고 대조군으로 쓰인 메커니즘들과 비교되었으며 그 결과는 제안된 접근방법에 의해 성능향상이 나타날 수 있음을 보여준다. 데드락 (deadlock), 반복입찰 (pingpong-bidding), 반복교환 (pingpong-swapping), 그리고 그 외의 여러 문제들도 분석되었다. 감사 메커니즘의 작동은 수치해석 (mathematical analysis) 방법과 시뮬레이션 (software simulation)을 이용하여 (수치해석은 전체 로봇 집단을 단위로 계산하였고, 시뮬레이션은 개별 로봇의 행동을 계산하였다.) 분석하였다. 수치해석과 시뮬레이션의 결과는 모두 감사 메커니즘이 여러 조건하에서 위반행위를 지나친 통신량을 사용하지 않으면서 높은 확률로 찾아낼 수 있다는 것을 보여준다. 또한, 각각의 개체가 자기 주변의 변하는 환경에 따라 통신량과 위반행위 적발률을 조절할 수 있도록 감사 메커니즘에 적응 메커니즘 (adaptive mechanism)을 통합하는 방법도 제안하였다. 개체의 행동에 대한 진화적 게임이론 (evolutionary game theory)을 이용한 분석과 시뮬레이션은 이 감사 메커니즘이 무임승차와 위반행위를 해당 시스템의 인기에 해가 되지 않으면서도 효과적으로 저지할 수 있음을 보여준다. 이 분석에서는 정직하게 시스템에 공헌하는 전략이 진화적으로 안정되어있음을 (evolutionarily stable) 보여 주었으며, 시뮬레이션에서는 그러한 전략을 채택한 개체가 소수였다 하더라도 결국은 지배적인 전략이 됨을 보여주었다.