Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-2, 5-8, 10, 13-14 and 17-20 are rejected under 35 U.S.C. 103 as being unpatentable over Basich et al. (US 2021/0132606 A1 – hereinafter Connor) and further in view of Connolly (“Harmonic Functions and Collision Probabilites”).
In regards to claim 1, Connor discloses a system comprising:
processing circuitry in communication with storage media, the processing circuitry configured to execute a reinforcement learning system configured to: (Connor para. [0246] teaches processing circuity in communication with storage media to execute instructions.)
perform, by an agent, an action within an environment; (Connor para. [0131] cites “The ACA 5002 can operate in, and plan for/with, multiple levels of autonomous operations (i.e., autonomy levels). …an AV performs a vehicle control action in an autonomy level, the AV (more specifically, the ACA) may receive a feedback signal ( or simply, feedback) in response to the AV's execution of the vehicle control action.” and para. [0139] cites “As mentioned, the DM 5004 can model the environment (i.e., the operational environment) that the ACA 5002 is operating in. For example, the DM 5004 can describe ( e.g., include) transition and/or cost dynamics of the environment with respect to the ACA 5002.”. This teaches an agent (ACA) performing an action (vehicle control action) in within an environment (operational environment).)
obtain one or more measurements from the environment, the one or more measurements resultant of the action performed by the agent; (Connor para. [00127] teaches the reinforcement learning (RL) model supplies a candidate action, and the result of it is determined to update the RL model, wherein it cites “In a RL model, the model may evaluate one or more events or interactions, which can include simulated events, and may generate, or modify, a corresponding model, or a solution thereof, in response to the respective event. Simulated events may include, for example, traversing an intersection,… An example of using a RL model to traverse an intersection includes the RL model indicating a candidate action for traversing the inter section. The autonomous vehicle then traverses the intersection using the candidate action as the vehicle control action for a temporal location. A result of traversing the intersection using the candidate action may be determined to update the RL model based on the result.”. Then in para. [0185 and 0190] teaches using LiDAR, radar and camera information from sensors and vehicle performing an edging action to move forward slightly to make sensors unobstructed to get environmental data, which is a result of the edging action. Para. [0203] teaches detecting at step 6002 detecting a states of environment, para. [0204] teaches selecting a policy and autonomy profile based on the state, then para. [209] teaches using the state, policy and autonomy profile to output an action to be performed and a level of autonomy. Then in figure 6 it teaches the action being performed in the action stage, and para. [0228] teaches the model proceeds back to step 602 to monitoring or sensing the current environment state.)
determine, based on the one or more measurements, a state of a domain model for the environment reached by the agent; and (Conner para. [0185] teaches domain information based on measurements from the sensors wherein it cites “
The domain model of the intersection scenario of FIG. 7 can include abstracted (e.g., symbolic) information that is extracted based on sensor (LiDAR, radar, camera, etc.) information. For example, the domain model can include information such as the location of the vehicle 7004 ( e.g., "approaching stop line of intersection"), other relevant world objects (e.g., "a vehicle on left side" that is a vehicle 7010), road configuration (e.g., "east-west road is thru traffic" meaning that there are no traffic signals, stop signs, yield signs or the like), other relevant information to the scenario ( e.g., "object on left has not moved in a long time," "left-side sensors obstructed," etc.).”. Also para. [0186] teaches changes in sensor data modify the scenario state, para. [0187] teaches the abstract state space and domain space and para[203] teaches the detected world state is a state of the domain model is detected using the vehicle sensors. This teaches detecting the state and changes in state based on sensor measurements.
distribute credit, based at least in part on a reward associated with the state. (Conner para. [0099, 0111, and 0143] teaches distributing credit (reward) based on a reward associated with the states wherein para. [0099] cites “In another example, identifying the vehicle control action from the candidate actions may include implementing a Markov Decision Process (MDP), or a Partially Observable Markov Decision Processes (POMDP), which may describe how respective candidate actions affect subsequent candidate actions, and may include a reward function that outputs a positive or negative reward for respective vehicle control actions.”; para. [0111] cites “[A MDP model may model a distinct vehicle operational scenario using a set of states, a set of actions, a set of state transition probabilities, a reward function, or a combination thereof.”; [0143] cites “For example, in the scenario of crossing an intersection, a good state is a state in which the AV completes crossing the intersection; and a bad state may correspond with the AV colliding with another vehicle or a state in which the AV violated a law. A negative reward can be associated with a bad state and a positive reward can be associated with a good state.”)
However, Connor does not explicitly disclose distributing credit, based at least in part on a reward associated with the state, across an explored state space for the domain model for the environment.
Connolly distributing credit, based at least in part on a reward associated with the state, across an explored state space for the domain model for the environment. (Connolly abstract, page 1 section 1, section 4 pages 7-10 with equations 12-14 discloses that the expected value functions can be reconstructed over the state space using direct relaxation methods. For boundary awards, the expected values at absorbing states z, represent rewards/penalties and are distributed through the harmonic expected value function. It further discloses the relationship between Laplace’s equation and Markov chains an be generalized when a reward or penalty is associated with each transition in the Markov chain using equation 14, which distributes the rewards/penalties within the state space, wherein f(x) is the reward/penalty as a function of state and the Poisson solution ɸ(x) assigns values throughout the modeled space. Section 4 also teaches performing SOR iterations over the entire grid. Thus, it distributes credit (reward) across the explored state space for the domain model.)
It would have been obvious to one of ordinary skill in the art before earliest effective filing date of the claimed invention to modify the teachings of the Connor with that of Connolly in order to allow for distributing credit across an explored state space as both references deal autonomous navigation using Markov Models and reinforcement learning, wherein rewards are assigned to states. It provides the benefit of creating a faster and more efficient model as the values functions obtained by reinforcement learning can be rapidly reconstructed by relaxation as cited by Connolly in the abstract.
In regards to claim 2, Connor in view of Connolly disclose the system of claim 1, wherein the reinforcement learning system comprises an absorbing Markov chain comprising a harmonic function of the Markov chain. (Connolly section 2.2 first paragraph teaches a Markov Chain having an absorbing set divided into obstacle and goal subsets. It defines the probability of absorption in one subset before reaching the other and shows the probability satisfies the weighted mean-value equation (equations 4 & 5). Section 4 page 8 paragraphs 1-3 along with equations 12 and 13 the expected value function for a Markov chain (absorbing chain) is determined by the transition matrix (P) and the expected values at the absorbing states (z). It also states a regular function for Markov chain defined by P is harmonic.)
In regards to claim 5, Connor in view of Connolly disclose the system of claim 1, wherein the reinforcement learning system is configured to implement one or more Markov decision processes (MDPs) represented using a state space, an action space, a transition function, and a reward function. (Connor para. [0019] cites “The autonomous vehicle operational management system may include one or more scenario-specific operational control evaluation modules (SSOCEMs). Each scenario-specific operational control evaluation module may be a model, such as a Partially Observable Markov Decision Process (POMDP) model,…”; para. [0099] cites “In another example, identifying the vehicle control action from the candidate actions may include implementing a Markov Decision Process (MDP), or a Partially Observable Markov Decision Processes (POMDP), which may describe how respective candidate actions affect subsequent candidate actions, and may include a reward function that outputs a positive or negative reward for respective vehicle control actions.”; and para. [0111] cites “A MDP model may model a distinct vehicle operational scenario using a set of states, a set of actions, a set of state transition probabilities, a reward function, or a combination thereof.”. Connor para. [0140] teaches state space, action space, transition function and para. [0099] teaches reward function.)
In regards to claim 6, Connor in view of Connolly disclose the system of claim 5, wherein the reinforcement learning system is further configured to estimate a value function using a Dirichlet Differencing (DD) update rule. (Examiner’s Note: Dirichlet Differencing is defined in the instant specification in para. [0071] as “In an aspect, the computing system 300 may implement a special case of reinforcement learning (referred to as Dirichlet Differencing – DD) where rewards are confined to a “boundary.” In other words, the agent 202 may only receive rewards in certain states, and not in others. This type of RL is known as an absorbing Markov chain. In an aspect, the Markov Model 350 may comprise an instance of the absorbing Markov chain”. Connolly abstract teaches reinforcement learning value functions may be reconstructed by relaxation once the extrema are known. Section 2.1 explains that obstacle and goal states supply fixed boundary conditions and that the harmonic function is calculated using successive over-relaxation. Section 4 identifies the boundary values as absorbing state rewards/penalties and establishes that the expected values are harmonic. It then compares TD and SOR and states Sor was iterated over the entire grid with absorbing state values used as boundary conditions. This teaches the function definition of DD update rules wherein rewards are confined to absorbing boundary states with the value estimated distributed to interior states by harmonic relaxation. )
In regards to claim 7, Connor in view of Connolly disclose the system of claim 1, wherein the reinforcement learning system is further configured to estimate a value function and wherein one or more measurements indicate a quality of the estimated value function. (Connolly section 4 page 8 paragraph 3 the text after equation 13 teaches equation 13 is the expected value function for Markov Chains subjected to appropriate boundary conditions. It then goes on in paragraph 4 to teach applying harmonic min-max property as a quality or convergence test, wherein the presence of local minima indicates the function has not converged.)
In regards to claim 8, Connor in view of Connolly disclose the system of claim 7, wherein the one or more measurements indicate a quality of the estimated value function for the one or more MDPs, and wherein the one or more MDPs comprise an absorbing MDP. (Connolly section 4 page 8 paragraph 3 the text after equation 13 teaches equation 13 is the expected value function for Markov Chains subjected to appropriate boundary conditions. It then goes on in paragraph 4 to teach applying harmonic min-max property as a quality or convergence test, wherein the presence of local minima indicates the function has not converged. Connolly section 2.2 first paragraph teaches a Markov Chain having an absorbing set divided into obstacle and goal subsets. It defines the probability of absorption in one subset before reaching the other and shows the probability satisfies the weighted mean-value equation (equations 4 & 5). Connolly Section 4 page 8 paragraphs 1-3 along with equations 12 and 13 the expected value function for a Markov chain (absorbing chain) is determined by the transition matrix (P) and the expected values at the absorbing states (z). It also states a regular function for Markov chain defined by P is harmonic.))
In regards to claim 10, Connor in view of Connolly disclose the system of claim 1, wherein the reinforcement learning system configured to distribute the credit across the explored state space is further configured to perform a relaxation update to distribute the credit. (Connolly abstract teaches expected values obtained by reinforcement learning (RL) can be rapidly reconstructed by relaxation once the extrema for such functions are known. Connolly page 1 section 1 teaches harmonic field is computed globally over the entire region of interest using a grid-based relaxation technique. Connolly section 2.1 page 4 first paragraph teaches successive overrelaxation (SOR) is used to solve the harmonic equations across the lattice. Connolly section 4 page 8 last paragraph – page 9 first paragraph teaches SOR computation performing 53 iterations when the boundary conditions were defined as in the TD case. Connolly page section 4 page 10 last paragraph and equation 14 teaches distributing credit (reward).)
Claim 13 is the method embodiment of claim 1 with similar limitation and thus is rejected using the same reasoning as that of claim 1.
Claim 14 is the method embodiment of claim 2 with similar limitation and thus is rejected using the same reasoning as that of claim 2.
Claim 17 is the method embodiment of claim 5 with similar limitation and thus is rejected using the same reasoning as that of claim 5.
Claim 18 is the method embodiment of claim 6 with similar limitation and thus is rejected using the same reasoning as that of claim 6.
Claim 19 is the method embodiment of claim 7 with similar limitation and thus is rejected using the same reasoning as that of claim 7.
Claim 20 is the non-transitory computer-readable storage media embodiment of claim 1 with similar limitation and thus is rejected using the same reasoning as that of claim 1.
Claims 3-4, 9, and 15-16 are rejected under 35 U.S.C. 103 as being unpatentable over Basich et al. (US 2021/0132606 A1 – hereinafter Connor) in view of Connolly (“Harmonic Functions and Collision Probabilites”) and further in view of Seabrook et al. (“A Tutorial on the Spectral Theory of Markov Chains” – hereinafter Seabrook.).
In regards to claim 3, Connor in view of Connolly disclose the system of claim 2, and a transition matrix P (Connolly Section 4 page 8 paragraphs 1-3 along with equations 12 and 13 the expected value function for a Markov chain (absorbing chain) is determined by the transition matrix (P) and the expected values at the absorbing states (z)), but does not explicitly disclose wherein the absorbing Markov chain comprises a time-homogeneous Markov chain governed by a stochastic transition matrix P.
Seabrook disclose wherein the Markov chain comprises a time-homogeneous Markov chain governed by a stochastic transition matrix. (Seabrook page 4 section 2.1 teaches when transition probabilities are independent of time, the Markov chain is homogeneous. The probabilities Pr(Xt+1 = sj|Xt = si) = Pij are collectively represented by an NxN right stochastic matrix where the rows sum to one. This teaches a time-homogeneous Markov chain governed by stochastic transition matrix P.)
It would have been obvious to one of ordinary skill in the art before the earliest effective filing date of the claimed invention to modify the teachings of the Connor in view of Connolly with that time-homogeneous Markov chain governed by a stochastic transition matrix P, as both Connor and Connolly disclose Markov models and Connolly disclose the use of the transition matrix. The benefit of using a time-homogenous Markov chain governed by a stochastic transition matrix is allows for simpler calculations as the transition probabilities are not longer dependent on time and the chance of moving from one state to another stays the same at every step so a new rule or updated transition table is not need at every new time step. This creates simpler calculations and a more efficient system.
In regards to claim 4, Connor in view of Connolly disclose the system of claim 2, but does not explicitly disclose wherein a stationary distribution for the absorbing Markov chain is concentrated at one or more absorbing states and is 0 at other states.
Seabrook discloses wherein a stationary distribution for the absorbing Markov chain is concentrated at one or more absorbing states and is 0 at other states. (Seabrook section 2.7 first paragraph teaches that all non-absorbing states are transient in an absorbing chain. Then on page proposition 2.4.9 teaches that every stationary distribution assigns probability zero to transient class states and that each recurrent class has a stationary distribution supported only on the that class. This means that non-absorbing states are transient and absorbing states form recent single classes, every stationary distribution is focused on one absorbing state and is zero at all non-absorbing states.)
It would have been obvious to one of ordinary skill in the before the earliest effective filing date of the claimed invention to modify the teachings of Connor in view of Connolly with that teachings of Seabrook in in the order for concentrated on absorbing states and 0 at other states as all the reference deal with using Markov Models. It provides the benefit of reliability and convergence by assuring that Connor does not get stuck in a non-goal or intermediate state.
In regards to claim 9, Connor in view of Connolly disclose the system of claim 1, wherein a reinforcement learning system is further configured to: perform a plurality of actions within the environment to explore the state space for the domain model; and (Connor para. [0228] cites “From 6018, the technique 6000 proceeds back 6002 to repeat the above described operations whereby the technique 6000 detects the current state of the world, selects an action to execute and an autonomy level, and so on.” and para. [0224] cites “In reinforcement learning literature, where the domain is not known, an agent must tradeoff between either exploiting the information it has and simply taking the action that has performed the best in the past, or exploring new actions and new states ( or ones that were simply suboptimal in the past) which may tum out to be better.”)
However Connor in view of Connolly does not explicitly disclose generate a topology of the explored state space.
Seabrook generate a topology of the explored state space. (Seabrook section 2.1 third paragraph cites “Markov chains can also be depicted visually in the form of a graph, with the state space S drawn as a collection of circles and labelled arrows between these circles representing the non-zero transition probabilities Pij . We call this diagram the transition graph of a Markov chain.” and the next paragraph teaches observing a PhD student for a few days and then generating a transition graph which is show in figure 1 on page 4.
It would have been obvious to one of ordinary skill in the art before the earliest effective filing date of the claimed invention to modify the teachings of Connor in view of Connolly with that topology (transition graph) of the Seabrook as all the reference deal with using Markov model and transition probabilities. The benefit of creating a transition graph from the information provides a easily readable and human interpretable transition graph for the users.
Claim 15 is the method embodiment of claim 3 with similar limitation and thus is rejected using the same reasoning as that of claim 3.
Claim 16 is the method embodiment of claim 4 with similar limitation and thus is rejected using the same reasoning as that of claim 4.
Allowable Subject Matter
Claims 11-12 are 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. None of the cited prior art references alone or in combination disclose wherein the reinforcement system comprise a non-absorbing Markov chains. The prior art reference disclose Markov chains having absorbing and non-absorbing states but not the entire chain is non-absorbing. Without a reference positively stating such, it would not have been obvious to the examiner to do so.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Kim et al. – US 2020/0279149 – teaches a method that uses reinforcement learning used by a generate a control a virtual environment wherein the environment and control is done using actual measurement data from the environment. It also discloses using Markov decision process (MDP) along with states, actions, rewards and transition probabilities.
Nikou et al. – US 2024/0311687 - teaches determining Companion Markov Decision Process (CMDP) that encodes states of the environment using a subset of the set of features used by the reinforcement learning (RL) agent. CMDPs, are a modified implementation of Markov Decision Processes (MDPs) that may be used to incorporate logical intents into the RL process to assist in the selection of actions that are compliant with the intent. A MDP is a tuple of the general form (S, A, Pa, Ra), where S is the set of states, A is the set of actions available in state s, Pa is the probability that performing action a when in state s will result in state s′, and Ra is the reward for transitioning from state s to state s’. MDPs are state-action discrete models, which model transitions between states of an environment as a result of actions performed on the environment.
Pierre-Luc Bacon – “On the Bottleneck Concept for Options Discovery: Theoretical Underpinnings and Extension in Continuous State Spaces” – teaches the theory of MDP in section 2.1 and 2.2 and also discusses absorbing chains.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to PAULINHO E SMITH whose telephone number is (571)270-1358. The examiner can normally be reached Mon-Fri. 10AM-6PM CST.
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, Abdullah Kawsar can be reached at 571-270-3169. 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.
/PAULINHO E SMITH/Primary Examiner, Art Unit 2127
Prosecution Insights