Orienting Parts with Shape Variation

Abstract

Industrial parts are manufactured to tolerances as no production process is capable of delivering perfectly identical parts. It is unacceptable that a plan for a manipulation task that was determined on the basis of a CAD model of a part fails on some manufactured instance of that part, and therefore it is crucial that the admitted shape variations are systematically taken into account during the planning of the task. We study the problem of orienting a part with given admitted shape variations by means of pushing with a single frictionless jaw. We use a very general model for admitted shape variations that only requires that any valid instance must contain a given convex polygon $P_I$ while it must be contained in another convex polygon $P_E$. The problem that we solve is to determine, for a given $h$, the sequence of $h$ push actions that puts all valid instances of a part with given shape variation into the smallest possible interval of final orientations. The resulting algorithm runs in $O(hn)$ time, where $n=|P_I|+|P_E|$.

1 Introduction

Most of the existing solutions in algorithmic automation assume a severely idealized world in which parts are perfectly identical to their CAD-model and manipulators and sensors are infinitely accurate. In real life, however, parts are manufactured to tolerances [6, 7] and therefore vary in shape [1], and sensors [4] and actuators [5] are inaccurate, causing the aforementioned algorithms to fail when employed in practice. The challenge is therefore to design algorithms for planning manipulation tasks that explicitly take into account manipulator (and sensor) inaccuracy and part imperfection and report solutions that work despite their presence. In this paper, we concentrate on part shape variation and study its impact on the problem of feeding or orienting it by means of pushing with a frictionless jaw in the spirit of the work by Goldberg [11]. We employ a very general model for shape variation and systematically explore its impact on the task of orienting by pushing. We use the resulting properties to develop a robust algorithm that reduces the uncertainty in the pose of an imperfect part, i.e., a part with shape variation, as much as possible.

Sensorless manipulation has received considerable attention over the past two decades. It focuses on manipulation systems that use simple (and thus cheap and reliable) hardware components that are only capable of performing simple physical actions while using simple or no sensors. The goal in sensorless part feeding or orienting is to reduce the set of possible orientations until the part is in a known final orientation. Lozano-Perez et al. [8] and Erdmann and Mason [9] proposed designs for feeding based on a finite set of actions to orient a part. Akella and Mason [10] developed a complete open-loop plan for feeding by means of pushing . Goldberg [11] showed that there always exists a plan for orienting a polygonal part by pushing or squeezing using a frictionless parallel-jaw gripper and proposed a greedy algorithm for computing the shortest such plan in $O(n^2 \log n)$ time, where $n$ is the number of vertices of the part. He conjectured that the length of the shortest plan is linear in $n$. Chen and Ierardi [12] proved Goldberg’s conjecture and also showed how to compute the maximum uncertainty radius such that a plan still exists. Berretty et al. [13] showed that 3D (polyhedral) parts can be oriented by a sequence of pushes by a perpendicular pair of planar jaws and gave an $O(n^3 \log n)$ time algorithm to find such a plan.

There are also approaches that are based on constrained forms of pushing. Wiegley et al. [14] considered a system consisting of a conveyor belt with fences mounted to its sides, which reorient parts that slide along them while traveling on the belt. The problem of designing the fences is equivalent to computing push actions with constraints on successive push directions. Wiegley et al. presented an exponential algorithm for finding the shortest sequence of fences that orients a given part. Berretty et al. [15] presented an alternative graph-based algorithm that runs in $O(n^3 \log n)$ time. In addition, Goldberg [11] and Chen and Ierardi [12] also studied grasps in which a jaw first pushes and then squeezes a part. Their time and complexity bounds are similar to those for pure pushing.

Several authors considered models and problems involving uncertainty in geometric data. For modeling shape variation, geometric approaches such as $\epsilon$-geometry [16], $\lambda$-geometry [17], toleranced and interval-geometry [18, 20] were proposed. In these models, imprecise input data (e.g. vertices of a polygon) are constrained to vary in a region such as a segment, disk, rectangle, or any convex polygon, and worst and best cases of the output of certain problems are studied.

There have been a few studies into part feeding in a context of imperfect parts. Akella and Mason [22] studied the problem of orienting convex polygons whose vertices and center of mass lie inside predefined disks centered at their nominal locations. They required that any variation keeps the part convex. They proposed graph-based approaches for fence and push-squeeze plans for parts that satisfy their assumptions. The problem of orienting a part by fences has been studied by Chen et al. [3]. They used a similar model for part shape variation by allowing the vertices to vary inside disks and squares that are defined relative to the center of mass. Based on their assumptions they proposed a method for computing the maximum allowable disk or square for each vertex for feeding. In addition to these studies, other related work [23, 24] considered location uncertainty and shape variation in a grasp planning context.

In comparison with the aforementioned studies, we consider a more general model for shape variation that allows to characterize variation along the entire boundary instead of only at the vertices. The model assumes that any valid instance of a part contains a given convex shape while it is contained in another given convex shape. Our goal is to solve the part feeding or orienting problem for the imperfect part, that is, we want to find the sequence of pushes that puts all instances from the shape family into the smallest possible interval of orientations. To this end we generalize the notions of radius and push function [11] to families of shapes. In Sects. 3 and 4 we present several properties of the generalized push function along with its upper and lower envelopes. These properties help us to develop a greedy algorithm for reporting the smallest interval of possible orientations for the entire shape family after a given number $h$ of pushes. We also show that there exist imperfect parts for which there always is a next push that shrinks the interval of possible orientations.

2 Preliminaries

In this section, we explain our assumptions and introduce the terminology and notation used throughout the paper. To do this, we first define the problem of orienting a part with shape variation . Then, we will have a short review of the relevant concepts from previous work and finally we define similar concepts for a part with shape variation. For brevity, we have omitted most proofs in this paper, but interested readers can find those in our technical report [27].

2.1 Orienting Parts with Shape Variation

Manufactured parts always have slight imperfections; hence, they are designed up to certain tolerances. We study the problem of orienting a part with shape variations by means of pushing with a single frictionless jaw [11] under the general shape variation model presented in [19]. In this model, for any manufactured planar model part of $P_M$, the set of acceptable instances is a family of shapes $S(P_I,P_E)=\{P \subset \mathbb {R}^2 | P_I \subseteq P \subseteq P_E\}$ where $P_I$ and $P_E$ are two given closed objects satisfying $P_I \subseteq P_M \subseteq P_E$. The closed region resulting from subtracting the interior of $P_I$ from $P_E$ is referred to be tolerance zone and denoted by $Q$. See Fig. 1a. We will often refer to a part with shape variation as an imperfect part. The objects $P_I$ and $P_E$ in this paper are assumed to be convex and polygonal with a total of $n$ edges. The property of convexity helps us to compute a tight bound on the final orientation of an imperfect part. Also, we assume that the boundaries of $P_I$ and $P_E$ are disjoint.

Fig. 1

a A family of shapes specified by a subshape $P_I$ and a supershape $P_E$ of a model part $P_M$ along with a valid instance $P \in S(P_I,P_E)$. b A polygon $P$ and its supporting line in the vertical downward direction; when the single jaw moves upward, $P$ rotates in counterclockwise direction

When there is variation in part shape there will also be variation in the location of the center of mass of the part. In general, the problem of finding the exact locus of the center of mass for a polygon with shape variation has been mentioned as an open problem in [4, 22]. An algorithm for computing a polygonal approximation of the locus has been presented in [19] under the aforementioned shape variation model. However, for simplicity in this paper, we assume that all instances of an imperfect part have their center of mass at the origin. As a result, an instance $P$ belongs to $S(P_I,P_E)$ if its boundary lies completely inside the tolerance zone $Q$ when its center of mass is placed at the origin.

The basic action of pushing a part at the direction of $\theta$ consists of placing a single jaw in orientation $\theta$ and moving it in a direction perpendicular to itself. When a part $P$ is pushed, it will start a compliant motion (rotation), during which it decreases the distance from its center of mass to the jaw. The motion stops when the normal to the jaw passes through the center of mass of the part. We refer to the corresponding direction of the contact normal as an equilibrium orientation. An equilibrium orientation is a stable orientation if an edge of part’s convex hull is in contact with the jaw [2].

We define the problem of orienting an imperfect part to be that of finding the sequence of push actions that orients the part to the smallest possible orientation set. This possible orientation set consists of disjoint intervals. However, we do not exploit this fact and focus on finding the smallest single interval that contains all possible orientations.

Fig. 2

An example of an imperfect part, the corresponding graphs of $r_I$, $r_E$ are illustrated in black and the red graph depicts $\delta _E$. The illustrated angles $\theta _R$, $\theta _L$ and $\theta _N$ are R-type, L-type and N-type, respectively; $\theta _m$ is both R-type and L-type. $\theta _{cw}$ is a clockwise and $\theta _{cw}$ is a counterclockwise unstable angle. $[\theta ', \theta )$ and $(\theta _1,\theta _2)$ are N-type intervals

2.2 Definitions for a Part

Throughout this paper, directions are relative to a fixed coordinate frame attached to the origin, increasing in counterclockwise order. Let the set of orientations of $P$ be identified with points on the planar unit circle $S^1:[0,2\pi )$. For any orientation $\theta$, the supporting line at the direction $\theta$ is a supporting line whose normal vector emanating from the origin has direction $\theta$. See Fig. 1b. Pushing $P$ at the direction $\theta$ means aligning the jaw with the supporting line at the direction $\theta$. For an interval $\varTheta$, we let $L(\varTheta )$ and $U(\varTheta )$ be the lower and upper bounds (left and right endpoints) of $\varTheta$, respectively, and $|\varTheta |$ be its length.

The radius function $r_P:S^1\rightarrow \mathbb {R}^+$ of a part $P$ maps an angle $\theta$ onto the distance between the center of mass and the supporting line of $P$ at the direction $\theta$ [2]. The distance function $\delta _P:S^1\rightarrow \mathbb {R}^+$ of $P$ maps an angle $\theta$ onto the distance between the center of mass and the intersection point of the boundary $\partial P$ of $P$ and the ray emanating from the center of mass at the direction $\theta$ [13]. Figure 2 depicts the radius functions of $P_I$ and $P_E$ and the distance function of $P_E$ for the illustrated imperfect part. The radius and distance functions are closely related; see Observation 1.

Observation 1

The local minima and maxima of $r_P$ and $\delta _P$ coincide; $r_P$ is increasing (decreasing) if and only if $\delta _P$ is increasing (decreasing).

The push function $\phi _P:S^1 \rightarrow S^1$ of $P$ maps a push direction of the jaw relative to $P$ in its reference orientation onto the orientation of $P$ after alignment with the jaw. It is well known [11] that the push function follows directly from the radius function as it maps all orientations that are strictly between two consecutive local maxima of the radius function onto the local minimum that is enclosed by these local maxima; moreover, the push function maps each local maximum of the radius function onto itself.

2.3 Definitions for a Part with Shape Variation

In this subsection, we define the relevant concepts related to imperfect parts. For simplicity, we use the abbreviations $r_I=r_{P_I}$, $r_E=r_{P_E}$, and $\delta _E=\delta _{P_E}$. Figure 2 illustrates an example of an imperfect part and the graph of $r_I$, $r_E$ and $\delta _E$. The following lemma shows that $r_I$ and $r_E$ bound the radius function of all instances of an imperfect part.

Lemma 1

$r_I \le r_P \le r_E$ for all $P \in S(P_I, P_E)$.

Pushing an imperfect part means pushing an unknown instance from a shape family $S(P_I,P_E)$. As a consequence, the outcome of such a push is the set of all orientations that might result after pushing any shape $P \in S(P_I,P_E)$. To capture this behavior we define the generalized push function $\varPhi ^*:S^1 \rightarrow \mathcal {P}(S^1)$, where $\mathcal {P}(S^1)$ denotes the power set of $S^1$. This function maps an angle $\theta$ onto the set of all possible orientations after a single push action in the direction $\theta$, so $\varPhi ^*(\theta )=\{\phi _P(\theta )|P \in S(P_I, P_E)\}$. As there are several ways to enclose the sets $\varPhi ^*(\theta )$ by a single interval (due to the cyclic nature of $S^1$) we must be careful when defining these intervals to avoid ambiguity. To this end we introduce the lower push function and the upper push function in Definition 1.

Definition 1

The lower push function $\varPhi ^*_L:S^1 \rightarrow S^1$ and upper push function $\varPhi ^*_U:S^1 \rightarrow S^1$ are the functions that bound $\varPhi ^*$ as follows. We consider three cases based on the push direction $\theta$.

• (a) If all instances of $S(P_I,P_E)$ rotate clockwise when pushed at $\theta$ then let $\alpha$ and $\beta$ be tight upper and lower bounds on the magnitude of the clockwise rotations, respectively. Then $\varPhi ^*_L(\theta ) =\theta -\alpha$ and $\varPhi ^*_U(\theta ) =\theta -\beta$.

• (b) If all instances of $S(P_I,P_E)$ rotate counterclockwise when pushed at $\theta$ then let $\alpha$ and $\beta$ be tight lower and upper bounds on the magnitude of the counterclockwise rotations, respectively. Then $\varPhi ^*_L(\theta ) =\theta +\alpha$ and $\varPhi ^*_U(\theta ) =\theta +\beta$.

• (c) Otherwise let $\alpha$ and $\beta$ be tight upper bounds on the magnitudes of the clockwise and counterclockwise rotations, respectively. Then $\varPhi ^*_L(\theta ) = \theta -\alpha$ and $\varPhi ^*_U(\theta ) =~\theta +\beta$.

Note that for each $\theta \in S^1$ the interval $[\varPhi ^*_L(\theta ),\varPhi ^*_U(\theta )]$ contains the set $\varPhi ^*(\theta )$. We will occasionally denote this interval by $\varPhi (\theta )$ and refer to it as the smallest interval containing the set $\varPhi ^*(\theta )$. Moreover, for an interval $\varTheta \subseteq S^1$ we let $\varPhi (\varTheta ) = [\varPhi ^*_L(L(\varTheta )),\varPhi ^*_U(U(\varTheta ))]$

We also note that $\varPhi ^*_L$ and $\varPhi ^*_U$ are monotone (non-decreasing), which admits a greedy approach to orient the imperfect part into the smallest possible range of angles. We start with the initial set of possible orientations $\varTheta _0=[0,2\pi )$ and repeatedly obtain $\varTheta _{i+1}$ by selecting it to be the shortest image of any translate of $\varTheta _i$ under $\varPhi$. The process continues as long as $|\varTheta _{i+1}|<|\varTheta _i|$. To this end, we need to compute the functions $\varPhi ^*_L$ and $\varPhi ^*_U$. For different types of orientations, the values of these functions are computed differently. These types of angles are defined in the next section.

Remark

Since range and domain of $\varPhi ^*_L$ and $\varPhi ^*_U$ are $S^1$, it is possible that $\varPhi ^*_L(L(\varTheta )) >\varPhi ^*_U(U(\varTheta ))$. In this case, $|\varPhi (\varTheta )|=2\pi + \varPhi ^*_U(U(\varTheta ))-\varPhi ^*_L(L(\varTheta ))$.

3 Types of Orientations

The set of all orientations can be divided into five types based on the computation of their image under $\varPhi ^*_L$ and $\varPhi ^*_U$. We distinguish two primary types which consist of two and three subtypes respectively.

• An orientation $\theta$ is unstable if there is no $P \in S(P_I,P_E)$ for which $r_P$ has a local minimum a $\theta$. Such an orientation can never be the final orientation of the imperfect part after pushing. Unstable orientations can be (i) clockwise unstable, or (ii) counterclockwise unstable.

• An orientation $\theta$ is potentially stable or p-stable if there exists an instance $P \in S(P_I, P_E)$ for which $r_P$ has a local minimum at $\theta$. Such an orientation can be a final orientation of the imperfect part after pushing. Potentially-stable orientations can be (i) right type (R-type), or (ii) left type (L-type), or (iii) neutral type (N-type).

In the following subsections we define the subtypes and properties of p-stable and unstable orientations. The types of orientations divide $S^1$ into intervals of orientation of the same type. These intervals will be referred to as critical intervals. The type of a critical interval equals the type of orientations it contains

3.1 Unstable Intervals

Unstable intervals help to reduce the uncertainty in the orientation of an imperfect part as they can never appear in the set of possible orientations after a push action. The following lemma describes how we can distinguish unstable angles.

Lemma 2

An orientation $\theta \in S^1$ is unstable if and only if $\delta _E(\theta )<r_I(\theta )$.

Figure 2 shows several unstable intervals, in which the (red) graph of $\delta _E$ lies below the (lower black) graph of $r_I$. Lemma 2 shows that we can determine the subdivision of $S^1$ into unstable and p-stable intervals by computing the intersection of $\delta _E$ and $r_I$. Note that the unstable intervals can be computed in $O(n)$ time since the number of intersection points cannot exceed $O(n)$.

Observation 2

Let $\varTheta \subset S^1$ be an unstable interval. All instances $P\in S(P_I,P_E)$ will rotate in the same direction, i.e., in either clockwise or counterclockwise direction, for all push directions $\theta \in \varTheta$.

The above observation shows that there are clockwise and counterclockwise orientations and intervals. For any instance $P \in S(P_I,P_E)$, $r_P$ is strictly increasing in a clockwise unstable interval and strictly decreasing in a counterclockwise unstable interval. In Fig. 2, $\theta _{cw}$ and its containing interval are clockwise unstable while $\theta _{ccw}$ and its containing interval are counterclockwise unstable.

3.2 Potentially-Stable Intervals

According to Lemma 2 p-stable orientations are angles in which the graph of $\delta _E$ lies above the graph of $r_I$. Now consider the graph of $\delta _E$. A p-stable angle $\theta$ is called R-type if from the point $(\theta ,\delta _E(\theta ))$ the graph of $r_I$ is horizontally visible to the right. Similarly, it is called L-type if the graph of $r_I$ is horizontally visible to the left. If there is no horizontal visibility of $r_I$ the p-stable angle is referred to as N-type. In Fig. 2 the angle $\theta _R$ is R-type because the horizontal ray emanating from $(\theta ,\delta _E(\theta ))$ to the right first hits $r_I$; $\theta _L$ is an L-type angle as the horizontal ray emanating from $(\theta ,\delta _E(\theta ))$ to the left hits $r_I$.

The following definition describes the three types of angles more precisely.

Definition 2

Let $\theta \in S^1$ be a p-stable angle.

• $\theta$ is R-type if and only if there is no angle $\xi$ such that $\theta < \xi < \theta '$ and $r_E(\xi ) =\delta _E(\theta )$, where $\theta ' > \theta$ is the smallest angle such that $r_I(\theta ') =\delta _E(\theta )$. The angle $\theta '$ is called upper bound of $\theta$ denoted by $B_U(\theta )$.

• $\theta$ is L-type if and only if there is no angle $\xi$ such that $\theta ' < \xi < \theta$ and $r_E(\xi ) =\delta _E(\theta )$, where $\theta ' < \theta$ is the largest angle such that $r_I(\theta ') =\delta _E(\theta )$. The angle $\theta '$ is called lower bound of $\theta$ denoted by $B_L(\theta )$.

• $\theta$ is N-type if it is neither R-type nor L-type.

Remark

Throughout this paper, the term right refers to the counterclockwise direction and left refers to the clockwise direction. The following observation can be made about $r_I$ and $r_E$. See Fig. 2.

Observation 3

Let $\theta \in S^1$ be R-type (L-type). Then $r_E$ is increasing (decreasing) in a sufficiently small right (left) neighborhood of $\theta$ and $r_I$ is increasing (decreasing) in a sufficiently small left (right) neighborhood of $B_U(\theta )$ ($B_L(\theta )$).

It is possible that an angle is both L-type and R-type. Lemma 3 shows that such angles are local minima of $r_E$.

Lemma 3

If $\theta \in S^1$ is R-type and L-type, then $\theta$ is a local minimum of $r_E$.

It is not difficult to see that each orientation is of one of the aforementioned types. Lemma 4 bounds the resulting number of critical intervals and their computation time.

Lemma 4

There are $O(n)$ critical intervals; they are computable in $O(n)$ time.

4 Computing the Lower and Upper Push Functions

To compute $\varPhi ^*_L$ and $\varPhi ^*_U$, we need to find the tight lower and upper bounds for the amount of clockwise or counterclockwise rotation of an imperfect part. (See Definition 1.) Recall that when a part is pushed, it rotates in the direction in which the radius function decreases. As a result, we are interested in as longest as possible non-increasing curve (to the right as well as to the left) that lies completely between $r_I$ and $r_E$. We note that not every such a curve corresponds to a valid part. Therefore, our strategy is to construct valid instances which create these bounds for clockwise and counterclockwise rotations when it is being pushed at $\theta$.

In this section, we show that if $\theta$ belongs to a counterclockwise unstable interval then $\varPhi ^*_L(\theta )$ is the right endpoint of that interval. Otherwise, $\varPhi ^*_L(\theta )$ is the left bound of some specific L-type angle. Similarly, if $\theta$ belongs to a clockwise unstable interval then $\varPhi ^*_U(\theta )$ is the left endpoint of that interval. Otherwise, $\varPhi ^*_U(\theta )$ is the right bound of some specific R-type angle. We will focus on computing upper bounds in this section with the understanding that lower bounds can be computed similarly.

If $\theta$ is a clockwise unstable angle then there is no instance $P \in S(P_I,P_E)$ that rotates counterclockwise. Therefore, the upper bound cannot exceed the left endpoint of the unstable interval that contains $\theta$. This upper bound is easy to compute. We now assume that $\theta$ is not a clockwise unstable angle. In this case, $\varPhi ^*_U(\theta ) \ge \theta$. We note that if an instance $P$ rotates counterclockwise, then $r_P$ has to be strictly decreasing in a sufficiently small right neighborhood of $\theta$. We define an instance whose radius function is decreasing along the largest possible interval. We refer to this instance as the upper critical instance at the direction $\theta$. The critical instance suggests us an approach to compute $\varPhi ^*_U(\theta )$. We present an algorithm that constructs the upper critical instance for every $\theta$. Then, we prove a theorem that helps to compute $\varPhi ^*_U$ from these critical instances.

By definition, if $P$ is an upper critical instance, then $r_P$ has to be decreasing in the interval $[\theta , \varPhi ^*_U(\theta )]$. For angles in which $r_E$ is decreasing, it is not difficult to find such instances. For the other angles we prove the following lemma.

Lemma 5

Let $\theta \in S^1$ be an angle such that $r_E$ is increasing in a right neighborhood of $\theta$ and let $P \in S(P_I,P_E)$ be an instance that rotates counterclockwise after a single push action at the direction $\theta$. Then $r_P(\theta ) \le \delta _E(\theta )$.

The next corollary follows from Lemma 5 and Observation 1.

Corollary 1

Let $\theta \in S^1$ be an R-type angle and $P \in S(P_I, P_E)$ be its upper critical instance. Then $r_P(\theta ) \le \delta _E(\theta )$.

Corollary 1 reveals that $B_U(\theta )$ is an upper bound on $\varPhi ^*_U(\theta )$. Note that by Observation 3 for an R-type angle $\theta$, $r_I$ is ascending in the left neighborhood of $B_U(\theta )$. So, no decreasing curve starting in the right neighborhood of $\theta$ cannot extend beyond $B_U(\theta )$. The following lemma shows that $B_U(\theta )$ is tight.

Lemma 6

Let $d>0$ be a constant and $[\theta _1,\theta _2] \subset S^1$ be an interval such that for all $\theta \in [\theta _1, \theta _2]$, $r_I(\theta )\le d \le \delta _E(\theta )$. Then there is an instance $P$ such that $r_P(\theta )=d$ for all $\theta \in [\theta _1,\theta _2]$.

So far, we discussed how to compute $\varPhi ^*_U(\theta )$ if $\theta$ is clockwise unstable or R-type. Otherwise, we claim that there is an instance $P \in S(P_I,P_E)$ such that $r_P$ is decreasing in $[\theta , B_U(\theta _m)]$, where $\theta _m$ is the closest R-type angle to $\theta$ in counterclockwise direction. If such an angle does not exist, then the upper bound is $2\pi$. The following lemma shows that $\theta _m$ is a local minimum of $r_E$.

Lemma 7

If an angle $\theta$ is neither a clockwise unstable angle nor an R-type angle, then the closest R-type angle to $\theta$ in counterclockwise direction is a local minimum for $r_E$.

Algorithm 1 creates the upper critical instance for an angle $\theta _0$ that is not clockwise unstable. The key idea is that for such an angle $\theta _0$, there is an instance $P \in S(P_I,P_E)$ such that $r_P$ is decreasing in $[\theta _0, B_U(\theta _m)]$ where $\theta _m$ is the closest R-type angle to $\theta _0$ in counterclockwise direction. If there is no such R-type angle, then there is an instance that can rotate arbitrarily close to $2 \pi$. We explain how to construct a decreasing function and then show that this function is a part of the radius function of the instance reported by Algorithm 1. Lemma 6 shows that any horizontal ray that lies above the graph of $r_I$ and below the graph of $\delta _E$ lies on the radius function of some instance. Note that according to Lemma 5 for any $\theta \in [\theta _0, B_U(\theta _m)]$ if $r_E$ is increasing in the neighborhood of $\theta$ and $P$ rotates in counterclockwise direction, then $r_P(\theta ) < \delta _E(\theta )$. Therefore, we construct a function for $P$ by starting from $\theta _0$ and follow the horizontal ray emanating from $(\theta _0,\delta _E(\theta _0))$ as long as it stays below $\delta _E$ and above $r_I$. Here $P$ satisfies $r_P(\theta )=\delta _E(\theta _0)$. If the ray hits $r_I$ we are done. Alternatively, it hits $\delta _E$ at some angle $\theta '$ at which $\delta _E$ is decreasing in the right neighborhoods of $\theta '$. We continue by choosing $r_P(\theta )=\delta _E(\theta ') \cos (\theta '-\theta )$ until we hit $r_E$. Then we follow $r_E$ until the closest local minimum and then again we use horizontal rays and continue similarly. The blue graph in Fig. 3 is an example of a function that is created using this procedure. Algorithm 1 constructs the corresponding instance which is also shown in Fig. 3. In Algorithm 1, $P(\theta _1, \theta _2)$ stands for the part of $P$ between two rays emanating from the center of mass in directions $\theta _1$ and $\theta _2$, $E_I$ and $E_E$ are the sets of edges of $P_I$ and $P_E$ respectively, and $D_d$ is the boundary of a disc of radius $d$ centered at the center of mass.

Fig. 3

Illustration of Algorithm 1 for an imperfect part. The critical instance constructed for the given angle $\theta _0$ is shown in blue. The diagram on the right shows that the corresponding radius function is decreasing; $\theta _m$ is the closest R-type angle in counterclockwise direction from $\theta _0$ and $\theta _u=B_U(\theta _m)$

The following lemmas provide the basis for the computation of the critical instance.

Lemma 8

Let $\theta \in S^1$ be R-type and satisfying $\theta =B_U(\theta )$. There is no instance $P \in S(P_I,P_E)$ that rotates counterclockwise when pushed at $\theta$.

Lemma 9

Assume that an imperfect part is pushed at direction $\theta _0$. If there is no $\theta \ne \theta _0$ such that $\theta$ is an R-type angle, then there is an instance in $S(P_I,P_E)$ that rotates arbitrarily close to $2 \pi$. Otherwise, we consider the following cases for the upper bound of the final orientation considering all instances $P\in S(P_I,P_E)$.

• (a) If $\theta _0$ is a clockwise unstable angle, then the left endpoint $\theta _u$ of the containing unstable interval is a tight closed upper bound.

• (b) If $\theta _0$ is not a clockwise unstable angle, then $\theta _u=B_U(\theta _m)$, with $\theta _m$ being the closest R-type angle to $\theta _0$ in counterclockwise direction, is a tight open upper bound.

We summarize the discussion of this section in the following theorem.

Theorem 4

$\varPhi ^*_L$ and $\varPhi ^*_U$ can be computed in $O(n)$.

Proof

Lemma 4 shows that the critical intervals can be computed in $O(n)$. For any $\theta$ belonging to a critical interval $\varTheta$, the function $\varPhi ^*_U$ can be computed by applying Lemma 9.

• If $\varTheta$ is clockwise unstable, then $\varPhi ^*_U(\theta )=L(\varTheta )$.

• If $\varTheta$ is R-type, then $\varPhi ^*_U(\theta )=B_U(\theta )$. Note that for an R-type angle $\theta$, $r_I(\varPhi ^*_U(\theta ))=\delta _E(\theta )$. Then, $\varPhi ^*_U(\theta )=r_I^{-1}(\delta _E(\theta ))$ for the corresponding range of $\delta _E$ and domain of $r_I^{-1}$.

• For all remaining intervals, i.e., counterclockwise unstable, L-type and N-type, $\varPhi ^*_U(\theta )=B_U(\theta _m)$ where $\theta _m$ is the closest R-type angle in counterclockwise direction. According to Lemma 7, $\theta _m$ is a local minimum of $r_E$; therefore it is sufficient to check only the local minima. Since the number of local minima is linear and they occur in order, using a simple traversal of the graphs all of them can be computed in a linear time.

The time complexity of computing $\varPhi ^*_U$ is $O(n)$. The same bound applies to $\varPhi ^*_L$. $\square$

Fig. 4

a An example of an imperfect part. b $r_I$, $r_E$ (black) and $\delta _E$ (red). c $\varPhi ^*_L$ (blue) and $\varPhi ^*_U$ (black)

Figure 4a, b illustrate an imperfect part and the radius and distance functions. The corresponding $\varPhi ^*_L$ and $\varPhi ^*_U$ are depicted by blue and black curves in Fig. 4c, respectively. It can be observed that for unstable and N-type intervals, the graphs of $\varPhi ^*_L$ and $\varPhi ^*_U$ are horizontal. For L-type intervals, the graph of $\varPhi ^*_L$ curves downward and the graph of $\varPhi ^*_U$ is horizontal, while for R-type intervals the graph of $\varPhi ^*_U$ curves upward and the graph of $\varPhi ^*_L$ is horizontal.

5 An Algorithm for Orienting an Imperfect Part

In the previous section we have shown how to compute $\varPhi ^*_L$ and $\varPhi ^*_U$. The monotonicity of these functions admits a greedy approach to find, for a given integer $h \ge 0$, the sequence of $h$ push actions that orients an imperfect part into the smallest possible interval of orientations. Let $\varTheta _i$ be the smallest interval containing all possible orientations after $i$ pushes. Obviously, $\varTheta _0=S^1$, and after the first push the part will be in one of the p-stable orientations, so $\varTheta _1=S^1-\varPi _{max}$, where $\varPi _{max}$ is the largest unstable interval. The interval $\varTheta _{i+1}$ can be obtained by computing the shortest image of any translate of $\varTheta _i$ under $\varPhi$. The process continues as long as $|\varTheta _{i+1}|<|\varTheta _i|$ and $i < h$. Lemma 10 helps us to discretize the search for $\varTheta _{i+1}$ by showing that it suffices to consider only translates of $\varTheta _i$ in which one of its endpoints coincides with an endpoint of some unstable interval. We first give an observation that is needed to prove Lemma 10. It says that any p-stable angle $\theta$ appears in its own image under $\varPhi ^*$ (and $\varPhi$), because, by definition, there is an instance in $S(P_I,P_E)$ that is stable after pushing at $\theta$.

Observation 5

$\varPhi ^*_L(\theta ) \le \theta \le \varPhi ^*_U(\theta )$ if and only if $\theta$ is a p-stable angle, for any $\theta \in S^1$.

Lemma 10

Let $\varTheta \subset S^1$ be an interval with the smallest image under $\varPhi$ among all the intervals with the length of a given value. If $|\varPhi (\varTheta )|<|\varTheta |$, then there exists an interval $\varTheta ' \subset S^1$ with $|\varPhi (\varTheta )| = |\varPhi (\varTheta ')|$ such that $L(\varTheta ')$ or $U(\varTheta ')$ coincides with an endpoint of an unstable interval.

Algorithm 2 computes the smallest possible interval of orientations for an imperfect part after (at most) $h$ push actions. Lemma 10 shows that it suffices to repeatedly align the endpoints of the current smallest interval $\varTheta _i$ with each of the endpoints of the $k$ unstable intervals $\varPi _j$ ($1 \le j \le k$) to determine $\varTheta _{i+1}$. Figure 5 shows the application of the algorithm to the imperfect part of Fig. 4.

Fig. 5

Illustration of Algorithm 2 applied to the imperfect part of Fig. 4a, showing the intervals $\varTheta _i$ for $i=0,\ldots ,7$. The length of the image of any translate of $\varTheta _7$ will be at least as long as $\varTheta _7$; as a result, no further reduction of the interval of possible orientations is possible

Theorem 6

Algorithm 2 finds the sequence of $h \ge 0$ push actions that puts the imperfect part given by $S(P_I,P_E)$ in the smallest interval of possible orientations in $O(hn)$ time.

Instead of running Algorithm 2 for a given maximum number $h$ of pushes, we can also remove that bound and run it as long as the intervals $\varTheta _i$ continue to shrink, to obtain the largest possible reduction of the uncertainty in the imperfect part’s pose. A natural question that arises is whether the algorithm would terminate in that case and thus whether the maximum reduction of pose uncertainty can be obtained after a finite number of pushes. It turns out that it is not always the case.

Recall that Algorithm 2 repeatedly aligns the left or right endpoint of an interval $\varTheta _i$ with one of the $O(n)$ endpoints of an unstable interval $\varGamma$. The other endpoint of $\varTheta _i$ then ends up in one of the $O(n)$ critical intervals, say $\varGamma '$. In order to obtain $\varOmega (n^2)$ iterations the endpoints of some interval $\varTheta _j$ with $j > i$ should be able to return to the same pair of intervals consisting of $\varGamma$ and $\varGamma '$.

We assume without loss of generality that the left endpoint of $\varTheta _i$ (and the future interval $\varTheta _j$) coincides with an endpoint of an unstable interval endpoint $\varGamma _L$. It is not hard to see that the interval $\varGamma _R$ containing the right endpoint(s) must have a variable $\varPhi ^*_U$.

Lemma 11

Assume that the left endpoints of two intervals $\varTheta _i$ and $\varTheta _j$ in Algorithm 2 for some $j>i$ share the same endpoint of an unstable interval $\varGamma _L$ and their right endpoints lie in the same critical interval $\varGamma _R$. Then $\varGamma _R$ must be R-type.

Fig. 6

a The sequence of $x_{n+1}=f(x_{n})-d$ where $\lim \limits _{n \rightarrow \infty }x_n=a$. b $L(\varPsi _{i-1})$ lies on $L(\varGamma _L)$ and $U(\varPsi _{i-1})$ lies in $\varGamma _R$; $|\varPhi (\varPsi _{i-1})|=|\varPsi _{i-1}|-|\varGamma _L|+ \varPhi ^*_U(U(\varPsi _{i-1}))-U(\varPsi _{i-1})$

Lemma 12 helps us to determine the conditions for which the resulting intervals of Algorithm 2 can be shrunk endlessly.

Lemma 12

Let $d>0$ be a constant value and $f$ be a continuous and non-decreasing function which has a derivative at every point in its domain $A \in \mathbb {R}$. Consider the recursive sequence with the general term $x_{n+1}=f(x_{n})-d$ and the first element $x_0>0$. If this sequence is decreasing and converges to some limit $a \in A$ then

• $f(x)<x+d$, $d f/d x>1$ where $x \in [a, x_0]$

• $f(a)=a+d$

Let $\varPsi _i$ ($i>0$) be the $i$th interval that has its left endpoint in the unstable interval $\varGamma _L$ and its right endpoint in the critical interval $\varGamma _R$. Assume that $i>1$ and $|\varPhi (\varPsi _i)|<|\varPsi _i|$. According to Observation 5, an unstable interval does not appear in its image while an R-type interval does appear in its image. See Fig. 6b. Considering the identity function and the image of $\varPsi _{i-1}$, it can be observed that $|\varPsi _i| \le |\varPhi (\varPsi _{i-1})|=\varPhi ^*_U(U(\varPsi _{i-1}))-\varPhi ^*_L(L(\varPsi _{i-1}))= |\varPsi _{i-1}|-|\varGamma _L|+\varPsi (U(\varPsi _{i-1}))$ where $\varPsi (\theta )=\varPhi ^*_U(\theta )-\theta$. Therefore, $|\varPsi _i| \le \varPhi ^*_U(U(\varPsi _{i-1}))-(|\varGamma _L|-L(\varPsi _{i-1}))$. Note that $|\varGamma _L|-L(\varPsi _{i-1})$ is a constant. According to Lemma 12 the smallest possible final orientation set can be obtained after a finite number of iterations unless the following conditions are met.

• 1. For $\theta \in \varGamma _R$ the graph of $f(\theta )=\theta +(|\varGamma _L|-L(\varPsi _{i-1}))$ lies above the graph of $\varPhi ^*_U$ and $d \varPhi ^*_U / d \theta <1$.

• 2. The graph of $f(\theta )=\theta +(|\varGamma _L|-L(\varPsi _{i-1}))$ intersects $\varPhi ^*_U$ in $\varGamma _R$.

According to Lemma 12, if $\varPsi _i$ satisfies both conditions, then the right endpoint of $\varPsi _i$ gets close to the intersection point of $f(\theta )=\theta +(|\varGamma _L|-L(\varPsi _{i-1}))$ and $\varPhi ^*_U(\theta )$. Therefore, $\lim \limits _{i \rightarrow \infty }|\varPsi _i|=|\theta -L(\varGamma _L)|$ where $\theta$ is an angle such that $\varPhi ^*_U(\theta )=\theta +(|\varGamma _L|-L(\varPsi _{i-1}))$. So the final orientation set can get arbitrarily close to this limit by increasing the number of push actions.

Recall that the symmetric case, where $\varGamma _L$ is L-type, is similar. There exist imperfect parts [27] that meet both of the above conditions for some $\varTheta _i$.

6 Conclusion

In order for automated planning algorithms for part handling tasks to be useful in practice it is important that these algorithms are capable of dealing with the inevitable shape variations of real industrial parts. The few papers that do not assume perfect parts generally assume a very restrictive model for shape variations, and often only determine how big these variations must be to invalidate a solution that was computed based on the perfect model part. In this paper, we have considered a more general model for shape variations and studied its effects on orienting parts by pushing . We have proposed an algorithm that takes into account these variations during planning and as such outputs a plan that simultaneously orients all instances satisfying the model into the smallest possible interval of orientations after a given number of push actions. We have also investigated the conditions for which the part cannot obtain the smallest final orientation set after finite number of push actions.

The set of possible orientations of an imperfect part can consists of several disjoint intervals. In this paper, we have focused on finding the smallest interval that contains all these subintervals. A different version of the problem would be to minimize the total size of the subintervals. Another extension is to allow for independent variations in the location of the center of mass. It is also interesting to explore which parameters affect the length of the final orientation interval; examples of such parameters are the width of the tolerance zone and the eccentricity of the part.