Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim(s) 1 – 22 are pending for examination.
This Action is made NON-FINAL.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claim(s) 3 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 3 recites the limitation " the operational metric" in line 3. There is insufficient antecedent basis for this limitation in the claim. A plurality of operational metrics have been recited thus its unclear which single operational metric of the plurality of operational metrics is being referenced.
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/process/file/efs/guidance/eTD-info-I.jsp.
Claim(s) 1-2, 4-6, and 12-22 are rejected on the ground of nonstatutory double patenting as being unpatentable over claim(s) 1, 3, 9-15, and 17-18 of patent US 12187321 B2.
Table has been created below to compare claims of the instant application and claims of the patent US 12187321 B2 side by side.
Instant Application 18/952546
Patent US 12187321 B2
1. A method comprising: receiving, using one or more processors of a vehicle, one or more operating constraints for operating the vehicle, wherein each operating constraint of the one or more operating constraints is defined by a respective linear temporal logic expression; determining, using the one or more processors, one or more motion segments for operating the vehicle, wherein motion segment of the one or more motion segments connects two different spatiotemporal locations; determining, using the one or more processors, values of the one or more linear temporal logic expressions for a sequence of states of the vehicle based on a temporal modal operator; assigning, using the one or more processors, operational metrics to the one or more motion segments based on the values of the one or more linear temporal logic expressions; selecting, using the one or more processors, a motion segment of the one or more motion segments, such that the selected motion segment has an assigned operational metric below a threshold value; and causing, using a control module of the vehicle, the vehicle to operate in accordance with the selected motion segment.
1. A method comprising:
storing, using one or more processors of a vehicle, a Kripke structure representing a motion segment for operating the vehicle, wherein the motion segment comprises a plurality of spatiotemporal locations;
for each spatiotemporal location of the plurality of spatiotemporal locations: evaluating, using the one or more processors, a linear temporal logic expression based on the Kripke structure, wherein the linear temporal logic expression defines an operating constraint for operating the vehicle in accordance with the motion segment;
responsive to a value of the linear temporal logic expression changing at the spatiotemporal location, inserting, using the one or more processors, a location marker within the Kripke structure at the spatiotemporal location to divide the motion segment into two different motion segments;
assigning, using the one or more processors, an operational metric to each motion segment of the two different motion segments based on the location marker;
determining, using the one or more processors, a trajectory for operating the vehicle based on the operational metric; and
causing, using a control module of the vehicle, the vehicle to operate in accordance with the determined trajectory.
10. The method of claim 1, wherein evaluating the linear temporal logic expression comprises determining values of the linear temporal logic expression for a sequence of states of the vehicle based on a temporal modal operator.
2. The method of claim 1, wherein the assigning of the operational metrics to the one or more motion segments comprises determining ranks of the one or more operating constraints.
12. The method of claim 1, wherein assigning of the operational metric comprises determining a rank of the operating constraint.
13. The method of claim 12, wherein the operating constraint is one of a ranked plurality of operating constraints.
4. The method of claim 1, further comprising: dividing a motion segment of the one or more motion segments into two different motion segments at a spatiotemporal location.
1. A method comprising:
storing, using one or more processors of a vehicle, a Kripke structure representing a motion segment for operating the vehicle, wherein the motion segment comprises a plurality of spatiotemporal locations;
for each spatiotemporal location of the plurality of spatiotemporal locations: evaluating, using the one or more processors, a linear temporal logic expression based on the Kripke structure, wherein the linear temporal logic expression defines an operating constraint for operating the vehicle in accordance with the motion segment;
responsive to a value of the linear temporal logic expression changing at the spatiotemporal location, inserting, using the one or more processors, a location marker within the Kripke structure at the spatiotemporal location to divide the motion segment into two different motion segments;
assigning, using the one or more processors, an operational metric to each motion segment of the two different motion segments based on the location marker;
determining, using the one or more processors, a trajectory for operating the vehicle based on the operational metric; and
causing, using a control module of the vehicle, the vehicle to operate in accordance with the determined trajectory.
5. The method of claim 4, wherein the dividing of the motion segment is performed responsive to a value of a linear temporal logic expression changing at the spatiotemporal location.
1. A method comprising:
storing, using one or more processors of a vehicle, a Kripke structure representing a motion segment for operating the vehicle, wherein the motion segment comprises a plurality of spatiotemporal locations;
for each spatiotemporal location of the plurality of spatiotemporal locations: evaluating, using the one or more processors, a linear temporal logic expression based on the Kripke structure, wherein the linear temporal logic expression defines an operating constraint for operating the vehicle in accordance with the motion segment;
responsive to a value of the linear temporal logic expression changing at the spatiotemporal location, inserting, using the one or more processors, a location marker within the Kripke structure at the spatiotemporal location to divide the motion segment into two different motion segments;
assigning, using the one or more processors, an operational metric to each motion segment of the two different motion segments based on the location marker;
determining, using the one or more processors, a trajectory for operating the vehicle based on the operational metric; and
causing, using a control module of the vehicle, the vehicle to operate in accordance with the determined trajectory.
6. The method of claim 1, wherein each linear temporal logic expression includes one or more linear temporal logic propositions.
3. The method of claim 1, wherein the linear temporal logic expression comprises one or more linear temporal logic propositions.
12. The method of claim 1, wherein the determining of the values of the one or more linear temporal logic expressions includes determining whether a value of a linear temporal logic expression is true or false.
9. The method of claim 8, wherein determining whether the operating of the vehicle in accordance with the motion segment violates the operating constraint comprises: determining that the value of the linear temporal logic expression is false, and responsive to determining that the value of the linear temporal logic expression is false, determining that the operating of the vehicle violates the operating constraint.
13. The method of claim 1, wherein the causing the vehicle to be operated in accordance with the selected motion segment violates an operating constraint of the one or more operating constraints.
9. The method of claim 8, wherein determining whether the operating of the vehicle in accordance with the motion segment violates the operating constraint comprises: determining that the value of the linear temporal logic expression is false, and responsive to determining that the value of the linear temporal logic expression is false, determining that the operating of the vehicle violates the operating constraint.
14. The method claim 1, wherein causing the vehicle to be operated in accordance with the selected motion segment violates the operating constraint, responsive to a value of a linear temporal logic expression defining the operating constraint being false.
9. The method of claim 8, wherein determining whether the operating of the vehicle in accordance with the motion segment violates the operating constraint comprises: determining that the value of the linear temporal logic expression is false, and responsive to determining that the value of the linear temporal logic expression is false, determining that the operating of the vehicle violates the operating constraint.
15. The method of claim 1, further comprising generating a Kripke structure.
1. A method comprising:
storing, using one or more processors of a vehicle, a Kripke structure representing a motion segment for operating the vehicle, wherein the motion segment comprises a plurality of spatiotemporal locations;….
16. The method of claim 15, wherein a first vertex of the Kripke structure corresponds to a first spatiotemporal location of the two different spatiotemporal locations of the vehicle.
14. The method of claim 1, further comprising generating the Kripke structure, wherein each vertex of a plurality of vertices of the Kripke structure corresponds to a respective spatiotemporal location of the plurality of spatiotemporal locations.
17. The method of claim 16, wherein a second vertex of the Kripke structure corresponds to a second spatiotemporal location of the two different spatiotemporal locations.
14. The method of claim 1, further comprising generating the Kripke structure, wherein each vertex of a plurality of vertices of the Kripke structure corresponds to a respective spatiotemporal location of the plurality of spatiotemporal locations.
18. The method of lc aim 17, wherein an edge of the Kripke structure connecting the first vertex and the second vertex corresponds to a motion segment for operating the vehicle from the first spatiotemporal location to the second spatiotemporal location.
15. The method of claim 14, wherein an edge of the Kripke structure connecting a first vertex and a second vertex corresponds to the motion segment for operating the vehicle from a first spatiotemporal location to a second spatiotemporal location.
19. The method of claim 15, wherein the Kripke structure comprises multiple vertices.
1. A method comprising:
storing, using one or more processors of a vehicle, a Kripke structure representing a motion segment for operating the vehicle, wherein the motion segment comprises a plurality of spatiotemporal locations;
for each spatiotemporal location of the plurality of spatiotemporal locations: evaluating, using the one or more processors, a linear temporal logic expression based on the Kripke structure, wherein the linear temporal logic expression defines an operating constraint for operating the vehicle in accordance with the motion segment;…
20. The method of claim 14, wherein the determining of the values of the one or more linear temporal logic expressions includes evaluating, at each vertex of the multiple vertices, the one or more linear temporal logic expressions.
1. A method comprising:
storing, using one or more processors of a vehicle, a Kripke structure representing a motion segment for operating the vehicle, wherein the motion segment comprises a plurality of spatiotemporal locations;
for each spatiotemporal location of the plurality of spatiotemporal locations: evaluating, using the one or more processors, a linear temporal logic expression based on the Kripke structure, wherein the linear temporal logic expression defines an operating constraint for operating the vehicle in accordance with the motion segment;…
21. A vehicle comprising: one or more computer processors; and one or more non-transitory storage media storing instructions which, when executed by the one or more computer processors, cause the one or more computer processors to perform operations comprising: receiving one or more operating constraints for operating the vehicle, wherein each operating constraint of the one or more operating constraints is defined by a respective linear temporal logic expression; determining one or more motion segments for operating the vehicle, wherein motion segment of the one or more motion segments connects two different spatiotemporal locations; determining values of the one or more linear temporal logic expressions for a sequence of states of the vehicle based on a temporal modal operator; assigning operational metrics to the one or more motion segments based on the values of the one or more linear temporal logic expressions; selecting a motion segment of the one or more motion segments, such that the selected motion segment has an assigned operational metric below a threshold value; and causing, using a control module of the vehicle, the vehicle to operate in accordance with the selected motion segment.
1. A method comprising:
storing, using one or more processors of a vehicle, a Kripke structure representing a motion segment for operating the vehicle, wherein the motion segment comprises a plurality of spatiotemporal locations;
for each spatiotemporal location of the plurality of spatiotemporal locations: evaluating, using the one or more processors, a linear temporal logic expression based on the Kripke structure, wherein the linear temporal logic expression defines an operating constraint for operating the vehicle in accordance with the motion segment;
responsive to a value of the linear temporal logic expression changing at the spatiotemporal location, inserting, using the one or more processors, a location marker within the Kripke structure at the spatiotemporal location to divide the motion segment into two different motion segments;
assigning, using the one or more processors, an operational metric to each motion segment of the two different motion segments based on the location marker;
determining, using the one or more processors, a trajectory for operating the vehicle based on the operational metric; and
causing, using a control module of the vehicle, the vehicle to operate in accordance with the determined trajectory.
10. The method of claim 1, wherein evaluating the linear temporal logic expression comprises determining values of the linear temporal logic expression for a sequence of states of the vehicle based on a temporal modal operator.
22. One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause the one or more computing devices to perform operations comprising: receiving one or more operating constraints for operating a vehicle, wherein each operating constraint of the one or more operating constraints is defined by a respective linear temporal logic expression; determining one or more motion segments for operating the vehicle, wherein motion segment of the one or more motion segments connects two different spatiotemporal locations; determining values of the one or more linear temporal logic expressions for a sequence of states of the vehicle based on a temporal modal operator; assigning operational metrics to the one or more motion segments based on the values of the one or more linear temporal logic expressions; selecting a motion segment of the one or more motion segments, such that the selected motion segment has an assigned operational metric below a threshold value; and causing, using a control module of the vehicle, the vehicle to operate in accordance with the selected motion segment.
1. A method comprising:
storing, using one or more processors of a vehicle, a Kripke structure representing a motion segment for operating the vehicle, wherein the motion segment comprises a plurality of spatiotemporal locations;
for each spatiotemporal location of the plurality of spatiotemporal locations: evaluating, using the one or more processors, a linear temporal logic expression based on the Kripke structure, wherein the linear temporal logic expression defines an operating constraint for operating the vehicle in accordance with the motion segment;
responsive to a value of the linear temporal logic expression changing at the spatiotemporal location, inserting, using the one or more processors, a location marker within the Kripke structure at the spatiotemporal location to divide the motion segment into two different motion segments;
assigning, using the one or more processors, an operational metric to each motion segment of the two different motion segments based on the location marker;
determining, using the one or more processors, a trajectory for operating the vehicle based on the operational metric; and
causing, using a control module of the vehicle, the vehicle to operate in accordance with the determined trajectory.
10. The method of claim 1, wherein evaluating the linear temporal logic expression comprises determining values of the linear temporal logic expression for a sequence of states of the vehicle based on a temporal modal operator.
Although the claims at issue are not identical, they are not patentably distinct from each other because both inventions are directed to AUTONOMOUS VEHICLE OPERATION USING LINEAR TEMPORAL LOGIC. Minor differences can be seen and noted in the table above, however it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to use the method of patent US 12187321 B2 to produce the of the instant application.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claim(s) 1-3, 6-8, 12-14, and 21-22 are rejected under 35 U.S.C. 102(a)(2) as being anticipated by Kobilarov et al. (US 20190101919 A1; hereinafter known as Kobilarov).
Regarding Claim 1, Kobilarov teaches A method comprising: receiving, using one or more processors of a vehicle, one or more operating constraints for operating the vehicle, wherein each operating constraint of the one or more operating constraints is defined by a respective linear temporal logic expression;
{abstract “In general, determining a route can include utilizing a search algorithm such as Monte Carlo Tree Search (MCTS) to search for possible trajectories, while using temporal logic formulas, such as Linear Temporal Logic (LTL), to validate or reject the possible trajectories. Trajectories can be selected based on various costs and constraints optimized for performance. Determining a trajectory can include determining a current state of the autonomous vehicle, which can include determining static and dynamic symbols in an environment.” and para [0082] “LTL can be used to concisely and precisely specify permitted and prohibited system behaviors in terms of the corresponding words.”
}
determining, using the one or more processors, one or more motion segments for operating the vehicle, wherein motion segment of the one or more motion segments connects two different spatiotemporal locations;
{para [0020] “As candidate routes and trajectories are generated for the autonomous vehicles, the routes and trajectories can be evaluated using the temporal logic formulas to determine if the trajectories satisfy the temporal logic formulas, in which case, trajectories can be rejected, or evaluated with respect to other costs and constraints to select the highest performing trajectory.”
Where a route includes at least a start and end location, so at least 2 spatiotemporal locations
}
determining, using the one or more processors, values of the one or more linear temporal logic expressions for a sequence of states of the vehicle based on a temporal modal operator;
{Para [0020] “As symbols, features, and predicates are added to a context indicating a state of an environment at an instant in time, processing can include determining temporal logic formulas, such as Linear Temporal Logic (LTL) formulas or Signal Temporal Logic (STL) formulas, that can be evaluated based on the present symbols, features, and/or predicates. As discussed throughout this disclosure, temporal logic can be used to model or encode formulas about the future of paths or objects, and whether conditions will eventually be true, whether a condition will be true until another fact becomes true, etc. In some instances, the temporal logic formulas can include statements about the world that reflect proper driving behavior for an autonomous vehicle, for example. As candidate routes and trajectories are generated for the autonomous vehicles, the routes and trajectories can be evaluated using the temporal logic formulas to determine if the trajectories satisfy the temporal logic formulas, in which case, trajectories can be rejected, or evaluated with respect to other costs and constraints to select the highest performing trajectory.”
}
assigning, using the one or more processors, operational metrics to the one or more motion segments based on the values of the one or more linear temporal logic expressions;
{ Fig. 7 label 718 where a trajectory is being generated and then selected based on the LTL formula, e.g. linear temporal logic formula. The trajectory includes operational metrics.
Para [0023] “If multiple trajectories are determined not to violate the LTL formula(s), a trajectory with a lowest cost (or a highest performance, comfort, etc.) can be selected. For example, for various operations of the autonomous vehicle, or for various possible trajectories, a cost function can penalize acceleration, jerk, lateral acceleration, yaw, steering angle, steering angle rate, etc.”
}
selecting, using the one or more processors, a motion segment of the one or more motion segments, such that the selected motion segment has an assigned operational metric below a threshold value; and
{Para [0122] “Accordingly, various trajectories can be generated and checked against the LTL formula 324 and/or against one or more automaton corresponding to the LTL formula 324 to verify a correctness of individual trajectories. In some instances, if different trajectories do not violate the LTL formula 324 (e.g., more than one trajectory satisfies the LTL formula 324), a trajectory can be selected based on costs (e.g., speed, comfort, performance, etc.). For example, costs can be determined and associated with specific actions associated with a trajectory. In one example, a first trajectory may satisfy the LTL formula associated with a task and may have a low cost relative to a second trajectory that also satisfies the LTL formula but has a higher cost to complete the trajectory. The decision module 106 may select the first trajectory to guide the autonomous vehicle 304, as the lower cost of the first trajectory may represent a faster travel, more comfortable ride (e.g., comfortable accelerations and decelerations), or may represent reduced wear and tear on the autonomous vehicle 304, for example.”
}
causing, using a control module of the vehicle, the vehicle to operate in accordance with the selected motion segment.
{Para [0091] “As a particular example, an LTL formula can be evaluated as true once an autonomous vehicle has determined that it has approached an intersection, detected another vehicle at the intersection, and waited until there was no longer another vehicle in the intersection.”
Where approaching an intersection and waiting at the intersect is implied to be an operating constraint and its being evaluated as true using the LTL formula.
}
Regarding claim 2, Kobilarov teaches The method of claim 1, wherein the assigning of the operational metrics to the one or more motion segments comprises determining ranks of the one or more operating constraints.
{Para [0166] “At operation 808, the process can include selecting a trajectory based at least in part on one or more costs. In some instances, the operation can include verifying that any candidate trajectory does not violate an LTL formula. Further, in some instances, a violation of an LTL formula many not result in discarding the candidate trajectory, but can be considered as a penalty, and can be considered when choosing a trajectory. In some instances, costs can depend on comfort aspects (acceleration, braking levels, etc.), and in some instances, the cost can be depend on safety aspects, in which case, a cost can be higher or lower depending on the importance of the factor under consideration.”
}
Regarding claim 3, Kobilarov teaches The method of claim 1, wherein the assigning of the operational metrics further comprises denoting a rank of an operating constraint defined by a linear temporal logic expression as the operational metric for the motion segment.
{ Para [0166] “At operation 808, the process can include selecting a trajectory based at least in part on one or more costs. In some instances, the operation can include verifying that any candidate trajectory does not violate an LTL formula. Further, in some instances, a violation of an LTL formula many not result in discarding the candidate trajectory, but can be considered as a penalty, and can be considered when choosing a trajectory. In some instances, costs can depend on comfort aspects (acceleration, braking levels, etc.), and in some instances, the cost can be depend on safety aspects, in which case, a cost can be higher or lower depending on the importance of the factor under consideration.”
}
Regarding claim 6, Kobilarov teaches The method of claim 1, wherein each linear temporal logic expression includes one or more linear temporal logic propositions.
{ Para [0080] “Additional details of the TL library module 222, and temporal logic in general, are discussed below. In one or more examples, properties of plans can be defined in terms of a set of atomic statements (also referred to as atomic propositions, or predicates). An atomic proposition is a statement about the world that is either True or False. In such an example, a finite set of atomic propositions, AP, can be used to indicate properties such as occupancy of a spatial region.”
Para [0082] “LTL can be used to concisely and precisely specify permitted and prohibited system behaviors in terms of the corresponding words. Formulas in LTL are constructed from p∈AP”
}
Regarding claim 7, Kobilarov teaches The method of claim 6, wherein the determining of the values of the one or more linear temporal logic expressions comprises evaluating each linear temporal logic proposition of the one or more linear temporal logic propositions.
{Para [0068] “The TL formulas 214 can be evaluated based on the present symbols, features, and/or predicates. As discussed throughout this disclosure, temporal logic (TL) can be used to model or encode formulas about the future of paths or objects, and whether conditions will eventually be true, whether a condition will be true until another fact becomes true, etc. In some instances, the temporal logic may include signal temporal logic (STL), interval temporal logic (ITL), computational tree logic (CTL), property specification language (PSL), Hennessy-Milner logic (HML), etc. In some instances, in addition to or instead of TL, the systems described herein can use planning domain definition language (PDDL) and/or STRIPS (Stanford Research Institute Problem Solver). In some instances, references to a particular implementation of temporal logic is not intended to limit the example to the particular implementation. In some instances, the TL formulas 214 can include statements about the world that reflect proper driving behavior (e.g., rules of the road, right-of-way rules, rules against tailgating, etc.) for an autonomous vehicle, for example. As candidate routes and trajectories are generated for the autonomous vehicles, the routes and trajectories can be evaluated using the TL formulas 214 to determine if the trajectories satisfy the TL formulas 214, in which case, trajectories can be rejected, or evaluated with respect to other costs and constraints to select the highest performing trajectory. In some instances, the temporal logic formulas can be used to automatically generate a state machine that can be used by components of the computer systems 102 and/or the vehicle control device 114 for tasks in addition to generating and/or rejecting candidate trajectories.”
}
Regarding claim 8, Kobilarov teaches The method of claim 7, wherein the determining of the values of the one or more linear temporal logic expressions further comprises aggregating the evaluated each linear temporal logic proposition of the one or more linear temporal logic propositions.
{Para [0069] “In some instances, a TL formula 214 can be evaluated (e.g., by a processor associated with the decision module 106) to determine if a formula is violated or not (e.g., as a Boolean result). By way of another example, a TL formula 214 can be evaluated (e.g., utilizing STL) to provide an indication of an extent to which a condition is satisfied, while determining a cost for violating a condition (e.g., assigning a penalty to a state as a function of how far an autonomous vehicle stops beyond a stop line, rather than or in addition to assigning a Boolean value to the condition). Additional aspects of the TL formula 214 are discussed throughout this disclosure.”
Para [0122] “Accordingly, various trajectories can be generated and checked against the LTL formula 324 and/or against one or more automaton corresponding to the LTL formula 324 to verify a correctness of individual trajectories. In some instances, if different trajectories do not violate the LTL formula 324 (e.g., more than one trajectory satisfies the LTL formula 324), a trajectory can be selected based on costs (e.g., speed, comfort, performance, etc.). For example, costs can be determined and associated with specific actions associated with a trajectory. In one example, a first trajectory may satisfy the LTL formula associated with a task and may have a low cost relative to a second trajectory that also satisfies the LTL formula but has a higher cost to complete the trajectory. The decision module 106 may select the first trajectory to guide the autonomous vehicle 304, as the lower cost of the first trajectory may represent a faster travel, more comfortable ride (e.g., comfortable accelerations and decelerations), or may represent reduced wear and tear on the autonomous vehicle 304, for example.”
}
Regarding claim 12, Kobilarov teaches The method of claim 1, wherein the determining of the values of the one or more linear temporal logic expressions includes determining whether a value of a linear temporal logic expression is true or false.
{Para [0021] “In some instances, an LTL formula can be evaluated to determine if the formula is violated or not (e.g., as a Boolean result). By way of another example, a temporal logic formula (such as STL) can be evaluated to provide an indication of how well a condition is satisfied while determining a cost for violating a condition (e.g., assigning a penalty to a state as a function of how far an autonomous vehicle stops beyond a stop line, in addition to or instead of assigning a Boolean value to the condition). Additional aspects of the temporal logic formulas are discussed throughout this disclosure.”
}
Regarding claim 13, Kobilarov teaches The method of claim 1, wherein the causing the vehicle to be operated in accordance with the selected motion segment violates an operating constraint of the one or more operating constraints.
{Para [0156] “At operation 706, the process can include determining one or more predicates based on the features. As discussed herein, in some instances, predicates can include logical formulas based on symbols, features, or other predicates that evaluate as True or False based on input values. In one example, a predicate can be evaluated to determine whether or not an autonomous vehicle has stopped in a stop region. In another example, a predicate can provide an indication of how well the predicate is satisfied by the conditions. For example, for a predicate that determines whether an autonomous vehicle stops in a stop region, in a scenario where the autonomous vehicle stops 1 cm beyond the stop region, the Boolean evaluation of the predicate would be False, although a predicate that returns an indication of the degree of satisfaction can indicate a location where the autonomous vehicle stopped or a degree of the predicate violation, and/or can associate a penalty with that action. In some instances, a penalty for stopping 1 cm outside a stop region can be a minor penalty, but a penalty for stopping 1 meter beyond the stop region can be a maj or penalty.”
Para [0161] “At operation 718, the process can include selecting a trajectory based at least in part on the trajectory satisfying one or more LTL formulas and one or more cost functions. For example, if multiple trajectories satisfy (e.g., do not violate) the LTL formula, the operation 718 can select a trajectory based on a cost or performance associated with the trajectory. In some instances, costs can be based at least in part on efficiency, comfort, performance, etc. of the autonomous vehicle. Thus, the process 700 can output a trajectory that has a highest performance and lowest cost to accomplish a goal associated with an autonomous vehicle.”
Where even if a constraint is violated if that constraint is low cost the trajectory can still be chosen.
}
Regarding claim 14, Kobilarov teaches The method claim 1, wherein causing the vehicle to be operated in accordance with the selected motion segment violates the operating constraint, responsive to a value of a linear temporal logic expression defining the operating constraint being false.
{Para [0156] “At operation 706, the process can include determining one or more predicates based on the features. As discussed herein, in some instances, predicates can include logical formulas based on symbols, features, or other predicates that evaluate as True or False based on input values. In one example, a predicate can be evaluated to determine whether or not an autonomous vehicle has stopped in a stop region. In another example, a predicate can provide an indication of how well the predicate is satisfied by the conditions. For example, for a predicate that determines whether an autonomous vehicle stops in a stop region, in a scenario where the autonomous vehicle stops 1 cm beyond the stop region, the Boolean evaluation of the predicate would be False, although a predicate that returns an indication of the degree of satisfaction can indicate a location where the autonomous vehicle stopped or a degree of the predicate violation, and/or can associate a penalty with that action. In some instances, a penalty for stopping 1 cm outside a stop region can be a minor penalty, but a penalty for stopping 1 meter beyond the stop region can be a maj or penalty.”
Para [0161] “At operation 718, the process can include selecting a trajectory based at least in part on the trajectory satisfying one or more LTL formulas and one or more cost functions. For example, if multiple trajectories satisfy (e.g., do not violate) the LTL formula, the operation 718 can select a trajectory based on a cost or performance associated with the trajectory. In some instances, costs can be based at least in part on efficiency, comfort, performance, etc. of the autonomous vehicle. Thus, the process 700 can output a trajectory that has a highest performance and lowest cost to accomplish a goal associated with an autonomous vehicle.”
Where even if a constraint is violated if that constraint is low cost the trajectory can still be chosen.
}
Regarding claim 21, it recites A vehicle having limitations similar to those of claim 1 and therefore is rejected on the same basis.
Additionally Kobilarov teaches A vehicle comprising: one or more computer processors; and one or more non-transitory storage media storing instructions which, when executed by the one or more computer processors, cause the one or more computer processors to perform operations comprising
{Fig. 1 and Para [0152] “FIGS. 7 and 8 illustrate example processes in accordance with embodiments of the disclosure. These processes are illustrated as logical flow graphs, each operation of which represents a sequence of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the operations represent computer-executable instructions stored on one or more computer-readable storage media that, when executed by one or more processors, perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that perform particular functions or implement particular abstract data types. The order in which the operations are described is not intended to be construed as a limitation, and any number of the described operations can be combined in any order and/or in parallel to implement the processes.”
}
Regarding claim 22, it recites A vehicle having limitations similar to those of claim 1 and therefore is rejected on the same basis.
Additionally Kobilarov teaches One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause the one or more computing devices to perform operations comprising:
{Para [0152] “FIGS. 7 and 8 illustrate example processes in accordance with embodiments of the disclosure. These processes are illustrated as logical flow graphs, each operation of which represents a sequence of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the operations represent computer-executable instructions stored on one or more computer-readable storage media that, when executed by one or more processors, perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that perform particular functions or implement particular abstract data types. The order in which the operations are described is not intended to be construed as a limitation, and any number of the described operations can be combined in any order and/or in parallel to implement the processes.”
}
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 4-5, 10, and 15-20 are rejected under 35 U.S.C. 103 as being unpatentable over Kobilarov et al. (US 20190101919 A1; hereinafter known as Kobilarov) in view of During et al. ( US 20180129214 A1 ; hereinafter known as During).
Regarding Claim 4, Kobilarov teaches The method of claim 1
Kobilarov does not teach, further comprising: dividing a motion segment of the one or more motion segments into two different motion segments at a spatiotemporal location.
However, During teaches further comprising: dividing a motion segment of the one or more motion segments into two different motion segments at a spatiotemporal location.
{Para [0034] “By way of example, the intermediate points can be arranged as grid points on a grid particularly between the starting point and the destination. If partial trajectories that each connect adjacent intermediate points are then determined, there are firstly numerous options (for instance, numerous partial trajectories) available for the trajectory that is to be determined and, secondly, numerous partial trajectories exist for every journey on the determined trajectory to be able to quickly replan the determined trajectory on the basis of these partial trajectories.”
}
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kobilarov to incorporate the teachings of During because as discussed in para [0017] of During, the “disclosed embodiments improve the determination of a trajectory or evasive trajectory for a vehicle”
Regarding Claim 5, Kobilarov in view of During teaches The method of claim 4. During Further teaches wherein the dividing of the motion segment is performed responsive to a value of a linear temporal logic expression changing at the spatiotemporal location.
{Para [0039] “Some of the intermediate points or each of the intermediate points may be defined not only by their/its location on the road or on the navigable ground but also by a vehicle orientation. In this case, the vehicle orientation determines the respective orientation of the vehicle that is present when the vehicle moves along a partial trajectory that begins or ends at the respective intermediate point. A partial trajectory can be connected to another partial trajectory only if one partial trajectory ends at the same intermediate point at which the other partial trajectory begins, the intermediate point also being defined by the vehicle orientation. In other words, one partial trajectory can be connected to the other partial trajectory only if the vehicle orientation at the end of one partial trajectory corresponds to the vehicle orientation at the beginning of the other partial trajectory.”
Para [0041] “Besides by the location and the vehicle orientation, an intermediate point can also be defined by a time and/or by a speed. In this case, the time of the intermediate point determines the time at which the vehicle arrives at the intermediate point when the vehicle travels along a partial trajectory ending at the intermediate point, or the time at which the vehicle sets off from the intermediate point when the vehicle travels along a partial trajectory beginning at the intermediate point. In a similar manner, the speed of the intermediate point determines the speed at which the vehicle arrives at the intermediate point when the vehicle travels along a partial trajectory ending at the intermediate point, or the speed at which the vehicle sets off from the intermediate point when the vehicle travels along a partial trajectory beginning at the intermediate point. As in the case of the vehicle orientation, it also holds for the time or the speed that a partial trajectory can be connected to another partial trajectory only if the time or the speed at the end of one partial trajectory corresponds to the time or the speed at the beginning of the other partial trajectory.”
}
Regarding Claim 10, Kobilarov teaches The method of claim 1
Kobilarov does not teach, further comprising: sampling spatiotemporal information obtained from a map of the environment within which the vehicle is located to generate a Kripke structure.
However, During teaches further comprising: sampling spatiotemporal information obtained from a map of the environment within which the vehicle is located to generate a Kripke structure.
{ Para [0019] “Within the context of the present disclosure, a method for automatically determining a trajectory for a vehicle is provided. This involves the trajectory to be determined being used to connect a starting point corresponding to the current position of the vehicle to a destination. The disclosed method comprises the following operations: [0020] Determining multiple intermediate points. [0021] Determining one or more first partial trajectories. In this case, the first partial trajectory connects the starting point to one of the intermediate points if only one first partial trajectory is determined. Alternatively, each of these first partial trajectories connects the starting point to a respective other instance of the intermediate points if multiple first partial trajectories are determined. [0022] Determining multiple second partial trajectories, each of these second partial trajectories connecting the final point to a respective other instance of the intermediate points. [0023] Determining the trajectory by virtue of the first partial trajectory being chosen if there is only a first partial trajectory and by virtue of a first partial trajectory being chosen from the first partial trajectories if there are multiple first partial trajectories and by virtue of a second partial trajectory being chosen from the second partial trajectories. The chosen first and chosen second partial trajectories then form at least one respective part of the determined trajectory. [0024] Actuating a component (e.g., the steering) of the vehicle on the basis of the determined trajectory.”
Para [0068] “n operation at S1, the environment of the vehicle is detected using one or more sensors of the vehicle. In the subsequent operation at S2, the starting point, the destination and intermediate points between the starting point and the destination are automatically determined. In this case, the starting point corresponds to the current position of the vehicle, and the destination is determined on the basis of the detected environment. To determine the intermediate points, a kind of grid can be arranged between the starting point and the destination on the road on which the vehicle travels. The grid points of this grid correspond to the intermediate points to be determined, with predefined points (e.g., at the edges of the road) also being able to be defined as intermediate points.”
Fig. 1 and 2 illustrate this and can be considered a Kripke structure, and map the points between a first and second point which can be considered as representing a motion segment.
}
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kobilarov to incorporate the teachings of During to generate a Kripke structure representing a motion segment because Kobilarov already considers the vehicle state a various points along a motion segment and a Kripke structure is a common way to represent the behavior of a system with various states and state transitions and thus would be obvious to try.
Additionally, It would be obvious to combine Kobilarov with During because the methods of during can help improve the determination of a trajectory or evasive trajectory for a vehicle (During Para [0017]).
Regarding Claim 15, Kobilarov teaches The method of claim 1
Kobilarov does not teach, further comprising generating a Kripke structure.
However, During teaches further comprising generating a Kripke structure.
{ Para [0019] “Within the context of the present disclosure, a method for automatically determining a trajectory for a vehicle is provided. This involves the trajectory to be determined being used to connect a starting point corresponding to the current position of the vehicle to a destination. The disclosed method comprises the following operations: [0020] Determining multiple intermediate points. [0021] Determining one or more first partial trajectories. In this case, the first partial trajectory connects the starting point to one of the intermediate points if only one first partial trajectory is determined. Alternatively, each of these first partial trajectories connects the starting point to a respective other instance of the intermediate points if multiple first partial trajectories are determined. [0022] Determining multiple second partial trajectories, each of these second partial trajectories connecting the final point to a respective other instance of the intermediate points. [0023] Determining the trajectory by virtue of the first partial trajectory being chosen if there is only a first partial trajectory and by virtue of a first partial trajectory being chosen from the first partial trajectories if there are multiple first partial trajectories and by virtue of a second partial trajectory being chosen from the second partial trajectories. The chosen first and chosen second partial trajectories then form at least one respective part of the determined trajectory. [0024] Actuating a component (e.g., the steering) of the vehicle on the basis of the determined trajectory.”
Fig. 1 and 2 illustrate this and can be considered a Kripke structure, and map the points between a first and second point which can be considered as representing a motion segment.
}
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kobilarov to incorporate the teachings of During to generate a Kripke structure representing a motion segment because Kobilarov already considers the vehicle state a various points along a motion segment and a Kripke structure is a common way to represent the behavior of a system with various states and state transitions and thus would be obvious to try.
Additionally, It would be obvious to combine Kobilarov with During because the methods of during can help improve the determination of a trajectory or evasive trajectory for a vehicle (During Para [0017]).
Regarding Claim 16, Kobilarov in view of During teaches The method of claim 15. During Further teaches wherein a first vertex of the Kripke structure corresponds to a first spatiotemporal location of the two different spatiotemporal locations of the vehicle.
{Fig. 1 and Fig. 2 where SP corresponds to a start point which is first spatiotemporal location.
}
Regarding Claim 17, Kobilarov in view of During teaches The method of claim 16. During Further teaches wherein a second vertex of the Kripke structure corresponds to a second spatiotemporal location of the two different spatiotemporal locations.
{Fig. 1 and Fig. 2 where 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, and ZP corresponds with intermediate/destination points which are a second spatiotemporal location.
}
Regarding Claim 18, Kobilarov in view of During teaches The method of claim 17. During Further teaches wherein an edge of the Kripke structure connecting the first vertex and the second vertex corresponds to a motion segment for operating the vehicle from the first spatiotemporal location to the second spatiotemporal location.
{Fig. 1 and Fig. 2 where which shows links, e.g. edges, between the different points of the possible trajectories of the vehicle.
}
Regarding Claim 19, Kobilarov in view of During teaches The method of claim 15. During Further teaches wherein the Kripke structure comprises multiple vertices.
{Fig. 1 and Fig. 2 where 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, and ZP corresponds with intermediate/destination points which are a second spatiotemporal location.
}
Regarding Claim 20, Kobilarov teaches The method of claim 14.
Kobilarov does not teach, wherein the determining of the values of the one or more linear temporal logic expressions includes evaluating, at each vertex of the multiple vertices, the one or more linear temporal logic expressions.
However, During teaches wherein the determining of the values of the one or more linear temporal logic expressions includes evaluating, at each vertex of the multiple vertices, the one or more linear temporal logic expressions.
{ Fig. 1 and Fig. 2 where SP corresponds to a start point which is first spatiotemporal location and where 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, and ZP corresponds with intermediate/destination points which are a second spatiotemporal location. Fig. 3 which shows that logic equations can be evaluated differently at different points based on proprieties at a point for example the presence of a obstacle.
}
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kobilarov to incorporate the teachings of During because as discussed in para [0017] of During, the “disclosed embodiments improve the determination of a trajectory or evasive trajectory for a vehicle”
Claim(s) 9 is rejected under 35 U.S.C. 103 as being unpatentable over Kobilarov et al. (US 20190101919 A1; hereinafter known as Kobilarov) in view of During et al. (US 20180129214 A1; hereinafter known as During) and Blake et al. (US 20210191404 A1; hereinafter known as Blake).
Regarding Claim 9, Kobilarov teaches The method of claim 1
Kobilarov does not teach, randomizing spatiotemporal information obtained from a map of the environment within which the vehicle is located to generate a Kripke structure.
However, During teaches acquiring spatiotemporal information obtained from a map of the environment within which the vehicle is located to generate a Kripke structure.
{Para [0019] “Within the context of the present disclosure, a method for automatically determining a trajectory for a vehicle is provided. This involves the trajectory to be determined being used to connect a starting point corresponding to the current position of the vehicle to a destination. The disclosed method comprises the following operations: [0020] Determining multiple intermediate points. [0021] Determining one or more first partial trajectories. In this case, the first partial trajectory connects the starting point to one of the intermediate points if only one first partial trajectory is determined. Alternatively, each of these first partial trajectories connects the starting point to a respective other instance of the intermediate points if multiple first partial trajectories are determined. [0022] Determining multiple second partial trajectories, each of these second partial trajectories connecting the final point to a respective other instance of the intermediate points. [0023] Determining the trajectory by virtue of the first partial trajectory being chosen if there is only a first partial trajectory and by virtue of a first partial trajectory being chosen from the first partial trajectories if there are multiple first partial trajectories and by virtue of a second partial trajectory being chosen from the second partial trajectories. The chosen first and chosen second partial trajectories then form at least one respective part of the determined trajectory. [0024] Actuating a component (e.g., the steering) of the vehicle on the basis of the determined trajectory.”
Para [0037] “The intermediate points are on a road or on navigable ground that the vehicle is currently on. In this case, one or more of the intermediate points may be on hand on the left-hand or right-hand lateral edge of this navigable ground as seen in the direction of travel of the vehicle.”
Fig. 1 and 2 illustrate this and can be considered a Kripke structure, and map the points between a first and second point which can be considered as representing a motion segment.
}
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kobilarov to incorporate the teachings of During to generate a Kripke structure representing a motion segment because Kobilarov already considers the vehicle state a various points along a motion segment and a Kripke structure is a common way to represent the behavior of a system with various states and state transitions and thus would be obvious to try.
Additionally, It would be obvious to combine Kobilarov with During because the methods of during can help improve the determination of a trajectory or evasive trajectory for a vehicle (During Para [0017]).
Kobilarov in view of during does not teach, randomizing spatiotemporal information obtained from a map
However, Blake teaches randomizing spatiotemporal information obtained from a map
{para [0097] “For example, the paths can be synthesised for each goal using a Rapidly Exploring Random Tree (RRT) model. A space of predicted paths (search space) is defined based on the reference location for each goal and the current location ro of the external vehicle. The search space is then randomly sampled (based on randomized input parameters), in order to determine the set of n paths, and a likelihood of each of those paths. To simulate n paths for each goal, the relevant parameters of the RRT are randomised n times to perform n appropriately based random searches of the search space. In the present disclosure, the probabilistic risk of collision along a given trajectory may be calculated, and used to rank the candidate trajectories by safety. This in turn provides the likelihood of each sampled path on the assumption that the external vehicle is more likely to take safer paths to execute the goal in question.”
}
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kobilarov in view During to incorporate the teachings of Blake because it can improve safety and computational efficiency of path planning (para [0011] “The core problem addressed herein is that of safe and computationally efficient motion planning in an imprecisely known environment.”)
Allowable Subject Matter
Claim 11 objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ALEXANDER MATTA whose telephone number is (571)272-4296. The examiner can normally be reached Mon - Fri 10:00-6:00.
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, James Lee can be reached at (571) 270-5965. 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.
/A.G.M./Examiner, Art Unit 3668
/ABDHESH K JHA/Primary Examiner, Art Unit 3668
Prosecution Insights