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 Bader teaches
“performing a graph repair procedure when a starting node or a delivery node is disconnected in the first graph” (Abstract on Page 577 shows in real world application, such as a transportation network (i.e. a network of paths for vehicles to travel), a replacement edge for the graph which represents the network must be determined when the real world network becomes disconnected (e.g. a traffic accident closes a road). The replacement edge completes the “minimum spanning tree,” which is a tree that optimally connects the vertices (i.e. nodes) of the 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” (Abstract on Page 577 shows am algorithm to identify a replacement edge to complete the minimum spanning tree (i.e. a minimum spanning algorithm). Page 580 shows “This paper introduces an algorithm that reduces the cost to O(m + n) time by a novel use of a special case of the disjoint set union data structure. We use the disjoint sets [(i.e. second infeasible graph)] for fast path compression based on the Gabow-Tarjan static union tree method [7, 8].” Page 580 Shows “The m− n + 1 remaining edges in E\ET are scanned in ascending order [(i.e. repeatedly inserting an edge)] by weight, inspecting the tree edges in each corresponding fundamental cycle. In this order, the first time a tree edge e is included in a fundamental cycle, its replacement Re is set to the non-tree edge from that cycle. As we will describe, the disjoint sets provide subpath compression as replacement edges are assigned to MST edges.” See also Example 3.1 on Pages 583-84.); 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” (Page 580 Shows “The m− n + 1 remaining edges in E\ET are scanned in ascending order by weight, inspecting the tree edges in each corresponding fundamental cycle. In this order, the first time a tree edge e is included in a fundamental cycle, its replacement Re is set to the non-tree edge from that cycle. As we will describe, the disjoint sets provide subpath compression as replacement edges are assigned to MST edges.” (Emphasis added). See also Example 3.1 on Pages 583-84.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Bader with Calder and Stadie because Stadie updates the paths based on updated conditions (¶144) and Bader maintains a transportation graph based on changes to the physical transportation network (Abstract on Page 577). Thus, combining Bader with Calder and Stadie furthers the interest taught in Bader, and therefore, would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention.
Regarding Claim 2, Calder, Stadie, and Bader teach “The method as recited in claim 1,” as discussed above.
Calder further teaches “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” (The broadest reasonable interpretation of “a parameter of movement of a vehicle” read in light of the specification (Fig. 3 and ¶33) includes the geometric path which the vehicle moves. Calder ¶16 shows that “One example of a traffic density map is a color coded congestion heat map.” Fig. 3A-3C, ¶¶6-8, and ¶52 shows “FIG. 3A[-3C are] a pictorial diagram depicting an illustrative traffic density map . . . The workspace is partitioned into a map 302 including three rows and three columns where each cell represents a sector of the workspace” (i.e. the heatmap comprises an adjacency matrix of cells). Fig. 3A-3C and ¶¶52-57 shows that each “cell” contains a “value” represented of the number of planned routes which travel through the sector represented by the cell (i.e. a parameter of a movement of a vehicle). ¶58 shows how historical routes are incorporated into the density map. ¶59 shows that the routes analyzed for the density map may be limited to a certain time domain. See also ¶15 showing “One example of a traffic density map is a color coded congestion heat map. The congestion heat map may be colored red in areas where more robots are planning to go and a gradient from red to orange/yellow/green may be used to color areas with less expected traffic. 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, and any updates to planned routes.” and ¶18 showing “The traffic density map may include graphical representations of the current locations of mobile drive units within the workspace. The graphical representations may be color coded to indicate an operational status of mobile drive unit such as idle, charging, moving, moving with item, malfunction, speed, etc. The graphical representations may include an icon such as an arrow to show the direction a mobile drive unit is moving or other operational status.”).
Regarding Claim 3, Calder, Stadie, and Bader teach “The method as recited in claim 2,” as discussed above.
Calder further teaches “wherein, . . . , [a route] between two nodes of a pair of nodes exists if a corresponding cell in the heatmap has a value greater than a minimum threshold” (Fig. 3A-3C and ¶¶52-58 shows that cells with a value of zero do not contain a path and cells with a value greater than zero do contain a path. Specifically, Fig. 3B and ¶53 shows “the second map 312 includes a representation of a first route 316 for a mobile drive unit[,and t]he first route 316 includes endpoints 318 and 320 representing terminal points of the first route 316” (i.e. a route between two nodes of a pair of nodes). Therefore, Calder teaches that a route exists if a corresponding cell in the heatmap has a value greater than a minimum threshold (i.e. greater than zero).).
Calder does not explicitly teach, but Stadie further teaches that “[a route] between two nodes of a pair of nodes exists” includes “in the first graph, an edge between two nodes of a pair of nodes exists” (As discussed in greater detail above, Fig. 5 shows a “Current Branch” comprising multiple possible paths of “Projected Path 1,” “Projected Path 2,” and “Projected Path 3” (i.e. graph). Therefore, Stadie teaches that the route (i.e. edge) exists in the “graph.” A “route” is referred to as an “edge” in the context of “graph theory” algorithms.).
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 using “graph” algorithms 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.
Regarding Claim 4, Calder, Stadie, and Bader teach “The method as recited in claim 1,” as discussed above.
Calder does not explicitly teach, but Stadie further teaches “wherein the first graph generated based on historical edges includes fewer edges than a fully connected graph” (As discussed in greater detail above, Fig. 5 shows a “Current Branch” comprising multiple possible paths of “Projected Path 1,” “Projected Path 2,” and “Projected Path 3” (i.e. graph). The three potential paths shown in the graph of Fig . 5 is less than a fully connected graph.).
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 using “graph” algorithms 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.
Regarding Claim 7, Calder, Stadie, and Bader teach “The method as recited in claim 1,” as discussed above.
Calder and Stadie do not explicitly teach, but Bader further teaches “wherein all nodes of the repaired graph are connected by cheapest edges” (Abstract on Page 577 shows that the “minimum spanning tree” connects each of the vertices of the graph with the lowest sum of edge weight and “the replacement edge [(i.e. graph repair)] may reconnect the MST at lowest cost [(i.e. cheapest)].”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Bader with Calder and Stadie because Stadie updates the paths based on updated conditions (¶144) and Bader maintains a transportation graph based on changes to the physical transportation network (Abstract on Page 577). Thus, combining Bader with Calder and Stadie furthers the interest taught in Bader, and therefore, would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention.
Regarding Claim 8, Calder, Stadie, and Bader teach “The method as recited in claim 7,” as discussed above.
Calder does not explicitly teach, but Stadie teaches “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” (¶145 indicates the “grid” is a series of nodes by showing “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.” ¶144 shows “the movement optimization module 304 may dynamically recalculate preferential paths during the course of a robot's journey to potentially determine an updated set of paths as conditions and constraints change over time.” ¶¶176-84 shows a “clearance module 312” which functions as a collision avoidance system between robots and allows of dynamic re-planning of routes to resolve or avoid conflict. The changing of the path of the robot discussed in ¶144 and ¶¶176-84 teaches a break in an itinerary for a vehicle that has been assigned a task involving movement of the vehicle to a certain node. As discussed in greater detail above, Fig. 5 shows a “Current Branch” comprising multiple possible paths of “Projected Path 1,” “Projected Path 2,” and “Projected Path 3” on the grid (i.e. series of nodes). As is demonstrated by Fig. 5 the selection of one path over another (i.e. switching from “Projected Path 1” to “Projected Path 2”) in ¶144 and ¶¶176-84 teaches disconnecting (i.e. unconnect[ing]) from certain nodes (i.e. disconnecting from the first node of “Projected Path 1” in order to connect to the first node of “Projected Path 2.” See also ¶227 showing “Where a new branch has a conflict with a path that another robot may be taking, or conflicts with an idle robot, the search algorithm may: Alter the branch to outrun the conflicting reservation (if acceleration profile allows); Alter the branch to contain a wait at any position along its path; or Discard the branch as infeasible.”).
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 using “graph” algorithms 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.
Regarding Claim 9, Calder, Stadie, and Bader teach “The method as recited in claim 1,” as discussed above.
Calder further teaches “wherein one of vehicles is an autonomous vehicle” (¶13 shows “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.”).
Regarding Claim 11, Calder teaches “A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations” (Fig.5-6 and ¶80 shows “The management device 115 may include one or more processors 518, one or more memory devices, such as computer readable media 520, a messaging controller 522, a main safety controller 524, an input/output interface 526, an alarm system 528, a transceiver 530, or any combination thereof. The computer readable media 520 may include instructions 532 that are executable by the processors 518 to perform the various functions of the management device 115.” See also Fig. 7 and ¶95 showing “computing device 700”) “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.”);
“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 Bader teaches
“performing a graph repair procedure when a starting node or a delivery node is disconnected in the first graph” (Abstract on Page 577 shows in real world application, such as a transportation network (i.e. a network of paths for vehicles to travel), a replacement edge for the graph which represents the network must be determined when the real world network becomes disconnected (e.g. a traffic accident closes a road). The replacement edge completes the “minimum spanning tree,” which is a tree that optimally connects the vertices (i.e. nodes) of the 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” (Abstract on Page 577 shows am algorithm to identify a replacement edge to complete the minimum spanning tree (i.e. a minimum spanning algorithm). Page 580 shows “This paper introduces an algorithm that reduces the cost to O(m + n) time by a novel use of a special case of the disjoint set union data structure. We use the disjoint sets [(i.e. second infeasible graph)] for fast path compression based on the Gabow-Tarjan static union tree method [7, 8].” Page 580 Shows “The m− n + 1 remaining edges in E\ET are scanned in ascending order [(i.e. repeatedly inserting an edge)] by weight, inspecting the tree edges in each corresponding fundamental cycle. In this order, the first time a tree edge e is included in a fundamental cycle, its replacement Re is set to the non-tree edge from that cycle. As we will describe, the disjoint sets provide subpath compression as replacement edges are assigned to MST edges.” See also Example 3.1 on Pages 583-84.); 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” (Page 580 Shows “The m− n + 1 remaining edges in E\ET are scanned in ascending order by weight, inspecting the tree edges in each corresponding fundamental cycle. In this order, the first time a tree edge e is included in a fundamental cycle, its replacement Re is set to the non-tree edge from that cycle. As we will describe, the disjoint sets provide subpath compression as replacement edges are assigned to MST edges.” (Emphasis added). See also Example 3.1 on Pages 583-84.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Bader with Calder and Stadie because Stadie updates the paths based on updated conditions (¶144) and Bader maintains a transportation graph based on changes to the physical transportation network (Abstract on Page 577). Thus, combining Bader with Calder and Stadie furthers the interest taught in Bader, and therefore, would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention.
Regarding Claim 12, Calder, Stadie, and Bader teach “The non-transitory storage medium as recited in claim 11,” as discussed above.
Calder further teaches “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” (The broadest reasonable interpretation of “a parameter of movement of a vehicle” read in light of the specification (Fig. 3 and ¶33) includes the geometric path which the vehicle moves. Calder ¶16 shows that “One example of a traffic density map is a color coded congestion heat map.” Fig. 3A-3C, ¶¶6-8, and ¶52 shows “FIG. 3A[-3C are] a pictorial diagram depicting an illustrative traffic density map . . . The workspace is partitioned into a map 302 including three rows and three columns where each cell represents a sector of the workspace” (i.e. the heatmap comprises an adjacency matrix of cells). Fig. 3A-3C and ¶¶52-57 shows that each “cell” contains a “value” represented of the number of planned routes which travel through the sector represented by the cell (i.e. a parameter of a movement of a vehicle). ¶58 shows how historical routes are incorporated into the density map. ¶59 shows that the routes analyzed for the density map may be limited to a certain time domain. See also ¶15 showing “One example of a traffic density map is a color coded congestion heat map. The congestion heat map may be colored red in areas where more robots are planning to go and a gradient from red to orange/yellow/green may be used to color areas with less expected traffic. 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, and any updates to planned routes.” and ¶18 showing “The traffic density map may include graphical representations of the current locations of mobile drive units within the workspace. The graphical representations may be color coded to indicate an operational status of mobile drive unit such as idle, charging, moving, moving with item, malfunction, speed, etc. The graphical representations may include an icon such as an arrow to show the direction a mobile drive unit is moving or other operational status.”).
Regarding Claim 13, Calder, Stadie, and Bader teach “The non-transitory storage medium as recited in claim 12,” as discussed above.
Calder further teaches “wherein, . . . , [a route] between two nodes of a pair of nodes exists if a corresponding cell in the heatmap has a value greater than a minimum threshold” (Fig. 3A-3C and ¶¶52-58 shows that cells with a value of zero do not contain a path and cells with a value greater than zero do contain a path. Specifically, Fig. 3B and ¶53 shows “the second map 312 includes a representation of a first route 316 for a mobile drive unit[,and t]he first route 316 includes endpoints 318 and 320 representing terminal points of the first route 316” (i.e. a route between two nodes of a pair of nodes). Therefore, Calder teaches that a route exists if a corresponding cell in the heatmap has a value greater than a minimum threshold (i.e. greater than zero).).
Calder does not explicitly teach, but Stadie further teaches that “[a route] between two nodes of a pair of nodes exists” includes “in the first graph, an edge between two nodes of a pair of nodes exists” (As discussed in greater detail above, Fig. 5 shows a “Current Branch” comprising multiple possible paths of “Projected Path 1,” “Projected Path 2,” and “Projected Path 3” (i.e. graph). Therefore, Stadie teaches that the route (i.e. edge) exists in the “graph.” To further aid in understanding the language of Stadie, Examiner points to Zander cited in the conclusion section, which may provide context that supports Examiner’s application of Stadie. For example, a “route” is referred to as an “edge” in the context of “graph theory” algorithms.).
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 using “graph” algorithms 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.
Regarding Claim 14, Calder, Stadie, and Bader teach “The non-transitory storage medium as recited in claim 11,” as discussed above.
Calder does not explicitly teach, but Stadie further teaches “wherein the first graph generated based on historical edges includes fewer edges than a fully connected graph” (As discussed in greater detail above, Fig. 5 shows a “Current Branch” comprising multiple possible paths of “Projected Path 1,” “Projected Path 2,” and “Projected Path 3” (i.e. graph). The three potential paths shown in the graph of Fig . 5 is less than a fully connected graph.).
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 using “graph” algorithms 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.
Regarding Claim 17, Calder, Stadie, and Bader teach “The non-transitory storage medium as recited in claim 11,” as discussed above.
Calder and Stadie do not explicitly teach, but Bader further teaches “wherein all nodes of the repaired graph are connected by cheapest edges” (Abstract on Page 577 shows that the “minimum spanning tree” connects each of the vertices of the graph with the lowest sum of edge weight and “the replacement edge [(i.e. graph repair)] may reconnect the MST at lowest cost [(i.e. cheapest)].”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Bader with Calder and Stadie because Stadie updates the paths based on updated conditions (¶144) and Bader maintains a transportation graph based on changes to the physical transportation network (Abstract on Page 577). Thus, combining Bader with Calder and Stadie furthers the interest taught in Bader, and therefore, would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention.
Regarding Claim 18, Calder, Stadie, and Bader teach “The non-transitory storage medium as recited in claim 17,” as discussed above.
Calder does not explicitly teach, but Stadie teaches “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” (¶145 indicates the “grid” is a series of nodes by showing “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.” ¶144 shows “the movement optimization module 304 may dynamically recalculate preferential paths during the course of a robot's journey to potentially determine an updated set of paths as conditions and constraints change over time.” ¶¶176-84 shows a “clearance module 312” which functions as a collision avoidance system between robots and allows of dynamic re-planning of routes to resolve or avoid conflict. The changing of the path of the robot discussed in ¶144 and ¶¶176-84 teaches a break in an itinerary for a vehicle that has been assigned a task involving movement of the vehicle to a certain node. As discussed in greater detail above, Fig. 5 shows a “Current Branch” comprising multiple possible paths of “Projected Path 1,” “Projected Path 2,” and “Projected Path 3” on the grid (i.e. series of nodes). As is demonstrated by Fig. 5 the selection of one path over another (i.e. switching from “Projected Path 1” to “Projected Path 2”) in ¶144 and ¶¶176-84 teaches disconnecting (i.e. unconnect[ing]) from certain nodes (i.e. disconnecting from the first node of “Projected Path 1” in order to connect to the first node of “Projected Path 2.” See also ¶227 showing “Where a new branch has a conflict with a path that another robot may be taking, or conflicts with an idle robot, the search algorithm may: Alter the branch to outrun the conflicting reservation (if acceleration profile allows); Alter the branch to contain a wait at any position along its path; or Discard the branch as infeasible.”).
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 using “graph” algorithms 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.
Regarding Claim 19, Calder, Stadie, and Bader teach “The non-transitory storage medium as recited in claim 11,” as discussed above.
Calder further teaches “wherein one of vehicles is an autonomous vehicle” (¶13 shows “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.”).
Claims 5 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over WO-2018052853-A1 ("Calder") in view of US-20180075402-A1 (“Stadie”), “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), and “Incremental A*” (“Koenig” Advances in Neural Information Processing Systems 14 (NIPS 2001), https://papers.nips.cc/paper_files/paper/2001/file/a591024321c5e2bdbd23ed35f0574dde-Paper.pdf).
Regarding Claim 5, Calder, Stadie, and Bader teach “The method as recited in claim 1,” as discussed above.
Calder does not explicitly teach, but Stadie further teaches “wherein a subset of historical itineraries is generated . . .” (¶7 shows “In some of these implementations, the containers are accessed by one or more robotic or automated means, which navigate through a grid of pathways to access containers for a variety of different operations, such as moving a container from one location to another for handling, conducting operations upon a container, returning a container to a position in a warehouse, etc.” (Emphasis added). ¶52 shows “For the purposes of this specification, a storage facility for the storage, retrieval, processing and/or fulfillment of orders, wherein access to such goods is provided by fully or semi-automatic retrieval, is referred to as a ‘hive’. The ‘hive’ may be comprised of a grid-like layout of the potential pathways for the movement of robotic elements or devices (‘robot’) to traverse and perform operations at various locations in the ‘hive’ (referred to as the ‘grid’).” (Emphasis added). ¶60 shows “The ‘hive’ itself may be a ‘dynamic’ environment, in the sense that robots and workstation locations may be associated with different parts of the hive for engaging in actions. For example, robots may need to access a specific container in a specific location in the hive dimensions (e.g. container at (X, Y, Z), depth W) to fulfil a particular order or to store a product in the “hive”. This involves movements of the robots along various possible paths, for example, along the top of the grid, and then accessing particular containers at selected depths of a stack.” Therefore, the “grid” is defined as several paths (i.e. historical itineraries). ¶69 shows that “Each grid may be segmented, physically or logically, into one or more sub-grids.” ¶¶145-46 shows that “optimization module 304” divides the grid into a plurality of smaller sub-grids to ease computational load. Additionally, ¶208 shows “A number of different algorithms and techniques may be used in determining a preferential path for a robot to take, including, . . . 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*).” Therefore, although grouping the grid into a sub-grid and a “Lifelong Planning A*” algorithm is explicitly taught by Stadie, Stadie does not teach the exact details as to how a “Lifelong Planning A*” would be implemented in connected with the “sub-grid” to find a solution.).
Calder, Stadie, and Bader do not explicitly teach, but Koenig teaches “wherein a subset of historical itineraries is generated based on the changes that have occurred in the operating environment” (Section 2 states “Lifelong Planning A* (LPA*) solves the following search task: It applies to finite graph search problems on known graphs whose edge costs can increase or decrease over time.” Abstract states “Incremental search techniques find optimal solutions to series of similar search tasks much faster than is possible by solving each search task from scratch. While researchers have developed incremental versions of uninformed search methods, we develop an incremental version of A*. The first search of Lifelong Planning A* is the same as that of A* but all subsequent searches are much faster because it reuses those parts of the previous search tree that are identical to the new search tree. We then present experimental results that demonstrate the advantages of Lifelong Planning A* for simple route planning tasks.” (Emphasis added). By “reusing parts of the previous search tree that are identical to the new search tree” Koenig teaches a subset (i.e. excluding the path segments reused because there is no change) is based on the changes that have occurred in the environment (i.e. a cell value is changed). Section 3 shows “Figure 2 shows in gray those cells whose start distances each of the four algorithms recomputes. (To be precise: it shows in gray the cells that each of the four algorithms expands.) During the search in the original gridworld, DynamicSWSF-FP computes the same start distances as breadth-first search during the first search and LPA* computes the same start distances as A*. During the search in the changed gridworld, however, both incremental search (DynamicSWSF-FP) and heuristic search (A*) individually decrease the number of start distances that need to get recomputed compared to breadth-first search, and together (LPA*) decrease the number even more.” Put simply, Section 3 and Figure 2 show that because only a subset of cells change, only a subset of paths need to be recalculated.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Koenig with Calder, Stadie, and Bader because Koenig teaches the details of implementing the Lifelong Planning A* algorithm (used in Stadie) which only recalculates a subset of the paths based upon the updated grid (Abstract). Thus, combining Koenig with Calder, Stadie, and Bader furthers the interest taught in Koenig, and therefore, would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention.
Regarding Claim 15, Calder and Stadie teach “The non-transitory storage medium as recited in claim 11,” as discussed above.
Calder does not explicitly teach, but Stadie further teaches “wherein a subset of historical itineraries is generated . . .” (¶7 shows “In some of these implementations, the containers are accessed by one or more robotic or automated means, which navigate through a grid of pathways to access containers for a variety of different operations, such as moving a container from one location to another for handling, conducting operations upon a container, returning a container to a position in a warehouse, etc.” (Emphasis added). ¶52 shows “For the purposes of this specification, a storage facility for the storage, retrieval, processing and/or fulfillment of orders, wherein access to such goods is provided by fully or semi-automatic retrieval, is referred to as a ‘hive’. The ‘hive’ may be comprised of a grid-like layout of the potential pathways for the movement of robotic elements or devices (‘robot’) to traverse and perform operations at various locations in the ‘hive’ (referred to as the ‘grid’).” (Emphasis added). ¶60 shows “The ‘hive’ itself may be a ‘dynamic’ environment, in the sense that robots and workstation locations may be associated with different parts of the hive for engaging in actions. For example, robots may need to access a specific container in a specific location in the hive dimensions (e.g. container at (X, Y, Z), depth W) to fulfil a particular order or to store a product in the “hive”. This involves movements of the robots along various possible paths, for example, along the top of the grid, and then accessing particular containers at selected depths of a stack.” Therefore, the “grid” is defined as several paths (i.e. historical itineraries). ¶69 shows that “Each grid may be segmented, physically or logically, into one or more sub-grids.” ¶¶145-46 shows that “optimization module 304” divides the grid into a plurality of smaller sub-grids to ease computational load. Additionally, ¶208 shows “A number of different algorithms and techniques may be used in determining a preferential path for a robot to take, including, . . . 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*).” Therefore, although grouping the grid into a sub-grid and a “Lifelong Planning A*” algorithm is explicitly taught by Stadie, Stadie does not teach the exact details as to how a “Lifelong Planning A*” would be implemented in connected with the “sub-grid” to find a solution.).
Calder, Stadie, and Bader do not explicitly teach, but Koenig teaches “wherein a subset of historical itineraries is generated based on the changes that have occurred in the operating environment” (Section 2 states “Lifelong Planning A* (LPA*) solves the following search task: It applies to finite graph search problems on known graphs whose edge costs can increase or decrease over time.” Abstract states “Incremental search techniques find optimal solutions to series of similar search tasks much faster than is possible by solving each search task from scratch. While researchers have developed incremental versions of uninformed search methods, we develop an incremental version of A*. The first search of Lifelong Planning A* is the same as that of A* but all subsequent searches are much faster because it reuses those parts of the previous search tree that are identical to the new search tree. We then present experimental results that demonstrate the advantages of Lifelong Planning A* for simple route planning tasks.” (Emphasis added). By “reusing parts of the previous search tree that are identical to the new search tree” Koenig teaches a subset (i.e. excluding the path segments reused because there is no change) is based on the changes that have occurred in the environment (i.e. a cell value is changed). Section 3 shows “Figure 2 shows in gray those cells whose start distances each of the four algorithms recomputes. (To be precise: it shows in gray the cells that each of the four algorithms expands.) During the search in the original gridworld, DynamicSWSF-FP computes the same start distances as breadth-first search during the first search and LPA* computes the same start distances as A*. During the search in the changed gridworld, however, both incremental search (DynamicSWSF-FP) and heuristic search (A*) individually decrease the number of start distances that need to get recomputed compared to breadth-first search, and together (LPA*) decrease the number even more.” Put simply, Section 3 and Figure 2 show that because only a subset of cells change, only a subset of paths need to be recalculated.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Koenig with Calder, Stadie, and Bader because Koenig teaches the details of implementing the Lifelong Planning A* algorithm (used in Stadie) which only recalculates a subset of the paths based upon the updated grid (Abstract). Thus, combining Koenig with Calder, Stadie, and Bader furthers the interest taught in Koenig, and therefore, would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure and is as follows:
CN-115675583-A (“Ye”) shows a “pruning” operation to narrow the size of the graph to determine an optimal driving strategy.
CN-110032187-A (“Tian”) shows using an A* algorithm to map the route of unmanned vehicles and using a “pruning” of historical route map to quickly determine the path of the vehicle.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MATTHEW PARKER GOODMAN whose telephone number is (571) 272-5698. The examiner can normally be reached on Monday-Thursday from 9:30 AM ET to 6:00 PM ET. If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jeffrey Zimmerman, can be reached at telephone number (571) 272-4602. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://portal.uspto.gov/external/portal. Should you have questions about access to the Private PAIR
system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free).
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
/MATTHEW PARKER GOODMAN/Examiner, Art Unit 3628
/JEFF ZIMMERMAN/Supervisory Patent Examiner, Art Unit 3628
Prosecution Insights