# US 12,001,934 B2 · Method and apparatus for constructing informative outcomes to guide multi-policy decision making > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,001,934 B2 - Document ID: US12001934B2 - Status: Granted - Kind: B2 - Application number: 18/196,897 - Filed: 2023-05-12 - Published: 2023-09-14 - Granted: 2024-06-04 - Earliest claimed: 2017-03-17 - Assignees: The Regents of the University of Michigan - Applicants: The Regents of the University of Michigan - Inventors: Edwin Olson; Dhanvin H. Mehta; Gonzalo Ferrer - Web page: https://patentgrep.com/patent/US12001934B2 ## CPC - G06N 3/02: Neural networks - G06N 3/008: based on physical entities controlled by simulated intelligence so as to replicate intelligent life forms, e.g. based on robots replicating pets or humans in their appearance or behaviour - G06N 3/084: Backpropagation, e.g. using gradient descent - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - H04N 1/00002: {Diagnosis, testing or measuring; Detecting, analysing or monitoring not otherwise provided for (error detection, error correction or monitoring in digital computers or digital computer components G06F11/00)} - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract In Multi-Policy Decision-Making (MPDM), many computationally-expensive forward simulations are performed in order to predict the performance of a set of candidate policies. In risk-aware formulations of MPDM, only the worst outcomes affect the decision making process, and efficiently finding these influential outcomes becomes the core challenge. Recently, stochastic gradient optimization algorithms, using a heuristic function, were shown to be significantly superior to random sampling. In this disclosure, it was shown that accurate gradients can be computed—even through a complex forward simulation—using approaches similar to those in dep networks. The proposed approach finds influential outcomes more reliably, and is faster than earlier methods, allowing one to evaluate more policies while simultaneously eliminating the need to design an easily-differentiable heuristic function. ## Claims ### Claim 1 A method comprising: for each policy of a set of policies: receiving a set of state estimates comprising: a state estimate for an agent and a state estimate for each of a set of objects; perturbing the set of state estimates to generate a set of perturbed state estimates; based on the policy, simulating movement of the set of objects and the agent with a set of simulations based on the set of perturbed state estimates; and determining a respective score for the policy based on an outcome quantified for the set of simulations; selecting a policy from the set of policies based on the respective score; and commanding the agent based on the selected policy. ### Claim 2 (depends on 1) The method of claim 1, further comprising, for each policy: with a first set of simulations, simulating movement of the set of environmental objects and the controlled object based on the set of state estimates, wherein the perturbation of the set of state estimates is based on the first set of simulations. ### Claim 3 (depends on 2) The method of claim 2, wherein the set of perturbed state estimates is associated with a set of influential outcomes of the first set of simulations, wherein each of the set of influential outcomes is associated with a set of cost metrics, wherein each of the set of cost metrics has a greater value than a cost metric associated with the set of state estimates. ### Claim 4 (depends on 3) The method of claim 3, wherein the set of influential outcomes is determined with an anytime algorithm. ### Claim 5 (depends on 3) The method of claim 3, wherein the set of influential outcomes is determined with a backpropagation process. ### Claim 6 (depends on 1) The method of claim 1, wherein the set of simulations comprises a series of forward simulations. ### Claim 7 (depends on 6) The method of claim 6, wherein the forward simulations are conducted iteratively over the set of perturbed state estimates based on a gradient computed iteratively over a series of timesteps. ### Claim 8 (depends on 1) The method of claim 1, wherein the score is determined with a cost function which evaluates a Blame metric and a Progress metric, wherein the Progress metric is based on proximity to an agent goal point, wherein the Blame metric is based on agent proximity to objects of the set of object. ### Claim 9 (depends on 8) The method of claim 8, wherein the cost function comprises a linear combination of the Blame metric and the Progress metric. ### Claim 10 (depends on 8) The method of claim 8, wherein the Blame metric is determined as a function of a velocity of the agent and a distance between the agent and an object of the set of objects. ### Claim 11 (depends on 8) The method of claim 8, wherein the score is further determined based on a probability of the perturbed state estimates. ### Claim 12 (depends on 1) The method of claim 1, wherein the respective score for each policy is determined based on a distance between the agent and a closest object of the set of objects. ### Claim 13 (depends on 1) The method of claim 1, wherein the set of simulations comprises repeating a simulation until a predetermined condition is satisfied. ### Claim 14 (depends on 13) The method of claim 13 wherein the predetermined condition is policy-specific. ### Claim 15 (depends on 1) The method of claim 1, wherein the respective score is determined based on multiple outcomes quantified for the set of simulations. ### Claim 16 (depends on 1) The method of claim 1, wherein the agent comprises an autonomous vehicle. ### Claim 17 (depends on 1) The method of claim 1, wherein the set of policies comprises a plurality of policies. ### Claim 18 (depends on 17) The method of claim 17, wherein set of simulations and policy selection are executed in real-time relative to receipt of the set of state estimates. ### Claim 19 (depends on 1) The method of claim 1, wherein the set of objects comprises a plurality of objects in an environment of the agent. ### Claim 20 (depends on 1) The method of claim 1, wherein commanding the agent comprises commanding the agent to traverse through the environment according to the policy.