Patent Description:
Reinforcement Learning (RL) is a machine learning paradigm that allows a machine to learn to perform desired behaviours with respect to a task specification, e.g. which control actions to take to reach a goal location in a robotic navigation scenario. Learning a policy that generates these behaviours with reinforcement learning differs from learning it with supervised learning in the way the training data is composed and obtained: While in supervised learning the provided training data consists of matched pairs of inputs to the policy (e.g. observations like sensory readings) and desired outputs (actions to be taken), there is no fixed training data provided in case of reinforcement learning. The policy is learned from experience data gathered by interaction of the machine with its environment whereby a feedback (reward) signal is provided to the machine that scores/asses the actions taken in a certain context (state).

The data-efficiency of RL algorithms is low in case the provided reward signal is very sparse. As a result, the training to meet a certain quality criterion with the trained control policy may take very long.

The publication "<NPL>, describes Value Iteration Networks (VIN) as a fully-differentiable planning module that learns an approximation of a value iteration planning algorithm. In a continuous control task, they hierarchically combine high-level VIN planning on a discrete, coarse, grid representation of the continuous environment with a low-level continuous control policy trained via guided policy search. The low-level policy receives a local excerpt of the value function (map) generated by the VIN planner as additional input.

The HiDe algorithm described in "<NPL>, hierarchically combines Value Propagation Networks (VProp), an improvement of VIN, with reinforcement learning for solving continuous state and action space robotic navigation tasks. The high-level VProp planner generates sub-goals for the low-level reinforcement learning. The VProp planner receives a 2D bird's-eye view image (coarse, discrete map representation) of the environment as input and calculates a value map as output. The current 2D position of the agent falls into one of the discrete cells. The next target cell for the low-level (RL) policy is selected by choosing the neighboring cell with the highest value in the value map. By subtracting the current 2D position from the target grid cell position, a target vector is generated. This target vector is refined by an 'interface layer policy' before being provided as an input to the low-level continuous control RL policy that additionally receives the internal agent state as an input and calculates the continuous actions applied to the actuators of the agent. The whole hierarchical <NUM>-level planning/policy is trained end-to-end via reinforcement learning.

However, end-to-end reinforcement learning including learning the value iteration procedure itself requires a substantial training effort and in particular high amounts of training data.

In view of the above, more data-efficient approaches for controlling a robot are desirable.

The method and the robot with the features of the claims <NUM> and <NUM> allow controlling a robot by training with less observation data since only a transition probability model needs to be learned for the high-level planner (e.g. using supervised learning) as opposed to learning the value iteration procedure itself end-to-end (like in the HiDe approach mentioned above) with the low-level continuous control policy via reinforcement learning, which is a more difficult learning task (since a transition and reward function also have to be learned implicitly).

The approach of the independent claims is also computationally more efficient than approaches learning a value iteration model (such as HiDe) since no backpropagation of gradients through the planner via the continuous control policy to update the (recurrent) planner is necessary.

In the following, exemplary embodiments are given.

Example <NUM> is a method for controlling a robot comprising receiving an indication of a target configuration (state) to be reached from an initial configuration (state) of the robot, determining a coarse-scale value map by value iteration, wherein the transition probabilities are determined using a transition probability model mapping coarse-scale states and coarse-scale actions to transition probabilities for coarse-scale states and for each coarse-scale state of a sequence of coarse-scale states of the robot, starting from an initial coarse-scale state determined from the initial configuration (state) of the robot and until the robot reaches the target configuration (state) or a maximum number of fine-scale states has been reached, determining a fine-scale sub-goal from the coarse-scale value map, performing, by an actuator of the robot, fine-scale control actions to reach the determined fine-scale sub-goal and obtaining sensor data to determine the fine-scale states reached as a result of performing the fine-scale control actions for each fine-scale state of the resulting sequence of fine-scale states of the robot, starting from a current fine-scale state of the robot and until the robot reaches the determined fine-scale sub-goal, the robot transitions to a different coarse-scale state, or a maximum sequence length of the sequence of fine-scale states has been reached and determining the next coarse-scale state of the sequence of coarse-scale states from the last fine-scale state of the sequence of fine-scale states.

Example <NUM> is the method of Example <NUM>, wherein the transition probability model is a model trainable by supervised learning.

Example <NUM> is the method of Example <NUM> or <NUM>, wherein the transition probability model is a neural network.

Using a model trainable by supervised learning such as a neural network for determining transition probabilities allows usage of value iteration planning on the high-level (i.e. coarse-scale) and thus a data-efficient training of the robot control.

Example <NUM> is a robot controller configured to perform a method of any one of Examples <NUM> to Example <NUM>.

Example <NUM> is a method for training a robot controller according to Example <NUM>.

Example <NUM> is the method for training a robot controller of Example <NUM> comprising training the transition probability model using supervised learning.

As mentioned above, learning a transition probability model for the value iteration using supervised learning is more data-efficient than learning to approximately perform the value iteration algorithm (which implicitly includes learning transition dynamics) end-to-end with the low-level control policy via reinforcement learning.

Example <NUM> is the method for training a robot controller of Example <NUM>, comprising training the transition probability model by maximizing the probability of the transition probability model to predict a coarse-scale state reached by fine-scale actions performed to reach a sub-goal.

Training the transition probability model in this manner allows training the high-level planner together with performing reinforcement learning for the low-level policy, i.e. learning of the low-level control policy by performing training rollouts to gather data to update the policy.

Example <NUM> is the method for training a robot controller of any one of Examples <NUM> to <NUM>, comprising training a fine-scale control policy via reinforcement learning that determines the fine-scale control actions to reach a sub-goal.

The low-level control can thus be trained using a reinforcement learning approach of choice (such as Q-learning, Deep Q-learning (DQN), Trust Region Policy Optimization (TRPO), Proximal Policy Optimization (PPO), Deep Deterministic Policy Gradient (DDPG), Twin Delayed DDPG (TD3), (Asynchronous) Advantage Actor Critic (A2C/A3C)).

Example <NUM> is a computer program comprising instructions which, when executed by a computer, makes the computer perform a method according to any one of Examples <NUM> to <NUM> or <NUM> to <NUM>.

Example <NUM> is a computer-readable medium comprising instructions which, when executed by a computer, makes the computer perform a method according to any one of Examples <NUM> to <NUM> or <NUM> to <NUM>.

In the drawings, similar reference characters generally refer to the same parts throughout the different views.

The following detailed description refers to the accompanying drawings that show, by way of illustration, specific details and aspects of this disclosure in which the invention may be practiced.

In the following, various examples will be described in more detail.

A robot <NUM> is located in an environment <NUM>. The robot <NUM> has a start position <NUM> and should reach a goal position <NUM>. The environment <NUM> contains obstacles <NUM> which should be avoided by the robot <NUM>. For example, they may not be passed by the robot <NUM> (e.g. they are walls, trees or rocks) or should be avoided because the robot would damage or hurt them (e.g. pedestrians).

The robot <NUM> has a controller <NUM> (which may also be remote to the robot <NUM>, i.e. the robot <NUM> may be controlled by remote control). In the exemplary scenario of <FIG>, the goal is that the controller <NUM> controls the robot <NUM> to navigate the environment <NUM> from the start position <NUM> to the goal position <NUM>. For example, the robot <NUM> is an autonomous vehicle but it may also be a robot with legs or tracks or other kind of propulsion system (such as a deep sea or mars rover).

Furthermore, embodiments are not limited to the scenario that a robot should be moved (as a whole) between positions <NUM>, <NUM> but may also be used for the control of a robotic arm whose end-effector should be moved between positions <NUM>, <NUM> (without hitting obstacles <NUM>) etc..

Ideally, the controller <NUM> has learned a control policy that allows it to control the robot <NUM> successfully (from start position <NUM> to goal position <NUM> without hitting obstacles <NUM>) for arbitrary scenarios (i.e. environments, start and goal positions) in particular scenarios that the controller <NUM> has not encountered before.

Various embodiments thus relate to learning a control policy for a specified (distribution of) task(s) by interacting with the environment <NUM>. In training, the scenario (in particular environment <NUM>) may be simulated but it will typically be real in deployment.

Reinforcement Learning (RL) is a technique for learning a control policy. An RL algorithm iteratively updates the parameters θ of a parametric policy πθ (a|s), for example represented by a neural network, that maps states s (e.g. (pre-processed) sensor signals) to actions a (control signals). During training, the policy interacts in rollouts episodically with the (possibly simulated) environment <NUM>. During a (simulated training) rollout in the environment <NUM>, the controller <NUM>, according to a current control policy, executes, in every discrete time step an action a according to the current state s, which leads to a new state s' in the next discrete time step. Furthermore, a reward r is received, which it uses to update the policy. A (training) rollout ends once a goal state is reached, the accumulated (potentially discounted) rewards surpass a threshold, or the maximum number of time steps, the time horizon T, is reached. During training a reward-dependent objective function (e.g. the discounted sum of of rewards received during a rollout) is maximized by updating the parameters of the policy. The training ends once the policy meets a certain quality criterion with respect to the objective function, a maximum number of policy updates have been performed, or a maximum number of steps have been taken in the (simulation) environment.

The data-efficiency of RL algorithms is low in case the provided reward signal is very sparse: For example, a binary reward that indicates task completion is only provided at the end of the interaction episodes. As a result, the training to meet a certain quality criterion with the policy may take very long, requiring many interaction steps in the (simulation) environment and/or policy updates, or fail.

Assuming some prior knowledge about the (simulated) environment (e.g. the availability of a map in case of an robot/vehicle navigation task), the combination of a planning algorithm that guides the reinforcement learning may be used in order to improve data-efficiency.

According to various embodiments, the controller <NUM> uses high-level planning on a coarse, discrete (map) representation of the environment <NUM> to set (relative) sub-goals (target vectors) for a low-level controller trained via reinforcement learning that acts in the continuous state and action space of the environment <NUM>. The coarse, discrete representation of the environment is for example a grid <NUM> (shown as dashed lines in <FIG>) wherein each tile of the grid <NUM> is a state in the coarse representation of the environment. High-level is also referred to as coarse-scale. Low-level learning operates on a practically "continuous" (e.g. up to calculation or number representation accuracy) scale, i.e. a much finer representation. Low-level is also referred to as fine-scale. For example, for an autonomous driving scenario, the tiles of the grid <NUM> are <NUM> meters x <NUM> meters while the low-scale has an accuracy of centimeters, millimeters or even below.

Instead of trying to solve the difficult learning problem of learning a high-level planner and a low-level policy end-to-end via reinforcement learning, the learning of the planner and the policy parameters, respectively, is split into two (related) problems: planner parameters (representing the transition probabilities between high-level (i.e. coarse-scale) states) are inferred via supervised learning, which is a simpler learning problem than reinforcement learning, and the policy parameters are learned via reinforcement learning. Unlike the HiDe approach described above, the exact value iteration planning algorithm is used instead of a learned approximation (VIN/VProp). For this a model of the transition probabilities of transitioning between the coarse, discrete high-level states given a chosen neighboring target coarse-scale state and the current low-level reinforcement learning policy is trained and used. This transition probability model reflects the current capabilities of the low-level reinforcement learning agent. It is learned from the data gathered during the reinforcement learning episodes. Different types of transition probability models are in principle possible. Specifically, according to various embodiments, a parametric model (neural network) is trained (whose parameters are the parameters of the planner) by supervised learning that works with local agent observation features and thereby generalizes across different environment layouts.

In the following, embodiments may be described in more detail.

Consider a distribution of Markov Decision Processes (MDPs) <IMG> that share the same state space <MAT> and action space <MAT>. Specific MDPs m = (<IMG>, <IMG>, <IMG>, rm, γ, T) may be sampled. Start state s<NUM>,m and goal state gm are sampled from the MDP specific state space <MAT>. The (goal-dependent) reward function is of the following form: <MAT> with d(. ) being some distance measure such that there is only a reward of <NUM> in case the goal (i.e. target) has been reached (wherein ε is a small number, e.g. dimensioned to avoid that the distance has to become exactly zero). <IMG> are the MDP specific transition dynamics that model the transition from a state s to the next state s' given as a result of action a. γ is the discount factor and T the time horizon (maximum amount of steps to reach the goal state <NUM> from the start state <NUM>).

It is the objective to maximize the rewards (for task completion) in expectation for randomly sampled MDPs m with uniformly sampled start and goal states: <MAT>.

The continuous low-level state space <IMG> is split into an external part <MAT> that describes the agent (e.g. robot <NUM>) in its environment (e.g. agent position) and an internal part <MAT> that describes the internal state of the agent (e.g. joint angles of the robot <NUM>), with <MAT>, where ⊗ denotes the cartesian product. A surjective mapping z = fz(s) = fz(sext) transforms the continuous low-level state space <IMG> into a finite high-level state space <IMG>. Another mapping s̃ext = <IMG>(z) transforms high-level states back to reference external low-level states s̃ext. The high-level action space consists of a finite number of temporally extended options o ∈ <IMG> (which can be seen to correspond to subgoals). The ideal/intended outcome (next high-level state) of taking option o in high-level state z is denoted as z(z, o).

The agent perceives local feature observations ϕ(sext) based on its external state. For example, the robot <NUM> has sensors observing the robot's vicinity, e.g. the presence of obstacles <NUM> in its vicinity. In particular, for each coarse-scale (i.e. high-level) state z (robot position on the coarse grid) there may be a feature observation ϕ (<IMG>(z)) which may for example include information for each tile of a part of the coarse grid <NUM> around the robot <NUM> (e.g. in a 3x3 section of the coarse grid <NUM> with the robot at its centre). This may for example include information about the presence of obstacles in the respective coarse-grid tile, the type of tile (e.g. rough terrain, smooth terrain). A feature observation may also include other information of a coarse-scale state such as speed and orientation of the robot <NUM>.

The option-dependent low-level policy denotes <MAT> with τ(o, sext) being the option-dependent target vector from the current external state to the sub-goal: τ(o, sext) = <IMG>(z(<IMG>(sext), o)) - sext.

The initiation set denotes <IMG> = <IMG>; any option can be selected everywhere.

The option-dependent (sub-goal) reward function for the low-level reinforcement learning policy denotes <MAT> with <MAT> being the agent state when option o was selected.

The low level-reinforcement learning policy πθ is trained using the sub-episodes that arise within the training episodes of horizon T from repeated option activation and termination. Therefore, the execution of an option o has a variable maximum time horizon To = T - to that depends on the time step to at which the option was activated.

Value iteration iteratively refines an estimate of the state value function V or the state-action value function Q. Let Vk be the state value function of the kth iteration and let Qk be the state-action value function Q of the kth iteration. These can be defined recursively. The value iteration starts with an arbitrary function (which can be seen as an initial guess) V<NUM>. Value iteration uses the following equations to get the functions for k+<NUM> <MAT> <MAT>.

P(s'ls, a) represents the transition dynamics to reach a next state s' from current states given the action a.

When the high-level states z = <IMG>(s) that correspond to the states s of a rollout of the low-level policy πθ are considered, it can be observed that the high-level states follow the transition dynamics <MAT> that depend on the low-level policy πθ. A parametric model p̂ψ with parameters ψ, which models these transition dynamics sufficiently well, is learned from data. In order to generalize across the MDPs within the distribution <IMG>, the model is learned with respect to the feature observations corresponding to the high-level states: p̂ψ(ϕ (<IMG>(z')) |ϕ (<IMG>(z)) , o, πθ).

The high-level planner runs value iteration to obtain the value map <IMG>(z). Options, which implicitly define sub-goals for the lower-level reinforcement learning, are greedily selected by the policy over options <MAT>.

As a result, the reward maximization in the objective is with respect to the parameters of the low-level reinforcement learning policy θ and the parameters of (the learned high-level transition dynamics model for the) the high-level (value iteration) planner ψ:
<MAT>.

According to various embodiments, the controller <NUM> applies a hierarchical planning-guided RL control policy that comprises a high-level (coarse-scale) value iteration planner and a low-level (fine-scale) policy trained via reinforcement learning.

The high-level value iteration planner carriers out value iteration planning in a coarse state space abstraction (high-level state space). Sub-goals for the low-level reinforcement learning are generated by selecting high-level actions (options) based on the generated (high-level) value map. The high-level planning maintains a transition probability model for the coarse-scale state space. This model may be of specific architecture as follows.

<FIG> shows a neural network <NUM> for predicting high-level states.

The neural network <NUM> implements a classifier that predicts the next high-level state by selecting one of the (fixed amount of) neighboring high-level states provided, as input <NUM>, the current high-level state (in terms of a feature observation for the current high-level state) and the selected option (from which the sub-goal for the low-level reinforcement learning is derived). The neural network <NUM> includes a plurality of hidden layers <NUM> followed by a softmax layer <NUM>. The softmax probabilities <NUM> of the classifier are used as transition probabilities <NUM> to all possible neighboring high-level states and are used to determine the neural network's output <NUM>.

The low-level RL module includes the control policy that interacts with the environment and is rewarded for achieving the sub-goals set by the high-level planning. It may be trained by a reinforcement learning algorithm of choice, e.g. Q-learning, Deep Q-learning (DQN), Trust Region Policy Optimization (TRPO), Proximal Policy Optimization (PPO), Deep Deterministic Policy Gradient (DDPG), Twin Delayed DDPG (TD3), (Asynchronous) Advantage Actor Critic (A2C/A3C), etc..

The hierarchical policy is trained for several training iterations until a maximum number of training iterations is reached or it meets a pre-defined quality criterion with respect to the objective function. In every iteration:.

Once the hierarchical policy is trained, the controller <NUM> performs the following during deployment:.

In summary, according to various embodiments, a method for controlling a robot is provided as illustrated in <FIG>.

<FIG> shows a flow diagram <NUM> illustrating a method for controlling a robot.

In <NUM>, an indication of a target configuration to be reached from an initial configuration of the robot is received.

In <NUM>, a coarse-scale value map is determined by value iteration, wherein the transition probabilities are determined using a transition probability model mapping coarse-scale states and coarse-scale actions to transition probabilities for coarse-scale states.

In <NUM>, for each coarse-scale state of a sequence of coarse-scale states of the robot, starting from an initial coarse-scale state determined from the initial configuration of the robot and until the robot reaches the target configuration or a maximum number of fine-scale states has been reached, a fine-scale sub-goal from the coarse-scale value map is determined in <NUM>. The fine-scale sub-goal may correspond to a coarse-scale action, e.g. may be a reference fine-scale state for a coarse-scale state (e.g. the coarse-scale state's center in fine-scale coordinates) to be reached the the coarse-scale action.

In <NUM>, by an actuator of the robot, fine-scale control actions are performed to reach the determined fine-scale sub-goal and sensor data are obtained to determine the fine-scale states reached as a result of performing the fine-scale control actions for each fine-scale state of the resulting sequence of fine-scale states of the robot, starting from a current fine-scale state (e.g. an initial fine-scale state of the current coarse-scale state) of the robot and until the robot reaches the determined fine-scale sub-goal, the robot transitions to a different coarse-scale state, or a maximum sequence length of the sequence of fine-scale states has been reached.

In <NUM>, the next coarse-scale state of the sequence of coarse-scale states is determined from the last fine-scale state of the sequence of fine-scale states is determined.

According to various embodiments, in other words, robot control is split into (at least) two hierarchy levels, wherein the lower level performs fine-scale control given by a (fine-scale) control policy (trained via reinforcement learning such as Q-learning, Deep Q-learning (DQN), Trust Region Policy Optimization (TRPO), Proximal Policy Optimization (PPO), Deep Deterministic Policy Gradient (DDPG), Twin Delayed DDPG (TD3), (Asynchronous) Advantage Actor Critic (A2C/A3C)) and the higher level, also referred to as planner, performs value iteration. Value iteration can be seen as iterative application of the Bellman equation to generate a value map. The transition probabilities for the value iteration are given by a transition probability model which, according to various embodiments, is trainable by supervised learning, e.g. represented by a neural network. The parameters of the neural network (e.g. the weights), denoted by ψ in the examples above, can be seen as parameters of the planner.

For example, a control signal is determined based on the potentially pre-processed sensory input using the learned (hierarchical) control policy. The high-level planner generates (sub-goal) targets based on the provided coarse environment representation (e.g. map). The low-level control module operating according to the low-level control policy calculates the control signals (for performing the low-level control actions) given these targets and the potentially pre-processed sensory input.

In case of vehicles (e.g. cars) or mobile robots, the coarse environment representation for the high level planner is for example a map (indicating obstacles) that is tiled such that a finite number of cells result, which are the potential sub-goals. The target vectors (i.e. the sub-goals) are for example the difference between the position of the center of the chosen cell and the current vehicle position. The low-level control module operating according to the low-level control policy receives this target vector along with the current potentially pre-processed sensory readings.

In case of a robotic task, the high-level planner may receive some sort of symbolic representation of the task (e.g. known subtasks that need to be fulfilled: mount a screw, move an object,. ) as coarse environment representation. It then generates a plan that sequences these sub-tasks (or maybe positional offset vectors for certain objects) which are the targets, i.e. the sub-goals, for the low-level policy.

The method of <FIG> as well as a method for training a robot controller to perform this method may be performed by one or more computers including one or more data processing units. The term "data processing unit" can be understood as any type of entity that allows the processing of data or signals. For example, the data or signals may be treated according to at least one (i.e., one or more than one) specific function performed by the data processing unit. A data processing unit may include an analogue circuit, a digital circuit, a composite signal circuit, a logic circuit, a microprocessor, a micro controller, a central processing unit (CPU), a graphics processing unit (GPU), a digital signal processor (DSP), a programmable gate array (FPGA) integrated circuit or any combination thereof or be formed from it. Any other way of implementing the respective functions, which will be described in more detail below, may also be understood as data processing unit or logic circuitry. It will be understood that one or more of the method steps described in detail herein may be executed (e.g., implemented) by a data processing unit through one or more specific functions performed by the data processing unit.

The term "robot" can be understood to refer to any physical system (with a mechanical part whose movement is controlled), such as a computer-controlled machine, a vehicle, a household appliance, a power tool, a manufacturing machine, a personal assistant or an access control system.

Claim 1:
A method for controlling a robot (<NUM>) comprising:
Receiving an indication of a target configuration (<NUM>) to be reached from an initial configuration (<NUM>) of the robot (<NUM>);
Determining a coarse-scale value map, which assigns values to each state of a coarse representation of an environment in which the robot is located, by a value iteration planner by iteratively refining estimates of values of the states of the coarse representation, wherein transition probabilities are determined using a transition probability model (<NUM>) mapping coarse-scale states and coarse-scale actions to transition probabilities for coarse-scale states; and
For each coarse-scale state of a sequence of coarse-scale states of the robot (<NUM>) in the coarse representation of the environment, wherein the sequence starts from an initial coarse-scale state determined from the initial configuration (<NUM>) of the robot (<NUM>) and ends when the robot (<NUM>) reaches the target configuration (<NUM>) or a maximum number of fine-scale states of a fine representation of the environment has been reached,
Determining a fine-scale sub-goal from the coarse-scale value map by selecting a coarse-scale action based on the value map, wherein the coarse-scale action is greedily selected by a fine-scale control policy;
Performing, by an actuator of the robot (<NUM>), fine-scale control actions according to the fine-scale control policy trained via reinforcement learning to reach the determined fine-scale sub-goal and obtaining sensor data to determine fine-scale states reached by the robot in the fine representation of the environment as a result of performing the fine-scale control actions for each fine-scale state of a resulting sequence of fine-scale states of the robot (<NUM>) in the fine representation of the environment, wherein the sequence starts from a current fine-scale state of the robot (<NUM>) in the fine representation of the environment which the robot has within the coarse-scale state and ends with a last fine-scale state when the robot (<NUM>) reaches the determined fine-scale sub-goal, the robot (<NUM>) transitions to a different coarse-scale state, or a maximum sequence length of the sequence of fine-scale states has been reached;
Determining the next coarse-scale state of the sequence of coarse-scale states from the last fine-scale state of the sequence of fine-scale states.