Selecting actions to be performed by a robotic agent

1. A method of planning actions to be performed by a robotic agent interacting with an environment to accomplish an objective, the method comprising:

determining an optimized trajectory of state—action pairs for accomplishing the objective, the state in each state action pair being a state encountered by the robotic agent during interaction with the environment and the action in the state—action pair being an action to be performed by the robotic agent when the environment is in the state, and the determining comprising:

maintaining a current optimized trajectory and a current trust region radius;

linearizing an environment dynamics mapping within a vicinity of the current optimized trajectory, wherein the environment dynamics mapping defines a mapping from an input state of the environment and an input action of the robotic agent to an output state of the environment that would result from performing the input action in response to the input state of the environment;

optimizing a localized objective within the current trust region radius of the current optimized trajectory to determine a candidate updated optimized trajectory subject to a constraint that the candidate updated optimized trajectory satisfies the linearized environment dynamics mapping, wherein the constraint requires that, for each state—action pair in the candidate updated optimized trajectory before a last state—action pair in the candidate optimized trajectory:

a result of processing the state and the action in the state—action pair using the linearized environment dynamics mapping matches the state in a next state—action pair in the candidate optimized trajectory;

determining whether the candidate updated optimized trajectory improves over the current optimized trajectory; and

in response to determining that the candidate updated optimized trajectory improves over the current optimized trajectory, updating the current optimized trajectory to the candidate updated optimized trajectory and updating the current trust region radius.

2. The method of claim 1 , wherein updating the current optimized trajectory to the candidate updated optimized trajectory and updating the current trust region radius comprises:

increasing the current trust radius.

3. The method of claim 1 , further comprising:

in response to determining that the candidate updated optimized trajectory does not improve over the current optimized trajectory, updating the current trust region radius without updating the current optimized trajectory.

4. The method of claim 3 , wherein updating the current trust region radius without updating the current optimized trajectory comprises:

shrinking the current trust radius.

5. The method of claim 1 , wherein the localized objective function comprises one or more non-convex and non-differentiable terms, and wherein optimizing the localized objective within the current trust region radius of the current optimized trajectory comprises:

optimizing the localized objective comprising the one or more non-convex and non-differentiable terms using a consensus alternating direction method of multipliers (ADMM) optimization.

6. The method of claim 1 , wherein the objective is expressed as a cost function to be minimized by the optimized trajectory, and wherein the method further comprises:

convexifying or partially convexifying the cost function around the current optimized trajectory; and

wherein optimizing the localized objective within the current trust region radius of the current optimized trajectory comprises:

optimizing the convexified or partially convexified cost function within the current trust region radius of the current optimized trajectory.

7. The method of claim 1 , wherein the optimized trajectory has additional constraints on navigation of the robotic agent through the environment and wherein the method further comprises:

convexifying or partially convexifying the additional constraints around the current optimized trajectory; and

wherein optimizing the localized objective within the current trust region radius of the current optimized trajectory comprises:

optimizing the localized objective within the current trust region radius of the current optimized trajectory to determine a candidate updated optimized trajectory that satisfies the convexified or partially convexified additional constraints.

8. The method of claim 1 , further comprising:

maintaining a filter of cost satisfaction—constraint satisfaction pairs, each pair comprising a cost satisfaction measure and a constraint satisfaction measure for either (i) the current optimized trajectory or (ii) a previous optimized trajectory, and wherein determining whether the candidate updated optimized trajectory improves over the current optimized trajectory comprises:

determining a cost satisfaction measure and a constraint satisfaction measure for the candidate updated optimized trajectory; and

determining that the candidate updated optimized trajectory improves over the current optimized trajectory when no pair in the filter has both (i) a cost satisfaction measure that is superior to the cost satisfaction measure for the candidate updated optimized trajectory and (ii) a constraint satisfaction measure that is superior to the constraint satisfaction measure for the candidate updated optimized trajectory.

9. The method of claim 8 , further comprising:

in response to determining that the candidate updated optimized trajectory improves over the current optimized trajectory, removing from the filter any pair having both (i) a cost satisfaction measure that is inferior to the cost satisfaction measure for the candidate updated optimized trajectory and (ii) a constraint satisfaction measure that is inferior to the constraint satisfaction measure for the candidate updated optimized trajectory.

10. The method of claim 1 , further comprising:

performing, by the robotic agent, the planned actions to accomplish the objective based upon the optimized trajectory.

11. A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one more computers to plan actions to be performed by a robotic agent interacting with an environment to accomplish an objective, the planning comprising:

determining an optimized trajectory of state—action pairs for accomplishing the objective, the state in each state—action pair being a state encountered by the robotic agent during interaction with the environment and the action in the state—action pair being an action to be performed by the robotic agent when the environment is in the state, and the determining comprising:

maintaining a current optimized trajectory and a current trust region radius;

linearizing an environment dynamics mapping within a vicinity of the current optimized trajectory, wherein the environment dynamics mapping defines a mapping from an input state of the environment and an input action of the robotic agent to an output state of the environment that would result from performing the input action in response to the input state of the environment;

optimizing a localized objective within the current trust region radius of the current optimized trajectory to determine a candidate updated optimized trajectory subject to a constraint that the candidate updated optimized trajectory satisfies the linearized environment dynamics mapping, wherein the constraint requires that, for each state—action pair in the candidate updated optimized trajectory before a last state—action pair in the candidate optimized trajectory:

a result of processing the state and the action in the state—action pair using the linearized environment dynamics mapping matches the state in a next state—action pair in the candidate optimized trajectory;

determining whether the candidate updated optimized trajectory improves over the current optimized trajectory; and

in response to determining that the candidate updated optimized trajectory improves over the current optimized trajectory, updating the current optimized trajectory to the candidate updated optimized trajectory and updating the current trust region radius.

12. The system of claim 11 , wherein updating the current optimized trajectory to the candidate updated optimized trajectory and updating the current trust region radius comprises:

increasing the current trust radius.

13. The system of claim 11 , wherein the planning further comprises:

in response to determining that the candidate updated optimized trajectory does not improve over the current optimized trajectory, updating the current trust region radius without updating the current optimized trajectory.

14. The system of claim 13 , wherein updating the current trust region radius without updating the current optimized trajectory comprises:

shrinking the current trust radius.

15. The system of claim 11 , wherein the localized objective function comprises one or more non-convex and non-differentiable terms, and wherein optimizing the localized objective within the current trust region radius of the current optimized trajectory comprises:

optimizing the localized objective comprising the one or more non-convex and non-differentiable terms using a consensus alternating direction method of multipliers (ADMM) optimization.

16. One or more non-transitory computer storage media storing instructions that when executed by one or more computers cause the one more computers to plan actions to be performed by a robotic agent interacting with an environment to accomplish an objective, the planning comprising:

determining an optimized trajectory of state—action pairs for accomplishing the objective, the state in each state—action pair being a state encountered by the robotic agent during interaction with the environment and the action in the state—action pair being an action to be performed by the robotic agent when the environment is in the state, and the determining comprising:

maintaining a current optimized trajectory and a current trust region radius;

linearizing an environment dynamics mapping within a vicinity of the current optimized trajectory, wherein the environment dynamics mapping defines a mapping from an input state of the environment and an input action of the robotic agent to an output state of the environment that would result from performing the input action in response to the input state of the environment;

optimizing a localized objective within the current trust region radius of the current optimized trajectory to determine a candidate updated optimized trajectory subject to a constraint that the candidate updated optimized trajectory satisfies the linearized environment dynamics mapping, wherein the constraint requires that, for each state—action pair in the candidate updated optimized trajectory before a last state—action pair in the candidate optimized trajectory:

a result of processing the state and the action in the state—action pair using the linearized environment dynamics mapping matches the state in a next state—action pair in the candidate optimized trajectory;

determining whether the candidate updated optimized trajectory improves over the current optimized trajectory; and

in response to determining that the candidate updated optimized trajectory improves over the current optimized trajectory, updating the current optimized trajectory to the candidate updated optimized trajectory and updating the current trust region radius.

17. The non-transitory computer storage media of claim 16 , wherein updating the current optimized trajectory to the candidate updated optimized trajectory and updating the current trust region radius comprises:

increasing the current trust radius.

18. The non-transitory computer storage media of claim 16 , wherein the planning further comprises:

in response to determining that the candidate updated optimized trajectory does not improve over the current optimized trajectory, updating the current trust region radius without updating the current optimized trajectory.

19. The non-transitory computer storage media of claim 18 , wherein updating the current trust region radius without updating the current optimized trajectory comprises:

shrinking the current trust radius.