Flexible parts feeding techniques have recently begun to gain industry acceptance. However, one barrier to effective flexible feeding solutions is a lack of knowledge of the underlying dynamics at work in flexible part feeders. This paper begins to address this topic. First, we discuss statistical modeling of the feeders' sub-systems and the fed parts themselves. For each feeding situation, we construct a generalized semi-Markov process (GSMP) model of the system that is built from these constituent models. Such models allow for a compact description of the complete feeder system and are amenable to high-level simulation and analysis. They can be used to answer questions regarding: the overall system throughput for a variety of parts, control strategies that may be employed to maximize throughput, and the trade-offs between different physical designs of the feeder versus the class of parts being fed. The paper closes with a discussion of future work that is required to mature our understanding of the control and modeling of flexible feeders.

1. Introduction

Automated manufacturing needs are changing from large-volume, single-product runs to small-size, customer-specific lots. There is also a continuing pressure for higher quality, lower cost, and shorter design cycles. The answer is flexible, reconfigurable automation that can produce a wide variety of products and allow the rapid introduction of new products. Crucial to this is the ability to quickly and economically feed parts.

As the concepts of flexible manufacturing systems continue to be accepted in manufacturing facilities, flexible feeding systems will be employed in greater numbers. Currently, a number of flexible feeders have been brought to market [ 1, 2, 3, 4 ] or patented [ 5, 6, 7, 8, 9 ]. It is, therefore, becoming increasingly important to thoroughly understand the flexible feeding process such that it may be utilized to its fullest.

Some initial research has been performed in the area of feeder simulation. For example, several papers [ 10, 11, 12 ] have discussed methods of static and dynamic simulation of tumbling parts. The results are the percentage of parts which will rest in an orientation required for retrieval and assembly. Goldberg and Gudmundsson [ 13 ] have examined the optimal conveyor speed setting for use in an Adept FlexFeeder by using a 2-D model of the physical system coupled with a statistical (Poisson process) model of the part arrivals. Lastly, Goldberg et al. [ 14 ] estimate feeder throughput using conveyor and robot speed and the probability of stable parts poses.

This paper introduces modeling of the complete feeder system based on the statistical probabilities of the feeder sub-systems and on the probabilities of parts resting in usable orientations. By building the model as a high-level statistical equivalent of the physical system, an effective tool for examining the complete system is realized. To construct such a model, however, the underlying properties of the system must be known. While currently obtained from empirical testing, as described in Section 2 and 3 of this paper, it may be possible to acquire such parameters from the lower-level modeling and simulation techniques reviewed previously.

The CWRU flexible parts feeder was used for the testing and modeling presented here. The feeder, shown schematically in Figure 1, has been described in previous publications [ 15, 16, 17, 18 ]. It uses an inclined conveyor to lift parts from a bulk hopper, a horizontal conveyor presents quasi-singulated parts to the robot at a underlit vision window, and a third conveyor to return unused parts to the hopper. An Adept550 robot is used to retrieve parts from the vision window. For testing, retrieved parts were simply dropped on the return conveyor for refeeding so that extended runs of data could be acquired without reloading the bulk hopper.

The paper is organized as follows. In Section 2, we discuss statistical properties of the overall system, its subsystems, and the parts retrieved. In Section 3, we show how to combine this data into a generalized semi-Markov process (GSMP) model of the entire flexible feeder system. We also show some simulations using this model and compare its output to the actual data described in Section 2. Section 4 presents conclusions of the foregoing. We end with Section 5, which touches on future directions.

2. Statistical Distributions for Parts and Sub-Systems

As described in Section 3, the modeling of the flexible feeder requires knowing the statistical properties of the feeder sub-systems as well as the statistical properties of parts resting in usable orientations. First a review of our metric to describe flexible feeders is presented. Next, the statistical distributions that describe the feeder sub-systems are reviewed and lastly, the probabilities that the system will transition between each of its states is examined.

2.1. Feeder Metric

As presented in [ 17, 18 ], a metric for describing the throughput of a flexible feeder in terms of the feeder sub-systems has been developed. This metric describes the throughput of a feeder in terms of its component sub-systems: the parts presentation mechanism (in our case, a series of conveyors), the vision system, and the part removal system (here, a robot). The combination of these three quantities yields the overall system throughput. The statistical distribution that describes each sub-system can then be determined independently.

2.2. Statistical Distributions

[ 17 ] and [ 18 ] discuss the distributions that model the sub-systems of the feeder (including graphs showing the fits of the data to the specified distributions), which are summarized here. The Overall System throughput may be modeled by a Poisson process (an exponential distribution) shifted from 0 by the minimum vision processing and part retrieval times. The Conveyor Sub-system is unique in that its data is very discrete. It takes a repeatable amount of time to advance the conveyor, therefore the possible move intervals can only be combinations of those times. Again, a Poisson process fit the data well. The Vision Sub-system is unique in that there is a minimum process time (for an empty window), to which is added the time required to find a part. Again, as with the overall system, a time-shifted Poisson process fit the data well. The Part Manipulator (robot), in contrast to the other sub-systems, was well modeled by a normal distribution. Figure 2 shows a cumulative distribution function of each case; the respective parameters are reported in Section 3.2.

2.3. System Transition Probabilities

As shown in the following section (Section 3), another property required for the modeling of the feeder is the probability of the system going to another state given its current state. For example, if the feeder just took a picture with the intention of finding a part, What is the probability that a particular part (or no part at all) was found? To determine this information, the system was tested for an extended period in which data was collected describing each state the system went through. From this data, the probabilities were determined. [ 17 ] and [ 18 ] have shown that, in certain cases, the probability of finding a particular part (when feeding multiple parts at once) is related to the statically stable poses of each part. Hence, future work may provide a way of determining these transition probabilities using one of the static or dynamic simulation techniques cited in the introduction.

3. Modeling of a Flexible Parts Feeder

The aim of this section is to formally model flexible parts feeding systems. This is an important step in the overall understanding of flexible feeders in that it allows a base of knowledge to be established. This base can then be used as a foundation for the development of ``a science of flexible feeding'' as discussed above.

We decided to create a GSMP model of the entire feeder system; such models are natural since they have been widely used in the analysis of queuing systems, which commonly arise in a variety of manufacturing applications [ 19 ]. This is not surprising, since the feeder itself can be viewed as a tiny factory: parts arrive from the hopper, are queued by the conveyor, and processed by the vision system and robot. For our purposes, a GSMP can be thought of as a finite set of states, S, with |S|=n; an n by n matrix of transition probabilities, P={p_ij}, where p_ij is the probability of transitioning to state j given that the system is in state i; a set of n probability distributions, f_i, representing the dwell time of the system in state i. The dynamics of such a system are as follows. Suppose that the system starts in state q. Then choose a dwell time, t_q, from the distribution f_q. At time t_q, transition to a new state r with probability p_qr. From there, pick a dwell time according to the distribution f_r, etc.

The states of a GSMP model can be chosen using engineering insight. Typically, our states will denote conveyor advances, vision processing times, and the grasp times for various types of parts. The transition probabilities between states and the distributions of dwell times within states can be estimated from empirical data. Some examples are computed below. Once a model is constructed, it can be simulated as described above, to generate sample sequences of states and dwell times that are consistent with the statistics of the original underlying data. We also show examples of this below. Such simulations can be used to examine properties of the system that may be expensive­or impossible­to simulate in actuality (e.g., one can examine the effects of replacing the robot with one that is 20% faster). Finally, such models can be examined analytically in order to compute the means of certain variables. For instance, one could estimate the mean time until a certain collection of parts (necessary for some sub-assembly) could be fed by the system. See [ 19 ] for details on analysis of GSMPs.

3.1. Physical Test Cases

To test the validity of our system modeling method, two experimental test runs of the feeder were used.

In the first test, a single part was fed for an extended period while data was collected. The test part was a flat plastic disk approximately 21/4'' in diameter by 1/8'' thick (Figure 3).

The system was run for approximately 5 hours with 3000 parts fed. The data was analyzed and then plotted to show the throughput of the feeder and its sub-systems over the test run. Figure 4 shows the results. Table 1 lists the average and standard deviation of throughput for the feeder and its sub-systems.

The second test fed a mixture of hex nuts and plastic sockets (Figure 3). Again, the throughput of the feeder and its sub-systems were plotted over the test run (which lasted approximately 30 hours). Table 2 shows the average and standard deviation of the overall feeder and the feeder sub-systems for this test.

3.2. Modeling

3.2.1. Test 1: Plastic Disks

The model for the plastic disk was a very simple system with three states: one state describing the conveyor system, a second describing the vision system, and a third describing the robot. To compute the dwell times, we used an exponential distribution for the conveyor system (lamda = 0.525), a time-shifted exponential for the vision system (lamda = 0.671, t_o = 0.703), and a normal distribution for the robot (mu = 1.60, sigma = 0.083). Figure 6 shows the layout of the model. The transition probabilities were all set to unity (i.e. if the system had just taken a picture, it always proceeds to the robot state). This simplifies the process, in that it does not accurately reflect the case of multiple pictures / conveyor advances to find a part. However, as shown in [ 18 ], when the system is working in a serial fashion the model is equivalent to the case of multiple pictures / conveyor advances.

After setting up the simulation and running it for a time equal to the length of the physical test, the results accurately described the physical feeder. Figure 8 shows the throughput of the overall feeder and feeder sub-systems for the model. As can be clearly seen, the model and the physical test are very similar. Table 4 shows the average and standard deviation of the throughput for the overall feeder and feeder sub-systems. The results agree quite well with the physical test.

3.2.2. Test 2: Mixed Hex Nuts and Sockets

The second test used a more complicated model for the case of feeding three parts at once in the same feeder (Figure 7). In this case, the vision system served as the central state (this is expected since the vision system ``drives'' the rest of the system, i.e. the vision determines when the conveyor needs to advance and when there is a part available for retrieval). From the vision system state, there are a total of five possible states into which the system may transition: big conveyor advance, small conveyor advance, retrieve a 3/8'' nut, retrieve a 5/16'' nut, or retrieve a socket. The probability of entering each of the states from the vision state is derived from experimental data. The distributions used and their parameters are described below. The transition probabilities, depicted in Figure 7, are shown in Table 5.

The vision state is modeled by a time-shifted exponential distribution (lambda = 3.38, t_o = 0.11), where the time-shift is the minimum time required to determine that the conveyor is empty. After computing a dwell time in the vision state, the next state is chosen randomly using the previously-listed probabilities.

The next two states represent the conveyor, which is modeled by one of two deterministic values. As discussed in [ 18 ], the conveyor system operates by ``loading'' the horizontal conveyor in one large move and then advances parts into the workcell by smaller motions of only the horizontal conveyor. The two values are then the time for a large move (2.41) and the time for a smaller move (0.45). After every X number of smaller moves (a reprogrammable value), a large move is made. Since this is deterministic, one would only need to keep a count of conveyor advances and return the dwell time of a large move when required. However, here we have decided to simply choose among the moves with a probability equal to their observed occurrence, as reported earlier. As we will see, this simplification does not detract from the model's fidelity in producing realistic throughputs. After a conveyor advance (either large or small), the system returns to the vision state.

The fourth state is the retrieval of a 3/8'' nut. Its dwell time is normally distributed (mu = 1.20, sigma = 0.063), and the system returns to the vision state after part retrieval.

The fifth state is the retrieval of a 5/16'' nut. Its dwell time is also a normal distribution (mu = 1.20, sigma = 0.061). Afterwards, the system returns to the vision state.

The last state is the retrieval of a socket. Again, its dwell time in this state is also normally distributed (mu = 1.28, sigma = 0.128). After retrieving a socket, the system returns to the vision state.

The six distributions are summarized in Table 6.

Together, these data represent a GSMP model of the flexible feeder system feeding three parts. Using it, we may generate sample sequences of states and dwell times and plot, for example, the throughput results. See Figure 10. Comparing this example with actual data [ 17, 18 ], the relative throughputs of the three parts are analogous. Also, the data depicted shows an anti-phasal relationship between the throughputs of the two nuts, as discussed extensively in those two references. Hence, this simple GSMP method models the operation of a flexible parts feeder well.

3.2.3. Test 3: Parts in Order

A third test was conceived in which the three parts of Test 2 must be fed in a particular order. To simulate this situation, a GSMP model of the system, shown in Figure 9, was created. In this model, the same transition probabilities and distribution parameters were used as in Test 2. Using these values, the throughput data shown in Table 9 was generated by the simulation. The part throughput had mean 3.14 and standard deviation 0.97.

To test the validity of this simulation, the system was programmed to retrieve parts in the specified order. Approximately 24 hours of data was recorded and examined. Table 10 shows the results of this test. Part throughput had mean 3.71 and standard deviation 0.53.

Comparing these results shows good agreement between the simulation and the test. The discrepancy is mostly due to the conveyor system. In the physical test, it was noticed that the system would occasionally be starved for sockets. This is because the sockets arrive in ``batches,'' as evidenced by their large relative standard deviation (cf. Table 8). This phenomena is not captured by the simulation and may account for the difference.

4. Conclusions

This paper has presented work which furthers the understanding of the operation of flexible parts feeders. A short discussion of the statistical distributions used to describe the overall feeder and feeder sub-systems was examined. The overall feeder, the vision system, and the conveyor system may be modeled by Poisson or time-shifted Poisson processes, while the robot (parts retrieval mechanism) may be modeled by a normal distribution. The parameters for these distributions are currently determined by empirical testing. In addition, the state transition probabilities were discussed as required for the GSMP model. The transition probabilities are currently determined by empirical testing, although it is expected that in certain cases one may determine them from static stability analyses of part poses.

Lastly, the method of GSMP modeling of the feeder was explained. Two physical test cases were modeled using GSMP. The first case, a single part being fed, was simulated well by the model; the second test, multiple parts fed at once, was also modeled and is consistent with previously reported data [ 17, 18 ]. Lastly, we used a GSMP model to test a case where multiple parts had to be fed in a specified order. Predictions were in good agreement with a subsequent, verifying physical test.

By studying and modeling flexible feeders in this way, we believe that we have made a step toward the ``science of flexible feeding'' that must be crafted so that feeders become more reliable and useful.

5. Future Work

The first area of future work is to more completely model flexible parts feeding systems. Herein, we considered GSMP models of specific feeder set-ups. Already, these can be used to answer questions about system throughput and its variability, make trade-offs among system components, and give insight as to relative loading of each part in the bulk hopper to ensure desired mean overall throughputs. However, we believe that more complicated models (e.g., consider a switched GSMP model in which one dynamically switches among constituent GSMP models) will be necessary in order to fully model all the options which flexible feeders can accommodate.

A second area of future work is the optimization and control of flexible parts feeders. Requisite upon the modeling aim described above, this task provides a means to convert identified models and parameters into design configurations that meet specifications. One can consider two distinct levels of optimization and control: (1) design-level optimization and nominal parameter setting, and (2) on-line parameter tuning and response to events.

In each case, example control inputs include part size, weight, and geometry plus any throughput and throughput variance requirements. The available control variables, however, depend on the level at which control is exercised: design parameters may be varied in a design optimization, while only programmable parameters may be changed in an on-line tuning process. To solve such problems, one can use techniques of optimal hybrid control [ 20 ] that have been developed to solve problems that have a mixed discrete-event and continuous-state character. Several general algorithmic methods for solving such problems already exist, including one based on linear programming [ 21 ].

This work was funded through the Center for Automation and Intelligent Systems Research (CAISR) at Case Western Reserve University by CAMP, Inc.

[1] SonyFA, Advanced Parts Orientating System, T-APOS. Company Product Literature. 560 Route 303 Rangeburg, New York 10962.

[2] Adept Robotics, Adept FlexFeeder 250, Company Product Literature, 150 Rose Orchard Way, San Jose, CA, Sept. 1995.

[3] S. Gordon. Flexible feeding of small parts. Proc. 1996 RIA Flexible Parts Feeding for Automated Handling and Assembly Workshop. Minneapolis, MN, October 1996.

[4] E.M. Ross. Flexible feeding devices for robotic assembly. Proc. 1994 RIA Flexible Parts Feeding for Automated Handling and Assembly Workshop. Cincinnati, OH, October 1994.

[5] T. Nonaka and K. Otsuka. Photoelectric control system for parts orientation. U.S. Patent #4333558. 8 June 1982.

[6] J.L. Goodrich and William L. Devlin. Programmable parts feeder. U.S. Patent #4608646. 26 August 1986.

[7] B.R. Carlisle. Flexible parts feeder. U.S. Patent #5687831. 18 November 1997.

[8] S.J. Gordon. Programmable reconfigurable parts feeder. U.S. Patent #5314055. 24 May 1994.

[9] D. Herndon et al. Robotically controlled component feed mechanism visually monitoring part orientation. U.S. Patent #4909376. 20 March 1990.

[10] B. Mirtich et al. Estimating pose statistics for robotic parts feeders. Proc. IEEE International Conf. Robotics and Automation. Minneapolis, MN, April 1996.

[11] J. Craig. Simulation-based robot cell design in AdeptRapid. Proc. IEEE International Conf. Robotics and Automation. Albuquerque, NM, April 1997.

[12] D. Berkowitz and J. Canny. Designing parts feeders using dynamic simulation. Proc. IEEE International Conf. Robotics and Automation. Minneapolis, MN, April 1996.

[13] D. Gudmundsson and K. Goldberg. Tuning robotic part feeder parameters to maximize throughput. Proc. IEEE International Conf. Robotics and Automation. Albuquerque, NM, April 1997.

[14] K. Goldberg et al. Estimating throughput for a flexible parts feeder. Proc. International Symp. Experimental Robotics. June 1995.

[15] R.D. Quinn et al. Design of an agile manufacturing workcell for light mechanical applications. Proc. IEEE International Conf. Robotics and Automation. Minneapolis, MN, April 1996.

[16] F.L. Merat et al. Advances in agile manufacturing. Proc. IEEE Conf. Robotics and Automation. Albuquerque, NM, April 1997.

[17] G. Causey and R. Quinn. Design of a flexible parts feeding system. Proc. IEEE International Conf. Robotics and Automation. Albuquerque, NM, April 1997.

[18] G.C. Causey. Elements of Agility in Manufacturing. Ph.D. Dissertation, Dept. of Mechanical and Aerospace Engineering , Case Western Reserve University, January 1999.

[19] C.G. Cassandras, Discrete Event Systems: Modeling and Performance Analysis, Richard D. Irwin, Homewood, IL, 1993.

[20] M.S. Branicky, V.S. Borkar, and S.K. Mitter, A unified framework for hybrid control: model and optimal control theory. IEEE Trans. Automatic Control, 43(1):31-45, 1998.

[21] M.S. Branicky and S.K. Mitter. Algorithms for optimal hybrid control. Proc. IEEE Conf. Decision and Control. New Orleans, LA, December 1995.