Olivier Lebeltel

Pierre Bessiere
email: pierre.bessiere@imag.fr

Julien Diard

Emmanuel Mazer

O Livier

P IERRE B ESSIÈRE , J ULIEN D IARD L Ebeltel

E Mmanuel

M Azer

Bayesian Robot Programming

Keywords: bayesian robot programming, control of autonomous robots, computational architecture for autonomous systems, theory of autonomous systems 1. Partially Observable Markov Decision Process. 2. Hidden Markov Models

come

Introduction

We assume that any model of a real phenomenon is incomplete . There are always some hidden variables, not taken into account in the model, that influence the phenomenon. The effect of these hidden variables is that the model and the phenomenon never have the same behavior.

Any robot system must face this central difficulty: how to use an incomplete model of its environment to perceive, infer, decide and act efficiently? We propose an original robot programming method that specifically addresses this question.

Rational reasoning with incomplete information is quite a challenge for artificial systems. The purpose of Bayesian inference and learning is precisely to tackle this problem with a wellestablished formal theory. BRP heavily relies on this Bayesian framework.

We present several programming examples to illustrate this approach and define descriptions as generic programming resources. We show that these resources can be used to incrementally build complex programs in a systematic and uniform framework. The system is based on the simple and sound basis of Bayesian inference. It obliges the programmer to explicitly state all assumptions that have been made. Finally, it permits effective treatment of incomplete and uncertain information when building robot programs.

The paper is organized as follows. Section 2 offers a short review of the main related work, Section 3 is dedicated to definitions and notations and Section 4 presents the experimental platform. Sections 5 to 9 present various instances of Bayesian programs: learning simple reactive behaviors; instances of behavior combinations; sensor fusion; hierarchical behavior composition; situation recognition; and temporal sequencing. Section 10 describes a combination of all these behaviors to program a robot to accomplish a night watchman task. Finally, we conclude with a synthesis summing up the principles, the theoretical foundations and the programming method. This concluding section stresses the main advantages and drawbacks of BRP.

Related work

Our work is based on an implementation of the principle of the Bayesian theory of probabilities.

In physics, since the precursory work of [START_REF] Laplace | Mémoire sur la probabilités des causes par les évènements; Mémoire de l'académie royale des sciences[END_REF][START_REF] Laplace | Mémoire sur la probabilités des causes par les évènements; Mémoire de l'académie royale des sciences[END_REF], numerous results have been obtained using Bayesian inference techniques (to take uncertainty into account) and the maximum entropy principle (to take incompleteness into account). The late Edward T. Jaynes proposed a rigorous and synthetic formalization of probabilistic reasoning with his "Probability as Logic" theory [START_REF] Jaynes | On the rationale of maximum-entropy methods[END_REF]. A historical review of this approach was offered by [START_REF] Jaynes | On the rationale of maximum-entropy methods[END_REF] and an epistemological analysis, by [START_REF] Matalon | Epistémologie des probabilités[END_REF]. Theoretical justifications of probabilistic inference and maximum entropy are numerous. The entropy concentration theorems [START_REF] Jaynes | On the rationale of maximum-entropy methods[END_REF][START_REF] Robert | An entropy concentration theorem: applications ; in artificial intelligence and descriptive statistics[END_REF] are among the more rigorous, Cox theorem [START_REF] Cox | The algebra of probable inference[END_REF] being the most well known, although it has been partially disputed recently by Halpern (1999a;1999b). Numerous applications and mathematical tools have been developed [START_REF] Smith | Maximum-Entropy and bayesian methods in inverse problems[END_REF]Tarentola, 1987;[START_REF] Bretthorst | Bayesian spectrum analysis and parameter estimation[END_REF]Erickson & Smith, 1988a;Erickson & Smith, 1988b;[START_REF] Mohammad-Djafari | Maximum entropy and bayesian methods[END_REF][START_REF] Kapur | A robot navigation architecture based on partially observable Markov decision process models[END_REF].

In artificial intelligence, the importance of reasoning with uncertain knowledge has been recognized for a long time. However, the Bayesian approach clearly appeared as one of the principle trends only since the proposal of Bayesian nets [START_REF] Pearl | Probabilistic reasoning in intelligent systems : Networks of plausible inference[END_REF] and graphical models (Lauritzen & Spiegehalter, 1988;[START_REF] Lauritzen | Graphical Models[END_REF][START_REF] Jordan | Learning in Graphical Models[END_REF][START_REF] Frey | Graphical Models for Machine Learning and Digital Communication[END_REF]. Bayesian inference has been proved to be an NP-hard problem [START_REF] Cooper | The computational complexity of probabilistic inference using Bayesian belief networks[END_REF]. However, very important technical progress has been achieved recently which permits approximated computation in reasonable time [START_REF] Saul | Mean Field Theory for Sigmoid Belief Networks[END_REF][START_REF] Zhang | Exploiting Causal Independence in Bayesian Network Inference[END_REF][START_REF] Delcher | Logarithmic-Time Updates and Queries in Probabilistic Networks[END_REF][START_REF] Darwiche | Query DAGs: A Practical Paradigm for Implementing Belief-Network Inference[END_REF][START_REF] Koller | Object-Oriented Bayesian networks[END_REF][START_REF] Ruiz | Probabilistic Inference from Arbitrary Uncertainty using Mixtures of Factorized Generalized Gaussians[END_REF]Jaakola & Jordan, 1999;[START_REF] Jordan | An introduction to variational methods for graphical models[END_REF].

Recent robot programming architectures [START_REF] Aji | The Generalized Distributive Law[END_REF][START_REF] Borrelly | The ORCCAD Architecture[END_REF][START_REF] Schneider | ControlShell: A Software Architecture for Complex Electromechanical Systems[END_REF][START_REF] Dekhil | Instrumented Sensor System Architecture[END_REF][START_REF] Mazer | START: an Industrial System for Teleoperation[END_REF] are in general not concerned with the problem of uncertainty. In robotics, the uncertainty topic was either related to calibration (Bernhardt & Albright, 1993) or to planning problems [START_REF] Brafman | Applications of a logic of knowledge to motion planning under uncertainty[END_REF]. In the latter case, some authors have considered modeling the uncertainty of the robot motions when planning assembly operations [START_REF] Lozano-Perez | Automatic synthesis of fine-motion strategies for robots[END_REF][START_REF] Donald | A geometric approach to error detection and recovery for robot motion planning with uncertainty[END_REF] or modeling the uncertainty related to the position of the robot in a scene [START_REF] Kapur | A robot navigation architecture based on partially observable Markov decision process models[END_REF]. More recently Bayesian techniques have been largely used in POMDP 1 to plan complex paths in partially known environments [START_REF] Kaelbling | Partially observable Markov decision processes for artificial intelligence ; Reasoning with Uncertainty in Robotics[END_REF][START_REF] Kaebling | Acting Under Uncertainty: Discrete Bayesian Models for Mobile-Robot Navigation[END_REF]Koening & Simmons, 1998;[START_REF] Kaebling | Planning and Acting in Partially Observable Stochastic Domains[END_REF][START_REF] Chapman | Learning strucured reactive navigation plans from executing MDP navigation policies[END_REF][START_REF] Lane | Toward hierachical decomposition for Planning in Uncertain Environments[END_REF] or for action selection [START_REF] Rosenblatt | Optimal Slection of Uncertain Actions by Maximizing Expected Utility[END_REF]. HMM 2 are also used to plan complex tasks and recognize situations in complex environments [START_REF] Aycard | Architecture de contrôle pour robot mobile en environnement intérieur structuré ; PhD. thesis[END_REF][START_REF] Thrun | Bayesian landmark learning for mobile robot localization[END_REF]. Finally, a lot of works have been done about probabilistic localization and navigation [START_REF] Shatkay | Learning Models for Robot Navigation[END_REF] either with probabilistic occupancy grids [START_REF] Konolidge | Improved Occupancy Grids for Map Building[END_REF], Markov localization [START_REF] Thrun | A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots[END_REF][START_REF] Gutmann | Experimental comparison of localization methods[END_REF][START_REF] Murphy | Bayesian Map Learning in Dynamic Environments[END_REF][START_REF] Fox | A Probabilistic Approach to Collaborative Multi-Robot Localization[END_REF] correlation-based Markov localization [START_REF] Konolidge | Markov Localization using Correlation[END_REF], Particle filters [START_REF] Fox | Particle filters for mobile robot localization[END_REF] or Kalman filtering (Roumeliotis & Bekey, 2000a;Roumeliotis & Bekey, 2000b).

However, to the best of our knowledge, the design of a robot programming system and architecture solely based on Bayesian inference has never been investigated before the PhD of Olivier Lebeltel, summarized in the present paper (Lebetel, 1999;[START_REF] Diard | Bayesian Learning Experiments with a Khepera Robot in Experiments with the Mini-Robot Khepera[END_REF]Lebeltel et al., 2000;Diard & Lebeltel, 2000). A paper by Thrun [START_REF] Thrun | Towards programming tools for robots that integrate probabilistic computation and learning[END_REF] explored this same direction but with less generality. BRP is a simple and generic framework for robot programming in presence of incompletness and uncertainty. It may be used as a unique formalism to restate and compare numerous classical probabilistic models such as for instance, Bayesian Network (BN), Dynamic Bayesian Network (DBN), Bayesian Filters, Hidden Markov Models (HMM), Kalman Filters, Particle Filters, Mixture Models, or Maxim Entropy Models. This is detailed in a survey by Bessiere [START_REF] Coué | Using Bayesian Programming for Multi-Sensor Multi-Target Tracking in Automotive Applications[END_REF].

Finally, a presentation of the epistemological foundations of BRP may be found in two articles by Bessière (Bessière et al., 1998a;Bessière et al., 1998b).

Basic concepts

In this section, we introduce the concepts, postulates, definitions, notations and rules that are necessary to define a Bayesian robot program.

It may be read twice, at first rapidly to acquire the main concepts, and revisited after the instances sections (5 to 11) to understand in detail the formal definitions.

Definition and notation

Proposition

The first concept we will use is the usual notion of logical proposition . Propositions will be denoted by lowercase names. Propositions may be composed to obtain new propositions using the usual logical operators:

denoting the conjunction of propositions and , their disjunction and the negation of proposition .

Variable

The notion of discrete variable is the second concept we require. Variables will be denoted by names starting with one uppercase letter. By definition, a discrete variable is a set of logical propositions such that these propositions are mutually exclusive (for all with , is false) and exhaustive (at least one of the propositions is true). stands for «variable takes its value». denotes the cardinal of the set (the number of propositions ).

The conjunction of two variables and , denoted , is defined as the set of propositions . is a set of mutually exclusive and exhaustive logical propositions. As such, it is a new variable 3 . Of course, the conjunction of variables is also a variable and, as such, it may be renamed at any time and considered as a unique variable in the sequel.

Probability

To be able to deal with uncertainty, we will attach probabilities to propositions.

We consider that, to assign a probability to a proposition , it is necessary to have at least some preliminary knowledge , summed up by a proposition . Consequently, the probability of a proposition is always conditioned, at least, by . For each different , is an application assigning to each proposition a unique real value in the interval . Of course, we will be interested in reasoning on the probabilities of the conjunctions, disjunctions and negations of propositions, denoted, respectively, by , and . We will also be interested in the probability of proposition conditioned by both the preliminary knowledge and some other proposition . This will be denoted .

For simplicity and clarity, we will also use probabilistic formula with variables appearing instead of propositions. By convention, each time a variable appears in a probabilistic formula , it should be understood as . For instance, given three variables , and , stands for:

[E3.1]

Inference postulates and rules

This section presents the inference postulates and rules necessary to carry out probabilistic reasoning.

3. By contrast, the disjunction of two variables, defined as the set of propositions , is not a variable. These propositions are not mutually exclusive.

ab ∧ ab a b ∨ a ¬ a Xx i ij , ij ≠ x i y j ∧ x i x i Xi th X Xx i XY X Y ⊗ XY × x i y j ∧ XY ⊗ n x i y j ∨ a π a π π . π | () P aa π | () P 01 , [] ab ∧π | () P ab ∨π | () P a ¬ π | () P a π ba b π ∧ | () P X Φ X () x i ∀ X ∈Φ x i () , XY Z XY ⊗ Z π ⊗ | () P X π | () P = x i ∀ X ∈ y j ∀ Y ∈ z k ∀ Z ∈ ,, x i y j ∧ z k π ∧ | () P x i π | () P =

Conjunction and normalization postulates for propositions

Probabilistic reasoning needs only two basic rules:

1-The conjunction rule , which gives the probability of a conjunction of propositions.

[E3.2]

2-The normalization rule , which states that the sum of the probabilities of and is one.

[E3.3]

For the purpose of this paper, we take these two rules as postulates 4 . As in logic, where the resolution principle [START_REF] Robinson | A Machine Oriented Logic Based on the Resolution Principle[END_REF][START_REF] Robinson | Logic : Form and Function[END_REF] is sufficient to solve any inference problem, in discrete probabilities, these two rules ([E3.2], [E3.3]) are sufficient for any computation. Indeed, we may derive all the other necessary inference rules from those two, especially the rules concerning variables:

1 Conjunction rule for variables:

Bayesian Programs

We define a Bayesian program as a mean of specifying a family of probability distributions. Our goal is to show that by using such a specification one can effectively control a robot to perform complex tasks.

The constituent elements of a Bayesian program are presented in Figure 1: • A program is constructed from a description and a question. • A description is constructed from preliminary knowledge and a data set.

• Preliminary knowledge is constructed from a set of pertinent variables, a decomposition and a set of forms. • F orms are either parametric forms or Bayesian programs.

Description

The purpose of a description is to specify an effective method to compute a joint distribution on 4. See some references on justifications of these two rules in § 2.

∧ π | () P a π | () P baπ ∧ | () P × = b π | () P abπ ∧ | () P × = aa ¬ a π | () P a ¬ π | () P +1 = XY ⊗ π | () P X π | () P YX π ⊗ | () P × = Y π | () P XY π ⊗ | () P × = X π | () P X ∑ 1 = XY ⊗ π | () P X ∑ Y π | () P = Program Description Preliminary Knowledge π () Pertinent Variables Decomposition Forms Parametrical Forms Programs           Data δ ()          Question            a set of variables
given a set of experimental data and preliminary knowledge . This joint distribution is denoted as: .

Preliminary Knowledge

To specify preliminary knowledge the programmer must undertake the following: 1Define the set of relevant variables on which the joint distribution is defined. 2 Decompose the joint distribution:

Given a partition of into subsets we define variables each corresponding to one of these subsets.

Each variable

is obtained as the conjunction of the variables belonging to the subset . The conjunction rule [E3.4] leads to:

[E3.7]
Conditional independence hypotheses then allow further simplifications. A conditional independence hypothesis for variable is defined by picking some variables among the variables appearing in conjunction , calling the conjunction of these chosen variables and setting:

[E3.8]
We then obtain: [E3.9] Such a simplification of the joint distribution as a product of simpler distributions is called a decomposition. 3Define the forms:

Each distribution

appearing in the product is then associated with either a parametric form (i.e., a function ) or another Bayesian program. In general, is a vector of parameters that may depend on or or both. Learning takes place when some of these parameters are computed using the data set .

Question

Given a description (i.e.,

), a question is obtained by partitioning into three sets : the searched variables, the known variables and the unknown variables.

We define the variables , and as the conjunction of the variables belonging to these sets. We define a question as the distribution:

.

[E3.10]

Running Bayesian programs

Running a Bayesian program supposes two basic capabilities: Bayesian inference and decisionmaking.

Bayesian inference

Given the joint distribution , it is always possible to compute any possible question, using the following general inference:

X 1 X 2 … X n ,,, {} δ π X 1 X 2 … X n ⊗⊗⊗ δ π ⊗ | () P X 1 X 2 … X n ,,, {} X 1 X 2 … X n ,,, {} kk L 1 … L k ,, L i X i 1 X i 2 … ,, {} i X 1 X 2 … X n ⊗⊗⊗ δ π ⊗ | () P L 1 δπ ⊗ | () P L 2 L 1 δπ ⊗⊗ | () P … × L k L k 1 - … L 2 L 1 δπ ⊗⊗⊗⊗ ⊗ | () P × × = L i X j L i 1 - … L 2 L 1 ⊗⊗⊗ R i L i L i 1 - … L 2 L 1 δπ ⊗⊗⊗⊗ ⊗ | () P L i R i δπ ⊗⊗ | () P = X 1 X 2 … X n ⊗⊗⊗ δ π ⊗ | () P L 1 δπ ⊗ | () P L 2 R 2 δπ ⊗⊗ | () P L 3 R 3 δπ ⊗⊗ | () P ×… × L k R k δπ ⊗⊗ | () P × × = L i R i δπ ⊗⊗ | () P f µ L i () µ R i δ δ X 1 X 2 … X n ⊗⊗⊗ δ π ⊗ | () P X 1 X 2 ...... X n ,, , {} Search Known Unknown Searched Known δπ ⊗⊗ | () P X 1 X 2 … X n ⊗⊗⊗ δ π ⊗ | () P [E3.11]
where the first equality results from the marginalization rule (equation [E3.6]), the second results from the product rule (equation [E3.4]) and the third corresponds to a second application of the marginalization rule. The denominator appears to be a normalization term. Consequently, by convention, we will replace it by . Finally, the joint distribution is replaced by its decomposition.

Two main problems have to be solved: searching the modes in a high dimensional space, and marginalizing in a high dimensional space.

Since may be a conjunction of numerous variables, each of them possibly having a lot of values or even being continuous, it is seldom possible to exhaustively compute . One may then decide either to build an approximate representation of this distribution or to directly sample from this distribution. In both cases the challenge is to find the modes where most of the probability density is concentrated. This may be very difficult, as most of the probability may be concentrated in very small sub-spaces of the whole searched space.

The situation is even worse, as computing the value of for a given value of (a single point of the searched space of the preceeding paragraph) is by itself a difficult problem. Indeed, it supposes to marginalize the joint distribution on the space defined by .

(like ) may be a conjunction of numerous variables, each of them possibly having a lot of values or even being continuous. Consequently, the sum should also be either approximated or sampled. The challenge is then to find the modes of [E3.12] (on the search space defined by ), where most of the probability density is concentrated and which mostly contribute to the sum. Finally, marginalizing in a high dimensional space appears to be a very similar problem to searching the modes in a high dimensional space.

It is well known that general Bayesian inference is a very difficult problem, which may be practically intractable. Exact inference has been proved to be NP-hard [START_REF] Cooper | The computational complexity of probabilistic inference using Bayesian belief networks[END_REF] and the general problem of approximate inference too [START_REF] Cox | Approximate probabilistic reasoning in Bayesian belief network is NP-Hard[END_REF].

However, approximate inference is often tractable in practical cases for three main reasons: 1 The conditional independences, as expressed by the decomposition of the joint distribution, break the complexity of the problem by reducing drastically the size of the searched space (see section 6 for an instance of that). The importance of the decomposition has already been stressed by many authors (e.g., [START_REF] Zhang | Exploiting Causal Independence in Bayesian Network Inference[END_REF] and explains mainly the good performances of our engine (10 inferences per second 5 ). 2 Some powerful symbolic simplifications can be made before any numerical computation (see next section on OPL). 3 Numerical optimization and marginalization have a long history and impressive 5. Order of magitude on a standard desktop computer for the inferences required by the experiments described in the sequel. ------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------

Searched

= Searched Unknown Known ⊗⊗ δ π ⊗ | () P Unknown ∑ Searched Unknown Known ⊗⊗ δ π ⊗ | () P Searched Unknown ∑ --
= 1 Σ --- Searched Unknown Known ⊗⊗ δ π ⊗ | () P Unknown ∑ × = 1 Σ --- L 1 () P L i R i | () P i 2 = k ∏ × Unknown ∑ × = Σ Searched Searched Known | () P Searched Known | () P Searched Unknown Unknown Searched L 1 () P L i R i | () P i 2 = k ∏ × Unknown
numerical methods have been developed which can be reused in this context (see next section on OPL).

OPL: an API to automate Bayesian inference

An inference engine and the associated programming API 6 (named OPL for Open Probabilistic Language) has been developed and used for the experiments presented in this paper and other industrial applications. OPL proceeds in two phases: a symbolic simplification of the required computation followed by some intensive numerical crunching.

The main goal of the simplification phase is to reduce the number of sums necessary to compute the distribution:

[E3.13]
These kinds of simplification techniques are largely used in the litterature. For instance, the well known JLO or junction tree algorithm [START_REF] Jensen | Bayesian updating in recursive graphical models by local computations[END_REF]) may be seen as such a simplification technique in the case of Bayesian Networks.

In OPL, a large spectrum of such simplifications is used. First, considering the different terms of the product , three possibilities of obvious simplifications may appear:

1 When a term is a uniform distribution it can be simplified: it vanishes from the expression and its value will implicitly be taken into account in the normalization constant . 2 When a term is a distribution where all the variables have values, then it is a constant for this question and may also be simplified. 3 When a term is a distribution where all the variables are either or , then it can be factorized out of the sum. After these three first steps, we get a new expression of the form:

[E3.14]
Now, considering , we can try to find an order on the sum to simplify terms that sum to 1.

Indeed, when a term appears in the sum, if all the variables appearing in are part of (summed) and if all the variables appearing in are either part of or , then sums to 1 and vanishes out of the global sum. This operation often leads to impressive simplifications.

Finally, the last simplification that can be made is to reorder the sums on the different unknown variables in order to minimize the number of operations to make. OPL uses the general distributive law algorithm to do this. A description of this algorithm may be found in a paper by [START_REF] Aji | The Generalized Distributive Law[END_REF].

A more detailed description of this simplification phase and of related work may be found in Bessière's survey [START_REF] Coué | Using Bayesian Programming for Multi-Sensor Multi-Target Tracking in Automotive Applications[END_REF].

The main goal of the numerical crunching phase is to estimate the distribution . A necessary subgoal is to estimate the corresponding sum. Two main approaches are possible to reach these objectives, either by building approximated explicit representation of these distributions or by sampling these distributions.

OPL includes different algorithms related to both approaches. It may approximate the distribution using either particle filters [START_REF] Arulampalam | A Tutorial on Particle Filters for On-line Nonlinear/Non-Gaussian Bayesian Tracking[END_REF] or Multi Resolution Binary Trees (MRBT), a homemade representation described in a pending patent (Bessière, 2002). OPL also

6. Application Programming Interface Searched Known | () P 1 Σ --- L 1 () P L i R i | () P i 2 = k ∏ × Unknown ∑ × = L 1 () P L i R i | () P i 2 = k ∏ × Σ Known Searched Known Searched Known | () P 1 Σ --- L j R j | () P jJ ∈ ∏ × L i R i | () P iI ∈ ∏ Unknown ∑ × = L i R i | () P iI ∈ ∏ Unknown ∑ L i R i | () P L i Unknown R i Known Unknown L i R i | () P Searched Known | () P
uses sampling techniques, mainly Monte Carlo sampling integration methods [START_REF] Radford | Probabilistic inference using Markov chain Monte-Carlo Methods[END_REF][START_REF] Mackay | Introduction to Monte Carlo Methods[END_REF] and an improved version of these techniques proposed by [START_REF] Mekhnacha | The design and implementation of a Bayesian CAD modeler for robotic applications[END_REF], where they are combined with simulated annealing.

Decision-making

For a given distribution, different decision policies are possible: for example, searching the best (highest probability) values or drawing at random according to the distribution. For our purposes, we will always use this second policy and refer to this query as:

. Utility functions could also be used to make the decision but they do not appear to be necessary for the work described in this paper.

Control loop of the robot

To control our robot using a Bayesian program, a decision is made every tenth of a second. A typical question is to select the values of the motor variables knowing the values of the sensory variables. Consequently, the basic loop to operate the robot is to loop on the following instructions every tenth of a second:

1 -Read the values of the sensors 2 -3 -Send the returned values to the motors

Experimental platform 4.1 Khepera robot

Khepera is a two-wheeled mobile robot, 57 millimeters in diameter and 29 millimeters in height, with a total weight of 80g (See Figure 2). It was designed at EPFL 7 and is commercialized by K-Team 8 .

Draw Motors Sensors δπ ⊗⊗ | () P ()
The robot is equipped with eight light sensors (six in front and two behind), taking values between 0 and 511 in inverse relation to light intensity, stored in variables (see Figure 3). These eight sensors can also be used as infrared proximeters, taking values between 0 and 1023 in inverse relation to the distance from the obstacle, stored in variables (see Figure 3).

The robot is controlled by the rotation speeds of its left and right wheels, stored in variables Mg and Md, respectively.

From these 18 basic sensory and motor variables, we derived three new sensory variables (, and ) and one new motor one ( ). They are described below. • is a variable that approximately corresponds to the bearing of the closest obstacle (see Figure 3). It takes values between -10 (obstacle to the left of the robot) and +10 (obstacle to the right of the robot), and is defined as follows:

[E4.1]
• is a variable that approximately corresponds to the proximity of the closest obstacle (See Figure 3). It takes values between zero (obstacle very far from the robot) and 15 (obstacle very close to the robot), and is defined as follows:

[E4.2]
• is a variable that approximately corresponds to the bearing of the greatest source of illumination. It takes on 36 values from -170° to 180°.

• The robot is piloted solely by its rotation speed (the translation speed is fixed). It receives motor commands from the variable, calculated from the difference between the rotation speeds of the left and right wheels.

takes on values between +10 (fastest to the right) and -10 (fastest to the left). Khepera accepts turrets on its top to augment either its sensory or motor capacities. For the final experiment (the nightwatchman task), a linear camera of 64 pixels and a micro turbine were added on top of the robot.

Environment

For all experiments described in the current paper, the Khepera is placed in a 1 m by 1 m environment. This environment has walls around its contour, textured to be easily seen by the robot. Inside this square, we place walls made of Lego © bricks that can be moved easily to set any con- -------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------

-   = Prox Prox Floor Max Px1 Px2 Px3 Px4 Px5 Px6 ,,,, , () 64 -
-   = Theta1 Vrot Vrot
figuration we need quickly. We usually build a recess made of high Lego © walls in a corner, and place a small light over this recess, to create a «base» for the robot (see Figure 12).

Reactive behavior

Goal and experimental protocol

The goal of the first experiment was to teach the robot how to push objects. First, in a learning phase, we drove the robot with a joystick to push objects. During that phase, the robot collected, every tenth of a second, both the values of its sensory variables and the values of its motor variables (determined by the joystick position). This data set was then used to identify the free parameters of the parametric forms.

Then, in a restitution phase, the robot has to reproduce the behavior it had just learned. Every tenth of a second it decided the values of its motor variables, knowing the values of its sensory variables and the internal representation of the task.

Specification

Having defined our goal, we describe the three steps necessary to define the preliminary knowledge.

1 -Chose the pertinent variables 2 -Decompose the joint distribution 3 -Define the parametric forms

Variables

First, the programmer specifies which variables are pertinent for the task.

To push objects it is necessary to have an idea of the position of the objects relative to the robot. The front proximeters provide this information. However, we chose to sum up the information of these six proximeters by the two variables and . We also chose to set the translation speed to a constant and to operate the robot by its rotation speed . These three variables are all we need to push obstacles. Their definitions are summed up as follows:

[S5.1]

Decomposition

In the second specification step, we give a decomposition of the joint probability as a product of simpler terms. This distribution is conditioned by both , the preliminary knowledge we are defining, and a data set that will be provided during the learning phase.

[S5.2]

The first equality results from the application of the product rule (equation [E3.4]). The second results from the simplification , which means that we consider that and are independent. The distances to the objects and their bearings are not contingent.

Parametric forms

To be able to compute the joint distribution, we finally need to assign parametric forms to each

Dir Prox Vrot Dir 10 - … 10 ,, {} ∈ Dir 21 = , Prox 0 … 15 ,, {} ∈ Prox 16 = , Vrot 10 - … 10 ,, {} ∈ Vrot 21 = , Dir Prox Vrot ⊗⊗ ∆ π-obstacle ⊗ | () P π-obstacle ∆ Dir Prox Vrot ⊗⊗ ∆ π-obstacle ⊗ | () P Dir ∆ π-obstacle ⊗ | () P Prox Dir ∆ π-obstacle ⊗⊗ | () P Vrot Prox Dir ∆ π-obstacle ⊗⊗ ⊗ | () P × × = Dir ∆ π-obstacle ⊗ | () P Prox ∆ π-obstacle ⊗ | () P Vrot Prox Dir ∆ π-obstacle ⊗⊗ ⊗ | () P × × = Prox Dir ∆ π-obstacle ⊗⊗ | () P Prox ∆ π-obstacle ⊗ | () P = Prox Dir
of the terms appearing in the decomposition:

[S5.3]
We have no a priori information about the direction and the distance of the obstacles. Hence, and are uniform distributions; all directions and proximities have the same probability.

For each sensory situation, we believe that there is one and only one rotation speed that should be preferred. The distribution is unimodal. However, depending of the situation, the decision to be made for may be more or less certain. This is resumed by assigning a Gaussian parametric form to .

Identification

We drive the robot with a joystick (see Movie 1 9 ), and collect a set of data . Let us call the particular set of data corresponding to this experiment . A datum collected at time is a triplet . The free parameters of the parametric forms (means and standard deviations for all the Gaussians) can then be identified by computing the means and standard deviations of for each position of the obstacle.

Finally, it is possible to compute the joint distribution:

[E5.1] According to equation [E3.11],
the robot can answer any question concerning this joint distribution.

We call the distribution a description of the task. A description is the result of identifying the free parameters of a preliminary knowledge using some given data. Hence, a description is completely defined by a couple preliminary knowledge + data. That is why a conjunction always appears to the right of a description.

Utilization

To render the pushing obstacle behavior just learned, the Bayesian controller is called every tenth of a second :

1 -The sensors are read and the values of and are computed 2 -The Bayesian program is run with the query:

[E5.2]
3 -The drawn is sent to the motors

Results, lessons and comments

Results

As shown in Movie 1 9 , the Khepera learns how to push obstacles in 20 to 30 seconds. It learns the particular dependency, corresponding to this specific behavior, between the sensory variables and and the motor variable . This dependency is largely independent of the particular characteristics of the objects (weight, color, balance, nature, etc.). Therefore, as shown in Movie 2 10 , the robot is also able to push different objects. This, of course, is only true within certain limits. For instance, the robot will not be able to push the object if it is too heavy. 9. http://www-laplace.imag.fr/ENGLISH/PRESENTATION/Semaine-Science/Trans7/T7.mov 10. http://www-laplace.imag.fr/ENGLISH/PRESENTATION/Semaine-Science/Trans8/T8.mov

Dir ∆ π-obstacle ⊗ | () P Uniform ≡ Prox ∆ π-obstacle ⊗ | () P Uniform ≡ Vrot Prox Dir ∆ π-obstacle ⊗⊗ ⊗ | () PG µ Prox Dir , () σ Prox Dir , () , () ≡ Dir ∆ π-obstacle ⊗ | () P Prox ∆ π-obstacle ⊗ | () P Vrot Prox Dir ∆ π-obstacle ⊗⊗ ⊗ | () P Vrot Vrot Prox Dir ∆ π-obstacle ⊗⊗ ⊗ | () P ∆ δ-push t vrot t dir t prox t ,, ( )
Dir Prox × Vrot Dir Prox Vrot ⊗⊗ δ-push π-obstacle ⊗ | () P Dir π-obstacle | () P Prox π-obstacle | () P × Vrot Prox Dir δ-push π-obstacle ⊗⊗ ⊗ | () P × = Dir Prox Vrot ⊗⊗ δ-push π-obstacle ⊗ | () P δπ ⊗ dir t prox t Draw Vrot prox t dir t δ-push π-obstacle ⊗⊗ ⊗ | () P () vrot t Dir Prox Vrot
Lesson 1: A generic method for Bayesian Robot Programming

In this experiment we apply a precise three-step method to program the robot.

1 -Specification: define the preliminary knowledge 1.1 -Choose the pertinent variables 1.2 -Decompose the joint distribution 1.3 -Define the parametric forms 2 -Identification:identify the free parameters of the preliminary knowledge 3 -Utilization: ask a question to the joint distribution

In the sequel, we will use the very same method for all the other BRP experiments.

Lesson 2: Bayesian Program = Preliminary Knowledge + Data + Question Numerous different behaviors may be obtained by changing some of the different components of a Bayesian program in the following ways.

• It is possible to change the question, keeping the description unchanged. For instance, if the information is no longer available because of some failure, the robot may still try to push the obstacles knowing only their direction. The query is then:

[E5.3]
• It is possible to change the data, keeping the preliminary knowledge unchanged. For instance, with the same preliminary knowledge , we taught the robot to avoid objects or to follow their contour (see Figure 4 and Movie 3 11 ). Two new descriptions 12 were obtained by changing only the driving of the robot during the learning phase. As a result, two new programs were obtained leading to the expected behaviors : «obstacle avoidance» and «contour following». • Finally, it is possible to change the preliminary knowledge, which leads to completely different behaviors. Numerous examples will be presented in the sequel of this paper.

For instance, we taught the robot another reactive behavior called phototaxy. Its goal is then to move toward a light source. This new preliminary knowledge uses the variables and . roughly corresponds to the direction of the light.

π-obstacle Dir Prox Vrot ⊗⊗ δ-avoid π-obstacle ⊗ | () P Dir Prox Vrot ⊗⊗ δ-follow π-obstacle ⊗ | () P π-phototaxy1

Vrot

Theta1 Theta1

Sensor fusion 6.1 Goal and experimental protocol

The goal of this experiment is to fuse the data originating from the eight light sensors to determine the position of a light source. This will be obtained in two steps. In the first one, we specify one description for each sensor individually. In the second one, we mix these eight descriptions to form a global one.

Sensor model

Specification

Variables

To build a model of the light sensor , we only require two variables:

the reading of the sensor, and , the bearing of the light source.

[S6.1]

Decomposition

The decomposition simply specifies that the reading of a sensor obviously depends on the position of the light source

[S6.2]

Parametric forms

As we have no a priori information on the position of the source, we state:

[S6.3]
The distribution is usually very easy to specify because it corresponds exactly to the kind of information that the sensor supplier provides: the expected readings of its device when exposed to a light. For the Khepera's light sensors, we obtain (see Figure 5): Figure 5:

iL i i th Theta2 Li 0 … 511 ,, {} ∈ Li 512 = , Theta2 170 - … 180 ,, {} ∈ Theta2 36 = , Theta2 Li ⊗∆ π-sensor ⊗ | () P Theta2 π-sensor | () P Li Theta2 ∆ π-sensor ⊗⊗ | () P × = Theta2 π-sensor | () P Uniform ≡ Li Theta2 ∆ π-sensor ⊗⊗ | () P K(Theta2,0) Theta2 (°) K Theta2 0 , () [S6.4]
In specification [S6.4], stands for the position of the sensor with respect to the robot, and will be used later to «rotate» this model for different sensors.

Specifications [S6.1], [S6.2], [S6.3] and [S6.4] are the preliminary knowledge corresponding to this sensor model. This preliminary knowledge is named .

Identification

No identification is required as there are no free parameters in . However, it may be easy and interesting to calibrate specifically each of the eight light sensors. This could be achieved, for instance, by identifying parameters and independently for each sensor, by observing the response of the particular sensor to a light source.

Fusion

Specification

Variables

The interesting variables are the eight variables and :

[S6.5]

Decomposition

The decomposition of the joint distribution is chosen to be:

[S6.6]
The first equality results from the product rule [E3.4]. The second from simplifications of the kind:

[E6.1]
These simplifications may seem peculiar as obviously the readings of the different light sensors are not independent. The exact meaning of these equations is that we consider (the position of the light source) to be the main reason for the contingency of the readings. Consequently, we state that, knowing , the readings are independent. is the cause of the readings and knowing the cause, the consequences are independent. This is, indeed, a very strong hypothesis. The sensors may be correlated for numerous other reasons. For instance, ambient temperature influences the functioning of any electronic device and consequently correlates their responses. However, we choose, as a first approximation, to disregard all these other factors.

Parametric forms

We do not have any a priori information on : -------------------------------------------------------= α 45 = () β 00 3 , = () ,

Li Theta2 π-sensor ⊗ | () PG K Theta2 θ i , () σ , Li () ≡ K Theta2 θ i , () 1 1 1 e 4β Theta2 θ i - α - () - + -
θ i π-sensor π-sensor α β Li Theta2 L1 0 … 511 ,, {} ∈ L1 512 = , … L8 0 … 511 ,, {} ∈ L8 512 = , Theta2 170 - … 180 ,, {} ∈ Theta2 36 = , Theta2 L1 L2 L3 L4 L5 L6 L7 L8 ⊗⊗⊗⊗⊗⊗⊗⊗ ∆π-fusion ⊗ | () P Theta2 ∆ π-fusion ⊗ | () P L1 Theta2 ∆ π-fusion ⊗⊗ | () P L2 L1 Theta2 ∆ π-fusion ⊗⊗ ⊗ | () P × × = … L8 L7 L6 L5 L4 L3 L2 L1 Theta2 ∆ π-fusion ⊗⊗⊗⊗⊗⊗⊗ ⊗ ⊗ | () P × Theta2 π-fusion | () P Li Theta2 ∆ π-fusion ⊗⊗ | () P i 1 = 8 ∏ × = Lj Lj 1 - … L1 Theta2 ∆ π-fusion ⊗⊗⊗ ⊗ ⊗ | () P Lj Theta2 ∆ π-fusion ⊗⊗ | () P = Theta2 Theta2 Lj Theta2 Theta2 [S6.7]
is obtained from the model of each sensor as specified in previous section (6.2):

[S6.8]

Identification

As there are no free parameters in , no identification is required.

Utilization

To find the position of the light source the standard query is:

[E6.1]
This question may be easily answered using equation [E3.11] and specification [S6.8]:

[E6.2]
Values drawn from this distribution may be efficiently computed given that the distribution is simply a product of eight very simple ones, and given that the normalizing constant does not need to be computed for a random draw.

Many other interesting questions may be asked of this description, as the following:

• It is possible to search for the position of the light source knowing only the readings of a few sensors:

[E6.3]
• It is possible to check whether the sensor is out of order. Indeed, if its reading at time t, persists in being inconsistent with the readings of the others for some period, it is a good indication of a malfunction. This inconsistency may be detected by a very low probability for :

[E6.4]

Results, lessons and comments

Results

Figure 6 presents the result obtained for a light source with a bearing of 10°:

The eight peripheral figures present the distributions corresponding to the eight light sensors. The central schema presents the result of the fusion, the distribution . Even poor information coming from each separate sensor may blend as a certainty.

Lesson 3: Breaking the complexity using conditional independences

The conditional independencies hypothesis which permits to transform:

[E6.5] into: Theta2 π-fusion | () P Uniform ≡ Li Theta2 ∆ π-fusion ⊗⊗ | () P Li Theta2 ∆ π-fusion ⊗⊗ | () P Li Theta2 π-sensor ⊗ | () P ≡ π-fusion Draw Theta2 l1 t ...... l8 t π-fusion ⊗⊗ ⊗ | () P () Theta2 l1 t … l8 t π-fusion ⊗⊗ ⊗ | () P 1 Σ --- li t Theta2 π-sensor ⊗ | () P i 1 = 8 ∏ × = Theta2 l1 t … l8 t π-fusion ⊗⊗ ⊗ | () P Σ Theta2 l1 t l2 t π-fusion ⊗⊗ | () P 1 Σ --- l1 t Theta2 π-sensor ⊗ | () P l2 t Theta2 π-sensor ⊗ | () P × × = il i t li t l1 t l2 t … l8 t π-fusion ⊗⊗ ⊗ | () P 1 Σ --- li t Theta2 π-sensor ⊗ | () P i 1 = 8 ∏ Theta2 ∑ × = Theta2 Li π-sensor ⊗ | () P Theta2 l1 t … l8 t π-fusion ⊗⊗ ⊗ | () P Theta2 L1 L2 L3 L4 L5 L6 L7 L8 ⊗⊗⊗⊗⊗⊗⊗⊗ ∆π-fusion ⊗ | () P [E6.6]
is the main tool at hand to simplify the treated problem. More than any clever inference algorithm they are the essential way to keep computation tractable. For instance, here the size of the search space for the joint distribution [E] is , when the size of the search space for the decomposition [E6.6] is .

Lesson 4: Calling Bayesian subroutines Specification [S6.8]:

, where a distribution appearing in a decomposition is defined by a question to another Bayesian program, may be seen as the probabilistic anologous to subroutine calls in regular programming.

This Bayesian subroutine call mechanism will play the same role than the usual one: allowing to build complex Bayesian programs as hierarchies of embedded calls to simpler and simpler Bayesian programming building blocks. Section 10 will present a more complex instance of this.

Lesson 5: Sensor fusion method

In the experiment just presented, we have seen a simple instance of a general method to carry out data fusion.

The key point of this method is in the decomposition of the joint distribution, which has been considerably simplified under the hypothesis that «knowing the cause, the consequences are independent». This is a very strong hypothesis, although it may be assumed in numerous cases.

This way of doing sensor fusion is very efficient. Its advantages are manifold.

• The signal is heightened.

(L5 =280) P(Theta2 | L6 ⊗ π-sensor) (L6 =489) P(Theta2 | L2 ⊗ π-sensor) (L2 =422) P(Theta2 | L1 ⊗ π-sensor) (L1 =506) P(Theta2 | L8 ⊗ π-sensor) (L8 =511) P(Theta2 | L7 ⊗ π-sensor) (L7 =511) P(Theta2 | L1⊗ ...⊗ L8 ⊗ π-fusion) (Theta2 = 10) Theta2 π-fusion | () P Li Theta2 ∆ π-fusion ⊗⊗ | () P i 1 = 8 ∏ × 36 512 8 × 2 79 ∝ 36 512 36 × () 8 × × 2 22 ∝ Li Theta2 ∆ π-fusion ⊗⊗ | () P Li Theta2 π-sensor ⊗ | () P ≡
• It is robust to a malfunction of one of the sensors.

• It provides precise information even with poor sensors.

• It leads to simple and very efficient computations.

We presented this method on a very simple case for didactic purposes. However it is a very popular technique to do sensor fusion which can be used for much more complicated cases in a large variety of applications. For instance, we used refinement of this technique for ADAS (Advanced Driver Assistance System) to merge information coming from two radars and one lidar in order to partially automate car driving [START_REF] Coué | Multi-Sensor Data Fusion Using Bayesian Programming: an Automotive Application[END_REF][START_REF] Coué | Using Bayesian Programming for Multi-Sensor Multi-Target Tracking in Automotive Applications[END_REF].

Lesson 6: No inverse and no ill-posed problems in the probabilitic framework

In this experiment, another fundamental advantage of Bayesian programming is clearly evident. The description is neither a direct nor an inverse model. Mathematically, all variables appearing in a joint distribution play exactly the same role. This is why any question may be asked of a description. Consequently one may define the description in one way ( ) and question it in the opposite way (

). In theory, any inverse problem may be solved when expressed in a probabilistic framework. In practice some of these inverse problems may require a lot of computational ressources. However, this is a major difference with non probabilistic modelling where inverse problem may only be solved in rare cases.

Furthermore, there is none ill-posed problem in a probabilistic framework. If a question may have several solutions, the probabilistic answer will simply have several peaks.

Behavior combination

Goal and experimental protocol

In this experiment we want the robot to go back to its base where it can recharge.

This will be obtained with no further teaching. As the robot's base is lit, the light gradient usually gives good hints on its direction. Consequently, we will obtain the homing behavior by combining together the obstacle avoidance behavior and the phototaxy behavior. By programming this behavior we will illustrate one possible way to combine Bayesian programs that make use of a «command variable».

Specification

Variables

We need , , and , the four variables already used in the two composed behaviors. We also need a new variable which acts as a command to switch from avoidance to phototaxy.

[S7.1]

Decomposition

We believe that the sensory variables , and are independent from one another. Far from any objects, we want the robot to go toward the light. Very close to obstacles, we want the robot to avoid them. Hence, we consider that should only depend on . Finally, we believe that must depend on the other four variables. These programmer choices lead to the following decomposition:

Parametric forms

We have no a priori information about either the direction and distance of objects or the direction of the light source. Consequently, we state:

[S7.3]
is a command variable to switch from avoidance to phototaxy. This means that when the robot should behave as it learned to do in the description and when the robot should behave according to the description . Therefore, we state:

[S7.4]
We want a smooth transition from phototaxy to avoidance as we move closer and closer to objects. Hence we finally state:

[S7.5]
The discrete approximation of the Sigmoid function we use above, which will not be defined in the current paper, is shown in Figure 7.

The

Identification

There are no free parameters in preliminary knowledge . No learning is required.

Utilization

While Khepera returns to its base, we do not know in advance when it should avoid obstacles or when it should go toward the light. Consequently, to render the homing behavior we will use the following question where is unknown:

[E7.1] Equation [E7.
1] shows that the robot does a weighted combination between avoidance and phototaxy. Far from any objects (

) it does pure phototaxy. Very close to objects ( ) it does pure avoidance. In between, it mixes the two.

Results, lessons and comments

Results

Figure 8 and Movie 4 13 show efficient homing behavior obtained this way.

Figures 9 and 10 present the probability distributions obtained when the robot must avoid an obstacle on the left with a light source also on the left. As the object is on the left, the robot needs to turn right to avoid it. This is what happens when the robot is close to the objects (see Figure 9). However, when the robot is further from the object, the presence of the light source on the left influences the way the robot avoids obstacles. In that case, the robot may turn left despite the presence of the obstacle (see Figure 10).

P H ∑ = 1 Σ --- avoidance Prox π-home ⊗ | () P Vrot Dir Prox δ-avoid π-obstacle ⊗⊗ ⊗ | () P × [ ] . phototaxy Prox π-home ⊗ | () P Vrot Theta1 δ-phototaxy π-phototaxy1 ⊗⊗ | () P × [ ] + × = prox 0 phototaxy prox π-home ⊗ | () P 1 = , = prox 15 avoidance prox π-home ⊗ | () P 1 = , =
Figure 9: Homing behavior (Khepera close to an object on its left and has also the light source on its left). The top left distribution shows the knowledge on given by the phototaxy description; the top right is given by the avoidance description; the bottom left shows the knowledge of the «command variable» ; finally the bottom right shows the resulting combination on .

Figure 10: Homing behavior (Khepera further from the object on its left). This figure is structured as Figure 9.

Lesson 7: A probabilistic if-then-else

In this experiment we present a simple instance of a general method to combine descriptions to obtain a new mixed behavior. This method uses a command variable to switch from one of the composing behaviors to another. A probability distribution on knowing some sensory variables should then be specified or learned 14 . The new description is finally used by asking questions where is unknown. The resulting sum on the different cases of does the mixing.

This shows that Bayesian robot programming allows easy, clear and rigorous specifications of such combinations. This seems to be an important benefit compared to some other methods that have great difficulties in mixing behaviors with one another, such as Brooks' subsumption architecture [START_REF] Bretthorst | Bayesian spectrum analysis and parameter estimation[END_REF][START_REF] Maes | How to Do the Right Thing[END_REF] or neural networks.

Description combination appears to naturally implement a mechanism similar to HEM 15 [START_REF] Jordan | Hierarchical mixtures of experts and the EM algorithm[END_REF] and is also closely related to mixture models (see [START_REF] Mclachlan | Finite Mixture Models[END_REF] for a reference document about mixture models and see [START_REF] Coué | Using Bayesian Programming for Multi-Sensor Multi-Target Tracking in Automotive Applications[END_REF] for detail about the relation between description combination and mixture models).

Finally, from a programming point of view, description combination can be seen as a probabilistic if-then-else. is the condition. If is known with certainty then we have a usual branching structure. If is known with some uncertainty through a probability distribution then the 2 possible consequences are automatically mixed using weights proportional to this distribution.

Situation recognition

Goal and experimental protocol

The goal of this experiment is to distinguish different objects from one another.

At the beginning of the experiment the robot does not know any object (see below for a precise definition). It must incrementally build categories for the objects it encounters. When it knows of them, the robot must decide if a presented object enters in one of the categories or if it is something new. If it is a new object, the robot must create a new category and should start to learn it.

Specification

Variables

The Khepera does not use its camera for this task. It must «grope» for the object. It uses the «contour following» behavior to do so (see Figure 4). It does a tour of the presented object and computes at the end of this tour four new variables:

the number of left turns, the number of right turns, the perimeter and the longest straight line. The values of these variables are not completely determined by the shape of the object, given that the contour following behavior is quite choppy.

We also require a variable to identify the different classes of object. The value is reserved for the class of unknown (not yet presented) objects.

Finally, we obtain:

[S8.1]

Decomposition

Obviously, the four variables , , and are not independent of one another. However, by reasoning similar to the sensor fusion case (see Section 6), we consider that knowing the 14. see [START_REF] Diard | Bayesian Learning Experiments with a Khepera Robot in Experiments with the Mini-Robot Khepera[END_REF] 15. Hierachical Mixture of Expert

H H H H HH H n n Nlt Nrt Per Lrl OO 0 = Nlt 0 … 24 ,, {} ∈ Nlt 25 = , Nrt 0 … 24 ,, {} ∈ Nrt 25 = , Per 0 … 9999 ,, {} ∈ Per 10000 = , Lrl 0 … 999 ,, {} ∈ Lrl 1000 = , O 0 … 15 ,, {} ∈ O 16 = ,
Nlt Nrt Per Lrl object , they are independent. Indeed, if the object is known, its perimeter or the number of turns necessary to complete a tour are also known. This leads to the following decomposition:

[S8.2]

Parametric forms

We have no a priori information on the presented object:

[S8.3]
For an already observed object ( ), we state that the distributions on and are Laplace succession laws 16 and that the distributions on and are Gaussian laws:

[S8.4]
Finally, we state that for a new object ( ) we have no a priori information about , , and :

[S8.5]
The preliminary knowledge composed of specifications [S8.1], [S8.2], [S8.3], [S8.4] and [S8.5] is named .

Identification

When an object is presented to the robot, if it is recognized as a member of a class , the parameters of the two Laplace succession laws and the two Gaussian laws corresponding to this class are updated.

If the object is considered by Khepera to be a new one, then a new class is created and the parameters of the distributions are initialized with the values of , , and just read. The learning process is incremental. Contrary to what we have seen up to this point, the identification and utilization phases are not separated. Each new experience changes the set of data , and leads to a new description .

Utilization

After experiences, to recognize a presented object, the question to answer is:

[E8.1]
This may be simply computed by: 16. A Laplace succession law on a variable V is defined by: with the total number of observations, the number of possible values for and the number of observations of the specific value .

O O Nlt Nrt Per Lrl ⊗⊗ ⊗ ⊗ ∆ π-object ⊗ | () P O π-object | () P Nlt O ∆ π-object ⊗⊗ | () P Nrt O ∆ π-object ⊗⊗ | () P × × = . Per O ∆ π-object ⊗⊗ | () P × Lrl O ∆ π-object ⊗⊗ | () P × O π-object | () P Uniform ≡ O 0 ≠ Nlt Nrt Per Lrl 1 n v + NV + --------------------- NV Vn v v o i O ∈ ∀ o i o 0 ≠ , Nlt o i ∆ π-object ⊗⊗ | () PL 1 n Nlt o i () () ≡ Nrt o i ∆ π-object ⊗⊗ | () PL 2 n Nrt o i () () ≡ Per o i ∆ π-object ⊗⊗ | () PG 1 µ o i () σ o i () , () ≡ Lrl o i ∆ π-object ⊗⊗ | () PG 2 µ o i () σ o i () , () ≡ O 0 = Nlt Nrt Per Lrl Nlt o 0 π-object ⊗ | () P Uniform ≡ Nrt o 0 π-object ⊗ | () P Uniform ≡ Per o 0 π-object ⊗ | () P Uniform ≡ Lrl o 0 π-object ⊗ | () P Uniform ≡ π-object o i Nlt Nrt Per Lrl ∆ O Nlt Nrt Per Lrl ⊗⊗ ⊗ ⊗ δ n π-object ⊗ | () P n 1 - O nlt n nrt n per n lrl n ⊗⊗ ⊗ δ n 1 - π-object ⊗⊗ | () P [E8.2]
If the most probable value for is zero, then Khepera assumes that it is facing a new object. Otherwise, this most probable value is considered to correspond to the recognized object.

Results, lessons and comments

Results.

The 15 objects shown on Figure 11 have been presented to the robot, five times each, in random order. Each time the question was as follows: «Do you know this object, or is it a new one?» mathematicaly stated as . The obtained results are presented on table 1.

It should be first noticed that two objects (top right of the picture, 3 and 7 in the order of first presentation) have the exact same square basis and thus may not be distinguished from one another given the four chosen variables. In these 2 cases, Khepera was in the position of someone asked to identify the color of an object by groping it.

The robot did not ever fail to recognize novelty (column 1) but for the first presentation of object 7 which was recognized as object 3.

At the second presentation of each object the robot recognized the object except for object 7 which was always identified as 3 and but once for object 12 (the wood pyramid) which was also recognized as 3.

O Nlt Nrt Per Lrl

⊗⊗⊗ δ n 1 - π-object ⊗⊗ | () P 1 Σ --- Nlt O δ n 1 - π-object ⊗⊗ | () P × Nrt O δ n 1 - π-object ⊗⊗ | () P × = . Per O δ n 1 - π-object ⊗⊗ | () P Lrl O δ n 1 - π-object ⊗⊗ | () P × × O O nlt n nrt n per n lrl n ⊗⊗ ⊗ δ n 1 - π-object ⊗⊗ | () P

Lesson 8: Categorization

The main lesson to retain from this experiment is that categorization of objects or situations may be considered as developing some specific sensor. Indeed, the method used in this section for object recognition is very similar to what was achieved for sensor fusion in Section 6. The hypotheses are similar and the advantages are the same.

Temporal sequences

Goal and experimental protocol

In this section, to exemplify the Bayesian programming method, we choose a «night watchman task». This may be obtained as temporal sequences of six simpler behaviors:

1 Idle: The robot is at its base, recharging its batteries. It waits for both an order and enough energy to leave. 2 Patrol: It wanders around its environment and sounds an alarm if it detects any movement. 3 Recognition: The robot tours object to identify them. 4 Fire-intervention: Khepera tries to extinguish fires by blowing on them using its micro-turbine. 5 Homing: It goes to its base when ordered to do so. 6 Recharge: When low on energy, it goes to its base to recharge. The purpose of this section is to show how such temporal sequences may be specified in the Table 1: Situation Recognition. The columns correspond to the «really» presented objects. The first column (F) corresponds to the first presentation of an object and the lines to the recognize objects.

For instance, is specified by table 2. This table should be read by column. Each column corresponds to the probability of knowing a certain behavior of the robot at time . Consequently, each column should sum to 1 to respect the normalization constraint.

For instance, the first column of table 3 specifies the probabilities of the variable knowing that the behavior of the robot at time was idle. If Khepera was idle, then it may stay idle with a high probability (90%), it may not directly change its behavior to either recognition, homing or recharge (probability 0), it may switch to patrol or fire-intervention with a low probability (0.05 for both case obtained by normalization as specified by the «x»).

If the Khepera was in mode patrol (second column), the most probable behavior is that it stays in this mode, although it can switch to any other one. If the Khepera was in mode recognition (third column) we set a very high probability for it to stay in this mode because we do not want it to be easily distracted from this task and we preclude any possibility of switching to idle. In mode fire-intervention (column 4) we exclude any switch to idle, recognition or homing. Finally, when in mode homing or recharge, the most probable behavior is to stay in the current mode, although nothing is definitely excluded.

Table 3 mainly says that patrol and recognition suppose that Vigil is true and that homing supposes that Vigil is false. When idle the probability that Vigil is true is not 0, because the Khepera may be idle to recharge its batteries even when ordered to work.

Table 4 specifies that when idle it is more probable that Energy is low than high. It also says that patrol and recognition suppose a high Energy and recharge the opposite.

Behavior Behavior_t-1 π-behavior ⊗ | () P Behavior t 1 - Behavior t 1 - Behavior Behavior_t-1 π-behavior ⊗ | () P Vigil Behavior π-behavior ⊗ | () P Energy Behavior π-behavior ⊗ | () P
recharge suppose with a high probability that Khepera is not at its base.

Table 6 means that when Khepera is facing a fire, it is necessarily in mode fire-intervention.

Finally, Table 7 says recognition imposes that Khepera has been ordered to do so (Identify is true).

Identification

No identification is required, as there are no free parameters in .

Utilization

The robot chooses its behavior with the following query:

[E9.1]
that can be easily computed:

[E9.2]

Results, lessons and comments

Results

Using these techniques, Khepera obtains temporal sequences of behaviors that appear convincing to a human observer (an instance of such a sequence will be given in the next section, see Movie 5 17 ). For instance, these sequences are stable. Khepera does not behave like a weathercock that changes its mind every second.

Lesson 9: Inverse programming

This experiment demonstrates a completely new method of specifying temporal sequences of tasks that could be called «inverse temporal programming». Indeed, the programmer does not specify, as usual, the necessary conditions for an action. On the contrary, he or she specifies for each action the expected observations and assumes that knowing the action these observations are independent.

Inverse programming presents two main advantages.

• It is robust to unforeseen situations. A sequence of actions is always produced, even in cases that the programmer did not explicitly take into account. • Due to the conditional independence assumption, the number of cases to take into account grows only linearly with the number of conditioning variables. The a priori specification of the probability distributions of the observed variables knowing the behavior may be a difficulty. However it is possible to learn these distributions (see [START_REF] Diard | Bayesian Learning Experiments with a Khepera Robot in Experiments with the Mini-Robot Khepera[END_REF].

Furthermore, the stability of the behavior according to the values in the tables is a critical question. We do not have yet any quantified results to answer this question but we are trying to set up an experimental protocol to evaluate it.

Integration: A Night watchman Task

Goal and experimental protocol

The practical goal and experimental protocol of the night watchman task has already been presented in Section 9.1.

The scientific purpose of this last experiment is to prove that Bayesian robot programming is an efficient constructive methodology and that all the previous descriptions may be integrated into a single synthetic one.

Three descriptions and a few corresponding variables necessary for the night watchman task

have not yet been presented to keep the paper short:

1-used by Khepera to decide if it is at its base 2-another temporal sequencing description required because some of the behaviors are successions of reactive movements. 3-built on the reactive behaviors to finally decide the rotation and translation speeds.

Specification

Variables

The nightwatchman task requires 41 variables:

• Thirty-three «sensory» variables that Khepera may read every tenth of a second. When convenient, we will summarize these 33 variables by their conjunction (a variable named ).

[E10.1]

• F ive internal variables:

• Three «motor» variables that Khepera must compute. These three variables are the rotation speed , the translation speed and the identity of the object .

Decomposition and parametric forms

The decomposition of the joint distribution on these 41 variables is a product of a uniform distribution on the sensory variables ( ) and eight questions addressed to the previously defined descriptions:

[E10.2]

Identification

No identification is required.

Utilization

The ultimate question that Khepera must answer is:

[E10.3]
«What order should be sent to the motors, knowing the sensory state, and ignoring the values of the internal variables?»

The answer to that question is obtained, as usual, by summing over the five ignored variables. This leads to the following result: [E10.4] This expression may seem complex. In fact, it exactly reflects the structure of the reasoning required to solve the problem.

• Recognizing the object is independent of the Khepera control.

• The innermost sum searches the ignoring

Principles

The dominant paradigm in robotics may be caricatured by Figure 13.

The programmer of the robot has an abstract conception of its environment. He or she may describe the environment in geometrical terms because the shape of objects and the map of the world can be specified. He or she may described the environment in analytical terms because laws of physics that govern this world are known. The environment may also be described in symbolic terms because both the objects and their characteristics can be named.

The programmer uses this abstract representation to program the robot. The programs use these geometric, analytic and symbolic notions. In a way, the programmer imposes on the robot his or her own conception of the environment.

The difficulties of this approach appear when the robot needs to link these abstract concepts with the raw signals it obtains from its sensors and sends to its actuators.

The central origin of these difficulties is the irreducible incompleteness of the models. Indeed, there are always some hidden variables, not taken into account in the model, that influence the phenomenon. The effect of these hidden variables is that the model and the phenomenon never behave exactly the same. The hidden variables prevent the robot from relating the abstract concepts and the raw sensory-motor data reliably. The sensory-motor data are then said to be «noisy» or even «aberrant». A queer reversal of causality occurs that seem to consider that the mathematical model is exact and that the physical world has some unknown flaws.

Compelling the environment is the usual answer to these difficulties. The programmer of the robot looks for the causes of «noises» and modifies either the robot or the environment to suppress these «flaws». The environment is modified until it corresponds to its mathematical model. This approach is both legitimate and efficient from an engineering point of view. A precise control of both the environment and the tasks ensures that industrial robots work properly. However, compelling the environment may not be possible when the robot must act in an environment not specifically designed for it. In that case, completely different solutions must be devised.

The purpose of this paper is to propose Bayesian Robot Programming (BRP) as a possible solution.

Figure 14 presents the principles of this approach. The fundamental notion is to place side by side the programmer's conception of the task (the preliminary knowledge) and the experimental data to obtain the programming resources called «descriptions». As seen in the different examples described in this paper, both the preliminary knowledge and the descriptions may be expressed easily and efficiently in probabilistic terms.

The preliminary knowledge gives some hints to the robot about what it may expect to observe. The preliminary knowledge is not a fixed and rigid model purporting completeness. Rather, it is a gauge, with open parameters, waiting to be molded by the experimental data. Learning is the means of setting these parameters. The resulting descriptions result from both the views of the programmer and the physical specificities of each robot and environment. Even the influence of the hidden variables is taken into account and quantified; the more important their effects, the more noisy the data, the more uncertain the resulting descriptions.

However, Bayesian robot programming preserves two very important merits of the symbolic approach. Thanks to the preliminary knowledge, the descriptions are comprehensible to the programmer. Thanks to Bayesian inference, complex reasoning is possible.

Theoretical foundations

The theoretical foundations of Bayesian robot programming may be summed up by Figure 15.

The first step transforms the irreducible incompleteness to uncertainty. Starting from the preliminary knowledge and the experimental data, learning builds probability distributions. The maximum entropy principle is the theoretical foundation of this first step. Given some preliminary knowledge and some data, the probability distribution that maximizes the entropy is the distribution that best represents this couple. Entropy gives a precise, mathematical and quantifiable meaning to the «quality» of a distribution (for justifications of the maximum entropy principle see, for instance, [START_REF] Jaynes | On the rationale of maximum-entropy methods[END_REF][START_REF] Robert | An entropy concentration theorem: applications ; in artificial intelligence and descriptive statistics[END_REF]Bessière et al., 1998b).

Two extreme examples may help to understand what occurs:

• Suppose that we are studying a formal phenomenon. There are no hidden variables. A complete model may be proposed. If we select this model as the preliminary knowledge, any data set will lead to a description made of Diracs. There is no uncertainty, any question may be answered either by true or false. Logic appears as a special case of the Bayesian approach in that particular context (see [START_REF] Cox | Approximate probabilistic reasoning in Bayesian belief network is NP-Hard[END_REF]). • On the opposite extreme, suppose that preliminary knowledge consists of very poor hypotheses about the modeled phenomenon. Learning will lead to «flat» distributions, containing no information. No relevant decisions can be made, only completely random ones. Hopefully, most common cases are somewhere in between these two extremes. Preliminary knowledge, even imperfect and incomplete, is relevant and provides interesting hints about the observed phenomenon. The resulting descriptions are neither Diracs nor uniform distributions. They give no certitudes, although they provide a means of taking the best possible decision according to the available information.

The second step consists of reasoning with the probability distributions obtained by the first step.

To do so, we only require the two basic rules of Bayesian inference (see Section 3). These two rules are to Bayesian inference what the resolution principle is to logical reasoning (see [START_REF] Robinson | A Machine Oriented Logic Based on the Resolution Principle[END_REF][START_REF] Robinson | Logic : Form and Function[END_REF]Robinson & Sibert, 1983a;Robinson & Sibert, 1983b). These inferences may be as complex and subtle as those usually achieved with logical inference tools, as illustrated in the different examples in this paper.

Advantages

In this section we survey, comment and briefly discuss the advantages of the BRP method proposed in this paper.

• Ability to treat incomplete and uncertain information: The basis of this work is related to the fundamental difficulty of robot programming in real environment. For us this difficulty is the direct consequence of the irreducible incompleteness of models. Consequently, the first advantage of BRP is its ability to take into account this incompleteness and the resulting uncertainty. This is obtained in three steps, thanks to the following three abilities of the method: °Ability to convert incompleteness to uncertainty by learning, as demonstrated in the numerous instances where the free parameters of preliminary knowledge are identified from experimental data (see, for instance, Section 5 concerning reactive behaviors or Section 8 concerning object recognition). Object recognition, for instance, shows that with simple preliminary knowledge, we are able to learn descriptions sufficient for classification. However, in this task there are numerous ignored variables such as, for instance, the color and material of the objects, the global lighting of the room, the approximate quality of the contour following behavior or the position from where the robot has started. °Ability to reason despite uncertainty, as demonstrated by all the experiments requiring inference (see, for instance, Section 6 about sensor fusion or Section 8 about object recognition). The «nightwatchman» task (see Section 10) shows the complexity of the possible reasoning (41 variables, 12 descriptions, four hierarchical levels). °Ability to decide, taking uncertainty into account: The decision strategy selected in this work has been to draw the values of the searched variables from the distributions obtained by the preceding inference step. This strategy «renders» uncertainty, the decision are nearly deterministic when the distributions are sharp, and conversely, nearly random when they are flat. • Simple and sound theoretical bases: The proposed approach is founded on simple theoretical bases. Essential questions may be asked clearly and formally and eventually answered by mathematical reasoning. For instance, one may consider to fairly compare Bayesian inference and logic as two possible models of reasoning. Thanks to these theoretical bases, the experimental results (successes or even more enlightening failures) may be analyzed and understood in detail. • Generic, systematic and simple programming method: BRP is simple, systematic and generic. Simple, as this method may be learned and mastered easily. Systematic, as it may be applied with rigor and efficiency. Generic, as this method may be also used in numerous other domains than robot programming. • Homogeneity of representations and resolution processes: BRP is based on a unique data structure, called a description, associated with two inference rules. This homogeneity leads to simple and generic program development. • Obligation to state all hypothesis: Choosing a description as the only data structure to specify robotics programs and following a systematic method to do so compel the programmer to exhaustively express his knowledge about the task. Everything that should be known about a given robotic problem is in its description: the synthesis between the preliminary knowledge and the experimental data. There is no hidden knowledge in either the inference program or the decision algorithm. As the description encapsulates all the relevant information, exchanging, sharing or discussing models is easy and rigorous. • Large capacity of expression: Descriptions offer a large capacity of expression to specify models and to question them as well. °Specification capacity: The different experiments described in this paper prove that descriptions may be used to specify numerous different models. Let us recall that we used descriptions to learn simple reactive behaviors (Section 5), to combine them (Section 6), to hierarchically compose them (Section 8), to merge sensor information (Section 6), to recognize situations (Section 8), to carry out temporal sequencing (Section 9) and finally, to specify a task integrating all the previously defined descriptions (Section 10). °Question capacity: Let us also recall that any question may be asked to a joint distribution. Mathematically, all variables appearing in a joint distribution play the exact same role. They may all, indifferently, be known, unknown or searched. The description is neither a direct nor an inverse model. Sensor fusion (Section 6), situation recognition (Section 8) or inverse programming (Section 9) offer instances where the questions asked do not correspond to the specification order. Furthermore, there is no ill-posed problem. If a question may have several solutions, the probabilistic answer will simply have several peaks. Some instances of sensor fusion exemplified this point (see Section 6.3). • Ability for real incremental development of robots: Bayesian Robot Programming, thanks to its clear theoretical foundations and to its rigorous programming methodology, appears to be an incremental method of developing robot programs that can really be used in practice. The final experiment (Section 10) demonstrates that point. °Ability to combine descriptions: The first incremental development tool is description combination (Section 6). With this tool it is possible to define new behaviors as weighted mixtures of different simpler ones. °Ability to compose descriptions: The second incremental development tool is hierarchical description composition (Section 8). It is in some senses similar to calling sub-procedures in classical programming, as some of the parametric forms appearing in a decomposition may be questions addressed to more basic descriptions. °Description = Resource: More generally, a description, as an internal representation of a physical phenomenon, may be considered as a programming ressource. For instance, a description may offer new variables to be used in other descriptions. This is the case with the variable that identifies the object, provided by the object recognition description (Section 8). Object recognition also proposes another example of the use of a description as a programming resource. Indeed, the countour following behavior is a necessary tool to be able for computing the four variables , , and used by the object recognition description. Numerous other possibilities for enhancing the capacity of a robot using descriptions as resources may be found in Dedieu's PhD. thesis [START_REF] Dedieu | La représentation contingente : Vers une reconciliation des approches fonctionnelles et structurelles de la robotique autonome[END_REF].

BRP in practice

BRP is a very simple, practical and efficient way to program robots for the 3 main following reasons:

• BRP proposes a generic methodology for robot programming:

1 -Specification: define the preliminary knowledge.

1.1 -Choose the pertinent variables. 1.2 -Decompose the joint distribution. 1.3 -Define the parametric forms. 2 -Identification : identify the free parameters of the preliminary knowledge 3 -Utilization: ask a question of the joint distribution.

• The conditional independences are used to break the complexity and keep the computation tractable. • BRP may really be considered as a programming language because it proposes three main tools to build complex programs from simpler ones: °Calling Bayesian subroutines. °Probabilistic if-then-else. °I nverse programming to sequence behaviors.

Scalability

This paper presented only very simple instances of robot programming for didactic purposes.

The goal was to illustrate the fundamental principles rather than to present applications. Consequently two fundamental questions are still open: is BRP scalable? may it be used for practical robotics applications?

Elements of answer to these two questions may be found in may be found in other works that used the BRP approach:

• Kamel Mekhnacha build a Bayesian robotic CAD system which offers the usual capa-

O Nlt Nrt

Per Lrl bilities of such a system but also handles the uncertainties. This system works with hundreds of variables and tens of probability distributions [START_REF] Mekhnacha | Méthodes probabilistes baysiennes pour la prise en compte des incertitudes géométriques : Application à la CAO-robotique[END_REF][START_REF] Mekhnacha | A Robotic CAD system using a Bayesian framework[END_REF][START_REF] Mekhnacha | The design and implementation of a Bayesian CAD modeler for robotic applications[END_REF] • Julien Diard proposed in his PhD thesis the concept of Bayesian maps, which is a specialization of the BRP formalism, for representing the environment in navigation tasks. In particular, the descriptions and the combination operators considered in this work are special cases of the one presented here [START_REF] Diard | La carte bayésienne : Un modèle probabiliste hiérarchique pour la navigation en robotique mobile[END_REF]. • Christophe Coué is using BRP for an Advanced Driving Assistance System (ADAS) [START_REF] Coué | Multi-Sensor Data Fusion Using Bayesian Programming: an Automotive Application[END_REF][START_REF] Coué | Using Bayesian Programming for Multi-Sensor Multi-Target Tracking in Automotive Applications[END_REF]. Ongoing works include manipulation with 6 DOF arms, pick and place problems, videogame Bot programming, outdoor SLAM with automotive vehicles and indoor service robotics.

[

Figure 1 :

 1 Figure 1: Structure of a Bayesian program

  Figure 2: The Khepera mobile robot

Figure 3 :

 3 Figure 3: The sensory-motor variables of the Khepera robot.

Figure 4 :

 4 Figure 4: Contour following (superposed images)

Figure 6 :

 6 Figure 6: The result of a sensor fusion for a light source with a bearing of 10°0

  preliminary knowledge is defined by specifications [S7.1], [S7.2], [S7.3], [S7.4] and [S7.5].

  Figure 7:

  phototaxy Prox π-home ⊗ | () P 1 avoidance Prox π-home ⊗ | () P -=

Figure 8 :

 8 Figure 8: Homing behavior (The arrow points out the light source) (superposed images).

(

  phototaxy avoidance

Figure 11 :

 11 Figure 11: The different objects presented to Khepera.

F

[

  of the light source ( ) is estimated by the fusion of the light sensors information.• The command variable is estimated according to the value of . • The outermost sum searches for and ignoring the precise values of the five internal variables.

Figure 13 :

 13 Figure13: The symbolic approach in robotics.

Figure 14 :

 14 Figure14: The BRP approach in robotics.

Figure

  Figure 15: Theoretical foundation.

Table 5

 5 says that idle imposes that Base is true, when patrol, recognition, homing and

	Behavior / Behavior_t-1	idle	patrol	recognition	fire-interv.	homing	recharge
	idle	0.9	x	0	0	x	x
	patrol	x	0.9	xxxx
	recognition	0	x	0.99	0	x	x
	fire-interv.	xxxxxx
	homing	0	x	x	0	0.9	x
	recharge	0	xxxx	0 . 9

Table 2 :

 2

	Vigil / Behavior	idle	patrol	recognition	fire-interv.	homing	recharge
	false	0.9	00x1x
	true	0.1	11x0x

Table 3 :

 3

	Energy / Behavior	idle	patrol	recognition	fire-interv.	homing	recharge
	very-low	0.325	00xx	0 . 8
	low	0.325	0.1	0.1	x	x	0.2
	high	0.25	xxxx0
	very-high	0.1	xxxx0

Table 4 :

 4

Table 6 :

 6

	Base/ Behavior	idle	patrol	recognition	fire-interv.	homing	recharge
	false	0	0.99	0.99	x	0.99	0.99
	true	1	0.01	0.01	x	0.01	0.01
			Table 5:
	Fire / Behavior	idle	patrol	recognition	fire-interv.	homing	recharge
	false	111011
	true	000100
	Identify / Behavior	idle	patrol	recognition	fire-interv.	homing	recharge
	false	xx0xxx
	true	xx1xxx

Table 7 :

 7

											P	Base Behavior π-behavior ⊗ | ()
											P	Fire Behavior π-behavior ⊗ | ()
											P	Identify Behavior π-behavior ⊗ | ()
											π-behavior
								Draw	(	P	(	Behavior Vigil Energy Base Fire Identify Behavior_t-1 π-behavior ⊗⊗ ⊗ ⊗ ⊗ ⊗ |	)	)
	P	(	Behavior Vigil Energy Base Fire Identify Behavior_t-1 π-behavior ⊗⊗ ⊗ ⊗ ⊗ ⊗ |	)
	=	1 Σ ---	×	P	Behavior_t-1 π-behavior | ()	×	P	Behavior Behavior_t-1 π-behavior ⊗ | ()
	.	×	P	Vigil Behavior π-behavior ⊗ | ()	×	P	Energy Behavior π-behavior ⊗ | ()
	.	×	P	Base Behavior π-behavior ⊗ | ()	×	P	Fire Behavior π-behavior ⊗ | ()	×	P	Identify Behavior π-behavior ⊗ | ()

17. http://www-laplace.imag.fr/ENGLISH/PRESENTATION/Semaine-Science/Trans12/T12.small.mov

Bayesian framework.

Specification

Variables

The first variable to consider is , which may take the six preceding values idle, patrol, recognition, fire-intervention, homing and recharge. This variable will be used to select a given behavior.

This selection will be made according to the values of the six following variables: • : a binary variable, used to order the Khepera to work.

Decomposition

At each time step the robot will select a behavior knowing the values of these six variables by answering the question:

It is tempting to specify this distribution directly. It would correspond to the usual programming method where the conditions at time establish what should be done at time . We propose to do the exact opposite. Indeed, it is quite easy, knowing the behavior, to have some notion of the possible values of the variables , , , , and . For instance, if the Khepera is patrolling, it means that it has been necessarily ordered to do so and that is true. Furthermore, we consider that knowing the behavior, these five variables are independent. These assumptions lead to the following decomposition:

Parametric forms

First we chose a uniform a priori value for :

We chose to specify all the other terms of this decomposition as discrete distributions. Their different values will be given a priori, one by one, using tables.

No decision is made except the ultimate one about and . Uncertainty is propagated from the innermost level to the outermost. All the available information is taken into account. The resulting observed robot behavior is, indeed, a probabilistic mixture of the different component descriptions.

Discarding no information has an obvious computational cost. The evaluation of the three levels of cascading sums may be very time consuming. Thus, the programmer may choose to make decisions on any intermediary variables. This choice will always trade a gain of efficiency for a loss of information. For instance, the most efficient possible program would make a decision for all the internal variables:

1 -to decide if the robot is at its base, 2 -to decide the knowing , 3 -to chosoe a movement knowing the , 4 -to decide the position of the light source, 5 -to decide between avoidance and phototaxy, 6 -and finally, to control the robot.

Results, lessons and comments

The results obtained are satisfactory to a human observer. The Khepera performed this task hundreds of time in various environments and conditions. The behavior was very robust; for instance, this experiment ran without interruption, 10 hours a day for three days as a demonstration during a public science fair.

The Movie 5 17 shows the Khepera during one of these experiments. It successively shows:

• Khepera identifying an object,

• Khepera aborting its object recognition due to a possible fire detection,

• Khepera verifying that it is really facing a fire by trying to blow it,

• Khepera extinguishing the fire,

• Khepera patrolling the environment (it stops occasionally to detect movement and sounds an alarm if it succeeds), • Khepera returning to its base.