High dimensional object rearrangement for a robot manipulation in highly dense configurations [ISR 2022]
1. Contribution
1. Propose an object rearrangement algorithm that minimizes object movement and grasp targets
2. The algorithm provides safety by considering stackable relationships btw objects and show completeness
2. Problem description
goal : Minimize the number of actions that rearrage the objects blocking a target object
-> Attempt to find a sequence of the obstacles by using a tree search and concept of 'Tower of Hanoi' (ToH)
3. Algorithm description
3.1 Finding of obstacles for rearrangement
Tree search를 수행함
- Node : object configuration -> gives scene information
- AccesibilityCheck를 수행하여, target object를 잡을 수 없다는 것이 확인되면, accesible한 물체 중 하나를 제거하는 것으로 child node를 생성 -> target object가 접근 가능해지면 종료 -> 이 노드를 goal node라고 부름
- Heurisitic cost c : determines the order of child nodes when generating them (cost 작은 node 부터 생성)
*Cost : "Efficient Obstacle Rearrangement for Object Manipulation Tasks in Cluttered Environments, Jinhwi Lee et al." 에 자세히 정의되어 있음
Goal : find an obstacle sequence $O_s$ with the minimum length $\left| O_s \right|$
* Previous obstacle sequence $O_{s0}$도 input으로 사용됨
-> 만약 motion planning이 fail 할 경우 다음 goal node는 $O_{s0}$랑 다른 것으로 결정함
3.2 Task planning for rearrangement
- Concept of ToH 를 차용하여 object 위에 다른 object을 올릴 수 있게 함
(단, object의 크기는 동일 + 1개만 올릴 수 있음 -> stability를 위함)
- Symbolic domain construction : task planning을 위해 Planning Domain Definition Language (PDDL 2.1) 을 사용함
-> 앞에서 만든 obstacle sequence $O_{s0}$ 를 이용해 task plan $P$ 를 만들어 냄 (contains series of action)
3.3 Task and Motion planning
Result of task planning : robot kinematic을 고려하여 verified 되어야 함 -> motion planning
-> Motion planning이 실패하면 새로운 obstacle 및 action sequence로 motion planning을 수행함
-SequenceSearch : finding the obstacle sequence $O_s$
-EmptySlotGeneration : generate the empty slot for rearranging obstacles
-TaskPlanning : generate action sequence $P$
- MotionPlanning : verify $P$