Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Status of Claims
Claims 1-5, 7-15, and 17-20 were rejected in the Final Office action mailed on 05/08/2025. Applicant’s amended claimset, entered on 07/31/2025, amends Claims 1 and 11 and cancels Claims 10 and 20. Herein this Final Office Action, Claims 1-5, 7-9, 11-15, and 17-19 are rejected.
Response to Arguments
Applicant’s arguments filed 07/31/2025, with respect to Rejections under 35 U.S.C. 101 for Claims 1-5, 7-9, 11-15, and 17-19, have been fully considered and are not persuasive.
Applicant argues on Page 8 that “As amended, claims 1 and 11 are directed to a technological improvement, at least inasmuch as a computing burden, associated with generation of vehicle itineraries, is reduced by one or more embodiments within the scope of the claims. As such, the claims are not directed to abstract subject matter.” Examiner does not agree.
Representative Claim 1 recites “a computational burden associated with the routing problem is lighter than a computational burden associated with the original routing problem.”
Examiner responds that the precise claim language references “a computational burden associated with the routing problem” (emphasis added). The broadest reasonable interpretation of “computational burden” includes a theoretical computational burden metric associated the routing problem. The “computational burden” characterizes the difficulty of solving the problem, and does not include the actual “computational burden” of solving the problem on a computer. This interpretation is further supported because the actual “original routing problem” is not actually solved on a computer. Thus, this limitation is not tied to execution on a computer, but merely used to define the “routing problem” as easier to solve than the “original routing problem.”
Additionally, actually reducing computational burden, does not necessarily ensure that the claims recite an improvement in the functioning of a computer under MPEP 2106.05(a). To demonstrate, Examiner provides a hypothetical example of a calculator performing 2+2+2+2+2+2 versus 2x6. The calculator could have reduced computational burden by performing different mathematical calculations that reach the same conclusion. However, both situations would likely be considered merely applying an abstract idea on a computer under MPEP 2106.05(f), which excludes determining an improvement in technology under MPEP 2106.05(a).
Applicant argues on Page 8 that “Moreover, even if the claims were alleged in any case to be directed to abstract subject matter - Applicant makes no concession - such subject matter is nonetheless integrated into a practical application. In particular, the claims recite a process for generation of itineraries that are provided to, and usable by, a vehicle to autonomously control its operations in an operating environment.”
Examiner first notes that Step 2A determines whether the claims are “directed to” an abstract idea by (prong 1) determining if the claim “recites” an abstract idea and (prong 2) determining if the recited additional elements integrate the recited abstract idea into a practical application. MPEP 2106. Thus, a claim that was “directed to” an abstract idea, by definition, is not integrated into a practical application, and a claim that is integrated into a practical application, by definition, is not “directed to” an abstract idea. Examiner will proceed assuming Applicant intended to present the hypothetical of if the claims “recited” an abstract idea.
Examiner responds that the specific claim language does not include actual implementation of autonomous vehicles, but instead limits the form of the itinerary such that “when” implemented by the vehicles, the vehicles would perform operations autonomously. Because this is a limitation on the information of the itinerary, the vehicles themselves are not additional elements and therefore cannot be additional elements that integrate the recited abstract idea into a practical application under MPEP 2106.
On Pages 8-9, Applicant argues that the claims are not directed to processes from “managing personal behavior or relationships or interactions between people” because the claims are concerned with the operations of an autonomous vehicle. Examiner does not agree.
Examiner first responds that the recited abstract idea has been categorized into the mathematical concepts, certain methods of organizing human activity, and mental processes groupings outlined in MPEP 2106.04(a)(2). Thus, Applicant would have to show that the entire claim does not recite each of the groupings in order to overcome the rejection.
MPEP 2106.04(a)(2)II states “Finally, the sub-groupings encompass both activity of a single person (for example, a person following a set of instructions or a person signing a contract online) and activity that involves multiple people (such as a commercial interaction), and thus, certain activity between a person and a computer (for example a method of anonymous loan shopping that a person conducts using a mobile phone) may fall within the ‘certain methods of organizing human activity’ grouping.” (Emphasis added).
As discussed in greater detail above and below, the “vehicle” is not an additional element, but merely referential in limiting the recited abstract idea (e.g. tracking routes of the vehicle, providing itineraries to the vehicle, or defining the itineraries as being capable of being used by the vehicle to perform operations). Put plainly, the claims are directed optimizing the business operations of a warehouse by solving a VRP, the steps of which can be categorized into each of the enumerated groupings of MPEP 2106.04(a)(2).
Applicant’s arguments filed 07/31/2025, with respect to Rejections under 35 U.S.C. 103 for Claims 1-5, 7-9, 11-15, and 17-19, have been fully considered and are not persuasive.
On Page 9, Applicant argues that Calder is of no relevance to the claims because the heat map in Calder enables human workers to better understand robot traffic, citing the abstract in Calder. Examiner does not agree.
Although Calder does mention the benefit of the heat map to human workers, Calder also uses the heat map to determine the route of the robots, as cited in the rejection. Specifically, ¶37 stating “FIG. 2 is a pictorial diagram depicting an illustrative traffic density guidance system. The traffic density guidance system 200 shown in FIG. 2 may be included as part of an inventory system such as the inventory system 100, The traffic density guidance system 200 may generate a traffic density map 204 based on present and/or historical mobile drive unit routes. The route data may be stored in a route data storage device 272 and accessed via a route planning server 274. The route planning server 274 may be provided to identify optimal routes for the mobile drive units with a workspace. The optimal routing may include consideration of the location of each mobile drive unit, the capabilities of the mobile drive units, inventory holders and/or items held by/in respective inventory holders, destination within the workspace for the items carried by the mobile drive unit (e.g., packing for shipment or transferring to another workspace), and other detectable characteristic of the inventory system or entity therein,” and ¶41 stating “ . . . the route planning server 274 generates or updates routes . . . the route planning server 274 may wirelessly transmit messages including route information to the mobile drive units.” Thus, examiner has shown the applicability of Calder to the instant claims and explicitly shown that updated itineraries are transmitted to the “mobile drive units.”
Additionally, Examiner notes that Applicant’s specification makes no claim that the heatmap used in the vehicle routing cannot be shown to a person.
On Pages 9-10, Applicant argues that Stadie fails to teach a first graph that is smaller in size that reduces the computational burden. Examiner does not agree.
Examiner responds that Stadie ¶145 explicitly teaches reducing the size of the graph to reduce processing load. Thus, the additional citation of Stadie teaches the amended limitations as discussed in greater detail below.
On Page 10, Applicant argues that because Calder is concerned with generating heat maps for human use and Stadie discloses heatmaps and graphs for robot use, the two references are concerned with fundamentally different principles and would not be obviously combined. Examiner does not agree.
Examiner responds that the heat map of Calder is for human and robot use (See ¶37 and ¶41 as discussed above). Additionally, the “heat,” representing traffic congestion at a grid point, of the heatmap in Stadie is “observed” or “learned” “using a variety of . . . techniques.” See ¶245. Thus, such intentional open-ended statement in Stadie (“using a variety of . . . techniques.”), would not preclude the heatmap of Calder, but instead would signal to a person of ordinary skill in the art to use any applicable heat map technique, including those disclosed in Calder. Further, both Calder and Stadie are directed towards route optimization in a warehouse picking environment. Thus, the rejection remains.
Claim Interpretation
Throughout Applicant’s claims and specification, Applicant refers to a “heat map” and “graph.” Examiner notes that these words are not necessarily a visual or graphical representation of data, but a description of the data itself. Such interpretation is consistent with Fig. 3-4d and ¶¶33-43 of the specification.
Throughout Applicant’s claims and specification, Applicant refers to a “one or more changes” in the operating environment. Such changes are not limited to a certain data structure, which is consistent with ¶21 of the specification.
Regarding Claim 1 specifically, Claim 1 recites “one or more changes that have occurred in a physical configuration on the operating environment” at lines 6-7.
Fig. 1 shows the figure below.
PNG
media_image1.png
498
614
media_image1.png
Greyscale
Specification ¶¶15-16 shows “[0015] With reference now to Figure 1, there is disclosed a simplified example of an operating environment 100 according to one embodiment of the invention. In an embodiment, the operating environment 100 may comprise a physical domain 102, one example of which is a warehouse. Note that while reference is made herein to a warehouse, and vehicles such as forklifts and trucks, that may operate in a warehouse, these references are provided for the purpose of illustration and are not intended to limit the scope of the invention in any way. [0016] In the example of Figure 1, the operating environment 100 may comprise one or more nodes 104, each of which may correspond to a respective physical location in the operating environment 100. As used herein, an ‘edge’ may refer to a path between nodes 104. In general, one or more vehicles 106, which may operate autonomously within the operating environment 100, may travel through and/or to one or more nodes 104 while carrying out one or more tasks which have been assigned to the vehicle(s) 106. The path taken by a vehicle 106 to a destination may be referred to herein as an ‘itinerary.’ As shown in Figure 1, an itinerary may comprise multiple hops 108, or a single hop 110. By way of illustration, a vehicle 106 may pick up cargo at one node 104, and deliver that cargo to one or more other nodes 104.” (Emphasis added). Therefore Fig. 1 and ¶¶15-16 shows that the “physical domain 102” includes “vehicles 106,” at a certain physical location, which travel along paths between “nodes 104,” which are physical locations. Thus, the broadest reasonable interpretation of “one or more changes that have occurred in a physical configuration on the operating environment” includes changes in the location of the vehicles or changes in the locations of the nodes which the vehicle will travel.
Claims 2-5, 7-9, 11-15, and 17-19 are interpreted consistently with the interpretation of Claim 1 above.
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
Claims 1-5, 7-9, 11-15, and 17-19 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention.
Claim 1 recites “A method, comprising: obtaining a group of historical itineraries by tracking routes of a vehicle in an operating environment, where each itinerary in the group of historical itineraries identifies [[a]] one of the routes previously taken by [[a]] the vehicle in [[an]] the operating environment, and the historical itineraries collectively define a portion of an original routing problem concerning the vehicle; . . .” (Emphasis added).
Specification ¶¶18-19 states “[0018] Planning the itinerary for a set of autonomous vehicles in warehouses is a challenging combinatorial problem due to the number of solutions in the search space, which is typically on the order of O(n!) solutions over n demanding tasks. This planning is a combinatorial optimization problem that stands for finding least-cost itineraries, or route, for all vehicles, where each task can only be assigned to one vehicle. In the literature, this problem is referred to as the Vehicle Routing Problem (VRP). Due to the complexity in finding high-quality solutions for this problem, an embodiment may reuse past itineraries to reduce the total computational effort by pruning the search space of solutions, as discussed in further detail below. [0019] Let a warehouse W and a shipping manifest that contains all available vehicles and all demanding tasks to be assigned. An embodiment may generate a reduced version of the original problem that accounts for the current dynamics of W to an optimization solver. To do so, an embodiment may create a heatmap H based on [1] a model M, [2] past itineraries P and [3] the current dynamics D of W. This heatmap may then be used to create an alternative graph G, which may be used for pruning the search space of solutions for the solver. One example embodiment is detailed below, and in Figure 2, which discloses a general flowchart which may be used to generate task assignment plans based on previously recorded itineraries.” (Emphasis added). In summary, Specification ¶¶18-19 shows that the original vehicle routing problem is defined by the tasks needing to be assigned to vehicles, and the warehouse. Specification ¶¶18-19 further shows that the past itineraries are used as part of the pruning process, which simplifies the original problem.
Specification ¶26 states “Thus, and with reference to the illustrative example of Figure 2, the original optimization problem, as a graph, may be transformed to a graph version with fewer edges and nodes than were in the original optimization problem [(i.e. the alternative graph)] and which may take into account past, or historical, itineraries, as well as current warehouse dynamics. Thus, the computational effort in solving a relatively smaller version of the original problem may become less expensive that solving a problem of the same size as the original problem and, in some cases, may be important for solving very-large scale problems. In some cases, a direct unique solution may be obtained from the use of the heat map.” (Emphasis added). In summary, Specification ¶26 shows that the alternative graph is created by incorporating historical itineraries into the original problem. Thus, the historical itineraries were not apart of the original problem.
Applicants original specification does not disclose that a portion of the original routing problem is “define[d by]” the historical itineraries collectively. Examiner notes that Fig. 4A-4B and Specification ¶41 further supports that the original routing problem, by definition, excludes the historical itineraries, the incorporation of which, via heatmap, defines the smaller routing problem, i.e. pruned graph. Therefore, Claim 1 is rejected under 35 U.S.C. 112(a).
Claims 2-5, 7-9, 11-15, and 17-19 are rejected via dependency or for reciting substantially similar limitations to the rejected Claim 1 discussed above.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-5, 7-9, 11-15, and 17-19 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Step 1
Claims 1-5 and 7-9 recite a method (i.e. a process) and Claims 11-15 and 17-19 recite non-transitory storage medium (i.e. a machine or manufacture). Therefore, Claims 1-5, 7-9, 11-15, and 17-19 all fall within the one of the four statutory categories of invention of 35 U.S.C. 101.
Step 2A, Prong One
Independent Claim 1 recites the abstract idea of:
“obtaining a group of historical itineraries by tracking routes of a vehicle in an operating environment, where each itinerary in the group of historical itineraries identifies [[a]] one of the routes previously taken by [[a]] the vehicle in [[an]] the operating environment, and the historical itineraries collectively define a portion of an original routing problem concerning the vehicle;
generating a heatmap using a model that aggregates the historical itineraries and one or more changes that have occurred in a physical configuration on the operating environment after past vehicle movements occurred following the historical itineraries;
deriving a first graph from the heatmap, wherein the first graph defines a routing problem that is smaller in size than the original routing problem and comprises a subset of the group of historical itineraries, and a computational burden associated with the routing problem is lighter than a computational burden associated with the original routing problem;
using the first graph to generate updated itineraries that account for the one or more changes in the physical configuration on the operating environment,
wherein the updated itineraries, when employed by the vehicle, enable the vehicle to autonomously perform operations in the operating environment;
providing one of the updated itineraries to the vehicle; and
performing a graph repair procedure when a starting node or a delivery node is disconnected in the first graph, wherein the graph repair procedure comprises:
running a minimum spanning algorithm to repeatedly insert an edge, thereby generating a second graph, while the second graph is infeasible; and
adding to the first graph an edge of the second graph, which connects disconnected nodes in the first graph, to generate a repaired graph.”
The limitations stated above are processes/ functions that under broadest reasonable interpretation covers (1) obtaining a group of historical routes traveled by tracking vehicles, (2) the historical routes define a VRP, (3) generating a heat map, (4) deriving and repairing a graph that is smaller than the original VRP (Examiner notes that the “computational burden associated with the routing problem” is merely a metric that relates to the complexity of the VRP, and does not necessitate the use of a computer to solving the VRP), and (5) updating itineraries (Examiner notes that the limitation of “when employed by the vehicle, enable the vehicle to autonomously perform operations in the operating environment” is a limitation on the information of the updated itineraries, and does not affirmatively include an autonomous vehicle as an additional element), (6) providing the updated itineraries to the vehicle (Examiner notes that providing information to a vehicle does not explicitly include the vehicle as an additional element, e.g. a step of “the vehicle receiving the itinerary and autonomously performing operations” is not included), all of which are mathematical relationships (i.e. heatmap, graph, and vehicle routing problem) and mathematical calculations (i.e. modeling a physical environment and graph repair algorithm), which are mathematical concepts, an abstract idea, under MPEP 2106.04(a)(2)I; commercial or legal interactions (i.e. running a warehouse by routing vehicles based on historical routes) and managing personal behavior or relationships or interaction between people (i.e. prescribing a route to be followed), which are certain methods of organizing human activity, an abstract idea, under MPEP 2106.04(a)(2)II; and observations (i.e. historical itineraries from tracking movement and graph repair algorithm), which are mental processes, an abstract idea, under MPEP 2106.04(a)(2)III. Therefore, Claim 1 recites an abstract idea.
Step 2A, Prong Two
The judicial exception is not integrated into a practical application because Claim 1 does not recite additional elements that would be analyzed to determine if the recited additional elements integrate the recited abstract idea into a practical application under MPEP 2106.04(d).
Step 2B
As discussed above with respect to Step 2A Prong Two, the claim does not recite additional elements. The same analysis applies here in Step 2B, i.e., there are not recited additional elements to provide an inventive concept or add significantly more under MPEP 2106.05.
Dependent Claims 2-5 and 7-10 recite the abstract idea of:
“wherein the heatmap comprises an adjacency matrix of cells containing values that each represent a parameter of a movement of a vehicle between two nodes in the operating environment” (Claim 2);
“wherein, in the first graph, an edge between two nodes of a pair of nodes exists if a corresponding cell in the heatmap has a value greater than a minimum threshold” (Claim 3);
“wherein the first graph generated based on historical edges includes fewer edges than a fully connected graph” (Claim 4);
“wherein a subset of historical itineraries is generated based on the changes that have occurred in the operating environment” (Claim 5);
“wherein all nodes of the repaired graph are connected by cheapest edges” (Claim 7);
“wherein one of unconnected nodes in the first graph represents a break in an itinerary for a vehicle that has been assigned a task involving movement of the vehicle to and/or from the unconnected node” (Claim 8); and
“wherein one of vehicles is an autonomous vehicle” (Claim 9).
Dependent Claims 2-5 and 7-9, have been given the full two-prong analysis including analyzing the further elements and limitations, both individually and in combination. When analyzed individually and in combination, these claims are also held to be patent ineligible under 35 U.S.C. 101. The further limitation of Claims 2-5 and 7-9 fail to establish claims that are not directed to an abstract idea because the further limitations (1) limit the data and structure of the heat map, (2) define the contents of the graph to including an edge, (3) the subset of itineraries are generated based on certain information, (4) a graph repair procedure, and (5) limit the type of vehicle described in the heatmap. Thus, the dependent claims merely limit the scope of the abstract idea recited in Claim 1 and do not introduce additional elements to be analyzed in Step 2A Prong 2 or Step 2B. Therefore, the dependent claims do not recite patent eligible subject matter.
Step 2A, Prong One
Independent Claim 11 recites the abstract idea of:
“obtaining a group of historical itineraries by tracking routes of a vehicle in an operating environment, where each itinerary in the group of historical itineraries identifies [[a]] one of the routes previously taken by [[a]] the vehicle in [[an]] the operating environment, and the historical itineraries collectively define a portion of an original routing problem concerning the vehicle;
generating a heatmap using a model that aggregates the historical itineraries and one or more changes that have occurred in a physical configuration on the operating environment after past vehicle movements occurred following the historical itineraries;
deriving a first graph from the heatmap, wherein the first graph defines a routing problem that is smaller in size than the original routing problem and comprises a subset of the group of historical itineraries, and a computational burden associated with the routing problem is lighter than a computational burden associated with the original routing problem;
using the first graph to generate updated itineraries that account for the one or more changes in the physical configuration on the operating environment,
wherein the updated itineraries, when employed by the vehicle, enable the vehicle to autonomously perform operations in the operating environment;
providing one of the updated itineraries to the vehicle; and
performing a graph repair procedure when a starting node or a delivery node is disconnected in the first graph, wherein the graph repair procedure comprises:
running a minimum spanning algorithm to repeatedly insert an edge, thereby generating a second graph, while the second graph is infeasible; and
adding to the first graph an edge of the second graph, which connects disconnected nodes in the first graph, to generate a repaired graph.”
The limitations stated above are processes/ functions that under broadest reasonable interpretation covers (1) obtaining a group of historical routes traveled by tracking vehicles, (2) the historical routes define a VRP, (3) generating a heat map, (4) deriving and repairing a graph that is smaller than the original VRP (Examiner notes that the “computational burden associated with the routing problem” is merely a metric that relates to the complexity of the VRP, and does not necessitate the use of a computer to solving the VRP), and (5) updating itineraries (Examiner notes that the limitation of “when employed by the vehicle, enable the vehicle to autonomously perform operations in the operating environment” is a limitation on the information of the updated itineraries, and does not affirmatively include an autonomous vehicle as an additional element), (6) providing the updated itineraries to the vehicle (Examiner notes that providing information to a vehicle does not explicitly include the vehicle as an additional element, e.g. a step of “the vehicle receiving the itinerary and autonomously performing operations” is not included), all of which are mathematical relationships (i.e. heatmap, graph, and vehicle routing problem) and mathematical calculations (i.e. modeling a physical environment and graph repair algorithm), which are mathematical concepts, an abstract idea, under MPEP 2106.04(a)(2)I; commercial or legal interactions (i.e. running a warehouse by routing vehicles based on historical routes) and managing personal behavior or relationships or interaction between people (i.e. prescribing a route to be followed), which are certain methods of organizing human activity, an abstract idea, under MPEP 2106.04(a)(2)II; and observations (i.e. historical itineraries from tracking movement and graph repair algorithm), which are mental processes, an abstract idea, under MPEP 2106.04(a)(2)III.
If a claim limitation, under its broadest reasonable interpretation, covers “mathematical relationships,” “mathematical calculations,” “commercial or legal interactions,” “managing personal behavior or relationships or interactions between people,” and “observations,” but for the recitation of generic computer components or other machinery merely used as a tool to apply the abstract idea, then it falls in these groupings of abstract ideas. MPEP 2106.04. Therefore, Claim 11 recites an abstract idea.
Step 2A, Prong Two
The judicial exception is not integrated into a practical application. Claim 11 as a whole amounts to: (i) merely invoking generic components as a tool to perform the abstract idea or “apply it” (or an equivalent) and (ii) generally links the use of a judicial exception to a particular technological environment or field of use. The claim recites the additional elements of:
(i) “non-transitory storage medium” and
(ii) “hardware processors.”
The additional element of (i) “non-transitory storage medium” (Fig. 5 and ¶70 shows “memory 502”) and (ii) “hardware processors” (Fig. 5 and ¶70 shows “one or more hardware processors 506”), are recited at a high-level of generality, such that, when viewed as whole/ordered combination (Fig. 5), they amount to no more than mere instruction to apply the judicial exception using generic machinery as a tool in its ordinary capacity or “apply it” (See MPEP 2106.05(f)).
The (i) “non-transitory storage medium” and (ii) “hardware processors” when viewed as whole/ordered combination (Fig. 5), does no more than generally link the use of the judicial exception to a particular technological environment or field of use (i.e. warehouse picking management) (See MPEP 2106.05(h)).
Accordingly, these additional elements, when viewed as a whole/ordered combination (Fig. 5), do not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. Thus, the claim is directed to an abstract idea.
Step 2B
As discussed above with respect to Step 2A Prong Two, the additional elements amount to no more than: (i) “apply it” (or an equivalent) and (ii) generally link the use of a judicial exception to a particular technological environment or field of use, and are not a practical application of the abstract idea. The same analysis applies here in Step 2B, i.e., (i) merely invoking the generic components as a tool to perform the abstract idea or “apply it” (See MPEP 2106.05(f)) and (ii) generally linking the use of a judicial exception to a particular technological environment or field of use (See MPEP 2106.05(h)), does not integrate the abstract idea into a practical application at Step 2A or provide an inventive concept at Step 2B.
Therefore, the additional elements of (i) “non-transitory storage medium” and (ii) “hardware processors” do not integrate the abstract idea into a practical application at Step 2A or provide an inventive concept at Step 2B. Thus, even when viewed as a whole/ordered combination (Fig. 5), nothing in the claims adds significantly more (i.e., an inventive concept) to the abstract idea. Thus, the claim is ineligible.
Dependent Claims 12-15 and 17-19 recite the abstract idea of:
“wherein the heatmap comprises an adjacency matrix of cells containing values that each represent a parameter of a movement of a vehicle between two nodes in the operating environment” (Claim 12);
“wherein, in the first graph, an edge between two nodes of a pair of nodes exists if a corresponding cell in the heatmap has a value greater than a minimum threshold” (Claim 13);
“wherein the first graph generated based on historical edges includes fewer edges than a fully connected graph” (Claim 14);
“wherein a subset of historical itineraries is generated based on the changes that have occurred in the operating environment” (Claim 15);
“wherein all nodes of the repaired graph are connected by cheapest edges” (Claim 17);
“wherein one of unconnected nodes in the first graph represents a break in an itinerary for a vehicle that has been assigned a task involving movement of the vehicle to and/or from the unconnected node” (Claim 18);
“wherein one of vehicles is an autonomous vehicle” (Claim 19).
Dependent Claims 12-15 and 17-19, have been given the full two-prong analysis including analyzing the further elements and limitations, both individually and in combination. When analyzed individually and in combination, these claims are also held to be patent ineligible under 35 U.S.C. 101. The further limitation of Claims 12-15 and 17-19 fail to establish claims that are not directed to an abstract idea because the further limitations 1) limit the data and structure of the heat map, (2) define the contents of the graph to including an edge, (3) the subset of itineraries are generated based on certain information, (4) a graph repair procedure, and (5) limit the type of vehicle described in the heatmap. The elements of Claims 12-15 and 17-19 fails to establish claims that are not directed to an abstract idea because the elements merely recite additional generic computer components used in its ordinary capacity similar to the generic computer components used in its ordinary capacity of Claim 11 and generally link the abstract idea to a particular technology or field of use (i.e. warehouse picking management) just as in Claim 11. The organization of the further limitations of Claims 12-15 and 17-19 fail to integrate an abstract idea into a practical application just as discussed above for Claim 11. Additionally, performing the abstract idea of Claim 11 as recited in each of the further limitations of Claims 12-15 and 17-19, individually or in combination, does not (1) impose any meaningful limits on practicing the abstract ideas, or (2) provide improvements to the functioning of computing systems or to another technology or technical field, just as discussed above regarding Claim 11. Therefore, Claims 12-15 and 17-19 amount to mere instructions to implement the abstract idea (1) using generic computer components—using the computer, in its ordinary capacity, as a tool to perform the abstract idea, and (2) generally linked to a particular technology or field of use. Because the claims merely use a computer, in its ordinary capacity in a particular field of use, as a tool to perform the abstract idea cannot provide an inventive concept, the elements and limitations of Claims 12-15 and 17-19 fail to establish that the claims provide an inventive concept, just as in Claim 11. Therefore, Claims 12-15 and 17-19 fails the Subject Matter Eligibility Test and are consequently rejected under 35 U.S.C. 101.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-4, 7-9, 11-14, and 17-19 are rejected under 35 U.S.C. 103 as being unpatentable over WO-2018052853-A1 ("Calder") in view of US-20180075402-A1 (“Stadie”) and “A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges” (“Bader” December, 2022, Journal of Graph Algorithms and Applications vol. 26, no. 4, pp. 577–588, https://jgaa.info/index.php/jgaa/article/download/paper609/2352/2159).
Regarding Claim 1, Calder teaches “A method, comprising:”
“obtaining a group of historical itineraries by tracking routes of a vehicle in an operating environment, where each itinerary in the group of historical itineraries identifies [[a]] one of the routes previously taken by [[a]] the vehicle in [[an]] the operating environment” (Fig. 1 and ¶20 shows “an illustrative inventory system environment” (i.e. operating environment) including “mobile drive unit 120” (i.e. vehicle) which “may transport one or more of the inventory holders 130 between points [(i.e. a route taken)] within a workspace 170 in response to commands communicated by the management device 115.” ¶24 shows “The mobile drive unit 120 may then interpret the commands to activate wheels to move along the route, position sensors and/or cameras to detect location and obstacles, and motors or robotic arms to lift the inventory holder.” Fig. 2 and ¶46 shows “The route density analyzer 252 may also obtain historical route information for the workspace. The historical route information may identify routes previously traversed by mobile drive units within the workspace.” (Emphasis added). Fig. 2 and ¶37 shows “The traffic density guidance system 200 may generate a traffic density map 204 based on present and/or historical mobile drive unit routes [(i.e. group of historical itineraries)]. The route data may be stored in a route data storage device 272 and accessed via a route planning server 274.”), and
“generating a heatmap using a model that aggregates the historical itineraries and one or more changes that have occurred in a physical configuration on the operating environment after past vehicle movements occurred following the historical itineraries” (¶16 shows that “One example of a traffic density map is a color coded congestion heat map. . . The traffic density map may be generated through analysis of planned routes for the mobile drive units within the workspace, and may be displayed to human workers. The analysis may include consideration of one or more of: currently planned routes, historical routes [(i.e. historical itineraries)], and any updates to planned routes [(i.e. one or more changes)].” Fig. 2 and ¶37 shows “The traffic density guidance system 200 may generate a traffic density map 204 [(i.e. heat map)] based on present [(i.e. updated, including changes)] and/or historical mobile drive unit routes [(i.e. historical itineraries)]. The route data may be stored in a route data storage device 272 and accessed via a route planning server 274.” See also Fig. 2, 4, ¶¶41-45, and ¶¶70-77 showing the generation of “traffic density map 204” with the “mapping server 250,” “route density analyzer 252,” and “route planning server 274” at “block 420.” See also Fig. 3A-3C and ¶¶52-58 showing example density maps. ¶49 shows “The mapping server 250 may also obtain information about the mobile drive unit 120 and/or tasks associated with the mobile drive unit from the management device 115. For example, the management device 115 may provide the current location and/or operational status of a mobile drive unit. This information may be used to generate density information and/or additional graphic output to provide guidance.” (Emphasis added). ¶39 shows “A control element may be provided that, when activated, refreshes the traffic density map 240 based on currently available route information, The refreshing of the map provides a real time presentation of the density information for the currently planned mobile drive units.” (Emphasis added). The updating and refreshing of the map based on the updated current location of mobile unit teaches “one or more changes that have occurred in a physical configuration on the operating environment.”); and
“. . . to generate updated itineraries that account for the one or more changes in the physical configuration on the operating environment.” (¶41 shows “the route planning server 274 generates or updates routes. . . the route planning server 274 may wirelessly transmit messages including route information to the mobile drive units.” ¶82 shows an example of changing a route by slowing down or navigating to a new location when it is detected that a human is near the mobile unit.)
“wherein the updated itineraries, when employed by the vehicle, enable the vehicle to autonomously perform operations in the operating environment” (¶41 shows “the route planning server 274 generates or updates routes. . . the route planning server 274 may wirelessly transmit messages including route information to the mobile drive units.” ¶13 shows “Modern inventory systems may include mobile drive units that receive commands to perform tasks such moving to a location, lifting a payload at the location, and carrying the payload to another location. A mobile drive unit may be an autonomous asset, such as a robot or a drone, and may include sensors to detect aspects of an operational area in which it is being implemented and execute received commands.”);
“providing one of the updated itineraries to the vehicle” (¶18 shows “The traffic density map may be updated such as every 20 seconds.” Fig. 2 and ¶37 shows “FIG. 2 is a pictorial diagram depicting an illustrative traffic density guidance system. The traffic density guidance system 200 shown in FIG. 2 may be included as part of an inventory system such as the inventory system 100, The traffic density guidance system 200 may generate a traffic density map 204 based on present and/or historical mobile drive unit routes. The route data may be stored in a route data storage device 272 and accessed via a route planning server 274. The route planning server 274 may be provided to identify optimal routes for the mobile drive units with a workspace. The optimal routing may include consideration of the location of each mobile drive unit, the capabilities of the mobile drive units, inventory holders and/or items held by/in respective inventory holders, destination within the workspace for the items carried by the mobile drive unit (e.g., packing for shipment or transferring to another workspace), and other detectable characteristic of the inventory system or entity therein.” ¶41 shows “ . . . the route planning server 274 generates or updates routes . . . the route planning server 274 may wirelessly transmit messages including route information to the mobile drive units.” See also ¶77, ¶86, and ¶97 showing updating route information.).
Calder does not explicitly teach, but Stadie teaches
“the historical itineraries collectively define a portion of an original routing problem concerning the vehicle” (¶85 and ¶89 shows “[0085] The various movements of the robots, placement of containers/objects, and control over selecting when to remove product from containers may be controlled and optimised by one or more control systems. This control may include the implementation of various strategies, including, for example: . . . [0089] Path optimisation [(i.e. routing problem)] through the application of one or more heuristic techniques to the one or more path finding algorithms (e.g. projected lowest cost, where in one embodiment of the invention, cost may be calculated as a function of total time to target, and total “accumulated heat” for congestion mitigation on the grid when viewed as a whole); . . .” (Emphasis added). ¶241 shows “In developing a heat-map, a ‘heat’ value may be assigned to each coordinate, approximating a model of congestion at points on the grid, or for particular areas of the grid.” (Emphasis added). ¶245 shows “In some embodiments, the ‘heat’ value may be determined using proximity to workstations, but in other embodiments of the invention, the ‘heat’ may be observed/learned/calculated/predicted using a variety of other techniques, some of which may be dynamic or iterative techniques.” (Emphasis added). Thus, the “heat” teaches historical itineraries that define a portion of an original routing problem.);
“deriving a first graph from the heatmap, wherein the first graph defines a routing problem that is smaller in size than the original routing problem and comprises a subset of the group of historical itineraries, and a computational burden associated with the routing problem is lighter than a computational burden associated with the original routing problem” (¶236 shows “In an embodiment of the invention, each search may track the current lowest cost branch and weighted cost functions may be used to bias the selection ordering of the branches based upon various heuristics, which may include: (a) a projected shortest path time and (b) a projected accumulated heat based on a heat-map. Other heuristic techniques may be contemplated but for illustrative purposes, further detail will be provided for the two identified above.” ¶208 shows “A number of different algorithms and techniques may be used in determining a preferential path for a robot to take, including, but not limited to: branch and bound algorithms, constraint programming, local search, heuristics, graph-traversal, dynamic path learning advisor techniques, pruning techniques and Bayesian graph searching techniques, Dijikstra's algorithm, Bellman-Ford algorithm, Floyd-Warshall algorithm, Johnson's algorithm, breadth-first recursive searches and depth-first recursive searches, weighted paths, A* search algorithm, variants on A* search algorithm (e.g. D*, Field D*, IDA*, Fringe, Fringe Saving A*, Generalized Adaptive A*, Lifelong Planning A*, Simplified Memory Bounded A*, Jump Point Search, Theta*).” (Emphasis added). ¶241 shows “In developing a heat-map, a ‘heat’ value may be assigned to each coordinate, approximating a model of congestion at points on the grid, or for particular areas of the grid.” (Emphasis added). ¶245 shows “In some embodiments, the ‘heat’ value may be determined using proximity to workstations, but in other embodiments of the invention, the ‘heat’ may be observed/learned/calculated/predicted using a variety of other techniques, some of which may be dynamic or iterative techniques.” (Emphasis added). Therefore, Stadie teaches that other techniques, such as those of Calder, can be used to calculate “heat.” Therefore, in using one of the “graph” based algorithms of ¶208, the “graph” would be derived from the “heat map.” See also Fig. 4-6b and ¶¶233-55 further showing an example of the algorithm. Because ¶236 shows that “branches” are “based on the heat map” and ¶208 shows several “graph” based algorithms as an alternative to the example “branch and bound” algorithm, Stadie teaches deriving a graph from the heatmap. Additionally, Fig. 5, with the context of ¶44 and ¶¶235-52, shows a “Current Branch” comprising multiple possible paths of “Projected Path 1,” “Projected Path 2,” and “Projected Path 3” (i.e. graph comprising a subset of the group of historical routes) overlayed on the “heat map” with relevant parameters such as “time” and “heat” values for each branch and path. ¶145 shows “In some embodiments, the grid may be pre-processed by the movement optimisation module 304 to potentially increase processing speed and/or reduce processing load [(i.e. lighter computational load)]. Other methods of reducing processing load are also contemplated, such as reducing the depth/breadth of searching, dividing the grid into sub-grids, distributed processing, caching future routes, computationally simplifying the grid (e.g. reducing the number of nodes under analysis), reducing path re-calculation, etc.” See also ¶¶90-97 shows pre-processing certain aspects of the optimization.); and
“. . . to generate updated itineraries . . .” includes “using the first graph to generate updated itineraries . . .” (¶208 shows “A number of different algorithms and techniques may be used in determining a preferential path for a robot to take, including, but not limited to: branch and bound algorithms, constraint programming, local search, heuristics, graph-traversal, dynamic path learning advisor techniques, pruning techniques and Bayesian graph searching techniques, Dijikstra's algorithm, Bellman-Ford algorithm, Floyd-Warshall algorithm, Johnson's algorithm, breadth-first recursive searches and depth-first recursive searches, weighted paths, A* search algorithm, variants on A* search algorithm (e.g. D*, Field D*, IDA*, Fringe, Fringe Saving A*, Generalized Adaptive A*, Lifelong Planning A*, Simplified Memory Bounded A*, Jump Point Search, Theta*).” (Emphasis added). At least the emphasized algorithms and techniques of ¶208 show “graph” based algorithms used to determine a path. See also ¶¶256-60 showing adjusting a robot’s path.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Stadie with Calder because Stadie teaches an optimization of vehicle routing based upon heat map improves the coordination and control of the movement of robots handing the fulfillment goods (¶¶11-36, ¶¶81-82, and ¶¶109-11). Thus, combining Stadie with Calder furthers the interest taught in Stadie, and therefore, would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention.
Calder and Stadie do not explicitly teach, but Ba