Multi-robot systems have been widely applied in various areas such as exploration, vehicle formation control, cooperative surveillance, and target tracking. The multi-robot task allocation (MRTA) problem is one of the important research areas in multi-robot systems. The market-based task allocation is one of the most popular approach, which is based on market economy principles in which each individual tries to maximize its profit, thus leading to the redistribution of resources and the efficient production of output. The market-based algorithms use an auction protocol, i.e., auction announcement, bid valuation and submission, winner determination, award accept/reject, and auction closing, in task allocation. In the auction announcement stage, any agent that desires to allocate a task becomes an auctioneer and broadcasts an auction call for a task. The others that are interested in the auctioned task become bidders. They submit their bids or costs to the auctioneer. Then the auctioneer selects a winner in the winner determination stage and awards the task
to the winner. The winner can either accept or reject the task in the award accept/reject stage. If it accepts the task, the auction is closed, and if not, the auctioneer repeats the auction process until the task is allocated. These approaches make no assumption about the heterogeneity or homogeneity of robots since robots compute their bids based on their own local information, and the task allocation is solely determined by their bids. Although the market-based approach is efficient in terms of communication load and computation, it has several disadvantages in terms of balanced task distribution, limited robot resources, and limited communication range.
This thesis is motivated by the balanced market-based multi-robot task allocation problem in a long-term operation scenario with limited robot resources and communication range. In the long-term operation scenario, robots have different capabilities and resource levels as well as limited communication ranges, and they must provide requested services or execute tasks as quickly as possible in a balanced manner. This thesis proposes three methods, a competency and workload balancing framework, a resource-aware cost generation algorithm, and an ad-hoc network-based task allocation algorithm, for efficient decentralized market-based task allocation. The competency and workload balancing framework allows the auctioneer to evaluate the properties of the bidders, and to adjust the relative importance between them in response to the characteristics of tasks, preference and environmental changes. The framework adopts the concept of subsidy for workload balancing in multi-robot systems. The resource-aware cost generation algorithm models multiple resources of a robot as a multivariate normal distribution and utilizes them to estimate the cost of the path consisting of the refill stations that the robot should visit before the task to avoid resource depletion while performing the task. Since the algorithm estimates the residual resources after completing the task, it is capable of minimizing extra resource consumption and time delay due to detour of the
robots to refill stations for refilling their resources during task execution. The ad-hoc network based task allocation algorithm constructs the minimal spanning tree and the robots in the network exchange information about the best candidate robot that has the lowest cost for the task. This does not require perfect communication links among the robots nor infinite bandwidth. It is also capable of finding a better solution than the auction algorithms with single-hop communication since more robots are allowed to participate in the task allocation process by using the multi-hop communication network.
다개체 로봇 시스템은 탐사, 대형 제어, 구조 작업 및 목표물 추적 등에 널리 활용되고 있다. 이러한 다개체 로봇 시스템에서 임무 할당 문제는 가장 중요한 연구 주제 중 하나이다.
시장 기반 임무 할당법은 가장 널리 알려진 다개체 로봇 임무 할당 기법이며, 이는 각 로봇이 자신의 이익을 최대화 하려는 목적을 가지게 함으로써 전체적인 임무 수행의 비용을 최소화 하도록 하는 방법이다. 시장 기반 방식은 경매 프로토콜을 사용하며, 경매 프로토콜은 경매 알림, 입찰가 제출, 승자 선택 및 임무 할당으로 구성된다. 경매 알림은 임무를 할당하고자 하는 로봇이 경매자가 되어 해당 임무를 다른 로봇에게 통신으로 브로드케스팅하여 알리는 과정이다. 입찰가 제출은 수신한 임무에 대해 수행 능력이 있는 로봇들이 입찰자가 되어 자신이 해당 임무를 수행하는 데에 필요한 비용을 계산하여 경매자에게 통신으로 자신의 입찰가를 전송한다. 승자 선택 및 임무 할당에서는 입찰자들로부터 입찰가를 수신한 경매자는 가장 비용이 적게 드는 입찰자를 승자로 선택하고 임무를 할당하게 된다. 비록 이러한 경매 기법은 통신량이나 계산량 면에서 중앙 집중형 임무 할당에 비해 유리하지만 균형적인 임무 분배, 제한된 로봇 자원량 및 제한된 통신 범위를 가진 환경에선 불리한 점들이 존재한다.
본 학위논문은 다개체 로봇 시스템에서의 효율적이고 분산적인 임무 할당법을 다룬다. 다개체 로봇 시스템에서 임무 할당법은 다수의 임무들을 최소의 비용으로 수행할 수 있는 다수의 로봇들에게 분배하는 최적화 문제로 변환될 수 있다. 가장 널리 사용되는 임무 할당법에는 경매 기반 임무 할당법이 있다. 이 방법에서는 기존의 중앙 집중식 임무 할당법과는 달리 임무를 할당하고자 하는 임의의 로봇이 경매자가 되고 해당 임무를 할당받고자 하는 다른 임의의 로봇들이 입찰자가 되어 가장 입찰가가 낮은 로봇에게 임무가 할당된다. 이러한 접근법은 분산형 임무 할당이 가능하므로 중앙 집중형 임무 할당법에서 발생하는 확장성에 따른 통신량, 계산량 등의 지수적인 증가 문제가 발생하지 않으며, 단일 지점 고장 문제를
방지할 수 있다. 하지만 경매 기반 기법은 로봇간의 경쟁을 기반으로 하므로 균형적인 임무 할당을 보장하지 못하며, 임무 수행에 대한 비용만을 고려하여 임무를 할당하므로 비용 계산법이 비효율적이거나 핵심적인 요소들을 비용 계산에 반영하지 않을 경우 비효율적인 임무 할당이 이루어지게 된다. 또한 통신범위가 제한적일 경우 이웃한 로봇간에만 경매가 가능하다는 단점이 있다. 본 학위논문에서는 이와 같은 경매 기반 임무 할당법의 단점을 보완하여 제한된 자원량과 통신범위를 가진 다수의 로봇들이 효율적으로 장기적인 임무 수행이 가능하게 하는 임무 할당법을 제안한다. 본 학위논문은 크게 균형적인 임무 분배법, 자원을 고려한 비용 생성법, 임시 통신 네트워크 형성을 기반으로 한 분산형 임무 할당법으로 구성된다. 균형적인 임무 분배법에서는 서로 다른 능력을 가지는 로봇들과 서로 다른 능력을 필요로 하는 임무들을 효율적으로 서술하는 방법을 제안하며, 보조금의 개념을 도입한 균형적인 임무 할당 구조를 제시한다. 제안한 방법은 다수의 로봇들이 다양한 종류의 물체들을 수집,
분류 및 정리하는 청소 미션 시뮬레이션에 도입하여 그 효율성을 검증하였다. 자원을 고려한 비용 생성법에서는 로봇이 임무 수행 중에 소비하는 다수의 자원들을 경매된 임무에 대한 비용 생성에 고려하는 알고리즘을 제안한다. 본 방법은 다개체 로봇을 이용한 수렵 채집 시뮬레이션에 적용하여 그 효율성을 검증하였다. 임시 통신 네트워크 형성을 기반으로 한 분산형 임무 할당법은 제한된 통신범위를 가진 로봇들 간에 임시 통신 네트워크를 구성하는 방법과 해당 네트워크를 이용한 다중 도약 통신법으로 임무를 할당하는 방법을 제안한다. 본 방법은 태양광 발전소 청소 시뮬레이션에 적용하여 그 효율성을 입증하였다.
