Squeezing parts

Another example of sensorless manipulation will now be described, which was developed by Goldberg and Mason in [394,395,396]; see also [681]. A Java implementation of the algorithm appears in [131]. Suppose that convex, polygonal parts arrive individually along a conveyor belt in a factory. They are to be used in an assembly operation and need to be placed into a given orientation. Figure 12.50 shows a top view of a parallel-jaw gripper. The robot can perform a squeeze operation by bringing the jaws together. Figure 12.50a shows the part before squeezing, and Figure 12.50b shows it afterward. A simple model is assumed for the mechanics. The jaws move at constant velocity toward each other, and it is assumed that they move slowly enough so that dynamics can be neglected. To help slide the part into place, one of the jaws may be considered as a frictionless contact (this is a real device; see [175]). The robot can perform a squeeze operation at any orientation in $[0,2 \pi)$ (actually, only $[0,\pi)$ is needed due to symmetry). Let $U = [0,2 \pi)$ denote the set of all squeezing actions. Each squeezing action terminates on its own after the part can be squeezed no further (without crushing the part).

Figure 12.50: A parallel-jaw gripper can orient a part without using sensors.

The planning problem can be modeled as a game against nature. The initial orientation, $x \in [0,2 \pi)$, of the part is chosen by nature and is unknown. The state space is ${\mathbb{S}}^1$. For a given part, the task is to design a sequence,

$$\pi = (u_1, u_2, \ldots, u_n) ,$$ (12.35)

of squeeze operations that leads to a known orientation for the part, regardless of its initial state. Note that there is no specific requirement on the final state. After $i$ motion commands have terminated, the history I-state is the sequence

$${\eta}= (u_1, u_2, \ldots, u_i)$$ (12.36)

of squeezes applied so far. The nondeterministic I-space ${\cal I}_{ndet}$ will now be used. The requirement can be stated as obtaining a singleton, nondeterministic I-state (includes only one possible orientation). If the part has symmetries, then the task is instead to determine a single symmetry class (which includes only a finite number of orientations)

Consider how a part in an unknown orientation behaves. Due to rotational symmetry, it will be convenient to describe the effect of a squeeze operation based on the relative angle between the part and the robot. Therefore, let $\alpha = u - x$, assuming arithmetic modulo $2 \pi$. Initially, $\alpha$ may assume any value in $[0,2 \pi)$. It turns out that after one squeeze, $\alpha$ is always forced into one of a finite number of values. This can be explained by representing the diameter function $d(\alpha)$, which indicates the maximum thickness that can be obtained by taking a slice of the part at orientation $\alpha$. Figure 12.51 shows the slice for a rectangle. The local minima of the distance function indicate orientations at which the part will stabilize as shown in Figure 12.50b. As the part changes its orientation during the squeeze operation, the $\alpha$ value changes in a way that gradually decreases $d(\alpha)$. Thus, $[0,2 \pi)$ can be divided into regions of attraction, as shown in Figure 12.52. These behave much like the funnels in Section 8.5.1.

Figure 12.51: The diameter function for a rectangle.

Figure 12.52: There are four regions of attraction, each of which represents an interval of orientations.

The critical observation to solve the problem without sensors is that with each squeeze the uncertainty can grow no worse, and is usually reduced. Assume $u$ is fixed. For the state transition equation $x' = f(x,u)$, the same $x'$ will be produced for an interval of values for $x$. Due to rotational symmetry, it is best to express this in terms of $\alpha$. Let $s(\alpha)$ denote relative orientation obtained after a squeeze. Since $\alpha$ is a function of $x$ and $u$, this can be expressed as a squeeze function, $s : {\mathbb{S}}^1 \rightarrow {\mathbb{S}}^1$, defined as

$$s(\alpha) = f(x,u) - u .$$ (12.37)

The forward projection with respect to an interval, $A$, of $\alpha$ values can also be defined:

$$S(A) = \bigcup_{\alpha \in A} s(\alpha) .$$ (12.38)

Any interval $A \subset [0,2\pi)$ can be interpreted as a nondeterministic I-state, based on the history of squeezes that have been performed. It is defined, however, with respect to relative orientations, instead of the original states. The algorithms discussed in Section 12.1.2 can be applied to ${\cal I}_{ndet}$. A backward search algorithm is given in [395] that starts with a singleton, nondeterministic I-state. The planning proceeds by performing a backward search on ${\cal I}_{ndet}$. In each iteration, the interval, $A$, of possible relative orientations increases until eventually all of ${\mathbb{S}}^1$ is reached (or the period of symmetry, if symmetries exist).

The algorithm is greedy in the sense that it attempts to force $A$ to be as large as possible in every step. Note from Figure 12.52 that the regions of attraction are maximal at the minima of the diameter function. Therefore, only the minima values are worth considering as choices for $\alpha$. Let $B$ denote the preimage of the function $s$. In the first step, the algorithm finds the $\alpha$ for which $B(\alpha)$ is largest (in terms of length in ${\mathbb{S}}^1$). Let $\alpha_0$ denote this relative orientation, and let $A_0 = B(\alpha_0)$. For each subsequent iteration, let $A_i$ denote the largest interval in $[0,2 \pi)$ that satisfies

$$\vert S(A_{i-1})\vert < \vert A_i \vert ,$$ (12.39)

in which $\Vert\cdot\Vert$ denotes interval length. This implies that there exists a squeeze operation for which any relative orientation in $S(A_{i-1})$ can be forced into $A_i$ by a single squeeze. This iteration is repeated, generating $A_{-1}$, $A_{-2}$, and so on, until the condition in (12.39) can no longer be satisfied. It was shown in [395] that for any polygonal part, the $A_i$ intervals increase until all of ${\mathbb{S}}^1$ (or the period of symmetry) is obtained.

Suppose that the sequence $(A_{-k},\ldots,A_0)$ has been computed. This must be transformed into a plan that is expressed in terms of a fixed coordinate frame for the robot. The $k$-step action sequence $(u_1,\ldots,u_k)$ is recovered from

$$u_i = s(\beta_{i-1}) - a_i - \begin{matrix}\frac{1}{2} \end{matrix} (\vert A_{i-k}\vert-\vert S(A_{i-k-1})\vert) + u_{i-1}$$ (12.40)

and $u_{-k} = 0$ [395]. Each $a_i$ in (12.40) is the left endpoint of $A_i$. There is some freedom of choice in the alignment, and the third term in (12.40) selects actions in the middle to improve robustness with respect to orientation errors. By exploiting a proof in [195] that no more than $O(n)$ squeeze operations are needed for a part with $n$ edges, the complete algorithm runs in time $O(n^2)$.

Example 12..9 (Squeezing a Rectangle)   Figure 12.53 shows a simple example of a plan that requires two squeezes to orient the rectangular part when placed in any initial orientation. Four different executions of the plan are shown, one in each column. After the first squeeze, the part orientation is a multiple of $\pi/2$. After the second squeeze, the orientation is known. Even though the execution looks different every time, no feedback is necessary because the I-state contains no sensor information. $\blacksquare$

Figure 12.53: A two-step squeeze plan [395].