DETAILED ACTION
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 .
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 (i.e., changing from AIA to pre-AIA ) 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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claim(s) 20, 21, 25, 27 and 30-32, 34-46, and 38-40 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 20120121161 A1 by Eade et al., hereafter Eade, in view of Scale Free Cluster Distributions from Conserving Merging-Fragmentation Processes by Ferkinghoff-Borg et al., hereafter Ferkinghoff-Borg, and in further view of US 20170235743 A1 by Kim et al., hereafter Kim.
Regarding claim 20, Eade teaches:
A method for thinning a simultaneous localization and mapping (SLAM) graph (SLAM graph), which is used for controlling a mobile device and has a plurality of nodes (landmarks and pose nodes) and a plurality of edges (edges), each of the edges ending with an end point at a node (identifier of its source node and its destination node), the method comprising the following steps: ((Eade) Fig. 4; Paragraph [0144], “FIG. 4 provides an example of how certain of the present embodiments represent landmarks and other poses of the robot in a graph structure, referred to herein as a SLAM graph... As illustrated in FIG. 4 a plurality of pose nodes 1802, 1804 are connected by a plurality of edges 1806.”; Paragraph [0146], “Each edge 1810 includes a unique identifier 1820, and the identifier of its source node 1822 and its destination node 1824.”)
obtaining (receiving) the SLAM graph (results); ((Eade) Paragraph [0191], “The process begins at state 2601 by receiving results from the front end.” The results are the SLAM graph. Thus, receiving results is obtaining the SLAM graph.)
removing a subset of nodes of the plurality of nodes (removing some of the landmarks) from the SLAM graph (map) to form an updated SLAM graph ((Eade) Paragraph [0126], “The SLAM module 604 uses the change in pose information to update the one or more poses and maps 620 maintained.”); and ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
outputting (outputs) the updated SLAM graph (maps); ((Eade) Paragraph [0119], "Outputs from the VSLAM system 600 can include one or more poses and maps 620.")
determining control instructions (control signals) for controlling the mobile device (instruct the robot) based on the updated SLAM graph (outputs from the VSLAM system in response to the image data), wherein the mobile device is a robot, a vehicle, or a drone (the robot 100); and
controlling the mobile device (control the movement of the robot) based on the control instructions (control signals); ((Eade) Paragraph [0101], "In response to the image data 106, the control 108 can provide control signals to the motors 110, 112 that control the movement of the robot 100. For example, the control 108 can provide control signals to instruct the robot to move forward, to stop, to move backward, to turn, to rotate about a vertical axis, and the like."; Paragraph [0119], “Inputs to the VSLAM system 600 include raw pose data 610 from one or more dead reckoning sensors 614 and also include visual data 612 from one or more cameras or other visual sensors 616.”)
Eade additionally teaches:
Determining, out of the plurality of nodes, nodes whose densities of nodes are high (too dense portion of the map)[[…]] and removing the determined nodes (selectively removing some of the landmarks) whose densities are high from the SLAM graph. ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
Eade does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Ferkinghoff-Borg teaches:
Determining … scale-invariant (“To analyze the origin of the scale invariant solution…”) density (n(x,t)), wherein the scale-invariant density for each node is determined by(n(x,t)=) integrating a plurality of densities associated with the node (Eq. 2, integrating a plurality of n(x,t) which are the number densities), each density of the plurality of densities corresponding to a predefined area ( cluster of size x), from among a plurality of predefined areas (clusters from size 0 to L(largest possible cluster size)), around the node ((Ferkinghoff-Borg) Page 2, Left column, Paragraph 3, “Let n(x,t) denote the number density of clusters of size x at time t.”; Eq. 2, uses integrating including n(x,t) from 0 to x, x to L(largest possible cluster size), and 0 to L(largest possible cluster size))
Ferkinghoff-Borg and Eade are analogous art because they are in field of endeavor: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have used the scale-invariant density-based clustering to group together nodes, as taught in Ferkinghoff-Borg, in the definition of the densities of the nodes of Eade. The motivation for this would have been to ensure that the densities are calculated in way that appropriately models situations in society, as Ferkinghoff-Borg indicates in Paragraph 1, lines 6-7, “Empirical observations of US companies indicates that their sizes follow a scale invariant distribution”. This application of a known technique of scale-invariant densities to calculate densities for the known node removal method of Eade would produce, inter alia, a method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph.
Eade, in view of Ferkinghoff-Borg, still does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Kim teaches:
For each node of the subset of nodes removed from the graph ((Kim) Paragraph [0027], “In some cases, the merging employs an iterative approach”), the removing ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”) includes:
Determining, out of the plurality of nodes, a node whose density is the highest ((Kim) Paragraph [0027], “For example, the geo-points may be selected in order of their density from highest to lowest.”), and removing the determined node from the graph. ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”)
Kim, Ferkinghoff-Borg, and Eade are analogous art to the claimed invention because they are in the same field of endeavor: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have modified Eade, in view of Ferkinghoff-Borg, which already teaches determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph, but does not explicitly teach that the process should be done iteratively, with the teachings of Kim which does teach an iterative density determination, and an iterative removal. This would be motivated in order to account for changes that would occur after each removal of a node, maximizing the amount of “memory [that] can be freed for other tasks” while minimizing the chance of overshooting “appropriate thresholds for “high” density”. ((Eade) Paragraph [0136]) This application of the known technique of iterative determination and removal as taught by Kim to the known method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph as Eade, in view of Ferkinghoff-Borg, teaches, would produce the predictable result of a method wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the multiplicity plurality of nodes, a node whose scale-invariant density at further nodes around the node is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
which is the same as in claim 20 of the instant application. The Examiner notes that this motivation applies to all dependent and/or other subsequently addressed claims.
Regarding claim 21, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 20, and additionally Eade teaches:
wherein the removing of the determined node whose density is the highest from the SLAM graph includes: linking an end point (transferring information from the edges marked for deletion to the edges connecting the nodes remaining), which is then unconnected (edges marked for deletion), of an edge that ended at the removed node to another node. ((Eade) Fig. 14; Paragraph [0201], "As indicated in graph 4800B, the node n_r and all its incident edges are marked for deletion as part of the marginalization process. New edges indicated by the dashed lines are introduced and the information from the edges marked for deletion is transferred to the new and previously existing edges connecting the nodes remaining.")
Regarding claim 25, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 20, and additionally Eade teaches:
wherein removing the subset of nodes from the SLAM graph to form the updated SLAM graph includes: removing the subset of nodes (“selectively removing some of the landmarks in a too dense portion of the map”) such that the scale-invariant density for each node in the updated SLAM graph is below a density threshold; (“appropriate thresholds for “high” density”) or removing the subset of nodes until a number of nodes in the updated SLAM graph is below a node threshold, (5-10 landmarks per square meter), wherein the node threshold is predetermined based on a geometric size of an environment represented by the SLAM graph. ((Eade) Paragraph [0136], “In another example, landmarks can be considered undesirable when, for example, it is determined that the density of landmarks in some parts of the map is relatively high, such as about 5-10 landmarks per square meter for an indoor environment. It will be understood that the density of landmarks can vary considerably from one environment to another and that correspondingly, appropriate thresholds for "high" density will also vary and will be readily determined by the skilled practitioner. By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.”)
Regarding claim 27, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 20, and additionally Eade teaches:
wherein independent of removing the subset of nodes, a subset of edges of the plurality of edges are removed from the SLAM graph (“edges can be heuristically pruned”) wherein removing an edge in each case includes: ((Eade) Paragraph [0223], "To limit the edge complexity of the graph, edges can be heuristically pruned during operation." The process of heuristically pruning edges is outside of the node removal process.)
determining, out of the plurality of nodes, the node at which the most edges end (node having the highest edge degree); ((Eade) Paragraph [0225], "The process may begin at state 3402 where the pose node in the SLAM graph or a portion thereof having the highest edge degree (i.e., the largest number of incident edges) is selected." )
determining, from the edges that end at the determined node at which the most edges end, an edge that has the greatest covariance or the least amount of information (least disagreement/least likely to affect the graph optimum); and ((Eade) Paragraph [0225], "Based on the residual an edge which is in least disagreement with the current state of the graph, and whose removal is therefore likely to affect the graph optimum least, may be identified.")
removing (delete) the determined edge (best candidate edge). ((Eade) Paragraph [0225], "Once the process is complete, the best candidate edge is deleted at state 3410.")
Regarding claim 30, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 27, and additionally Eade teaches:
wherein, independent of the removal of a node, as many edges are removed (“edges are removed from each node in the list”) from the SLAM graph as are needed such that a number of edges that end at each node in the updated SLAM graph is below an edge threshold (“fixed, pre-determined bound” for node degrees) at all the nodes (“for each node”). ((Eade) Paragraph [0224], "One embodiment of an edge pruning procedure keeps a list of nodes with degree above a fixed, pre-determined bound. The list needs to be modified only when edges are added to graph, which occurs during landmark observations or node removal events. Then edges are removed from each node in the list until no node degrees exceed the bound." The edge pruning procedure happens independently of the node removal process.)
Regarding claim 31, Eade teaches:
A method for operating a mobile device (mobile robot 100), comprising the following steps: ((Eade) Paragraph [0099], "FIG. 1 illustrates an example of a mobile robot 100 in which a VSLAM system can be incorporated."
obtaining environment information (observe the environment) captured using one or more sensors (video camera/dead reckoning device); ((Eade) Paragraph [0096], "The VSLAM used by the scout can be coupled to a video camera carried by the scout to observe the environment and to a dead reckoning device, such as an odometer, a pedometer, a GPS sensor, an inertial sensor, and the like, to measure displacement.")
determining a current position and/or orientation (“estimate a current position and orientation(pose)”) of the mobile device (robot) based on a current SLAM graph (“previous position and orientation”)and the environment information (“dead reckoning”); ((Eade) Paragraph [0096], "With dead reckoning, the robot can compute course and distance traveled from a previous position and orientation (pose) and use this information to estimate a current position and orientation (pose).")
determining control instructions (control signals) for controlling (control the movement) the mobile device (the robot) based on the current position and/or orientation (in response to the image data), wherein the mobile device is a robot, a vehicle, or a drone (a robot); and ((Eade) Paragraph [0101], "In response to the image data 106, the control 108 can provide control signals to the motors 110, 112 that control the movement of the robot 100." The current position and/or orientation is based on environmental information that includes the image data, so being based on a current position and/or orientation means in response to the image data.)
controlling the mobile device (instruct the robot) based on the control instructions (control signals); ((Eade) Paragraph [0101], "For example, the control 108 can provide control signals to instruct the robot to move forward, to stop, to move backward, to turn, to rotate about a vertical axis, and the like.")
wherein: i) an older SLAM graph that has been thinned is used as the current SLAM graph (SLAM database that has had landmarks removed), and/or ii) the current SLAM graph is expanded (creating a landmark) using the environment information (“when a new physical landmark is encountered”)) and is then thinned (“remove landmarks”) for use as the current SLAM graph (“to provide efficient performance of VSLAM processing”); ((Eade) Paragraph [0113], "In one embodiment, when the new physical landmark is encountered and processed by the Visual Front End 602, the SLAM module 604 correspondingly "creates" a landmark by storing an initial estimate of the landmark pose"; Paragraph [0133], "...the SLAM database 608 can be managed to provide efficient performance of VSLAM processing in a diverse variety of settings and to manage the amount of memory used in VSLAM processing. One way to efficiently manage the databases is to remove landmarks from the databases")
wherein the thinning of a SLAM graph of the older SLAM graph or the current SLAM graph includes:
removing a subset of nodes of the plurality of nodes (removing some of the landmarks) from the SLAM graph (map) to form an updated SLAM graph ((Eade) Paragraph [0126], “The SLAM module 604 uses the change in pose information to update the one or more poses and maps 620 maintained.”), and ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
outputting (outputs) the updated SLAM graph (maps); ((Eade) Paragraph [0119], "Outputs from the VSLAM system 600 can include one or more poses and maps 620.")
Eade additionally teaches:
Determining, out of the plurality of nodes, nodes whose densities of nodes are high (too dense portion of the map)[[…]] and removing the determined nodes (selectively removing some of the landmarks) whose densities are high from the SLAM graph. ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
Eade does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Ferkinghoff-Borg teaches:
Determining the scale-invariant (“To analyze the origin of the scale invariant solution…”) density (n(x,t)), wherein the scale-invariant density for each node is determined by(n(x,t)=) integrating a plurality of densities associated with the node (Eq. 2, integrating a plurality of n(x,t) which are the number densities), each density of the plurality of densities corresponding to a predefined area (cluster of size x), from among a plurality of predefined areas (clusters of size 0 to L(largest possible cluster size)), around the node ((Ferkinghoff-Borg) Page 2, Left column, Paragraph 3, “Let n(x,t) denote the number density of clusters of size x at time t.”; Eq. 2, uses integrating including n(x,t) from 0 to x, x to L(largest possible cluster size), and 0 to L(largest possible cluster size))
Ferkinghoff-Borg and Eade are analogous art because they are in the same area of invention: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have used the scale-invariant density-based clustering to group together nodes, as taught in Ferkinghoff-Borg, in the definition of the densities of the nodes of Eade. The motivation for this would have been to ensure that the densities are calculated in way that appropriately models situations in society, as Ferkinghoff-Borg indicates in Paragraph 1, lines 6-7, “Empirical observations of US companies indicates that their sizes follow a scale invariant distribution”. This application of a known technique of scale-invariant densities to calculate densities for the known node removal method of Eade would produce, inter alia, a method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph.
Eade, in view of Ferkinghoff-Borg, still does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Kim teaches:
For each node of the subset of nodes removed from the graph ((Kim) Paragraph [0027], “In some cases, the merging employs an iterative approach”), the removing ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”) includes:
Determining, out of the plurality of nodes, a node whose density is the highest ((Kim) Paragraph [0027], “For example, the geo-points may be selected in order of their density from highest to lowest.”), and removing the determined node from the graph. ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”)
Kim, Ferkinghoff-Borg, and Eade are analogous art to the claimed invention because they are in the same field of endeavor: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have modified Eade, in view of Ferkinghoff-Borg, which already teaches determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph, but does not explicitly teach that the process should be done iteratively, with the teachings of Kim which does teach an iterative density determination, and an iterative removal. This would be motivated in order to account for changes that would occur after each removal of a node, maximizing the amount of “memory [that] can be freed for other tasks” while minimizing the chance of overshooting “appropriate thresholds for “high” density”. ((Eade) Paragraph [0136]) This application of the known technique of iterative determination and removal as taught by Kim to the known method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph as Eade, in view of Ferkinghoff-Borg, teaches, would produce the predictable result of a method wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the multiplicity plurality of nodes, a node whose scale-invariant density at further nodes around the node is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
which is the same as in claim 31 of the instant application. The Examiner notes that this motivation applies to all dependent and/or other subsequently addressed claims.
Regarding claim 32, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 31, and additionally Eade teaches:
Wherein the mobile device is a robot (mobile robot 100) ((Eade) Paragraph [0099], “FIG. 1 illustrates an example of a mobile robot 100 in which a VSLAM system can be incorporated.”)
Regarding claim 34, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 31, and additionally Eade teaches:
Wherein the one or more sensors is selected from: video cameras (video camera), radar sensors, LiDAR sensors, laser rangefinders, ultrasonic sensors, inertial sensors (inertial sensor)¸ and odometers (odometer). ((Eade) Paragraph [0096], “The VSLAM used by the scout can be coupled to a video camera carried by the scout to observe the environment and to a dead reckoning device, such as an odometer, a pedometer, a GPS sensor, an inertial sensor, and the like, to measure displacement.”)
Regarding claim 35, Eade teaches:
An arithmetic logic unit (microprocessor) ((Eade) Paragraph [0118])configured to thin a simultaneous localization and mapping (SLAM) graph (SLAM graph), which is used for controlling a mobile device and has a plurality of nodes (landmarks and pose nodes) and a plurality of edges (edges), each of the edges ending with an end point at a node (identifier of its source node and its destination node), the arithmetic logic unit being configured to: ((Eade) Fig. 4; Paragraph [0144], “FIG. 4 provides an example of how certain of the present embodiments represent landmarks and other poses of the robot in a graph structure, referred to herein as a SLAM graph... As illustrated in FIG. 4 a plurality of pose nodes 1802, 1804 are connected by a plurality of edges 1806.”; Paragraph [0146], “Each edge 1810 includes a unique identifier 1820, and the identifier of its source node 1822 and its destination node 1824.”)
obtain (receiving) the SLAM graph (results); ((Eade) Paragraph [0191], “The process begins at state 2601 by receiving results from the front end.” The results are the SLAM graph. Thus, receiving results is obtaining the SLAM graph.)
remove a subset of nodes of the plurality of nodes (removing some of the landmarks) from the SLAM graph (map) to form an updated SLAM graph ((Eade) Paragraph [0126], “The SLAM module 604 uses the change in pose information to update the one or more poses and maps 620 maintained.”); and ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
output (outputs) the updated SLAM graph (maps); ((Eade) Paragraph [0119], "Outputs from the VSLAM system 600 can include one or more poses and maps 620.")
determine control instructions (control signals) for controlling the mobile device (instruct the robot) based on the updated SLAM graph (outputs from the VSLAM system in response to the image data), wherein the mobile device is a robot, a vehicle, or a drone (the robot 100); and
control the mobile device (control the movement of the robot) based on the control instructions (control signals); ((Eade) Paragraph [0101], "In response to the image data 106, the control 108 can provide control signals to the motors 110, 112 that control the movement of the robot 100. For example, the control 108 can provide control signals to instruct the robot to move forward, to stop, to move backward, to turn, to rotate about a vertical axis, and the like."; Paragraph [0119], “Inputs to the VSLAM system 600 include raw pose data 610 from one or more dead reckoning sensors 614 and also include visual data 612 from one or more cameras or other visual sensors 616.”)
Eade additionally teaches:
Determining, out of the plurality of nodes, nodes whose densities of nodes are high (too dense portion of the map)[[…]] and removing the determined nodes (selectively removing some of the landmarks) whose densities are high from the SLAM graph. ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
Eade does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Ferkinghoff-Borg teaches:
Determining the scale-invariant (“To analyze the origin of the scale invariant solution…”) density (n(x,t)), wherein the scale-invariant density for each node is determined by(n(x,t)=) integrating a plurality of densities associated with the node (Eq. 2, integrating a plurality of n(x,t) which are the number densities), each density of the plurality of densities corresponding to a predefined area (cluster of size x), from among a plurality of predefined areas (clusters of size 0 to L(largest possible cluster size)), around the node ((Ferkinghoff-Borg) Page 2, Left column, Paragraph 3, “Let n(x,t) denote the number density of clusters of size x at time t.”; Eq. 2, uses integrating including n(x,t) from 0 to x, x to L(largest possible cluster size), and 0 to L(largest possible cluster size))
Ferkinghoff-Borg and Eade are analogous art because they are in the same area of invention: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have used the scale-invariant density-based clustering to group together nodes, as taught in Ferkinghoff-Borg, in the definition of the densities of the nodes of Eade. The motivation for this would have been to ensure that the densities are calculated in way that appropriately models situations in society, as Ferkinghoff-Borg indicates in Paragraph 1, lines 6-7, “Empirical observations of US companies indicates that their sizes follow a scale invariant distribution”. This application of a known technique of scale-invariant densities to calculate densities for the known node removal method of Eade would produce, inter alia, a method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph.
Eade, in view of Ferkinghoff-Borg, still does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Kim teaches:
For each node of the subset of nodes removed from the graph ((Kim) Paragraph [0027], “In some cases, the merging employs an iterative approach”), the removing ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”) includes:
Determining, out of the plurality of nodes, a node whose density is the highest ((Kim) Paragraph [0027], “For example, the geo-points may be selected in order of their density from highest to lowest.”), and removing the determined node from the graph. ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”)
Kim, Ferkinghoff-Borg, and Eade are analogous art to the claimed invention because they are in the same field of endeavor: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have modified Eade, in view of Ferkinghoff-Borg, which already teaches determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph, but does not explicitly teach that the process should be done iteratively, with the teachings of Kim which does teach an iterative density determination, and an iterative removal. This would be motivated in order to account for changes that would occur after each removal of a node, maximizing the amount of “memory [that] can be freed for other tasks” while minimizing the chance of overshooting “appropriate thresholds for “high” density”. ((Eade) Paragraph [0136]) This application of the known technique of iterative determination and removal as taught by Kim to the known method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph as Eade, in view of Ferkinghoff-Borg, teaches, would produce the predictable result of a method wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the multiplicity plurality of nodes, a node whose scale-invariant density at further nodes around the node is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
which is the same as in claim 35 of the instant application. The Examiner notes that this motivation applies to all dependent and/or other subsequently addressed claims.
Regarding claim 36, Eade teaches:
A mobile device (mobile robot 100), comprising: ((Eade) Paragraph [0099], "FIG. 1 illustrates an example of a mobile robot 100 in which a VSLAM system can be incorporated."
at least one sensor (video camera/dead reckoning device) configured to capture environment information (observe the environment); ((Eade) Paragraph [0096]) and
an arithmetic logic unit ((Eade) Paragraph [0102], microprocessor in control 108) configured to control the mobile device (control 108 can provide control signals that control the movement of the robot), the arithmetic logic unit configured to:
obtain the environment information (observe the environment) captured using the at least one sensor (video camera/dead reckoning device); ((Eade) Paragraph [0096],
determine a current position and/or orientation (“estimate a current position and orientation(pose)”) of the mobile device (robot) based on a current simultaneous localization and mapping (SLAM) graph (“previous position and orientation”)and the environment information (“dead reckoning”); ((Eade) Paragraph [0096)
determine control instructions (control signals) for controlling (control the movement) the mobile device (the robot) based on the current position and/or orientation (in response to the image data); and ((Eade) Paragraph [0101], "In response to the image data 106, the control 108 can provide control signals to the motors 110, 112 that control the movement of the robot 100." The current position and/or orientation is based on environmental information that includes the image data, so being based on a current position and/or orientation means in response to the image data.)
control the mobile device (instruct the robot) based on the control instructions (control signals); ((Eade) Paragraph [0101], "For example, the control 108 can provide control signals to instruct the robot to move forward, to stop, to move backward, to turn, to rotate about a vertical axis, and the like.")
wherein: i) an older SLAM graph that has been thinned is used as the current SLAM graph (SLAM database that has had landmarks removed), and/or ii) the current SLAM graph is expanded (creating a landmark) using the environment information (“when a new physical landmark is encountered”)) and is then thinned (“remove landmarks”) for use as the current SLAM graph (“to provide efficient performance of VSLAM processing”); ((Eade) Paragraph [0113], "In one embodiment, when the new physical landmark is encountered and processed by the Visual Front End 602, the SLAM module 604 correspondingly "creates" a landmark by storing an initial estimate of the landmark pose"; Paragraph [0133], "...the SLAM database 608 can be managed to provide efficient performance of VSLAM processing in a diverse variety of settings and to manage the amount of memory used in VSLAM processing. One way to efficiently manage the databases is to remove landmarks from the databases")
wherein the arithmetic logic unit is configured to thin a SLAM graph of the older SLAM graph or the current SLAM graph by:
removing a subset of nodes of the plurality of nodes (removing some of the landmarks) from the SLAM graph (map) to form an updated SLAM graph ((Eade) Paragraph [0126], “The SLAM module 604 uses the change in pose information to update the one or more poses and maps 620 maintained.”), and ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
outputting (outputs) the updated SLAM graph (maps); ((Eade) Paragraph [0119], "Outputs from the VSLAM system 600 can include one or more poses and maps 620.")
Eade additionally teaches:
Determining, out of the plurality of nodes, nodes whose densities of nodes are high (too dense portion of the map)[[…]] and removing the determined nodes (selectively removing some of the landmarks) whose densities are high from the SLAM graph. ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
Eade does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Ferkinghoff-Borg teaches:
Determining the scale-invariant (“To analyze the origin of the scale invariant solution…”) density (n(x,t)), wherein the scale-invariant density for each node is determined by(n(x,t)=) integrating a plurality of densities associated with the node (Eq. 2, integrating a plurality of n(x,t) which are the number densities), each density of the plurality of densities corresponding to a predefined area (cluster of size x), from among a plurality of predefined areas (clusters of size 0 to L(largest possible cluster size)), around the node ((Ferkinghoff-Borg) Page 2, Left column, Paragraph 3, “Let n(x,t) denote the number density of clusters of size x at time t.”; Eq. 2, uses integrating including n(x,t) from 0 to x, x to L(largest possible cluster size), and 0 to L(largest possible cluster size))
Ferkinghoff-Borg and Eade are analogous art because they are in the same area of invention: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have used the scale-invariant density-based clustering to group together nodes, as taught in Ferkinghoff-Borg, in the definition of the densities of the nodes of Eade. The motivation for this would have been to ensure that the densities are calculated in way that appropriately models situations in society, as Ferkinghoff-Borg indicates in Paragraph 1, lines 6-7, “Empirical observations of US companies indicates that their sizes follow a scale invariant distribution”. This application of a known technique of scale-invariant densities to calculate densities for the known node removal method of Eade would produce, inter alia, a method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph.
Eade, in view of Ferkinghoff-Borg, still does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Kim teaches:
For each node of the subset of nodes removed from the graph ((Kim) Paragraph [0027], “In some cases, the merging employs an iterative approach”), the removing ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”) includes:
Determining, out of the plurality of nodes, a node whose density is the highest ((Kim) Paragraph [0027], “For example, the geo-points may be selected in order of their density from highest to lowest.”), and removing the determined node from the graph. ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”)
Kim, Ferkinghoff-Borg, and Eade are analogous art to the claimed invention because they are in the same field of endeavor: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have modified Eade, in view of Ferkinghoff-Borg, which already teaches determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph, but does not explicitly teach that the process should be done iteratively, with the teachings of Kim which does teach an iterative density determination, and an iterative removal. This would be motivated in order to account for changes that would occur after each removal of a node, maximizing the amount of “memory [that] can be freed for other tasks” while minimizing the chance of overshooting “appropriate thresholds for “high” density”. ((Eade) Paragraph [0136]) This application of the known technique of iterative determination and removal as taught by Kim to the known method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph as Eade, in view of Ferkinghoff-Borg, teaches, would produce the predictable result of a method wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the multiplicity plurality of nodes, a node whose scale-invariant density at further nodes around the node is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
which is the same as in claim 36 of the instant application. The Examiner notes that this motivation applies to all dependent and/or other subsequently addressed claims.
Regarding claim 38 of the instant application, Eade teaches:
A non-transitory machine-readable storage medium (tangible medium) on which is stored a computer program ((Eade) Paragraph [0103], "The software can include instructions that are embodied in a tangible medium, such as a hard disk or an optical disk.") for thinning a simultaneous localization and mapping (SLAM) graph (SLAM graph), which is used for controlling a mobile device and has a plurality of nodes (landmarks and pose nodes) and a plurality of edges (edges), each of the edges ending with an end point at a node (identifier of its source node and its destination node), the computer program, when executed by an arithmetic logic unit ((Eade) Paragraph [0118], “software executed by a microprocessor”), causing the arithmetic logic unit to perform the following steps: ((Eade) Fig. 4; Paragraph [0144], “FIG. 4 provides an example of how certain of the present embodiments represent landmarks and other poses of the robot in a graph structure, referred to herein as a SLAM graph... As illustrated in FIG. 4 a plurality of pose nodes 1802, 1804 are connected by a plurality of edges 1806.”; Paragraph [0146], “Each edge 1810 includes a unique identifier 1820, and the identifier of its source node 1822 and its destination node 1824.”)
obtaining (receiving) the SLAM graph (results); ((Eade) Paragraph [0191], “The process begins at state 2601 by receiving results from the front end.” The results are the SLAM graph. Thus, receiving results is obtaining the SLAM graph.)
removing a subset of nodes of the plurality of nodes (removing some of the landmarks) from the SLAM graph (map) to form an updated SLAM graph ((Eade) Paragraph [0126], “The SLAM module 604 uses the change in pose information to update the one or more poses and maps 620 maintained.”); and ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
outputting (outputs) the updated SLAM graph (maps); ((Eade) Paragraph [0119], "Outputs from the VSLAM system 600 can include one or more poses and maps 620.")
determining control instructions (control signals) for controlling the mobile device (instruct the robot) based on the updated SLAM graph (outputs from the VSLAM system in response to the image data), wherein the mobile device is a robot, a vehicle, or a drone (the robot 100); and
controlling the mobile device (control the movement of the robot) based on the control instructions (control signals); ((Eade) Paragraph [0101], "In response to the image data 106, the control 108 can provide control signals to the motors 110, 112 that control the movement of the robot 100. For example, the control 108 can provide control signals to instruct the robot to move forward, to stop, to move backward, to turn, to rotate about a vertical axis, and the like."; Paragraph [0119], “Inputs to the VSLAM system 600 include raw pose data 610 from one or more dead reckoning sensors 614 and also include visual data 612 from one or more cameras or other visual sensors 616.”)
Eade additionally teaches:
Determining, out of the plurality of nodes, nodes whose densities of nodes are high (too dense portion of the map)[[…]] and removing the determined nodes (selectively removing some of the landmarks) whose densities are high from the SLAM graph. ((Eade) Paragraph [0136], "By selectively removing some of the landmarks in a too dense portion of the map, memory can be freed for other tasks.")
Eade does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Ferkinghoff-Borg teaches:
Determining the scale-invariant (“To analyze the origin of the scale invariant solution…”) density (n(x,t)), wherein the scale-invariant density for each node is determined by(n(x,t)=) integrating a plurality of densities associated with the node (Eq. 2, integrating a plurality of n(x,t) which are the number densities), each density of the plurality of densities corresponding to a predefined area (cluster of size x), from among a plurality of predefined areas (clusters of size 0 to L(largest possible cluster size)), around the node ((Ferkinghoff-Borg) Page 2, Left column, Paragraph 3, “Let n(x,t) denote the number density of clusters of size x at time t.”; Eq. 2, uses integrating including n(x,t) from 0 to x, x to L(largest possible cluster size), and 0 to L(largest possible cluster size))
Ferkinghoff-Borg and Eade are analogous art because they are in the same area of invention: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have used the scale-invariant density-based clustering to group together nodes, as taught in Ferkinghoff-Borg, in the definition of the densities of the nodes of Eade. The motivation for this would have been to ensure that the densities are calculated in way that appropriately models situations in society, as Ferkinghoff-Borg indicates in Paragraph 1, lines 6-7, “Empirical observations of US companies indicates that their sizes follow a scale invariant distribution”. This application of a known technique of scale-invariant densities to calculate densities for the known node removal method of Eade would produce, inter alia, a method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph.
Eade, in view of Ferkinghoff-Borg, still does not explicitly disclose:
wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the plurality of nodes, a node whose scale-invariant density is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
Kim teaches:
For each node of the subset of nodes removed from the graph ((Kim) Paragraph [0027], “In some cases, the merging employs an iterative approach”), the removing ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”) includes:
Determining, out of the plurality of nodes, a node whose density is the highest ((Kim) Paragraph [0027], “For example, the geo-points may be selected in order of their density from highest to lowest.”), and removing the determined node from the graph. ((Kim) Paragraph [0026], “Merging a geo-point can include removing the geo-point from the set of geo-points.”)
Kim, Ferkinghoff-Borg, and Eade are analogous art to the claimed invention because they are in the same field of endeavor: grouping together points of information using density.
Thus, it would be obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the references in front of them, to have modified Eade, in view of Ferkinghoff-Borg, which already teaches determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph, but does not explicitly teach that the process should be done iteratively, with the teachings of Kim which does teach an iterative density determination, and an iterative removal. This would be motivated in order to account for changes that would occur after each removal of a node, maximizing the amount of “memory [that] can be freed for other tasks” while minimizing the chance of overshooting “appropriate thresholds for “high” density”. ((Eade) Paragraph [0136]) This application of the known technique of iterative determination and removal as taught by Kim to the known method of determining, out of the plurality of nodes, nodes whose scale-invariant density at further nodes around the nodes are high and removing the determined nodes whose scale-invariant densities are high from the SLAM graph as Eade, in view of Ferkinghoff-Borg, teaches, would produce the predictable result of a method wherein, for each node of the subset of nodes removed from the SLAM graph, the removing includes:
determining, out of the multiplicity plurality of nodes, a node whose scale-invariant density at further nodes around the node is the highest, wherein the scale-invariant density for each node is determined by integrating a plurality of densities associated with the node, each density of the plurality of densities corresponding to a predefined area, from among a plurality of predefined areas, around the node; and
removing the determined node whose scale-invariant density is the highest from the SLAM graph.
which is the same as in claim 38 of the instant application. The Examiner notes that this motivation applies to all dependent and/or other subsequently addressed claims.
Regarding claim 39, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 20, and additionally Eade teaches:
wherein the control instructions (control signals) comprise one or more indications indicating whether the mobile device should perform a turning maneuver(to turn), a rate at which the mobile device should perform the turning maneuver, or how far the mobile device should travel as part of the turning maneuver, and wherein controlling the mobile device based on the control instructions includes controlling the mobile device according to the one or more indications (instruct the robot to turn). ((Eade) Paragraph [0101], “For example, the control 108 can provide control signals to instruct the robot to move forward, to stop, to move backward, to turn, to rotate about a vertical axis, and the like.”)
Regarding claim 40, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 20, and additionally Ferkinghoff-Borg teaches:
wherein, for each node, each predefined area (cluster of size x) of the plurality of predefined areas (clusters of size 0 to L) corresponds to a radius (size x) from among a plurality of radii (sizes from 0 to L) around the node. ((Ferkinghoff-Borg) Page 2, Left column, Paragraph 3, “Let n(x,t) denote the number density of clusters of size x at time t.”; Eq. 2, uses integrating including n(x,t) from 0 to x, x to L(largest possible cluster size), and 0 to L(largest possible cluster size))
The reasoning for combining Ferkinghoff-Borg and Eade remains the same as in the parent claim, claim 20.
Claim(s) 22 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eade, in view of Ferkinghoff-Borg and Kim, and in further view of Large-Scale LiDAR SLAM with Factor Graph Optimization on High-Level Geometric Features by Cwian et al., hereafter Cwian.
Regarding claim 22, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 21, and Eade additionally teaches:
wherein, out of the nodes adjacent to the removed node, the another node to which the unconnected end point is linked is selected by moving the end point (transferring the information) forward (new edges) or backward (previously existing edges)along a movement chain made up of movement edges (new and previously existing edges connecting the nodes remaining) until a further node is reached, ((Eade) Paragraph [0201], "New edges indicated by the dashed lines are introduced and the information from the edges marked for deletion is transferred to the new and previously existing edges connecting the nodes remaining.")
Eade, in view of Ferkinghoff-Borg and Kim, does not explicitly disclose:
wherein the further node at which a length of the newly produced edge is shortest is selected as the another node to which the unconnected end point is linked.
Cwian teaches:
wherein the further node (point) at which a length (Euclidean distance between points) of the newly produced edge is shortest (closest points) is selected as the node to which the unconnected end point is linked (the matching). ((Cwian) Pg. 7. Section 3.1 Paragraph 1, "These points are then matched to the closest points of the same type (planar or linear) from the previously captured point cloud. The matching is performed based on the Euclidean distance between points of the same type, accommodating a simple sensor motion prediction model.")
In addition, Cwian suggests that matching points by closest points solves the challenge of finding a fast way of matching points. ((Cwian) Pg. 13. Section 3.2.5. Paragraph 2, "One of the challenges of using a map composed of high-level features is a fast way of matching a point to the growing number of features stored in the map. Using a linear search would not provide real-time performance for large maps. Therefore, when a point is matched to the features in the map, we firstly determine the closest point in the map using efficient kd-trees and then we retrieve the ID of the high-level feature that contains this point.")
Cwian and Eade are analogous art because they are in the same field of endeavor: optimization of SLAM graphs based on geometric features.
Thus, it would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention, having the references in front of them, to have modified the selection of the node where unconnected endpoints are linked to by moving back and forth along a movement chain, as Eade teaches, by selecting the closest points to link together to form an edge, as taught by Cwian. The motivation for this would be in order to have a fast, real-time performance connecting between nodes as Cwian teaches ((Cwian) Pg. 13. Section 3.2.5. Paragraph 2). This application of a known technique of selecting the shortest points to link together as taught by Cwian to the method of linking as Eade teaches would produce the predictable result that is the same as the disclosure of claim 22 of the instant application.
Claim(s) 23 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eade, in view of Ferkinghoff-Borg and Kim, and in further view of US 20230358546 A1 by Broadway et al., hereafter Broadway.
Regarding claim 23, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 21.
Eade, in view of Ferkinghoff-Borg and Kim, does not explicitly disclose:
wherein, when two edges are combined when linking the end point of an edge to another node, a loop-closure edge is removed when it contradicts a movement edge, and/or, when both of the two edges are loop-closure edges, both of the two edges are removed when they contradict each other.
Broadway teaches:
wherein, when two edges (trajectories) are combined when linking the end point of an edge to another node, a loop-closure edge (loop closures) is removed (rejected) when it contradicts (not well satisfied/inconsistent with the new constraints) a movement edge, and/or, when both of the two edges are loop-closure edges, both of the two edges are removed when they contradict each other. ((Broadway) Paragraph [0235], "Optionally, a trajectory in the pose graph 313 may be cut, and segments of it may be removed between iterations, if new and old constraints consistently contradict each other in a particular section of a trajectory."; Paragraph [0237], "The uncertainty … may be increased for those loop closures that are inconsistent with the new constraints. In other words, the loop closures … that are not well satisfied are negatively reinforced (or rejected).")
Broadway and Eade are analogous art because they are in the same field of endeavor: building a map for mobile device activity and optimization of the mapping.
Thus, it would have been obvious to a person having ordinary skill in the art before the effective filing date to have modified Eade, which already teaches the removing of a determined edge, but does not specify when to remove a loop closure edge, by specifying a condition for removing (rejecting) a loop closure edge (trajectory): when it contradicts another edge, as taught by Broadway, in order to improve performance by eliminating poor quality directions. This application of a known technique of specifying a condition to remove a loop closure edge, as taught by Broadway, into the edge removal method taught by Eade would produce the predictable result that is the method disclosed in claim 23 of the instant application.
Claim(s) 26 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eade, in view of Ferkinghoff-Borg and Kim, and in further view of Tactile SLAM: Real-time inference of shape and pose from planar pushing by Suresh et al., hereafter Suresh.
Regarding claim 26, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 20.
Eade, in view of Ferkinghoff-Borg and Kim, does not explicitly disclose:
wherein a predetermined quantity of nodes most recently added to the SLAM graph are not taken into account when removing the subset of nodes.
Suresh teaches:
wherein a predetermined quantity of nodes most recently added (fixed temporal window of states) to the SLAM graph are not taken into account (fixed temporal window of states not being the marginalized states) when removing the subset of nodes (marginalizing out states). ((Suresh) Pg. 4. Section V. Pose Estimation With Factor Graphs Subsection A. Factor graph formulation, “Fixed lag smoothing maintains a fixed temporal window of states Xw, while efficiently marginalizing out preceding states” Maintaining a fixed temporal window of states, while marginalizing out preceding states is the same as a predetermined quantity of nodes most recently added to the SLAM graph are not being taken into account when removing nodes.)
Suresh and Eade are analogous art because they are in the same area of invention: optimization of SLAM graphs.
Thus, it would have been obvious to a person having ordinary skill in the art before the effective filing date to have modified Eade, which teaches a method of removing nodes, by implemented a method of maintaining a fixed number of recently added nodes of the SLAM graph and only removing previous nodes, as taught by Suresh. The motivation for this would be in order to bound optimization time over the exploration to make more effective use of available memory. This application of a known technique of maintaining a fixed number of recently added nodes to not remove to the node removal method of Eade would produce the predictable result that is the same as claim 26 of the instant application.
Claim(s) 28 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eade, in view of Ferkinghoff-Borg and Kim, and in further view of SLAM Pose-graph Robustification via Multi-scale Heat-Kernel Analysis by Datta et al., hereafter Datta.
Regarding claim 28, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 27.
Eade, in view of Ferkinghoff-Borg and Kim, does not explicitly disclose, but together with Datta does teach:
Datta teaches:
wherein the determined edge is removed (pruned) only when it is a loop-closure (LC) edge. ((Datta) Section V. Proposed Approach, "We propose a novel multi-scale LC pruning method which can significantly improve the performance of existing SLAM optimization techniques by pruning the noisy constraints (incorrect LC edges) from the pose-graph." LC stands for loop-closure.)
Datta and Eade are analogous art because they are in the same area of invention: optimization of SLAM graphs.
Thus, it would be obvious to a person having ordinary skill in the art before the effective filing date of the application to have modified Eade, which already teaches an edge removal method, by limiting the edge removal to specifically incorrect loop-closure edges, as taught by Datta. The motivation for this would be to significantly improve the performance of existing SLAM optimization techniques as Datta indicates ((Datta) Section V. Proposed Approach). This implementation of a known technique of limiting the edge removal to loop-closure edges into the edge removal method taught by Eade would yield the predictable result that is the same as the disclosure of claim 28 of the instant application.
Claim(s) 29 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eade, in view of Ferkinghoff-Borg, Kim, and in further view of US 20180007593 A1 by Gormley et al., hereafter Gormley and Geometric Spanners: Recent Results and Open Directions by Kanj, hereafter Kanj.
Regarding claim 29, Eade, in view of Ferkinghoff-Borg and Kim, teaches the material disclosed in claim 27.
Eade, in view of Ferkinghoff-Borg and Kim, does not explicitly disclose:
wherein the determined edge is removed only when a factor, which indicates a ratio of a length of a shortest path, not containing the edge, between two nodes at which the edge ends to a length of the edge, is below a factor threshold.
Gormley teaches:
Wherein the determined edge is removed (marked as removal candidates) only when a factor (ratio), which indicates a ratio of a length of a path between two nodes to an edge (ratio of a longest edge to a shortest edge), is below a factor threshold (threshold value). ((Gormley) Paragraph [0187], "...in some embodiments, the two longest edges may both be marked as removal candidates. In an embodiment, an additional threshold may apply to this situation. For example, a length of a shortest edge 2814 may be compared to a threshold value, a ratio between the two longest edges may be compared to a threshold value, a ratio of a longest edge to a shortest edge can be compared to a threshold value, etc." )
Gormley and Eade are analogous art because they are in the same field of endeavor: efficiently determining positions of nearby objects using geometry.
Thus, it would have been obvious to a person having ordinary skill in the art before the effective filing date to have modified Eade, which already teaches an edge removal method, by implementing a limitation of only removing edges based on if a ratio between edges is below a threshold value, as taught by Gormley. The motivation for this would be in order to only remove poor or incorrect connections. This implementation of a known technique of limiting which edges are removed into the edge removal method of Eade would produce the predictable result of the edge removal procedure of Eade done only when a ratio of edge lengths is below a threshold value.
Eade, in view of Ferkinghoff-Borg and Kim, and in further view of Gormley, still does not explicitly disclose:
wherein the determined edge is removed only when a factor, which indicates a ratio of a length of a shortest path, not containing the edge, between two nodes at which the edge ends to a length of the edge, is below a factor threshold. Kanj teaches:
a factor (stretch factor), which indicates a ratio (a fixed constant times) of a length of a shortest path (weight of a shortest path), not containing the edge, between two nodes (between any pair of points in H) at which the edge ends to a length (weight equal to the Euclidean distance between the two endpoints of the edge)of the edge (spanner E), is below a factor threshold (lightweight stretch factor)((Kanj) Pg. 1. Section I. Introduction Paragraph 1, “Given a set of n points S in the Euclidean plane, the Euclidean graph E on S is the complete graph whose pointset is S; each edge in E is associated with a weight equal to the Euclidean distance between the two endpoints of the edge. A geometric spanner H of a subgraph G of E is a spanning subgraph of G in which the weight of a shortest path between any pair of points in H is at most a fixed constant times that in G; this constant is called the stretch factor of the spanner. A spanner of E is lightweight if its weight is at most a constant times the weight of a minimum spanning tree of E.”)
Kanj, Gormley, and Eade are analogous art because they are in the same area of invention: efficient graph structures using geometry.
Thus, it would have been obvious to a person having ordinary skill in the art before the effective filing date to have modified Eade, in view of Gormley, which already teaches an edge removal method that limits the edge removal to when a ratio between edges is below a threshold, by further limiting the condition to when the ratio between edges is a ratio between a shortest path not including a specified edge, and the specified edge. The motivation for this would be for more effective computation due to proximity of nodes. This simple substitution of the ratio of Gormley for the ratio of Kanj would produce the predictable result of the edge removal procedure of Eade done only when a ratio of the length of a shortest path between two nodes and the length of the edge being below a factor threshold, which is the same as disclosed in claim 29 of the instant application.
Response to Arguments
Applicant’s arguments, see page 11, lines 12-15, filed 08/10/2026, with respect to objections because of informalities have been fully considered and are persuasive. The appropriate corrections were made that fix the informalities. The objections to the specification and claims 20 and 36 have been withdrawn.
Applicant’s arguments, see page 11, lines 16-19, filed 08/10/2026, with respect to rejections under 35 U.S.C. 112(b) as being indefinite have been fully considered and are persuasive. The appropriate amendments were made that fix the errors. The 35 U.S.C. 112(b) rejections for claims 20-38 have been withdrawn.
Applicant’s arguments, see pages 12-14, filed 08/10/2026, with respect to rejections under 35 U.S.C. 101 have been fully considered and are persuasive. The amendment to claims 20, 31, 35, 36, and 38 changing operating the mobile device to controlling the mobile device moves the consideration for limitation to Step 2A, Prong One. The specificity in the explanation of how the scale-invariant density is calculated meets the requirements to link the improvement disclosed in the specification to the claim. This allows the additional elements in the limitation to integrate into a practical application. The 35 U.S.C. 101 rejections for claims 20-38 have been withdrawn.
Applicant’s arguments, se pages 14-19, with respect to rejections under 35 U.S.C 103 for claim(s) 20-23, 25-32, 34-36, and 38-40 have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument. References applied in the prior rejection of record are used for teachings or matters not challenged in the argument.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Patents and/or related publications are cited in the Notice of References Cited (Form PTO-892) attached to this action to further show the state of the art with respect to effective node and edge removal methods, including selectively ignoring certain nodes and basing removal on geometrical features.
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.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DYLAN H LAI whose telephone number is (571)272-8628. The examiner can normally be reached Monday - Friday 7:30am-5:00pm.
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.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Tamara Kyle can be reached at 5712524241. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/D.H.L./Examiner, Art Unit 2144
/TAMARA T KYLE/Supervisory Patent Examiner, Art Unit 2144
Prosecution Insights