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 .
Status of Claims
Claims 1-4, 6-8, 10, 12-14, and 16-20 have been amended.
Claims 1-20 are currently pending and addressed below.
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.
Claims 1-17 and 19-20 are rejected under 35 U.S.C. 103 as being unpatentable over Geisberger (US 2014/0200807), hereinafter referred to as Geisberger, in view of Phillips et al. (US 2021/0114617) as cited in the IDS filed 19 July 2024, hereinafter referred to as Phillips. Geisberger and Phillips are considered analogous to the claimed invention because they are in the same field of determining travel routes for a vehicle.
Regarding claim 1, Geisberger teaches:
A method comprising: selecting a proxy destination for a machine along a planned route to a destination (“As shown in FIG. 3, the route from source node 304 to destination node 305 thus comprises a path 306 computed by the Dijkstra search with live traffic and a path 307 computed using precomputed data with predicted traffic. The path 306 computed by the Dijkstra search extends from the source node to an intermediate node 308 at which the Dijkstra search stopped. The path computed using predicted traffic data extends from the intermediate node 308 to the destination node 305.” – see at least Geisberger: paragraph 0052) (The examiner notes that the intermediate node as taught by Geisberger corresponds to the claimed proxy destination);
based at least on the selecting, computing cost values associated with nodes corresponding to potential future locations of the machine in a graph (“Known route planning methods have a precomputation phase (ie: a computation phase prior to query time) in which map data is processed to form a graph data structure representing possible routes between locations. Costs may be assigned to arcs of the graph to apply weights based on the travel time between locations, and may take into account the distance between particular locations, the type of road, traffic conditions, and other factors which may affect travel time. Costs can alternatively or additionally be assigned to other parts of the graph, e.g: to nodes or subpaths.” – see at least Geisberger: paragraph 0003)
based at least on propagating a location score associated with the proxy destination through the nodes (“Optimal routes may be calculated by way of a graph search algorithm on the weighted graph. Known graph search algorithms include Dijkstra's algorithm and the A* search algorithm, which compute a connected sequence of arcs from a source node to a target node such that the sum of the arc costs is minimal over all such paths.” – see at least Geisberger: paragraph 0004) (The examiner notes that the sum of the arc costs of a connected sequence of arcs from a source node to a target node as taught by Geisberger corresponds to propagating a location score through the nodes as claimed)
searching, using the cost values, the nodes for a nominal path to the proxy destination (“The present invention provides a computer-implemented route planning method, comprising: determining source and destination nodes in a graph data structure based on a route planning query, executing an initial graph search on the graph data structure using graph costs based on real-time traffic data, wherein the initial graph search starts at the source node and settles nodes until it stops” – see at least Geisberger: paragraph 0007) (The examiner notes that the route planned based on the initial graph search as taught by Geisberger corresponds to the claimed nominal path, wherein the graph costs of Geisberger correspond to the claimed location scores);
Geisberger does not explicitly disclose, but Phillips teaches:
generating one or more trajectories based at least on adjusting one or more first positions along the nominal path to one or more second positions (“As depicted in the figure, the initial travel path 706 can be a path that the autonomous vehicle 702 would travel if there were no obstacles in the travel path. However, given that sensor data may indicate one of our obstacles the autonomous vehicle can generate an altered trajectory. The generated trajectory 704 has an offset 708 from the initial travel path that varies from the initial travel path 706.” – see at least Phillips: paragraph 0144);
and performing one or more control operations corresponding to the machine based at least on the one or more trajectories ("The method can include controlling, by the computing system, motion of the autonomous vehicle based, at least in part, on the trajectory." – see at least Phillips: paragraph 0005).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to have modified Geisberger with these above aforementioned teachings from Phillips to include generating one or more trajectories based at least on adjusting one or more first positions along the path to one or more second positions, and performing one or more control operations corresponding to the machine based at least on the one or more trajectories. At the time of the effective filing date of the claimed invention, one of ordinary skill in the art would have been motivated to incorporate Phillips’ method of generating altered trajectories with Geisberger’s route planning system in order to adjust an initial travel path (“The offset profile can include a plurality of offset values, each offset value representing an amount and direction of lateral offset from the initial travel path.” – see at least Phillips: paragraph 0026). Doing so would provide the benefit of allowing the vehicle to autonomously avoid objects that obstruct the initial travel path, and to generate candidate trajectories which improve vehicle efficiency (“The offset profile can indicate a lateral movement for the autonomous vehicle that would allow it to avoid an object (e.g., within a lane, using a partial lane departure, etc.). As such, a lateral offset profile can increase the number of candidate trajectories to be considered by the autonomous vehicle and allow for more efficient vehicle movement.” – see at least Phillips: paragraph 0026).
Regarding claim 2, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger further teaches:
wherein the graph comprises a lane graph, the cost values comprise time rewards assigned to respective graph nodes of the lane graph (“Costs may be assigned to arcs of the graph to apply weights based on the travel time between locations, and may take into account the distance between particular locations, the type of road, traffic conditions, and other factors which may affect travel time. Costs can alternatively or additionally be assigned to other parts of the graph, e.g: to nodes or subpaths.” – see at least Geisberger: paragraph 0003),
and the nominal path comprises a directed path of segments connecting a subset of the graph nodes ("Known graph search algorithms include Dijkstra's algorithm and the A* search algorithm, which compute a connected sequence of arcs from a source node to a target node such that the sum of the arc costs is minimal over all such paths. " – see at least Geisberger: paragraph 0004).
Regarding claim 3, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger further teaches:
wherein the propagating is back from a node in the graph that corresponds to the proxy destination ("Combining forward and reverse search spaces to determine optimal routes is a well known aspect of CH and other bidirectional graph searches (e.g: bidirectional Dijkstra), and will not be described in detail here. In some embodiments, the CH query module may combine the forward search spaces to form a combined CH forward search space, and then determine meeting spots between the combined CH forward search space and the backward CH search space, thereby to determine the shortest paths." – see at least Geisberger: paragraph 0055) (The examiner notes that “reverse search” and “backward search” as taught by Geisberger correspond to propagating back from a node as claimed).
Regarding claim 4, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger further teaches:
wherein the searching includes: evaluating, using the cost values, control actions for the machine, each control action of the control actions corresponding to a respective maneuver type and path segment connecting the nodes of the graph (“More specifically, the module 120 precomputes shortest paths (called shortcuts) by way of the CH technique, using the graph data structure generated by the graph generation module 122. As will be appreciated by those skilled in the art, the CH shortcuts are generated in a known manner dependent on graph costs.” – see at least Geisberger: paragraphs 0037-0038);
and based at least on the evaluating, selecting a plurality of control actions from the control actions, wherein, based at least on the selecting of the plurality of control actions, the nominal path includes the respective maneuver type and path segment for each control action in the plurality of control actions ("The shortest paths thus determined are then used to select the best route (ie: shortest path) from the source node 304 to the destination node 305 via a node at which the initial graph search stopped, thereby to determine 214 a route." – see at least Geisberger: paragraph 0051).
Regarding claim 5, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger does not explicitly disclose, but Phillips teaches:
wherein the control actions include at least two of: a lane follow action ("A cost function can be encoded for one or more of: the avoidance of object collision, keeping the autonomous vehicle on the travel way/within lane boundaries, preferring gentle accelerations to harsh ones, etc. " – see at least Phillips: paragraph 0122) (The examiner notes that keeping the autonomous vehicle within lane boundaries as taught by Phillips corresponds to the claimed lane follow action).
a lane change action;… or a double lane change action (“For example, if the trajectory calls for a lane change into a lane in which another vehicle is traveling at a higher speed than the autonomous vehicle, the one or more cost functions 222 may determine that a burden has been placed on the other vehicle because that other vehicle will eventually need to reduce its speed or change lanes.” – see at least Phillips: paragraph 0130);
an overtake action (“For example, one sub-cost value can represent the costs associated with overtaking another actor (e.g., generated by the overtaking buffer cost function)” – see at least Phillips: paragraph 0049).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to have modified Geisberger with these above aforementioned teachings from Phillips such that the control actions include at least two of: a lane follow action; a lane change action; an overtake action; or a double lane change action. At the time of the effective filing date of the claimed invention, one of ordinary skill in the art would have been motivated to incorporate Phillips’s use of a plurality of control actions for a vehicle with Geisberger’s route planning system in order to evaluate different actions that a vehicle may perform (“By way of example, the motion planning system 128 can determine that the autonomous vehicle 102 can perform a certain action (e.g., pass an object) without increasing the potential risk to the autonomous vehicle 102 and/or violating any traffic laws (e.g., speed limits, lane boundaries, signage).” – see at least Phillips: paragraph 0104). Doing so would provide the benefit of allowing generation of a motion plan for the vehicle (“The motion planning system 128 can provide the motion plan data 134 with data indicative of the autonomous vehicle actions, a planned trajectory, and/or other operating parameters to the vehicle control systems 138 to implement the motion plan data 134 for the autonomous vehicle 102.” – see at least Phillips: paragraph 0107).
Regarding claim 6, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger further teaches:
wherein the computing includes updating, for a subset of the graph that corresponds to the proxy destination, initial cost values associated with the nodes to the cost values associated with the nodes (“Suitable algorithms include Dijkstra's algorithm, the A* algorithm, or any other flexible algorithm in which graph costs can be changed quickly at query time to accommodate costs based on real-time traffic data. According to various embodiments, the initial graph search is a one-to-many graph search.” – see at least Geisberger: paragraph 0018) (The examiner notes that changing of the graph costs based on real-time traffic data as taught by Geisberger corresponds to the claimed updating of initial cost values).
Regarding claim 7, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger does not explicitly disclose, but Phillips teaches:
further comprising, based at least on the planned route: cutting out, from a larger version of the graph, a corridor corresponding to the planned route; targeting the proxy destination within the corridor based at least on a distance from the machine; and performing the propagating from the proxy destination within the corridor ("In some examples, the system can generate a corridor or tube in which the optimizer can modify the selected trajectory based on smoothness considerations. However, the corridor can be supplied to the overall path planner to pad the area of the tube (or corridor) to ensure that no obstacles or other actors enter into the tube and render it unsafe." – see at least Phillips: paragraph 0028).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to have modified Geisberger with these above aforementioned teachings from Phillips to include based at least on the planned route: cutting out, from a larger version of the graph, a corridor corresponding to the planned route; targeting the proxy destination within the corridor based at least on a distance from the machine; and performing the propagating from the proxy destination within the corridor. At the time of the effective filing date of the claimed invention, one of ordinary skill in the art would have been motivated to incorporate Phillips’ use of a corridor for a vehicle trajectory with Geisberger’s route planning system in order to generate a corridor within which a vehicle may travel to maintain a smooth trajectory (“In some examples, the system can generate a corridor or tube in which the optimizer can modify the selected trajectory based on smoothness considerations.” – see at least Phillips). Doing so would provide the benefit of determining a smoother path for the vehicle which would be more comfortable for a passenger (“The vehicle computing system (e.g., vehicle computing system 112 of FIG. 1) can generate, at 1504, a smoothed path. A smoothed path (or basis path) can be generated by an optimizer which can minimize the jerk and wrench expected along the path.” – see at least Phillips: paragraph 0205).
Regarding claim 8, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger does not explicitly disclose, but Phillips teaches:
wherein the one or more trajectories include a plurality of trajectories that are each a variation of the nominal path and are each starting from a starting position of the nominal path (“FIG. 6 depicts a graphical representation of a plurality of candidate trajectories according to example embodiments of the present disclosure. As seen herein, the plurality of offset profiles (e.g., offset profiles 400 in FIG. 4) can be applied to an initial travel path (e.g., initial travel path 500 in FIG. 5) to create a plurality of candidate trajectories. These candidate trajectories can be evaluated (e.g., a cost value can be generated) such that the best candidate trajectory can be selected.” – see at least Phillips: paragraph 0143) (The examiner notes that Fig. 6 of Phillips as shown below illustrates a plurality of trajectories which are each a variation of the initial travel path, and each start from the starting position of the initial travel path).
PNG
media_image1.png
329
462
media_image1.png
Greyscale
and the method further includes: determining, for each given trajectory of the plurality of trajectories and using the cost scores, a respective series of location scores, wherein the location scores are adjusted to correspond to the given trajectory ("The scoring system 220 can determine a cost for each respective trajectory in the plurality of trajectories based, at least in part, on the data obtained from the one or more sensor(s). For instance, the scoring system 220 can score each trajectory against a cost function that ensures safe, efficient, and comfortable vehicle motion." – see at least Phillips: paragraph 0122);
and selecting a trajectory from the plurality of trajectories for the machine based at least on evaluating the respective series of the time scores for one or more of the plurality of trajectories ("The vehicle computing system can select the candidate trajectory with the lowest determined cost." – see at least Phillips: paragraph 0027).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to have modified Geisberger with these above aforementioned teachings from Phillips such that the one or more trajectories include a plurality of trajectories that are each a variation of the path and are each starting from a starting position of the path, and the method further includes: determining, for each given trajectory of the plurality of trajectories and using the cost scores, a respective series of location scores, wherein the location scores are adjusted to correspond to the given trajectory, and selecting a trajectory from the plurality of trajectories for the machine based at least on evaluating the respective series of the time scores for one or more of the plurality of trajectories. At the time of the effective filing date of the claimed invention, one of ordinary skill in the art would have been motivated to incorporate Phillips’ method of generating candidate trajectories with Geisberger’s route planning system in order to adjust an initial travel path (“The offset profile can include a plurality of offset values, each offset value representing an amount and direction of lateral offset from the initial travel path.” – see at least Phillips: paragraph 0026). Doing so would provide the benefit of allowing the vehicle to autonomously avoid objects that obstruct the initial travel path, and to generate candidate trajectories which improve vehicle efficiency (“The offset profile can indicate a lateral movement for the autonomous vehicle that would allow it to avoid an object (e.g., within a lane, using a partial lane departure, etc.). As such, a lateral offset profile can increase the number of candidate trajectories to be considered by the autonomous vehicle and allow for more efficient vehicle movement.” – see at least Phillips: paragraph 0026).
Regarding claim 9, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger does not explicitly disclose, but Phillips teaches:
wherein the generating the one or more trajectories corresponding to the nominal path includes laterally varying a plurality of positions along the nominal path to adjust the plurality of position to a corresponding plurality of positions along each of the one or more trajectories while maintaining curvature of the nominal path for each of the one or more trajectories (“FIG. 6 depicts a graphical representation of a plurality of candidate trajectories according to example embodiments of the present disclosure. As seen herein, the plurality of offset profiles (e.g., offset profiles 400 in FIG. 4) can be applied to an initial travel path (e.g., initial travel path 500 in FIG. 5) to create a plurality of candidate trajectories. These candidate trajectories can be evaluated (e.g., a cost value can be generated) such that the best candidate trajectory can be selected.” – see at least Phillips: paragraph 0143) (The examiner notes that Fig. 6 of Phillips as shown above illustrates a plurality of trajectories which each include a plurality of positions which are lateral offsets of positions of an initial travel path, which maintains the curvature of the initial travel path for each of the plurality of trajectories).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to have modified Geisberger with these above aforementioned teachings from Phillips such that the generating the one or more trajectories corresponding to the path includes laterally varying a plurality of positions along the path to adjust the plurality of position to a corresponding plurality of positions along each of the one or more trajectories while maintaining curvature of the path for each of the one or more trajectories. At the time of the effective filing date of the claimed invention, one of ordinary skill in the art would have been motivated to incorporate Phillips’ method of generating candidate trajectories with Geisberger’s route planning system in order to adjust an initial travel path (“The offset profile can include a plurality of offset values, each offset value representing an amount and direction of lateral offset from the initial travel path.” – see at least Phillips: paragraph 0026). Doing so would provide the benefit of allowing the vehicle to autonomously avoid objects that obstruct the initial travel path, and to generate candidate trajectories which improve vehicle efficiency (“The offset profile can indicate a lateral movement for the autonomous vehicle that would allow it to avoid an object (e.g., within a lane, using a partial lane departure, etc.). As such, a lateral offset profile can increase the number of candidate trajectories to be considered by the autonomous vehicle and allow for more efficient vehicle movement.” – see at least Phillips: paragraph 0026).
Regarding claim 10, this claim is substantially similar to claim 1 and is, therefore, rejected in the same manner as claim 1 as has been set forth above.
Regarding claim 11, this claim is substantially similar to claim 2 and is, therefore, rejected in the same manner as claim 2 as has been set forth above.
Regarding claim 12, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger further teaches:
wherein the cost values include sequential time rewards for the potential future locations, the sequential time rewards indicating a traversal time to reach the proxy destination (“Costs may be assigned to arcs of the graph to apply weights based on the travel time between locations, and may take into account the distance between particular locations, the type of road, traffic conditions, and other factors which may affect travel time.” – see at least Geisberger: paragraph 0003)
Regarding claim 13, this claim is substantially similar to claim 4 and is, therefore, rejected in the same manner as claim 4 as has been set forth above.
Regarding claim 14, this claim is substantially similar to claim 6 and is, therefore, rejected in the same manner as claim 6 as has been set forth above.
Regarding claim 15, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger does not explicitly disclose, but Phillips teaches:
wherein the one or more control operations correspond to the machine implementing a trajectory of the one or more trajectories ("The method can include controlling, by the computing system, motion of the autonomous vehicle based, at least in part, on the trajectory." – see at least Phillips: paragraph 0005).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to have modified Geisberger with these above aforementioned teachings from Phillips such that the one or more control operations correspond to the machine implementing a trajectory of the one or more trajectories. At the time of the effective filing date of the claimed invention, one of ordinary skill in the art would have been motivated to incorporate Phillips’ method of generating altered trajectories with Geisberger’s route planning system in order to adjust an initial travel path (“The offset profile can include a plurality of offset values, each offset value representing an amount and direction of lateral offset from the initial travel path.” – see at least Phillips: paragraph 0026). Doing so would provide the benefit of allowing the vehicle to travel according to the selected trajectory (“Once a candidate trajectory has been selected and optimized, the data associated with the trajectory can be communicated to a vehicle controller. The controller can cause the autonomous vehicle to move in accordance with the trajectory, thereby implementing the trajectory's velocity and offset profiles to efficiently maintain vehicle speed with gentle acceleration, while avoiding any objects within the vehicle's environment.” – see at least Phillips: paragraph 0029).
Regarding claim 16, this claim is substantially similar to claim 1 and is, therefore, rejected in the same manner as claim 1 as has been set forth above.
Regarding claim 17, this claim is substantially similar to claim 12 and is, therefore, rejected in the same manner as claim 12 as has been set forth above.
Regarding claim 19, this claim is substantially similar to claim 4 and is, therefore, rejected in the same manner as claim 4 as has been set forth above.
Regarding claim 20, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger further teaches:
wherein the location score comprises an expected time reward of the proxy destination from the planned route (“Costs may be assigned to arcs of the graph to apply weights based on the travel time between locations, and may take into account the distance between particular locations, the type of road, traffic conditions, and other factors which may affect travel time.” – see at least Geisberger: paragraph 0003).
Claim 18 is rejected under 35 U.S.C. 103 as being unpatentable over Geisberger, in view of Phillips, further in view of Takahashi (US 2020/0231150), hereinafter referred to as Takahashi. Takahashi is considered analogous to the claimed invention because they are in the same field of determining travel routes for a vehicle.
Regarding claim 18, Geisberger in view of Phillips teaches all of the elements of the current invention as stated above. Geisberger does not explicitly disclose, but Takahashi teaches:
wherein the nodes include a first series of nodes along a first segment of a first lane and a second series of nodes along a second segment of a second lane ("According to the present disclosure that is configured as described above, in the case where the sampling point is located within the host vehicle lane, it is possible to appropriately secure the influence of the route cost related to the lane centering on the route selection. On the other hand, in the case where the sampling point is located on the outside of the host vehicle lane, it is possible to appropriately suppress the influence of the route cost related to the lane centering on the route selection." – see at least Takahashi: paragraph 0021) (The examiner notes that based on at least the cited section of paragraph 0021 of Takahashi, as well as Fig. 2 of Takahashi as shown below, the sampling points may correspond to at least a first route segment which involves traveling along a first lane that the host vehicle is currently traveling in, or a second route segment which involves traveling in a second lane which is different from the first lane).
PNG
media_image2.png
383
728
media_image2.png
Greyscale
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to have modified Geisberger with these above aforementioned teachings from Takahashi such that the nodes include a first series of nodes along a first segment of a first lane and a second series of nodes along a second segment of a second lane. At the time of the effective filing date of the claimed invention, one of ordinary skill in the art would have been motivated to incorporate Takahashi’s method of determining route costs for travelling in different lanes with Geisberger’s route planning system in order to evaluate a route cost for a route that involves changing lanes (“Furthermore, in this embodiment, unlike the case where the sampling point SP is located within the host vehicle lane 5a, in the case where the sampling point SP is located on the outside of the host vehicle lane 5a, the change rate of the route cost with respect to the distance from the center line C1 is set to be the same among the short-distance area, the middle-distance area, and the long-distance area (the gradients of the graphs G1, G2, and G3 are set to be the same).” – see at least Takahashi: paragraph 0079). Doing so would provide the benefit of determining a lowest cost route among route segments corresponding to different lanes (“Moreover, lattice-based graphs are constructed by applying a set of motion primitives to each state expanded during the search in order to generate valid successor states. By doing this, they generate edges in the search graph between the (possibly non-adjacent) discretized states which serve as the graph nodes. A graph search algorithm, such as A* act on this lattice to generate a trajectory as a sequence of motion primitives between the start and goal state.” – see at least Takahashi: paragraph 0084).
Response to Arguments
Applicant’s arguments filed 24 October 2025 with regards to the rejections of claims 1-20 under 35 U.S.C. 103 have been fully considered but they are not persuasive. Therefore, the claims remain rejected using the same prior art references as previously relied upon. As appropriate, new grounds of rejection are made to address amendments to the claims in view of the previously relied upon references by Geisberger, Phillips, and Takahashi.
In particular, the Applicant asserts that the combination of references does not teach or suggested the amended claims. Namely, the Applicant asserts that “Geisberger does not disclose that the intermediate node (alleged proxy destination) is selected “along a planned route to a destination,” as recited in amended claimed 1” and “Instead, the intermediate node is generated as an initial portion of a route to a destination node that is being planned using the graph data structure”. As best understood by the examiner, the Applicant’s arguments do not clearly distinguish the intermediate node taught by Geisberger from the claimed proxy destination, because both the intermediate node taught by Geisberger and the claimed proxy destination are representative of locations along a planned route to a destination.
Based on at least paragraph 0037 of the specification of the instant application, the claimed proxy destination is being interpreted as a location centered some distance along a suggested route, which is used as a temporary proxy destination during route planning. This is considered to be substantially similar to the intermediate node of Geisberger, which is a node that connects a path from a source node 304 to a destination node 305 at an intermediate point at which an initial graph search stops, as described in at least paragraphs 0051-0052 of Geisberger, and as set forth in further detail above in the section for rejections under 35 U.S.C. 103. In other words, the intermediate node as taught by Geisberger is considered to be “along a planned route to a destination” as claimed.
The Applicant further asserts that Geisberger does not teach or suggest “based at least on the selecting, computing cost values associated with nodes corresponding to potential future locations of the machine in a graph based at least on propagating a location score associated with the proxy destination through the nodes” and “searching, using the cost values, the nodes for a nominal path to the proxy destination”. The Applicant references that Geisberger “uses precomputed data to complete the path from the intermediate node to the destinate node” as opposed to performing the aforementioned claimed functions, but it is unclear how the use of precomputed data as taught by Geisberger would preclude performing the claimed functions. In particular, the precomputed data of Geisberger is based on traffic prediction data and is used to determine a route from the intermediate node to the destination node, which is representative of a portion of the route for which real-time traffic data is not reliable (“The initial graph search is stopped based on a preset condition, which is set based on the observation that real-time traffic data is only good to use for some time (e.g: 30 minutes in the future). Precomputed data based on traffic prediction data available at precomputation time is then used for the later part of the route.” – see at least Geisberger: paragraph 0016). In other words, as best understood by the examiner, the precomputed data of Geisberger is used after an initial graph search, whereas cost values for the initial graph search are determined based on real-time traffic data rather than precomputed data. Since the initial graph search to the intermediate node as taught by Geisberger corresponds to the claimed searching for a nominal path to the proxy destination as set forth above, and Geisberger teaches that the initial graph search utilizes real-time traffic data rather than precomputed data, the use of precomputed data is considered irrelevant to these aforementioned limitations.
Instead, with regard to the aforementioned limitations related to computing cost values based at least on propagating a location score through the nodes and using the cost values to search for a nominal path to the proxy destination, Geisberger teaches the use of well-known route searching techniques such as Dijkstra’s algorithm and the A* algorithm to compute a sum of costs for a connected sequence of arcs from a source node to a target node (“Optimal routes may be calculated by way of a graph search algorithm on the weighted graph. Known graph search algorithms include Dijkstra's algorithm and the A* search algorithm, which compute a connected sequence of arcs from a source node to a target node such that the sum of the arc costs is minimal over all such paths.” – see at least Geisberger: paragraph 0004). In this manner, the sum of arc costs between the source node and the intermediate node is considered to correspond to the claimed propagation of a location score through the nodes. Further, at least paragraph 0040 of the specification of the instant application recites using Dijkstra’s algorithm, and/or another shortest path algorithm type, to search a lane graph and settle nodes, much like the aforementioned teachings of Geisberger, which provides further evidence that the claimed steps are substantially similar to the teachings of Geisberger.
As best understood by the examiner, the claimed steps relating to computing cost values associated with nodes based at least on propagating a location score through the nodes, and using the cost values to search a nominal path is a well-known process in the art which can be performed by commonly used shortest path search algorithms including Dijkstra's algorithm and the A* search algorithm, such as in the manner taught by Geisberger for searching a path to an intermediate node. The examiner has cited additional references which, while not relied upon to reject the claims, provide additional evidence that the claimed process of computing cost values by propagating a location score through nodes of a graph and using the cost values to search for a path is well known in the art. For example, Blewitt (US 2002/0169543), hereinafter referred to as Blewitt, teaches a long distance routing method including applying Dijkstra’s algorithm to endpoints of a route within a road network modelled as a graph of edges and vertices, wherein cost values are propagated to vertices (i.e. nodes) in the graph from the route endpoints (see at least paragraphs 0012 and 0018-0021 of Blewitt). As such, the amended claims are considered to be fully taught by the prior art.
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.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DOMINICK ANTHONY MULDER whose telephone number is (571)272-3610. 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, Vivek Koppikar can be reached on (571) 272-5109. 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.M./Examiner, Art Unit 3667
/TUAN C TO/Primary Examiner, Art Unit 3667