1. Contribution
"Coordination of multiple robots to sort multiple objects in clutter by given types and priorities (For the first time)"
- Coordination : 로봇들을 각 object들에 배정하는 것
- Sort : object들을 주어진 타입에 맞게 분류(물리적으로) 하는 것
- Priorities : 하노이탑 처럼 특정한 순서가 부여된 것
2. Problem Description
Goal : Minimize the the length of 'sequence of objects to be sorted' ( $\mathcal{O}_{\mathcal{S}}$ )
*우선 순위에 따라 바로 다음에 sorting 해야하는 object들 중 다른 object 등에 가려져 한번에 바로 sorting 할 수 없는 경우가 있음(non monotone instance)
2 Subproblems
1) Ordered sorting problem : Occlusions btw objects 로 인해 로봇이 주어진 order constraint를 따를 수 없는 경우
2) Multi-Robot Task Allocation (MRTA) problem : 어떤 로봇이 어떤 물체를 sorting 할 지 결정 - > 로봇의 수보다 물체의 수가 더 많은 상황을 가정하므로, extended time frame을 고려해야 함
3. Methods
3.1 Search based Planning
총 4가지 버전
- Uninformed search : Breadth-First and Depth-First Search
- Informed search : Best-First and A* Search
Procedure
1) $\mathcal{O}_A$ = GetAccessibleObjs($\mathcal{O}$, $\mathcal{R}$, $\mathcal{W}$)
: 전체 object들 중 바로 접근 할 수 있는 object들을 분리
* $\mathcal{O}$ : Object set, $\mathcal{R}$ : Robot set, $\mathcal{W}$ : Workspace
2) $\mathcal{O}_G$ = GetNextObjs($\mathcal{G}_1$, ..., $\mathcal{G}_K$)
: 주어진 order에 따라 바로 다음에 sorting 해야할 object들을 분리
3) $\mathcal{O}_N = \mathcal{O}_A \cap \mathcal{O}_G$
: 바로 다음에 sorting 해야할 object들 중 접근 가능한 object들만 분리
4-1) $\mathcal{O}_N$이 있으면 해당 object들을 해당하는 group으로 sorting
4-2) $\mathcal{O}_N$이 없으면 occlusion으로 인해(nonmonotone) $\mathcal{O}_G$가 모두 접근 불가능 한 상황임
-> RelocObjs를 사용해 최소한 하나의 $\mathcal{O}_G$ 안의 물체는 접근 가능해질 때까지 buffer에 relocate 반복
Heuristics for informed search
- Heuristic function $h(v)$ : 아직 sort되지 않은 object들의 개수 -> admissible (A* 에 optimal 보장)
- Order constraint로 인해 한 로봇이 depot에 transport 할 때 까지 다른 로봇이 근처에서 기다리고 있는 상황이 발생 가능
-> 로봇 여러 대가 모이면 충돌이나 deadlock이 발생 할 가능성이 높아짐
-> evaluation function $f(v)$에 penalty를 줌 : 같은 그룹에 속한 object가 연속적으로 sorting 될 때
3.2 Greedy task allocation
online greedy task allocation algorithm을 사용함
-> idle 로봇 중 접근 가능 한 로봇에게 object를 assign하는데, 이때 1대 이상의 로봇이 접근 가능하면, 가장 가까운 로봇을 assign
