April 19, 1996
This is an html version of the paper published by the International Journal of Human-Computer Studies, Volume 46, Number 6, June 1997.
The Internet offers tremendous potential for rapid development of mechanical products to meet global competition. In the past several years, a variety geometric algorithms have been developed to evaluate CAD models with respect to manufacturing properties such as feedability, fixturability, assemblability, etc. Unfortunately, most of these algorithms are tailored to a particular CAD system and format and so have not been widely tested by industry. The World Wide Web (WWW) may offer a solution: its simple interface language offers a de facto standard for the exchange of geometric data with industry and research groups (e.g., to encourage verification of algorithms). In this paper we describe a feasibility study for such an interactive system, which can be tested online at:
http://teamster.usc.edu/fixture
The Internet has launched a revolution in the means of worldwide data transfer. WWW browsers such as Netscape have opened up new avenues in information and resource sharing. This has fueled the emergence of many commercial services and products that are marketed and accessed over the Net. This technology also offers potential for the design and manufacture of new products. For examples, see Enterprise Integration Technologies, Inc., Stanford's ACORN Project, and Autodesk's Mechanical Library:
http://acorn.eit.com/acorn-info.html http://www.autodesk.com/products/datapub/mechlibr/mechlib.htm
Digital communication over the Internet offers advantages in terms of speed, efficiency and automation. Fortunately, new geometric algorithms for design, simulation, and manufacture have been developed and reported in the research literature. Unfortunately, the impact of these advances on the manufacturing community has been limited despite a well documented need for improved communication during product development. At the same time researchers rarely have access to each others algorithms since implementations are difficult to port from one platform to another. In this paper we describe one model for interactive computer aided design (CAD) via the WWW that we believe holds promise for use both in industry (e.g., during the design cycle) and in research (e.g., to encourage verification of results).
Our FixtureNet automated fixture design service utilizes a new algorithm to help designers. Its systematic evaluation of all solutions results in better designs in less time. While we strove to produce an efficient and natural user interface (Frits L. Engel and Reinder Haakma, 1993 [3]), hypertext markup language (HTML) imposed significant design constraints. Our target user interface application was the then state-of-the-art version 1.2 of Netscape. Interactive CAD systems on the WWW require interfaces that:
FixtureNet demonstrates such an interface in the context of modular fixturing. In automated manufacturing, parts undergoing fabrication or assembly operations are often held or supported in fixtures. Fixtures can either be custom designed or assembled from modular fixturing kits. Modular fixtures are amenable to automated design, particularly if the number of modular elemental types is small. Such is the case with the three-locator-and-clamp planar modular fixturing set utilized in (Randy Brost and Ken Goldberg, 1994 [2]). As a feasibility study, we implemented an interactive WWW interface to that modular fixture design algorithm.
Figure 1: The L-shaped bracket, three circular fixture elements (fixels) and a sliding clamp are shown at the left. FixtureNet computes an arrangement of these parts (a fixture), shown in the center. We then constructed the fixture, shown at the right.
Work related to ours includes user interface design, software testing, and CAD. The WWW provides an unprecedented opportunity for a large number of researchers to test experimental computer programs. Often the designers of a research algorithm cannot anticipate the kinds of inputs a variety of users in related disciplines might subject the program to. The automated design of fixtures is a challenging research area. The earliest work in this area is related to the necessary conditions for holding parts (work pieces) securely.
Goldman and Tucker (A. J. Goldman and A. W. Tucker 1956 [3]), in a purely mathematical paper on linear algebra, described the necessary and sufficient conditions for positively spanning an n-dimensional Euclidean space, which coincidentally describes the necessary and sufficient conditions for form closure. Wagner, Zhuang, and Goldberg (1995 [10]) make use of a simplification of that proof in validating an intuitive form closure test.
Asada and By (H. Asada and Andre B. By 1985 [1]) in "Kinematic Analysis of Workpart Fixturing for Flexible Assembly with Automatically Reconfigurable Fixtures" describe an automatic fixture reconfiguration system using a robot manipulator and a CAD system to provide a systematic method for designing fixtures. They also provide an analytic test for form closure and suggest how contact points might be applied, but they did not consider how a restricted set of modular elements could be used to reach those points. They call fixture synthesis "designing a fixture layout," which is in keeping with the mechanical drawing practice of calling a drawing that gives the locations of parts a "layout" drawing. They develop analytic tools for designing fixture layouts using a set of hardware primitives implemented at MIT. They also considered loading and unloading of their fixtures.
Wolter and Trinkle (J. D. Wolter and J. C. Trinkle 1994 [13]) describe a non-modular fixture synthesis that uses analysis of frictionless stability in "Automatic Selection of Fixture Points for Frictionless Assemblies." This is an impressive paper because it applies to both 2D and 3D fixtures, but it is "non-modular" because the fixture points selected are from a continuum in space and not from a discrete set of locations. In their problem, frictionless elements of assemblies need to be held together by a fixture. They analyze fixtures for "stability" in terms of virtual work. Their fixture synthesis algorithm uses a "shotgun" approach: they scatter fixels about the assembly and solve a linear program to minimize contact forces at the fixels by having fixel location on the part boundary be a system variable. Fixels that have reaction forces of zero get discarded. This is an effective approach, but it is not guaranteed to find an optimal solution. Also, it is not applicable to modular fixturing hardware sets as currently available.
Brost and Goldberg (Randy Brost and Ken Goldberg 1994 [2]) have demonstrated a complete algorithm for synthesizing 2D fixtures that forms the basis of FixtureNet Since that paper appeared, other papers regarding planar modular fixturing have appeared, including "Planning for Modular and Hybrid Fixtures" by Wallack and Canny (Aaron S. Wallack and John F. Canny 1994 [11]), which describes a vise-like fixture with four cylindrical locators. Clamping motion is provided by a translating lattice, and they give a complete algorithm to evaluate all possible configurations.
Until recently there have been few papers describing modular fixture synthesis algorithms in 3D. However, Wagner, Yzhuang, and Goldberg have described a new modular strut hardware set and a complete algorithm for automated fixture synthesis with these primitives in (Rick Wagner, Yan Zhuang, and Ken Goldberg 1995 [10]), also the subject of an extension to Fixture Net in section 6, below.
Recently, Ponce has described "immobilizing" grasps (Jean Ponce, Joel Burdick, and Elon Rimon 1995 [8]), and has proposed their possible application in fixturing in both two and three dimensions. Immobilizing fixtures require only three contact points in the plane and four contacts in three dimensions. The practical application of immobilizing fixtures is somewhat limited, however, in that when they are evaluated in terms of the quality metrics generally applied to form closure fixtures, they will be ranked below fixtures with form closure. This is because an immobilizing fixture generates very large reactions (assuming no friction and rigid parts and fixture elements) with the application of a moment load. Immobilizing fixtures may be a very attractive alternative for light duty applications with friction.
http://www.cs.cmu.edu:80/afs/cs.cmu.edu/user/rajum/www/fix4.html
http://www.geom.umn.edu:80/apps/
http://www.ics.uci.edu/~eppstein/geom.html
http://www.cs.berkeley.edu/~jeffe/compgeom.html
http://www.piaggio.ccii.unipi.it/prova/motion.html
http://www.AutomationNET.com/
We invite readers to test the software by going to the FixtureNet
home page:
http://rjwagner49.com/Robotics/Fixture/fn3/
The home page is shown in Figure 2 and includes a graphical introduction to the algorithm, many examples, and links to related work and papers. It also includes an on-line manual detailing how to use the FixtureNet service (and documentation on the FixtureNet implementation itself, including system architecture, etc.).
Figure 2: The FixtureNet home page.
When the user clicks on the FIXTURE SERVICE link, he or she is given an option for the input data style and then encounters the appropriate form to describe the user's polygonal part, including a graphical interface to permit users to point and click to define parts (using an "ISMAP" that is a feature of the HTML language) (Figure 3). All processing is done on the servers at the USC campus, not on the client machine as with Java applications. The data is then submitted by clicking on a SUBMIT button and the server responds with a line drawing of the user's part (Figure 4).
Figure 3: The user may use the mouse to click vertex points to draw a new part. Here hook-shaped part is nearly completed.
After pressing CONTINUE, the system returns with an estimate of the approximate time required to run the algorithm for the user's part (Figure 5). The time estimate is computed by sampling the server's current CPU processing power (a function of the current load) and evaluating the complexity of the of the computation by analyzing the part size and number of edges. The algorithm currently runs on a 25 Mhz 486 machine with limited (four Mbyte) memory and can require several minutes to compute a set of solutions. One issue is that the system currently permits only one user at a time, hence users must queue and long runtimes can become a problem (see "Future Work," section 7). The HTML server needs to be responsive to the client browser requests to avoid browser time-out, so the server sends back a place holder (teaser), an important innovation in this project.
Figure 4: The input part is shown in relation to the fixel grid (lattice).
After the estimated time, the user presses the CONTINUE button and the server either asks for more time (with an appropriate estimate) or returns images of the user's part in each of the "best" four solutions (Figure 6) (modular fixture configurations) ranked on the basis of a quality metric related to the fixture's ability to resist a combination of forces in the plane of the fixture and moments about a normal to the lattice plane.
The user can also request other solutions and is given an ID number so that he or she can view the solutions anytime within 24 hours (after which the solutions are deleted and must be regenerated).
Figure 5: Time estimate generation considers current CPU load on the host machine.
The user accesses the Teamster HTTP server (a Linux client with respect to the fixture server on Teaser) via the Internet (with Netscape or some other WWW browser application). The ability of the user to describe the part to be fixtured by drawing with the mouse is a convenient feature. The mechanism behind image maps is straightforward: the image that we wish to use (in our case a square where the user can draw his part) consists of an array of picture elements (pixels) and the coordinates that define these points are determined by the local operating system and recorded by the browser application when the user clicks his mouse. When the user selects a point its coordinates are passed to a drawing program (written in the C language). The coordinates are stored for use when the part will be submitted to FixtureNet. The user can also enter the part vertex coordinates manually through the keyboard, he can prepare and send (by FTP) a file listing of the coordinates which the server can read, or he can change and submit default input provided in input text boxes.
Figure 6: If more than zero fixtures are found for the part, FixtureNet offers to display the best four.
We used the Unix Bourne shell script language to build our gateway scripts. These are a powerful feature of Web browser and server interaction: they enable the users to interact with the Web document.
A gateway script is a program that is run on a Web server activated by input from a browser. It is usually a link between the server and some other program running on the system: they are also called CGI (common gateway interface) scripts. The gateway scripts are called by the server based on information from the browser. The URL (uniform resource locator) points to a gateway script in the same way that it points to any other HTML page on a server; when the server receives the request, it notes that the URL points to a script (based on the file location, usually the cgi-bin directory) and executes that script.
The script performs some action based on the input, in our case, simply to call a correspondent C program. After this the script format its result in a manner that the Web server can understand. The Web Server receives the result from the script and passes it back to the browser, which formats and displays it for the user. FixtureNet uses 13 different gateway scripts and 13 correspondent C programs. Each script is a Web server interface to call a C program binary.
Figure 7: The four best solutions (fixture configurations) for the hook-shaped part. The default quality metric is formulated to resist several generic combinations of forces and moments.
When the part is submitted, FixtureNet parses the input in accordance with the input format specification (described for the user on the "explanation") page. If an error is found, a message is returned to the user, otherwise FixtureNet opens network communication with the fixture server on machine A (Teaser) and sends the formatted input part.
Figure 8: The FixtureNet Architecture
After the Linux client sends the fixture server the data describing a polygonal part, the fixture server initiates the fixture design algorithm by spawning a fixture synthesis process which estimates run time based on part size and grid pitch. The estimate is returned to the Linux client, which formats it into an HTML page and returns it to the user.
When the fixture synthesis program completes the design algorithm, it communicates the data via Windows dynamic data exchange (DDE) to the fixture server which relays it to the Linux client in the form of textual descriptions of solutions. Each solution includes the pose (position and orientation in the plane) of the user's part the position of three locators on the lattice, and the position and offset for a clamp such that the part is held in form closure.
The Linux client then runs a custom graphics routine to generate (CompuServe's) graphic interchange format (.gif) images of the part in each of the best four solutions.
Communication via Berkeley sockets is the key to building a cross-platform WWW service of this kind. We used the Windows Socket application programming interface (API), a subset of Berkeley sockets. For rapid development we implemented the algorithm in Visual Basic using a Windows Socket custom control (a precompiled MS Windows dynamic link library (DLL)) from Distinct Corporation.
There are a number of architectures that can be used for communication with sockets and we experimented with several of them before finally settling on using a single client socket in the Linux client and a server socket in the fixture server. We used a 7-bit ASCII string to pass information through the socket connection formatted with an 8-digit service request identifier and a 3-digit type code. The type codes (defined somewhat arbitrarily) and their meanings are shown below in Table 1.
Code Meaning
001 Initial fixture request
009 Get job status
011 Get fixture data
012 Go to next fixture
013 Go to previous fixture
014 Use minimal reaction quality
metric
015 Use 50/50 quality metric
(default)
030 Kill the synthesis process
Table 1: Message codes used in FixtureNet
The Linux client initiates a fixture service request with a socket connect request and an initial fixture request message (code 001) that includes the part data (number of vertices and x-y coordinates of each vertex) and the desired grid pitch (coarse, medium, or fine). When the fixture server receives the request, it responds with a "request acknowledged" string and then spawns an instance of the fixture synthesis program which then generates a time estimate for the job based on the current CPU load and the part parameters. When the Linux client requests job status, the fixture server then relays the fixture synthesis program time estimate and state to the client. While multiple fixture synthesis program instances can be run simultaneously, the throughput of the system will not be increased by doing so. FixtureNet can be easily extended by adding additional server machines.
FixtureNet Statistics Number Requests of FixtureNet service input 66 (keyboard): Requests of FixtureNet service input 111 (drawing): Solution sets delivered: 142 Total fixture configurations computed: 8732
Table 2: FixtureNet Statistics
In many cases (35, 25%), users jump to another page and don't return to request to view the solutions. These solutions are computed, but are not delivered and not captured into the "sets delivered" statistics. A typical run time for a fixture computation is about a minute. The "square" example part takes four seconds.
This model also suggests a new model for evaluating algorithms. Generally those who develop an algorithm are the least qualified to rigorously test it. The Internet provides access to an enormous community of tinkerers who will be more than happy to discover flaws in an algorithm (as recent publicity on Netscape security flaws attests). The Internet is also a great way to disseminate research results to academic colleagues, industrial users, and ultimately to the taxpayers, who support the work directly or indirectly.
It is important to remember that FixtureNet is intended as a feasibility study and not for industrial usage. An industrial implementation will require fixtures built from a larger set of primitives to accommodate industrial practices. The planar modular fixture design algorithm is the first step toward a comprehensive algorithm for fixturing 3D parts.
This model also suggests a new model for design evaluation software, which is often expensive and used in bursts. Rather than maintaining a user license and copy of the software, users can send data and receive results without ever owning the software. This has a number of implications in terms of security and maintainability which are beyond the scope of this paper.
FixtureNet offers a glimpse of the potential of the Internet as a resource for manufacturing and design. We've shown how geometric part descriptions can be input over the Internet and how the WWW can provide remote execution of geometric algorithms and graphical display of results. Remote design evaluation tools for VLSI circuits have been available for years. Planar fixtures are only one type of mechanical design evaluation possible. A variety of WWW sites offering interactive design resources will appear in the coming years.
One shortcoming of the current state of FixtureNet is that the we have only one machine running the fixture synthesis algorithm. FixtureNet can be easily extended to handle multiple requests by sending them to additional servers (machines running MS Windows and the fixture server program). The Linux client would allocate service requests among multiple hosts.
A long range goal is to accept a clean .gif (possibly from a camera) image of the part. We would then extract edges using image processing methods. Another possible extension to FixtureNet is to add 3D solid faceted part fixture synthesis capability. We are seriously considering a new implementation that will provide fixture design services for both 2D (as in the current FixtureNet) and for 3D parts. Java applets may help provide an easier to use interface for the more complicated services of this kind. The drawbacks of Java applets include the transport time for program code (the messages of HTML require little bandwidth) code and reliance on computation resources on the client side, however. Server-push technology may play a role in future developments.
This work was supported in part by the National Science Foundation under Award DDM-9215362 (Strategic Manufacturing Initiative) and by NSF Young Investigator Award IRI-9457523, and by a grant from Cu-Co, Inc., a vendor of modular fixture systems. Part of this research was performed while Goldberg was at the University of Southern California.
About the Authors: Richard Wagner is a Ph.D. student at the University of Southern California's Institute for Robotics and Intelligent Systems (IRIS). Giuseppe Castanotto is visiting USC from the University of Pisa, Italy. Ken Goldberg is a professor of industrial engineering at the University of California at Berkeley. Dr. Goldberg is Mr. Wagner's thesis advisor.
Email Richard dot J dot Wagner at gmail dot com
wcg1-6.html, this file created sometime in 1997, updated November 5, 1997.
Last updated October 19, 2010, by
Rick Wagner. Copyright © 1997-2010, all rights reserved.