FixtureNet: Interactive Computer Aided Design via the WWW

Rick Wagner (USC), Giuseppe Castanotto (USC, visiting), and Ken Goldberg (UC Berkeley)
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.

Abstract

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://memento.ieor.berkeley.edu/fixture

Motivation

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.

Related Work

Commercially available "modular fixturing" systems typically include a square lattice of tapped and doweled holes with precise spacing and an assortment of precision locating and clamping elements that can be rigidly attached to the lattice using hardened bushings or expanding mandrels. Ordinarily, human expertise is required to synthesize a suitable arrangement of these elements to hold a given part (E. G. Hoffman. Modular Fixturing 1987 [5]). Besides being time consuming, if the set of alternatives is not systematically explored, the designer may fail to find an acceptable fixture or may settle upon a sub-optimal fixture. Our fixture design algorithm often generates counter-intuitive solutions that may be overlooked by even an experienced machinist, much as chess machines can play moves that look naive at first glance but lead the experienced chess player to explore new variations.

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.

Form Closure

Reuleaux (F. Reuleaux 1963 [9]) in "The Kinematics of Machinery" first described form closure which captures the intuitive requirement of a fixture: a part is held in form closure if it can resist arbitrary forces and torques. Lakshminarayana (K. Lakshminarayana 1978 [5]) showed that seven frictionless contacts are necessary to hold a 3D part in form closure; Mishra (Bud Mishra 1987 [7]) showed that seven frictionless contacts are also sufficient.

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.

Modular Fixturing

Hoffman's text (E. G. Hoffman 1987 [5]) provides an overview of conventional practice with modular fixtures. Research on Modular Fixturing includes basic questions about the existence of solutions (Y. Zhuang, K. Goldberg, and Y. C. Wong 1994 [15]), practical extensions to 3D (Wagner, Zhuang, and Goldberg 1995 [10]) and the problem of fixture loading (Kyeonah Yu and Ken Goldberg 1995 [14]). We are also studying how the model can be extended to curved parts (Aaron S. Wallack and John F. Canny 1994 [12]).

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.

Related Web Sites

Related Web sites include the following. All of these can be reached from our FixtureNet "Related Links" page:
 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/

The Modular Fixturing Algorithm

Brost and Goldberg (Randy Brost and Ken Goldberg 1994 [2]) considered a class of modular fixtures that prevent a part from translating and rotating in the plane based on three round locators, each centered on a lattice point, and one translating clamp that must be attached to the lattice via a pair of unit-spaced holes, thus allowing contact at a variable distance along the principle axes of the lattice (see Figure 1). Brost and Goldberg gave an algorithm that accepts part geometry as input and synthesizes the possibly empty set of all fixture designs in this class that achieve form closure for the given part. If the part has n edges and its maximal diameter (in units of lattice spacing) is d, the algorithm runs in time O(n5d5). The paper describes extensive experiments run on a Lisp machine. This is the first fixture synthesis algorithm that is complete in the sense that it guarantees to find an admissible fixture if one exists.

Quality Metric

The FixtureNet algorithm is complete in the sense that it will find all solutions to a fixturing problem if any exist and report failure if no solutions exist. FixtureNet often finds a large number of solutions. The user generally cares only about a subset of the best solutions. The issue of measuring the quality of a fixture is a research topic in its own right. FixtureNet provides two very different quality metrics, a default metric that minimizes part interface reactions under a "general" load, and an optional metric that minimizes locator interface reactions for a fixed clamp load. The "best" fixtures selected under these two metrics are usually quite different sets.

FixtureNet Interface

Recently, we developed a WWW server to provide modular fixture design alternatives to engineering users around the world. We refer to this service as FixtureNet. The first version is based on the Brost-Goldberg algorithm as described above; subsequent versions will incorporate the 3D extensions described in (Rick Wagner, Yan Zhuang, and Ken Goldberg 1995 [10]).

We invite readers to test the software by going to the FixtureNet home page:

http://memento.ieor.berkeley.edu/fixture/
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).

Implementation

Architecture

The FixtureNet system architecture is shown below in Figure 8 and is also illustrated on-line. FixtureNet involves two machines connected via an Ethernet local area network (LAN). The LAN is in turn connected via the USC gateway to the Internet. Machine A (host Teaser in Figure 8) runs the Brost-Goldberg algorithm. It is a dedicated 486DX 25 Mhz PC (ISA, industry standard architecture) running the Microsoft Windows 3.1 environment on MS-DOS. Machine B (host Memento in Figure 8) is a WWW server and uses custom cgi-bin routines to send requests to the fixture server running on Machine A. Machine B is a 90 Mhz Pentium PC (ISA, industry standard architecture) running the Linux operating system. Machine A communicates with B via Ethernet using the TCP/IP protocol.

Figure 5: Time estimate generation considers current CPU load on the host machine.

The user accesses the Memento 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.

Usage Statistics

FixtureNet was first operational and publicly available in July of 1995. Some problems were identified at that time and remedied in August. Incremental improvements were incorporated through November, and usage statistics were compiled starting December 16, 1995. FixtureNet has been publicly available continuously since then. From December 16, 1995 to March 31, 1996, the FixtureNet usage statistics are: 
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.

Discussion

As a feasibility study, we believe FixtureNet offers a glimpse of the future 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.

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.

Future Work

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.

Acknowledgments

We thank Steven Gentner and Jeff Wiegley (graduate students at USC) for their generous assistance with the details of the WWW, Linux, sockets, and .gif images. Steven was instrumental in getting over some initial rough spots and it was with Jeff's continued prodding that we arrived at a satisfactory socket communication architecture. We also thank George Bekey and Ari Requicha (professors at USC) for their advice and discussions on modular fixturing.

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.

References

  1. H. Asada and Andre B. By. "Kinematic Analysis of Workpart Fixturing for Flexible Assembly with Automatically Reconfigurable Fixtures," IEEE Journal of Robotics and Automation, RA-1(2), June 1985.
  2. Randy Brost and Ken Goldberg. "A Complete Algorithm for Synthesizing Modular Fixtures for Polygonal Parts," International Conference on Robotics and Automation, IEEE, May 1994.
  3. Frits L. Engel and Reinder Haakma. "Expectations and Feedback in User-System Communication," International Journal of Man-Machine Studies, 1993 volume 39, p. 427-452,.
  4. A. J. Goldman and A. W. Tucker. Polyhedral Convex Cones, Princeton University Press, Princeton, N. J., 1956.
  5. E. G. Hoffman. Modular Fixturing, Manufacturing Technology Press, Lake Geneva, Wisconsin, 1987.
  6. K. Lakshminarayana. "The Mechanics of Form Closure," Technical Report 78-DET-32, ASME, 1978.
  7. Bud Mishra, J. T. Schwartz, and M. Sharir. "On the Existence and Synthesis of Multifinger Positive Grips," Algorithmica, 2(4):641-558, 1987.
  8. Jean Ponce, Joel Burdick, and Elon Rimon, "Computing the Immobilizing Three-Finger Grasps of Planar Objects," (draft) 1995.
  9. F. Reuleaux. The Kinematics of Machinery. Macmilly and Company, 1876. Republished by Dover in 1963.
  10. Rick Wagner, Yan Zhuang, and Ken Goldberg. "Fixturing Faceted Parts with Seven Modular Struts," International Symposium on Automation and Task Planning, IEEE, 1995.
  11. Aaron S. Wallack and John F. Canny. "Planning for Modular and Hybrid Fixtures," International Conference on Robotics and Automation, IEEE, May 1994.
  12. Aaron Samuel Wallack. Algorithms and Techniques for Manufacturing, Ph.D. Dissertation, 1995.
  13. J. D. Wolter and J. C. Trinkle. "Automatic Selection of Fixture Points for Frictionless Assemblies," IEEE Transactions on Robotics and Automation, 1994.
  14. Kyeonah Yu and Ken Goldberg. "Loading Planar Fixtures in the Presence of Uncertainty. International Symposium on Assembly and Task Planning, ISATP Proceedings August 1995.
  15. Y. Zhuang, K. Goldberg, and Y. C. Wong. "On the Existence of Modular Fixtures," IEEE International Conference on Robotics and Automation, pages 543-549, San Diego, CA, May, 1994.
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.