Julien Diard
email: julien.diard@upmf-grenoble.fr

Pierre Bessière
email: pierre.bessiere@imag.fr

Bayesian Maps: probabilistic and hierarchical models for mobile robot navigation

Introduction

Imagine yourself lying in your bed at night. Now try to answer these questions: Is your body parallel or not to the sofa that is two rooms away from your bedroom? What is the distance between your bed and the sofa? Except for some special cases (like rotating beds, people who actually sleep on their sofas, or tiny apartments), these questions are usually nontrivial, and answering them requires abstract thought. If pressed to answer quickly, so as to forbid the use of abstract geometry learned in high school, the reader will very probably give wrong answers.

However, if people had the same representations of their environment that roboticians usually provide to their robots, answering these questions would be very easy. The answers would come quickly, and they would certainly be correct. Indeed, robotic representations of space are usually based on largescale, accurate, metric Cartesian maps. This enables judgment of parallelism and estimations of distances to be straightforward.

On the other hand, even though humans have difficulties with these questions, they usually have no trouble navigating from the sofa to the bed, or learning to do so in a new apartment. Robots have more difficulties in the same situation. In most robotic mapping approaches, the acquisition of a precise, and more importantly, accurate map of the environment is a prerequisite to solving navigation tasks. This is still a difficult and open issue in the general case.

Therefore, there appears to be a discrepancy in representations of space between the ones we usually provide to the robots we build and program, and the representations of space humans or animals use. Indeed, the nature, number, and possible interplay of the spatial representations involved in human or an-imal navigation processes are still an open question in the life sciences. There is also a discrepancy in the difficulty of navigation tasks currently solved by state-of-the-art robots and the navigation tasks solved very easily by humans or animals.

We believe studying the difference between robotics and life sciences models of navigation can be very fruitful, both for modelling better robots and understanding animal navigation better. That is the topic of this chapter.

We first offer a quick overview of navigation models, both in robotics and in biology. We will first focus, more precisely, on probabilistic approaches to navigation and mapping in robotics. These approaches include -but are far from limited to -Kalman filters [START_REF] Leonard | Dynamic map-building for an autonomous mobile robot[END_REF], Markov localization models [START_REF] Thrun | Probabilistic algorithms in robotics[END_REF], (partially or fully) observable Markov decision processes [START_REF] Kaelbling | Planning and acting in partially observable stochastic domains[END_REF], and hidden Markov models [Rabiner and Juang, 1993]. We will here assume that the reader has some familiarity with these approaches. We will show how these methods differ from most models of human or animal navigation. Indeed, whereas robotics approaches mostly rely on large-scale monolithic representations of space, models of animal navigation, right from the start, assume hierarchies of representations. We thus then describe hierarchical approaches to robotic mapping.

Indeed, in this domain of probabilistic modelling for robotics, hierarchical solutions are currently flourishing. However, we will argue that the main philosophy used by all these approaches is to try to extract, from a very complex but intractable model, a hierarchy of smaller models. Of course, automatically selecting the relevant decomposition of a problem into subproblems is quite a challenge -this challenge being far from restricted to the domain of navigation for robots facing uncertainties.

We propose to pursue an alternative route. We investigate how, starting from a set of simple probabilistic models, one can combine them to build more complex models. The goal of this paper is therefore to present a new formalism for building models of the space in which a robot must navigate (the Bayesian Map model), and a method for combining such maps together in a hierarchical manner (the Abstraction operator). This formalism allows for a new representation of space, in which the final program is built upon many inter-related models, each of them deeply rooted in lower-level sensorimotor relationships.

For brevity, we will discuss neither the learning methods that can be included in Bayesian Maps [START_REF] Simonin | Learning Bayesian models of sensorimotor interaction: from random exploration toward the discovery of new behaviors[END_REF], nor other operators for merging Bayesian Maps (such as the Superposition operator [START_REF] Diard | Merging probabilistic models of navigation: the bayesian map and the superposition operator[END_REF]). The foundation of the present work was created in Diard's PhD thesis [START_REF] Diard | La carte bayésienne -Un modèle probabiliste hiérarchique pour la navigation en robotique mobile[END_REF].

The rest of this chapter is organized as follows. Section 2 gives a quick overview of the most prominent models of navigation and representation of large-scale space, first from a robotics point of view, then from a life sciences point of view. Section 3 offers a comparison of the main characteristics of the models, and an analysis of their strengths and weaknesses, and argues in favour of the need for hierarchical and modular probabilistic models of navigation. We then introduce our contribution to the domain, the Bayesian Map formalism (Section 4), and one of the operators we defined for combining Bayesian Maps, the abstraction operator (Section 5). Finally, we report in Section 6 a series of robotic experiments in which we apply the Bayesian Map model and the abstraction operator on a Koala mobile robot, in a proof-ofconcept experiment.

Navigation models in robotics and biology

We focus this brief review on existing models of navigation skills, in both robotics and life sciences. Because the literature in robotics concerning the representation of space is so large, we focus here on probabilistic approaches to mapping. In the life sciences, we describe some of the more prominent theoretical models of large-scale navigation in humans and animals, focusing on their hierarchical nature.

Probabilistic models of navigation and mapping

There is currently a wide variety of models in the domain of probabilistic mobile robot programming. These approaches include Kalman Filters (KF, [START_REF] Leonard | Dynamic map-building for an autonomous mobile robot[END_REF]), Markov Localization models (ML, [START_REF] Thrun | Probabilistic algorithms in robotics[END_REF]), (Partially or fully) Observable Markov Decision Processes (POMDP, MDP, [START_REF] Boutilier | Decision theoretic planning: Structural assumptions and computational leverage[END_REF]), Hidden Markov Models (HMM, [Rabiner and Juang, 1993]), Bayesian Filters (BFs), and even Particle Filters (PFs). The literature covering these models is huge: for references that present several of them at once, giving unifying pictures, see [START_REF] Murphy | Dynamic Bayesian Networks: Representation, Inference and Learning[END_REF][START_REF] Roweis | A unifying review of linear gaussian models[END_REF][START_REF] Smyth | Probabilistic independence networks for hidden markov probability models[END_REF]. Some of these papers define taxonomies of these approaches, by proposing some ordering that helps to classify them into families. One such taxonomy is presented in Fig. 1 (from [START_REF] Diard | A survey of probabilistic models, using the bayesian programming methodology as a unifying framework[END_REF]). It is based on a general-to-specific ordering: for example, it shows that Dynamic Bayesian Networks (DBNs) are a specialization of the Bayesian network formalism, tailored to take time series into account. In Fig. 1, subtrees that correspond to different specialization strategies can be identified. In the remainder of this section, we will focus on the Markov localization subtree, which corresponds to specializing DBNs using a four-variable model.

The ML model is basically an HMM with an additional action variable. It seems especially relevant in the robotic programming domain, because obviously robots can affect their states via motor commands. The stationary model of an HMM is basically the decomposition

P (P t L t L t-1 ) = P (L t-1 )P (L t | L t-1 )P (P t | L t ), (1)
where P t is a perception variable, and L t and L t-1 are state variables or, more precisely in our navigation case, location variables at time t and t -1. Fig. 1. Some common probabilistic modelling formalisms and their general-tospecific partial ordering (adapted from [START_REF] Diard | A survey of probabilistic models, using the bayesian programming methodology as a unifying framework[END_REF]). The ML subtree, which results from specializing DBNs, is highlighted (dashed nodes).

P (L t | L t-1
) is commonly called the transition model, and P (P t | L t ) is referred to as the observation model. Starting from this structure, the action variable A t is used to refine the transition model

P (L t | L t-1 ) into P (L t | A t L t-1
), which is called the action model. Thus, the ML model is sometimes referred to as the input-output HMM model. Because of the generality of the BRP formalism, the model for Markov Localization can be cast into a BRP program. This is shown Fig. 2.

Program                                          Description                                    Specification                           
Relevant Variables: P t : perception variable L t : discrete location variable at time t L t-1 : discrete location variable at time t -1 A t : action variable Decomposition: The ML model is mostly used in the literature to answer the question P (L t | A t P t ), which estimates the state of the robot, given the latest motor commands and sensor readings. When this state represents the position of the robot in its environment, this amounts to localization. When this stationary ML model is replicated over time to estimate the positions L 0:T of the robot over a long series of time steps, it can be shown that an iterative localization procedure exists that localizes the robot simply by updating the last position estimate in view of the latest motor commands A t and sensor readings P t . This justifies, in this presentation, the focus on the stationary model.

P (A t L t L t-1 L t ) = P (L t | A t L t-
The ML model has been successfully applied in a range of robotic applications, the most notable examples being the Rhino ( [START_REF] Thrun | Map learning and high-speed navigation in RHINO[END_REF], Burgard et al., 1999]) and Minerva ( [Thrun et al., 1999a,b]) robotic guides. The most common application of the ML model is the estimation of the position of a robot in an indoor environment, using a fine-grained metric grid as a representation. In other words, in the model of Fig. 2, the state variable is very frequently the pose of the robot, i.e. a pair of x, y discrete Cartesian coordinates for the position, and an angle θ for the orientation of the robot. Assuming a grid cell size of 50 cm, an environment of 50 m × 50 m, and a 5 • angle resolution entails a state space of 720,000 states.

Using some specialized techniques and assumptions, it is possible to make this memory-consuming model tractable.

For example, the forms of the probabilistic model can be implemented using sets of particles. These approximate the probability distributions involved in Fig. 2, which leads to an efficient position estimation. This specialization is called the Monte Carlo Markov Localization model (MCML, [START_REF] Fox | Monte Carlo localization: Efficient position estimation for mobile robots[END_REF]).

Another possibility is to use a Kalman filter as a specialization of the ML model, in which variables are continuous. The action model P (L t | A t L t-1 ) and the observation model P (P t | L t ) are both specified using Gaussian laws with means that are linear functions of the conditioning variables. With these hypotheses, it is possible to solve the inference problem analytically to answer the localization question. This leads to an extremely efficient algorithm that explains the popularity of Kalman filters.

Biologically inspired models

All the approaches mentioned in the preceding section are based on the classical view of robotic navigation, which is inherited from marine navigation. In this view, solving a navigation task basically amounts to answering sequentially the questions of Levitt and Lawton: "Where am I?", "Where are other places with respect to me?", and "How do I get to other places from here?" [START_REF] Levitt | Qualitative navigation for mobile robots[END_REF]. These are formulated somewhat similarly in the works of Leonard and Durrant-Whyte: "Where am I?", "Where am I going?", and "How should I get there?" [START_REF] Leonard | Mobile robot localization by tracking geometric beacons[END_REF].

While they are a valid first decomposition of the navigation task into subtasks, these questions have usually led to models that require a global model of the environment, which allows the robot to localize itself (the first questions), to infer spatial relationships between the current recognized location and other locations (the second questions), and to plan a sequence of actions to move within the environment (the third questions). These skills amount to the first two phases of the "perceive, plan, act" classical model of robotic control.

Very early in their analysis, biomimetic models of navigation disputed this classical view of robotic navigation. Indeed, when studying living beings, the existence of such a unique and global representation that would be used to solve these three questions is very problematic. This seems obvious even for simple animals like bees and ants. For instance, the outdoor navigation capabilities of the desert ant Cataglyphis, which have been widely studied, rely on the use of the polarization patterns of the sky [START_REF] Lambrinos | A mobile robot employing insect strategies for navigation[END_REF]. It is clear that such a strategy is useless for navigating in a nest; this calls for another navigation strategy, and another internal model. The existence of a unique representation is also doubtful for humans. The navigation capabilities of humans are based on internal models of their environment (cognitive maps), but their nature, number and complexity are still largely debated (see for instance [START_REF] Berthoz | The Brain's Sense of Movement[END_REF][START_REF] Redish | Cognitive maps beyond the hippocampus[END_REF][START_REF] Wang | Human spatial representation: insights from animals[END_REF], for entry points into the huge literature associated with this domain).

As a consequence, biomimetic approaches assume from the start the existence of multiple representations, most often articulated in a hierarchical manner. We now give a brief review of some theories from that domain, focusing on their hierarchical components.

Works by Redish and Touretzky

Works by Redish and Touretzky address the issue of the role of the hippocampus and parahippocampal populations in rodent navigation, focusing on the well-studied place cells and head direction cells. They proposed a conceptual model [START_REF] Touretzky | A theory of rodent navigation based on interacting representations of space[END_REF] and discussed its anatomical plausibility [START_REF] Redish | Cognitive maps beyond the hippocampus[END_REF]. Their hierarchical conceptual model consists of four spatial representations (place code, local view, path integrator and head direction code), supplemented by two components called the reference frame selection subsystem and the goal subsystem.

Place codes are local representations tied to one or several landmarks or geometric features of the environment. When the environment of the animal becomes large or structured, several place codes may be used to describe this environment, each place code representing a part of the environment. For instance, Gothard et al. [START_REF] Gothard | Binding of hippocampal CA1 neural activity to multiple reference frames in a landmark-based navigation task[END_REF] found different place codes for a rat navigating in an environment containing a goal and a starting box. They identified three independent place codes: one tied to the room, one to the goal, and one to the box. These effectively provide representations of sections of the environment: cells tuned to the box frame were only active when the rat was in or around the box, cells tuned to the goal only responded when the rat was near the goal, cells tuned to the room were active at other times (i.e. when the rat was not near the box or the goal).

The reference frame selection component is responsible for selecting the appropriate place code for navigating in the environment. In the above example, this means that it is responsible for selecting, at any given time, which place code should be active.

This theory thus proposes an account of the low-level encoding of space in central nervous systems of animals using a two-layer hierarchy of models. The low-level layer consists of a series of place codes describing portions of the animal environment, under the hierarchical supervision of a larger-space model.

Computational models of the low-level component of this hierarchy, (i.e. place cells and head-direction cells) abound in the literature (e.g. [START_REF] Hartley | Encyclopedia of Cognitive Science[END_REF]), whereas the reference frame selection component, to the best of our knowledge, has yet to be mathematically defined.

Works by Jacobs and Schenk

Jacobs and Schenk proposed a new theory of how the hippocampus encodes space [Jacobs and[START_REF] Jacobs | Unpacking the cognitive map: the parallel map theory of hippocampal function[END_REF]. This theory is called the Parallel Map Theory (PMT), and it defines a hierarchy of navigation representations made of three components and two layers.

The bearing map is the first, low-level, component. This is a single map based on several directional cues such as intersecting gradients. It provides a large-scale two-dimensional reference frame, enabling large-scale navigation skills, simply using gradient ascent or descent.

The sketch maps are the second component of the low-level layer of the hierarchy. They encode small-scale fine-grained representations of the relationship of landmarks that are close to each other (positional cues). This creates local representations, which can be used for precise control of the position, and thus for solving precise, small-scale navigation tasks.

Finally, the integrated map is the third, high-level, component. This is constructed from the bearing map and several sketch maps. It consists of a unified map of large-scale environments, where the local sketch maps are cast into the large-scale reference frame of the bearing map. This provides the means to infer large-scale spatial relationship between the local, metric representations of the sketch maps, thus allowing computation of large-scale shortcuts and detours.

To the best of our knowledge, the papers by Jacobs and Schenk do not provide computational models of these different components. Instead, they mainly focus on the anatomical and phylogenetic plausibility of their conceptual model. This provides many experimental predictions concerning possible impairments resulting from lesions.

Works by Wang and Spelke

These authors dispute the idea that enduring, allocentric, large-scale representations of an environment should be the main theoretical tool used for investigating navigation in humans and animals. Indeed, the cognitive map concept, introduced by Tolman in 1948, is still controversial [START_REF] Tolman | Cognitive maps in rats and men[END_REF]. Instead, Wang and Spelke argue that many navigation capabilities in animals can be explained by dynamic, egocentric representations that cover a limited portion of the environment [Wang andSpelke, 2000, 2002]. Such representations can be studied in animals that are far simpler than humans, such as desert ants [START_REF] Lambrinos | A mobile robot employing insect strategies for navigation[END_REF].

Studies on these animals have identified three subsystems: a path integration system, a landmark-based navigation system, and a reorientation system. This last component is not hierarchically related to the other two, as it is mainly responsible for resetting the path integration system when the animal becomes disoriented. However, the first two components show a strong hierarchical relation. Indeed, it has been shown that the landmark-based strategy is hierarchically higher in the cognitive mechanisms of insects and rodents. It also appears that, in the sudden absence of landmarks after learning a path, animals rely on the path integration encoding as a "backup" [Stackman et al., 2002, Stackman and[START_REF] Stackman | Rats with lesions of the vestibular system require a visual landmark for spatial navigation[END_REF].

This model is somewhat different from the previous studies, as it focuses on defining a hierarchy of skills of navigation, instead of hierarchies of representations of space, as in the PMT or studies of the hippocampal and parahippocampal areas.

Works by Kuipers, Franz, and Trullier The hierarchies of models proposed in the biomimetic robotic literature ( [START_REF] Kuipers | A hierarchy of qualitative representations for space[END_REF][START_REF] Trullier | Biologically-based artificial navigation systems: Review and prospects[END_REF][START_REF] Franz | Biomimetic robot navigation[END_REF][START_REF] Kuipers | The spatial semantic hierarchy[END_REF][START_REF] Victorino | An hybrid representation well-adapted to the exploration of large scale indoors environments[END_REF]) have several aspects: they are hierarchies of increasing navigation skills, but also of increasing scale of the represented environment, of increasing time scale of the associated movements, and of increasing complexity of representations. This last aspect means that topologic representations, which are simple, come at a lower level than global metric representations, which are arguably more complex to build and manipulate. This ordering stems from the general observation that animals that are able to use shortcuts and detours between two arbitrary encoded places (skills that require global metric models) are rather complex animals, like mammalians. These skills seem to be mostly absent from simpler animals, like invertebrates.

The resulting proposed hierarchies show a striking resemblance. We present the salient and common features of these hierarchies by summarizing the Spatial Semantic Hierarchy (SSH) proposed by Kuipers [START_REF] Kuipers | A hierarchy of qualitative representations for space[END_REF][START_REF] Kuipers | The spatial semantic hierarchy[END_REF]. It is, to the best of our knowledge, the only biomimetic approach that has been applied to obtain a complete and integrated robotic control model.

The SSH essentially consists of four hierarchical levels: the control level, the causal level, the topological level, and the metric level.

The control level is a set of reactive behaviours, which are control laws deduced from differential equations. These behaviours describe how to move the robot to reach an extremum of some gradient measure. This extremum can be zero-dimensional (a point in the environment), in which case it is called a locally distinctive state. The associated behaviour is called a hillclimbing law. The extremum can also be one-dimensional (a line or curve in the environment), in which case the behaviour is called a trajectory-following law. Provided that any trajectory-following law guarantees arriving at a place where a hill-climbing law can be applied, then alternating laws of both types displace the robot in a repetitive fashion. This solves the problem of the accumulation of odometry errors. The control level is also referred to as the guidance level [Trullier et al., 1997, Franz and[START_REF] Franz | Biomimetic robot navigation[END_REF].

Given the control level, the environment can be structured and summarized by the locations of locally distinctive states and the trajectories used to go from one such state to another. This abstraction takes place in the causal level, which is the second level of the hierarchy of representations. Unlike the control level, it allows the robot to memorize relationships between places that are outside the current perceptive horizon (this is part of the way-finding capabilities in other terminologies [Trullier et al., 1997, Franz and[START_REF] Franz | Biomimetic robot navigation[END_REF]). To do so, Kuipers abstracts locally distinctive places as views V , the application of lower-level behaviours as actions A, and defines schemas as tuples V, A, V ′ (expressed as first-order logic predicates). The schemas have two meanings. The first is a procedural meaning: "when the robot is at V , it must apply action A." This aspect of a schema is equivalent to the recognition-triggered response level of the other hierarchies [Trullier et al., 1997, Franz and[START_REF] Franz | Biomimetic robot navigation[END_REF]], or to the potential field approaches, or to other goal-oriented methods. However, the second meaning of schemas is a declarative one, where V, A, V ′ stands for: "applying action A from view V eventually brings the robot to view V ′ ." This allows using the schemas for prediction of future events, or in a planning process, for example.

The goal of the topological level is to create a globally consistent representation of the environment, as structured by places, paths and regions. These are extracted from lower-level schemas by an abduction process that creates the minimum number of places, paths and regions to maintain consistency with the known schemas. Places are zero-dimensional parts of the environment that can be abstractions of lower-level views, or abstractions of regions (for higher-level topological models). Paths are one-dimensional, oriented, and can be built upon one or more schemas. Finally, regions are two-dimensional subspaces, delimited by paths. It must be noted that, because the problem of accumulation of odometry error was dealt with at the control level, building a globally consistent topological representation (i.e. solving the global connectivity problem) is much easier. To do so, Kuipers proposes an exploration strategy, the rehearsal procedure, which, unfortunately, requires a bound on the exploration time and is not well suited to dynamic environments. The places and paths of the topological representation obtained can be used for solving planning queries using classical graph-searching algorithms.

The last level is the metric level, in which the topological graph is cast into a unique global reference frame. For reasons outlined above (and detailed in [START_REF] Kuipers | The spatial semantic hierarchy[END_REF]), this level is considered as a possibility, not a prerequisite for solving complex navigation tasks. If the sensors are not good enough to maintain a good estimation of the Cartesian coordinates of the position, for instance, it is still possible to use the topological model to act in the environment -although shortcuts and detours are not possible. Indeed, few robotics systems implementing biomimetic models include the metric level [START_REF] Franz | Biomimetic robot navigation[END_REF]Mallot, 2000, Trullier et al., 1997].

Theoretical comparison

Which mathematical formalism?

A major drawback of the biomimetic models presented previously is that they are seldom defined as computational models: they give conceptual frameworks for understanding animal navigation but lack complete mathematical definitions that would make simulations of these models possible. The notable exception is the SSH model, which not only defines layers in a hierarchy of space representations but also defines each of them mathematically.

However, the SSH model uses a variety of formalisms for expressing knowledge at different layers of the hierarchy: differential equations and their solutions for the control level, and first-order logic and deterministic algorithms for higher-level layers of the hierarchy. This makes it difficult to justify the consistency and correctness of the mechanisms for communication between the layers of the hierarchy theoretically. In some cases, it even limits and constrains the contents of the layers: for instance, the SSH model requires that the behaviours of the control level guarantee that the robot reaches the neighbourhood of a given locally distinctive state. In our view, this constraint is barely acceptable for any kind of realistic robotic scenario. Consider dynamic environments: how can we guarantee that a robot will reach a room if a door on the route can be closed?

We assume as a starting point for our analysis that the best formalism for expressing incomplete knowledge and dealing with uncertain information is the probabilistic formalism [START_REF] Bessière | Interprétation vs. description I : Proposition pour une théorie probabiliste des systèmes cognitifs sensori-moteurs[END_REF][START_REF] Jaynes | Probability Theory: The Logic of Science[END_REF]. This gives us a clear and rigorous mathematical foundation for our models. The probability distributions are our unique tool for the expression and manipulation of knowledge, and in particular, for communication between submodels. We will thus argue in favour of hierarchical probabilistic models.

Hierarchical probabilistic models

This idea is not a breakthrough: in the domain of probabilistic modelling for robotics, hierarchical solutions are currently flourishing. The more active domain in this regard is decision-theoretic planning: one can find variants of MDPs that accommodate hierarchies or that select automatically the partition of the state space (see, for instance, [Hauskrecht et al., 1998, Lane and[START_REF] Lane | Toward hierarchical decomposition for planning in uncertain environments[END_REF], or browse through the references in [START_REF] Pineau | An integrated approach to hierarchy and abstraction for POMDPs[END_REF]). More exceptionally, one can find hierarchical POMDPs [START_REF] Pineau | An integrated approach to hierarchy and abstraction for POMDPs[END_REF]. The current work can also be related to Thrun's object mapping paradigm [START_REF] Thrun | Robotic mapping: A survey[END_REF], in particular concerning the aim of transferring some of the knowledge the programmer has about the task to the robot. Some hierarchical approaches outside the MDP community include hierarchical HMMs and their variants (see [START_REF] Murphy | Dynamic Bayesian Networks: Representation, Inference and Learning[END_REF] and references therein), which, unfortunately, rely on the notion of the final state of the automaton. Another class of approaches relies on the extraction of a graph from a probabilistic model such as a Markov localization model [START_REF] Thrun | Learning metric-topological maps for indoor mobile robot navigation[END_REF], or an MDP [START_REF] Lane | Nearly deterministic abstractions of markov decision processes[END_REF]. Using such deterministic notions is inconvenient in a purely probabilistic approach, such as we are pursuing here.

Moreover, the main philosophy used by all the previous approaches is to try to extract, from a very complex but intractable model, a hierarchy of smaller models (structural decomposition, see [START_REF] Pineau | An integrated approach to hierarchy and abstraction for POMDPs[END_REF]).

Again, this comes from the classical robotic approach, where the process of perception (in particular, localization) is assumed to be independent of the processes of planning and action. A model such as the ML model (Fig. 2) is only concerned with localization, not control; therefore, its action variable A t is actually only used as an input to the model. In this view, a pivotal representation is used between the perception and planning subproblems. It is classically assumed that the more precise this pivotal model, the better. Unfortunately, when creating integrated robotic applications, dealing with both the building of maps and their use is necessary. Some authors have realized that their global metric maps were too complex to be easily manipulated. Therefore, they have tried to degrade their maps, which were so difficult to obtain initially, for instance, by extracting graphs from their probabilistic models [START_REF] Thrun | Learning metric-topological maps for indoor mobile robot navigation[END_REF]. This problem is also at the core of the robotic planning domain, where the given description of the environment is assumed to be an infinitely precise geometrical model. The difficulty is to discretize this intractable, continuous model into a finite model, typically, in the form of a graph [START_REF] Latombe | Robot Motion Planning[END_REF][START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF], Mazer et al., 1998[START_REF] Svestka | Probabilistic path planning[END_REF]].

Modular probabilistic models: towards Bayesian Maps

We propose to pursue an alternative route, investigating how, starting from a set of simple models, one can combine them to build more complex models. Such an incremental development approach allows us to depart from the classical "perceive, plan, act" loop, considering instead hierarchies built upon many inter-related models, each of them deeply rooted in lower-level sensory and motor relationships.

The Bayesian robotic programming methodology offers exactly the formal tool that can transfer information from one program to another in a theoretically rigorous fashion. Indeed, in Bayesian robotic programs, terms appearing in a description c 1 can be defined as a probabilistic question to another description c 2 . This creates a link between the two descriptions, one being used as a resource by another. Depending on the way questions are used to link subprograms, several different operators can be created, each with specific semantics: for instance, in the framework of behaviour-based robotics, Lebeltel has defined behaviour combination, hierarchical behaviour composition, and behaviour sequencing and sensor model fusion operators. He has also applied these successfully to realize a complex watchman robot behaviour using a control architecture involving four hierarchical levels [START_REF] Lebeltel | Bayesian robot programming[END_REF].

Thus, we can solve a global robotic task problem by first decomposing it into subproblems, then writing a Bayesian robot program for each subproblem, and finally combining these subprograms. This method makes robot programming similar to structured computer programming. So far in our work, we have let the programmer do this analysis: relevant intermediary representations can be imagined, or copied from living beings. We propose to apply this strategy to the map-based navigation of mobile robots. The submodels can be submaps, in the spatial sense (i.e. covering a part of the global environment), or in the subtask sense (i.e. modelling knowledge necessary for solving part of the global navigation task), or even in less familiar senses (e.g. modelling partial knowledge from part of the sensorimotor apparatus).

Our approach is therefore based on a formalism for building models of the space in which the robot must navigate, called the Bayesian Map model, that allows us to build submodels that provide behaviours as resources. We also define operators for combining such maps in a hierarchical manner.

The Bayesian Map formalism: definition

Probabilistic definition

A Bayesian Map c is a description that defines a joint distribution

P (P L t L t ′ A | c),
where:

• P is a perception variable (the robot reads its values from physical sensors or lower-level variables); • L t is a location variable at time t; • L t ′ is a variable having the same domain as L t , but at time t ′ (without loss of generality, let us assume t ′ > t); and • A is an action variable (the robot writes commands to this variable).

For simplicity, we will assume here that all these variables have finite domains.

The choice of decomposition is not constrained: any probabilistic dependency structure can therefore be chosen here; see [START_REF] Attias | Planning by probabilistic inference[END_REF] for an example of how this can lead to interesting new models. Finally, the definition of forms and the learning mechanism (if any) are also not constrained.

For a Bayesian Map to be usable in practice, the description must be rich enough to generate behaviours. We describe as elementary behaviour any question of the form P (A i | X), where A i is a subset of A, and X is a subset of the other variables of the map (i.e. of those not in A i ). A typical example consists of the probabilistic question P (A | [P = p] [L t ′ = l]): compute the probability distribution over actions, given the current sensor readings p and the goal l to reach in the internal space of possible locations.

A behaviour can be not elementary, for example, if it is a sequence of elementary behaviours, or, in more general terms, if it is based on elementary behaviours and some other knowledge (which may be expressed in terms other than maps).

For a Bayesian Map to be interesting, we will also require that it generates several behaviours -otherwise, defining just a single behaviour instead of a map is enough. Such a map is therefore a resource, based on a location variable relevant enough to solve a class of tasks; this internal model of the world can be reified.

A "guide" one can use to "make sure" that a given map will generate useful behaviours is to check whether the map answers in a relevant manner the three questions

P (L t | P ) (localization), P (L t ′ | A L t ) (prediction) and P (A | L t L t ′ ) (control).
By "relevant manner", we mean that these distributions must be informative, in the sense that their entropy is "far enough" from its maximum (i.e. the distribution is different from a uniform distribution). This constraint is not formally well defined, but it seems intuitive to focus on these three questions. Indeed, the skills of localization, prediction and control are well identified in the literature as ways of generating behaviours. Checking that the answers to these questions are informative is a first step to evaluating the quality of a Bayesian Map with respect to solving a given task.

Figure 3 is a summary of the definition of the Bayesian Map formalism.

Generality of the Bayesian Map formalism

We now invite the reader to verify that the Markov localization model is indeed a special case of the Bayesian Map model by comparing Fig. 2 and Fig. 3. Recall that Kalman filters and particle filters are special cases of Markov localization, as they add hypotheses over the choice of dependency structure made by the Markov localization model. This implies that Kalman filters and particle filters are also special cases of Bayesian Maps. Bayesian Maps can therefore accommodate many different forms, depending on the need or information at hand: for example, a Bayesian Map can be

Program                                              Description                                Specification                       
Relevant Variables: P : perception variable L t : location variable at time t L t ′ : location variable at time t ′ , t ′ > t A : action variable Decomposition: Any Parametric Forms: Any Identification: Any Question:

elementary behaviours: structured like a real-valued Kalman filter for tracking the angle and distance to some feature when it is available. If that feature is not present, or if the linearity hypotheses fail, we can use another Bayesian Map, which may not be a Kalman filter (for example, based on a symbolic variable). Hierarchies of Bayesian Maps (via the abstraction operator) can thus be hierarchies of Markov localization models or hierarchies of Kalman filters, and so on. Moreover, heterogeneous hierarchies of these models can be imagined: ML over KFs, or even n KFs and one ML model. In our view, this would be a potential alternative to the solution of Tomatis et al. [START_REF] Tomatis | A hybrid approach for robust and precise mobile robot navigation with compact environment modeling[END_REF][START_REF] Tomatis | Hybrid simultaneous localization and map building: a natural integration of topological and metric[END_REF].

P (Ai | X), with Ai ⊆ A, X ⊆ {P, L t , L t ′ , A} \ Ai

Combining Bayesian Maps: definition of the abstraction operator and example

Having defined the Bayesian Map concept, we now turn to defining operators for combining Bayesian Maps. The one we present here is called the abstraction of maps. It is defined in Fig. 4 and discussed in the rest of this section.

As stressed above, in a Bayesian Map, the semantics of the location variable can be very diverse. The main idea behind the abstraction operator is to build a Bayesian Map c containing locations that are other Bayesian Maps c 1 , c 2 , . . . , c n . The location variable of the abstract map will therefore take n possible symbolic values, one for each underlying map c i . Each of these maps will be "nested" in the higher-level abstract map, which justifies the use of the term "hierarchy" in our work. Recall that Bayesian Maps are designed for generating behaviours.

In this decomposition, P (L t ) and P (L t ′ ) are defined as uniform distributions. All the terms of the form

P (P i L t i L t ′ i A i | [L t = c]
) are defined as follows: when c = c i , the probabilistic dependency between the variables P i , L t i , L t ′ i , A i of the map c i is supposed unknown, and therefore defined by a uniform distribution. When c = c i , however, this dependency is exactly what the map c i defines. Therefore this term is a question to the description c i but a question that includes the whole subdescription by asking for the joint distribution it defines. Because the last term, P (A | L t L t ′ ), only includes symbolic variables that have a small number of values, it makes sense to define it as a table, which can be easily programmed a priori or learned experimentally.

The abstract Bayesian Map is now fully defined, and, given the n underlying maps, can be built automatically. The last step is to verify that it generates useful behaviours. We will examine the guiding questions of localization, prediction and control.

The localization question leads to the following inference (derivation omitted):

P (L t | P ) ∝ n i=1 P (P i L t i L t ′ i A i | L t ).
The interpretation of this result will be explained with an example in Section 6. The derivations for solving the prediction P (L t ′ | A L t ) and control P (A | L t L t ′ ) questions are also straightforward, given Fig. 4.

Recall that the final goal of any Bayesian Map is to provide behaviours. In the abstract map, this is done by answering a question like

P (A | [L t ′ = c i ] [P = p])
: what is the probability distribution over lower-level behaviours, knowing all values p of the variables of the lower level, and knowing that we want to "go to map c i " (more formally, "reach some location recognized as the lower-level map c i ")? Answering this question thus allows selection of the most relevant underlying behaviour to reach a given high-level goal. The computation is as follows:

P (A | L t ′ P ) ∝ L t n i=1 P (P i L t i L t ′ i A i | L t ) P (A | L t L t ′ ). ( 3
)
This computation includes the localization question, by weighing the probabilities given by the control model P (A | L t L t ′ ). In other words, the distribution over the action variable A includes all localization uncertainties. Each underlying model is used, even when the robot is located at a physical location that this model is not made for. As a direct consequence, there is no need to decide what map the robot is in, nor to switch from map to map: the computation considers all possibilities and weighs them according to their (localization) probabilities. Therefore the underlying maps are not necessarily "mutually exclusive" in a geographical sense.

Experimental validation

We report here an experiment made on the well-known Koala mobile robot platform (K-team company). To keep as much control as possible over our experiments and the different effects we observe, we simplify the sensorimotor system and its environment. We only use the 16 proximeters P x = P x 0 ∧ . . . ∧ P x 15 of our robot, and we keep two degrees of freedom of motor control, via the rotation and translation speeds V rot and V trans. The environment we use is a 5 m × 5 m area made of movable planks (a typical configuration is shown in Fig. 5). The goal of this experiment is to solve a navigation task: we want the robot to go and hide in any corner, as if the empty space in the middle of the area were dangerous.

The first programming step is to analyse this task into subtasks. Three particular situations are relevant for solving the task: the robot can either be near a wall, and it should follow it in order to reach the nearest corner, or the robot can be in a corner, and it should stop, or finally it could be in empty space, and should therefore go straight, so as to leave the exposed area as quickly as possible.

Low-level Bayesian Maps

Given this analysis, the second programming step is to define one Bayesian Map for each of the three situations. They all use the same perception variable P = P x and the same action variable A = V rot ∧ V trans.

The first map, c wall , describes how to navigate in the presence of a single wall, using a location variable L t = θ ∧ Dist: the phenomenon "wall" is summarized by an angle θ and a distance Dist. Therefore, c wall defines P (P x θ t Dist t θ t ′ Dist t ′ V rot V trans | c wall ). We have implemented this map using 12 possible angle values and three different distances. This leads to a compact model that is still accurate enough to solve the subtasks. The dependency structure we choose is (c wall on right hand sides omitted):

P (P x θ t Dist t θ t ′ Dist t ′ V rot V trans) = P (θ t Dist t ) i P (P x i | θ t Dist t ) P (θ t ′ Dist t ′ ) P (V rot | θ t Dist t θ t ′ Dist t ′ )P (V trans | θ t Dist t θ t ′ Dist t ′ ).
P (θ t Dist t ) and P (θ t ′ Dist t ′ ) are uniform probability distributions. Each term of the form P (P x i | θ t Dist t ) is a set of bell-shaped probability distributions 3 that were identified experimentally in a supervised learning phase: we physically put the robot in all 36 possible situations with respect to the wall and recorded proximeter values so as to compute experimental means and standard deviations. Finally, the two control terms P (V rot | θ t Dist t θ t ′ Dist t ′ ) and P (V trans | θ t Dist t θ t ′ Dist t ′ ) were programmed "by hand": given the current angle and distance, and the angle and distance to be reached, what should the motor commands be? This map successfully solves navigation tasks like "follow wall right", "follow wall left", "go away from wall", "stop", using behaviours of the same name. For example, "follow wall right" is defined by the probabilistic question P (V rot V trans | P x [L t ′ = 90, 1 ]): compute the probability distribution on motor variables knowing the sensory input and knowing that the location to reach is θ = 90 , Dist = 1 (wall on the right at medium distance).

This map is an instance where a Kalman filter-based Bayesian Map could have been used instead, for example, if we had required a more accurate angle and distance to the wall using continuous variables. The coarse-grained set of values we used were sufficient for our experiments.

The two other Bayesian Maps we define are the following. 1) c corner describes how to navigate in a corner, using a symbolic location variable that can take four values: F rontLef t, F rontRight, RearLef t and RearRight. This is enough for solving tasks like "quit corner and follow right", "away from both walls", "stop". 2) c emptyspace describes how to navigate in empty space, i.e. when the sensors do not see anything. The behaviours defined here are "straight ahead" and "stop". For brevity, these two Bayesian Maps are not described further here; the interested reader can find details in Diard's PhD thesis [START_REF] Diard | La carte bayésienne -Un modèle probabiliste hiérarchique pour la navigation en robotique mobile[END_REF].

Abstract Bayesian Map

Given these three maps, the third and final programming step is to apply the abstraction operator to them. We obtain a map c with a location variable L t = {c wall , c corner , c emptyspace }. The action variable lists the behaviours defined by the low-level maps: A = {follow wall right, go away from wall, . . .}. The rest of the abstract map is in accordance with the schema of Fig. 4.

We now discuss the localization question. Let us assume that the robot is in empty space: all its sensors read zero. Let us also assume that the robot is currently applying the "straight ahead" behaviour, which sets V rot and V trans near 0 (no rotation) and 40 (fast forward movement), respectively, using sharp bell-shaped distributions.

Let us consider the probability of being in location c emptyspace (with w standing for wall, c for corner and e for emptyspace).

P ([L

t = c emptyspace ] | P ) ∝   P (P w L t w L t ′ w A w | [L t = c emptyspace ]) P (P c L t c L t ′ c A c | [L t = c emptyspace ]) P (P e L t e L t ′ e A e | [L t = c emptyspace ])   .
Of the three terms of the product, two have uniform distributions, and one is the joint distribution given by c emptyspace . This joint distribution gives a very high probability for the current situation, because describing the phenomenon "going straight ahead in empty space" basically amounts to favouring sensory readings of 0 and motor commands near 0 and 40 for V rot and V trans, respectively. The situation is quite the opposite for P ([L t = c wall ] | P ): for example, c wall does not favour this sensory situation at all. Indeed, the phenomenon "I am near a wall" is closely related to the sensors actually sensing something. The probability of seeing nothing on the sensors knowing that the robot is near a wall is very low: P ([L t = c wall ] | P ) will be very low. The reasoning is similar for P ([L t = c corner ] | P ). This computation can thus be interpreted as the recognition of the most pertinent underlying map for a given sensorimotor situation. Alternatively, it can be seen as a measure of the coherence of the values of the variables of each underlying map, or even as a Bayesian comparison of the relevance of models, as assessed by the numerical value of the joint distributions of each lower-level model. Because these distributions include (lower-level) location and action variables, the maps are recognized not only from sensory patterns but also from what the robot is currently doing.

The localization question can therefore be used to assess the "validity zones" of the underlying maps, i.e. the places in the environment where the hypotheses of each model hold. Experimentally, we make the robot navigate in the environment, and we ask at each time step the localization question. We can visually summarize the answer, for example, by drawing values for L t , and reporting the drawn value on a Cartesian map of the environment. A simplified but readable result is shown in Fig. 5. As can be seen, the robot correctly recognizes each situation for which it has a model. Note that the resulting zones are not contiguous in the environment: for example, all the corners of the environment are associated with the same symbol, namely, c corner . This effect is known as perceptual aliasing. However, this very simple representation is sufficient for solving the task that was given to the robot: the behaviour "go hide in any corner" is indeed generated by the abstract map.

Using the abstract Bayesian Map we have programmed in this way, the robot can solve the task of reaching corners. A typical trajectory for the robot, starting from the middle of the arena, is to start by going straight ahead. As soon as a couple of forward sensors sense something, the "empty space" situation is no longer relevant, and the robot applies the best model it has, depending on the correlation between what the sensors see: if it looks like a wall and continues to do so as the robot moves, then the probability for the "wall" model is high; on the other hand, if it instead feels like a corner, then the corner model wins the probabilistic competition. Suppose the robot is near a wall and starts to follow it until a corner is reached. In our first version, the corner model was designed too independently of the wall model: the validity zone of the c corner map was too small and seldom visited by the robot as it passed the corner using the "follow wall right" behaviour, defined by c wall . The robot would then miss the first corner and stop at another one. This shows that the decomposition of the task gives independent subtasks only as a first approximation. We solved the problem by modifying the "corner" model, so that it would recognize a corner on a typical "follow wall right" trajectory.

Conclusion

We have presented the Bayesian Map formalism: it is a generalization of most probabilistic models of space found in the literature. Indeed, it drops the usual constraints on the choice of decomposition, forms, or implementation of the probability distributions. We have also presented the abstraction operator, for building hierarchies of Bayesian Maps.

The experiments we presented are of course to be regarded only as "proofs of concept". Their simplicity also served didactic purposes. However, these experiments, in our view, are a successful preliminary step towards applying our formalism. Part of the current work is of course aimed at enriching these experiments, in particular with respect to the scaling up capacity of the formalism.

Moreover, because each map of the hierarchy is a full probabilistic model, it is potentially very rich. Possible computations based on these maps include questions like the prediction question P (L t ′ | A L t ), which can form the basis of planning processes. Hierarchies of Bayesian Maps can therefore be considered as model-based approaches rather than as purely reactive approaches.

Exploiting such knowledge by integrating a planning process in our Bayesian Map formalism is also part of the ongoing work.

Fig. 3 .

 3 Fig. 3. The Bayesian Map model definition expressed in the BRP formalism.

  Fig. 5. 2D projection of the estimated "validity zones" of the maps c wall , ccorner and cemptyspace. The bottom part of the figure is a screenshot of the localization module of the abstract map: it shows the "comparison" and competition between the underlying models. The winner is marked by the central dot: in this case, the robot was near a wall.

Bell-shape probability distributions approximate Gaussian probability distributions on finite discretized ranges.

Acknowledgements

This work has been supported by the BIBA European project (IST-2001-32115). The authors wish to thank Emmanuel Mazer, Alain Berthoz and Panagiota Panagiotaki for many discussions on this work, and Carla Koike for invaluable comments on drafts of this chapter.

a priori programming or learning of Let us denote a 1 , a 2 , . . . , a k , the k behaviours defined in the n underlying maps, with k ≥ n. In the abstract map, these behaviours can be used for linking the locations c i . The action variable of the abstract map will therefore take k possible symbolic values, one for each behaviour of the underlying maps. To build an abstract map having n locations, the programmer will require n previously defined lower-level maps, which generate k behaviours. The numbers n and k are therefore small, and so the abstract map deals with a small internal space, having retained from each underlying map only a symbol, and having "forgotten" all their details. This justifies the use of the name "abstraction" for this operator. However, this "summary mechanism" has yet to be described: that is what the perception variable P of the abstract map will be used for, as it will be the list of all the variables appearing in the underlying maps:

Given the four variables of the abstract map, we define its joint distribution with the following decomposition:

(2)


Shu-Heng Chen
email: chchen@nccu.edu.tw

Nicolas Navet
email: nnavet@loria.fr

Pretests for genetic-programming evolved trading programs: "zero-intelligence" strategies and lottery trading ⋆

Over the last decade, numerous papers have investigated the use of GP for creating financial trading strategies. Typically in the literature results are inconclusive but the investigators always suggest the possibility of further improvements, leaving the conclusion regarding the effectiveness of GP undecided. In this paper, we discuss a series of pretests, based on several variants of random search, aiming at giving more clearcut answers as to whether a GP scheme, or any other machine-learning technique, can be effective with the training data at hand. Precisely, pretesting allows us to distinguish between a failure due to the market being efficient of due to GP being inefficient. The analysis is illustrated with GP-evolved strategies for three stock exchanges exhibiting different trends.

Motivation and Introduction

The computational intelligence techniques such as genetic programming 3 , with their continuous advancement, persistently bring us something positive to expect, and incessantly push the application domain to more challenging issues. However, sometimes, the costs and benefits of using these advanced CI techniques are uncertain. Usually the benefits are not assured, while the costs are immediate. On the one hand, the CI techniques are frequently used as intensive search algorithms, which are inevitably computationally demanding, and take up a great amount of computational resources. On the other hand, whether there is a needle in the haystack remains dubious. 4 Certainly, if such a needle does not ⋆ An extended version of this paper will appear as chapter 8 of the book Computational Intelligence in Economics and Finance -Volume 2 , Springer Verlag, to be published in 2007. 3 Although, in this paper, we only focus on genetic programming, but the general ideas and some specific implementations may also be applicable to other computational intelligence techniques used to induce trading strategies. 4 For example, in the financial application domain, the lack of such a needle may be due to the efficient market hypothesis or the no-arbitrage condition.

exist at all, the all efforts are made to no avail. Given this asymmetry between costs and benefits, it would be economical, at the first stage, to test the existence of such a needle before a fully-fledged version of search is applied. We refer to this procedure as a pretest.

The pretest procedure proposed here is in a sense similar to the pretests used in econometrics where the estimator of an unknown parameter is chosen on the basis of the outcome of a pretest ( [START_REF] Giles | Pre-test Estimation and Testing in Econometrics: Recent Developments[END_REF]). Pretesting, also known as "data-snooping" in finance, classically serves to select the right model that will be used later on for forecasting purpose ( [START_REF] Danilov | Forecast Accuracy After Pretesting with an Application to the Stock Market[END_REF][START_REF] Sullivan | Data-Snooping, Technical Trading Rule Performance, and the Bootstrap[END_REF]). More broadly, pretesting can be considered to be a practice of a sequential decision-making process, which is used when the decision involves a great deal of uncertainty, and the costs of making a wrong decision are huge. 5 In this case, at the first stage, we would like to expend some limited resources in probing into gaining some initial information, e.g. the distribution of a very uncertain environment, while in the later stages, we will make our decision based on the gauged distribution.

The reasoning behind prestesting is very intuitive, and [START_REF] Kaboudan | A Measure of Time Serie's Predictability Using Genetic Programming Applied to Stock Returns[END_REF] is the first to apply this idea to the financial application of genetic programming (GP). [START_REF] Kaboudan | A Measure of Time Serie's Predictability Using Genetic Programming Applied to Stock Returns[END_REF] proposed a measure known as the η statistic. The η statistic is a measure of predictability. Basically, using a simple (vanilla) version of GP, one can first gauge the predictability based on η. When η is low or close to zero, it indicates that there is nothing to forecast. So, the use of fully-fledged GP is not advised. The virtue of doing this is to distinguish two kinds of possibilities when we see a failure of an initial attempt based on simple GP. First, the series itself has nothing to forecast; second, GP has not been used appropriately. Understanding this distinction can result in big differences in our second stage of the decision. In the former case, we may simply give up any further search to avoid wasting resources. In the latter case, we should keep on exploring different deliberations of GP to search for potential gains before a final conclusion can be made. In either case, we have a clear-cut situation. However, when a pretest is absent, we become less conclusive: we are no longer sure whether the problem is due to the non-existence of the needle, or the improper use of GP.

Unfortunately, in most financial trading applications of GP, a pretest has been largely neglected. 6 We think that this negligence may give rise to many inconclusive results. Typically, what happens is that the results from using GP are not very convincing, but the investigators always suggest directions for further 5 The problem of sequential decision making under incomplete knowledge has been studied by researchers in various fields, such as optimal control, psychology, economics, and game theory. 6 This may not be completely so. In fact, most earlier studies selected the buy-and-hold strategies or a risk-free investment (e.g., treasury bills) as the benchmark. However, the conclusion that "GP performs better than buy-and-hold in a bearish market and worse in a bullish market" is often found in the literature. However, nothing different can be expected since buy-and-hold is the worst possible strategy in a steadily decreasing market and the best possible strategy in a steadily increasing market. This shows the limits of choosing buy-and-hold as a benchmark. See, for example, [5].

improvement, leaving the actual conclusion regarding the effectiveness of GP undecided. Therefore, this study attempts to provide practical pretesting procedure aimed at reducing the number of cases where the conclusion is inconclusive. Needless to say, there are various ways of implementing different types of pretesting. For example, the η statistic mentioned above can be used as a pretest, as [START_REF] Kaboudan | A Measure of Time Serie's Predictability Using Genetic Programming Applied to Stock Returns[END_REF] did, but that is mainly applied to forecasting time series. That a series is to a certain extent predictable does not necessarily imply that we can develop profitable trading strategies. For example, the predictability horizon might be too short, the fluctuation might not be volatile enough to cover the roundtrip transaction costs or, simply, the right trading instrument might not be available (e.g., no short selling in a downward oriented market) or else they are some regulation and rules (e.g., the "uptick rule" makes intraday trading with short selling more difficult). Consequently, literature on forecasting with GP and literature on trading with GP usually are separated. Therefore, in this paper, we attempt to develop pretest procedures that are more suitable for trading purposes.

More precisely, we will propose several different styles of pretests, which when put together can help us decide whether there are hidden patterns to be discovered and whether GP is properly designed to do the job. The essential idea underlying all proposed pretests is to compare the performance of GP with random trading strategies or behavior. However, as we shall see in Section 2, just making trading strategies or trading behavior arbitrarily random is not sufficient to provide a fair and informative comparison. To do so, some constraints are expected, and the intriguing point is how to impose these constraints properly.

The rest of the paper is organized as follows. Section 2 provides a detail formulation of four pretests. The first three are concerned with the trading strategies, whereas the last one is concerned with the trading behavior. Normally, trading behavior comes from trading strategies, and they cannot be separated; however, when randomness is introduced, difference between the two may arise. In particular, in the vein of algorithmic complexity, random trading strategies can imply trading behavior actually using knowledge, while random trading behavior presumably excludes such a possibility. We, therefore, intentionally distinguish between the two by calling the former zero-intelligence strategies, and the latter lottery trading. Section 3 discuss how to use these proposed tests together to make a better judgement given the initial results we have. Section 4 illustrates the proposed pretests based on the real detail and the experimental designs detailed in the appendix. Section 5 gives the concluding remarks.

Pretests: description and rationale

In this section, we describe a series of 4 pretests and discuss their purpose and implementation. Of the 4 pretests, we highlight that 2 are of particular interest and, as shown in Section 3, enable us to gain complementary knowledge on the data under study and on the efficiency of the GP's implementation. In the following, we consider GP with a validation stage before the actual testing on the out-of-sample data. Validation means that the best rules induced on the training interval are further selected on the unseen data, the validation period, before being applied out-of-sample. The validation step is a device to fight overfitting 7 that has been widely used in earlier GP work (see for instance [7,8]). Note that our pretest proposals remain valid for GP without the validation step except that pretest 2 replaces pretest 1, which requires validation.

GP versus equivalent intensity random search

The basic idea here is to compare the outcome of GP with an equivalent intensity random search. We say that two search algorithms are equivalent in terms of search intensity if their execution leads to the evaluation of the same number of different trading strategies on the training data. For instance, let us consider GP with the parameters chosen for this study: a population of 500 individuals evolved over 100 generations. In the first approximation, the equivalent random search (ERS) would consist of evaluating 50,000 randomly created solutions. In practice, search algorithms sometimes rediscover identical solutions over the course of their execution. This can be detected by keeping track of all created individuals since the beginning of the execution, and, in doing so, useless fitness evaluations can be skipped, which actually saves computing time when the fitness function is rather time-consuming as it is in our context. Since, computationally speaking, what is preponderant is the fitness evaluation, and since the extent to which GP re-discovers the same individuals is very dependent upon the implementation, we impose that our definition of equivalent search intensity only accounts for unique individuals, i.e. individuals which require evaluation. We consider two solutions to be different if their expression is syntactically different 8 , in our context, if the trees representing the programs are different.

The three following pretests compare GP with a random search both with and without training and validation stage. In the latter search technique, the biologically inspired evolution process of GP is simply replaced by the creation of solutions at random. Since with random search the strategies do not benefit 7 The actual effectiveness of validation in this context is, however, still an open question, see [5] and [6]. 8 Two individuals can be syntactically different while being equivalent in the sense that they lead to equivalent trading decisions, the equivalence could thus also be defined in terms of semantics. With symbolic simplification using rewriting rules and interval arithmetic on the function arguments, we could detect that some syntactically different individuals are in fact semantically identical. However, there is no way of making sure that all duplicates will be detected and the implementation of this procedure would be so complex and time consuming at run time that, in our opinion, a definition based on semantics would be of little practical interest. Alternatively, the equivalence in search intensity could be defined in terms of equivalent computing time. However there is such a difference of complexity between a fully-fledged GP implementation and random search that it is hard to imagine how we can ensure that the two implementations have been optimized in a similar manner, while a better implementation of GP for instance may lead us to come to an opposite conclusion.

from the "intelligence" resulting from the evolution or learning process, we dub randomly created solutions as zero-intelligence trading strategies.

For each pretest i, we formulate the null hypothesis H i,0 that GP does not outperform the technique it is compared with at pretest i, where the alternative hypothesis is denoted by H i,1 .The experiments will provide us with the answer on whether H i,0 should be rejected in favour of H i,1 or not.

Pretest 1: GP versus equal search intensity random search with training and validation stage. The implementation of the random search strategy is straightforward: parameters of GP are set in such a way that only the initial generation, where individuals are created at random, is used. The size of the initial population is adjusted so that the resulting search intensity is identical to the one of the regular GP.

-Hypothesis H 1,0 cannot be rejected: the first explanation that can be envisaged is that, GP or not, there is nothing essential to be learned from the past. It that case GP would strongly "overfits" the training data, possibly explaining that its out-of-sample performance is worse than with a random search. This can be due by the market being efficient or because the training interval is very dissimilar to the out-of-sample9 . Another explanation is that the GP machinery is not working properly, for instance due to a wrong choice of the function/terminal sets, because the parameters are inappropriate (e.g. too low search intensity), or the genetic operators are unable to create betterthan-random individuals. -Hypothesis H 1,0 is rejected in favour of H 1,1 : there may be something to learn from the past and GP, with the chosen parameters, may be effective in that task.

Rejecting H 1,0 is of course a first indication of the efficiency of GP but we cannot rule out the case where there would nothing useful to learn on the data at hand and GP would beat random search by mere luck. We will see in Section 3, that further investigation may provide additional evidence to answer that question.

Pretest 2: GP versus equal search intensity random search with training but without a validation stage. Here, the best random solutions on the training interval are applied directly to the out-of-sample period. With regard to pretest 1, pretest 2 could give us some insight about how effective is validation as a device to fight against overfitting. However, since overfitting is unlikely to occur with random solutions, the rationale for using pretest 2 is unclear and it will not be further considered in this study. A more direct and effective way to evaluate the effect of the validation stage is simply to compare regular GP with and without validation 10 .

Pretest 3: GP versus equal search intensity random search without training and without validation stage. In pretest 3, the selection of the strategies on the training set is removed: a large number random strategies are created and applied directly out-of-sample. The performance is evaluated as the average performance (e.g. average total return) over the set of random strategies.

Comparing the outcome of pretest 3 with regard to pretest 1 and regular GP tells us something about how effective the selection process is, the extent to which a top performing rule on the training and validation sets will keep on performing well out-of-sample. If strategies selected by GP or random search on the training and validation intervals have some predictive ability out-of-sample, it provides use with some evidence that there is something to learn from the past. It is worth pointing out that the randomness of the strategies is here constrained by the GP language: rules can only be made with GP functions/terminals organized according to the typing scheme. For instance, it is possible that the GP language is not sufficiently expressive to define a rule consisting in buying and selling every other period11 . In the remainder of this study, we will consider pretest 4, presented in Section 2.2, that is similar in spirit to prestest 3, but is more random in the sense that it does not possess the bias in randomness induced by the GP language.

GP versus lottery trading

We refer to lottery trading as a strategy that would consist in making the investment decision at random on the basis of the outcome of a random variable.

In its simplest form, the random variable would follow a Bernoulli distribution where the parameter p expresses the probability to take a long position and 1-p the probability to be out of the market.

In our context, this requires refinement since we are interested in profitability and profitability takes into account transaction costs. So, to allow a fair comparison with GP, we should make sure that the expected number of transactions for lottery trading is the same as for GP. We refer to the expected number of transactions per unit of time as the frequency of a trading strategy. Another important characteristic of a trading strategy is what we term its intensity, i.e. the number of periods where a position12 "in the market" is held, over the length of the trading interval. We should also enforce lottery trading to have the same expected intensity as GP to avoid misleading results, for instance, the case where, given its frequency, the intensity of lottery trading is not sufficient to cover the transaction costs with the volatility of the market under study.

One denotes by F GP and I GP respectively the average frequency and average intensity observed for the set of GP evolved rules applied on the testing interval over all GP runs, N GP is the number of transactions leading to F GP . For the experiments made in the following, a sequence of investment decisions S LT resulting from lottery trading is generated at random according to the following procedure:

the intensity for lottery trading,

I LT , is uniformly chosen in [I GP • (1 - α), min(1, I GP • (1 + α))] with 0 ≤ α ≤ 1.
In a first step, S LT is made of the '0' positions (i.e. out of the market) followed by the block of '1' positions (i.e. in the market) corresponding to I LT , -the number of transactions N LT is uniformally chosen in the set of integer values that are even

13 in interval [N GP •(1-α), N GP •(1+α)].
The block of '1' is subdivided at random in N LT /2 sub-sequences and each sub-sequence is inserted at random inside the block of '0'. This design avoids the problem of overlapping among the '1' sub-sequences that may occur with other schemes.

We formulate the pretest comparing GP and lottery trading and denote by H 4,0 the null hypothesis that GP does not outperform lottery trading.

Pretest 4: GP versus lottery trading. Obviously, if GP is not able to outperform lottery trading, it gives strong evidence that GP will not be good at evolving effective trading strategies with the data at hand. In Section 3, we shall discuss this point in more detail.

3 What does the pretest tell us ?

The outcomes of the pretests provide us with answers to the following two questions: is there something essential to learn on the training data that can be of interest for the out-of-sample period ? Does the GP implementation show some evidence of effectiveness in that task ? Clearly, before actually trading with GP evolved programs, these two questions must be answered with reasonable certainty; the rest of this section explains how pretests may help in that regard.

3.1 Question 1: is there something to learn ?

The null hypothesis H 4,0 corresponding to pretest 4 has been presented in Section 2.2. We introduce pretest 5 that will be used in conjunction with pretest 4.

Pretest 5: equivalent intensity random search with training and validation versus lottery trading. Here, we compare lottery trading to a random search with training and validation, and a search intensity equivalent to the one used for GP in pretest 4. The null hypothesis H 5,0 is that the equivalent intensity random does not outperform lottery trading on the out-of-sample data.

Depending on the validity of H 4,0 and H 5,0 , we can draw the conclusions that are summarized in Table 1.

H4,0 H5,0 Interpretation case 1 ¬R ¬R there is evidence that there is nothing to learn case 2 R ¬R there may be something to learn (weak certainty) case 3 R R there is evidence that there is something to learn case 4 ¬R R there may be something to learn (weak certainty) Table 1. Information drawn from the outcomes of pretest 4 and pretest 5 (¬R means that the null hypothesis Hi,0 cannot rejected while R means that the hypothesis is rejected in favour of the alternative hypothesis).

In case 1, best solutions on the training intervals, obtained with 2 different search algorithms, do not perform better than lottery trading on the out-ofsample period. This suggests to us than there is nothing to learn. In case 2, GP outperforms lottery trading but random search does not; it is possible that there is something to learn, but that the selected random rules do not have a sufficient predictive ability. Anyway, this lead us to a less certain conclusion than in case 3 where both search techniques outperform lottery trading. Finally case 4 is a special case where random search performs better than lottery trading but GP does not. The whole evolutionary process of GP has thus a detrimental effect and a possible explanation is that GP-induced solutions overfit the training data.

Question 2: is the GP machinery working properly ?

The second question we ought to ask is whether GP is effective. Of course, this cannot be answered with the data at hand if pretests 4 and 5 have shown that there is nothing to be learned (case 1 in Table 1). In addition, in case 4 of Table 1, we already know that GP is not efficient since, by transitivity, it is outperformed by the random search-based algorithm. Thus, the only two cases where one really needs to proceed to further examination are case 2 and case 3. The validity of the null hypothesis H 1,0 , which can be tested with pretest 1, gives a helpful insight into the answer: only if H 1,0 should be rejected can we conclude that GP shows some real effectiveness. We would like to stress that rejecting H 1,0 is far from implying profitability, but beating a mere random search algorithm on a difficult problem with an infinite search space is the bare minimum one can expect from GP.

The aim of the experiments is to evaluate the extent to which the pretests proposed are reliable. The methodology adopted here is to check if the outcomes of the pretests are consistent with results already published in the literature. We call GP2 the GP implementation developed for this study and GP1 the software14 used in [5], which will constitute our benchmark. The GP2 control parameters, as close as possible to the ones used in [5] for GP1, are summarized in Table 1 (Appendix A).

The traded instruments are the indexes of 3 stock exchanges: the TSE 300 (Canada), the Nikkei Dow Jones (Japan) and the Capitalization Weighted Stock Index (Taiwan). They have been chosen among the 8 markets studied in [5] because they exhibit the main evolution patterns that can be found in the set of 8 markets. The aim of GP is to induce the most profitable strategy, measured by the accumulated return, for trading the stock exchange index. The use of short selling is possible. We adopt what is done classically in literature in terms of datapreprocessing and use normalized data that is obtained by dividing each day's price by a 250-day moving average15 . In a way similar to what is done usually, we subdivide the whole dataset into three sections: the training, validation and outof-sample test periods. For each stock index considered, 3 different out-of-sample test periods of 2 years each (i.e. 1999-2000, 2001-2002, 2003-2004) follow a 3year validation and a 3-year training period. In the following, the term market refers to a stock exchange during a specific out-of-sample period. For instance, market Canada-1 (C1 for short) is the TSE 300 during the out-of-sample period 1999-2000. Hypothesis testing is performed with the Student's t-test at a 95% confidence level. The samples for statistics are constituted of the results of 50 GP runs, 50 runs of equivalent search intensity random search with training and validation (ERS) and 100 runs of lottery trading (LT).

In 4 out of the 9 markets (i.e. C3, J2, T1, T3), there is evidence that there is something to learn from the training data (case 3 in Table 1). This is consistent with [5] where GP2 performs outstandingly on these 4 markets (respective total return: 0.34, 0.17, 0.52, 0.27 with GP1). In markets C1, J3 and T2, pretests 4 and 5 suggest to us that there is nothing to learn (case 1). Except for C1, GP2 also performs poorly (-0.18 for J3 and -0.05 for T2). Finally, in the 3 markets where GP2 is shown to beat ERS (H 1,0 is rejected in favor of H 1,1 for J1, J2 and T1), the GP results are very good : both GP1 and GP2 produce positive returns and outperform the buy-and-hold strategy.

Although more comprehensive tests are needed, the experiments conducted here show some preliminary evidence that the proposed pretests possess some predictive ability. Indeed, when the outcome is "nothing to learn", the two GP implementation perform very poorly (except in one case). On the contrary, when the pretests suggest that there is something to learn, at least one implementation does well, and when GP2 is more efficient than random search (i.e. ERS), GP1 from [5] is efficient too. In the light of the pretests, we should also conclude that our GP implementation (i.e. GP2) is more efficient than ERS (GP2 outperforms ERS in 3 markets while ERS never beats GP2 with statistical significance). However, in our experiments, searching trading rules at random, with the same set of functions and terminals as used in GP, is usually enough to come up with trading systems that outperform lottery trading when GP does as well. This suggests to us that GP2 may only be able to take advantage of "simple" regularities in the data.

Conclusions

The main purpose of this paper is to enrich the earlier research on Genetic Programming (GP) induced market-timing decisions by proposing pretests aiming to shed light on the GP results. In actual fact, in the literature, the results of applying GP for market-timing decisions are typically not very convincing, but the investigators always suggest the possibility of further improvements. If the investigators can first convince that there is something to learn and that GP is suitable for that task, then their conclusion would be less vague and uncertain. We propose here a series of pretests, where GP is tested against a random behavior (lottery trading) and against strategies created at random (zero-intelligence strategies), that aim to answer these two crucial questions. Of course there is the risk of getting a wrong pretest result and the possible reasons why GP may have failed should be thoroughly investigated before drawing a conclusion. But, in the end, analyzing the results in the light of the pretests should help draw more fine-grained conclusions. A Genetic programming settings

Program GP2 implements strongly typed GP with the set of functions and terminals described in Table 1. The parameters here are basically identical to the ones in [5] (program GP1) except when fine-tuning GP2 have highlighted that better results may be obtained with different parameters. Precisely, we make use of more elitism, the size of the tournament selection is set to 5 and numerical mutation is implemented.

  5. S.-H. Chen and T.-W. Kuo and K.-M. Hoi: Genetic Programming and Financial Trading: How Much about "What we Know". In: Handbook of Financial Engineering. Kluwer Academic Publishers (2006) Forthcoming. 6. S.-H. Chen and T.-Z. Kuo: Overfitting or Poor Learning: A Critique of Current Financial Applications of GP. In Springer-Verlag, ed.: Proceedings of the Sixth European Conference on Genetic Programming (EuroGP-2003). Number 2610 in LNCS (2003) 34-46 7. F. Allen and R. Karjalainen: Using Genetic Algorithms to Find Technical trading rules. Journal of Financial Economics 51 (1999) 245-271 8. C. Neely and P. Weller and R. Dittmar: Is Technical Analysis in the Foreign Exchange Market Profitable? A Genetic Programming Approach. Journal of Financial and Quantitative Analysis 32(4) (1997) 405-427

Fig. 1 .

 1 Fig. 1. GP control parameters

In [5], numerous experiments have highlighted that when training and out-of-sample data sets are very "dissimilar", for instance if the market exhibits an opposite trend, then there is little chance that GP will perform well out-of-sample.

Period refers to the granularity of time used for trading, for instance, one second or one day.

Implicitly, we consider here the trading of a single instrument, e.g. an index, where 2 decisions are possible at each time period: be in or be out of the market without short selling, or with short selling as implemented in [5], holding a long position or a short position. The concept remains valid where one can be holding a long position, a short position or be out of the market. One can also define the intensity and the frequency of a strategy for each instrument traded.

NLT has to be even since a "buy" transaction is followed by a sell transaction and no positions are left open.

Although both programs have been developed by members of the AI-ECON Research Center, they have not been written by the same persons and do not share a single line of code. Furthermore GP2, which is based on the Open-Beagle library (see http://beagle.gel.ulaval.ca/), implements strongly-typed GP.

15 See [5] for a discussion about how non-normalized data affects the performance of GP.

Acknowledgment. This research was conducted when the second author (Nicolas Navet) was visiting researcher at the AI-ECON Research Center, National Chengchi University (NCCU), Taipei, Taiwan. The financial support from the AI-ECON Research Center as well as NCCU and INRIA is greatly acknowledged. The authors would like also to acknowledge the grant from National Science Concil #95-2415-H-004-002-MY3.