CITE: 42 F.3d 1376
CMON: December 1994
PLAIN: In re Trovato
DEFND: United States Patent and Trademark Office
COURT: US Court of Appeals Federal Circuit
DATE: December 19, 1994
HISTORY:
Appeal from the US Patent and Trademark Office, Board of Patent Appeals
and Interferences.
Patent applications, nos. 07/508,024 and 07/617,303, filed by Karen I.
Trovato and Leendert Dorst. From decision affirming rejection of claims,
applicants appeal. Affirmed.
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 Appeal and Interferences (Board), Appeal Nos. 92-1843
and 92-4106, respectively. The Board affirmed the reject of claims pending
in US Patent Applications 07/508,024 (the '024 application) and 07/617,303
(the '303 application) for lack of statutory subject matter under 35 USC
101 (1988). Finding no reversible error in the Board's decision, we affirm.
SUMMARY:
Algorithm as method without apparatus is not patentable.
JUDGE: Nies, Judge
Before Nies, Michel, and Schall, circuit judges.
DECISION:
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
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, suing 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 Section 101 after applying the so-called
"Freeman-Walter-Abele" test. {1} See In re Abele, 684 F.2d 902 (CCPA 1982);
Application of Walter, 618 F.2d 758 (CCPA 1980); In re Freeman, 573 F.2d
1237 (CCPA 1978). This Court has followed our predecessor court on this
issue, In re Schrader, 22 F.3d 290, 292-94 (Fed. Cir. 1992), In re Iwahashi,
888 F.2d 1370, 1374 (Fed. Cir. 1989), In re Grams, 888 F.2d 835, 838-39
(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.
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, and cases cited therein, and
Parker v. Flook, 437 US 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} 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
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
Freeman-Walter-Abele. {3} 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 CCPA 1979), affirmed, Diamond v. Bradley,
450 US 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 (citing Freeman, 573 F.2d
at 1246). 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. Analyzing the most recent
Supreme Court decision pertaining to computer-related inventions,
Diamond v. Diehr, 450 US 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 or controlling the I-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 Sect. 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 (quoting Diehr, 450 US at 187).
Unlike the invention claimed in Diehr, the specifications involved
here provide not 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 ot 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. See
also In re Richman, 563 F.2d 1026 (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 Sect. 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. See also Abele, 684 F.2d at 909; In re de
Castelet, 562 F.2d 1236, 1244 (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 (analyzing electrocardiograph signals);
In re Taner, 681 F.2d 787, 790 (CCPA 1982) (conversion of seismic signals);
and Application of Sherwood, 613 F.2d 809, 819 (CCPA 1980), cert. denied,
Diamond v. Sherwood, 450 US 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; In re Sarkar, 588 F.2d 1330, 1335 (CCPA 1978);
In re Chatfield, 545 F.2d 152, 158 (CCPA 1976), cert. denied, Dann v. Noll,
434 US 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. We must conclude that the "felt meaning" of the claim,
Autogiro Co. of America v. United States, 384 F.2d 391, 397 (Ct. Cl. 1976)
(quoting United States v. Johnson, 221 US 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 (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. See also In re Alappat,
33 F.3d 1526, 1542 (Fed. Cir. 1994) (in banc) ("the Supreme Court never
intended to create an overly broad, fourth category of subject matter
[mathematical algorithms] excluded form Sect. 101").
As in Warmerdam, Trovto'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 Sec. 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, 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, unlike Trovato's
applications. Trovato also turns to IEEE Standard Computer Dictionary
(1991), also noted in Warmerdam, 33 F.3d at 1361-62, 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 '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} Use of "means for" invokes 35 USC Sect. 112,
paragraph 6 (1988), which indicates that the PTO must construe the claims
in light of the disclosed means for performing the recited functions and
the equivalents thereof. See In re Donaldson, 16 F.3d 1189 (Fed. Cir. 1994)
(in banc). Although Donaldson had not yet been decided when the Board
reached its decisions regarding these applications, it nonetheless
applied Sect. 112, paragraph 6 to both applications. It did so under
the guidance of our earlier holdings in Arrhythmia, 958 F.2d at 1060, and
Iwahashi, 888 F.2d at 1375, which reached the same result in the context
of Section 101. At oral argument, counsel for Trovato agreed that the
Donaldson holding did not impact this appeal.
The use of different claim formats does not necessarily diminish the
impact of Sect. 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 (citing In re Noll, 545 F.2d 141, 148, (CCPA 1976),
cert. denied, Dann v. Noll, 434 US 875 (1979)). In this case, the
additional claims 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 (Fed. Cir. 1989).
Similarly, in Abele, 684 F.2d at 907 (citations omitted), our predecessor
court noted:
The goal is to answer the question "What did applicant's 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, Sect. 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 Secgt. 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 (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 Sect. 112, paragraph 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:
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 ("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, are "drafted in illusory apparatus format".
Our result here comports with our recent decision in Alappat, 33 F.3d 1526.
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. Specific note was also made of the combination of
claimed elements from which the inventor formed a machine. Id. at 1544.
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, 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 worth 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 US at 185 ("This Court has undoubtedly recognized limits to
Sect. 101 and every discovery is not embraced within the statutory terms.").
As the "basic tools of scientific and technological work," Gottschalk v.
Benson, 409 US 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 Sect. 101. The decisions of
the Board are therefore
AFFIRMED.
FOOTNOTES:
{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.
{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.
{3} Similar claims of the parent of the '024 application were allowed,
and matured into U.S. Patent No. 4,949,277.
{4} See generally Richard Stern, Tales from the Algorithm War, 18 AIPLA
Quarterly Journal 371 (1991).