of 
ich 
to 
cit 
lies 
et, 
on- 
ct” 
uts 
ion 
  
(9) 
| its 
ne. 
sive 
the 
] be 
lore 
ties 
ting 
ace. 
ping 
cess 
10ve 
ting 
this 
jS in 
peal 
995 
241 
is not so much based on the expected grasping quality but more on the spatial arrangement of the scene as a 
whole. To give two examples: If a box is located on top of a truncated square pyramid, one will first take away 
the box without spending time on trying to figure out how to grasp the underlying pyramid (in fact, even the 
grasping of the pyramid may not be possible if the surface is slippery and/or the pyramid is too flat). A second 
example is the situation where there are two separated objects (i.e., located far away from each other). Here 
one normally concentrates on the closer object without inspecting the other one. It seems that we first select 
the object and then decide how to grasp it. 
So we think that it is reasonable to divide the task of removing heaps of objects into the following two subprob- 
lems: the search for an adequate object to be removed next, and the finding of grasping opportunities for the 
selected object. The next two sections will describe these two processes in more detail. 
4.1 Object Selection 
As already mentioned, one of the factors determining the selection of an object to be removed is the spatial 
arrangement of the scene. The following two main rules guide the decision process: 
- First of all we want to limit the effect of our action (the grasping) to the smallest possible area (namely the 
object to be removed). This restriction is very closely related to the "focus of attention” paradigm. Here we 
may call it “focus of action”. In other words, we want to disturb the scene as little as possible, thus reducing 
the possibility of unexpected *movements" ,e.g., the collapse of a pile. As a consequence we will refrain from 
removing objects which are covered by others. Otherwise we would not only change the position of the object 
to be removed but also that of the objects on top of it (they will fall down). 
- Second, we want to simplify the scene as much as possible. Not necessarily with respect to the vision system, 
but more with respect to the path planing for the robot. The goal is to allow the robot to move freely between 
the disposal area where it may have placed a previous object and the new grasping position. By first removing 
objects close to the disposal area we reduce the chance of accidental collisions. This not only simplifies the 
movement towards the new object but even more importantly makes the move back with the object in the hand 
less error prone. In addition, if the grasp is bad and the object falls down on the way back to the disposal area, 
it has less chance to hit another object. 
Certainly there are exceptions to these two rules. It can happen that we cannot find grasping points for the 
selected object, or a grasping opportunity was found but the robot is not able to perform the action (e.g., the 
position is not reachable). In cases like these the object is skipped and marked as “non-graspable”. The next 
“best” object is then being considered. 
4.2 Grasping Point Determination 
After having decided on which object to grasp, we concentrate on the question of how to grasp it. For the case 
of a two-finger-gripper with parallel jaws of a certain width, the search for a grasping opportunity involves the 
determination of the following features for a pair of vertices and their small neighborhoods of triangles (which 
we choose to call patches): 
a) there exists a pair of patches the normals of which are roughly antiparallel 
b) the patches are in a relation of oppositeness 
c) the patches are not too far apart 
d) the line joining the two patches passes near the "center of gravity" of the object 
e) there is enough clearance for the approach of the gripper jaws 
f) the height of the patch pair relative to the base is above a certain threshold 
(Grippers with three round fingers or others with just a single suction cup would require the assertion of à 
partially different set of features, of course.) 
As already mentioned, we consider all possible vertex pairs as candidate point pairs for the grasp. Thus we 
have to calculate the above features for all these pairs. The sequence of the pairs is chosen arbitrarily but not 
the sequence of the calculation of the features. The reason is that if for a certain vertex pair one feature is 
absent, we do not have to calculate the remaining ones anymore, e.g., if two vertices are not in a relation of 
oppositeness, then calculating possible collision points for the gripper would be a loss of time. We therefore 
order the features according to their computational complexity and to their “selective power”. A feature which 
is simple to calculate and recognizes most of the non-suitable vertex pairs, should be placed first in the list. We 
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop "From Pixels to Sequences", Zurich, March 22-24 1995