In this section we review related research on parts feeders and autonomous manipulation. An excellent introduction to mechanical parts feeders can be found in [1]. The vibratory bowl feeder is the most common mechanism for feeding industrial parts. The bowl has a helical track climbing the inside wall. By giving the bowl a circular vibratory motion, parts dumped into the bowl will climb the helical track in single file. As parts climb the track, they encounter a sequence of obstacles which either re-orient the parts, or deflect disoriented parts back into the center of the bowl. Boothroyd, Poli and Murch describe vibratory bowl feeders in detail as well as non-vibratory feeders such as magnetic and revolving hook feeders. They note that the feedrate for a parts feeder is related to the probability that parts are aligned correctly when they encounter a mechanical filter and give probabilistic models for the orientation of rectangular and cylindrical parts dropped at random.
Vibratory bowl feeders are not very flexible. For each part, the obstacles are designed by trial-and-error. This process can require months. Singer [18] identified criteria for a parts feeder that included changeover time for new parts, ability to handle a wide variety of parts, and feedrate. He proposed several designs for programmable parts feeders including one that used impact and another that used programmed vibration to actively excite parts into a stable orientation [19].
A parts feeding mechanism marketed by the SONY Corporation [7] is also based on programmed vibration. This mechanism uses an array of nests (silhouette traps) cut into a vibrating plate. The nests and the vibratory motion are designed so that the part will remain in the nest only in a particular orientation. By tilting the plate and letting parts flow across it, the nests eventually fill up with parts in the desired orientation. Although the vibratory motion is under software control, some trial-and-error is required to tune the nests and vibratory motion for each new shape.
Sensors can also be used to feed parts. For example, Suzuki and Kohno [20] used a binary vision system to sense the orientation of a part and an actuator to mechanically reorient the part with an actuator. Sensor-based parts feeders are generally more costly than open-loop mechanisms because they require the sensor to be integrated with the mechanical actuator.
Converting part geometry into a parts feeding program is an example of motion planning in the presence of uncertainty; that is, we need a plan to move a part but we are uncertain about the part's initial orientation. A geometric theory for planning with uncertainty was outlined by Lozano-Perez, Taylor, and Mason [10]. The fundamental idea is that planning can be transformed into a geometric problem in a state (configuration) space, where robot actions correspond to mappings and mechanical properties such as stability, friction, and kinematic constraints are related to geometric conditions. The geometric theory has been further explored over the past six years; see [9][3] for reviews.
Manipulation plans depend on the underlying mechanics. Mason [12] explored the mechanics of pushing. Mani and Wilson [11] used Mason's results and a heuristic planner to orient parts with a sequence of pushing actions. Peshkin and Sanderson [17] considered the problem of designing an arrangement of planar ``fences'' such that polygonal parts on a conveyor belt are oriented as they slide along the fences. Brost [2] developed one-step grasping plans to eliminate bounded uncertainty in the orientation of polygonal parts. Erdmann and Mason [5] developed multi-step plans to orient parts using a sequence of tray-tilting actions. Multi-step planners were also considered by Mason, Taylor, and Goldberg [14][21] for orienting parts using a sequence of grasps with a parallel-jaw gripper. Although each of the planning algorithms described in this paragraph use realistic models of mechanics, none are guaranteed to find a plan in polynomial time.
Natarajan [15] ignored the mechanics of parts feeders and
focussed on the abstract problem of planning with a given set of transfer
functions. Citing a result by [8] as evidence that solving
the problem for an arbitrary set of transfer functions is PSPACE-Complete,
Natarajan developed a polynomial-time planning algorithm for the class of
monotonic transfer functions. A function is monotonic if the
states have a cyclic ordering:
and the sequence
also has cyclic
order. Recently, Eppstein [4] reported an
algorithm for this problem where
is the number of states and
is the
number of transfer functions.
Combining the mechanical analysis of previous research with recent
computational results, we identify a a class of monotonic transfer
functions related to the mechanics of a parallel-jaw gripper. There are
unique transfer functions corresponding to each polygonal part.
Thus Eppstein's algorithm could be used to find a plan for an
-sided polygonal part in time
. We present a geometric planning
algorithm that finds a plan in time
.