IN RE KAREN I. TROVATO AND LEENDERT DORST

Lee E. Barrett, Associate Solicitor, Office of the Solicitor, of Arlington, Virginia, argued for appellee. With him on the brief were Fred E. McKelvey, Solicitor, Albin F. Drost, Deputy Solicitor and Joseph G. Piccolo, Assistant Solicitor. Of counsel was Richard E. Schafer.

Appealed from: U.S. Patent and Trademark Office

Board of Patent Appeals and Interferences

DECIDED: December 19, 1994

Before NIES, MICHEL and SCHALL, Circuit Judges.

NIES, Circuit Judge.

Karen I. Trovato and Leendert Dorst (collectively Trovato) appeal the July 22, 1992, and May 26, 1993, decisions of the Patent and Trademark Office Board of Patent Appeals and Interferences (Board), Appeal Nos. 92-1843 and 92-4106, respectively. The Board affirmed the rejection of claims pending in U.S. Patent Applications 07/508,024 (the '024 application) and 07/617,303 (the '303 application) for lack of statutory subject matter under 35 U.S.C. § 101 (1988). Finding no reversible error in the Board's decision, we affirm.

I.

The problem of finding the shortest distance between two points is a recurring one, and is of particular interest to students of the computer science field known as graph theory. Trovato's inventions work within this area, attempting to solve the "shortest path problem" by finding the optimal path between two locations, whether in terms of distance, cost, capacity, time or other criteria. The inventions model possible object movements in the real world--the "physical task space"--by a graph called a "configuration space." Each node of the graph represents a discrete state, or set of conditions, such as location or orientation. Edges connect the graph nodes and indicate the cost of transferring from one state to another.

The configuration space is stored in a "data structure." Although Trovato does not define this term, their specification makes clear that the data structure arranges various information needed to solve the shortest path problem. The data structure thus includes known information, such as the number of states in the configuration space, a "metric" providing the transition cost to any neighboring state, and the location of obstacles and goals in the configuration state. The data structure also accounts for data which Trovato's invention must calculate, including the optimal transition cost from one state to another, and the orientation, or next state on the path toward the nearest goal state.

The invention Trovato describes in the '303 application determines the most efficient path between states in the configuration space by propagating "cost waves," a process also known as "budding." Initially, the cost and direction of movement to the goal state from any particular state are unknown. The budding process calculates a value representing the cost of movement to the goal state for each possible state, as well as the direction to the goal state. Starting with the goal state and working outward to the remaining states, each neighboring state is explored in successive "waves," ultimately indicating the lowest cost path from the initial state to the goal state, leading through a number of intermediate states.

The '024 application describes an invention which improves upon the budding process described in the '303 application. In the event of a change in conditions in the physical task space, the invention set forth in the '024 application uses various techniques to distinguish that subset of states in the configuration space which is impacted by the altered condition. Thus, rather than recalculating the entire configuration space, only the values associated with those states that are actually affected need be redetermined using the budding process.

Representative claims of the '303 application include method claims 1 and 2, which recite:

1. A method for determining motion of an object comprising the steps of:
a) storing a configuration space data structure representing a physical task space, the configuration space data structure including representations of the object and its environment; and
b) propagating cost waves, in the configuration space data structure, to fill the configuration space data structure with cost values according to a space variant metric.

2. The method of claim 1, further comprising the steps of:

a) deriving a sequence of object pose representations within the configuration space data structure, using the cost values, which representations represent physical poses defining a least cost path from a start pose to a goal pose in the physical task space; and
b) providing a series in electronic form usable by the object to follow the path.

Claim 33 provides an example of an apparatus claim within the application:

33. Apparatus for planning a least cost path comprising:
a) means for storing a discretized representation of a physical task space;
b) means for assigning at least one respective cost to at least one neighboring position of any given position, based on
i) a cost assigned to the given position; and
ii) a measure which varies according to position within the discretized representation, so that a least cost path from the neighboring position to the given position is established;
c) means for starting the assigning means at a first position of known cost;
d) means for causing the assigning means to iterate, so that all positions within the discretized representation are assigned respective costs, in waves propagating outward from the first position; and
e) means for identifying a least cost path between two positions in the discretized representation based on the respective costs.

The examiner rejected claims 1-26 and 33 as being directed to nonstatutory subject matter under § 101 after applying the so-called "Freeman-Walter-Abele" test.1

[1]The examiner indicated that claims 29-32 were drawn to patentable subject matter, but rejected them on other grounds. They are not at issue in this appeal.

See In re Abele, 684 F.2d 902, 214 USPQ 682 (CCPA 1982); Application of Walter, 618 F.2d 758, 205 USPQ 397 (CCPA 1980); In re Freeman, 573 F.2d 1237, 197 USPQ 464 (CCPA 1978). This Court has followed our predecessor court on this issue, In re Schrader, 22 F.3d 290, 292-94, 30 USPQ2d 1455, 1457-59 (Fed. Cir. 1994), Arrhythmia Research Technology, Inc. v. Corazonix Corp., 958 F.2d 1053, 1058, 22 USPQ2d 1033, 1037 (Fed. Cir. 1992), In re Iwahashi, 888 F.2d 1370, 1374, 12 USPQ2d 1908, 1910-11 (Fed. Cir. 1989), In re Grams, 888 F.2d 835, 838-39, 12 USPQ2d 1824, 1827 (Fed. Cir. 1989), and has summarized its methodology as follows:

It is first determined whether a mathematical algorithm is recited directly or indirectly in the claim. If so, it is next determined whether the claimed invention as a whole is no more than the algorithm itself; that is, whether the claim is directed to a mathematical algorithm that is not applied to or limited by physical elements or process steps.
Arrhythmia, 958 F.2d at 1058, 22 USPQ2d at 1037.

The examiner reasoned that the claims, at least indirectly, recited a mathematical algorithm. Per the examiner, Trovato's claimed steps such as measuring transition costs, propagating cost waves and assigning costs values were all mathematical functions. Applying the second part of the Freeman-Walter-Abele test, he individually considered each claim and concluded that the claims did not involve physical structure or process steps beyond insignificant data-gathering steps or post-solution output, following Grams, 888 F.2d at 839-40, 12 USPQ2d at 1828, and cases cited therein, and Parker v. Flook, 437 U.S. 584, 590 (1978).

Trovato appealed the rejection to the Board, where the examiner's rejection of claims 1-23 and 33 was sustained. Again applying the Freeman-Walter-Abele test, the Board reasoned that the claims recited the budding process, which amounted to the indirect recitation of a mathematical algorithm. Turning to the second element of the Freeman-Walter-Abele test, the Board held that no specific physical apparatus was claimed. The Board reversed the examiner's rejection of claims 24-26, however, on the grounds that the claims recited sufficient physical structure.2

[2] Claims 24-26 recite apparatus such as a building emergency alarm system and an electronic map, and name objects to be moved such as an emergency vehicle, a person trying to exit a building, and a person trying to find a route in a new area.

One member of the Board dissented from the rejection of claims 2 and 4-23, characterizing these claims as reciting meaningful structural limitations rather than post-solution activity without patentable significance.

Representative claim 1 of the '024 application provides:
1. A method for planning a path for an object to follow in a physical task space in which there has been a change in conditions comprising the steps of:
a) starting from an initialized configuration space data structure representing the physical task space, the configuration space data structure storing signals representing the object and its environment;
b) receiving signals indicating the change in conditions;
c) identifying the perimeter of a region in the configuration space data structure which is affected by the change in conditions;
d) propagating cost waves in the configuration space data structure from the perimeter to update the signals stored in the configuration space data structure; and
e) providing parameter signals based on the updated direction arrows [sic, signals], the parameter signals being usable by the object to follow the path.

Claim 41 of the '024 application provides a second example:
41. Computer apparatus for planning a path for an object to follow in a physical task space in which there has been a change in conditions comprising:
a) means for storing a configuration space representing the object and its environment;
b) means for receiving signals indicating the change of conditions;
c) means for identifying a perimeter of a region in the configuration space which is affected by the change in conditions;
d) means for propagating cost waves from the perimeter by updating the configuration space, within the means for storing, to fill the configuration space with an updated representation corresponding to the change in conditions; and
e) means for supplying parameter signals based on the updated configuration space, the parameter signals being usable by the object to follow the path.

The same examiner who considered the '303 application rejected claims 1, 30, and 41-45 of the '024 application, offering the same analysis under Freeman-Walter-Abele.3

[3] Similar claims of the parent of the '024 application were allowed, and matured into U.S. Patent No. 4,949,277.

The Board upheld the rejection in its entirety, inter alia on the grounds that the claims indirectly recited a mathematical algorithm. One member of the Board again dissented, indicating his belief that Trovato's claims were statutory as being "directed to a computer-implemented process wherein the computer performs process steps to plan a path for an object to follow, updating such plans as more frequent data relating to changed conditions becomes available." Trovato now brings an appeal from these decisions of the Board, which have been consolidated for purposes of our review.

II.

The claims of Trovato's applications will for convenience be referred to as method and apparatus claims, as denominated by Trovato. We consider first the method claims: claims 1-21 of the '303 application and claims 1, 30 and 44-45 of the '024 application.

Trovato argues that neither element of the Freeman-Walter-Abele test is met. First, Trovato contends that the claimed invention solves a physical, not mathematical problem. Second, citing our predecessor court's decision in In re Bradley, 600 F.2d 807, 202 USPQ 480 (CCPA 1979), aff'd, Diamond v. Bradley, 450 U.S. 381 (1981), Trovato argues that the claimed data structure is a physical entity, consisting of electrical or magnetic signals and requiring interaction between the processing and memory apparatus of a computer.

We are unconvinced by Trovato's argument that the claims of the applications do not recite a mathematical algorithm. Although the claimed process is not expressed in terms of a mathematical formula, application of the Freeman-Walter-Abele test is more refined than this simple determination. Our precedent also recognizes that "[w]ords used in a claim operating on data to solve a problem can serve the same purpose as a formula." Grams, 888 F.2d at 837 n.1, 12 USPQ2d at 1826 n.1 (citing Freeman, 573 F.2d at 1246, 197 USPQ at 471). Here, the budding process described in each claim calculates a numerical transition cost, adds the transition cost to a previously computed sum of the costs to the goal state, and compares the sums for different states within the configuration space. Importantly, any number of vastly differing aspects of the physical task space--including obstacles, terrain features such as slopes or slick surfaces, and danger to the moving object--are represented abstractly, through a numerical value. The claims describe a systemic way of examining this data, which at every turn involves arithmetic operations manipulating numbers. We thus conclude that Trovato's method claims indirectly recite a mathematical algorithm.

Under the second part of the Freeman-Walter-Abele test, the court must "determine what the claimed steps do, independent of how they are implemented," Arrhythmia, 958 F.2d at 1059, 22 USPQ2d at 1038. Analyzing the most recent Supreme Court decision pertaining to computer-related inventions, Diamond v. Diehr, 450 U.S. 175 (1981), our predecessor court explained in Abele:

In [Diehr,] the Court held that a process for curing synthetic rubber constituted patentable subject matter notwithstanding that the process used an equation for controlling the in-mold time which was constantly updated by a digital computer. In Diehr, were the claim to be read without the algorithm, the process would still be a process for curing rubber, although it might not work as well since the in-mold time would not be as accurately controlled. Hence, the Court concluded that the claimed invention fell within § 101 because it presented "an application of a law or nature or mathematical formula to a known structure or process." [Emphasis in original.]

684 F.2d at 907, 214 USPQ at 686 (quoting Diehr, 450 U.S. at 187).

Unlike the invention claimed in Diehr, the specifications involved here provide no grasp of any underlying physical process. Although cursory references to such diverse apparatus as robots, dynamic emergency exit routes and electronic maps are present, no computer architecture is provided, no circuit diagram is revealed, and no hardware at all receives more than a brief mention. Indeed, the specifications note the inventions' "general applicability to numerical methods" and seek to describe them "[f]rom a mathematical point of view." When questioned during oral argument before this Court, counsel for Trovato admitted that neither specification includes a hardware enablement of the claimed invention. Instead, the entire disclosure consists of flow charts and program code computing the least cost path from starting to goal states based upon the data in the configuration space. We therefore conclude that Trovato claims nothing more than the process of performing a numerical calculation. Simply stated, viewing the claims absent the algorithm, and as a whole, no statutory subject matter is present. See Abele, 684 F.2d at 908, 214 USPQ at 687. See also In re Richman, 563 F.2d 1026, 195 USPQ 340 (CCPA 1977) (claimed method of calculating airborne radar boresight correction angle is nonstatutory).

Although some of Trovato's claims describe an electronic readout of the computed data, it is well-established that mere post-solution display does not render patentable a mathematical algorithm. As our predecessor court noted in Walter, "[i]f § 101 could be satisfied by the mere recordation of the results of a nonstatutory process on some record medium, even the most unskilled patent draftsman could provide for such a step." 618 F.2d at 770, 205 USPQ at 409. See also Abele, 684 F.2d at 909, 214 USPQ at 688; In re de Castelet, 562 F.2d 1236, 1244, 195 USPQ 439, 446 (CCPA 1977). Nor do Trovato's applications describe inventions which manipulate physical qualities, as with the inventions held to fall within statutory subject matter in cases such as Arrhythmia, 958 F.2d at 1059, 22 USPQ2d at 1039 (analyzing electrocardiographic signals); In re Taner, 681 F.2d 787, 790, 214 USPQ 678, 681 (CCPA 1982) (conversion of seismic signals); and Application of Sherwood, 613 F.2d 809, 819, 204 USPQ 537, 546 (CCPA 1980), cert. denied, Diamond v. Sherwood, 450 U.S. 994 (1981) (conversion of seismic traces). Indeed, the claimed invention does not even take the actual step of gathering the data from the "physical task space" that is arranged into the recited "configuration space data structure," a procedure which in itself cannot render an otherwise nonstatutory subject matter patentable. See Grams, 888 F.2d at 840, 12 USPQ2d at 1828; In re Sarkar, 588 F.2d 1330, 1335, 200 USPQ 132, 139 (CCPA 1978); In re Chatfield, 545 F.2d 152, 158, 191 USPQ 730, 736 (CCPA 1976), cert. denied, Dann v. Noll, 434 U.S. 875 (1977).

Trovato's applications fail even to explain how the claimed inventions actually employ the numbers derived to control movement. Although the inventions likely employ techniques known to the art to move an object along the lowest cost path it calculates, the absence of even a cursory description of how the computed values are implemented further indicates that the claimed methods comprise only numerical manipulation. Much like the application in Grams, "[t]he specification does not bulge with disclosure" regarding this crucial physical step, and instead focuses exclusively upon the mathematical calculations performed by the invention. 888 F.2d at 840, 12 USPQ2d at 1828. We must conclude that the "felt meaning" of the claim, Autogiro Co. of America v. United States, 384 F.2d 391, 397, 155 USPQ 697, 702 (Ct. Cl. 1967) (quoting United States v. Johnson, 221 U.S. 488, 496 (1911) (Holmes, J.)), is directed wholly toward an unpatentable mathematical algorithm.

For the purposes of the determination of statutory subject matter, we find these claims scarcely distinguishable from those before the Court in its recent decision in In re Warmerdam, 33 F.3d 1354, 31 USPQ2d 1754 (Fed. Cir. 1994). In Warmerdam, this Court held that claims reciting a method for creating a data structure which controlled the motion of objects did not constitute patent eligible subject matter. Citing the difficulties in determining the proper boundaries of the nonstatutory category of mathematical algorithms, Warmerdam did not proceed by employing the latter term. The court instead reasoned that the claimed method was nothing more than the manipulation of abstract ideas, rather than speaking of a mathematical algorithm. Id. at 1360, 31 USPQ2d at 1758-59. See also In re Alappat, 33 F.3d 1526, 1542, 31 USPQ2d 1545, 1556 (Fed. Cir. 1994) (in banc) ("the Supreme Court never intended to create an overly broad, fourth category of subject matter [mathematical algorithms] excluded from § 101").

As in Warmerdam, Trovato's claims operate merely in the domain of abstract ideas. The methodical application of arithmetic operations to data placed within a numerical configuration in order to determine the least cost path through a mathematically structured graph amounts only to a generality or disembodied concept, outside the subject matter listed in § 101. Without further application or connection to a technical art, we cannot say that Trovato's claims pass muster under the alternative analysis of statutory subject matter expressed in Warmerdam.

Bradley, 600 F.2d 807, 202 USPQ 480, cited as support by Trovato for the patentability of the claimed methods, is not to the contrary. Our reading of this precedent was set forth in Warmerdam--that the Bradley application concerned "a physical, interconnected arrangement of hardware and was thus embraced by the term 'machine'," 33 F.3d at 1362, 31 USPQ2d at 1760, unlike Trovato's applications. Trovato also turns to the IEEE Standard Computer Dictionary (1991), also noted in Warmerdam, 33 F.3d at 1361-62, 31 USPQ2d at 1760, which defines a data structure as a "physical or logical relationship among data elements, designed to support specific data manipulation functions." (Emphasis added.) We fail to see how this definition particularly advances their cause, however, as its express language implies a physical arrangement of a computer's memory contents only in the alternative. In any event, the mere citation of a dictionary definition on appeal cannot augment the paucity of structure disclosed in Trovato's specification.

We conclude that the Board did not err in sustaining the rejection of claims 1-21 of the '303 application, as well as claims 1, 30, and 44-45 of the '024 application.

III.

The remaining claims of the '303 and '024 applications recite some sort of apparatus in the preamble. The apparatus claims essentially follow the format of the earlier method claims, although Trovato employs two additional drafting mechanisms. First, the preamble recites the term "apparatus." Second, the term "means for" has been placed prior to the various claim limitations.4

[4] See generally Richard Stern, Tales From the Algorithm War, 18 AIPLA Q.J. 371 (1991).

The use of different claim formats does not necessarily diminish the impact of § 101. "Even though the claimed invention is a machine, we must nevertheless determine whether the claim recites a mathematical algorithm, and, if so, whether it preempts the use of the algorithm." Bradley, 600 F.2d at 813, 202 USPQ at 486 (citing In re Noll, 545 F.2d 141, 148, 191 USPQ 721, 726 (CCPA 1976), cert. denied, Dann v. Noll, 434 U.S. 875 (1979)). In this case, the additional claim language employed in this second group of claims, viewed in light of the specification, is of no patentable significance.

Although Trovato's claims employ the term "apparatus" in the preamble, such language alone will not always amount to a structural limitation affecting the scope of a claim. This Court has noted instead that:

No litmus test can be given with respect to when the introductory words of a claim, the preamble, constitute a statement of purpose for the device or are, in themselves, additional structural limitations of a claim. To say that a preamble is a limitation if it gives "meaning to the claim" may merely state the problem rather than lead one to the answer. The effect preamble language should be given can be resolved only on review of the entirety of the patent to gain an understanding of what the inventors actually invented and intended to encompass by the claim.

Corning Glass Works v. Sumitomo Elec. U.S.A. Inc., 868 F.2d 1251, 1257, 9 USPQ2d 1962, 1966 (Fed. Cir. 1989).

Similarly, in Abele, 684 F.2d at 907, 214 USPQ at 687 (citations omitted), our predecessor court noted:

The goal is to answer the question "What did applicants invent?" If the claimed invention is a mathematical algorithm, it is improper subject matter for patent protection, whereas if the claimed invention is an application of the algorithm, § 101 will not bar the grant of a patent.

In answering that question, [e]ach invention must be evaluated as claimed; yet semantogenic considerations preclude a determination based solely on words appearing in the claims. In the final analysis under § 101, the claimed invention, as a whole, must be evaluated for what it is.

Hence, the analysis requires careful interpretation of each claim in light of its supporting disclosure. See also Grams, 888 F.2d at 839, 12 USPQ2d at 1827 (quoting Abele).

Our review of Trovato's application in its entirety indicates that they do not disclose a machine of any sort. We can discern no disclosed apparatus provided in the specifications as suggested in the various claim preambles. Further, all the disclosed means are simply software instructions; no "structure" appears in the specification as required under § 112, ¶ 6. Although Trovato points to the "signals" drafted in some of their claims, indicating the electrical signals internally transmitted by a computer as part of its solution of the budding process, the mere noting of "signals" does not transform their inventions into statutory subject matter under the circumstances presented here. As noted in Bradley, 600 F.2d at 811-12, 202 USPQ at 485:

It is of course true that a modern digital computer manipulates data, usually in binary form, by performing mathematical operations, such as addition, subtraction, multiplication, division, or bit shifting, on the data. But this is only how the computer does what it does. Of importance is the significance of the data and their manipulation in the real world, i.e., what the computer is doing. It may represent the solution of the Pythagorean theorem, or a complex vector equation describing the behavior of a rocket in flight, in which case the computer is performing a mathematical algorithm and solving an equation. [Emphasis in original.]

As with the hypothetical vector equation suggested in Bradley, Trovato's claims do no more than solve a mathematical algorithm. See also de Castelet, 562 F.2d at 1244, 195 USPQ at 446 ("That the computer is instructed to transmit electrical signals, representing the results of its calculations, does not constitute the type of 'post solution activity' found in Flook, and does not transform the claim into one for a process merely using an algorithm.") We can only conclude that Trovato's claims, as was the claimed invention in Walter, 618 F.2d at 769, 205 USPQ at 409, are "drafted in illusory apparatus format."

Our result here comports with our recent decision in Alappat, 33 F.3d 1526, 31 USPQ2d 1545. Although the claims of the inventor in Alappat were also drafted in means format, unlike the disclosure here, his application disclosed a specific hardware embodiment. There, we extensively relied upon the hardware listed in the specification, including arithmetic logic circuits, barrel shifters and a read only memory in reaching the result that the claimed invention constituted patent eligible subject matter. Id. at 1541, 31 USPQ2d at 1555. Specific note was also made of the combination of claimed elements from which the inventor formed a machine. Id. at 1544, 31 USPQ2d at 1557. As we have noted, however, a search through Trovato's application for the combination of similar apparatus is unavailing. The use of an apparatus claim format in this fashion is precisely the sort of "guise" recognized in Alappat, 33 F.3d 1541, 31 USPQ2d at 1555, and the cases cited therein.

Other than noting the preamble terminology and the use of a means plus function claim format, Trovato's remaining argument regarding the patentability of their claims concerns the discipline of computer science itself. Trovato argues that the Board's result is unjust because they have made a useful, novel and nonobvious contribution to the field of computer science. Trovato further contends that scientists working in the field of computer software are not less worthy of obtaining patent protection for their inventions than technologists in more traditional fields.

To the contrary, we have no reason to doubt that Trovato has made a contribution in the field of graph theory. Ingenuity and utility, however, have never been sufficient in themselves to garner patent protection. See Diehr, 450 U.S. at 185 ("This Court has undoubtedly recognized limits to § 101 and every discovery is not embraced within the statutory terms."). As the "basic tools of scientific and technological work," Gottschalk v. Benson, 409 U.S. 63, 67 (1972), mathematical calculations per se remain outside the sphere of patent protection. The presence of patent eligible subject matter must always be determined upon the individual facts of each case. The application in this case fails to meet the statutory standard.

IV.

Trovato does not claim to have invented a new kind of computer which the recited mathematical algorithm controls. Nor do they claim that the recited mathematical algorithm has been combined with a new memory controlling a computer known to the art. Putting Trovato's claims in their most favorable light, the most they provide is a systemic way in which to compute a number representing the shortest path. A new way to calculate a number cannot be recognized as statutory subject matter. We thus conclude the Board properly rejected claims 1-23 and 33 of the '303 application, as well as claims 1, 30, and 41-45 of the '024 application, for lack of statutory subject matter under § 101. The decisions of the Board are therefore

AFFIRMED .