1. Contribution
1. 로봇 여러대 간의 'switch' 횟수를 최대화하는 allocation method 제안 -> 로봇 여러 대가 동시에 작업을 수행 할 수 있으므로 전체 미션이 빨리 끝날 수 있음
2. 처음으로 manipulation task들이 precedence constraints를 가진 clutter 환경에서 object retrieval을 위한 multiple manipulator coordination을 수행함
2. Problem definition
Goal : coordinate 2 manipulators efficiently to retireve the target object from the confined space cluttered with other movable obstacles.
총 3가지 subproblem으로 분리함
1) Object rearrangement planning (ORP)
- Target object를 retrieve하기 위한 relocation task들과 그들의 precedence constraints를 찾음 -> aim to minimize the number of relocated objects
2) Multi-manipulator task allication (MMTA)
- Relocation task를 로봇들에세 allocate -> maximize the number of switches
3) Minimum makespan action sequencing (MMAS)
- Allocated task를 위한 Collision free motion을 찾음 -> minimize the execution time
3. Methods
3.1 Object rearrangement planning
다른 논문 ("Fast and resilient manipuation planning for target retrieval in clutter", C.Nam et al.)에서 제안된 알고리즘 사용
-> T-graph (Traversability graph) 생성 : represents the movable paths of objects in clutter
---> Node : location of an object or the end-effector
---> Edge : connected if a collision free path of the end-effector exists
The shortest path in the graph = the smallest number of objects to relocate
*두 로봇이 서로 다른 T-graph와 최단경로를 가지고 있을 수 있음
Output : Object rearrange plans for each robots
ex)
$\mathcal{O}^1_R=(o_1, o_3, o_t)$
$\mathcal{O}^2_R=(o_4, o_6, o_3, o_t)$
3.2 Multi-manipulator task allocation
2가지 버전을 제안
3.2.1 Uniform-cost search
Uniform-cost search를 수행함
1) 2개의 initial node가 각 로봇에 해당하는 Object rearrnage plan 마다 생성됨
2) Child node 생성
- Left : Object rearrnage가 로봇 1 에 의해 수행된 상태를 나타냄
- Right : Object rearrnage가 로봇 2 에 의해 수행된 상태를 나타냄
3) Goal state (target is finally relocated)에 도착하면 종료함
ex)
Solution : $\mathcal{X}_R=(r_2, r_1, r_2)$ for $\mathcal{O}^1_R=(o_1, o_3, o_t)$
* If no collision-free motion is found in $\mathcal{O}^1_R$, 새로운 path to the target이 T-graph를 업데이트 한 다음에 계산됨
-> $\mathcal{O}^2_R$ 가 찾아지면 $\mathcal{O}^2_R$ 를 선택함 (relocate 된 object의 수를 최소화 하기 위해)
The uniform-cost search는 evaluation function $f(n)=g(n)$ 에 의해 guide 됨
- $g(n)$ : the sum of penalties imposed if no switching occurs
- Frontier list에서 miminum $f(n)$이 가장 작은 것이 골라짐, cost가 같은 것이 여러 개 있으면 제일 먼저 만들어진 것이 골라짐
3.2.2 Greedy version
fast planning이 중요한 경우에 사용
- Search : 현재 node까지 쌓인 penalty들을 모두 종합해서 고려
- Greedy : 해당 turn에 switching이 일어나는지만 확인
3.3 Minumum makespan action sequencing
Parallelize 'pick' and 'place' action
-> 'standby' 를 'pick' and 'place' 사이에 추가함 -> 로봇이 모든 action을 미리 정해진 자세에서 시작 할 수 있도록 하기 위함
