** Lee E. Barrett**, Associate Solicitor, Office of the Solicitor, of Arlington, Virginia, argued for appellee. With him on the brief were

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.

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**-

[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);

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**-

Trovato appealed the rejection to the Board, where the examiner's rejection of claims 1-23 and 33 was sustained. Again applying the ** Freeman**-

[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**-

[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.

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**-

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**-

Under the second part of the ** Freeman**-

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

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.

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.

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,

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

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

** 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

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.

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,

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

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.

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

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.,

As with the hypothetical vector equation suggested in ** Bradley**, Trovato's claims do no more than solve a mathematical algorithm.

Our result here comports with our recent decision in ** Alappat**, 33 F.3d 1526, 31 USPQ2d 1545. Although the claims of the inventor in

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,"

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 .