当前位置:首页 >> >>

Optimal Probing Strategies


Optimal Probing Strategies

John Canny jfc@cs.berkeley.edu

Eric Paulos paulos@cs.berkeley.edu

Department of Electrical Engineering and Computer Sciences University of California, Berkeley

August 19, 2001

Abstract
Probing is a common operation employed to reduce the position uncertainty of objects. This paper demonstrates a technique for constructing provably near optimal probing strategies for precisely localizing polygonal parts. This problem is shown to be dual to the well studied grasping problem of computing optimal ?nger placements as de?ned by Mishra et al. [Mishra et al., 1987] and others [Ferrari and Canny, 1992, Mirtich and Canny, 1994]. A useful quality metric of any given probing strategy can easily be computed from simple geometric constructions in the displacement space of the polygon. The approach will always ?nd a minimal set of probes that is guaranteed to be near optimal for constraining the position of the polygon. The size of the resulting set of probes is within O 1 of the optimal number of probes and can be computed in

On log2 n time whereas the exact optimal solution is in NP-hard [Das and Joseph, 1990].
The result of this work is a probing strategy useful in practice for re?ning part poses.

1

Introduction

In industrial manufacturing and automated assembly, accuracy is extremely important. Attaining and maintaining high precision can increase the cost of ?xturing and feeding several fold [Nevins and Whitney, 1978]. The meaning of high verses low precision depends on the application, but for typical mechanical assembly, low precision tooling might provide accuracies in the tens of mils, while high precision would be around one mil or less (One mil =

10,3 inch = 25:4 microns). This paper studies the pose re?ne-

ment problem. In pose re?nement, sensing is used as an inexpensive route to high precision part pose, assuming the pose is already known at low precision. Most research to

1

date in computer vision and RISC [Canny and Goldberg, 1994] sensing addresses the pose acquisition problem, where pose is determined with no knowledge of initial pose. The result of pose re?nement is a high-precision estimate, but it differs from the problem of high-precision pose acquisition. Since initial pose is approximately known in pose re?nement, it can be used to make judicious choices about sensor placement. The same accuracy can be achieved with fewer or less expensive sensors for pose re?nement as compared to pose acquisition, which must deal with all possible poses. Initial motivation for tackling this problem arose after visits to several state-of-theart manufacturing companies, especially PTI (Productivity Technologies Inc.), Adept, and Hewlett Packard Labs. In typical industrial workcells, it was pose re?nement rather than pose estimation that was the dominant sensing task. There are two reasons for this: 1. Feeder economics: Vibratory feeders are an inexpensive way to provide many part types in known (albeit low precision) pose. Small parts can also be fed on tape, which is more expensive (a couple of cents per part) but still costs far less than a high-precision pallet. So the initial and ongoing costs of achieving lowprecision pose without sensing are small. 2. Multi-step manufacturing: In typical manufacturing, there are not one but several sequential stages, including assembly stages, testing and packaging. A single step might mate two parts whose poses are known at high precision. But the assembly step itself introduces a small amount of uncertainty, and it is expensive to transport the partial assembly at high precision to the next assembly stage. A more economical solution is to use pose re?nement at the next stage. So while there might be one pose acquisition step per part to get approximate initial pose,

2

Path

Sensor Object

z y x

Light Beam

Figure 1: A typical simple re?ective sensor used for probing

there will be several pose re?nement steps for that part that start with the low precision output from the previous step and feeder, and increase the precision as needed for the next step. So the arguments for pose re?nement are (1) that it replaces the most expensive (high precision) ?xturing and feeding steps and (2) it replaces the most frequent ?xturing and feeding steps in multi-step assembly. This paper focuses primarily on the use of simple light-beam sensors that act as line probes in 3D, or point probes in the objects projection onto a horizontal surface. A point light source and receiver de?ne a line in space that is broken and unbroken by an object as it moves relative to the beam (see Figure 1). The positions of the object when the beam breaks give position readings, and three or more of these determine pose. Those readings are subject to error, and the pose estimate accuracy is limited by those errors and the sensor placements. This research provides algorithms for choosing the probe placements to achieve near-optimal accuracy with a ?xed number of probes, or

3

to ?nd a near-minimal number of probes to achieve a speci?ed accuracy. An important assumption of this work is that individual probing operations do not disturb or alter the part’s pose in any way. Common industrial optical sensors easily satisfy this constrain by being contactless. The problem is best summarized with the following problem statement. Problem Statement: Given: A polygonal part geometry and an initial pose estimate of

Oi =

Oix; Oiy ; Oi  within = kO , Oikm of the exact actual pose of the object, O . Here k  km is de?ned to be the m-norm.
Assumption: A probing operation leaves a part’s pose unchanged. Solve: Find the optimal set of point probes de?ned as the minimal number of probes and their placement necessary to reduce the uncertainty in the position of an object to better than some acceptable level. The probes are de?ned by a set of ?xed points and vectors denoting the direction of travel for each probe. A probe returns a real value. That value is the time or position that a simple binary sensor changes state. The error associated with this value is at most , where , based upon the presence or

absence of an object’s edge at a particular point along the path of the probe. With enough time, one could simply perform a large number of probes as shown in Figure 2. However, in real industrial robotic assembly workcell design, throughput is a heavily weighted criterion. Therefore, the goal is to produce the best possible

4

Figure 2: A typical initial probe placement along the edges of an object

probing strategies that conform to the imposed constraints. The probing strategies that result can be used by any point probe of the object’s two-dimensional projection. There are natural generalizations to higher dimensions, although they are not as ef?cient. A typical probe, shown in Figure 1, consists of a simple re?ective light beam sensor that can easily detect the presence or absence of an object. The algorithm also allows for construction of specialized optimal probing strategies such as those for a scanning array of probes as shown in Figure 3. These near-optimal probings are obtained with a small number of actual probes by maximizing the utility of each sensor probe placed on the object. This in turn makes the problem tractable for a real robot in a high throughput automation system. These strategies are within a constant factor of the optimal probing strategy and can be solved in

On log2 n time whereas the exact optimal solution is in NP-

hard [Das and Joseph, 1990].

5

Scanning Sensor Object Motion Measured Probes

Figure 3: Example of a ?xed array scanning beam sensor

2

Previous and Related Work

We ?rst discuss related work in part probing. Our main result is to show that probing is dual to the grasping problem, and to give an optimal probing algorithm based on set coverings. Therefore we then discuss related work on grasping and on set covering algorithms.

2.1

Work in Probing

The importance of probing in terms of localizing and identifying objects with probes has been explored by several individuals. Cole and Yap [Cole and Yap, 1987] and Bernstein [Bernstein, 1986] developed algorithms for choosing probes to obtain the geometry of an unknown two-dimensional convex object. A generalization of this strategy for higher dimensions is presented by Dobkin et al. [Dobkin et al., 1986] while a nonconvex version was developed by Boissonnat and Yvinec [Boissonnat and Yvinec, 1992]. Also, Lindenbaum and Bruckstein [Lindenbaum and Bruckstein, 1990] describe simi-

6

lar probing strategies for a geometric probe composed of two line probes rotating about a common axis point. Development of ef?cient algorithms for scanning objects with probes for the purpose of identi?cation and localization have been explored by Wallack et al. [Wallack and Canny, 1994, Wallack et al., 1993]. Likewise, point probing strategies have been developed for insertion operations by Paulos and Canny [Paulos and Canny, 1994]. Jia and Erdmann [Jia and Erdmann, 1995] demonstrate an elegant technique for choosing placements of simple binary sensors to discriminate objects in the plane. In fact they also employ recent work on hitting sets and set coverings in solving their problem. The work in this paper differs mainly in the type of problem that is solved. Jia and Erdmann choose ?xed probes to discriminate individual object poses from a large set of possible poses. The problem tackled in this paper is how to best choose moving probes to re?ne the pose of a known object.

2.2

Work in Grasping

The need for good grasp planning algorithms for arbitrary shapes has always been important for robotics and industrial automation. The problem of optimal ?nger placement has been addressed by Mishra et al. [Mishra et al., 1987] who de?ne easily computable quality metrics for grasps. Markenscoff and Papadimitriou [Markenscoff and Papadimitriou, 1989] chose to optimize the grasp with respect to minimizing the forces needed to balance the object’s weight through friction. Ponce and Faverjon [Ponce and Faverjon, 1991] ?x the number of ?ngers and solve a system of linear constraints in the positions of the ?ngers to optimally position them along the polygonal edges. A similar technique for

7

three-dimensional polyhedral objects was developed by Ponce et al. [Faverjon and Ponce, 1991]. Goldberg [Goldberg, 1993] also details a method for choosing grasps with a parallel jaw gripper when the initial pose of the object is unknown. Other optimizing grasps techniques based on simple geometric constructions have been developed by Brost [Brost, 1988] and later Mirtich, Canny, and Ferrari [Ferrari and Canny, 1992, Mirtich and Canny, 1994].

2.3

Work in Set Coverings

This paper will prove that ?nding the minimal set of probes is equivalent to solving the convex set covering problem. This problem is discussed by Clarkson [Clarkson, 1993] who describes a

Ocn logO1 n time randomized algorithm for ?nding covering sets of cardinality within O log c of the optimal set covering c.
More recent results by Br¨ nniman and Goodrich [Br¨ nnimann and Goodrich, 1994] o o on the dual problem of ?nding minimal hitting sets improves on these bounds. They demonstrate an

On log2 n algorithm that ?nds a hitting set of size O1 from the

optimal set size. They employ work by Matou?ek [Matou?ek, 1990] using -nets. s s

3

RISC Robotics

RISC robotics [Canny and Goldberg, 1994] (Reduced Intricacy in Sensing and Control) is an attempt to fuse automation and robotics technologies. The RISC acronym, borrowed from computer architecture, suggests the parallels between the two technologies. RISC robotics performs complex manufacturing operations by composing simple elements. A synonymous phrase to describe this theme is simply minimalist robotics.

8

RISC robotics can be applied to many areas of manufacturing. For example, RISC grasping uses simple two and three ?ngered grippers with traditional ?xturing devices such as clamps and vices [Wallack and Canny, 1994]. RISC sensing employs simple but precise sensor elements that can be combined to form complete systems for localizing and recognizing arbitrary objects from a library [Wallack et al., 1993, Wallack and Canny, 1993]. RISC robotics systems inherently consist of few degrees of freedom and lowdimensional sensor spaces. This results in algorithms for manipulation and sensing that are simple, highly accurate, and very fast.

4

De?ning Optimality

When probing an object the objective is to choose point probes that allow the minimum variation of the object pose. Point probes inherently contain some known error so it is not enough to take k independent measurements to constrain k degrees of freedom. The placement of the probes effects the worst case object displacement. Therefore, it is the relationship between the object displacements and the corresponding probe displacements that are of interest. The goal is to ?nd a set of probe placements that minimizes the potential worst case object displacement.

4.1

Object Pose De?nition

We de?ne O as the actual pose of the object in two-dimensions as

O = Ox; Oy ; O 

9

Our aim in this work is not in locating an object, but in re?ning the position of a known object whose pose is known to some reasonable degree of accuracy. Our approach relies on this initial coarse accuracy pose information. We de?ne the assumed initial pose as

Oi and quantify a bound on the worse case displacement of the assumed pose from the
actual pose as

kOi , Okm 
where k  km is de?ned to be the m-norm. At this point, we run into the usual problem of de?ning a metric on a space with distance and angular coordinates. There may be application-speci?c ways to weight the angular component, but a good default is to weight the angular component by the object’s radius (i.e. the largest distance from any point in the object to its coordinate origin). With this choice, the metric bounds the maximum distance between any two corresponding points on the object at O and Oi . A typical value for would be tens of mils. Finally, while we are considering an m-norm for generality, the 2-norm would seem to be the most natural choice. We will be using point probes to re?ne the position of the object. Therefore, for a given set of probe measurements there will also be a set of valid poses for the object

 consistent with those sensor readings. We denote this object pose as O and de?ne it to
be an object pose chosen by an adversary consistent with some sensor readings given the object is at O . We de?ne the difference between the actual object position and the adversary’s choice as o.

 o=O,O
will always

Recall that we are attempting to re?ne the position of the object so that

10

be at least an order of magnitude larger than kok.

kok
In terms of linear displacement the initial pose uncertainty, , is typically on the order of tens of mils while the uncertainty under probing is on the order of a mil or less. To quickly summarize we have O as the actual pose of the object, Oi as our initial

 sensor readings. That is, we cannot determine from the sensors if the object is at O or  not. We will clarify later exactly how O is de?ned.
Probe Placement

 pose estimate, and O as a pose that an adversary can choose that does not violate our

4.2

We construct probes along the perimeter of the object and denote them as

p = px; py 

l = lx; ly 

where p is the point where the probe touches the object when the object is at Oi , and l is the direction of motion of the probe. We must guarantee that no matter where the object actually is, this probe always contacts the same edge. Assuming that the object radius was used to weight the angular component of the pose metric, this can be accomplished in a simple way: construct a strip about the probe path l whose boundaries are parallel to l, and at distance from it; This strip represents the possible relative positions of the probe for various actual object poses O . If the edge we are probing crosses the entire strip, it will always be probed correctly. If the edge crosses only part of the strip, then there is a possible O such that this probe misses the edge completely. From now on, we assume that all probes are chosen so that their strips touch only the edge of interest.

11

c) a)

b)

probe with error ball region of allowable motion

Figure 4: Relationship of placement of probes (solid points) with error balls (dashed circles) along an edge (solid line) and the resulting displacement region (shaded). (a) Probes at endpoints of edge. (b) Probes moved inward from edge resulting in larger region of allowable motion. (c) Probes coincident at center of edge, allowing maximum displacement region.

The initial probe placement consists of placing a pair of probes on each edge. Each probe is placed as near as possible to an endpoint of the edge, but subject to the strip constraint above. As we shall see later, there is no loss of generality with this step as the probes at the edge endpoints always provide the most constraining measurements. Our algorithm will choose a subset of these initial probes as the near optimal probe set. Our initial choice is based on the fact that we receive the most accurate pose information by probing near the vertices of an object. Observe that probes near the vertices give rise to large sensor displacements as a result of small rotational perturbations, while position information is the same anywhere on the edge. Figure 4 demonstrates how moving a set of probes with a given error out towards the vertices of an edge shrinks the size of of allowable displacements for that edge.

12

This set of probes is guaranteed to contain the optimal probe placement. Any edgeinterior probes would give only redundant information in the worst case, and our probe choice is based on a worst-case analysis. A typical initial probe placement example is shown in Figure 2. The remaining problem is to determine a subset of these probes that still provide a substantial gain in object pose accuracy. 4.3 Probing Function

We place a coordinate system at the center of mass (COM) of the object. In addition we de?ne the rotational displacement of the object to be about this COM axis. In Figure 5 we depict the construction of the corresponding probe displacement for a given object displacement. This will de?ne the probing function. In this ?gure to the edge being probed, displacement O from the origin. Recall that is very small allowing us to take small angle approximations and write

n is a unit normal

p is the initial probe location and p0 is its location after the

p0k  pk + Ox; Oy  + p?O k
where p?

= x; y? = ,y; x and k denotes the kth probe. It follows that the change pk = p0k , pk = Ox; Oy  + p?O k

in probe position is

The probe actually only gives us useful position information normal to the edge being probed. We could freely displace the object along the edge without changing that probe reading. Therefore, the change in probe position along the edge normal nk can be

13

n

p p’



(O x ,O y )
Figure 5: Original probe p and resulting probe p0 after an object displacement (Ox ; Oy ; O )

. written as nk

 pk .

Observe that even if we approach an edge at an angle, when

we detect the edge we can only claim that some point of the edge must intersect the detected point. This is equivalent to the information we receive if we approach normal to the edge. Therefore, the two probe approach techniques are equivalent and thus the choice of edge approach is independent and left as a ?nal implementation detail. It does affect the -strip described earlier, and the amount of clearance from the edge endpoint needed to ensure the correct edge is detected.

: R 3 ! R k to be a real valued function which maps object positions into ideal probe outputs of the form P1 ; P2 ; : : : ; Pk .
We are now ready to de?ne the probing function P We de?ne each element to be

Pk O = pk  nk
 probes as P

(1)

Our probes will have a sensor error , typically a mil or so. We de?ne the measured

2 R k . Given a sensor error of

, we observe that the measured probe values

14

 P must be consistent with the ideal probes given object pose O.  kP , P Ok1 
(2)

 Similarly, any possible object position O that the adversary chooses must have all measured probes within of the given measurements.

  kP O , P k1 
Using the triangle inequality on these last two expressions, we ?nd that the satisfy

(3)

 O and O
(4)

 kP O , P Ok1  2

  and observe that for any O satisfying this inequality that there a is P satisfying Equations 2 and 3. Thus the combined bound is tight. We will call the set of object displace-

 ments O that satisfy this inequality K.

O and the possible in   terpreted object position for some sensor reading is O where O is any O satisfying
Recall that the actual position of the object is de?ned as Equation 4. We want to constrain the distance between the interpreted object position and the actual object position to be as small as possible. This in turn minimizes the worst case distance between the actual and measured poses, which is the ultimate goal of pose re?nement. We represent the former quantity as

 kO , Okm

(5)

We employ an adversarial argument and note that if an adversary is allowed to move

 the object to some valid O consistent with the sensor readings it will always choose the

15

 O such that the quantity in

5 is maximized. We express this as

 O2K

 sup kO , Okm

(6)

However, we are allowed to choose the set of probes P . Furthermore, we desire a set of probes that will output drastically different values for different nearby object poses, thus allowing us to identify different poses easily. Essentially we would like to eliminate the possibilities of obtaining identical or near-identical sensor readings for an object in two different poses. We can write this as

 max kP O , P Ok1 P
or since P O  is linear in O we can make the substitution to

(7)

 max kP O , Ok1 P
or rewriting

(8)

(9)  kP O , Ok1   Expression 6 scales linearly with O , O, while 9 scales as the reciprocal of O , O. It is natural to combine them as a product which is then independent of the magnitude of

min P

1

 O , O:

 kO , Okm min max   P O2K kP O , Ok1  kO , Okm QP  = min max kP O , Ok  1  P O2K



(10)

From this we can arrive at our ?nal optimality criterion and probe quality measurement

Q.



(11)

16

5

Displacement Space

Working in displacement space, we observe that there is a simple geometric construction of the optimality criterion as given in Equation 11. Displacement space, denoted
D

2 R 3 , is the space of all displacements in x; y;  of the object O to be probed. Each

probe sensor that we introduce imposes constraints on the allowable set of displacements of the object without violating the probe value. Equation 4 from the previous section de?nes a pair of halfspaces in displacement space D for each probe pk .

 kPk O , Pk Ok1  kPk O , Ok1 kPk ok1 knxox + ny oy + p?  no k1

   

2 2 2 2

 where o = O , O . These two halfspace can be written as

nxox + ny oy + p?  no , 2  0 nxox + ny oy + p?  no + 2  0
sents a convex polytope in D . We name this polytope S with the de?nition

(12) (13)

The intersection of all 2k halfspaces constructed from k probes by de?nition repre-

S=

h2HP  h

where HP  is the family of 2k halfspaces de?ned by the set of k probes P . In displacement space this polytope S will have furthest outlying point which will occur in the non-degenerate case at a vertex of S . This furthest outlying point represents

17

the largest object displacement from the assumed pose that still satis?es the given probe measurements. More formally we de?ne this point as

,S  = sup kqkm
q2S
The distance to

,S  is exactly the optimality criteria as de?ned in Equation 11.

To

see this, assume that the denominator of Equation 11 has been ?xed to some constant

 . Because the denominator scales with O , O, we can always do this. The constraint  kP O , P Ok1 =  de?nes a polytope in displacement space (choice of O), and if we set  = 2 , it de?nes exactly the polytope S . With its denominator constrained,  maximizing 11 means maximizing its numerator kO , Ok, which is exactly what is
speci?ed by ,S . We assume that

P

is ?xed, so there is only optimization by the adversary over q .

Recall that an adversary can choose the actual sensor readings

 displacement ,S  is a valid interpretation of P . Hence, this is the largest displacement
of the object undetectable by the given probing strategy. For illustrative purposes we work through a simple example without rotation. In Figure 6 we show three probes on a triangle, an admittedly simple case, but enough to demonstrate our method. Notice that each probe in real space gives rise to a pair of parallel halfspaces in displacement space, D . If we remove probe

 P such that the object

p2 , the area of

polygon S in displacement space increases which represents the additional translational freedom that the object can undergo and still remain consistent with the remaining two sensor readings. Therefore, the added sensor p2 is a useful addition since it decreases the area of S and reduces the distance to ,S . We are interested in probing strategies P 0 that have approximately the same quality

18

Probe Space

Displacement Space p+
0

Γ p
0
Error Bars Measured Probe

p0

S
p
1

p+
1

p1

Γ p
0

p+
0

p0

p+
2

S
p
1

p2

p

p+
1

2

p1

Figure 6: Simple example of probe space and displacement space without considering rotation. Note the removal of one probe and the resulting change of the polygon S in the displacement space.

metric P . Remember that every probe we remove from P removes a pair of halfspace in D . This in turn changes the shape of S but not always the point ,S  which de?nes the optimality criteria. Therefore, we would like to ?nd other optimal probes with fewer probes. In particular, we would like to ?nd

P P
0

min jP 0j : QP 0  QP 

where j  j is simply the cardinality of the set P 0 . We de?ne S 0 to be the polytope de?ned by the intersection of the halfspaces de?ned

19

by the probes P 0 . Observe that

S0 S
which implies that when we remove a probe, hence two halfspaces, we expect the furthest outlier to remain where it is or increase in distance from the origin giving

j,S 0j  j,S j
Rather than removing half-planes in an ad hoc manner such that

QS 0 remains

essentially unchanged, we will dualize and solve for a minimal convex set covering for the corresponding points in the dual. These minimal set of points will be exactly dual to the minimal set of halfspaces in displacement space by de?nition of the minimal convex set cover problem. These resulting halfspaces in D correspond to minimal set of probes, as desired. We discuss this dualization in the next section. Observe that the production of any such probing strategy is independent of the error,

2 . This is true because we are interested in optimizing the ratio shown in Equation 11. One can also note that topology of the polytope S of the solution space is independent
of which only serves as a scaling factor. That is, when we double we get the same polytope at twice the linear size (eight times the volume). Therefore, without loss of generality we set to one for the duration of the paper.

6

Displacement Space Dual

A strong relationship to grasping is shown in this section. We show that ?nding the optimal k probe placements is equivalent to ?nding the optimal push-pull grasp for a

20

set of k ?ngers. A push-pull grasp is de?ned as a grasp that employs ?ngers capable of exerting a pushing or pulling force at the contact. We de?ne D D to be the dual of D . We de?ne the dual exactly in Table 1. In this mapping we show how points in D map to planes in D D and similarly for planes in
D to points in D D . We note that by de?nition the dual of D D is D , hence the duality

operation is symmetric.
D DD

p : px; py ; p  S = polytope

$ pD : pxx + py y + p = 1 $ S D = ff D : f
Table 1: Duality Mappings

f : ax + by + c = 1 $ f D : a; b; c
IntS  = ;g

Observe that a polytope S de?ned as the intersection of a set of halfspaces hk becomes the polytope S D . We de?ne Boundhk  to be the plane on the boundary of the halfspace hk . The polytope S D can also be expressed as the convex hull of the union of dual points Boundhk D .

S D = ConvfBoundhi D j i = 1 : : : ; kg
Let r

2 S . The distance of r from the origin in D

q 2 2 jrj = rx + ry + r 2

is simply

The dual plane r D in D D by de?nition is represented as

rxx + ry y + r = 1

21

This distance of the closest point on this plane to the origin in D D is given by

jrD j = q
Setting in D is

q 2 2 2 rx + ry + r we get that the distance of this point r from the origin and the minimal distance of the dual plane r D from the origin in D D is 1 .
=

1 2 2 2 rx + ry + r

Therefore,

Let fc be the closest plane to the origin of D D not intersecting IntS D . The distance to fc is the same as the distance to the closest point uc in the boundary of S D (which is contained in fc ). And it is easy to see that ,S D as the furthest outlying point in S . The closest point to the origin in the boundary of a polytope lies on the largest inscribed sphere centered at the origin. Observe that ,S  lies on the smallest circumscribing sphere of S in D . Therefore, ?nding the smallest circumscribing sphere  for a polytope S is equivalent to ?nding the largest inscribed sphere D of the dual polytope

jrj = jr1 j D

= fc where ,S  was de?ned earlier

S D . This follows from the relationship
rad = where rad is the radius of the sphere . Now the planes Boundh through the halfspaces in D dualize to the points Boundhk D

1 radD 

= nx; ny ; p? k

These points are equivalent to the wrenches due to unit pull ?nger forces acting at p. In the probing problem we obtain a pair of halfspaces for each probe. Hence, the op-

22

timal probing problem is equivalent to the optimal push-pull grasping problem. We use the optimal grasping criteria as de?ned by Mishra et al. [Mishra et al., 1987] and others [Ferrari and Canny, 1992, Mirtich and Canny, 1994] which is the set of ?nger placements such that the one-norm of the ?nger forces can resist the largest externally applied wrench on the object. We also de?ne the optimal probe placement as the minimal number of probes and their placement necessary to reduce the uncertainty in the position of an object to better than some acceptable level. Using these metric de?nitions, we obtain the following result. Theorem 1 Finding the optimal placement of

k probes is equivalent to ?nding the optimal push-pull frictionless grasp for a set of k ?ngers.
Hitting Sets and Set Covers

7

Recall from the last section that the quality of that probing strategy is given directly by the radius of the maximally inscribed sphere in

SD.

We would like to remove some

vertices of S D such that the radius of the maximally inscribed sphere does not decrease by much. This problem can be posed as a convex set cover problem. The set cover problem is stated for arbitrary sets

L and U

in R d . The problem is to ?nd

C U

with

L ConvU . Here we have L as the sphere of desired radius. This problem has been
studied by several individuals. Recently, Clarkson [Clarkson, 1993] describes a randomized algorithm for computing the three-dimensional convex point set cover from an initial set of n points to within O log c of the optimal cover of c points. His algorithm has a running time of O cn logO1 n.

23

Recent work by Br¨ nniman and Goodrich [Br¨ nnimann and Goodrich, 1994] imo o prove on both the running time and approximation to the optimal convex set covering. Their deterministic algorithm solves the equivalent problem of ?nding a minimal hitting set, where a hitting set is a subset H

X such that H has a non-empty intersection
On log2 n time that is

with every set R in a collection of subsets of X . Their algorithm employs work by Matou?ek [Matou?ek, 1990] on -nets to obtain a hitting set in s s within O 1 of the optimal size hitting set. This set corresponds exactly to the optimal probe placement which we de?ne as a set of c probes that reduce the uncertainty in the position of an object to at least some necessary level for the operation to be performed. In our optimal construction we obtain pairs of halfspaces, hence pairs of points in the dual. However, in the Br¨ nniman and Goodrich algorithm they are treated o as two completely unrelated elements. This will result in near-optimal set sizes that are in the worst case twice as large as we could achieve by grouping the pairs. Alternatively, we can group them to obtain the near-optimal hitting set at a slight running time cost. This performance slowdown is a result of an increase in the VC? dimension [Vapnik and Cervonenkis, 1971] as a result of our pairing. ˇ VC-dimension, named for Vapnik and Chervonenkis, is de?ned for a range space

X; R with P X as the cardinality of the largest set P that is shattered by R. A set P is shattered by R if RP  is the power-set of P , where R P  denotes the set of all intersections of P with sets in R.
To obtain an optimal probing strategy for an array of scanning sensors as shown in Figure 3, we identify the co-linear points in the displacement space and assign them labels such that the hitting set algorithm will include all or none of a set of co-linear

24

points in the probe optimization selection. This also results in an increase in the VCdimension which affects the running time but still ?nds a hitting set within O 1 of the optimal one. Our algorithm successfully handles other variations similar to the co-linear constraint for the scanning sensor without major modi?cation. This makes it well adapted to situations where optimal probing strategies under special constrains are needed and not intuitive to observe. The Theorem below summarizes much of the results of this paper. Theorem 2 A near optimal set of c point probes can be found for any polygonal object in O n log2 n time. Furthermore, the size of the set c will be within O 1 of the size of the optimal set of c point probes.

8

Conclusion

This paper has demonstrated a fast method by which optimal probe placements can be obtained for any known polygonal object. More importantly, the solutions it generates are guaranteed to be within a constant of the actual optimal number of probes necessary. These probing strategies re?ne the position of an object whose pose is approximately known. Furthermore, it is this pose re?nement problem that is a real and frequently encountered challenge in industrial manufacturing. The constraint of requiring probes that leave a part’s pose unchanged after each probing operation is easily satis?ed by employing optical contactless sensors commonly found in industry. This paper also shows that the problem of optimal probe placement is dual to the well studied pushpull grasping problem of positioning frictionless ?ngers on an object.

25

References
[Bernstein, 1986] Bernstein, H. (1986). Determining the shape of a convex n-sided polygon by using 2nk+k tactile probes. In Information Procssing Letters, pages 225–260. [Boissonnat and Yvinec, 1992] Boissonnat, J. and Yvinec, M. (1992). Probing a scene of nonconvex polyhedra. In Algorithmica, pages 321–342. [Br¨ nnimann and Goodrich, 1994] Br¨ nnimann, H. and Goodrich, M. (1994). Almost optimal o o set covers in ?nite vc-dimension. In Proc. 10th ACM Symp. on Computational Geometry (SCG), pages 293–302. [Brost, 1988] Brost, R. C. (1988). Automatic grasp planning in the presence of uncertainty. International Journal of Robotics Research, 7(1):3–17. [Canny and Goldberg, 1994] Canny, J. and Goldberg, K. (1994). RISC for industrial robotics: Recent results and open problems. In IEEE International Conference on Robotics and Automation, volume 3, pages 1951–1958. [Clarkson, 1993] Clarkson, K. L. (1993). Algorithms for polytope covering and approximation. In Proc. 3rd Workshop Algorithms Data Struct., volume 709, pages 246–252. [Cole and Yap, 1987] Cole, R. and Yap, C. (1987). Shape from probing. Journal of Algorithms, 8:19–38. [Das and Joseph, 1990] Das, G. and Joseph, D. (1990). The complexity of minimum nested polyhedra. In Canadian Conference on Computational Geometry.

26

[Dobkin et al., 1986] Dobkin, D., Edelsbrunner, H., and Yap, C. (1986). Probing convex polytopes. In 18th Anual ACM Symposium on Theory of Computing, pages 424–432. [Faverjon and Ponce, 1991] Faverjon, B. and Ponce, J. (1991). On computing two-?nger force closure grasps of curved 2d objects. In IEEE International Conference on Robotics and Automation, pages 424–429. [Ferrari and Canny, 1992] Ferrari, C. and Canny, J. (1992). Planning optimal grasps. In IEEE International Conference on Robotics and Automation, pages 2290–2295. [Goldberg, 1993] Goldberg, K. (1993). Orienting polygonal parts without sensors. Algorithmica. Special Issue on Computational Robotics, Volume 10(3):201–225. [Jia and Erdmann, 1995] Jia, Y.-B. and Erdmann, M. (1995). The complexity of sensing by point sampling. Algorithmic Foundations of Robotics, pages 283–298. [Lindenbaum and Bruckstein, 1990] Lindenbaum, M. and Bruckstein, A. (1990). Reconstructing a convex polygon from binary perspective projections. In Pattern Recognition, pages 1343–1350. [Markenscoff and Papadimitriou, 1989] Markenscoff, X. and Papadimitriou, C. H. (1989). Optimum grip of a polygon. International Journal of Robotics Research, 8(2):17–29. [Matou?ek, 1990] Matou?ek, J. (1990). Construction of -nets. In Discrete Computational s s Geometry, pages 5:427–448. [Mirtich and Canny, 1994] Mirtich, B. and Canny, J. (1994). Easily computable optimum grasps in 2d and 3d. In IEEE International Conference on Robotics and Automation. [Mishra et al., 1987] Mishra, B., Schwartz, J. T., and Sharir, M. (1987). On the existence and synthesis of multi?ngered positive grips. Algorithmica, 2:541–558.

27

[Nevins and Whitney, 1978] Nevins, J. and Whitney, D. (1978). Computer controlled assembly. Scienti?c America, 238(2):62–74. [Paulos and Canny, 1994] Paulos, E. and Canny, J. (1994). Accurate insertion strategies using simple optical sensors. In IEEE International Conference on Robotics and Automation, pages 1656–1662. [Ponce and Faverjon, 1991] Ponce, J. and Faverjon, B. (1991). On computing three-?nger force closure grasps of polyhedral objects. Robotics, pages 1018–1023. ? ? [Vapnik and Cervonenkis, 1971] Vapnik, V. N. and Cervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. In Theory Probab. Appl., pages 16:264–280. [Wallack and Canny, 1993] Wallack, A. and Canny, J. (1993). A geometric matching algorithm for beam scanning. In SPIE International Society for Optical Engineering, volume 2060 Vision Geometry II, pages 143–160. [Wallack and Canny, 1994] Wallack, A. and Canny, J. (1994). Planning for modular and hybrid ?xtures. In IEEE International Conference on Robotics and Automation. [Wallack et al., 1993] Wallack, A., Canny, J., and Manocha, D. (1993). Object localization using crossbeam sensing. In IEEE International Conference on Robotics and Automation, pages 692–699. In International Conference on Advanced

28


相关文章:
更多相关标签: