TECHNICAL FIELD

This invention relates to interactive operation of computer-controllable machines, and more particularly, a method and system by which a machine user interacts with a programmable system to operate the machine within the limits of a preestablished set of geometric or other constraints. The invention has broad applicability, but one area in which it finds particular utility is in the field of computer operated machine tools. Accordingly, the description of the invention will be in the context of a manufacturing process and system in which a machinist interacts with a programmable system to manufacture a part according to a numerical model.

BACKGROUND ART

Advancements of computer technology have revolutionized many industries, but none more than the design and manufacture of complex parts using machine tools. Designers and draftsmen working on drawing boards to produce designs for execution by skilled machinists have been replaced in many instances by computer-skilled engineers executing parts design and control programs for numerically controlled machine tools.

Generally, the process has been characterized by batch processing in which a "job" or part program is created "off line" and then executed serially in a cued approach at the machine tool system. This yields significant advantages in efficiency, economy and improved quality which can be achieved through the repetitive execution of the part program.

Following the batch processing philosophy, industry efforts have concentrated on developing improvements in computer aided design and manufacturing (CAD/CAM) , off-line

systems for part program generation and increasingly sophisticated computer numeric control (CNC) systems for machine tool motion control. All of these systems have focused on the efficient creation and execution of standardized part program formats, and have increasingly moved control of the machine tool away from the skilled machinist and given it to the CAD/CAM part programmer.

Batch-oriented CNCs are now the industry standard. However, trends are emerging which suggest that manufacturing in the near future will not be centered around such a long-run production strategy. Manufacturers have discovered the advantages of just-in-time and agile manufacturing over batch processing, and have realized cost savings from contracting out short run jobs to small job shops. Many such small shops are springing up in response to the new demand.

Batch processing does not lend itself well to efficient and economical execution of short-run jobs. The time required to plan and program a part on a CNC-controlled machine may be longer than the time consumed during a short production run. In addition, the effects of tool wear, deflection, part placement, and fixturing are impossible to predict accurately before program execution. Moreover, accuracy derived from batch processing with CNC is not available for short-run jobs without considerable setup time. As a consequence, job shops still perform many tasks on manual machines, and industry sources estimate that six times as many manual machines have been sold over the past several years into the market world-wide as CNC machines.

DISCLOSURE OF INVENTION

The present invention seeks to apply the economic and quality improvement advantages of CNC to short-run manufacturing. Generally speaking, the machine tool control method and system according to this invention provide an

interactive computer aided approach to parts manufacture in which a skilled or semi-skilled machinist provides real-time operating commands for the cutting tool, and the control system interprets the operator's commands in relation to a part model to generate the actual cutting instructions. The process, which we call Path-Free Control, differs from existing computerized machine tool technology in that it takes advantage of the best capabilities of human, machine, and computer. By optimizing the relationship between the operator and the computer, both can perform efficiently in their areas of expertise.

Interactive Path-Free Control returns a portion of the machine control to the skilled machinist. It makes the machine tool an extension of the machinist's hands and the CNC an extension of the machinist's knowledge. Using Path-Free Control, the machinist makes the objective or process-step related (high level) decisions which guide the machine toward the overall goal of cutting a precision part. The CNC portion of the system operates as an expert system performing the tasks that computers perform best—high speed calculation, feedback monitoring, and controlling low level, i.e., machine operation responsibilities. This division of labor allows the machinist to focus on the cutting processes while the controller handles part geometry and machine constraints. Path planning time is thus reduced, and the accuracy of a conventionally controlled CNC machine is available to job shops.

Using the Path-Free Control system, the machinist enters the part geometry into the computer and immediately begins cutting the part. Part geometry defines only the finished product, and not the tool path and other commands used to produce it. During the cutting process, the machinist makes decisions as to tool path and cutting tool pattern, cutting sequence, fixturing strategy, feed speeds and cutting depths, and even part finish. The machinist can evaluate the

integrity of the cutting process and other operating conditions in real-time and can modify the machining conditions accordingly. The machinist communicates with the machine interactively using a joy-stick type control device linked to the machine tool's control software.

The Path-Free Control equipment according to this invention is quite economical compared to existing CNC systems whereby small producers can retrofit the new control system on existing manual machine tools and even on machines having exiting proprietary CNCs.

The control system according to this invention may also include the capability for recording the machinist- directed tool path and other operating commands. Accordingly, a cutting program can be generated during the process of machining a prototype.

An interactive system also has the advantage of providing more job opportunities for highly skilled journeyman machinists, currently a decreasing resource of continuing strategic importance. Machinists using such a system will develop and use traditional skills to control the quality of the parts, efficiency of production, and even to help design parts.

In addition, the system will be safer for its operators. By keeping the operator in direct control of the machine but physically removed from the cutting surface, there is less of a chance for an operator to be injured by unexpected programmed actions that may occur with autonomous systems.

Accordingly, it is an object of the present invention to provide a manufacturing method interactively involving a skilled or semi-skilled machinist with a numerical

control system responding to a geometric model of the part to be machined.

It is a related object of this invention to provide a manufacturing method and machine tool control system in which the geometric model defines the configuration of the finished product rather than the tool path which produces it.

It is also an object of this invention to provide a machine tool control system which utilizes the geometric model, input commands and tool position feedback to generate a tool tip trajectory for precision machining in accordance with the part design.

Another object is to provide such a system in which the operating steps performed by the machinists can be recorded for future reuse in totally automated operation.

The above-stated objects may be achieved using a system constructed of specially designed components, or preferably, with a microcomputer based system programmed in accordance with the principles of this invention, and other standard components. Functionally, the system includes the

Path Free Controller itself, a multi-axis motor interface subsystem, a tool position feedback system and an interface unit including data entry means by which a numerical model of the part may be entered into the system, an operator input control unit for directing tool motion and positioning, and a display subsystem which provides a graphic display of the part geometry, the relationship of the cutting tool to the part, progress of the machining process itself and other operating parameters.

An important feature of the Path-Free Control concept is the implementation of real time collision avoidance in the interactive control process. This is facilitated by

a relatively simple algorithm which rapidly locates the tool position in relation to adjacent part surfaces.

If the part configuration being machined is complex, locating the tool tip in relation to one or more part surfaces can be quite time consuming, even with currently available fast processors. According to our invention, we have developed what we call a geometric compiler which significantly reduces computation time. The geometric compiler divides the part model into cells or regions according to a preestablished partitioning scheme. Each cell contains a predetermined maximum number of part boundaries; the data stored for each cell represents the spatial coordinates of these boundaries.

The cell partitioning takes place during system initialization. During the actual machining operation, a cell identifier employs the cell boundary coordinates to identify the cell in which the tool tip is located. Once the tool tip cell is identified, position computations only need to be performed in relation to the part boundaries associated with that particular cell.

The Path Free controller generates collision avoidance control laws from which the tool tip trajectories for the machining process are computed. The permitted tool tip trajectories, or operating modes, as allowed by the control laws, are determined by the instantaneous tool tip position, the surrounding geometry and the operator's apparent intentions as reflected by his or her input commands. The operating modes may be regarded as conceptualizations of all the permitted trajectories, given the tool tip location and surrounding geometry.

The control law data and the operator's input commands are processed by a command execution subsystem which generates direction and magnitude signals for a conventional

multiple axis servo system. The tool tip position feedback loop may be closed by a shaft position or linear encoder or in any other conventional fashion.

If it is desired to provide the capability for recording the sequence of steps performed by machinist for future use in completely automated operation, the system will also include a data acquisition and manipulation module and a playback unit. The actual sequence of commands which constituted the operators tool trajectory are recorded, along with the related position and velocity information, and may be used for direct playback.

Alternatively, the recorded data may be further processed to abstract from it a body of data of the type usually provided as the input to a standard CAM system, which is then used to generate a new optimized part program, rather than the actual recorded tool path. This, in turn is used as the input to the command execution subsystem, or it may be transferred to a standard CNC system for execution. In this way, the operator's real-time experience in cutting the part is utilized, and the resulting part program takes better account of unique real-life conditions associated with the design and manufacture of the part in question.

BRIEF DESCRIPTION OF THE DRAWINGS

The features and objects of this inventions are achieved as explained in the following detailed description, in conjunction with the appended drawing in which:

FIGURE 1 is a simplified block diagram showing the general nature of prior art CNC systems; FIGURE 2 is a simplified flow diagram showing the essential features of the process according to the present invention;

FIGURE 3 is a block diagram showing functional and architectural features of an interactive machine tool control system according to this invention;

FIGURE 4 is a diagram of a part feature which shows cell partitioning as performed according to the present invention;

FIGURE 5 is a flow diagram of a recursive partitioning algorithm employed by the geometric compiler in a preferred embodiment of the present invention; FIGURE 6 is a flow diagram of a cell identification algorithm employed by the controller according to a preferred embodiment of the present invention;

FIGURE 7 is a tree diagram showing the partitioning of the part feature of FIGURE 5 to illustrate the implementation of the cell location algorithm;

FIGURE 8A-8N illustrate the various operating modes available in accordance with a preferred embodiment of the invention;

FIGURES 9A-9C, arranged as illustrated in FIGURE 9D, are a transition diagram demonstrating the implementation of the control law selector;

FIGURE 10 is a sectional view taken along line 10-10 in FIGURE 4 illustrating the collision avoidance process according to this invention; FIGURE 11 is a vector diagram illustrating one mode of operation of the command execution function according to the present invention;

FIGURE 12 is a flow diagram showing an embodiment of the invention which provides record and play back functionality; and

FIGURE 13 is a block diagram showing functional and architectural features of the embodiment of FIGURE 12.

BEST MODE FOR CARRYING OUT THE INVENTION

Referring now to the drawings, FIG. 1 shows in flow diagram form, the essential features of a typical prior art

process for computer aided design and manufacturing using computer controlled machine tool from conception to the production of a physical component.

The first step is part design definition (Step S1A) .

Here, the component is conceptualized according to design criteria which may include shape, form and function.

This conceptualization is then converted to a geometric model, and recorded in machine readable form (Step SIB) . This is typically done using a geometric modeler, such as one of the many commercially available computer aided design (CAD) packages. This step is often performed by a design engineer.

The next step is the development of a manufacturing strategy for the part based on the geometric model (Step SIC) . Typically, this includes modifying the geometric model to take account of the geometry of the cutting tool and limitations on machine motion, fixturing strategies, tolerance requirements and machine tool specifications, and variables that effect the machining process. The augmented description of the component including the machining strategy is then used to generate a tool path program (Step SID) . Typically, this is performed by a manufacturing engineer using commercially available computer aided manufacturing (CAM) software. Frequently, the resulting CNC tool path program, is post processed to translate the CNC program into a series of point to point moves specifying the sequential cutter locations needed to manufacture the component.

The machine tool operator then prepares the machine tool to manufacture the component by loading and fixturing the stock, initializing the machine tool and loading the CNC tool path program (Step S1E) . The tool path program is then executed on the controller which converts the point to point

moves in the program into a series of trajectories used by the servo control loop (Step S1F) .

FIGURE 2 shows a flow diagram of the essential features of a design and manufacturing process utilizing the interactive procedures according to the present invention. Here, the first two steps, definition of the part design (Step S2A) , and definition of the geometric model of the component to be manufactured (Step S2B) , may be performed in accordance with conventional techniques, and do not form a part of this invention.

In contrast to the prior art, however, with the present invention, the geometric model is then used as an input to an interactive control process. Using a suitable input device, the machinist directs the cutting process by conveying real-time process objectives to the machine tool controller, including tool movement commands (Step S2C) . Based on the machinist's input, the geometric model, and tool position feedback from the machine tool (Step S2D) , interactive control/collision avoidance signals are generated (Step S2E) . These are employed to direct cutter motion for actually machining the component in real time (Step S2F) .

The interactive control process according to the present invention allows the operator wide control over the machining process, while at the same time, assuring production of high tolerance parts. In effect, the three inputs (geometric model, operator commands and tool position feedback) are combined to provide collision avoidance between the cutter and the component, allowing the machinist to rest the cutter against the part surface but not to violate its intended final shape.

A detailed description of the interactive control system and method according to one embodiment of the present invention will now be presented in conjunction with FIGURES

3 through 11. In considering this description, it is to be understood that the design of the control hardware emphasizes low-cost implementation to facilitate purchase of complete machine tool systems by small job shops, and to encourage retrofitting on existing manually operated machine tools, and on conventional CNC machines. In furtherance of this principle, conventional microcomputer system architecture, and commercially available components are employed wherever possible in the preferred embodiment. For this reason, and in the interest of brevity, a detailed description of the physical implementation of the system has been omitted; however, the assembly of the necessary hardware and software capable of performing the functions described will be apparent to one skilled in this field from the information presented.

Turning now to FIGURE 3 , there is shown in block diagram form, the important functional features of a preferred embodiment of our invention. As illustrated, the system, generally denoted at 10, includes a suitable system control and coordination unit 12, memory unit 14, a hard disk drive 22, and associated controller 24, a floppy disk drive 26 and associated controller 28, an operator interface subsystem generally denoted at 30, geometric compiler 32, the path-free control subsystem generally denoted at 34, a motor interface subsystem 36, and a tool position feedback subsystem 38.

Hard disk 22 stores a geometric model of the component to be machined. This may be in the form of a database containing the dimensions and other physical characteristics of the part or in any other suitable form. Hard disk 22 also stores other data and application software needed to run the system. Floppy disk drive 26 is used to load the geometric model and operating software in conventional fashion.

User interface 30 provides the means by which the machinist interacts with Path-Free Control subsystem 34. The

interface provides the capability for selecting the controller operating mode as described below, for entering tool setup commands and environmental parameters, and for editing part geometry. Data entry is provided by input devices such as keyboard 48, and mouse 50, or by other suitable devices and is implemented by appropriate data input software. A display device 52 such as a CRT monitor and an associated display generator 54 provide the user a visual display of system operating conditions, prompts for user inputs, and, as explained below, a graphical representation of the part and the progress of the machining process.

Responding to suitable on-screen prompts, the operator uses keyboard 48 and mouse 50 to provide information to path-free controller 34 about parameters such as cutter and fixture geometry, stock location within the machine work space, maximum allowable feed rate, etc. Additional machining information such as which feature of the part is to be machined at a particular time, the intended direction of motion of the cutter, the position of the stock relative to the machine tool's home position, the dimension of the cutter currently loaded in the spindle, etc. may be provided to controller 34 by these means as well.

The data input software is written to provide what we call Flexible Fixturing, and the functions are implemented by fixturing data processor 56. This feature gives the operator freedom to clamp and re-clamp the work piece without concern for clamp or work piece position on the table. Once a work piece is clamped, the machinist can mark regions that contain the clamp by jogging the machine tool cutter to opposite corners of the clamp and recording those positions using keyboard 48 or mouse 50. The geometric model is then updated to include a simplified model of the clamp, for example, in the form of a rectangular box. This is used in the collision avoidance computations performed by Path-Free controller 34 as described below.

If the part is re-clamped at a new location after some phase of the machining process, the operator invokes the flexible fixturing software, and again using keyboard 48 and/or mouse 50, removes the previous clamp location from the part model, and registers the new position. Using this capability, a machinist can reduce setup time and effort while maintaining a high degree of accuracy and operator safety.

The exact manner in which fixturing data processor 56 and its associated software operates to achieve the described functions is dependent on the data format used to generate the geometric model. The details are omitted in the interest of brevity, but will be apparent to those skilled in the art from the description provided.

User interface 30 also includes the means by which the operator enters the cutter movement commands. This function is provided by a joy stick type device 58. In a three dimensional embodiment, the Spaceball ^™ manufactured by Spaceball Technologies, Inc, Lowell, Massachusetts is preferred, but other two or three dimensional input devices may also be used. For a two dimensional system, mouse 50 or even keyboard 48 may be used.

For purposes of discussion, let it be assumed that input device 58 is a force measuring device, and thus provides an output related to how hard the operator pushes on the control mechanism. One or more outputs are provided, representing the resolution of the user's input force vector along orthogonal coordinates.

To put this information into use, we prefer to produce a weighted average of a succession of samples of these vector components. In one embodiment using the spaceball described above, samples are taken approximately 20 times per second. The sampling interval is treated as a measure of the duration of the input force. Each of the vector components

is multiplied by this time value to produce a velocity command to be used by path-free control subsystem 34 as described below.

Best results are achieved if input device 58, in conjunction with the operating software, permits smooth and steady tool motion and easy control of the cutting process. To assure this, Path-Free Control system 34 is designed to move the cutter at a speed which is functionally related to the intensity of the operator's action. In other words, if the operator pushes harder (or further, depending on the input device used) , the tool will move faster. Friction proportional to speed, and feedback to the operator on contact with a surface may also be provided through software implementation as will be obvious from the description provided.

As previously mentioned, the monitoring function is provided by a display generator 54 and display device 52. To insure that the component has been completely machined, display generator 54 creates a part status display in the form of a graphical image showing both the intended part configuration and the portions which remain un-machined at a given time. The display uses color or other attention focusing means, such as a flashing display, to highlight the uncompleted portions of the part.

Information for generating the part status display is derived from the geometric model, and from the tool position data gathered by the tool position feedback subsystem

38 as the part is being machined. The tool position data is used to identify all points on the perimeter of the part with which the cutting tool has come in contact, thereby identifying any unmachined areas. Any suitable software for controlling the display may be used for this purpose.

Additionally, the current machining mode, tool position, feed, speed etc. may be displayed to the machinist. Display generator 54 may also include means to compare the machinist's cutting commands and tool selection with the geometric model, and to identify any areas where the machinist's actions had not fulfilled (or were unable to fulfill) the requirements of the part geometry, for example, by selection of a tool of inappropriate size.

Geometric compiler 32 transforms the part geometry file data, into a segmented model characterized by a plurality of regions or cells. The segmented model is optimized for the real-time collision avoidance computations as described below. By using the segmented model, Path-Free Controller 34 only needs to check surfaces within the vicinity of the tool, when performing the collision avoidance computations. This can significantly decrease computation time.

Path-Free controller 34 includes cell identifier 60 which processes the segmented model produced by geometric compiler 32 to identify the cell in which the tool tip is located at a given time. Controller 34 also includes collision avoidance control law/command selector 62 and tool motion command execution processor 64.

The strategy for implementing geometric compiler 32 may be understood with reference to FIGS. 4 and 5. Assume, for example, as shown in the Figure 4, that the part to be machined, generally denoted at 78, includes a pocket 80, the walls of which are defined by straight-line segments W1-W5, arc segments Al and A2 , and a cylindrical island 82 defined by arc segments A3 and A4 within pocket 80. To simplify the explanation, assume that the boundaries of pocket 80 have been contracted (and those of island 82 have been expanded) by a distance equal to the tool radius so the tool may be regarded as having zero diameter.

We have found that several different partitioning rules may be employed, but the preferred one is as follows:

(a) The area that contains the features to be partitioned is assumed to be rectangular and is divided in half by defining a boundary which perpendicularly bisects its longest side;

(b) The regions to the left and right (or above and below) of the boundary are treated separately. In each region, the number of wall segments (either arcs or straight lines) is counted. If the number is less than or equal to a pre-determined maximum number n, the area is defined as a cell;

(c) if the number of wall segments exceeds the pre-determined maximum n, the dividing process is repeated until no areas have more than n wall segments.

Step (b) above may be modified slightly if desired to take account of the possibility of a part wall segment being close to a cell boundary. This involves a predetermined small parallel displacement of the dividing line (e.g., about 0.32 mm) to expand the region before the part wall segments are counted. Both regions are expanded in this way so a part wall segment close to the dividing line is counted in both regions. The result will be a slightly overlapping cell structure with wall segments that are close to cell boundaries being counted in adjacent cells. This will prevent the tool from encountering an unexpected part boundary immediately upon crossing into a new cell.

As will be appreciated, the smaller the number of part wall segments required to define a cell, the larger will be the number of cells required to partition the geometric model. For a small value of n, the search time to identify

the cell in which the tool tip is located may take longer, but the actual tool-tip-to-part-boundary computations will require less time. Since these computations are performed more frequently, a small value for n is preferred. Generally, good results are achieved if n is selected to be three or four.

A flow diagram of a recursive algorithm for the partitioning process described above is shown in FIG. 5. For purposes of explanation, assume (as in the preferred embodiment) that the dimensions of the geometric model are represented by x, y, and z coordinates of each part feature, in this case, the end points of the wall segments defining pocket 80 and cylinder 82 (see FIG. 4) .

The process begins at Step S5A by loading the coordinates of the wall segment representing the part (or part feature) to be segmented. The number of wall segments is then counted (Step S5B.) This may be done, for example, using a conventional clipping algorithm, modified in a manner which will be obvious to one skilled in the computer arts to count, rather than clip. Algorithms suitable for this purpose include the Cohen-Sutherland Algorithm, or the Liang-Barsky Line Algorithm as described in Computer Graphics by Donald Hearn and M. Pauline Baker, published 1986 by Prentice-Hall, Inc., Englewood Cliffs, NY, 1986.

If the number counted is <n, the pre-selected acceptable maximum, a cell has been identified, and its coordinates are recorded (Step S5C) .

If the total number of segments counted is >n, the process continues. At Step S5D, a rectangle is defined which contains the part (or feature) , and its longest dimension is identified. If the length exceeds the height, the process branches to Step S5E. If the length is not greater than the height, the process branches to Step S5F.

In Step S5E, a boundary is defined which bisects the longest wall of the rectangle to create a rectangle representing the right of the boundary (AREA_RIGHT, Step S5E- 1) and a rectangle representing the area to the left of the boundary (AREA_LEFT, Step S5E2). Preserving AREA-LEFT for future examination, the process returns to Step S5A. AREA RIGHT is now examined to determine its number of wall segments. (If desired, as described above, the boundary may be displaced to the left before the count is made.) If the number is <n, the region under examination is a cell, and its coordinates are recorded (Step S5C) . If the number of segments is >n, the process continues to Step S5D and the length-height examination is repeated.

If the length is again greater than the height, the process returns to Step S5E; otherwise, it proceeds to Step S5F. In either case, one of the two resulting regions is again put aside for future processing and the process returns to Step S5A. The process is repeated (with the cell boundaries being displaced, if desired) until all regions have been identified as cells, and none remain to be examined.

Referring again to FIG. 4, the partitioning process for part 78 will now be illustrated, assuming that n=3. Since the length of the rectangle that contains pocket 80 is greater than its width, Step S5D (FIG. 5) dictates that the pocket first be partitioned vertically. A line LI is therefore defined which partitions the rectangle into left and right regions. If the tool happens to be to the right of line LI, or if preferred, to the right of expanded boundary line LI', FIG. 4 shows that we need to be concerned with its distance from only the three straight-line segments, Wl, W2, and W3. This meets our criterion for cell definition (FIG. 5, Step S5B) . The right half of the rectangle therefore constitutes a cell, denoted 80a.

However, if the tool is to the left of line LI, (or if preferred, to the left of expanded boundary line LI") , Step S5B reveals that we must be concerned with its position relative to eight wall segments (i.e., all but W2). Thus, the geometry on the left side of Ll must be partitioned further. Since the region to the left of line Ll is taller than it is wide, Step S5D dictates that we divide it in half horizontally. A line L2 is therefore defined which partitions the rectangle into upper and lower regions. The number of segments located in each region is counted again and the partitioning continues until all regions contain no more than 3 wall segments. The result of this process is the definition of a series of cells 80a-80g, as shown in FIG. 4.

If it is necessary to create a cell structure based on the outer boundaries of the part, the process described above may be performed by treating the part itself as an island within a pocket whose dimensions are large compared to the part itself.

Referring again to FIG. 3, the data produced by geometric compiler 32 is used by cell identifier 60 to rapidly determine the cell in which the tool tip is located during a particular computation cycle. The process is performed using a recursive search algorithm similar to the partitioning algorithm described above.

With reference to FIG. 6, assume that the tool tip is located at some point having coordinates x _t ,y _t . For convenient utilization by cell identifier 60, the data produced by geometric compiler 32 is stored in the form of a tree structure. The tree structure corresponding to the configuration illustrated in FIG. 4 is shown in FIG. 7. As illustrated, the tree consists of series of branching nodes 84, and a second series of cell nodes 86. Branching nodes contain information as to the partitioning rule for the area under examination, while cell nodes contain the coordinates of the wall segments in the cell. Again, if the cell

boundaries have been enlarged to define overlapping cells, the coordinates of a particular wall segment may be included in more than one cell.

The objective of the algorithm illustrated in FIG.

6 is to identify the cell containing point x _t ,y _t .

The search starts with the original rectangle 80 and p=(x _t ,y _t ) at Step S6A. At Step S6B, the data associated with node 84a is examined. Since rectangle 80 is not a cell, node 84a contains a partitioning rule, and the execution of the program goes down to step S6D. Now, because in our case, the length of the original rectangle is greater than its height, the execution goes to Step S6H. To test if p is to the right of dividing line Ll, the algorithm only needs to compare x _t with XI, the x coordinate of Ll. If x _t >Xl, corresponding to node 86A in FIG. 7, the execution goes to Step S6I, with AREA_RIGHT corresponding to rectangle 80a.

Since the algorithm is recursive, we return to Step

S6A again (with (area) being rectangle 80a. Step S6B then reveals that node 86a contains coordinates rather than a partitioning rule. This reveals that the tool is in a cell, and the process transfers to the END state, Step S6C.

If x _t <Xl, the process goes to Step S6D, which examines the data stored at node 84b to see if it contains a horizontal or vertical partitioning rule. Here, the system finds a horizontal partitioning rule, so the process branches to Step S6E.

Here, y _t is compared to Y2, the y-coordinate of partitioning line L2. If y _t <Y2, the process branches to Step S6F and examines the bottom of the area (corresponding to node 84c in FIG. 7 or if y _t ≥Y2 , the process branches to Step S6G and examines the top of the area (corresponding to node 84d in FIG. 7) . From either Step S6F or S6G, the process returns

to Step S6A and the process is repeated. As will be appreciated, neither of nodes 84c nor 84d in FIG. 7 corresponds to a cell, so in both instances, the partitioning rule must again be examined (FIG. 6, Step S6D.) In both cases, a vertical partitioning rule is encountered, and the process goes from Step S6D to Step S6H. Taking node

84c as an example, if x _t <X3 , the X coordinate of dividing line L3, Step S6B reveals that the tool tip is within cell 80e (FIG. 7, node 86e) , and the process ends, Step S6C. If x _t >X3, corresponding to node 84f, the process continues again to S6D, where a horizontal partitioning rule is encountered. Here, the coordinate y _t is compared with the coordinate Y4 of line L4. If y _t ≥Y4, Step S6B reveals that the tool tip is located in cell 80f (corresponding to node 86f in FIG. 7) . Conversely, if y _t <Y4 , Step S6B reveals that the tool tip is in cell 80g (FIG. 7, node 86g.)

If, in fact, at node 84b, y _t had been found to be >Y2 the algorithm would proceed to evaluate the portion of the tree beginning with node 84d. At the completion of the recursive process represented by FIG. 6, the coordinates x _t ' ^v _t would be uniquely associated with one of cell nodes 86a-86g in FIG. 7. In performing collision avoidance computations, control law selector only has to determine the distance of the tool tip from the boundaries associated with that cell.

Referring again to FIG. 3, control law/command selector 62 in Path Free controller subsystem 34 uses the data provided by cell identifier 60, tool position feedback subsystem 38 and input device 58 to select one of several available operating modes and/or movement control laws for directing the motion of the machine cutter head. Essentially, control law selector 62 functions to interpret the machinist's input commands in light of the part geometry to select a suitable operating mode and to perform the collision avoidance computations between the work piece and the cutting tool.

Before explaining how the control laws are selected, and how collision avoidance is implemented, it will be helpful to understand that there are many operating "modes", i.e., allowable sets of tool trajectories which can be implemented in a computer control machine tool. With reference to FIGS. 8A through 8N, those we have found to be advantageous in path- free machining include:

Jog Mode (see FIG 8A) : Here, the cutter moves in the x, y, or z axis direction, depending on which component of the input command vector 90 is largest. As illustrated, the x-component is the largest, so the tool trajectory 88 is the x-direction. The tool velocity is fixed at a predetermined value, and part boundary conditions are not taken into account. This is useful in initializing the machine, for recording fixture locations, etc.

Free Form Mode (see FIGS 8B and 8C) : Here, the cutter trajectory 92 is allowed full three-dimensional freedom. Cutter direction and velocity are determined by the input command vector 96 produced by input device 58 (see FIG 3) . This is used for rapid movement of the cutting tool.

Strict Grid Mode (see FIG 8D) : Here, the cutter is permitted single axis moves along a user-defined grid in the X-Y plane, stopping only at the nearest point of intersection between grid lines, provided that the tool does not contact a part surface. The separation d _x and d between the grid lines is defined by the operator as an initial operating condition (e.g., in response to on¬ screen prompts) . The input command vector 98 is projected onto the grid and the direction of motion 100 is along the grid line corresponding to the component having the greatest magnitude. This is used most often during a facing operation.

Grid Mode (see FIG 8E) : This is similar to the Strict Grid Mode but also allows for movement along 45 degree angles to the grid. This is also used for facing operations, but because it allows faster point to point travel, it is also advantageous for roughing operations.

Corner Mode (see FIG 8F) : Here cutting tool 102 automatically moves around a corner once the cutting tool is brought to within a region 104 that is a pre- determined distance, dc, from the corner 106. This is used to assure complete machining of all corners.

Corner Post Mode (see FIG 8G) : Here, cutting tool 108 pauses briefly near a corner 110 to allow the operator time either to machine the corner or continue past it. This is also used to assure the complete machining of all corners. However, the decision to machine the corner is left to the operator. The machinist will preselect this or the Corner Mode when setting up the machine, according to his preference.

Position Locating Mode (see FIGS 8H and 81) : This serves to position tool 112 over an active point 114, e.g., the center of a hole, closest to the tool. This is invoked when the tool reaches some predefined active plane, 115, e.g., a predetermined distance from some part boundary. At that time, an input command signal 116 which would cause tool 112 to pass through the plane instead is converted into a motion command 118 in plane 115 directed toward point 114. The tool velocity is functionally related to the magnitude 120 of the input command component normal to plane 115. This is used to accurately locate holes, and the start and end points of slots.

Z-Only Mode ( see FIG. 8J) : Here, a user input command, 122 is resolved into its components along the x, y and z axes. Tool movement is in the z-direction at a velocity

functionally related to the magnitude of the Z-component of the input command. The tool is not permitted to violate any part boundary. This is used to drill holes, and facilitate cutting deep features.

Manhattan Mode (see FIGS. 8K and L) : Here, cutter motion is along one machine axis at a time, provided that no part boundary is violated. The input command vector 124 is decomposed along the machine axes, and the tool moves in the direction corresponding to the largest component. This is used during roughing and positioning.

Sliding Mode (see FIG. 8M) : Here, the tool follows the contour of a surface 126 by resolving an input command vector 128 along the vectors 130 and 132 which are normal and tangential , respectively, to the boundary at the point of contact 134 with the tool. Motion proceeds along the contour and the system remains in sliding mode as long as the input command is not within a predefined angle of the normal and pointed away from the part boundary. This is used to machine complex curved surfaces, and during finishing operations.

Slot Mode (see FIG. 8N) : Here, tool 136 moves along a predefined trajectory 138 with velocity functionally related to the magnitude of the input command component along the trajectory. This is used to machine slots where the tool tip diameter equals this slot width.

Referring now to FIGS. 9 through 11, there will be described the operation of a control law/command selector 62 in accordance with this invention. FIGS. 9A-9C arranged as shown in FIG. 9D, show a transition diagram in which the permitted states are indicated by circles and transitions between the states are indicated by transition vectors. Conditions initiating movement from one state to another are indicated in brackets (i.e., [ ]) next to the transition

vectors. The control laws associated with each of the transition conditions are shown unbracketed. The operating modes (see FIGS. 8A-8N) are shown in parentheses.

The system is initialized in the START state (Step

FIG. 9B, S9A) . Assume, for example, that the operator desires to machine a pocket. A [Do Pocket] command is issued, e.g., in response to an on-screen prompt, and a transition is made to the POCKET CLEARANCE state (FIG. 9C, Step S9B) .

From here, various transitions are possible. For example, when the operation is completed, or if the user selects to terminate the operation before it is completed, an [End Cycle] signal is issued, and the system returns to the START state (FIG. 9C, Step S9B-1) .

While in the POCKET CLEARANCE state (FIG. 9C) if the user operates input device 58 (FIG. 3) to move the tool horizontally, i.e., in the x-y plane, the system receives a horizontal motion command [HM] . This causes control law/command selector 62 to select the Free Form operating mode (without Z-axis motion) (see FIG. 8B) . The resulting control law allows unrestricted horizontal motion of the cutting head (FIG. 9C, Step S9B-2).

If a command is received for upward z-axis movement [VM-U] , or downward z-axis movement [VM-D] from operator input device 58 when the tool is outside the pocket boundary, i.e., the tool is not inside the pocket, the Z-Only operating mode is selected (FIG. 9C, Step S9B-3). The resulting control law allows vertical motion of the cutting head above a computed "clearance plane", i.e., a plane of possible tool motion devoid of any obstruction such as a tool clamp or the stock material itself. (With reference to FIG. 10, an example of a clearance plane is shown at 140, at a distance d above pocket 80) .

In the POCKET CLEARANCE state, if a vertical motion command [VM-D or VM-U] , is received when tool tip 142 is inside the pocket boundary (FIG. 10) , the system enters the VERTICAL state (FIG. 9C, Step S9B-4) . In the VERTICAL state, upward tool movement commands [VM-U] and downward motion commands [VM-U] result in selection of the Z-Only mode. This permits vertical motion within the pocket but bounded by the pocket bottom. The tool is thus free to remove stock material, or to pass through space where stock material has already been removed. (FIG. 9C, Step S9B-6) .

If a [VM-U] command is detected when tool tip 142 is above clearance plane 140 (see FIG. 10) , the system returns to the POCKET CLEARANCE state (FIG. 9C, Step S9B-5) .

Still in the VERTICAL state, if an [HM] command is received, the system enters the MANHATTAN state (FIG. 9C, Step S9B-7) , and tool movement consistent with the Manhattan mode is permitted. An upward or downward motion command, [VM-U] or [VM-D] , returns the system to the vertical state (FIG. 9C, Step S9B-8) . If a horizontal motion command [HM] is received, Manhattan mode motion (see FIG. 8) is permitted as long as the tool tip is more than a small value f, (see FIG. 10) from the pocket boundary (FIG. 9C, Step S9B-9) . A horizontal motion command detected when the cutter is less than the distance f from the pocket boundary causes a transition of the system to the SLIDING state (FIG. 9C, Step S9B-10) .

Here, the Sliding mode (see FIG. 8M) is selected, and the tool tip follows the pocket boundary, (FIG. 9C, Step S9B-11) . Boundary following continues until an input command vector is detected which has a component pointed away from and "approximately" normal, to the part boundary, i.e., within a predetermined angle α of the normal at the time of the computation. In that event, the system returns to the MANHATTAN state (FIG. 9C, Step S9B-12) .

Referring to FIGS. 9A and 9B, if the operator indicates his intent to drill a hole, a [Do Hole] command is issued, and the system goes to the HOLE CLEARANCE state from the START state (FIG. 9A, Step S9C) . Again, an [End Cycle] signal returns the system to START state (FIGS. 9A and 9B, Step S9C-1) . A horizontal motion command [HM] places the system in the Free Form mode, with movement as previously described. (FIG. 9A, Step S9C-2) . From this state, a vertical motion command [VM-U or VM-D] received while the tool tip is above the clearance plane 140 selects the Z-Only mode (FIG. 9A, S9C-3) , but when the tool tip reached the clearance plane 140, the Position Locating mode (see FIGS. 8H and 81) is selected, and the tool tip moves toward the nearest hole center as directed by the geometric model (FIG. 9A, Step S9C- 4) .

If a down motion command is still being received when the tool tip 112 reaches a predetermined small distance g (e.g., 0.0025mm) from the hole center, the system enters the DRILLING state (FIG. 9A, Step S9C-5) . In the DRILLING State, Z-Only operating mode is selected. Execution of an upward motion command [VM-U] is permitted; if upward motion is still being called for when the tool tip reaches the clearance plane, the system returns to the HOLE CLEARANCE State (FIG. 9A, Step S9C-6) . Downward vertical motion is allowed, but bounded by the hole bottom (FIG. 9A, Step S9C-7) .

Referring again to FIG. 9B, if the user desires to machine a slot, a [Do Slot] command is issued, and the system enters the SLOT CLEARANCE state (Step S9D) . An [End Cycle] signal returns the system to START state (Step S9D-1) . A horizontal motion command [HM] places the system in the Free Form mode, allowing unrestricted horizontal moves as previously described. (Step S9D-2) . A vertical motion command [VM-U or VM-D] received while the tool tip is above the clearance plane 140 selects the Z-Only mode (S9D-3) . This allows vertical motion above the clearance plane. However,

when the tool tip reaches clearance plane 140, the Position Locating mode (see FIGS. 8H and 81) is selected, and the tool tip moves toward the starting point of the slot (Step S9D-4) .

If a down motion command is still being received when the tool tip 112 reaches a predetermined small distance g (e.g., 0.0025mm) from the starting point of the slot, the system enters the IN SLOT state (Step S9D-5) . If upward motion commands [VM-U] or down motion commands [VM-D] are encountered, the Z-Only mode is selected. Up or down motion is permitted as long as the slot bottom depth is not exceeded ((Step S9D-6) . However, if upward motion is being called for when the tool tip reaches the clearance plane, the system returns to the HOLE CLEARANCE state (Step S9D-7) .

If horizontal motion commands [HM] are encountered while in the IN SLOT state, the Slot mode is selected (Step S9D-8) . This permits the slot to be machined based on motion as described in connection with FIG. 8N. The extent of horizontal motion is determined by the slot shape and orientation according to the geometric model.

To facilitate understanding of the invention, the description has presented only three kinds of machining operations for control law/command selector 62. However, other kinds of operations may be provided for as well, each with its own control algorithm.

The ability of the system to analyze the operator's intentions from the input commands compensates for inherent human inaccuracies, and limitations on the resolution of real¬ time, hand-operated input devices. By transitioning between the available operating states, the required part tolerances are as readily achieved in the interactive environment as with a conventional CNC machine. It should be understood, however, that the operating modes described are not exhaustive, and others are possible within the scope of the invention.

As will be appreciated, many ways exist for implementing the functions described in connection with FIG. 9, as will be apparent to one skilled in this art, and in the interest of brevity, a description of the coding is not presented. It should, of course, be recognized that the boundary constraints and state transitions noted in describing the permissible tool tip trajectories are determined by comparing the instantaneous tool tip coordinates with the corresponding coordinates of the model boundaries.

Tool motion command execution processor 64 (see FIG. 3) uses control law commands passed to it by control law/command selector 62 to move the tool tip along the trajectory corresponding to the selected operating mode, while assuring that the part boundaries are not violated.

FIG. 11 shows how command execution processor 64 functions in response to control law selector commands. Here, it is assumed that control law/command selector 62 has sent an instruction to command execution processor 64 allowing motion of tool 148 along a straight line path 150 ending at a point 152, which might represent a part boundary, and that, at some particular time, with the tool tip located at position 156 as shown, the user operates input device 58 to produce an input command vector 154. The output of command execution processor 64 is a control vector V ₂ . This is produced by a five step computation cycle as follows:

a) Determine the coordinates of current tool tip position 156. This information is provided by tool position feedback subsystem 38 (see FIG. 3) .

b) Calculate the distance d _is from tool tip position 156 to end point 152, and the distance d from tool tip position 156 to desired path 150.

c) Calculate the vector U, the projection along too path 150 of the control input command vector 154.

d) Calculate a vector V ₁ according to the relationship:

V ₁ = f(d _is ) * U (1)

e) Modify V _λ to create the final control vector V ₂ , according to the following:

For the sliding mode, as illustrated in FIG 8M, th input control signal 128 is resolved into two components F and F _n tangent and normal respectively, to part boundary 126.

To maintain contact along a boundary defined by a straigh line segment, command execution processor 64 produces a output signal V ₂ such that:

V ₂ = V-L - f(d) * N (2)

where N is the unit vector normal to the boundary pointin toward the inside of the pocket and d is the distance from th tool to the boundary along N. (In FIG. 8M, the distance d is shown equal to 0.)

If the boundary is defined by an arc segment of radius r, equation (2) is modified so that control vector V ₂ is:

v ₂ = v,- ¹ , _n κ, * t* \u _t \ * \u _t \ \ (3)

where |U _t | is the absolute value of U _t , t is the elapsed time since the last calculation and d is again the distance of the tool from the desired trajectory.

These formulas are directly applied in general (i.e., non-sliding mode case as illustrated in FIG. 11, by substituting the path 150 for the boundary 126 (see FIG. 8M) .

A variety of functional relationships for f(d _is ) and f(d) are possible, but in actual practice, simple linear relationships are quite satisfactory. Thus, the relations ips: and f ₁ (d)=K ₂ d (5) are preferred.

Referring still to FIG 11, as the distance d _is decreases, the magnitude of vector V ₁ also decreases, This, in turn, reduces the magnitude of vector V ₂ as tool tip 148 approaches the intended boundary point 152. (If the tool could cross the boundary, d _is would become negative generating a control signal pushing the tool away from the boundary.) Also, as will be recalled, the sliding mode is defined such that if the angle between N and U becomes smaller than some predetermined distance, e.g., 20 degrees, control law/command selector 62 will pick a new control law, and operation of command execution processor 64 would be governed by other constraints.

In the drilling example, (See FIGS. 8H, 81 and 9) a downward force generated while the tool is located on or above the clearance plane 115 results in movement of the machine tool tip 112 to center it over the nearest hole, e.g., at point 114.

The x and y components of the velocity command vector V from command generator 64 are made proportional to the vertical component U _v of the input command, and are functionally related to C _χ and C _y/ the respective x and y

components of vector 118 from the tool tip 112 to the point 114 above the hole center. Thus:

^V x ^=f 2< ^C χ) * ! ^U v! (6) and

V _y =f ₂ (C _y ) * jU _v i (7)

The path of motion is planar, and as in the previous examples, the preferred functional relationship is linear, i.e. , f ₂ (C)=K ₅ C. (8)

By making the magnitude of vector V proportional to U _v , the speed of tool movement toward the hole is correlated with the force being applied by the operator to input device 58.

As will be understood, command execution processor 64 provides signals for controlling the machine tool drive motors (not illustrated) . This may be accomplished in any conventional way through motor interface subsystem 36 as will be understood by one skilled in the art based on the above description.

FIG. 12 shows a flow diagram of an augmented embodiment of the present invention which differs from that previously described in that the process also includes recording the tool motion commands for subsequent use in automated cutting operation. As shown, the process again includes generation of a geometric model (Step S12A) , operator input of real time processing information (Step S12B) , interactive generation of tool motion commands (Step S12C) to control the cutting operation (Step S12D) and tool position feedback (Step S12E) to close the control loop. In addition, however, the process also includes processing of the tool motion commands to create a cutting program (Step S12F) ,

recording the processed command information (Step S12G) , and playing back the recorded cutting program (Step S12H) .

A functional implementation of the process of FIG. 12 is shown in FIG. 13. Two different approaches may be used in processing the motion commands; direct playback and abstracted playback. Both are shown in FIG. 13. As illustrated, the augmented system includes control law/command selector 62 and command execution processor 64 as previously described, process recorder 170, process storage means 171, and clock 175.

According to the invention, changes in either the tool trajectory direction 150 (see FIG. 11) , or end point 152 are considered as "significant events". Process Recorder, 170 detects these changes. This may be accomplished in any suitable way; for example, the Process Recorder 170 monitors the commands passed from the Control Law Command selector 62, to Command Execution Processor 64. Each command that is passed to the Command Execution Processor 64 is compared with the previously passed command. If they are the same, the Process Recorder 170 does nothing; if they are different, the Process Recorder records the current position and time from the clock 175.

At this point, if the commanded end point has changed, the new position is stored in process storage means 171, and the distance traveled by the tool tip since the previous "significant event" is divided by the recorded time interval to create a current value of average tool tip velocity. This also is stored in process storage means 171.

The data in process storage means 171 may be used as an input to Path-free controller 34 to machine additional parts without input commands from an operator. In that case, the data played back are the series of recorded commands stored in process storage means 171. The stored commands are

sequentially executed by the command execution processor 64; when the end point for a given command is reached, the nex command in the recorded sequence is executed. For eac command, the associated average velocity is used.

The sequence of recorded commands may also be down¬ loaded to a floppy disk, and edited or modified using conventional programming tools to create a part program for running a conventional CNC machine tool.

There are several benefits to recording the operator's interactive machining session for future playback. For example, use of the Path-free technology according to this invention allows the machinist to cut parts with consistent accuracy, and playback allows additional parts to be machined in a fashion similar to the first. Using this system in the direct playback mode, a machinist can rapidly and accurately generate small batches of components.

INDUSTRIAL APPLICABILITY

The invention has been described in the context of a machine tool, but has utility in other applications requiring manual control limited by predetermined objective- related constraints. These could include process control, simulators, robotics, and even semi-automated vehicle control.

Similarly, machine tool applications other than those specifically described are also within the scope of the invention.

Further, while the invention has been described in process and functional terms to illustrate significant features and apreferred implementation, it should be understood that the description is only intended to enable practice of the invention by those skilled in the art, and that other implementations are possible.