Olga Kozlova
email: olga.kozlova@isir.upmc.fr

Olivier Sigaud
email: olivier.sigaud@upmc.fr

Christophe Meyer
email: christophe.meyer@thalesgroup.com

Texdyna: hierarchical reinforcement learning in factored mdps

Introduction

One central issue in animat research consists in facing the complexity of the real world with adaptive methods. Among such adaptive methods, reinforcement learning (RL) is one of the most studied. However, due to the "curse of dimensionality" inherent to the Markov Decision Process (MDP) framework, standard RL algorithms cannot address large scale real world problems mostly because they must enumerate all states [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. In order to apply RL to robotics problems, two main lines of research can be followed. One consists in making profit of the structure of the sensory system of the robot using Factored MDPs (FMDPs), using a representation where a state is implicitly described by an assignment of values to some set of state variables. Then, one can exploit the dependencies between variables to get a compact representation [START_REF] Boutilier | Exploiting structure in policy construction[END_REF]. The second line of research consists in making profit of the structure of the decision problem itself, using Semi-MDPs (SMDPs), an extension of MDPs where the number of time steps between one decision and the next is a random variable. The SMDP framework is the basis for Hierarchical Reinforcement Learning (HRL) algorithms as it decomposes the original task into subtasks that are easier to solve individually [START_REF] Barto | Recent advances in hierarchical reinforcement learning[END_REF].

The methods to solve FMDPs and SMDPs usually assume that the structure of the problem is given, though that structure is rarely available in practice. As to hierarchical representations, HEXQ [START_REF] Hengst | Discovering hierarchy in reinforcement learning with HEXQ[END_REF] and VISA [START_REF] Jonsson | Causal graph based decomposition of factored MDPs[END_REF] are two algorithms designed to solve this problem. Besides, for FMDPs, [START_REF] Degris | Learning the structure of factored markov decision processes in reinforcement learning problems[END_REF] have proposed SDYNA to solve Factored Reinforcement Learning (FRL) problems. Here, we propose TeXDYNA, an algorithm that combines the benefits of HRL and FRL, building an HRL-augmented version of SDYNA.

The paper is organized as follows. First, in Section 2, we give the minimal background necessary to understand what follows. In Section 3, we present TeXDYNA, introducing the method for discovering options from the internal structure of the problem and showing how to introduce options into FRL algorithms. In Section 4, we present an experimental study of our system based on the LIGHT BOX problem. In Section 5, we discuss the contributions and limitations of our work as well as related work.

A quick index to the background

An FMDP is described by a set of state variables S = {X 1 , . . . , X n }, where each X i takes its value in a finite domain Dom(X i ). Structured Dynamic Programming (SDP) algorithms such as SVI [START_REF] Boutilier | Stochastic dynamic programming with factored representations[END_REF] make profit of this structure to compute a policy compactly. Structured-DYNA (SDYNA) [START_REF] Degris | Learning the structure of factored markov decision processes in reinforcement learning problems[END_REF] is a general framework that adapts indirect RL of the DYNA family [START_REF] Sutton | DYNA, an integrated architecture for learning, planning and reacting[END_REF] to the FMDP framework. SPITI is a particular instance of SDYNA based on a decision trees induction process to learn the structure of the problem and on SVI to obtain an efficient policy. While the FMDP representation technique reduces the size of the representation of state-action space of large problems by decomposing states into a set of random variables, the HMDP representation decomposes the overall state-action space into a set of smaller state-action spaces each of which can be factored. SMDPs are an extension to MDPs where the number of time steps between two decisions is a random variable. Among several other frameworks (see [START_REF] Barto | Recent advances in hierarchical reinforcement learning[END_REF] for an overview), the options framework [START_REF] Sutton | Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning[END_REF] is designed to solve SMDPs by building a hierarchy of options. An option is a tuple I, π, β , where I ⊆ S is an initiation set, that is a subset of states in which it is possible to execute o, π : S × O → [0, 1] is a policy executed in o, and β : S → [0, 1] is a termination condition function, that is the probability of terminating the option in each state. Options are a generalization of primitive actions including temporally extended courses of actions. As a result, the algorithms deal only with options and do not have to distinguish options from primitive actions. Previous algorithms combining FMDP representation and HMDP structure learning are HEXQ [START_REF] Hengst | Discovering hierarchy in reinforcement learning with HEXQ[END_REF] and VISA [START_REF] Jonsson | A causal approach to hierarchical decomposition in reinforcement learning[END_REF]. The work most closely related to ours, Incremental-VISA [START_REF] Vigorito | Autonomous Hierarchical Skill Acquisition in Factored MDPs[END_REF][START_REF] Vigorito | Hierarchical Representations of Behavior for Efficient Creative Search[END_REF] is discussed in Section 5.

TeXDYNA

TeXDYNA hierarchically decomposes an FMDP by automatically splitting it into a set of options. Meanwhile, the local policy of each option is incrementally improved by a SDYNA-like approach. The central contribution of this work comes from the fact that the discovery of options and the construction of the model of the FMDP, as well as policy computation, are simultaneous. To achieve simultaneous SMDP structure learning, FMDP structure learning as well as local and global policy computation, TeXDYNA is built on top of SPITI. There are two main advantages to our approach. First, we make profit of the learning method used in SDYNA to learn only a local model for each option. As a result, the models are smaller and, therefore, easier to learn. Second, introducing options in the planning stage results in the possibility to plan over smaller partitions of the state-action space. In order to decompose hierarchically the overall FMDP into sub-FMDPs represented by options, TeXDYNA builds a global transition function that represents the structure of the problem and uses this function to build a hierarchy of options. For each option, TeXDYNA computes a local transition function and a local policy. Therefore, TeXDYNA can be decomposed into two simultaneous processes: (1) Learning options: learning the transition function of the overall FMDP (updating the FMDP model with (s,a,s ,r)) and adding or updating options (Algorithm 1); (2) Planning with options: using a modified version of the SPITI algorithm for model learning, planning and acting with options, i.e. updating hierarchical policy π = π o0 , π o1 , ...π on , (Algorithm 2).

Defining options

The purpose of our approach is to decompose the overall FMDP into smaller subtasks or mutually independent stand-alone policies. Our representation takes advantage of the FMDP structure using temporal abstraction techniques. We use a specific options representation inspired from the goal-oriented exit options of VISA [START_REF] Jonsson | A causal approach to hierarchical decomposition in reinforcement learning[END_REF] and HEXQ [START_REF] Hengst | Discovering hierarchy in reinforcement learning with HEXQ[END_REF], where options are defined by their exit states that can be seen as subgoals of the task. Our options are noted o: o = I, π, e where I ⊆ S is an initiation set, π is a policy executed in o and e is the related exit. We do not use the usual termination function β since it is defined by the exit and computed at each time step during the option execution.

An exit corresponds to changes of values of state variables linked to the reward function, as in HEXQ. However, unlike HEXQ, where exits are state-action pairs, we define exits as a tuple v, a, v ch , c , where v is the variable whose value is changed by this exit, a is the exit action that makes the value of v change at the next state, v ch is a variable change, i.e. a pair of values x, x where x is the value before a is executed and x the value after a is executed. In the stochastic case, the variable change is a probability distribution over v ch and the highest probability is kept in the exit definition. Finally, c = {x 1 , ..., x n } is the context, that is the set of constraints (i.e. assignment of values to a subset of state variables) that makes this exit available. In this representation, the primitive actions have an empty context. Thus, there is at most one exit per action and per variable change. Thus, each option corresponds to a unique exit.

The initiation set I o of option o defines the state space where this option can be executed. On the one hand, it determines if the resources necessary for the successful execution of the option are available, and, on the other hand, it specifies the state space from where the exit of the option is reachable. In practice, it is the union of its own exit context and all the exit contexts of its sub-options. If a sub-option is a primitive action, its exit variable is added to I o with all possible values. Otherwise, the exit variable of the sub-option is added with its value change. By convention, a sub-option with an empty initiation set is admissible everywhere. This is particularly true for primitive actions. Therefore, all the values of the corresponding exit variables of these options are accepted. Thus, I o contains all the states from which the exit of the option is reachable. This property of direct reachability is ensured by the fact that the exit context copies the constraints of the corresponding branch in the transition tree. In other words, the nodes of the branch represent the variables of the context. When those variables can be changed by a sub-option, the exit of the parent option becomes reachable from all the states where its sub-options are accessible.

The hierarchical structure of the options set is determined by the variables interdependencies expressed in the structure of the transition function. However, for the sake of sound planning, a rank is assigned to each option as the highest rank of its suboptions plus one. As a result, the planning algorithm chooses an option to execute at each abstraction level in the hierarchy by going down from the most abstract options to primitive actions. Transition model learning and options discovery are simultaneous. Thus the options discovered first represent the transitions learned first and consequently have less constraints as they represent the most accessible subgoals. If the problem has a hierarchical structure, this gives a bottom-up direction to the options discovery. First the options with the lowest abstraction level are discovered, then their execution gives access to more constrained options. Defined this way, each option represents a sub-FMDP M o = S o , O o , Ψ, T o , R o containing a reduced partition of the initial stateaction space, where S o is a set of context variables, O o is a set of sub-options, Ψ is a set of admissible state-option pairs defined by the initiation set, T o is the local transition function and R o is the local reward function. In this respect, when an option is created, we initialize its local FMDP tree structure composed of the transition trees for its context variables, as well as a local planning algorithm. Thus, when learning the internal FMDP structure of the option, the states injected in the learning algorithm are reduced to contain only variables x i such that ∀i, x i ∈ X o .

Learning: Adding and updating options

To discover options, the overall task transition function is learned in a decision tree form. The FMDP model provides the structure used for the options discovery process, as this structure represents the dependencies between variables and constraints under which those variables change their values.

Algorithm 1 describes the procedure for adding or updating options. An option is introduced each time there is an action that can change one variable value. The suboptions are the options available in the sub-FMDP represented by the corresponding parent option. Sub-options are added in the following way: for each variable in the context of the parent option, if the set of options E contains an option that modifies the value of this variable, this option is added to the set of sub-options. Note that, when computing the context of an exit, the exit variables are excluded from the context to avoid cross-dependencies between options. This procedure supposes that there is one option per variable change and that each option changes at most one variable value. For instance, if some options change more than one variable, then one variable can be changed by more than one option. As a consequence, these options would be suboptions of one another, creating loops in the hierarchy. Nevertheless, this constraint can be relaxed by reorganizing the hierarchy once the options have been added. The procedure is the following: if a cross-dependency is detected between two options, the hierarchical link between them is removed and both options are attributed the lowest rank of the two. This way, more than one option may have the same exit variable.

The options are defined over the model of the problem while this model is learned. Thus some are incomplete or erroneous, especially in the first stages of the learning As to incrementality, [START_REF] Degris | Learning the structure of factored markov decision processes in reinforcement learning problems[END_REF] proposes to re-initialize the value function each time the reward function changes, mainly because the structure of the value function results from the reward function. In the incremental options learning case, the value function tree is reset each time the reward function changes in order to take into account every modification that changes the structure of the policy. There are exactly as many options as possible variable value changes. Thus there is no need to remove incorrect options given that as soon as their context is correct, they become accurate. Meanwhile, however, inaccurate options can influence planning and exploration by building an erroneous policy (see the next section).

Planning: FRL over options

The planning stage builds a hierarchical policy over options by incrementally improving and modifying it simultaneously with the learning process. The planning algorithm, built upon the ideas coming from HRL algorithms and FRL methods based on SPITI, is given in Algorithm 2. To operate with options and take into account the hierarchical structure of the policy, we use a modified instance of SPITI for model learning, planning and acting with options. The algorithm executes options recursively by going down the hierarchy of options up to primitive actions that can be executed by the agent in its environment, then performs the updates by going up in the hierarchy. This upward update guarantees that the model of transitions includes the changes that occur during the incremental learning process. Thus, local planning is performed for each option with respect to the current structure of its local model of the transition and reward functions. The inner loop of SPITI is decomposed into three stages:

-Acting: choose an action using -greedy exploration; -Learning: update the model of the transition and reward functions of the FMDP from X, a, X , R observations using ITI; -Planning: update T ree(V ) and T ree(π) using one sweep of SVI.

Then, in the learning stage, the ITI algorithm is modified to work with options by replacing primitive actions by options in trees and allowing to remove or add new transition trees while learning. Moreover, ITI uses reduced states representations containing only variables present in the context of the option, so that the local model is updated with observations S o , a, S o , R where S o is a set of local context variables.

Finally, in the planning stage, the adaptation of SDP algorithms like SVI to the options framework is straightforward. Since the action space is restricted by the number of sub-options available on a given hierarchical level, the algorithm has an additional argument that specifies the list of options to iterate through.

The primitive actions available in the environment are all initialized as options with empty exit context and initiation set. TeXDYNA builds the hierarchical policy π = π o0 , π o1 , ...π on , where a higher level policy is based on a set of lower level policies. Each option follows the policy of its FMDP, its sub-options follow their respective policies and so on. Moreover, to propagate the external rewards to the local policies of options, when a high level option is discovered, an additional reward, named "internal reward" r o (by contrast with the external reward received from the environment) is assigned to its exit action. We set r o = Ro 2 , where R o is the internal reward of the parent option. For the options on the top level of the hierarchy, R o is the maximal immediate external reward that the agent can get. This heuristics is inspired by the "salient event" heuristics introduced in [START_REF] Singh | Intrinsically motivated reinforcement learning[END_REF].

As mentioned above, in the first iterations, the hierarchy of options and often options themselves are inaccurate or irrelevant. This is why the procedure to choose options (Algorithm 3) must take inaccuracies into account and use a strategy that favors exploration in the first steps and chooses the options at the right level of the hierarchy. The root node of the option hierarchy represents the overall FMDP. The first option o is chosen according to the root policy while its initiation set contains the current state s. The sub-options are selected according to the internal policy π o of the option o augmented with an -greedy exploration policy. If the policy is incomplete and does not contain any information about options available in a current state, then an option is chosen randomly from the options set E on the current rank level with respect to its initiation set. If no option is available with a given rank, the algorithm chooses from options with lower rank and so forth. Thus, in the first stages of learning, only the options with rank 0 are available, that is primitive actions chosen randomly and in the end the preference always goes to the options with the higher level of abstraction. This provides a high level of exploration at the beginning and then for unexplored parts of the state space, therefore this speeds up the overall learning process.

In order to avoid an option from being stuck within an erroneous policy that fails to achieve its exit, we introduce the notion of selection penalty that forbids one option for a given number of time steps. In practical terms, when an option reaches its exit state but fails to change the corresponding variable value, that means that its structure is inaccurate. In this case we forbid this option selection for (max time steps per episode) 10 time steps in order to let the model of transitions of its parent option be improved. Here, we have chosen to evaluate TeXDYNA on the LIGHT BOX domain [START_REF] Vigorito | Autonomous Hierarchical Skill Acquisition in Factored MDPs[END_REF], presented in Fig. 1. It consists of a set of twenty "lights", each of which is a binary variable corresponding to ON and OFF, named "0", "1", "2", etc. Each light has a corresponding action that toggles the light ON or OFF. Thus there are twenty actions, 2 20 ≈ 1 million states, thus approximately 20 million state-action pairs. The 9 white lights are simple toggle lights that can be turned ON or OFF by executing the 9 corresponding actions. The green lights are toggled similarly, but only if certain configurations of white lights are ON, with each green light having a different set of dependencies. Similarly, the blue lights depend on certain configurations of green lights being ON, and the red light depends on configurations of the blue lights. The goal is to turn the red light on, in which case the agent receives a reward of 20.

The results presented below are averaged over 20 runs of 150 episodes where each episode is limited to 300 steps. The curves are smoothed by computing the moving average weighted over ten neighboring values. The algorithms use the following parameters: N = 300 in DYNA-Q and = 0.1 in -greedy. The ITI algorithm uses χ 2 = 30 in stochastic problems and χ 2 = 0 in deterministic ones. The algorithms are coded in C# and run on Intel Core2Duo 1.80GHz processor with 2Go RAM.

An example of hierarchy of options obtained on the LIGHT BOX problem is given in Fig. 2. The complete state representation in the LIGHT BOX problem is given by 20 variables corresponding to 20 lights, but the states used to update the internal structure of the FMDP corresponding to the option toggle16 contains only 2 variables "10" and Fig. 3 shows the performance in number of time steps required to complete one episode of the LIGHT BOX problem within three experimental contexts: random policy, TeXDYNA and DYNA-Q applied to both the deterministic version of the LIGHT BOX problem and a stochastic version where the agent performs random actions with a 10% probability. We could not obtain the convergence curve for SPITI because SPITI attempts to build the complete value tree representing all possible combinations that is 1 million leaves. This assertion is explained by the results presented in Table 1 that recaps the average time in seconds per step and the size of the functions in the stochastic LIGHT BOX problem. TeXDYNA requires less time to perform one step since it works on a smaller representation. While SPITI is struggling to check if the red light is dependent on the white light, the policy built by TeXDYNA goes straight to the goal state by achieving subgoals one by one at each level. The algorithm finds the same structure in the stochastic case as in the deterministic one. One can notice that it takes more time to the algorithm to learn a stochastic transition function, but in the end it discovers the same hierarchy of options and the same policy and value functions. Similarly, stochastic DYNA-Q needs more episodes than its deterministic counterpart to converge. Furthermore, as shown in Table 1, TeXDYNA builds much smaller representations than its competitors in the stochastic case.

In order to explain the lesser performance of SPITI compared to TeXDYNA, we record the policy function size for SPITI and TeXDYNA, and the number of state-action pairs in DYNA, at the end of each episode. Fig. 3(b) shows the evolution of the corresponding functions size over episodes. TeXDYNA quickly reaches a plateau on its optimal policy size, while the policy discovered by DYNA continues to grow up until representing all possible states. Therefore, DYNA results given in Fig. 3(a) are biased by the fact that even if it discovered a kind of sub-optimal policy in a reasonable time, the algorithm is unable to perform the complete policy computation. As to SPITI, the system fails to achieve convergence because of a too strong memory requirement. Indeed, as soon as one tree size exceeds 15000 nodes, the system runs out of memory. Further code optimization might reduce this limitation, but the main point is that exponential task structure simplification allows TeXDYNA to scales much better. Indeed, local models combined with state reduction to the set of context variables ignoring anything else provides a significant state-action space reduction within the structure of each option.

Discussion

TeXDYNA ideas are first inspired by Sutton's DYNA architecture [START_REF] Sutton | DYNA, an integrated architecture for learning, planning and reacting[END_REF], enriched and adapted to FMDPs by [START_REF] Degris | Learning the structure of factored markov decision processes in reinforcement learning problems[END_REF]. Second, as to the exit oriented options representation, some ideas come from the HEXQ [START_REF] Hengst | Discovering hierarchy in reinforcement learning with HEXQ[END_REF] and VISA [START_REF] Jonsson | A causal approach to hierarchical decomposition in reinforcement learning[END_REF][START_REF] Jonsson | Causal graph based decomposition of factored MDPs[END_REF] frameworks, where the exit definition proposed in HEXQ is extended to include variable change and context in order to address more complex structures. TeXDYNA builds a hierarchy of options online and directly from the transition trees taking advantage of their structure, whereas VISA builds a variable influence graph from the given DBNs and then builds transition graphs and reachability trees to determine the initiation sets of the options. Furthermore, it only discovers options linked to the variables directly connected to reward, while TeXDYNA backpropagates the reward among subgoals.

Finally, Incremental-VISA [START_REF] Vigorito | Autonomous Hierarchical Skill Acquisition in Factored MDPs[END_REF][START_REF] Vigorito | Hierarchical Representations of Behavior for Efficient Creative Search[END_REF] is adapting VISA to the case where the model of the problem is not known in advance. Like TeXDYNA, it attempts to simultaneously learn the hierarchical (options discovery) and factored (DBN learning) structure of the MDP. The approach learns incrementally and autonomously both the causal structure of the environment and useful skills that exploit this structure. It uses DBN structure learning techniques to learn the environment structure and SDP algorithms like SVI to build hierarchical policies online. The authors propose an active learning scheme to improve the efficiency with which this structure is acquired that bootstraps on existing structural and procedural knowledge. As new structure is discovered, more complex skills are learned, which in turn allow the agent to discover more structure, and so on. The major differences between TeXDYNA and Incremental-VISA is, for the moment, that the latter is limited to the deterministic case, whereas TeXDYNA is adapted to stochastic problems. The second difference lies in the way of introducing options into planning: Incremental-VISA waits the option to be "mature enough" before introducing it in the hierarchy by using a measure of entropy on the transition functions whereas TeXDYNA inserts options directly in the hierarchy in order to accelerate its completion. In the same way as VISA, Incremental-VISA uses the DBNs to discover dependencies between state variables. Therefore, it needs to build intermediate graphs and trees to catch the internal hierarchical structure, while TeXDYNA operates on decision trees and discovers the structural links directly. Unfortunately, we were not able to compare the performance mainly because of the absence of a common metrics. Indeed, the experimental results published in [START_REF] Vigorito | Hierarchical Representations of Behavior for Efficient Creative Search[END_REF][START_REF] Vigorito | Autonomous Hierarchical Skill Acquisition in Factored MDPs[END_REF] are based on the number of value changes and the time to compute the policy without giving the corresponding metrics criteria.

At this point in time, the algorithm presents some limitations. Firstly, instead of using "internal reward" to propagate the external reward to local policies so that all options have fixed interest, the options discovery algorithm could be combined with taskspecific knowledge to identify useful, salient or challenging subroutines. Secondly, we consider that there is at most one option per variable value change. This assumption simplifies computations within the algorithms, but can be relaxed. More importantly, as to the problem representation, our option-specific state abstraction is strongly goaloriented, that is reaching a unique exit context. This can result in the creation of excessive number of options in problems where an action can change more than one variable at the same time. Finally, the hierarchy of options is strictly ordered, that means that we cannot address problems where the FMDP structure includes synchronic arcs or postaction variable dependencies, because it would introduce cross-dependencies between options and cycles in the hierarchy of options.

Conclusion

We have presented TeXDYNA, a powerful framework that combines factored and hierarchical reinforcement learning. This framework is built on three main ideas:

-The use of the transition function structure represented as decision trees to discover options results in efficient learning and planning capabilities that are integrated into the (factored) model-based RL framework. -The localization of the models results in an exponential reduction of the state-action space of each option. Instead of taking transition trees from the global structure, the models of transitions are learned locally for each option. This accelerates the solution process. -The immediate use of the just discovered options in the planning process speeds up the learning of its internal structure and of its parent option structure.

We have evaluated on the LIGHT BOX problem the capability of TeXDYNA to efficiently generate hierarchical policies and shown that it performs better than its non factored and non hierarchical ancestors. The main issue for future work consists in replacing the basic -greedy exploration strategy by a more sophisticated policy, either along the "optimism in the face of uncertainty" line [START_REF] Szita | The many faces of optimism: a unifying approach[END_REF] or based on adding internal motivations such as an artificial curiosity process [START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF][START_REF] Singh | Intrinsically motivated reinforcement learning[END_REF] into the framework. Then the application of TeXDYNA to a robotics problem will be the matter of a more experimental work.

Algorithm 1 : 2 forall 3 if 4 if 6 • 7 • 8 • 9 •

 12346789 Add and update options init : options set E = ∅ input: FMDP F = [∀xi ∈ X : T ree(P (x |x))] 1 forall transition tree T ree(P (x |x)) ∈ F do 1 leaf l of the T ree(P (x |x)) do 2 branch contains an action a & a modifies the value of the variable x in leaf l 3 then if E does not contain a definition of option o with the exit corresponding to 4 variable x and action a then 5 introduce new option o defined by exit e : v, a, v ch , c with : 5 variable v ← x 6 action a ← current action a 7 variable change v ch ← value in the branch, value in the leaf 8 context c ← variables of the branch that leads to the leaf l 9 10 else if E contains a partial definition of o then 10 11 update o with new information 11 process. To ensure the relevance of discovered options, they are updated every time the model of transitions changes. The algorithm checks if the set of options E already contains an option defined by the same action and variable, but with a different context definition. If so, it updates it (line 10 in Algorithm 1) using the following procedure: 1. Update the exit context c of the option; 2. Update the transitions trees (add missing ones and discard irrelevant ones); 3. Update the sub-options list (add missing ones and discard irrelevant ones); 4. Re-compute the rank k of the option; 5. Re-compute the Initiation set I o .

Algorithm 3 :1

 3 Choose Option input: current state s, policy T ree(π), hierarchy of options E, level k Get option o from to the current policy, o = maxo[leaf (T ree(π)|s)] 2 if o is null then choose option o from E accessible in the current state s with current rank k 3 while o is null do choose option o from E accessible in the current state s with rank k -1 (if k = 0 choose random primitive action) return o

Fig. 1 .

 1 Fig. 1. (a) The LIGHT BOX problem: number and color of "lights" with their dependencies. (b) Internal dependencies of the LIGHT BOX problem.

Fig. 2 .

 2 Fig. 2. Example of options discovered in the LIGHT BOX problem.

Fig. 3 .

 3 Fig. 3. (a) Convergence over episodes on the LIGHT BOX problem. (b) Policy size on the LIGHT BOX problem.

  Algorithm 2: SPITI with options input : FMDP F, hierarchy of options E

	for each time step t
	1 if no option is running then
		option o ←ChooseOption(s, T ree(π), E)
	2 if terminal condition of o is satisfied then
	2.1	execute exit action a; observe next state s and immediate reward r
	2.2.a	update local FMDP Fo with (s,a,s ,r)
	2.2.b	update parent FMDP F parent(o) with (s,o,s ,r)
	2.3.a	update local policy πo with Fo
	2.3.b	update parent policy π parent(o) with F parent(o)
	3 else
		sub-option i ←ChooseOption(s, T ree(πo), E)
		if sub-option i is primitive action then
	3.1	execute i; observe s and r
	3.2	update local FMDP Fo with (s,i,s ,r)
	3.3	update local policy πo with Fo
	3.4	return: i

4 else

call SPITI over sub-option i : i →SPITI (Fi, E)

Table 1 .

 1 Performance on the stochastic LIGHT BOX problem (Policy and value function size in total number of nodes in decision trees).

		TeXDYNA SPITI	DYNA-Q
	Transition function size 780 ± 14 790 ± 25 -
	Value function size	240 ± 20 > 15000 > 10000
	Policy function size	180 ± 8 > 15000 > 10000
	Time/step(sec)	0.04	> 100	> 2

This work was founded by CIFRE convention -1032/2006


Lionel Rigoux
email: lionel.rigoux@laposte.net

Olivier Sigaud
email: olivier.sigaud@lip6.fr

Learning postures through sensorimotor training: a human simulation case study Belonia Gabalda

In this paper, we present a case study showing why the modeling effort of computational neuro-sciences must call upon interactions with an environment when developmental phenomena are investigated. More specifically, in the context of a model of the spatial organization of a repertoire of postures, we show that calling upon a realistic simulation of the human kinematics (i) results in raising the question of the nature of information encoded in this repertoire ; and (ii) reveals that some previous assumptions about the functional organization of this repertoire were not necessary. Finally, we point out that conversely, robotics can benefit from such studies by using the suggested principles to design more adaptive control architectures.

Introduction

Given the complexity of tasks that humans and animals can address in contrast to the limited cognitive and motor capabilities of robots, an emerging line of research consists in building developmental and neuro-computational models of biological systems, with the hope to understand some underlying principles that may then be re-used to design robot control architectures. In particular, a way of understanding the principles of the generation of movement in the corresponding specific neural structures (some parts of the motor cortex, the cerebellum and basal ganglia) consists in building computational models implementing these principles and investigating their functional properties. But, in order to evaluate these models, we will exemplify in this paper the importance of embedding the neuro-computational model into a physical body or at least a realistic simulation, particularly when the model calls upon developmental processes. Indeed, we will show through a case study how taking into account the kinematics of the physical system can both reveal important questions ignored by models that did not simulate thiskinemat-ics and point out unnecessary assumptions made by these previous models.

More specifically, our starting point is Aflalo and Graziano's model (Aflalo and Graziano, 2006b), which addresses the emergence of a repertoire of motor primitives representing final arm postures corresponding to experimental observations. Indeed, Graziano and his team have observed through intracranial stimulations of the Macaque monkey that the hand reaches particular spatial configurations independently of its initial configuration when particular groups of neurons are stimulated (Graziano et al., 2002a[START_REF] Graziano | The cortical control of movement revisited[END_REF][START_REF] Graziano | Distribution of hand location in monkeys during spontaneous behavior[END_REF][START_REF] Graziano | Mapping from motor cortex to biceps and triceps altered by elbow angle[END_REF]. The stimulated area lies within the precentral gyrus. It contains parts of the primary motor cortex (M1), the caudal part of the dorsal premotor cortex (PMdc) and the ventral premotor cortex (areas F4 and F5 in the monkey), as shown in Figure 1. [START_REF] Graziano | Arm movements evoked by electrical stimulation in the motor cortex of monkeys[END_REF] Later on, through recording the neural activity in the monkey during free movement of superior limbs, (Aflalo and Graziano, 2006a) have shown that the relevant neurons were mainly, though non exclu-sively, tuned for the final posture in terms of articular angles. Other parameters previously considered as encoded in the premotor cortex, such as movement direction [START_REF] Georgopoulos | Neuronal population coding of movement direction[END_REF], speed, torques, hand position, seem less correlated to the variability observed in the neural firing rate.

In [START_REF] Graziano | Mapping from motor cortex to biceps and triceps altered by elbow angle[END_REF], the authors claim that groups of neurons involved in arm movement form a map of final hand positions, where the tuning of neurons reflects the behavioral repertoire of the animal. Finally, it is suggested in [START_REF] Graziano | Arm movements evoked by electrical stimulation in the motor cortex of monkeys[END_REF] that the organization of this map is not only based on the spatial position of the hand, but also on the somatotopy and the "ethological category" of the posture (i.e. the monkey "reaches", "eats", "climbs" etc.). Those three parameters would compete and the competition would result in a complex organization where all three representations overlap.

Aflalo and Graziano's model is based on a Kohonen map [START_REF] Kohonen | Self-Organizing Maps and Associative Memory[END_REF][START_REF] Kohonen | Self-Organizing Maps[END_REF]. Very shortly, Kohonen maps are a family of neural networks with self-organizational properties, where the activated cell is the one that matches some input the most closely. Training a map with a set of inputs composed of a vector of values results in the property that neighbor cells according to some lowdimensional topology get activated for similar data in the higher dimensional space of inputs.

In the case of Aflalo and Graziano's model, each input of the Kohonen map is a vector in three parts representing the limbs involved, the ethological category of the corresponding movement and the position of the hand. The first part is a binary vector of length 10 (one bit for each limb) where a 1 indicates that the corresponding limb is involved. The second part is a binary vector of length 5 that codes for the 5 possible categories (one bit for each ethological category). The third part is a real number vector of length 3 coding for the spatial coordinates of the hand in 3 dimensions.

Aflalo and Graziano initialize their Kohonen map with a simple somatotopic representation of the primary motor cortex drawn from [START_REF] Woolsey | Pattern of localization in precentral and supplementary motor areas and their relation to the concept of a premotor area[END_REF]. They show how training the map with a large set of handcrafted inputs results in a spatial organization similar to the one they observed on the surface of the cortex of the monkey by stimulating it. Nevertheless, the ad hoc encoding of information they used is questionable. In particular, one may wonder how the encoding of the ethological category of the movement could be so explicit in the neural system of the monkey.

Based on this work, (Ognibene et al., 2006a) have proposed another model of the constitution of a repertoire of postures. In (Ognibene et al., 2006b), they used a Kohonen map as well, but their model is trained in the context of a system learning to interact with its environment.

Our work shares some similarities with Ognibene et al.'s but, where their system only consists of a simple arm model with two degrees of freedom (dofs) in the context of a simple reaching task, we use a more complicated 24 dofs human-like system realizing a more complete repertoire of movements. Addressing this more complex system raises the issue of the most efficient encoding of the postural information within the Kohonen map. In particular, we compare an encoding based on articular parameters with an encoding based on spatial positions of the extremities of relevant body parts. More importantly, we show that, just by rewarding some postures in some contexts and combining a reinforcement learning process with a self-organizing process, we can obtain a topological organization of the map reflecting the ethological categories of movement that Aflalo and Graziano were giving explicitly to their system.

The paper is organized as follows. First, we present the global architecture and principles of our model. We describe how these principles are implemented and our experimental procedure in section 3. Results comparing the coding with angles to the coding with positions are described in section 4. We discuss these results and more general features of our model in section 5. Finally, we conclude and present some directions for future research.

Our computational model

Our model consists of three elements (see Figure 2):

• an environment specifying a sequence of contexts where our system must fulfil successive constraints on postures in order to get rewarded (see table 1) ;

• a human-like manikin simulation providing a realistic kinematics where one can check at any moment whether the current posture corresponds to a rewarded posture in a given context or not ;

• a control architecture based on a Kohonen map, which must be trained to code for the relevant rewarded postures.

Environment

Our model of the environment reflects very abstractly the situation of a monkey motivated by hunger in the presence of a fruit. The monkey must successively catch the fruit, manipulate it, bring it to its mouth and defend itself against an opponent (Figure 3 right). This simplified environment is directly inspired by [START_REF] Graziano | Arm movements evoked by electrical stimulation in the motor cortex of monkeys[END_REF] (see Figure 3 left). The constraints that a posture must fulfil to be rewarded are given in table 1.

Context

Goal of action Constraints on final posture (C1) fruit in range catch fruit dhb > 64cm (C2) fruit in hand manipulate fruit dhh < 16cm, dhb < 40cm, h in front of b (C3) fruit peeled eat fruit dhm < 14cm (C4) aggression defense dhh < 15cm, daa < 22cm, daf < 19cm 1) activates the marked neuron (1) which codes for the represented goal posture (2). Movement from the initial posture to the goal posture is shown at the bottom from left to right (3). The forth posture satisfies the context rewarding constraints, thus the link between C1 and the most active cell is reinforced (4). Finally, the Kohonen map is trained with this posture and a subsequent one towards the goal posture corresponding to C2 (5)

Simulated body: Arboris

We use a human manikin simulation named "Arboris" [START_REF] Collette | Etude et réalisation d'algorithmes de contrôle d'humains virtuels dynamiques[END_REF]. The poly-articulated model of the system contains 5 branches: the trunk, both legs and both arms (see Figure 4 left). The trunk is split into two bodies, arms and legs are split into three bodies. There are 36 dofs, expressed in articular parameters corresponding to angles. All bodies and articular limitations are defined according to anthropometric data adapted from the HuMAnS manikin documentation [START_REF] Wieber | The humans toolbox, a homogeneous framework for motion capture, analysis and simulation[END_REF]. We restrict the manikin to 24 dofs on the upper part of the model to avoid dealing with equilibrium constraints. The movement from one posture to another is obtained by a mere spline interpolation, imposing a bell-shaped velocity profile as observed in natural motion. The number N of intermediate postures between the initial and final null speed postures is a parameter of our system (here we take N = 5).

Posture representation

Like (Aflalo and Graziano, 2006b) and (Ognibene et al., 2006b), our encoding of a repertoire of postures is based on Kohonen maps [START_REF] Kohonen | Self-Organizing Maps and Associative Memory[END_REF][START_REF] Kohonen | Self-Organizing Maps[END_REF]. But our use of a complex virtual manikin highlights a problem that neither of these authors addressed. Indeed, building our model implies finding a good match between three languages: the specification of rewards associated to each context, the encoding of goal postures in the repertoire, and the encoding of the current posture in the manikin simulation.

The goal of the repertoire learning process is to ensure that Kohonen cells representing goal postures code as precisely as possible for rewarded postures of the manikin. Aflalo and Graziano did not face this question because their model does not call upon a simulation, and Ognibene's two-dimensional model being too simple, the transformation from angles to positions and vice-versa is trivial.

In our case, the movement of the manikin is defined by the articular parameters of the initial and final postures, thus coding postures with angles, as we do in a first model, seems the most appropriate. But representing rewarded postures is simpler with positions of body parts or cartesian distances between these parts than with angles. For instance, when the manikin must eat, the relevant feature is the relative position of one hand with respect to the mouth and specifying that with a chain of articular angles is complex. The underlying question is whether the brain codes for postures in a language adapted for controlling the body or adapted for specifying the goals, or even something else.

As a consequence, we designed a second model where the topology of the Kohonen map is based on positions rather than on angles. We extracted 24 coordinates corresponding to the spatial position of eight body parts: both shoulders, elbows, wrists and hand tips. These positions are expressed in a reference frame based on the eyes, as shown in Figure 4 right, so as to be able in future work to integrate visuomotor transformations in the context of a wider model calling upon a visual loop and a motor loop as suggested by [START_REF] Nakahara | Parallel cortico-basal ganglia mechanisms for acquisition and execution of visuomotor sequences[END_REF].

In order to implement this second model, we must transform a goal position defined with spatial coordinates into a goal posture defined with angles, which is necessary to control the manikin. In our context, we cannot directly use inverse kinematics solution schemes, since we specify the position of only a subset of body parts: there exists infinitely many corresponding angular configurations. (Ognibene et al., 2006b) solved this problem with a "direct inverse modeling" method by learning simultaneously two associations through a large set of 2D postures: first, the association between articular angles (outputs) and the activation of the Kohonen map and second, the association between a perceived position and the activation of the Kohonen map. The articular angles can then be retrieved by a mere activation of the map. However, what they did on a simple two-dimensional problem cannot be straightforwardly extended to our 24 dofs context. Thus we rather used a second Kohonen map, as shown in Figure 5. The second map codes for positions, and a cell in this map can be addressed from a cell of the map coding for angles through a direct geometric transformation computing the position from the angles. The neighborhood relationship is established in the map coding for positions. Then, during training, this relationship is "mapped" onto the map coding for angles through a 25 th variable coding for distances between postures expressed as a set of positions of body parts. Then, the map coding for angles is trained and the result is transferred again to the map coding in positions, so as to preserve the oneto-one correspondence. Through this process, we can both use our interpolation mechanism and constrain the modification of angles so as to ensure that articular limitations are not violated.

Model implementation and experimental design

We used an implementation of Kohonen maps available on internet1 . The cells of the Kohonen map in our model code for goal postures (noted P g ) of the manikin, which means that the vector of weights associated to each cell contains information about a posture (either with angles or with positions). These tion of an initial random posture (Figure 6, line 1), we present to the system the sequence of contexts (noted C) that appears in table 1, starting on the top line. The system must learn to reach the corresponding rewarded postures. Once the first rewarded posture is reached, the second context is presented and so on up to the fourth. If the system fails, a new iteration starts: a new random posture is selected and the system is reinitialized to the first context. We consider that the goal posture corresponding to a context is learned as soon as the system reaches it during 10 successive iterations. We perform N i = 1000 iterations of the algorithm in Figure 6 for each test.

Q(c,C k ) T )/(Σ j e Q(c j ,C k ) T ) (b) Pc(i + 1) ← interpolate(Pc(i), Pg) (c) if (Pc(i + 1) rewarded) • Q(Pc(i+1), C k ) = (1-α)Q(Pc(i+1), C k )+αR with R = 1 • train Kohonen map, (d) if ((Pc(i + 1) not rewarded) and (Pc(i + 1) = Pg)) Q(Pc(i + 1), C k ) = (1 -α)Q(Pc(i + 1), C k ) + αR with R = -0.3 4
We do not model context perception: a "context cell" is simply set to "on" in the corresponding context. In order to learn the correspondence between contexts and goal postures, we define a set of links (noted Q(c, C)) between each context cell and each cell in the Kohonen map. The active goal posture P g will tend to be the one whose link to the current context cell is the strongest, provided that we use some exploration. ere, our exploration mechanism is a classical Boltzmann law (Figure 6, line 3a) that explores all the more than the constant temperature T is higher and we take T = 0.03. All links are initialized to 0 at the beginning of a test.

Given an initial posture and a goal posture, the manikin control system will generate a sequence of current postures P c through a simple interpolation mechanism. If a current posture satisfies the constraints corresponding to the current context, the link Q(P c , C) is reinforced (Figure 6, line 3c). If the current posture is the goal posture and the posture is not rewarded, the link Q(P c , C) is weakened (Figure 6, line 3d).

Furthermore, a second learning process consists in training the Kohonen map so as to represent opti-mally the set of postures that are rewarded in a given context. The training data are the postures corresponding to the first rewarded posture in a given context and the first posture after the next change of context if this posture would have been rewarded in the previous context. This latter posture is added so as to drive the current goal posture towards the next goal posture when it is possible. For instance, when one manipulates before eating, it may be more efficient to manipulate with the hands as close to the mouth as possible. The system performs 15 standard training iterations for each of these postures.

Results

We studied the influence of the type of coding, either angles or positions, on the learning speed and resulting organization. Figures 7 and8 were obtained from the same initial map, but in the former we coded postures with angles whereas in the latter they were coded with positions. From these figures, one can see that there are already in the initial map a few cells (between 1 and 8 cells with a slightly different topology each time) that code for a rewarded posture in each context. And we noted that the convergence time is highly dependent upon this number of initial "correct" cells.

Our learning process results from the combination of two tightly coupled learning and self-organization processes. First, the system learns to bind to each context the cell representing an adequate goal posture in this context so as to drive the manikin towards this posture. Second, the Kohonen map is trained so that each goal cell codes as precisely as possible for the domain in which the corresponding postures are rewarded.

If we restricted the model to the first learning process, it would consist in finding through a random trial-and-error process that activating those initially adequate goal cells in adequate contexts results in receiving some reward. Then the link between the corresponding cell and context would be reinforced and this cell would get a higher probability of getting activated when the same context is presented again. Thus if there was no such cells coding for rewarded postures in the initial map, this first learning process would fail. This explains why the convergence time depends so much on the initial conditions.

The second learning process comes into play because, each time the current posture is rewarded, the Kohonen map is trained so that the active cell codes more centrally for this rewarded posture in the future (Figure 6, line 3c). In Figures 7 and8, one can observe that this self-organization process results in a global reduction of distances coded by neighbor cells and in the formation of clusters of goal cells that code adequately for rewarded postures. This is a key el- ement in our work: thanks to this second process, clusters corresponding to the ethological categories of Aflalo and Graziano's model are formed without giving explicitly these categories as inputs.

Globally, whatever the encoding used, our algorithm learns steadily to reach a sequence of rewarded postures that are not given explicitly to the system, but discovered through a trial-and-error process. On average over 40 runs, it takes 100 iterations to learn to reach steadily the next rewarded posture in the sequence once the previous one is already learned.

The location of the cluster of neurons corresponding to the "catching" context is different between Figures 7 and8. These figures were chosen to illustrate the fact that a cluster tend to be formed around the neurons coding initially for a rewarded posture. In the case of "catching", we can see that in the initial map two regions are relevant for this context, but with our learning algorithm only one region is trained per run. So in two different runs, this cluster can be at two different positions; but in the same run, even if two different occurrences of the same ethological posture are presented in the sequence, only one cluster is formed. By comparing these figures, one can also observe that this cluster formation process is slightly faster and clearer when postures are represented with articular parameters, though the difference in speed is not significant.

Discussion

While (Aflalo and Graziano, 2006b) were trying to reproduce the complex spatial organization of neurons coding for a repertoire of postures in the precentral gyrus of the monkey that they had observed through stimulation and recording, our standpoint was rather to look for general organizational principles that may explain the constitution of this repertoire through learning in interaction with an environment.

As a consequence, our work led us to question some of the methodological assumptions underlying Aflalo and Graziano's model. In particular, the organization they get in their Kohonen map directly results from an ad hoc encoding of the inputs of this map. In that respect, we have shown how one can obtain a spatial organization into clusters coding for relevant ethological categories without explicitly representing these categories in the inputs of the repertoire.

Furthermore, whereas in Aflalo and Graziano's model the cells of the Kohonen map only keep track of the position of one hand, the fact that we considered a complex representation of postures with 24 dofs led us to face the problem, biologically relevant, of the nature of information used to code for these postures.

Indeed, we observed that coding with articular parameters results in a clearer organization of clusters than with body parts positions. The distances between encoded goals outside of clusters is more uniform and this distance decreases faster, resulting in a faster cluster formation process in the former case. As a result, coding with angles seems more advantageous, since it is also computationally less expensive: it does not call upon the costly transformation from articular angles to positions and back.

These arguments in favor of coding with angles obtained in a simulation study must be reconsidered in the light of the neuro-physiological debate.

Indeed, some experimental studies inspired by the "target position hypothesis" [START_REF] Mcneilage | Motor control of serial ordering of speech[END_REF][START_REF] Russel | Spatial location cues and movement production[END_REF] clearly speak in favor of a "global" reference system expressed with positions (Georgopoulos et al., 1981, Baud-Bovy and[START_REF] Baud-Bovy | Pointing to kinesthetic targets in space[END_REF].

But other studies like [START_REF] Scott | Reaching movements with similar hand paths but different arm orientations: I. activity of individual cells in motor cortex[END_REF] or [START_REF] Rosenbaum | Remembered positions : Stored locations or stored postures?[END_REF] have shown that motor cortical neurons fire in function of initial and final angular postures of a movement. Thus it seems that both kinds of information are used in the brain. The kind of representation used may depend on the task, or there might be some redundant encoding in the motor system, as [START_REF] Haggard | Patterns of coordinated multi-joint movement[END_REF] and [START_REF] Kawato | Bidirectional theory approach to integration[END_REF] suggest. A control strategy based on this redundancy still awaits to be studied.

Another possibility would be that the postures are coded in a visual reference frame. There is an important body of literature about the different reference frames and transformations between them that are used in visuomotor control [START_REF] Brotchie | Head position signals used by parietal neurons to encode locations of visual stimuli[END_REF][START_REF] Pouget | Multisensory spatial representations in eyecentered coordinates for reaching[END_REF]. Taking this dimension into account would also open the possibility to distinguish two learning mechanisms, one in the visual system and one in the motor system [START_REF] Nakahara | Parallel cortico-basal ganglia mechanisms for acquisition and execution of visuomotor sequences[END_REF].

Conclusion and future work

In this paper, we have shown that using a simulation of a sophisticated human-like manikin may be necessary to design more accurate models of the neurophysiological processes that take place in the control of complex movements in humans and animals. First, such a choice revealed the importance of the nature of information encoded in the repertoire of postures that was not addressed by simpler models lacking this simulation dimension. Second, it was made possible to show that the assumption of an explicit encoding of the ethological category was not necessary to obtain the expected organization. Indeed, since the repertoire of postures obtained was resulting from the combination of a self-organization process and a reinforcement learning process involving interactions with an environment, a simulation of this interaction was necessary to observe the emergence of these ethological categories.

Thus we have shown how human-like simulations can contribute to modeling activities in life sciences. Conversely, our study illustrates how drawing inspiration from neuro-physiological studies to model developmental processes that take place in motor control can result in the design of efficient control architecture for virtual manikin and humanoid robots. Indeed, from the repertoire of postures that we obtained, one can design or learn complex sequences of simple actions that may result in the achievement of diverse robotics tasks.

Like Aflalo and Graziano's, our model was focused on learning a repertoire of postures. Even if our study is concerned with sensorimotor learning, here we did not address numerous aspects of the motor learning system such as the constitution of sequences of actions or motor adaptation.

In order to address biological relevance further, in the immediate future we have to replace the simple interpolation mechanism used in our model by a more accurate low level control law taking into account the dynamics of the system and some equilibrium constraints that must be satisfied to prevent the manikin from falling. In parallel, we are investigating the automatic learning of a dynamical model that may take place in the cerebellum.

Furthermore, the structure of the sequence of goals learned here is extremely simple, it is a mere succession of associations between a set of predefined contexts and constraints on postures. In order to address more general robotics tasks, we will have to focus in the future on a more accurate model of sequence learning and goal processing architecture, drawing inspiration from computational models of basal ganglia that try to elucidate the mechanisms of reinforcement learning and sequence formation. A true robotic implementation will then be necessary to qualify the robustness of the global architecture to sensors and actuators noise.

Figure 1 :

 1 Figure 1: The areas involved in the monkey's brain: primary motor area and subparts of the premotor area. The stimulated areas are in grey [from[START_REF] Graziano | Arm movements evoked by electrical stimulation in the motor cortex of monkeys[END_REF]

Table 1 :

 1 Figure 2: Model architecture: environment, Kohonen map and simulated manikin. Context C1 (see table1) activates the marked neuron (1) which codes for the represented goal posture (2). Movement from the initial posture to the goal posture is shown at the bottom from left to right (3). The forth posture satisfies the context rewarding constraints, thus the link between C1 and the most active cell is reinforced (4). Finally, the Kohonen map is trained with this posture and a subsequent one towards the goal posture corresponding to C2 (5)

Figure 3 :

 3 Figure 3: Left: categories of movement targets [from Aflalo and Graziano 2006]. Light blue: hand-to-mouth; dark blue:reach; red:protect oneself; green:manipulate; pink:climb. Right: equivalent in our simulation. Dark blue:catch; green:manipulate; light blue:eat; red:defense

Figure 5 :

 5 Figure 5: Second model architecture: one Kohonen map coding for spatial positions of body parts extremities is added with respect to Figure 2 and the correspondence between angles and positions is ensured (see text)

  maps of 16 × 24 = 384 cells (noted c) are initialized by training them with angles with 2 million random postures, taken in different order, which results in different maps. After initialization of the Kohonen map and selec-Parameters: {C 1 , ...Cn}, N (hereN = 5) 1. Pc(0) ← random posture 2. for k = 1 to n //index of current context 3. for i = 1 to N //index of current posture (a) Pg ← maxc (e

Figure 6 :

 6 Figure 6: The main algorithm (implemented in Matlab)

Figure 7 :

 7 Figure 7: Evolution of the repertoire of postures along iterations when postures are coded with articular parameters. First and third lines: average distances between the postures represented by neighbor neurons (dark blue = very close, red = very far). Second and fourth lines: cells coding for rewarded postures in different contexts are shown in color: dark blue: catch ; green: manipulate ; light blue: eat; red: protect oneself .

Figure 8 :

 8 Figure 8: Same information as in Figure 7, but cells code for body parts positions instead of articular parameters.

at http://www.cis.hut.fi/projects/somtoolbox

Acknowledgments

The authors thank Sébastien Barthelemy, Cyrille Collette and Alain Micaelli for providing Arboris.


Olivier Sigaud

Martin Butz2

Giovanni Pezzulo

Oliver Herbort

The anticipatory construction of reality as a central concern for psychology and robotics

Understanding and reproducing the organization of animal and human behavior has been one of the central problems in the life and engineering sciences throughout the centuries. It is still largely unresolved.

The life sciences approach consists in designing experiments that may reveal underlying principles of this organization in living systems. A key requirement for such experiments is that the interpretation of their results is unequivocal. The complexity of natural behavior is an obstacle to this requirement because the more complex the context and the behavior, the greater the number of potential interpretations of any set of results. Furthermore, in order to compare their favored principle with possible alternatives, researchers in sub-domains such as motor adaptation tend to all use the same experimental paradigms (for instance, planar reaching movement with one arm under a force field), generating cumulative data out of which they produce evolving interpretations. Consequently, they focus on extremely elementary phenomena, yielding a biased picture of more general aspects of the organization of behavior.

By contrast, the engineering approach to the organization of behavior is synthetic. It starts from principles whatever their origin, implements them on robotics platforms or simulators, and then evaluates the properties of the resulting systems. The purpose of engineering-oriented research is to produce functional systems. Consequently, the more elaborate the generated behavior, the better it is.

The principles that the life sciences researchers carefully extract from experimental data and that the engineers use for designing their systems are the meeting point between the two approaches. Nevertheless, synthetic systems still fall far short of living systems in their abilities to interact appropriately with their environment. Thus researchers in the engineering sciences hope to improve their systems by calling upon better principles revealed by research in the life sciences.

Reciprocally, experimental research in the life sciences benefits from the theoretical investigations of the principles led by engineering researchers and from demonstrations that the principles can generate the observed behavior in synthetic systems. The theories built in the engineering effort provide useful tools to conceptualize the results of life science experiments. An example of this process is the case of trial-and-error learning, which was first studied by experimental psychologists, then formalized by computer scientists as reinforcement learning algorithms, eventually leading to the discovery of neural processes that were consistent with the predictions of the theory (e.g., [START_REF] Schultz | A neural substrate of prediction and reward[END_REF]. [START_REF] Schack | Representation and learning in motor action -Bridges between experimental research and cognitive robotics[END_REF] stress the inadequacy of studying elementary behavioral phenomena in isolation. In order to transfer the corresponding concepts to robotics, one must rather frame them into more general theories and control architectures that cast additional constraints on them. Thus, an outstanding benefit of interactions between engineers and life scientists is that engineering goals push the life science research towards more integrative studies of complex behavioral phenomena.

Such interactions have been further promoted since the emergence of humanoid robotics. Given the complexity of controlling a humanoid robot so that it achieves most of the tasks a human being is capable of, it has become mandatory for engineers to call upon the principles of human motor control, learning, and decision making -to cite a few -that are studied by psychologists and neurosciences researchers. For the study of simple behavior, the connection between the engineering sciences and the life sciences in these domains is becoming quite tight, as illustrated by many transdisciplinary conferences, journals and research organizations. But researchers from both disciplines have now entered more complex domains of investigation where a lot remains to be done.

One such difficult domain is our feeling that there is a steady world and an underlying space around us. In developmental psychology, the issue of "the child's construction of reality" was raised more than 70 years ago by [START_REF] Piaget | The construction of reality in the child (M. Cook, Trans.)[END_REF][START_REF] Piaget | The construction of reality in the child (M. Cook, Trans.)[END_REF]; philosophical and mathematical investigations, by authors like [START_REF] Husserl | Die Frage nach dem Ursprung der Geometrie als intentionalhistorisches Problem[END_REF]Husserl ( /1970) ) and [START_REF] Poincaré | The value of science (G.B. Halsted, Trans.)[END_REF][START_REF] Poincaré | The value of science (G.B. Halsted, Trans.)[END_REF], go even farther back in some cases. The question can be stated as follows: How is it that, given our diverse sensors that are moving at any moment, we get to the idea that there is a more or less permanent world around us that contains objects and living beings and that is endowed with spatial and temporal properties? This is a difficult question because it does not seem trivial to extract these properties from our sensors. The importance of this question for explaining the performance of a soccer player is nicely framed by [START_REF] Sandamirskaya | Using Dynamic Field Theory to extend the embodiment stance toward higher cognition[END_REF]. Part of the answer to this question seems to rely on our dynamic interactions with this world: It seems that we need to act on it to form a notion of its existence. This difficult question is also crucial from the standpoint of "developmental robotics." If we want a robot to plan its actions in a complicated setting, it has to reason in a space appropriate for such a plan; i.e., "external" space and the objects it contains. But if we want this approach to work in unprepared environments, providing the robot with a detailed representation of what is around it is not an option. The robot has to be able to build its own representation of its environment through its interactions with it. This special issue of New Ideas in Psychology addresses such difficult questions from a transdisciplinary standpoint. The articles derive from the workshop on Anticipatory Behavior in Adaptive Learning Systems (ABiALS) that was held at the Center for Interdisciplinary Research (ZIF) in Bielefeld, Germany, in February 2011. The topic of the workshop was "Spatial Representations and Dynamic Interactions."

Since the first ABiALS workshop, which took place in 2002 in Edinburgh, Scotland, participants have worked from the shared assumption that predictions and anticipations play a key role in organizing behavior [START_REF] Butz | Internal models and anticipations in adaptive learning systems[END_REF][START_REF] Butz | Anticipations, Brains, Individual and Social Behavior: An Introduction to Anticipatory Systems[END_REF]. Recent research using empirical, theoretical and computational methodologies is increasingly revealing that brain function and cognition are essentially anticipatory(e.g., [START_REF] Berthoz | The Brain's Sense of Movement[END_REF]Berthoz, /1999)). The view of a proactive brain continuously generating and evaluating predictions has been put forward in a number of interdisciplinary initiatives, including but not limited to the ABiALS conferences. The view of the brain as an anticipatory device can inform and cross-fertilize neuroscientific, psychological, and engineering studies. It can advance our understanding of the representation and construction of reality in much the same way as theories of reinforcement learning have advanced our understanding of reward and motivation. Some of the contributions to this issue are more concerned with spatial representation; others focus to a greater extent on dynamic actions or interactions with the world; still others are dedicated to the anticipatory processes involved in learning and using the corresponding representations.

In the first category, Wolfram [START_REF] Schenck | Robot studies on saccade-triggered visual prediction[END_REF] examines the anticipatory visual processing of the environment when the eyes are performing saccadic movements. Schenck postulates that a visual forward model predicts the visual input to the eye after a saccade is performed, which would correspond to mentally centering an object seen at the periphery before actually making a saccade towards it. The neurophysiological phenomenon is called "predictive remapping" and may play a central role in our feeling that there is a steady world around us. With a robotic set-up, Schenk shows that predictive remapping strongly enhances the performance of a grasping module. He then discusses the biological relevance of the resulting control architecture, in light of such phenomena as attention and mental imagery.

As [START_REF] Piaget | The construction of reality in the child (M. Cook, Trans.)[END_REF][START_REF] Piaget | The construction of reality in the child (M. Cook, Trans.)[END_REF] clearly pointed out, building a representation of the external world further implies building a representation of ourselves in this world. Where the spatial position and posture of the body are concerned, the representations to be acquired are called the body schema and the body image (see e.g. Hoffmann et al. (2110)). When we are interacting with the world, particularly when we do this with tools, is the representation of the tool included in the representation of the world or in the body schema? Two contributions are dedicated to this topic.

Cristina [START_REF] Massen | Cognitive representations of tool-use interactions[END_REF] investigates two questions about tool use that requires some planning capabilities. First, when we are using a tool, do we incorporate it as an extension of our body schema, or do we call upon a central representation that maps between body movements and the environmental effects of the tool? Second, is the potential central representation of the tool abstract or concrete? Her survey provides arguments in favor of rather abstract central representation, based on the study of precuing, bimanual coordination, and observational and priming effects. The role of anticipation in motor preparation is particularly important in the precuing paradigm.

The contribution from Christine [START_REF] Sutter | Limitations of distal effect anticipation when using tools[END_REF] is complementary to Massen's. The authors focus on technologies that give rise to complex visuomotor transformations, such as laparoscopic minimally invasive surgery tools with an external visual feedback display. In that context, they study the respective influence of proximal feedback (proprioceptively and visually related to the hand) versus distal feedback (related to the end effector of the tool). They show that the dominance of distal effects in action control is a major precondition for controlling tools successfully. It allows for a wide range of flexible sensorimotor adaptations and it gives the user the feeling of being in control. However, this mechanism seems to be subject to boundary conditions: it breaks down when there are extreme discrepancies in perception-action feedback. Here the conflict in information processing makes the behavior slower and more error-prone; moreover, action control mostly based on distal effects shifts to action control based on proximal effects. Thus, action-effect control principles play an important role for understanding the constraints on acquiring and dealing with tool transformations.

Beyond the representation of tools, we must study the representation of actions themselves. Thomas Schack and Helge Ritter (2012) investigate the impact of the organization of cognitive representation of actions on motor performance. They introduce the notion of Basic Action Concepts (BACs) as elementary components of the agent's possible representations of his/her own actions and study the relationship between the structure of a set of BACs and performance in motor tasks. In addition, they investigate how this general framework derived from studies in experimental psychology can be applied in a robotic context, by providing key elements of a control architecture.

Action representation is also central to Action Simulation Theory (AST). Laura Barca and colleagues (2012) provide a survey of this theory, before sketching a computational model. One of the key ideas in AST is that the representation of an action is not a static content stored in a memory register -as would be the case for the representation of a variable in a computer -but rather a dynamic process involving the re-enactment of the action. AST casts new light on motor phenomena, but it may also be applicable to the representation of space or even to social contents.

The next two contributions are more concerned with the selection, coordination, and control of dynamic interactions with the world. Oliver [START_REF] Herbort | Optimal versus heuristic planning of object manipulations: A review and a computational model of the continuous end-state comfort effect[END_REF] studies the sequential planning of movements, focusing on the impact of the next movement on the way a previous movement is performed. For instance, we would not grasp a knife the same way in order to put it on a table, to cut something with it, or to give it to someone else. The most commonly accepted explanation for these phenomena is based on the optimal control framework. Herbort shows the limitations of this explanation, which is neither necessary nor sufficient to account for the properties of movement. He proposes an alternative model, based on a collection of simple biases, which better explains the data.

At a more abstract level, Martin [START_REF] Butz | Goals and behavioral control: Implications from learning predictive modularizations[END_REF] investigates the modular decomposition within an anticipatory framework between an action selection module that determines which goal should be pursued and a control module that determines how to achieve the current goal. He shows how the representation of goals may emerge from the combination of such modules and concludes that the emergent goal representations may be a key to the development of behaviorally grounded, pre-linguistic structures.

The contribution from [START_REF] Lommertzen | Perceptuomotor rules as prediction tools in (joint) action: The case of orientation perception[END_REF] studies the interactions between perceptual and motor processes. The authors compare the impact of the Rod and Frame Illusion (RFI) in two contexts that imply very different motor involvement from the participants. They show that participants are similarly affected by the illusion independently of the amount of motor involvement, arguing for a common representation level for the perceptual and the motor systems involved in the tasks.

The contributions reviewed so far would normally be considered research in psychology and/or robotics. The last two bring in computational models of phenomena studied in the neurosciences.

First, Dynamic Field Theory (DFT) models the dynamics of the populations of neurons involved in sensory-motor phenomena at a rather abstract level. It can be seen as an intermediate formalism facilitating the transfer of principles between neurosciences and engineering. Yulia [START_REF] Sandamirskaya | Using Dynamic Field Theory to extend the embodiment stance toward higher cognition[END_REF] explain how DFT can be extended to perform more cognitive operations: creating or activating an instance of an abstract representation from sensory data (i.e., the capacity to recognize an object), changing a reference frame, and performing a sequence of recognition operations by storing the sought objects in memory until they are found. These very basic cognitive capabilities are illustrated in a robotic context.

Finally, the paper from Keith [START_REF] Downing | Neural predictive mechanisms and their role in cognitive incrementalism[END_REF] presents an overview of the neural mechanisms involving anticipatory or predictive processes in different brain areas (the cerebellum, the basal ganglia, the hippocampus, and the neocortex). He applies the theory of cognitive incrementalism, which states that high-level cognition is built on top of lower-level sensorimotor behavior.

Taken together, all these papers give an up-to-date picture of research at the intersection between the representation of space and complex, interactive behavior. We believe that the different viewpoints collected in the special issue shed a complementary light on the corresponding questions and we hope that the edition of this special issue will contribute in strengthening the growing community of researchers concerned with them, both from the life sciences side and from the robotics side.