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 Application
Claims 1-20 are pending.
Claims 1, 8, and 14 are independent.
Claims 1, 8, and 14 have been amended.
This FINAL action is in response to “Amendments and Remarks” received on 06 February 2026.
Response to Amendment/Remarks
With respect to Applicant’s remarks filed 06 February 2026, Applicant’s “Amendments and Remarks” have been fully considered and were not wholly persuasive. Applicant’s remarks will be addressed in sequential order as they were presented.
With respect to objection of the claims, Applicant’s “Amendments and Remarks” have been fully considered and are persuasive. Therefore, the objections to the claims have been withdrawn.
With respect to claim rejections under 35 U.S.C. 101, Applicant’s “Amendments and Remarks” have been fully considered and are persuasive. Therefore, the rejection is withdrawn.
With respect to claim rejections under 35 U.S.C. 102 and/or 35 U.S.C. 103, Applicant’s “Amendments and Remarks” have been fully considered and are persuasive. Therefore, the rejection is withdrawn. However, upon further consideration, there is a new ground(s) of rejection in view of newly found prior art.
Final Office Action
Claim Interpretation
During examination, claims are given the broadest reasonable interpretation consistent with the specification and limitations in the specification are not read into the claims. See MPEP §2111, MPEP §2111.01 and In re Yamamoto et al., 222 USPQ 934 10 (Fed. Cir. 1984). Under a broadest reasonable interpretation, words of the claim must be given their plain meaning, unless such meaning is inconsistent with the specification. See MPEP 2111.01 (I). It is further noted it is improper to import claim limitations from the specification, i.e., a particular embodiment appearing in the written description may not be read into a claim when the claim language is broader than the embodiment. See 15 MPEP 2111.01 (II).
A first exception to the prohibition of reading limitations from the specification into the claims is when the Applicant for patent has provided a lexicographic definition for the term. See MPEP §2111.01 (IV). Following a review of the claims in view of the specification herein, the Office has found that Applicant has not provided any lexicographic definitions, either expressly or implicitly, for any claim terms or phrases with any reasonable clarity, deliberateness and precision. Accordingly, the Office concludes that Applicant has not acted as his/her own lexicographer.
A second exception to the prohibition of reading limitations from the specification into the claims is when the claimed feature is written as a means-plus-function. See 35 U.S.C. §112(f) and MPEP §2181-2183. As noted in MPEP §2181, a three-prong test is used to determine the scope of a means-plus-function limitation in a claim:
(A) the claim limitation uses the term "means" or "step" or a term used as a substitute for "means" that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function
(B) the term "means" or "step" or the generic placeholder is modified by functional language, typically, but not always linked by the transition word "for" (e.g., "means for") or another linking word or phrase, such as "configured to" or "so that"
(C) the term "means" or "step" or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
The Office has found herein that the claims do not contain limitations of means or means type language that must be analyzed under 35 U.S.C. §112 (f).
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.
Claims 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over Bin-Nun et al. (US 20220080962 A1), hereinafter Bin-Nun, in view of Yaghoubi et al. (US 20240042993 A1), hereinafter Yaghoubi, and further in view of Maseedu (US 11178028 B1).
Regarding claim 1, Bin-Nun discloses:
An autonomy computing system of an autonomous vehicle for controlling quality in planning a trajectory of the autonomous vehicle, comprising at least one processor in communication with at least one memory device, and the at least one processor programmed to (Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 1; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23):
process sensor data received from one or more sensors of the autonomous vehicle (Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23);
generate the trajectory of the autonomous vehicle based on the sensor data and a plurality of rules, wherein the at least one processor is further programmed generate the trajectory by (Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23):
analyzing a plurality of nodes in a graph search of the trajectory based on the plurality of rules, wherein the plurality of nodes correspond to points on a road along which the autonomous vehicle travels (Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
and generating the trajectory of navigating the road by minimizing a total cost associated with traversing along the trajectory, the total cost including the costs associated with the plurality of nodes (Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
However, Bin-Nun does not specifically state:
wherein at least one of the plurality of rules corresponds to at least one of a plurality of costs
each rule of the plurality of rules having a cost associated with violation of each rule
generate a log of violations of the plurality of rules at one or more nodes along the trajectory, wherein the log includes explanations of the violations in a human readable language;
and transmit the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system.
Yaghoubi teaches:
wherein at least one of the plurality of rules corresponds to at least one of a plurality of costs ([0078], In some embodiments, at least one processor receives sensor data after the operation of the AV. The sensor data is representative of scenarios encountered by the AV while navigating through the environment. Hierarchical rules of the hierarchical plurality of rules are applied to scenarios simulated by an AV stack to modify and improve the AV development after-the-fact (e.g., after operation of the AV, where sensor data is captured). In examples, this offline framework is configured to develop a transparent and reproducible rule-based pass/fail evaluation of AV trajectories in test scenarios. For example, in an offline framework, a given trajectory output by the planning system 404 is rejected if a trajectory that leads to a lesser violation of the rule priority structure (e.g., a rule with a lower priority as compared to the priority of the rule violated by the trajectory) is found. The planning system is modified and improved based on, at least in part, the rejected trajectory and data associated with the rejected trajectory. In some embodiments, the present techniques receive a fixed set of trajectories generated after-the-fact from a given scenario and determines a particular trajectory to evaluate if the AV passes or fails a predetermined test. The present techniques use a set of fixed trajectories to create a graph. In some embodiments, the graph is an edge weighted graph and weights are assigned to edges that correspond to trajectories based on rule violations. Each trajectory can be associated with one or more costs, each cost corresponding to a rule violation. Determining the fixed set of trajectories is described with respect to FIG. 7; Fig. 7)
each rule of the plurality of rules having a cost associated with violation of each rule ([0078], In some embodiments, at least one processor receives sensor data after the operation of the AV. The sensor data is representative of scenarios encountered by the AV while navigating through the environment. Hierarchical rules of the hierarchical plurality of rules are applied to scenarios simulated by an AV stack to modify and improve the AV development after-the-fact (e.g., after operation of the AV, where sensor data is captured). In examples, this offline framework is configured to develop a transparent and reproducible rule-based pass/fail evaluation of AV trajectories in test scenarios. For example, in an offline framework, a given trajectory output by the planning system 404 is rejected if a trajectory that leads to a lesser violation of the rule priority structure (e.g., a rule with a lower priority as compared to the priority of the rule violated by the trajectory) is found. The planning system is modified and improved based on, at least in part, the rejected trajectory and data associated with the rejected trajectory. In some embodiments, the present techniques receive a fixed set of trajectories generated after-the-fact from a given scenario and determines a particular trajectory to evaluate if the AV passes or fails a predetermined test. The present techniques use a set of fixed trajectories to create a graph. In some embodiments, the graph is an edge weighted graph and weights are assigned to edges that correspond to trajectories based on rule violations. Each trajectory can be associated with one or more costs, each cost corresponding to a rule violation. Determining the fixed set of trajectories is described with respect to FIG. 7; Fig. 7)
generate a log of violations of the plurality of rules at one or more nodes along the trajectory, wherein the log includes explanations of the violations in a human readable language (Fig. 9; [0094], FIG. 9 is a diagram of system 900 that calculates a priority (e.g., a score) for all or a portion of trajectories according to a hierarchical plurality of rules. A path can include multiple trajectories and the system 900 can calculate a priority of the path based on a highest priority of a trajectory of the path as compared to other trajectories of the path, a cumulative priority of the priorities of all or a portion of the trajectories of the path, etc. In the example of FIG. 9, a hierarchical plurality of rules 902 provides three exemplary hierarchical rules: R1 (highest priority), R2 (next highest priority), R3 (lowest priority). The system 900 can assign all or a portion of the hierarchical rules a base priority based on the hierarchical plurality of rules 902. The system 900 can further determine a priority of a violation of a rule by a trajectory based on the base priority and a level of a violation of the rule. For example, the hierarchical plurality of rules 902 indicates that a violation of rule R1 has a priority of 1 and the system 900 determines that a singular violation of rule R1, a lesser violation of rule R1 (as compared to other violations), etc. has a priority of 1 and multiple violations of rule R1, a greater violation of rule R1 (as compared to other violations), etc. has a priority of 2. Additionally, a fixed set of trajectories 904 includes a trajectory x, trajectory y, and trajectory z. The fixed set of trajectories may be the same as or similar to the trajectories 616 (FIG. 6) or trajectories 820, 822, or 824 of FIG. 8. In some embodiments, the fixed set of trajectories represent all or a portion of the actions that vehicles can make in traffic situations. In some examples, the fixed set of trajectories is generated using a planning system of an AV (e.g., planning system 404 of FIG. 4) in response to simulation in a predetermined scenario. In examples, the predetermined scenario is represented by AV compute inputs and outputs as the AV travels from a starting pose toward a destination; [0096], In the example of FIG. 9, system 900 identifies rule violations caused by all or a portion of the fixed set of trajectories to determine rule violation priorities 906 for each trajectory. In particular, the system 900 evaluates all or a portion of the rules to determine the rule violation priorities for a trajectory. At evaluation 908, the system 900 evaluates rule R1 to determine if trajectory x, trajectory y, or trajectory Z violates rule R1. In the example of FIG. 9, the system 900 determines that trajectory z violates rule R1, while trajectory x and trajectory y do not violate rule R1. The system 900 assigns trajectory z a priority of 1 with respect to rule R1. The system 900 assigns trajectories x and y a priority of 0 with respect to rule R1. At evaluation 910, the system 900 evaluates rule R2 to determine if trajectory x, trajectory y, or trajectory Z violates rule R2. In the example of FIG. 9, no trajectory violates rule R2. The system 900 assigns each trajectory a priority 0 with respect to rule R2. At evaluation 908 trajectory z is the only trajectory that violates R1, so the system 900 assigns a priority for violation of rule R1 to trajectory z. At evaluation 902, no trajectory violates rule R2 so the system 900 does not assign a priority for violation of rule R2 to any of the trajectories (or assigns a priority of 0));
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Yaghoubi into the invention of Bin-Nun to include rules having an associated cost and generating a log of rule violations as Yaghoubi discloses with a reasonable expectation of success. One would be motivated to incorporate aspects of the cited prior art to create a more robust system that generates a most optimal and safest route. Additionally, the claimed invention is merely a combination of old, well-known elements of an autonomous vehicle trajectory planner that minimizes cost associated with a trajectory as disclosed by Bin-Nun and including rules for planning trajectories which consider safety as taught by Yaghoubi. The combination each element merely would have performed the same function as it did separately, and one of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that the results of the combination would have been predictable.
However, Bin-Nun in view of Yaghoubi does not specifically state:
and transmit the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system.
Maseedu teaches:
and transmit the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system (Col. 4, Lines 51-64, The decoding server 230 can be a QCAT server, which is an integrated software package that acts as log translation server and allows decoding of device logs generated in the QMDL format. The decoding server 230 can have a translator 232 to translate the logs from the machine-readable format into a human readable format. In addition, the decoding server 230 can also contain custom scripts 234, such as Perl or Python scripts, that can perform further filtering of the logs, such as retrieving specific layer messages of the radio stack. The decoding server 230 can pass the translated and filtered logs to the automation server 210. The log parser 216 and the log monitor 218 can further analyze the logs to determine whether any problems are present).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Maseedu into the invention of Bin-Nun in view of Yaghoubi to include transmitting a log to a server to translate into human-readable language and filter for important aspects as Maseedu discloses with a reasonable expectation of success. One would be motivated to incorporate aspects of the cited prior art to create a more robust system that generates a traceable log at a server to offload vehicle computational resources. Additionally, the claimed invention is merely a combination of old, well-known elements of an autonomous vehicle trajectory planner that minimizes cost associated with a trajectory as disclosed by Bin-Nun in view of Yaghoubi and transmitting a log to a server to translate into human-readable language as taught by Maseedu. The combination each element merely would have performed the same function as it did separately, and one of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that the results of the combination would have been predictable.
Regarding claim 2, Bin-Nun in view of Yaghoubi and Maseedu teaches:
identifying a common parent node that has a first child node and a second child node, the common parent node and the first child node included in the trajectory, the second child node not included in the trajectory, the second child node having a lower cost than the first child node but having an end child node violating a rule having a priority higher than a rule violated by the first child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together).
Regarding claim 3, Bin-Nun in view of Yaghoubi and Maseedu teaches:
tracing back to the common parent node from the end child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
and recording the violations between the common parent node and the end child node (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects).
Regarding claim 4, Bin-Nun in view of Yaghoubi and Maseedu teaches:
wherein a parent node has a first child node and a second child node, the parent node included in the trajectory, the first child node having a higher cost than the second child node, the at least one processor is further programmed to (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects):
generate the trajectory by (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together):
expanding the trajectory to include the first child node only if a child node of the second child node violates a rule having a higher priority than a rule violated by the first child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together).
Regarding claim 5, Bin-Nun in view of Yaghoubi and Maseedu teaches:
transmit the log in real time (Bin-Nun: [0097], Computing devices 146 located on the AV 100 algorithmically generate control actions based on both realtime sensor data and prior information, allowing the AV system 120 to execute its autonomous driving capabilities; [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects; [0094], The communication interfaces 140 transmit data collected from sensors 121 or other data related to the operation of AV 100 to the remotely located database 134. In an embodiment, communication interfaces 140 transmit information that relates to teleoperations to the AV 100. In an embodiment, the AV 100 communicates with other remote ( e.g., "cloud") servers 136).
Regarding claim 6, Bin-Nun in view of Yaghoubi and Maseedu teaches:
transmit a graph of the trajectory (Bin-Nun: Fig. 10; [0097], Computing devices 146 located on the AV 100 algorithmically generate control actions based on both realtime sensor data and prior information, allowing the AV system 120 to execute its autonomous driving capabilities; [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects; [0094], The communication interfaces 140 transmit data collected from sensors 121 or other data related to the operation of AV 100 to the remotely located database 134. In an embodiment, communication interfaces 140 transmit information that relates to teleoperations to the AV 100. In an embodiment, the AV 100 communicates with other remote ( e.g., "cloud") servers 136).
Regarding claim 7, Bin-Nun in view of Yaghoubi and Maseedu teaches:
generate the log by (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects):
generating a plurality of violation sets (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects);
and combining the plurality of violation sets into the log (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects).
Regarding claim 8, Bin-Nun discloses:
A method for controlling quality in planning a trajectory of an autonomous vehicle, the method comprising (Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 1; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23):
processing sensor data received from one or more sensors of an autonomous vehicle (Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23);
generating the trajectory of the autonomous vehicle based on the sensor data and a plurality of rules, wherein generating the trajectory further comprises (Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23):
analyzing a plurality of nodes in a graph search of the trajectory based on the plurality of rules, wherein the plurality of nodes correspond to points on a road along which the autonomous vehicle travels (Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
and generating the trajectory of navigating the road by minimizing a total cost associated with traversing along the trajectory, the total cost including the costs associated with the plurality of node (Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
However, Bin-Nun does not specifically state:
wherein at least one of the plurality of rules corresponds to at least one of a plurality of costs
each rule of the plurality of rules having a cost associated with violation of each rule
generating a log of violations of the plurality of rules at one or more nodes along the trajectory, wherein the log includes explanations of the violations in a human readable language;
and transmitting the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system.
Yaghoubi teaches:
wherein at least one of the plurality of rules corresponds to at least one of a plurality of costs ([0078], In some embodiments, at least one processor receives sensor data after the operation of the AV. The sensor data is representative of scenarios encountered by the AV while navigating through the environment. Hierarchical rules of the hierarchical plurality of rules are applied to scenarios simulated by an AV stack to modify and improve the AV development after-the-fact (e.g., after operation of the AV, where sensor data is captured). In examples, this offline framework is configured to develop a transparent and reproducible rule-based pass/fail evaluation of AV trajectories in test scenarios. For example, in an offline framework, a given trajectory output by the planning system 404 is rejected if a trajectory that leads to a lesser violation of the rule priority structure (e.g., a rule with a lower priority as compared to the priority of the rule violated by the trajectory) is found. The planning system is modified and improved based on, at least in part, the rejected trajectory and data associated with the rejected trajectory. In some embodiments, the present techniques receive a fixed set of trajectories generated after-the-fact from a given scenario and determines a particular trajectory to evaluate if the AV passes or fails a predetermined test. The present techniques use a set of fixed trajectories to create a graph. In some embodiments, the graph is an edge weighted graph and weights are assigned to edges that correspond to trajectories based on rule violations. Each trajectory can be associated with one or more costs, each cost corresponding to a rule violation. Determining the fixed set of trajectories is described with respect to FIG. 7; Fig. 7)
each rule of the plurality of rules having a cost associated with violation of each rule ([0078], In some embodiments, at least one processor receives sensor data after the operation of the AV. The sensor data is representative of scenarios encountered by the AV while navigating through the environment. Hierarchical rules of the hierarchical plurality of rules are applied to scenarios simulated by an AV stack to modify and improve the AV development after-the-fact (e.g., after operation of the AV, where sensor data is captured). In examples, this offline framework is configured to develop a transparent and reproducible rule-based pass/fail evaluation of AV trajectories in test scenarios. For example, in an offline framework, a given trajectory output by the planning system 404 is rejected if a trajectory that leads to a lesser violation of the rule priority structure (e.g., a rule with a lower priority as compared to the priority of the rule violated by the trajectory) is found. The planning system is modified and improved based on, at least in part, the rejected trajectory and data associated with the rejected trajectory. In some embodiments, the present techniques receive a fixed set of trajectories generated after-the-fact from a given scenario and determines a particular trajectory to evaluate if the AV passes or fails a predetermined test. The present techniques use a set of fixed trajectories to create a graph. In some embodiments, the graph is an edge weighted graph and weights are assigned to edges that correspond to trajectories based on rule violations. Each trajectory can be associated with one or more costs, each cost corresponding to a rule violation. Determining the fixed set of trajectories is described with respect to FIG. 7; Fig. 7)
generating a log of violations of the plurality of rules at one or more nodes along the trajectory, wherein the log includes explanations of the violations in a human readable language (Fig. 9; [0094], FIG. 9 is a diagram of system 900 that calculates a priority (e.g., a score) for all or a portion of trajectories according to a hierarchical plurality of rules. A path can include multiple trajectories and the system 900 can calculate a priority of the path based on a highest priority of a trajectory of the path as compared to other trajectories of the path, a cumulative priority of the priorities of all or a portion of the trajectories of the path, etc. In the example of FIG. 9, a hierarchical plurality of rules 902 provides three exemplary hierarchical rules: R1 (highest priority), R2 (next highest priority), R3 (lowest priority). The system 900 can assign all or a portion of the hierarchical rules a base priority based on the hierarchical plurality of rules 902. The system 900 can further determine a priority of a violation of a rule by a trajectory based on the base priority and a level of a violation of the rule. For example, the hierarchical plurality of rules 902 indicates that a violation of rule R1 has a priority of 1 and the system 900 determines that a singular violation of rule R1, a lesser violation of rule R1 (as compared to other violations), etc. has a priority of 1 and multiple violations of rule R1, a greater violation of rule R1 (as compared to other violations), etc. has a priority of 2. Additionally, a fixed set of trajectories 904 includes a trajectory x, trajectory y, and trajectory z. The fixed set of trajectories may be the same as or similar to the trajectories 616 (FIG. 6) or trajectories 820, 822, or 824 of FIG. 8. In some embodiments, the fixed set of trajectories represent all or a portion of the actions that vehicles can make in traffic situations. In some examples, the fixed set of trajectories is generated using a planning system of an AV (e.g., planning system 404 of FIG. 4) in response to simulation in a predetermined scenario. In examples, the predetermined scenario is represented by AV compute inputs and outputs as the AV travels from a starting pose toward a destination; [0096], In the example of FIG. 9, system 900 identifies rule violations caused by all or a portion of the fixed set of trajectories to determine rule violation priorities 906 for each trajectory. In particular, the system 900 evaluates all or a portion of the rules to determine the rule violation priorities for a trajectory. At evaluation 908, the system 900 evaluates rule R1 to determine if trajectory x, trajectory y, or trajectory Z violates rule R1. In the example of FIG. 9, the system 900 determines that trajectory z violates rule R1, while trajectory x and trajectory y do not violate rule R1. The system 900 assigns trajectory z a priority of 1 with respect to rule R1. The system 900 assigns trajectories x and y a priority of 0 with respect to rule R1. At evaluation 910, the system 900 evaluates rule R2 to determine if trajectory x, trajectory y, or trajectory Z violates rule R2. In the example of FIG. 9, no trajectory violates rule R2. The system 900 assigns each trajectory a priority 0 with respect to rule R2. At evaluation 908 trajectory z is the only trajectory that violates R1, so the system 900 assigns a priority for violation of rule R1 to trajectory z. At evaluation 902, no trajectory violates rule R2 so the system 900 does not assign a priority for violation of rule R2 to any of the trajectories (or assigns a priority of 0));
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Yaghoubi into the invention of Bin-Nun to include rules having an associated cost and generating a log of rule violations as Yaghoubi discloses with a reasonable expectation of success. One would be motivated to incorporate aspects of the cited prior art to create a more robust system that generates a most optimal and safest route. Additionally, the claimed invention is merely a combination of old, well-known elements of an autonomous vehicle trajectory planner that minimizes cost associated with a trajectory as disclosed by Bin-Nun and including rules for planning trajectories which consider safety as taught by Yaghoubi. The combination each element merely would have performed the same function as it did separately, and one of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that the results of the combination would have been predictable.
However, Bin-Nun in view of Yaghoubi does not specifically state:
and transmitting the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system.
Maseedu teaches:
and transmit the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system (Col. 4, Lines 51-64, The decoding server 230 can be a QCAT server, which is an integrated software package that acts as log translation server and allows decoding of device logs generated in the QMDL format. The decoding server 230 can have a translator 232 to translate the logs from the machine-readable format into a human readable format. In addition, the decoding server 230 can also contain custom scripts 234, such as Perl or Python scripts, that can perform further filtering of the logs, such as retrieving specific layer messages of the radio stack. The decoding server 230 can pass the translated and filtered logs to the automation server 210. The log parser 216 and the log monitor 218 can further analyze the logs to determine whether any problems are present).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Maseedu into the invention of Bin-Nun in view of Yaghoubi to include transmitting a log to a server to translate into human-readable language and filter for important aspects as Maseedu discloses with a reasonable expectation of success. One would be motivated to incorporate aspects of the cited prior art to create a more robust system that generates a traceable log at a server to offload vehicle computational resources. Additionally, the claimed invention is merely a combination of old, well-known elements of an autonomous vehicle trajectory planner that minimizes cost associated with a trajectory as disclosed by Bin-Nun in view of Yaghoubi and transmitting a log to a server to translate into human-readable language as taught by Maseedu. The combination each element merely would have performed the same function as it did separately, and one of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that the results of the combination would have been predictable.
Regarding claim 9, Bin-Nun in view of Yaghoubi and Maseedu:
identifying a common parent node that has a first child node and a second child node, the common parent node and the first child node included in the trajectory, the second child node not included in the trajectory, the second child node having a lower cost than the first child node but having an end child node violating a rule having a priority higher than a rule violated by the first child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together).
Regarding claim 10, Bin-Nun in view of Yaghoubi and Maseedu:
tracing back to the common parent node from the end child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
and recording the violations between the common parent node and the end child node (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects).
Regarding claim 11, Bin-Nun in view of Yaghoubi and Maseedu:
wherein a parent node has a first child node and a second child node, the parent node included in the trajectory, the first child node having a higher cost than the second child node, generating the trajectory further comprising (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects):
expanding the trajectory to include the first child node only if a child node of the second child node violates a rule having a higher priority than a rule violated by the first child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together).
Regarding claim 12, Bin-Nun in view of Yaghoubi and Maseedu:
transmitting the log in real time (Bin-Nun: [0097], Computing devices 146 located on the AV 100 algorithmically generate control actions based on both realtime sensor data and prior information, allowing the AV system 120 to execute its autonomous driving capabilities; [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects; [0094], The communication interfaces 140 transmit data collected from sensors 121 or other data related to the operation of AV 100 to the remotely located database 134. In an embodiment, communication interfaces 140 transmit information that relates to teleoperations to the AV 100. In an embodiment, the AV 100 communicates with other remote ( e.g., "cloud") servers 136).
Regarding claim 13, Bin-Nun in view of Yaghoubi and Maseedu:
transmitting a graph of the trajectory (Bin-Nun: Fig. 10; [0097], Computing devices 146 located on the AV 100 algorithmically generate control actions based on both realtime sensor data and prior information, allowing the AV system 120 to execute its autonomous driving capabilities; [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects; [0094], The communication interfaces 140 transmit data collected from sensors 121 or other data related to the operation of AV 100 to the remotely located database 134. In an embodiment, communication interfaces 140 transmit information that relates to teleoperations to the AV 100. In an embodiment, the AV 100 communicates with other remote ( e.g., "cloud") servers 136).
Regarding claim 14, Bin-Nun discloses:
One or more non-transitory machine-readable storage media for controlling quality in planning a trajectory of an autonomous vehicle, comprising a plurality of instructions stored thereon that, in response to being executed, cause a system to ([0104], In an embodiment, the computer system 300 includes a bus 302 or other communication mechanism for communicating information, and a hardware processor 304 coupled with a bus 302 for processing information. The hardware processor 304 is, for example, a general-purpose microprocessor. The computer system 300 also includes a main memory 306, such as a random-access memory (RAM) or other dynamic storage device, coupled to the bus 302 for storing information and instructions to be executed by processor 304. In one implementation, the main memory 306 is used for storing temporary variables or other intermediate information during execution of instructions to be executed by the processor 304. Such instructions, when stored in non-transitory storage media accessible to the processor 304, render the computer system 300 into a special-purpose machine that is customized to perform the operations specified in the instructions; Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 1; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23):
process sensor data received from one or more sensors of the autonomous vehicle (Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23);
generate the trajectory of the autonomous vehicle based on the sensor data and a plurality of rules, wherein the plurality of instructions further cause the system to generate the trajectory by (Abstract, Methods for vehicle operation using a behavioral rule model include receiving sensor data from a first set of sensors and a second set of sensors. The sensor data represents operation of the vehicle with respect to one or more objects. Violations of a behavioral model of the operation of the vehicle are determined based on the sensor data. A first risk level of the one or more violations is determined based on a distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, a trajectory is generated. The trajectory has a second risk level lower than the threshold risk level. The vehicle is operated based on the trajectory to avoid a collision of the vehicle and the one or more objects; Fig. 4; Fig. 5; Fig. 9; Fig. 10; Fig. 14; Fig. 22; Fig. 23):
analyzing a plurality of nodes in a graph search of the trajectory based on the plurality of rules, wherein the plurality of nodes correspond to points on a road along which the autonomous vehicle travels (Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
and generating the trajectory of navigating the road by minimizing a total cost associated with traversing along the trajectory, the total cost including the costs associated with the plurality of nodes (Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
However, Bin-Nun does not specifically state:
wherein at least one of the plurality of rules corresponds to at least one of a plurality of costs
each rule of the plurality of rules having a cost associated with violation of each rule
generate a log of violations of the plurality of rules at one or more nodes along the trajectory, wherein the log includes explanations of the violations in a human readable language;
and transmit the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system.
Yaghoubi teaches:
wherein at least one of the plurality of rules corresponds to at least one of a plurality of costs ([0078], In some embodiments, at least one processor receives sensor data after the operation of the AV. The sensor data is representative of scenarios encountered by the AV while navigating through the environment. Hierarchical rules of the hierarchical plurality of rules are applied to scenarios simulated by an AV stack to modify and improve the AV development after-the-fact (e.g., after operation of the AV, where sensor data is captured). In examples, this offline framework is configured to develop a transparent and reproducible rule-based pass/fail evaluation of AV trajectories in test scenarios. For example, in an offline framework, a given trajectory output by the planning system 404 is rejected if a trajectory that leads to a lesser violation of the rule priority structure (e.g., a rule with a lower priority as compared to the priority of the rule violated by the trajectory) is found. The planning system is modified and improved based on, at least in part, the rejected trajectory and data associated with the rejected trajectory. In some embodiments, the present techniques receive a fixed set of trajectories generated after-the-fact from a given scenario and determines a particular trajectory to evaluate if the AV passes or fails a predetermined test. The present techniques use a set of fixed trajectories to create a graph. In some embodiments, the graph is an edge weighted graph and weights are assigned to edges that correspond to trajectories based on rule violations. Each trajectory can be associated with one or more costs, each cost corresponding to a rule violation. Determining the fixed set of trajectories is described with respect to FIG. 7; Fig. 7)
each rule of the plurality of rules having a cost associated with violation of each rule ([0078], In some embodiments, at least one processor receives sensor data after the operation of the AV. The sensor data is representative of scenarios encountered by the AV while navigating through the environment. Hierarchical rules of the hierarchical plurality of rules are applied to scenarios simulated by an AV stack to modify and improve the AV development after-the-fact (e.g., after operation of the AV, where sensor data is captured). In examples, this offline framework is configured to develop a transparent and reproducible rule-based pass/fail evaluation of AV trajectories in test scenarios. For example, in an offline framework, a given trajectory output by the planning system 404 is rejected if a trajectory that leads to a lesser violation of the rule priority structure (e.g., a rule with a lower priority as compared to the priority of the rule violated by the trajectory) is found. The planning system is modified and improved based on, at least in part, the rejected trajectory and data associated with the rejected trajectory. In some embodiments, the present techniques receive a fixed set of trajectories generated after-the-fact from a given scenario and determines a particular trajectory to evaluate if the AV passes or fails a predetermined test. The present techniques use a set of fixed trajectories to create a graph. In some embodiments, the graph is an edge weighted graph and weights are assigned to edges that correspond to trajectories based on rule violations. Each trajectory can be associated with one or more costs, each cost corresponding to a rule violation. Determining the fixed set of trajectories is described with respect to FIG. 7; Fig. 7)
generate a log of violations of the plurality of rules at one or more nodes along the trajectory, wherein the log includes explanations of the violations in a human readable language (Fig. 9; [0094], FIG. 9 is a diagram of system 900 that calculates a priority (e.g., a score) for all or a portion of trajectories according to a hierarchical plurality of rules. A path can include multiple trajectories and the system 900 can calculate a priority of the path based on a highest priority of a trajectory of the path as compared to other trajectories of the path, a cumulative priority of the priorities of all or a portion of the trajectories of the path, etc. In the example of FIG. 9, a hierarchical plurality of rules 902 provides three exemplary hierarchical rules: R1 (highest priority), R2 (next highest priority), R3 (lowest priority). The system 900 can assign all or a portion of the hierarchical rules a base priority based on the hierarchical plurality of rules 902. The system 900 can further determine a priority of a violation of a rule by a trajectory based on the base priority and a level of a violation of the rule. For example, the hierarchical plurality of rules 902 indicates that a violation of rule R1 has a priority of 1 and the system 900 determines that a singular violation of rule R1, a lesser violation of rule R1 (as compared to other violations), etc. has a priority of 1 and multiple violations of rule R1, a greater violation of rule R1 (as compared to other violations), etc. has a priority of 2. Additionally, a fixed set of trajectories 904 includes a trajectory x, trajectory y, and trajectory z. The fixed set of trajectories may be the same as or similar to the trajectories 616 (FIG. 6) or trajectories 820, 822, or 824 of FIG. 8. In some embodiments, the fixed set of trajectories represent all or a portion of the actions that vehicles can make in traffic situations. In some examples, the fixed set of trajectories is generated using a planning system of an AV (e.g., planning system 404 of FIG. 4) in response to simulation in a predetermined scenario. In examples, the predetermined scenario is represented by AV compute inputs and outputs as the AV travels from a starting pose toward a destination; [0096], In the example of FIG. 9, system 900 identifies rule violations caused by all or a portion of the fixed set of trajectories to determine rule violation priorities 906 for each trajectory. In particular, the system 900 evaluates all or a portion of the rules to determine the rule violation priorities for a trajectory. At evaluation 908, the system 900 evaluates rule R1 to determine if trajectory x, trajectory y, or trajectory Z violates rule R1. In the example of FIG. 9, the system 900 determines that trajectory z violates rule R1, while trajectory x and trajectory y do not violate rule R1. The system 900 assigns trajectory z a priority of 1 with respect to rule R1. The system 900 assigns trajectories x and y a priority of 0 with respect to rule R1. At evaluation 910, the system 900 evaluates rule R2 to determine if trajectory x, trajectory y, or trajectory Z violates rule R2. In the example of FIG. 9, no trajectory violates rule R2. The system 900 assigns each trajectory a priority 0 with respect to rule R2. At evaluation 908 trajectory z is the only trajectory that violates R1, so the system 900 assigns a priority for violation of rule R1 to trajectory z. At evaluation 902, no trajectory violates rule R2 so the system 900 does not assign a priority for violation of rule R2 to any of the trajectories (or assigns a priority of 0));
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Yaghoubi into the invention of Bin-Nun to include rules having an associated cost and generating a log of rule violations as Yaghoubi discloses with a reasonable expectation of success. One would be motivated to incorporate aspects of the cited prior art to create a more robust system that generates a most optimal and safest route. Additionally, the claimed invention is merely a combination of old, well-known elements of an autonomous vehicle trajectory planner that minimizes cost associated with a trajectory as disclosed by Bin-Nun and including rules for planning trajectories which consider safety as taught by Yaghoubi. The combination each element merely would have performed the same function as it did separately, and one of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that the results of the combination would have been predictable.
However, Bin-Nun in view of Yaghoubi does not specifically state:
and transmit the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system.
Maseedu teaches:
and transmit the log over a wireless communication channel to a remote computing device configured to process the log, wherein the explanations of the violations in the human readable language in the log enable pinpointing what rules are violated at which nodes in causing selection of the trajectory and control of quality of the trajectory in autonomous driving of the autonomous vehicle without noticeable detrimental effects on computation resources of the autonomy computing system (Col. 4, Lines 51-64, The decoding server 230 can be a QCAT server, which is an integrated software package that acts as log translation server and allows decoding of device logs generated in the QMDL format. The decoding server 230 can have a translator 232 to translate the logs from the machine-readable format into a human readable format. In addition, the decoding server 230 can also contain custom scripts 234, such as Perl or Python scripts, that can perform further filtering of the logs, such as retrieving specific layer messages of the radio stack. The decoding server 230 can pass the translated and filtered logs to the automation server 210. The log parser 216 and the log monitor 218 can further analyze the logs to determine whether any problems are present).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Maseedu into the invention of Bin-Nun in view of Yaghoubi to include transmitting a log to a server to translate into human-readable language and filter for important aspects as Maseedu discloses with a reasonable expectation of success. One would be motivated to incorporate aspects of the cited prior art to create a more robust system that generates a traceable log at a server to offload vehicle computational resources. Additionally, the claimed invention is merely a combination of old, well-known elements of an autonomous vehicle trajectory planner that minimizes cost associated with a trajectory as disclosed by Bin-Nun in view of Yaghoubi and transmitting a log to a server to translate into human-readable language as taught by Maseedu. The combination each element merely would have performed the same function as it did separately, and one of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that the results of the combination would have been predictable.
Regarding claim 15, Bin-Nun in view of Yaghoubi in view of Maseedu:
identifying a common parent node that has a first child node and a second child node, the common parent node and the first child node included in the trajectory, the second child node not included in the trajectory, the second child node having a lower cost than the first child node but having an end child node violating a rule having a priority higher than a rule violated by the first child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together).
Regarding claim 16, Bin-Nun in view of Yaghoubi in view of Maseedu:
tracing back to the common parent node from the end child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together);
and recording the violations between the common parent node and the end child node (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects).
Regarding claim 17, Bin-Nun in view of Yaghoubi in view of Maseedu:
wherein a parent node has a first child node and a second child node, the parent node included in the trajectory, the first child node having a higher cost than the second child node, the plurality of instructions further cause the system to generate the trajectory by (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects):
expanding the trajectory to include the first child node only if a child node of the second child node violates a rule having a higher priority than a rule violated by the first child node (Bin-Nun: Fig. 10; [0130], FIG. 10 illustrates a directed graph 1000 used in path planning, e.g., by the planning module 404 (FIG. 4), in accordance with one or more embodiments. In general, a directed graph 1000 like the one shown in FIG. 10 is used to determine a path between any start point 1002 and end point 1004. In real-world terms, the distance separating the start point 1002 and end point 1004 may be relatively large (e.g., in two different metropolitan areas) or may be relatively small ( e.g., two intersections abutting a city block or two lanes of a multi-lane road); [0131], In an embodiment, the directed graph 1000 has nodes l006a-d representing different locations between the start point 1002 and the end point 1004 that could be occupied by an AV 100. In some examples, e.g., when the start point 1002 and end point 1004 represent different metropolitan areas, the nodes l006a-d represent segments of roads. In some examples, e.g., when the start point 1002 and the end point 1004 represent different locations on the same road, the nodes l006a-d represent different positions on that road. In this way, the directed graph 1000 includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point 1002 and the end point 1004 are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV 100; [0132], The nodes l006a-d are distinct from objects l008a-b which cannot overlap with a node. In an embodiment, when granularity is low, the objects l008a-b represent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects l008a-b represent physical objects in the field of view of the AV 100, e.g., other automobiles, pedestrians, or other entities with which the AV 100 cannot share physical space. In an embodiment, some or all of the objects l008a-b are static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car); [0133], The nodes l006a-d are connected by edges 1010ac. If two nodes l006a-b are connected by an edge 1010a, it is possible for an AV 100 to travel between one node 1006a and the other node 1006b, e.g., without having to travel to an intermediate node before arriving at the other node 1006b. (When we refer to an AV 100 traveling between nodes, we mean that the AV 100 travels between the two physical positions represented by the respective nodes.) The edges 1010a-c are often bidirectional, in the sense that an AV 100 travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges 1010a -c are unidirectional, in the sense that an AV 100 can travel from a first node to a second node, however the AV 100 cannot travel from the second node to the first node. Edges 1010a-c are unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints; [0134] In an embodiment, the planning module 404 uses the directed graph 1000 to identify a path 1012 made up of nodes and edges between the start point 1002 and end point 1004. [0135], An edge 1010a-c has an associated cost 1014a-b. The cost 1014a-b is a value that represents the resources that will be expended if the AV 100 chooses that edge. A typical resource is time. For example, if one edge 1010a represents a physical distance that is twice that as another edge 1010b, then the associated cost 1014a of the first edge 1010a may be twice the associated cost 1014b of the second edge 1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges 1010a-b may represent the same physical distance, but one edge 1010a may require more fuel than another edge 1010b, e.g., because of road conditions, expected weather, etc.; [0136], When the planning module 404 identifies a path 1012 between the start point 1002 and end point 1004, the planning module 404 typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together).
Regarding claim 18, Bin-Nun in view of Yaghoubi in view of Maseedu:
transmit the log in real time (Bin-Nun: [0097], Computing devices 146 located on the AV 100 algorithmically generate control actions based on both realtime sensor data and prior information, allowing the AV system 120 to execute its autonomous driving capabilities; [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects; [0094], The communication interfaces 140 transmit data collected from sensors 121 or other data related to the operation of AV 100 to the remotely located database 134. In an embodiment, communication interfaces 140 transmit information that relates to teleoperations to the AV 100. In an embodiment, the AV 100 communicates with other remote ( e.g., "cloud") servers 136).
Regarding claim 19, Bin-Nun in view of Yaghoubi in view of Maseedu:
transmit a graph of the trajectory (Bin-Nun: Fig. 10; [0097], Computing devices 146 located on the AV 100 algorithmically generate control actions based on both realtime sensor data and prior information, allowing the AV system 120 to execute its autonomous driving capabilities; [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects; [0094], The communication interfaces 140 transmit data collected from sensors 121 or other data related to the operation of AV 100 to the remotely located database 134. In an embodiment, communication interfaces 140 transmit information that relates to teleoperations to the AV 100. In an embodiment, the AV 100 communicates with other remote ( e.g., "cloud") servers 136).
Regarding claim 20, Bin-Nun in view of Yaghoubi in view of Maseedu:
generate the log by (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects):
generating a plurality of violation sets (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects);
and combining the plurality of violation sets into the log (Bin-Nun: [0004], The one or more processors determine a first risk level of the one or more violations based on a stored distribution of events of the operation of the vehicle with respect to the one or more objects. Responsive to the first risk level being greater than a threshold risk level, the one or more processors generate a trajectory for the vehicle. The trajectory has a second risk level lower than the threshold risk level. The second risk level is determined with respect to the one or more objects. The one or more processors operate the vehicle based on the trajectory to avoid a collision of the vehicle and the one or more objects).
Documents Considered but Not Relied Upon
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure.
Shah (US 11780466 B1) discloses a vehicle which may include an active ride comfort tuning system that reactively and/or proactively alters a parameter of a system of the autonomous vehicle to mitigate or avoid interruptions to ride smoothness. An indication that a ride smoothness interruption occurred at a vehicle may be generated at the vehicle and/or at a remote computing device. The remote computing device may determine an altered parameter for controlling how the vehicle operates and a ruleset for when the vehicle should implement the altered parameter in place of a nominal parameter. Bagnell et al. (US 11787439 B1) discloses methods for multistage autonomous vehicle motion planning include obtaining sensor data descriptive of an environment of the autonomous vehicle; identifying one or more objects in the environment based on the sensor data; generating a plurality of candidate strategies, wherein each candidate strategy of the plurality of candidate strategies comprises a set of discrete decisions respecting the one or more objects, wherein generating the plurality of candidate strategies includes: determining that at least two strategies satisfy an equivalence criterion, such that the plurality of candidate strategies include at least one candidate strategy corresponding to an equivalence class representative of a plurality of different strategies that are based on different discrete decisions; determining candidate trajectories respectively for the plurality of candidate strategies; and initiating control of the autonomous vehicle based on a selected candidate trajectory. Ward (US 11840234 B1) discloses a system and method that can control a merge of an autonomous vehicle when other vehicles are present on the road. In one example, the method may include iteratively estimating a series of values associated with one or more vehicles in an adjacent lane with respect to an ego vehicle, identifying a trend associated with the one or more vehicles from the iteratively estimated series of values, determining merge intentions of the one or more vehicles with respect to the ego vehicle based on the identified trend over time, verifying the merge intentions against a simulated change in the trend, selecting a merge position of the ego vehicle with respect to the one or more vehicles within the lane based on the verified merge intentions, and executing an instruction to cause the ego vehicle to perform a merge operation based on the selected merge position. Hu et al. (US 11873004 B2) discloses methods and systems for generating a channel for use as a spatio-temporal constraint for motion planning for an autonomous vehicle. The method generates a triangulation mesh for a space in an environment. The triangulation mesh includes a plurality of nodes, each represents a geographic location in the space. Some of the nodes correspond to dynamic objects. Based on the triangulation mesh, a candidate channel extending from a starting location to a target location of the autonomous vehicle is generated. Further, the method predicts a time and location of a future triangulation mesh topology event caused by at least one of the nodes that will impact the candidate channel. A valid channel segment for the channel is selected, which extends from the starting location to a channel segment end location preceding the predicted location of the future triangulation mesh topology event. The channel improves the validity of motion planning for a longer time period. Walker et al. (US 20230410567 A1) discloses systems and methods for assessing the performance of an automated autonomous driving evaluator are disclosed herein. One embodiment receives a driving log including at least one of raw vehicle sensor data and information derived from the raw vehicle sensor data correlated with a time index; receives ground-truth data associated with the driving log, wherein the ground-truth data includes at least one of human-initiated disengagements of an autonomous driving system and human-entered annotations indicating mistakes made by the autonomous driving system; analyzes the driving log using an automated autonomous driving evaluator to generate a report; automatically compares the report with the ground-truth data to generate a performance assessment for the automated autonomous driving evaluator; and provides the performance assessment to a development process in which the automated autonomous driving evaluator is modified based, at least in part, on the performance assessment to improve the performance of the automated autonomous driving evaluator.
Conclusion
THIS ACTION IS MADE FINAL. 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 IZCALLI ANDRE RIOS-AGUIRRE whose telephone number is (571)272-0790. The examiner can normally be reached Monday through Friday 8:30 - 17:00 EST.
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, Scott A. Browne can be reached at (571) 270-0151. 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.
/I.A.R./ Examiner, Art Unit 3666
/SCOTT A BROWNE/ Supervisory Patent Examiner, Art Unit 3666
Prosecution Insights