Particle methods for nonlinear control

• US 8,965,834 B2
• Filed: 11/20/2012
• Issued: 02/24/2015
• Est. Priority Date: 12/07/2011
• Status: Active Grant

• Current Assignee: Artificial Genius Incorporated
• Original Assignee: Extendabrain Corp.
• Inventors: Burchard, Paul
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US13/682,088
• Publication Number:
  US 20130151460A1
• Time in Patent Office: 826 Days
• Field of Search: 706/52
• US Class Current: 706/52
• CPC Class Codes: G06N 3/006 based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
• CPC Class Codes: G06N 5/042 Backward inferencing
• CPC Class Codes: G06N 5/048 Fuzzy inferencing
• CPC Class Codes: G06N 7/00 Computing arrangements based on specific mathematical models
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06N 7/02 using fuzzy logic computing arrangements based on biological models G06N3/00; computing arrangements using knowledge-based models G06N5/00

Abstract

Aspects herein describe new methods of determining optimal actions to achieve high-level goals with minimum total future cost. At least one high-level goal is inputted into a user device along with various observational data about the world, and a computational unit determines, through particle methods, an optimal course of action as well as emotions. The particle method comprises alternating backward and forward sweeps and tests for convergence to determine said optimal course of action. In one embodiment a user inputs a high-level goal into a cell phone which senses observational data. The cell phone communicates with a server that provides instructions. The server determines an optimal course of action via the particle method, and the cell phone then displays the instructions and emotions to the user.

Claims

1. A method comprising:

receiving, by a sensor, a current observation about a real or simulated world;

maintaining, by a computational unit, an objective;

representing the objective using an incremental cost of a plurality of potential actions;

maintaining, by the computational unit, a current uncertainty about an unknown state of the world, wherein the current uncertainly is updated using the current observation;

determining, by the computational unit, one or more optimal actions to achieve the objective with a minimum expected total future cost, wherein said determining comprises performing both backward induction on the minimum expected total future cost and forward induction on the uncertainty about the unknown state of the world, wherein said determining makes approximations based on an unstructured sample of the plurality of unknown states of the world; and

effecting, via an actuator, the one or more optimal actions.

2. The method of claim 1, further comprising:

determining a first number t, which represents a future time;

determining a first vector x, which represents the unknown state of the world at time t;

determining a second vector u, which represents a potential action at time t;

determining a sequence of vectors i, called the information, which represents the preferred history of observations from the current time up to time t, leading to state x;

determining a first function ƒ

(t,x), called the local cost function;

determining a first probability distribution p(t,x), called the unconditional uncertainty, which represents the uncertainty of the plurality of unknown states x of the world at time t, unconditional on future observations;

wherein said induction comprises;

restricting the set of future uncertainties conditional on observations that need to be considered to probability distributions of the form p_i(t,x), which comprises the restriction of the unconditional uncertainty p(t,x) to states x having the same information i at time t;

representing the expected total future cost at time t with information i as E_pi[ƒ

], where the operator E[ ] represents the expectation of a function with respect to a probability distribution;

determining the local cost function ƒ

by backward induction;

determining the unconditional uncertainty p and the information i by forward induction; and

determining the optimal actions u by optimization for each value of the information i and time t.

3. The method of claim 2, wherein the steps of representing the objective and the stochastic dynamics of the world include:

determining second number dt, which represents the time step;

determining a third vector y, which represents the observation at time t;

determining a first stochastic function A(t,x,u), called the dynamics, whose values provide the random distribution of state after time step dt when starting from state x and taking the potential action u at time t;

determining a second stochastic function B(t,x,u), called the measurement, whose values provide the random distribution of observations after time step dt when starting from state x and taking the potential action u at time t; and

determining a second function C(t,y,u), which represents the incremental cost over time step dt of the potential action u, based in part on the observation y, at time t, wherein backward induction determines ƒ

at time t from time t+dt by;

ƒ

(t,x)=C(t,y,u)+E<sub>x′

˜

A(t,x,u)</sub>[ƒ

(t+dt,x′

)]

where ˜

denotes the distribution of a stochastic variable,

wherein forward induction determines p at time t+dt from time t by;

p(t+dt,x′

)˜

{x′

A(t,x,u)|x˜

p(t,x)}

and determines i at time t+dt from time t as a preferred value of i appended with the observation y, and

wherein the optimization of the potential actions determines u at time t by;

u=arg min E_pi[ƒ

(t,x)|u].

4. The method of claim 3, further comprising determining an approximate solution of the backward and forward induction equations by means of an unstructured sample, comprising:

determining a sample of particles such that each particle in the sample possesses;

an instance of time t,

an instance of the unknown state x,

an instance of the observation y,

an instance of the potential action u,

an instance of the value of the local cost function f,

an instance of the information i,

an instance of a weight representing the probability assigned by the unconditional uncertainty p, and

an instance of a uniform weight q representing the relative number of states of the world represented by this sampled particle;

repeating, until convergence is achieved, the following unordered steps;

initializing the instance of the value f of the local cost function of each particle to a known terminal cost,

performing a backward sweep in time of the instance of the value f of the local cost function on the sampled particles,

determining a candidate for the optimal potential action u at the current time,

initializing the instance of the weight p of each particle to approximate the known current uncertainty about the unknown state of the world,

initializing the instance of the information i of each particle to the known current observation y,

performing a forward sweep in time of the instance of the weight p and the instance of the information i on the sampled particles,

determining whether the instance of the weight p and the instance of the information i have converged for all particles at a terminal time, or whether the candidate for the optimal action u has converged at the initial time; and

identifying one or more optimal actions as candidate optimal actions in the final iteration of this sequence of steps when convergence has been achieved.

5. The method of claim 4, wherein performing the backward sweep comprises repetition of the following unordered steps until the current time is reached:

propagating the particles backward in time;

performing particle interactions; and

optionally resampling the particles,

and wherein the forward sweep comprises repetition of the following unordered steps until the terminal time is reached;

propagating the particles forward in time;

performing particle interactions; and

optionally resampling the particles.

6. The method of claim 5 wherein the computations involved in each step in respect of each particle is carried out by means of a parallel computational sub-unit, and the particle interactions are effected by means of communication between the parallel computational sub-units.

7. The method of claim 5 wherein the sampling or resampling particles further includes:

determining a desired un-normalized particle sampling density r(x); and

employing importance sampling according to the desired un-normalized sampling density r(x).

8. The method of claim 7 wherein the step of employing importance sampling according to the un-normalized density r(x) comprises applying, one or more times, the following sequence of steps to all particles in the old sample to produce the new sample:

starting with an old particle with state x;

randomly drawing a symmetric jump from state x to another state x′

;

creating, with a probability of min(1, r(x′

)/r(x)) a new particle with state x′

;

creating, independently and with probability max(0, 1−

r(x′

)/r(x)), a new particle with state x.

9. The method of claim 3, wherein the computation of the variance of the total future cost under the assumption of optimal actions is obtained as:

E_pi[ƒ

₂]−

(E_pi[ƒ

])²,

wherein the local square cost function ƒ

₂(t,x) is determined by backward induction according to the equation;

ƒ

₂(t,x)=C(t,y,u)²+2C(t,y,u)E<sub>x′

˜

A(t,x,u)</sub>[ƒ

(t+dt,x′

)]+E<sub>x′

˜

A(t,x,u)</sub>[F₂(t+dt,x′

)].

10. The method of claim 2, wherein the steps of representing the objective and the stochastic dynamics of the world include:

determining a third vector y, which represents the observation at time t;

determining a second function c(t,y,u), which represents the incremental cost of the potential action u, based in part on the observation y, at time t;

determining a third function a(t,x,u), called the expected dynamics, which represents the average rate of change of the state x when the potential action u is taken at time y;

determining a fourth function s(t,x), called the noise, which represents the standard deviation of the rate of change of the state x at time t; and

determining a fifth function m(t,x), called the measurement, which represents the measurement process that yields the observation y in state x at time t.

11. The method of claim 10, wherein the local cost function ƒ

is determined by backward induction according to the backward time differential equation;

12. The method of claim 11, further including determining an approximate solution of the backward and forward differential equations, comprising:

determining a sample of particles such that each particle in the sample possesses;

an instance of time t,

an instance of the unknown state x,

an instance of the observation y,

an instance of the potential action u,

an instance of the value of the local cost function ƒ

,

an instance of the information i,

an instance of a weight representing the probability assigned by the unconditional uncertainty distribution p,

an instance of a uniform weight q representing an approximation of a uniform probability distribution on unknown states at time t;

repeating the following sequence of steps until convergence is achieved;

initializing the instance of the value ƒ

of the local cost function of each particle to a known terminal cost,

performing a backward sweep in time of the instance of the value ƒ

of the local cost function on the sampled particles,

determining a candidate for the optimal potential action u at the current time,

initializing the instance of the weight p of each particle to approximate the known current uncertainty about the unknown state of the world,

initializing the instance of the information i of each particle to the known current observation y,

performing a forward sweep in time of the instance of the weight p and the instance of the information i on the sampled particles,

determining whether the instance of the weight p and the instance of the

information i have converged for all particles at a terminal time; and

identifying one or more optimal actions as candidate optimal actions in the final iteration of this sequence of steps when convergence has been achieved.

13. The method of claim 12 wherein performing the backward sweep comprises repetition of the following steps until the current time is reached:

propagating the particles backward in time;

performing particle interactions; and

optionally resampling the particles, and

wherein the forward sweep comprises repetition of the following steps until the terminal time is reached;

propagating the particles forward in time;

performing particle interactions; and

optionally resampling the particles.

14. A method of simulating an emotional response, comprising:

receiving, by a sensor, a current observation about a real or simulated world;

maintaining, by a computational unit, an objective;

representing the objective using an incremental cost of a plurality of potential actions;

maintaining, by the computational unit, a current uncertainty about an unknown state of the world, wherein the current uncertainly is updated using the current observation;

determining, by the computational unit, one or more optimal actions to achieve the objective with a minimum expected total future cost;

determining, via the computational unit, a significant statistic of the computation determining the optimal actions, corresponding to a simulated emotion; and

communicating, via an actuator, a representation of the emotion to the world.

15. The method of claim 14, wherein the statistic of the computation is the minimum expected total future cost, of which low values correspond to a happy emotion and high values correspond to a sad emotion.

16. The method of claim 14, wherein the statistic of the computation is the variance of the total future cost under an assumption of optimal actions, of which low values correspond to a calm emotion and high values correspond to a tense emotion,

wherein a combination of tense and sad emotions is interpreted as a fearful emotion, and

wherein a combination of tense and happy emotions is interpreted as an excited emotion.

17. The method of claim 14, wherein the statistic of the computation is the covariance of the total future costs of two competing objectives under an assumption of optimal actions, the first objective representing the self, and the second objective representing another actor in the world, of which a negative value in combination with a sad emotion is interpreted as an angry emotion, and a negative value in combination with a happy emotion is interpreted as a gloating emotion, and a positive value in combination with a happy emotion is interpreted as a loving emotion.

18. A system comprising:

a sensor configured to receive input defining a current observation about a real or simulated world;

a computational unit configured to;

maintain an objective,

represent the objective using an incremental cost of a plurality of potential actions,

maintain a current uncertainty about an unknown state of the world, wherein the current uncertainly is updated using the current observation, and

determine one or more optimal actions to achieve the objective with a minimum expected total future cost, wherein said determining comprises performing both backward induction on the minimum expected total future cost and forward induction on the uncertainty about the unknown state of the world, wherein said determining makes approximations based on an unstructured sample of the plurality of unknown states of the world; and

an actuator configured to effect the one or more optimal actions based on instructions from the computational unit.