Multi-agent multi-task decentralized allocation is a well-studied field with many proven algorithms. In the real world, many tasks have complicated coupled relationships that affect the feasibility of some algorithms. In this thesis, we consider an agent-task allocation problem where agents greedily assign themselves to a set of tasks with spatial and/or temporal constraints. Due to the coupled nature of the tasks, cooperation between the agents is necessary. We formulate the coupled-constraint task allocation problem as an exact potential game and show that it can converge to a Nash equilibrium.
다수 개체의 분산형 다중 임무 할당 문제는 여러 입증된 알고리즘통해 많은 연구가 이루어진 분야이다. 실제적으로는 여러 임무가 상호간에 복합적으로 엮여 몇 알고리즘의 실행가능성에 영향을 미친다. 본 논문에서는 개체들이 공간적 및(또는) 시간적 제약조건을 갖는 임무 집합에 스스로를 탐욕적으로 할당하는 개체-임무 할당 문제를 다룬다. 임무가 상호간에 엮이는 특성 때문에 개체간의 협업이 필요하다. 이를 위해 본 논문에서는 상호간의 제약조건하의 임무 할당 문제를 엄밀한 포텐셜 게임으로 문제정의하고 본 문제가 내쉬 평형점으로 수렴함을 보인다.
