Mehdi Benallegue

Jean-Paul Laumond

Alain Berthoz

A head-neck-system to walk without thinking

Most of the time, humans do not watch their steps when walking, especially on even grounds. They walk without thinking. How robust is this strategy? How rough can the terrain be to walk this way? Walking performance depends on the dynamical contribution of each part of the body. While it is well known that the head is stabilized during the motions of humans and animals, its contribution to walking equilibrium remains unexplored. To address the question we operate, in simulation, a simplified walking model. We show that the introduction of a stabilized head-neck system drastically improves the robustness to ground perturbations. It significantly influences the dynamics of walking and hence to the balance. Our study is a starting point of a wider research on the involvement of vertebral limbs in the mechanics and control of the human steady gait. It also studies the benefits of such simple control schemes capable to produce complex behaviors.

Introduction

Depending on the nature of the terrain, a walker's foot placement requires more or less attention. On the top part of the pavement depicted by Figure 1, he/she has to anticipate what stones will next be used for stepping. On the other hand, walking on the pavement indicated in bottom part of the figure 1 does not require any anticipation of the foot placement: in this case we walk without thinking. While step watching clearly requires head and gaze control to see the stones, head control is apparently less important when walking on a flat surface. However neurophysiologists have observed that humans and animals stabilize their head when moving, even on flat surfaces. In former studies, we have shown that head stabilization facilitates the fusion of visual and vestibular information. It offers a consistent egocentric reference frame for motion perception and control in general [START_REF] Berthoz | The Brain's Sense of Movement[END_REF] and for locomotion in particular [START_REF] Pozzo | Head stabilization during various locomotor tasks in humans[END_REF][START_REF] Hicheur | Head motion in humans alternating between straight and curved walking path: Combination of stabilizing and anticipatory orienting mechanisms[END_REF]. Our recent results show that head stabilization improves the estimation of the vertical direction by a vestibular-like inertial sensor [START_REF] Farkhatdinov | Modeling verticality estimation during locomotion[END_REF]. Here we contribute to elucidate the role played by the head to maintain balance when walking.

Our novel hypothesis is that the head-neck system plays an important role to balance the human steady gait trajectory, because it not only deals with the tilt estimation within the visuo-vestibular system and the neck position sense, but also it accounts for a substantial contribution to the dynamics of walking due to the head stabilization. Indeed, the head at the top of the body weighs around 8% of the total body mass. It then carries a significant part of the moment of inertia. Thus, head stabilization contributes to reduce the angular momentum of the body. Moreover, it may also be used to balance the walker by controlling reaction torques, similar to tightrope-walkers' poles.

This study is the starting point of a wider research on the involvement of vertebral limbs in the mechanics and control of the human steady gait and the benefits of such simple control schemes capable to produce complex behaviors. The objective is also to improve diagnosis and therapy of unsteadiness and balance disorders, for example in the case of neck sensorimotor diseases [START_REF] Lajoie | Gait of a deafferented subject without large myelinated sensory fibers below the neck[END_REF][START_REF] Stokell | Dynamic and functional balance tasks in subjects with persistent whiplash: a pilot trial[END_REF]. Furthermore, our control models open new routes to design humanoid robots with more efficient and balanced biped locomotion.

We describe briefly hereafter the models and simulations we use to study the influence of the headneck system on the dynamics of gait. Next, the results obtained with this setting are shown followed by a discussion on our interpretations and conclusions. The remaining of the paper consists of a detailed technical description of the materials and methods used to obtain our results.

Models

Based on mechanical concepts from passive robot walkers [START_REF] Collins | Efficient bipedal robots based on passive-dynamic walkers[END_REF][START_REF] Byl | Metastable walking machines[END_REF], we introduce a walking simulation scheme promoting the notion of ground texture as a key factor to study walking balance. Two simple walking mechanical models are then compared. These models include improvements to classical compass-like walkers, by adding torso, interleg actuation, spring-damper at the feet, and rough terrains. These additions are active research topics, but their effects and dynamics are beyond the scope of this paper. We refer then to [START_REF] Collins | Efficient bipedal robots based on passive-dynamic walkers[END_REF][START_REF] Mcgeer | Passive dynamic walking[END_REF][START_REF] Van Der Linde | Passive bipedal walking with phasic muscle contraction[END_REF][START_REF] Su | Dynamic stability of passive dynamic walking on an irregular surface[END_REF][START_REF] Mcgeer | Stability and control of two-dimensional biped walking[END_REF][START_REF] Benallegue | Contribution of actuated head and trunk to passive walkers stabilization[END_REF] for dedicated studies.

In the first of our two models, the walker has a rigid neck and tends to stabilize the torso upright. In the second one the neck is modeled as a limb of two joints and the walker tends to maintain the head direction constant. Both walker models are inspired by the mechanical design of passive walking robots [START_REF] Collins | Efficient bipedal robots based on passive-dynamic walkers[END_REF]. The energy efficiency of these robots, the low-frequency of their control and their natural limit-cycle dynamics are common characteristics with human locomotion [START_REF] Alexander | Walking made simple[END_REF][START_REF] Goswami | Limit Cycles in a Passive Compass Gait Biped and Passivity-Mimicking Control Laws[END_REF]. Indeed, we do not aim at modeling perfectly the human gait. Up to now, only simple dynamical models allow to reproduce locomotion gaits [START_REF] Mombaur | Using optimization to create self-stable human-like running[END_REF]. Dynamical modeling of human walking is out of reach of all current simulators. In our study, we aim at reproducing a broad dynamics of an anthropomorphic walker in a steady limit-cycle gait, similarly to what is done in [START_REF] Donelan | Mechanical work for step-to-step transitions is a major determinant of the metabolic cost of human walking[END_REF][START_REF] Roos | Influence of simulated neuromuscular noise on the dynamic stability and fall risk of a 3d dynamic walking model[END_REF].

Figure 2 illustrates our model. It operates in the sagittal plane. It is made of five articulated rigid bodies: two bodies for the (knee-free) legs, one body for the torso, one for the neck and one for the head. Note that the neck is modeled as an articulated body and not as a simple joint. This setting reflects the property of the head-neck system to have two centers of rotation in the sagittal plane: one at the base of the neck and the other at ear level [START_REF] Viviani | Dynamics of the head-neck system in response to small perturbations: analysis and modeling in the frequency domain[END_REF]. The mass distribution and the limb lengths are anthropometric (e.g., [START_REF] Armstrong | Anthropometry and mass distribution for human analogues[END_REF]).

The first walker (Model A) we consider, has a rigid neck, i.e. the torso, the neck and the head make a single rigid body. The second walker corresponds to the model of head stabilization (Model B): the neck joints are controlled to maintain a zero tilt for the head. Apart from the neck, both walkers have the same controls: the torso is actuated to be stabilized upright while a lightweight controller actuates the inter-leg angle. Finally a velocity driven foot impulsion is given just before the swing phase. The weakness of the control of the lower limbs make them sensitive to perturbations, and their dynamics can differ according to upper-body control.

Both models need to know the orientations of the upper-body segments in order to stabilize them. The model A has a unique orientation to be observed and controlled, since it has a rigid upper-body. The model B has three segments with different orientations. Nonetheless, if we know the orientation of one segment and the two joint-positions of the neck, we can reconstruct the two other orientations. So from sensing viewpoint, for both models, we place a tilt estimator in the head, while neck and torso inclinations are deduced from neck joint angles. This model of sensing is inspired by neurophysiology. Humans have an efficient orientation sensor in the head, including the vestibular systems. They have also a good accuracy in the estimation of neck joint angles, as the neck possesses a dense concentration of proprioceptors [START_REF] Cooper | Muscle spindles in man; their morphology in the lumbricals and the deep muscles of the neck[END_REF]. The estimation of the body segment directions is then obtained by a top-down combination of the neck joints with the head direction given by the vestibular system [START_REF] Berthoz | The Brain's Sense of Movement[END_REF].

Detailed description of the models is presented in the Materials and Methods section.

Simulations

Head stabilization has two types of effects. The first one is mechanical: the head has a non-negligible mass contribution, and the motion of the head influences the dynamics of the body. The second one lies in attitude estimation: different motions generate different inputs on the tilt sensors and may lead to different magnitudes of estimation errors. For the purpose of isolating each effect, we study two sensor models for each walker model. The first one is an ideal tilt sensor, i.e. the head direction is perfectly known. The second one is a simplified model of the vestibular system as presented in [START_REF] Farkhatdinov | Modeling verticality estimation during locomotion[END_REF]: it combines noisy measurements of an accelerometer, a gyrometer and an inclinometer. The ideal sensor makes the walking models equivalent in terms of sensing and it enables us to compare them only from a mechanical point-of-view. The vestibular model permits to reproduce the effects of head motion on the accuracy of tilt esimation, and to study their impact on gait balance. Performance comparison is based on a metric called Mean First Passage Time (MFPT) [START_REF] Byl | Metastable walking machines[END_REF]. MFPT is derived from the classical analysis of metastable systems [START_REF] Talkner | Discrete dynamics and metastability: Mean first passage times and escape rates[END_REF]. This metric aims at providing an estimation of the distance a walker may travel safely. MFPT of walking systems is the average number of steps the walker makes before falling. However, in the context of walking simulation, MFPT estimation is highly time consuming. To overcome this bottleneck we had to introduce a new dedicated simulation algorithm based on limit-cycle properties [START_REF] Benallegue | Metastability for high-dimensional walking systems on stochastically rough terrain[END_REF].

Results

For noise-free environments and sensors, a well-controlled walker may walk indefinitely without falling. In other words, its MFPT is infinite. Perturbations, such as uneven terrains or noisy sensors, give rise to finite MFPTs, i.e. the walker necessarily falls at some stage. In this context, we introduce the notion of textured ground. A textured ground is a terrain for which the unevenness follows a probability law. The texture model consists in changing the slope of the ground at each step, following a centered Gaussian distribution. We can make the terrain more or less rough by changing the standard deviation (SD) of the Gaussian law.

We conducted simulations on four models resulting from the combination of the presence or absence of head stabilization with ideal or vestibular-like tilt sensor respectively. Each model was simulated on a set of different textures (from 0 to 0.1 rad of SD). For each model-texture combination, we computed the corresponding MFPT. The results of these simulations are described hereafter.

Noise-free sensor

In the case of an ideal attitude sensor, on flat terrain, and for both control models, it has not been possible to find an upper bound on MFPTs (see Fig. 3). This confirms the fact that, in the absence of perturbation, a well-controlled walker may walk indefinitely without falling. However walker performances greatly differ as soon as a slight texture change appears. The phenomenon can be seen from the example of 0.01 rad standard deviation. In this case, MFPT of the rigid neck model is 23 steps, while head stabilization guarantees MFPT of more than 3 million steps! This performance improvement persists as the ground texture increases, even if the difference declines. This is purely due to mechanical effects, i.e. to the contribution of the head motion to the balance of the gait.

To better understand this effect, we compare the mechanical powers of A and B models during the period between two impacts of the limit cycle on level ground (Fig. 4-A). The two curves have almost the same integral, which means that they absorb a same amount of the energy between two feet impacts. The important feature is the difference in power consumption during the first 30% of the cycle. The head stabilization enables the walker to absorb less energy during the impact, while distributing the energy consumption over a longer period.

One of the consequences of this delay in energy absorption is on the dynamics of the swing leg. For both models, at the impact, a part of the momentum is transferred into a rotation motion around the new stance foot. But this transfer applies forces and moments on the upper-body. These forces tend to tilt the upper body which compensates this inclination using the torque actuator at the hip. Hip torques absorb an important amount of kinetic energy, and apply moments on the new swing leg which tend to slow its angular velocity. The head-neck system enables to delay a part of this absorption and let the swing leg have a greater initial velocity (Fig. 4-B). Later in the cycle, even if the same amount of energy is absorbed due to the delay, the walker has already reached a more stable configuration where the swing leg is already prepared for the next step.

Indeed, in the case of human gait, as for our simulated models, imbalance caused by uneven and textured ground result mostly in forward falls [START_REF] Smeesters | Disturbance type and gait speed affect fall direction and impact location[END_REF]. A forward fall happens when the swing foot reaches the ground too close to the stance foot, and cannot compensate for the destabilizing linear and angular momenta. When we increase the swing leg velocity in the beginning of the cycle, we enable the walker to reach earlier a balanced position with a forward leg better prepared for the next impact.

This effect suggests that the head-neck system is used to store the mechanical energy and to restore it at the appropriate phase of the walking cycle. These results give an insight into the role of the vertebral column in the management of gait mechanical energy. The whole upper-body inertia and elasticity would store energy and restore it at the right instant, similarly to [START_REF] Gomes | Walking model with no energy cost[END_REF] where the walking model which walks on level ground with zero-energy cost.

As this level we may conclude that head stabilization improves the dynamic balance of walking systems. We show next that the improvement is even better when considering a noisy gravity estimator.

Inertial sensor

If we consider a walker's head equipped with an on-board vestibular-like sensor, the head stabilization minimizes the error of gravity direction estimation [START_REF] Farkhatdinov | Modeling verticality estimation during locomotion[END_REF]. We show here how head stabilization greatly improves the robustness to the estimation error when compared to trunk stabilization. To avoid a combination of mechanical and sensing effects, we compare separately the two sensor models for each walking model. The difference shown in Fig. 5 between the performance of the noise-free sensor walker and the inertial one is only due to a loss in the accuracy of the verticality estimation.

Compared to the noise-free sensor, the root-mean-square error of the tilt estimation is of 3.5 • for Model A and of 0.78 • for Model B. This confirms that head stabilization contributes to a better accuracy of the gravity estimation.

More interesting is the influence of this accuracy on gait balance. Small errors induce important differences in the performances of walking systems on rough terrain as shown in Figure 5: MFPTs for Model B is much greater than MFPTs for Model A and the property holds for any ground texture. Finally, MFPT on a horizontal surface is greater than 10 5 when the head is stabilized, while it is less than 10 for Model A: we see clearly the importance of head stabilization, and how the difference with an ideal sensor becomes negligible on small textures.

Discussion

Our model-based approach of bipedal walking reveals the contribution of head-neck control to the gait dynamics. The effect of head stabilization is twofold. First, it impacts sensing. The dynamics of vestibular-like sensors relies on inertial and gravitational effects, which are driven by accelerations and rotations of the head. Stabilizing the head enables the walker to reduce excitation and to maintain the sensors in local dynamics for a finer posture-estimation.

Second, the effect of head stabilization is mechanical. Head stabilization is an heuristic answer to the question of taking advantage of the head mobility during walking. Indeed, while it is likely not the optimal control of the neck regarding balance, it is a very simple control that produces a complex behavior with significant benefits. It is worth to emphasize that the importance of this mechanical effect is also due to the weakness of lower limbs actuation, which makes them highly sensitive to external forces. Indeed, other stiffer controls can be found for which the mechanical contribution of the head stabilization is reduced. However, stiffer controllers implies increasing energy consumption and control frequency, which does not reflect the natural energy-efficiency of walking without thinking on low textures, where the walkers take maximum advantage of the natural passive dynamics of the body. On the contrary, stiff actuation and high frequency control are required to guarantee balance for highly uneven and unpredictable environments, and in this case head stabilization is not expected to play such an important mechanical role.

These results fit with clinical observations on humans. The unsteadiness and the loss of balance resulting from head-neck system sensorimotor disturbances have been widely documented. Deficiency in neck-joint position sense, as well as its motor abilities have an important impact on balance, whether in chronic neck injuries [START_REF] Lajoie | Gait of a deafferented subject without large myelinated sensory fibers below the neck[END_REF][START_REF] Stokell | Dynamic and functional balance tasks in subjects with persistent whiplash: a pilot trial[END_REF] or in one-time experimental induced impairment [START_REF] Bove | Neck muscle vibration and spatial orientation during stepping in place in humans[END_REF][START_REF] Vuillerme | Postural control during quiet standing following cervical muscular fatigue: effects of changes in sensory inputs[END_REF]. It has even been suggested that the impairments in the neck somatosensory inputs and sensorimotor control are as important for balance as a lower-limb proprioception loss following a knee or an ankle injury [START_REF] Treleaven | Sensorimotor disturbances in neck disorders affecting postural stability, head and eye movement control[END_REF]. Therefore, our study certainly opens new clinical perspectives in diagnosis and therapy.

Finally, other challenging issues remain to be addressed. Similarly to head stabilization and arms swinging, the vertebral limbs, by their mass, flexibility and control, surely have -yet unexplored-dynamical effects on steady gait. Furthermore, coming back to Figure 1, other questions arise. What is the critical value of the ground texture that imposes to watch one's steps? How does the brain switch from a locomotion modality to another one when crossing the line separating the two pavements?

Materials and Methods

This material and methods section is structured as follows. We first discuss neuroscience and robotics models for human walking and we describe how passivity-based walkers gather many of its properties regarding dynamics and control. We describe the walkers models we study in terms of geometry and mass distribution. We then describe the control of the actuators of our models. We present the vestibular sensor model and the state observer we use to reconstruct the attitude of the walker. We switch then to a brief description of the method we introduced to estimate the balance performances of our walkers. We finish by describing briefly the simulation framework and the software environment we use in this study.

Passive-dynamics walkers

Neuroscience has showed a great will to understand the neurophysiological process of gait generation for humans. Several researchers suggest that locomotion patterns in vertebrates, including humans, are mainly generated within the spinal cord rather than in the brain. This generation is usually modeled by the combination of a rhythm generator called Central Pattern Generator (CPG) and reflexes in response to peripheral stimuli [START_REF] Dietz | Spinal cord pattern generators for locomotion[END_REF]. This provides the walker with an attractive limit-cycle behavior when no perturbations occur. This model is not the basis of gait control for the vast majority of biped robots. For them, keeping balance reduces to respect a criterion related to a point on the ground, defined by the contact forces, called Zero Moment Point (ZMP). The criterion is to keep the ZMP strictly inside the surface beneath support limbs [START_REF] Vukobratović | On the stability of anthropomorphic systems[END_REF]. Several approaches showed then the possibility to control the ZMP position to enable safe locomotion [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF]. However, the walking control using these approaches is usually energy inefficient, especially compared to humans. Moreover, the ZMP constraint needs to be respected at each instant, requiring high-frequency control. Frequencies which are far beyond the capabilities of the humans muscular system [START_REF] Alexander | Walking made simple[END_REF].

On the contrary, passive-dynamic walking robots have remarkably close energetic efficiency to humans', without complying to the ZMP balance criterion. The limit-cycle walking of a passive-dynamic robot is also considered as a suitable model for the human natural gait [START_REF] Héliot | Online generation of cyclic leg trajectories synchronized with sensor measurement[END_REF]. In addition, passive-dynamic walkers are commonly assumed to generate visually more human-like motions, even with the presence of geometrical or mechanical discrepancies between the robot and humans [START_REF] Collins | Efficient bipedal robots based on passive-dynamic walkers[END_REF]. Accordingly, this similarity has attracted the interest of biomechanics in order to study the passivity properties of the human gait [START_REF] Goswami | Limit Cycles in a Passive Compass Gait Biped and Passivity-Mimicking Control Laws[END_REF].

The walker models

The models A and B we simulate are the same planar 5 limbs walker (Fig 2). The limbs are: a head with a mass on the top, a neck and a torso with masses at the middle, and the legs, each of which with a mass at distance l l from the hip. Each two successive limbs are attached with a rotational joint. The difference between the models A and B is that the model A has fixed neck, forming a straight rigid upper-boy (see Figure 6). Each leg is ended with a prismatic joint equipped with a spring-damper. We call toe, the bottom of the mobile part of the leg. The hip-toe length l p at the rest position of the spring is denoted by l p,0 . The masses distribution and limbs proportions are anthropometric [START_REF] Armstrong | Anthropometry and mass distribution for human analogues[END_REF] (see Table 1).

Control

During the simulations, the models are always walking, there is always at least a contact between a toe and the surface of the ground. If this condition is not satisfied, the robot is considered as fallen.

Except for toe off impulsion, the controllers for the robot are proportinal-derviative (PD), each of them has two gain parameters. The gains for lower body are chosen to be lightweight, to simulate the low energy consumption of human's steady walk. The upper body has to a bit stiffer to guarantee a successful vertical stabilization for the trunk and the head.

There are two ways for obtaining the values of the control gains. The first and the best one is to use optimization techniques to find out the best parameters of each model according to a balance criterion. However, our criterion, MFPT, is too long to compute and its optimization would take years of computation. The second method, to which we have to resort, is to take the values arbitrarily in the set of values guaranteeing stable steady gait on flat ground. If for several samples of these values, the stabilization phenomenon is still observed, that means that there is a strong probability that it is a general effect on the class of weakly actuated gaits. In our tests, among many reasonable gain values used, the studied effect remains visible as soon as the walkers are stable on flat surface.

The parameters we present hereafter are the values used to obtain the numerical outcomes described in Results section.

Toes. The exchange between the swing phase and the stance phase occurs at impacts. Impacts are considered inelastic and contacts are considered perfect with no slipping. The toe of the stance leg has a spring-damper dynamics. The contact force follows the direction of the stance leg and its magnitude has a proportional-derivative (PD) expression:

f t = -K toe,p (l p -l p,0 ) -K toe,d l p (1)
where K toe,p = 5000 N/m is the elasticity of the spring and K toe,d = 200 N s/m is the damping factor. This force is applied only when it is positive because of the unilateral force constraint of the contact (the ground cannot pull the body). When a leg is in a swing phase, its toe comes back instantly to the rest position l p,0 of the spring, and remains constant until the end of the swing phase. We denote then simply by l p the length of the stance leg.

The walkers loose a part of their mechanical energy at each impact. They require then to be actively fed with an external source of energy. At the instant of take-off of the stance leg, a velocity controlled impulsion is applied to the ground to give propulsion to the robot (Figure 6). The required force for this impulsion is f t :

f t = h( lp,r ) (2)
where lp,r = 1 m.s -1 is the desired velocity and h is the controller function. Most modern dynamic simulators provide implementations of velocity-driven motors. The dynamical simulator solves the problem of finding the exact force that has to be applied to the joint during one time-sample in order to reach the desired velocity. This gives an automatic computation of h which has no closed form. We use it then to apply the force f t during one time-step of simulation. The idea of velocity-driven impulsion is to compensate for energy loss of foot impact. Moreover, by having a constant toe-off velocity at the beginning of each step, we ensure to start every step with comparable levels of energy and momentum. Therefore the impulsion force is smaller for high velocity stepping and bigger for low velocity ones, and this helps to reject a part of the deviations from the limit cycle.

In addition, the propulsion during human gait is of course a subject of debate, but several studies show the role of calf and ankle in the propulsion during the support phase [START_REF] Hill | The mechanics of active muscle[END_REF][START_REF] Winter | Energy generation and absorption at the ankle and knee during fast, natural, and slow cadences[END_REF], their contribution to swing leg initiation [START_REF] Hof | Calf muscle work and segment energy changes in human treadmill walking[END_REF][START_REF] Meinders | The role of ankle plantar flexor muscle work during walking[END_REF] and their involvement in the control of trunk dynamics [START_REF] Neptune | Contributions of the individual ankle plantar flexors to support, forward progression and swing initiation during walking[END_REF]. We wanted then to reproduce a part of these effects with our simplified model of toe-propulsion.

Interleg joint. The inter-leg joint is controlled by a PD pure torque generator toward a reference angle:

τ hip = -K hip,p (θ -θ r ) -K hip,d θ (3)
where K hip,p = 1 N m/rad is the proportional gain, θ r = 0.3 rad is the reference angle and K hip,d = 0.15 N m s/rad is the derivative gain. In order to preserve the natural dynamics of the legs the values of the gains are small.

Trunk. On the other hand, we need to maintain the upper-body globally upright. There are two major approaches that enable passive walkers to control an upper-body. First, the bisector constrained walker, introduced by Wisse et al [START_REF] Wisse | Adding an upper body to passive dynamic walking robots by means of a bisecting hip mechanism[END_REF], is a compass with an upper limb that is constrained to be in the midway angle of the two legs, a successful real design was presented using chains, and has the advantage to be entirely passive. However, beside the fact that it is not an accurate model to human walking, its bisecting constraint introduces an instability, especially in the presence of a heavy upper body [START_REF] Asano | Pseudo virtual passive dynamic walking and effect of upper body as counterweight[END_REF], which is the case for humans. The second method is to stabilize actively the upper body against the vertical, which better models the human gait [START_REF] Winter | The Biomechanics and Motor Control of Human Gait[END_REF]. The stabilization is achieved either by applying torque on both legs [START_REF] Hoshino | A passive walking strategy for a biped robot with a large mass torso by a spring and a damper[END_REF] or more commonly on the stance leg only [START_REF] Mcgeer | Passive dynamic walking[END_REF]. We choose this last solution to not disturb the passive swing motion. The trunk torque is actuated by a pure torque generator, controlled by a PD that brings back the torque to vertical (α = 0):

τ trunk = -K trunk,p α -K trunk,d α (4)
where τ trunk is the trunk-stance-leg torque, K trunk,p = 30 N m/rad is the proportional gain and K trunk,d = 15 N m s/rad is the derivative gain.

Head stabilization. For the model B, there are two other controllers, which are the neck stabilization and head stabilization, they are also controlled by PD pure torque generators. Their torques expressions are the following:

τ neck = -K neck,p γ -K neck,d γ (5)
τ head = -K head,p β -K head,d β (6)
where τ neck is the torque applied to the torso-neck joint, K neck,p = 5 N m/rad is the neck proportional gain, K neck,d = 0.06 N m s/rad is the neck derivative gain, τ head is the torque applied to the neck-head joint, K head,p = 15 N m/rad is the head proportional gain and K head,d = 0.1 N m s/rad is the head derivative gain.

Sensors

The walking models use two models of tilt sensors, both placed in the head. The first one is an ideal sensor, which gives perfect orientation β and angular velocity β measurements. These are directly provided by the dynamic simulator. This sensor does not require any observation technique to retrieve the state of the walker.

The second model of sensors is a 2D version of the model of vestibular system described in [START_REF] Farkhatdinov | Modeling verticality estimation during locomotion[END_REF]. It uses a set of inertial sensors giving noisy measurements that are provided to a Kalman filter in order to reconstruct the attitude of the head. This sensor will be described in depth hereinafter.

For both models, the orientation and the angular velocities of the other limbs α, α, γ and γ are reconstructed by the use of articular angles and angular rates which are considered perfectly accurate. These estimations are used in the control of the upper body of the walker models.

The vestibular sensor

This sensor consists of:

1. An accelerometer, it provides noisy measurements of the acceleration and gravity in the head's frame

a x a z = px cos β -(p z + g) sin β px sin β + (p z + g) cos β + w 1 w 2 (7)
Where (p x , p z ) are the coordinates of the head in the global frame, g is the standard earth's gravity. w 1 and w 2 are the measurement noises.

2.

A gyrometer which provides noisy estimations of the rotation of the head:

r h = β + w 3 ( 8
)
where w 3 is the measurement noise.

3. An inclinometer, which provides the inclination of the head with a slow dynamics, we denote this data by ν, the sensor gives then a noisy estimation of ν.

i h = ν + w 4 (9)
where w 4 is the measurement noise.

The dynamics of the inclinometer is modeled by the dynamics of a damped pendulum of length l i = 2.5 × 10 -3 m, mass m i = 6 × 10 -4 kg and damping factor K i,d = 2.5 × 10 -10 N m s/rad (see Fig. 7).

Due to the small mass and dimensions of the pendulum, we consider the influence of the motion of the inclinometer on the walker's dynamics as negligible. But the motion of the head influences the dynamics of the inclinometer. We describe the dynamics of µ = ν + β the inclination of the pendulum in the global frame:

μi = (-m i l i g sin µ -m i l i (p x cos µ + pz sin µ) -K i,d ( μ -β)) I i ( 10
)
where

I i = m i l 2
i is the moment of inertia of the pendulum.

The accelerometers and the gyrometer represent the phasic system of the vestibular system, which detects mostly peaks in acceleration and jerk. For this reason, we give them higher noise levels but fast dynamics. The inclinometer, with a lower-level noise, reflects the linear dynamics of the tonic system at lower-frequencies [START_REF] Av-Ron | An investigation of tonic versus phasic firing behavior of medial vestibular neurons[END_REF]. Therefore, we make sure that the measurement noise vector w = (w 1 w 2 w 3 w 4 ) T follows a multivariate centered Gaussian white noise, with the following covariance matrix:

R =     2.5 × 10 -3 0 0 0 0 2.5 × 10 -3 0 0 0 0 9 × 10 -2 0 0 0 0 3 × 10 -4     (11)

Other modeled dynamics

In order to use these measurements to reconstruct the head orientation β, we need to have a model of the dynamics of β. The torque on the head τ head is known, because it is provided by the on-board stabilization controller. The orientation dynamics is described by the following differential equation:

β = τ head + gm h (c z sin β + c x cos β) I head + v 1 (12)
where I head = m h l 2 h is the moment of inertia of the head, v 1 is the process noise and (c x , c y ) are the coordinates of the head's center of mass (CoM) in the head's reference frame which is located at the head-neck joint. This model of β is wrong, and this is not how we simulate the dynamics of the head. This model is just used to predict the head dynamics by using only given data, state variables and known inputs. The error between this model and the real dynamics are integrated to the process noise v 1 .

Finally, we don't know the dynamics of the linear accelerations of the head (p x , pz ). We make then the simplest assumption by considering that this acceleration is zero. The process noises v 2 and v 3 represent the committed modeling error: px = v 2 (13)

pz = v 3 (14)

Kalman filtering for observing the orientation

We use an extended Kalman filter to exploit the signal vector y = (a 1 a 2 r h i h ) T and the dynamics models to reconstruct the inclination of the head β. Therefore, we define the sensor state vector s = (β β µ μ px pz ). The state's dynamics and the measurements are time-discretized:

s k = f (s k-1 , τ head,k-1 ) + v k (15)
y k = g(s k-1 ) + w k ( 16
)
where k is the index of the current time-sample, v k is the process noise and f and g are the functions describing the state dynamics and the measurements, respectively. The modeling errors of the function f are represented by process errors. The process error vector v k = (0 v 1,k 0 0 v 2,k v 3,k ) T follows also a multivariate centered Gaussian white noise, with the following covariance matrix:

Q =         0 0 0 0 0 0 0 0.125 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 × 10 4 0 0 0 0 0 0 1 × 10 4         (17)
Once these definitions given, we can describe the observer. The extended Kalman filter enables to reconstruct the state s by minimizing the quadratic error. The estimation of s is denoted ŝ and its update equations are :

ŝ- k = f (ŝ k-1 , τ head,k-1 ) (18)
P - k = F k P k-1 F T k + Q (19)
K k = P - k G T k (G k P - k G T k + R) -1 (20) ŝk
= ŝ- k + K k (y k -g(ŝ k )) (21)
P k = (I -K k G)P - k (22)
where ŝk is the prediction of the k-th state, K k is the Kalman gain, P - k and P k are the error covariance matrices of ŝk and ŝk respectively. We choose to set the initial value of the state to s 0 = 0 and the initial error covariance matrix to:

P 0 =        
1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 0 0 0 0 0 100

        (23)

MFPT estimation

MFPT of a walking system, is the mean number of steps it makes before to fall. This balance metric has been introduced by Byl and Tedrake [START_REF] Byl | Metastable walking machines[END_REF]. However, the proposed methods are either to use Monte-Carlo sampling, or to discretize all the state-space and to use Markov chain model. The first method is timeconsuming especially for rare falls. The second method can only be used for low-dimensional walking systems and cannot be extended to complex walkers.

For this reason, we propose a method which relies on the presence of an attractive limit-cycle [START_REF] Benallegue | Metastability for high-dimensional walking systems on stochastically rough terrain[END_REF]. This method can be used for complex systems and takes much lower computation time than Monte-Carlo sampling.

The dynamics of walking systems is cyclic. At each step, there is an impact and a swing phase. If we know the pre-impact state of the walker, all the state evolution is predictable during this state until the following impact. This property is particularly interesting on textured ground, because the next impact itself is not predictable when the slope is uncertain. Therefore, it is enough to have the sequence of preimpact states to be able to reconstruct all the dynamics of the walking system. The pre-impact states constitute a manifold called Poincaré section and the intersection of the dynamics with this manifold is called a first recurrence map or a Poincaré map.

The state vector of the robot is: ξ = (θ, θ, η, φ, α, α, γ, γ, β, β, l p , l p ). The limit cycle has then one intersection with the Poincaré section in a given state ξ l (see Table 2 for the values of ξ l for our models, note that the displayed precision is necessary as the dynamics is sensitive to perturbations in the value of the limit-cycle). However, the walking dynamics stops intersecting the Poincaré section when the walker falls. For simplifications, we gather all the fall-states into one symbol ξ f (see Fig 8). The number of steps is then the number of times the walker's state intersects the Poincaré section before to reach ξ f .

The estimation of MFPT proceeds as follows:

1. use sampling technique, each sample starts with initial state ξ l , simulate the dynamics, and stops either when the walker comes back to the limit cycle ξ l (success) or falls and reaches ξ f (failure).

2. for each sample, record the number of steps, and the "success" or "failure" answer.

3. obtain estimations of p f , the probability of a sample to fail, n f the mean number of steps of a failure and n l the mean number of steps of a success.

4. compute r = 1-p f p f
the mean number of returns to the limit cycle before to fall.

5. MFPT is then estimated by n = r n l + n f .

A "success" sample is a simulation where the walker comes back to the limit cycle. However, the probability that any walker's state is exactly equal to ξ l is zero. This means that the walker almost never actually reaches the limit cycle state. Thus, instead of checking equality with ξ l in order to detect the return to the limit-cycle, we check if the current state in inside a given neighborhood Ξ l of ξ l .

Consequently, before to start estimating MFPT, our method requires two data: the limit-cycle state ξ l and a suitable neighborhood Ξ l . To obtain them, we make a rough sampling of 8000 states in the statespace of the walker, and we simulate the walking motion, on flat ground, until it falls or it convergences to the limit-cycle. If a simulated motion does not fall, we assume that an accurate convergence to the limit cycle happens after 400 steps. In a perfect environment and simulation, the walker's state is supposed to converge to a unique limit value ξ l . But due to numerical rounding and to simulation errors, the states have still multiple values even after the convergence. So for each viable sample, we record the states between the 400th and the 500th step. This gives a set of ξi of recorded states after the convergence. This set of states describes a small area in the state space within which the dynamics of the walker's state changes: it is no longer attracted to a limit-state ξ l , but it generates a local chaotic behavior. We call this area the limit kernel. This area is attractive, in the sense that, on flat ground, when the state is outside of it, the dynamics will make it converge to the limit kernel, and in case the walker doesn't fall, the state will enter the area in a finite number of steps with probability 1. Moreover, if the state is inside the limit kernel, it will never go out, in the absence of disturbances. The limit kernel is then the suitable definition for our neighborhood Ξ l .

Even in the absence of a unique value of the limit-cycle state, the simulation still requires an estimation of ξ l , because it is the initial state of the walker when estimating MFPT. We approximate ξ l by the mean value of the set of ξi (see Table 2).

The limit kernel Ξ l is approximated by a multidimensional ellipsoid such that:

ξ ∈ X l ⇐⇒ (ξ -ξi ) T C(ξ -ξi ) < d 0 (24)
where C = (cov{ ξi }) + is the semi positive definite matrix defined by the Moore-Penrose pseudoinverse of the covariance matrix of the set { ξi }, and d 0 is a threshold defining the size of Ξ l . For our case, we take d 0 = 1000. More details and discussions of this approach, comparisons with existing methods and generalizations to cases of bifurcations and chaos are available in [START_REF] Benallegue | Metastability for high-dimensional walking systems on stochastically rough terrain[END_REF].

Simulations

Simulations are performed in a tailored c++ framework for simulating passivity based walkers. The resolution of the dynamics integration is achieved using the dynamic simulator Open Dynamics Engine (ODE). This dynamics engine has the advantage to solve the dynamics of mechanical systems subject to constraints, such as unilateral contacts and joint constraints. It provides also ideal controllers for velocity referenced linear and angular motors, which are necessary for the generation of the impulsion at the toe take-off of our models.

Since the walker has no knees, the swing leg always touches the ground when both legs are aligned. This contact is undesirable and the simulation has then to take care of this aspect by ignoring the contacts of the swing leg until the inter-leg angles exceeds a threshold, the collision detection is then activated to catch the actual impact with the ground. A fall is spotted by detecting a contact between the floor and a non-support limb. The ground slope is changed after the toe-off to simulate the texture of the ground. This texture is equivalent to having a polygonal ground (see Figure 1).

The time-discretization is of 1 KHz, but a special simulation time-sample is set to 0.1 ms at the double support instant in order to increase the physical realism of the impacts. This framework simulates over 25 steps by second. This enables a fast exploration of the possible dynamics of the walker on textured ground, and makes computation-time accessible for the estimation of MFPT when using our proposed method. Mean number of steps with an ideal orientation sensor. Mean number of steps of the walker models equipped with an ideal orientation sensor on different textures of the ground. By texture we mean the standard deviation of the ground slope. MFPTs are displayed in logarithmic scale. For higher ground roughness, MRPT of both models drops such that they need to change their walking control: watching their step becomes necessary. Figure 4. Mechanical power and leg velocity over the walking limit cycle. A-The mechanical power during phases of limit-cycle on flat ground. From 0% to 30% of the cycle, the distribution of the mechanical energy consumption is different, the head stabilization offers a lower absorbtion following the impact. B-The angular velocity of the swing leg during the limit-cycle. The influence of the machanical power difference in the first 5% is visible, the swing leg has a better initial velocity until 30% of the cycle.

Figure 5. Mean number of steps with ideal and vestibular sensors. MFPTs of both models with inertial sensor are compared to MFPTs with ideal one. We see in B that when we stabilize the head, we have the same performances with and without ideal sensor against relatively small perturbations. If we don't stabilize the head (in A), the estimation errors still degrade the MFPT even for high roughness of the ground. Figure 6. The models' actuations. On the left, we see the two models of upper-body (for model A and model B). On the right, a scheme of the spring-damper at impact and the impulsion at take-off. The precision of this estimation is necessary as the step dynamic is very sensitive to its initial state.

Figure 1 .

 1 Figure 1. Pavement in Roma: two textured grounds. In the bottom part, we walk without thinking, in the upper part, one has to watch his/her step.

Figure 2 .Figure 3 .

 23 Figure 2. A representation of the models we simulate. The A model is the same structure subject to the constraints α = β = γ. The B model has stabilized neck joints. The rough terrain is modeled with a slope change at each step.

Figure 7 .

 7 Figure 7. The inclinometer model with a damped pendulum. The slow dynamics of this sensor delays the sensor's response and makes it more accurate when stabilized.

Figure 8 .

 8 Figure 8. Representation of poincaré map for limit-cycle walking system. The solid line represents the dynamics of the state. The green loop represents the attractive limit cycle. The red ball represent fall-state. The blue plane represent the Poincaré section. The dynamics intersect the Poincaré section in a sequence of states.

Table 1 .

 1 The parameters of our simulated walkerLength (m) Mass (Kg) Head l h =0.09 m h = 0.4 Neck l n =0.07 m n = 0.1 Torso l t =0.75 m t = 4.5 Leg l p,0 = 1 m l = 1.5 Leg CoM l l = 0.40The proportions of segments lengths and masses are anthropometric.

Table 2 .

 2 The value of the limit-cycle state for each model. -2.8762875858822364 × 10 -2 -2.8922093483844728 × 10 -2 α (rad/s) -2.833396497756952 × 10 -1 -2.7748692131065689 × 10 -1 γ (rad) -2.8762875858822364 × 10 -2 -2.600560458444371 × 10 -2 γ (rad/s) -2.833396497756952 × 10 -1 -6.5999316473546024 × 10 -2 β (rad) -2.8762875858822364 × 10 -2 -4.486308262077859 × 10 -3 β (rad/s) -2.833396497756952 × 10 -1 -1.3160142438761284 × 10 -2 l p (m) -1.1240788365238969 × 10 -2 -1.2773555160365727 × 10 -2 l p (m/s) 1.5310682674033354 × 10 -2 -1.2773555160365727 × 10 -2

		Rigid neck (model A)	Head stabilization (model B)
	θ (rad)	6.2299180819971001 × 10 -1	5.1725140512546985 × 10 -1
	θ (rad/s) -2.6420926894326163 × 10 -1	1.0569297195519001
	η (rad/s)	1.5756657271195875	1.31670983108577720
	φ (rad)	0	0
	α (rad)

Acknowledgments

References


Nicolas Drougard

Florent Teichteil-Königsbuch

Jean-Loup Farges

Didier Dubois

Structured Possibilistic Planning Using Decision Diagrams

Qualitative Possibilistic Mixed-Observable MDPs (π-MOMDPs), generalizing π-MDPs and π-POMDPs, are well-suited models to planning under uncertainty with mixed-observability when transition, observation and reward functions are not precisely known and can be qualitatively described. Functions defining the model as well as intermediate calculations are valued in a finite possibilistic scale L, which induces a finite belief state space under partial observability contrary to its probabilistic counterpart. In this paper, we propose the first study of factored π-MOMDP models in order to solve large structured planning problems under qualitative uncertainty, or considered as qualitative approximations of probabilistic problems. Building upon the SPUDD algorithm for solving factored (probabilistic) MDPs, we conceived a symbolic algorithm named PPUDD for solving factored π-MOMDPs. Whereas SPUDD's decision diagrams' leaves may be as large as the state space since their values are real numbers aggregated through additions and multiplications, PPUDD's ones always remain in the finite scale L via min and max operations only. Our experiments show that PPUDD's computation time is much lower than SPUDD, Symbolic-HSVI and APPL for possibilistic and probabilistic versions of the same benchmarks under either total or mixed observability, while still providing high-quality policies.

Introduction

Many sequential decision-making problems under uncertainty can be easily expressed in terms of Markov Decision Processes (MDPs) [START_REF] Bellman | A Markovian Decision Process[END_REF]. Partially Observable MDPs (POMDPs) [START_REF] Smallwood | The Optimal Control of Partially Observable Markov Processes Over a Finite Horizon[END_REF] take into account situations where the system's state is not totally visible to the agent. Finally, the Mixed Observable MDP (MOMDP) framework [START_REF] Ong | Planning under uncertainty for robotic tasks with mixed observability[END_REF][START_REF] Araya-López | A closer look at MOMDPs[END_REF]) generalizes both previous ones by considering that states can be expressed in terms of two parts, one visible and the other hidden to the agent, which reduces the dimension of the infinite belief space. With regard to POMDPs, exact dynamic programming algorithms like incremental pruning [START_REF] Cassandra | Incremental pruning: A simple, fast, exact method for partially observable markov decision processes[END_REF] can only solve very small problems: many approximation algorithms have been proposed to speed up computations while controlling the quality of the resulting policies [START_REF] Pineau | Point-based value iteration: An anytime algorithm for pomdps[END_REF][START_REF] Smith | Heuristic search value iteration for pomdps[END_REF][START_REF] Kurniawati | SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces[END_REF]. In this paper, we proceed quite differently: we start with an approximated qualitative model that we exactly solve.

Qualitative possibilistic MDPs (π-MDPs), POMDPs (π-POMDPs) and more broadly MOMDPs (π-MOMDPs) were introduced in [START_REF] Sabbadin | Possibilistic markov decision processes[END_REF][START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF][START_REF] Sabbadin | A possibilistic model for qualitative sequential decision problems under uncertainty in partially observable environments[END_REF][START_REF] Drougard | Qualitative Possibilistic Mixed-Observable MDPs[END_REF]). These possibilistic counterparts of probabilistic models are based on Possibility Theory [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty (traduction revue et augmentée de "Théorie des Possibilités[END_REF] and more specifically on Qualitative Decision Theory [START_REF] Dubois | Decisiontheoretic foundations of qualitative possibility theory[END_REF][START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]. A possibility distribution, classically models imprecision or lack of knowledge about the model. Links between probabilities and possibilities are theoretically well-understood: possibilities and probabilities have similar behaviors for problems with low entropy probability distributions [START_REF] Dubois | Probability-possibility transformations, triangular fuzzy sets and probabilistic inequalities[END_REF]. Using Possibility Theory instead of Probability Theory in MOMDPs necessarily leads to an approximation of the initial probabilistic model [START_REF] Sabbadin | Empirical comparison of probabilistic and possibilistic markov decision processes algorithms[END_REF], where probabilities and rewards are replaced by qualitative statements that lie in a finite scale (as opposed to continuous ranges in the probabilistic framework), which results in simpler computations. Furthermore, in presence of partial observability, this approach benefits from computations on finite belief state spaces, whereas probabilistic MOMDPs tackle infinite ones. It means that the same algorithmic techniques can be used to solve π-MDPs, π-POMDPs or π-MOMDPs. What is lost in precision of the uncertainty model is saved in computational complexity.

Nevertheless, existing works on π-(MO)MDPs do not totally take advantage of the problem structure, i.e. visible or hidden parts of the state can be themselves factored into many state variables, which are flattened by current possibilistic approaches. In probabilistic settings, factored MDPs and Symbolic Dynamic Programming (SDP) frameworks [START_REF] Boutilier | Stochastic dynamic programming with factored representations[END_REF][START_REF] Hoey | Spudd: Stochastic planning using decision diagrams[END_REF] have been extensively studied in order to reason directly at the level of state variables rather than state space in extension. However, factored probabilistic MOMDPs have not yet been proposed to the best of our knowledge, probably because of the intricacy of reasoning with a mixture of a finite state subspace and an infinite belief state subspace due to the probabilistic model -contrary to the possibilistic case where both subspaces are finite. The famous algorithm SPUDD [START_REF] Hoey | Spudd: Stochastic planning using decision diagrams[END_REF]) solves factored probabilistic MDPs by using symbolic functional representations of value functions and policies in the form of Algebraic Decision Diagrams (ADDs) [START_REF] Bahar | Algebric decision diagrams and their applications[END_REF], which compactly encode realvalued functions of Boolean variables: ADDs are directed acyclic graphs whose nodes represent state variables and leaves are the function's values. Instead of updating states individually at each iteration of the algorithm, states are aggregated within ADDs and operations are symbolically and directly performed on ADDs over many states at once. However, SPUDD suffers from manipulation of potentially huge ADDs in the worst case: for instance, expectation involves additions and multiplications of real values (probabilities and rewards), creating other values in-between, in such a way that the number of ADD leaves may equal the size of the state space, which is exponential in the number of state variables. Therefore, the work presented here is motivated by the simple observation that symbolic operations with possibilistic MDPs would necessarily limit the size of ADDs: indeed, this formalism operates over a finite possibilistic scale L with only max and min operations involved, which implies that all manipulated values remain in L.

This paper begins with a presentation of the π-MOMDP framework. Then we present our first contribution: a Symbolic Dynamic Programming algorithm for solving factored π-MOMDPs named Possibilistic Planning Using Decision Diagram (PPUDD). This contribution alone is insufficient, since it relies on a belief-state variable whose number of values is exponential in the size of the state space. Therefore, our second contribution is a theorem to factorize the belief state itself in many variables under some assumptions about dependence relationships between state and observation variables of a π-MOMDP, which makes our algorithm more tractable while still exact and optimal. Finally, we experimentally assess our approach on possibilistic and probabilistic versions of the same benchmarks: PPUDD against SPUDD and APRICODD (St-aubin, [START_REF] St-Aubin | Apricodd: Approximate policy construction using decision diagrams[END_REF] under total observability to demonstrate that generality of our approximate approach does not penalize performances on restrictive submodels; PPUDD against symbolic HSVI [START_REF] Sim | Symbolic heuristic search value iteration for factored pomdps[END_REF]) and APPL [START_REF] Kurniawati | SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces[END_REF][START_REF] Ong | Planning under uncertainty for robotic tasks with mixed observability[END_REF]) under mixed-observability.

Qualitative Possibilistic MOMDPs

Qualitative Possibilistic Mixed-Observable MDPs (π-MOMDPs) have been first formulated in [START_REF] Drougard | Qualitative Possibilistic Mixed-Observable MDPs[END_REF]. Let us define L = {0, 1 k , . . . , k-1 k , 1}, the fixed possibilistic scale (k ∈ N * ). A possibility distribution over the state space S is a function π : S → L which verifies the possibilistic normalization: max s∈S π(s) = 1. This distribution ranks plausibilities of events: π(s) < π(s ′ ) means that s is less plausible than s ′ . A π-MOMDP is defined by a tuple S = S v × S h , A, L, T π , O, Ω π , µ where:

• S = S v × S h is a finite set of states composed of states in S v visible to the agent and states in S h hidden to it;

• A is a finite set of actions; The state's hidden part may initially not be entirely known: an estimation can be however available, expressed in terms of a possibility distribution β 0 : S h → L called initial possibilistic belief state. For instance, if ∀s h ∈ S h , β 0 (s h ) = 1, the initial hidden state is completely unknown; if ∃s h ∈ S h such that ∀s h ∈ S h , β 0 (s h ) = δ s h ,s h (Kronecker delta), the initial hidden state is known to be s h . Let us use the prime notation to label the symbols at the next time of the process (e.g. β ′ for the next belief) and the unprime one at the current time (e.g. a for the current action). By using the possibilistic version of Bayes' rule [START_REF] Dubois | The logical view of conditioning and its application to possibility and evidence theories[END_REF], the belief state's update under mixed-observability is [START_REF] Drougard | Qualitative Possibilistic Mixed-Observable MDPs[END_REF]

) ∀s ′ h ∈ S h : β ′ (s ′ h ) = 1 if s ′ h ∈ argmax s ′ h ∈S h π ( o ′ , s ′ v , s ′ h | s v , β, a )> 0 π ( o ′ , s ′ v , s ′ h | s v , β, a ) otherwise, (1) denoted by β ′ = U (β, a, s v , s ′ v , o ′ ).
The set of all beliefs over S h is denoted by B π . Note that B π is finite of size #L #S h -(#L -1) #S h unlike continuous probabilistic belief spaces B [0, 1] S h . It yields a belief finite-state π-MDP over S v × B π , named state space accessible to the agent, whose transitions are [START_REF] Drougard | Qualitative Possibilistic Mixed-Observable MDPs[END_REF]

): π ( s ′ v , β ′ | s v , β, a ) = max s ′ h ∈S h o ′ |β ′ =U (β,a,sv,s ′ v ,o ′ ) π ( o ′ , s ′ v , s ′ h | s v , β, a ) .
Finally, preference over (s v , β) is defined such that this paired state is considered as good if it is necessary (according to β) that the system is in a good state:

µ(s v , β) = min s h ∈S h max { µ(s v , s h ), 1 -β(s h ) } .
A stationary policy is defined as a function δ : S v ×B π → A and the set of such policies is denoted by ∆. For t ∈ N,

s t s t+1 π ( s t+1 | s t , a t ) π ( o t | s t, a t-1 ) π ( o t+1 | s t+1, a t ) s v,t s v,t+1 s h,t s h,t+1 a t a t-1 o t o t+1 Figure 1: Dynamic influence diagram of a (π-)MOMDP the set of t-length trajectories starting in state x = (s v , β) ∈ S v × B π by following policy δ is denoted by T δ t (x). For a trajectory τ ∈ T δ t (x), τ (t ′ ) is the state visited at time step t ′
t and its quality is defined as the preference of its terminal state: µ(τ ) = µ(τ (t)). The value (or utility) function of a policy δ in a state x = (s v , β) ∈ S v × B π is defined as the optimistic quality of trajectories starting in x:

V δ (x) = +∞ max t=0 max τ ∈T (δ) t (x) min{π(τ | x 0 = x, δ), µ(τ (t))}
By replacing max by and min by ×, one can easily draw a parallel with probabilistic MDPs' expected criterion with terminal rewards. The optimal value function is defined as:

V * (x) = max δ∈∆ V δ (x) , x = (s v , β) ∈ S v × B π .
As proved in [START_REF] Drougard | Qualitative Possibilistic Mixed-Observable MDPs[END_REF], there exists an optimal stationary policy δ * ∈ ∆, which is optimal over all history-dependent policies and independent from the initial state, which can be found by dynamic programming if there exists an action a such that π

( s ′ v , β ′ | s v , β, a ) = δ (sv,β),(s ′ v ,β ′ ) (Kronecker delta). This assumption is satis- fied if π ( s ′ | s, a ) = δ s,s ′ (state does not change) and π ( o ′ | s ′ , a ) = 1 ∀s ′ , o ′ (
agent does not observe). Action a is similar to the discount factor in probabilistic MOMDPs; it allows the following dynamic programming equation to converge in at most #S v × #B π iterations to the optimal value function V * :

V * t+1 (x) = max a∈A max x ′ ∈Sv×B π min{π(x ′ | x, a), V * t (x ′ )}, (2)
with initialization V * 0 (x) = µ(x). This hypothesis is yet not a constraint in practice: in the returned optimal policy δ * , action a is only used for goals whose preference degree is greater than possibility degree of transition to better goals. For a given action a and state s, we note q a (x) = max x ′ ∈Sv×B π min{π(x ′ | x, a), V * t (x ′ )} which is known as the Q-value function.

This framework does not consider s v nor β to be themselves factored into variables, meaning that it does not tackle factored π-MOMDPs. In the next section, we present our first contribution: the first symbolic algorithm to solve factored possibilistic decision-making problems.

Solving factored π-MOMDPs using symbolic dynamic programming

Factored MDPs [START_REF] Hoey | Spudd: Stochastic planning using decision diagrams[END_REF]) have been used to efficiently solve structured sequential decision problems under probabilistic uncertainty, by symbolically reasoning on functions of states via decision diagrams rather than on individual states. Inspired by this work this section sets up a symbolic resolution of factored π-MOMDPs, which assumes that S v , S h and O are each cartesian products of variables. According to the previous section, it boils down to solving a finite-state belief π-MDP whose state space is in the form of

S v,1 × • • • × S v,m × B π
, where each of those state variable spaces is finite. We will see in the next section how B π can be further factorized thanks to the factorization of S h and O. While probabilistic belief factorization in [START_REF] Boyen | Exploiting the architecture of dynamic systems[END_REF][START_REF] Shani | Efficient add operations for point-based algorithms[END_REF]) is approximate, the one presented here relies on some assumptions but is exact. For now, as finite state variable spaces of size K can be themselves factored into ⌈log 2 K⌉ binary-variable spaces (see [START_REF] Hoey | Spudd: Stochastic planning using decision diagrams[END_REF])), we can assume that we are reasoning about a factored belief-state π-MDP whose state space is X = (X 1 , . . . , X n ), n ∈ N * and ∀i, #X i = 2.

t t + 1 X 1 X 2 . . . X ′ 1 X ′ 2 . . . a t a t-1 T a,1 T a,2
Dynamic Bayesian Networks (DBNs) [START_REF] Dean | A model for reasoning about persistence and causation[END_REF]) are a useful graphical representation of process transitions, as depicted in Figure 2. In DBN semantics, parents(X ′ i ) is the set of state variables on which X ′ i depends. We assume that parents(X ′ i ) ⊂ X, but methods are discussed in the literature to circumvent this restrictive assumption [START_REF] Boutilier | Correlated action effects in decision theoretic regression[END_REF]). In the possibilistic settings, this assumption allows us to compute the joint possibility transition as π

( s ′ v , β ′ | s v , β, a ) = π ( X ′ | X, a ) = min n i=1 π ( X ′ i | parents(X ′ i ), a )
. Thus, a factored π-MOMDP can be defined with transition functions

T a,i = π ( X ′ i | parents(X ′ i ), a )
for each action a and variable X ′ i . Each transition function can be compactly encoded in an Algebraic Decision Diagram (ADD) [START_REF] Bahar | Algebric decision diagrams and their applications[END_REF]). An ADD, as illustrated in Figure 3a, is a directed acyclic graph which compactly represents a real-valued function of binary variables, whose identical sub-graphs are merged and zero-valued leaves are not memorized. The possibilistic update of dynamic programming, i.e. Equation 2, can be rewritten in a symbolic form, so that states are now globally updated at once instead of individually ; the Q-value of an action a ∈ A can be decomposed into independent computations thanks to the following proposition: Proposition 1. Consider the current value function V * t : {0, 1} p → L. For a given action a ∈ A, let us define: -

q a 0 = V * t (X ′ 1 , • • • , X ′ n ), -q a i = max X ′ i ∈{0,1} min ( X ′ i | parents(X ′ i ), a
) , q a i-1 , Then, the possibilistic Q-value of action a is: q a = q a n . Proof.

q a = max (s ′ v ,β ′ )∈Sv ×B π min{π(s ′ v , β ′ |sv, β, a), V * t (s ′ v , β ′ )} = max X ′ ∈Sv ×B π min n min i=1 π X ′ i parents(X ′ i ), a , V * t (X ′ ) = max X ′ n ∈{0,1} min π X ′ n parents(X ′ n ), a , • • • max X ′ 2 ∈{0,1} min π X ′ 2 parents(X ′ 2 ), a , max X ′ 1 ∈{0,1} min{π X ′ 1 parents(X ′ 1 ), a ,V * t (X ′ )} • • •
where the last equation is due to the fact that, for any variables x, y ∈ X , Y finite spaces, and any functions ϕ : X → L and ψ : Y → L, we have:

max y∈Y min{ϕ(x), ψ(y)} = min{ϕ(x), max y∈Y ψ(y)}
The Q-value of action a, represented as an ADD, can be then iteratively regressed over successive post-action state KEY true false

X ′ 1 1 X 1 X 2 1 3 2 3 (a) ADD en- coding T a,1 of Fig. 2 ✄ ✂ ✁ min X ′ 1 X ′ 2 0 2 3 1 , X ′ 1 1 X 1 X 2 1 3 2 3 = X ′ 1 X 1 X 2 1 3 2 3 0 ------→ ✄ ✂ ✁ max X ′ 1 X 1 X 2 1 3 2 3
(b) Symbolic regression of the current Q-value ADD combined with the transition ADD of Figure 3a Figure 3: Algebraic Decision Diagrams for PPUDD variables X ′ i , 1 i n. The following notations are used to make it explicit that we are working with symbolic functions encoded as ADDs: -

✄ ✂ ✁ min { f, g } where f and g are 2 ADDs; - ✄ ✂ ✁ max Xi f = ✄ ✂ ✁ max f Xi=0 , f Xi=1 ,
which can be easily computed because ADDs are constructed on the basis of the Shannon expansion: f = X i • f Xi=0 + X i • f Xi=1 where f Xi=1 and f Xi=0 are sub-ADDs representing the positive and negative Shannon cofactors (see Fig. 3a).

Figure 3b illustrates the possibilistic regression of the Qvalue of an action for the first state variable X 1 and leads to the intuition that ADDs should be far smaller in practice under possibilistic settings, since their leaves lie in L instead of R, thus yielding more sub-graph simplifications.

Algorithm 1 is a symbolic version of the π-MOMDP Value Iteration Algorithm [START_REF] Drougard | Qualitative Possibilistic Mixed-Observable MDPs[END_REF], which relies on the regression scheme defined in Proposition 1. Inspired by SPUDD [START_REF] Hoey | Spudd: Stochastic planning using decision diagrams[END_REF], PPUDD means Possibilistic Planning Using Decision Diagrams. As for SPUDD, it needs to swap unprimed state variables to primed ones in the ADD encoding the current value function before computing the Q-value of an action a (see Line 5 of Algorithm 1 and Figure 3b). This operation is required to differentiate the next state represented by primed variables from the current one when operating on ADDs.

We mentioned at the beginning of this section that belief variable B π could be transformed into ⌈log 2 K⌉ binary variables where K = #L #S h -(#L -1) #S h . However,

Algorithm 1: PPUDD 1 V * ← 0 ; V c ← µ ; δ ← a ; 2 while V * = V c do 3 V * ← V c ; 4 for a ∈ A do 5 q a ← swap each X i variable in V * with X ′ i ; 6 for 1 i n do 7 q a ← ✄ ✂ ✁ min { q a , π( X ′ i | parents(X ′ i ), a ) } ; 8 q a ← ✄ ✂ ✁ max X ′ i q a ; 9 V c ← ✄ ✂ ✁ max { q a , V c } ;
10 update δ to a where q a = V c and V c > V * ; 11 return (V * , δ) ; this K can be very large so we propose in the next section a method to exploit the factorization of S h and O in order to factorize B π itself into small belief subvariables, which will decompose the possibilistic transition ADD into an aggregation of smaller ADDs. Note that PPUDD can solve π-MOMDPs even if this belief factorization is not feasible, but it will manipulate bigger ADDs.

π-MOMDP belief factorization

Factorizing the belief variable requires three structural assumptions on the π-MOMDP's DBN, which are illustrated by the Rocksample benchmark [START_REF] Smith | Heuristic search value iteration for pomdps[END_REF].

Motivating example. A rover navigating in a N × N grid has to collect scientific samples from interesting ("good") rocks among R ones and then to reach the exit. It is fitted with a noisy long-range sensor that can be used to determine if a rock is "good" or not: -S v consists of all the possible locations of the rover in addition to the exit (#S v = N 2 + 1), -S h consists of all the possible natures of the rocks (S h = S h,1 × . . . × S h,R with ∀1 i R, S h,i = { good, bad }), -A contains the (deterministic) moves in the 4 directions, checking rock i ∀1 i R and sampling the current rock, -O = { o good , o bad } are the possible sensor's answers for the current rock.

The more the rover is close to the checked rock, the better it observes its nature. The rover gets the reward +10 (resp.

-10) for each good (resp. bad) sampled rock, and +10 when it reaches the exit.

In the possibilistic model, the observation function is approximated using a critical distance d > 0 beyond which checking a rock is uninformative:

π ( o ′ i | s ′ i , a, s v ) = 1 ∀o ′ i ∈ O i .
The possibility degree of erroneous observation becomes zero if it stands at the checked rock, and lowest non zero possibility degree otherwise. Finally, as possibilistic semantics does not allow sums of rewards, an additional visible state variable s v,2 ∈ { 1, . . . , R } which counts the number of checked rocks is introduced. Preference µ(s) equals qualitative dislike of sampling

R+2-sv,2 R+2
if all rocks are bad and location is terminal, zero otherwise. The location of the rover is finally denoted by s v,1 ∈ S v,1 and the visible state is then

s v = (s v,1 , s v,2 ) ∈ S v,1 × S v,2 = S v .
Observations { o good , o bad } for the current rock can be equivalently modeled as a cartesian product of observations

{ o good1 , o bad1 } × • • • × { o goodR ,
o badR } for each rock. By using this equivalent modeling, state and observation spaces are both respectively factored as

S v,1 × . . . × S v,m × S h,1 × . . . × S h,l and O = O 1 × . . . × O l ,
and we can now map each observation variable o j ∈ O j to its hidden state variable s h,j ∈ S h,j . It allows us to reason about DBNs in the form of Figure 4, which expresses three important assumptions that will help us factorize the belief state itself: 1. all state variables s v,1 , s v,2 , . . . , s h,1 , s h,2 , . . . are independent post-action variables (no arrow between two state variables at the same time step, e.g. s v,2 and s h,1 ); 2. a hidden variable does not depend on previous other hid-

t t + 1 s v,1 s v,2 . . . s ′ v,1 s ′ v,2 . . . s h,1 s h,2 . . . s ′ h,1 s ′ h,2
. . .

a t a t-1 o 1 o 2 o ′ 1 o ′ 2 Figure 4: DBN of a factored belief-independent π-MOMDP
den variables: the nature of a rock is independent from the previous nature of other rocks (e.g. no arrow from s h,1 to s ′ h,2 ); 3. an observation variable is available for each hidden state variable. It does not depend on other hidden state variables nor current visible ones, but on previous visible state variables and action (e.g. no arrow between s ′ h,1 and o ′ 2 , nor between s ′ v,1 and o ′ 1 ). Each observation variable is indeed only related to the nature of the corresponding rock.

Formalization. To formally demonstrate how the three previous independence assumptions can be used to factorize B π , let us recursively define the history (h t ) t 0 of a π-MOMDP as: h 0 = { β 0 , s v,0 } and for each time step t 1,

h t = { o t , s v,t , a t-1 , h t-1 }.
We first prove in the next theorem that the current belief can be decomposed into marginal beliefs dependent on history h t via the min aggregation:

Theorem 1. If s h,1 , . . . , s h,l are initially independent, then at each time step t > 0 the belief over hidden states can be written as β t = l min j=1 β j,t with ∀s h,j ∈ S h,j , β j,t (s h,j ) = π ( s h,j | h t ) the belief over S h,j . Proof. First s h,1 , . . . , s h,l are initially independent, then

∃ ( β 0,j ) l j=1 such that β 0 (s h ) = l min j=1 β 0,j (s h,j
). The independence between hidden variables conditioned on the history can be shown using the d-separation relationship [START_REF] Pearl | Probabilistic reasoning in intelligent systems: networks of plausible inference[END_REF] used for example in [START_REF] Witwicki | A flexible approach to modeling unpredictable events in mdps[END_REF]. In fact, as shown in Figure 4, given 1 i < j l, s ′ h,i and s ′ h,j are d-separated by the evidence h t+1 recursively represented by the light-gray nodes. Thus π

( s ′ h | h t+1 ) = l min j=1 π s ′ h,j h t+1 i.e. β t (s ′ h ) = l min j=1 β j,t (s ′ h,j
). Note however that it would not be true if the same observation variable o would have concerned two different hidden state variables s h,p and s h,q : as o is part of the history, there would be a convergent (towards o) relationship between s h,p and s h,q and the hidden state variable would have been dependent (because d-connected) conditioned on history. Moreover if hidden state variable s ′ h,p could depend on previous hidden state variable s h,q , then s ′ h,p and s ′ h,q would have been dependent conditioned on history because d-connected through s h,q .

Thanks to the previous theorem, the state space accessible to the agent can now be rewritten as

S v,1 × . . . × S v,m × B π 1 × • • • × B π l with B π j L S h,j . The size of B π j is #L #S h,j -(#L -1) #S h,j . If all state variables are binary, #B π j = 2#L -1 for all 1 i l, so that #S v × B π = 2 m
(2#L -1) l : contrary to probabilistic settings, hidden state variables and visible ones have a similar impact on the solving complexity, i.e. both singly-exponential in the number of state variables. In the general case, by noting κ = max{max 1 i m #S v,i , max 1 j l #S h,j }, there are O(κ m (#L) (κ-1)l ) flattened belief states, which is indeed exponential in the arity of state variables too.

It remains to prove that s v,1 , . . . , s v,m , β 1 , . . . , β l are independent post-action variables. This result is based on Lemma 1, which shows how marginal beliefs are actually updated. For this purpose, we recursively define the history concerning hidden variable s h,j : h j,0 = { β j,0 } and ∀t 0, h j,t+1 = { o j,t+1 , s v,t , a t , h j,t }. We note π o ′ j , s ′ h,j s v , β j , a = max s h,j min π o ′ j s ′ h,j , s v , a ,π s ′ h,j s v , s h,j , a ,β j (s h,j ) : Lemma 1. If the agent is at time t in visible state s v , with a belief over j th hidden state β j,t , executes action a and then gets observation o ′ j , the update of the belief state over S h,j is:

β j,t+1 (s ′ h,j ) =    1 if s ′ h,j ∈ argmax s ′ h,j ∈S h,j π o ′ j , s ′ h,j s v , β j,t , a > 0 π o ′ j , s ′ h,j s v , β j,t , a otherwise.
(3)

Proof. First note that s h,j and { o m,s } s t,m =j ∪ { s v,t } are d-separated by h j,t then s h,j is independent on { o m,s } s t,m =j ∪ { s v,t } conditioned on h j,t : π ( s h,j | h t ) = π ( s h,j | h j,t ). Then, possibilistic Bayes' rule as in Equation 1 yields the intended result.

Finally, Theorem 2 relies on Lemma 1 to ensure independence of all post-action state variables of the belief π-MDP, which allows us to write the possibilistic transition function of the belief-state π-MDP in a factored form:

Theorem 2. ∀β, β ′ ∈ B, ∀s v , s ′ v ∈ S v , ∀a ∈ A, π ( s ′ v , β ′ | s v , β, a ) = min m min i=1 π s ′ v,i s v , β, a , l min j=1 π β ′ j s v , β j , a
Proof. Observation variables are independent given the past (d-separation again). Moreover, we proved in Lemma 1 that updates of each marginal belief can be performed independently on other marginal beliefs, but depends on the corresponding observation only. Thus, we conclude that the marginal belief state variables are independent given the past. Finally as s ′ v and o ′ are independent given the past,

π ( s ′ v , β ′ | s v , β, a ) = max o ′ |β ′ =U (β,a,sv,o ′ ) π ( s ′ v , o ′ | s v , β, a ) = min π ( s ′ v | s v , β, a ) , max o ′ |β ′ =U (β,a,sv,o ′ ) π ( o ′ | s v , β, a ) = min { π ( s ′ v | s v , β, a ) , π ( β ′ | s v , β,

Experimental results

In this section, we compare our approach against probabilistic solvers in order to answer the following question: what is the efficacy/quality tradeoff achieved by reasoning about an approximate model but with an exact efficient algorithm? Despite radically different methods, possibilistic policies and probabilistic ones are both represented as ADDs that are directly comparable and statistically evaluated under identical settings i.e. transition and reward functions defined by the probabilistic model.

We first assessed PPUDD performances on totally observable factored problems since PPUDD is also the first algorithm to solve factored π-MDPs (by inclusion in π-MOMDPs). To this end, we compared PPUDD against SPUDD on the navigation domain used in planning competitions [START_REF] Sanner | Probabilistic track of the 2011 international planning competition[END_REF]. In this domain, a robot navigates in a grid where it must reach some goal location most reliably. It can apply actions going north, east, south, west and stay which all cost 1 except on the goal. When moving, it can suddenly disappear with some probability defined as a Bernoulli distribution. This probabilistic model is approximated by two possibilistic ones where: the preference of reaching the goal is 1; in the first model (M1) the highest probability of each Bernoulli distribution is replaced by 1 (for possibility normalization reasons) and the same value for the lowest probability is kept; for the second model (M2), the probability of disappearing is replaced by 1 and the other one is kept. Figure 5a shows that SPUDD runs out of memory from the 6 th problem, and PPUDD computation's time outperforms SPUDD's one by many orders of magnitude for the two models. Intuitively, this result comes from the fact that PPUDD's ADDs should be smaller because their leaves' values are in the finite scale L rather than R, which is indeed demonstrated in Figure 5b. Performances were evaluated with two relevant criteria: frequency of runs where the policy reaches the goal (see Figure 5c), and average length of execution runs that reach the goal (see Figure 5d), that are both functions of the problem's instance. As expected, M2) is more cautious than model (M1) and gets a better goal-reached frequency (similar to SPUDD's one for the instances it can solve). The later is more optimistic and gets a better average length of execution runs than model (M2) due to its dangerous behavior. For fairness reasons, we also compared ourselves against APRICODD, which is an approximate algorithm for factored MDPs: parameters impacting the approximation are hard to tune (either huge computation times, or zero qualities) and it is largely outperformed by PPUDD in both time and quality whatever the parameters (curves are not shown since uninformative).

Finally, we compared PPUDD on the Rocksample problem (RS) against a recent probabilistic MOMDP planner, APPL [START_REF] Ong | Planning under uncertainty for robotic tasks with mixed observability[END_REF], and a POMDP planner using ADDs, symbolic HSVI [START_REF] Sim | Symbolic heuristic search value iteration for factored pomdps[END_REF]. Both algorithms are approximate and anytime, so we decided to stop them when they reach a precision of 1. Figure 6a, where problem instances increase with grid size and number of rocks, shows that APPL runs out of memory at the 8 th problem instance, symbolic HSVI at the 7 th one, while PPUDD outperforms them by many orders of magnitude.

Instead of precision, computation time of APPL can be fixed at PPUDD's computation time in order to compare their expected total rewards after they consumed the same CPU time. Surprisingly, Figure 6b shows that rewards gathered are higher with PPUDD than with APPL. The reason is that APPL is in fact an approximate probabilistic planner, which shows that our approach consisting in exactly solving an approximate model can outperform algorithms that approximately solve an exact model.

Conclusion

We presented PPUDD, the first algorithm to the best of our knowledge that solves factored possibilistic (MO)MDPs with symbolic calculations. In our opinion, possibilistic models are a good tradeoff between non-deterministic ones, whose uncertainties are not at all quantified yielding a very approximate model, and probabilistic ones, where uncertainties are fully specified. Moreover, π-MOMDPs reason about finite values in a qualitative scale L whereas probabilistic MOMDPs deal with values in R, which implies larger ADDs for symbolic algorithms. Also, the former reduce to finitestate belief π-MDPs contrary to the latter that yield continuous-state belief MDPs of significantly higher complexity. Our experimental results highlight that using an exact algorithm (PPUDD) for an approximate model (π-MDPs) can bring significantly faster computations than reasoning about exact models, while providing better policies than approxi-mate algorithms (APPL) for exact models. In the future, we would like to generalize our possibilistic belief factorization theory to probabilistic settings.

Figure 2 :

 2 Figure 2: DBN of a factored π-MDP

  a ) } which concludes the proof.

  Figure 5: PPUDD vs. SPUDD on the navigation domain

Figure 6 :

 6 Figure 6: PPUDD vs. APPL and symb HSVI (RS) model (M2) is more cautious than model (M1) and gets a better goal-reached frequency (similar to SPUDD's one for the instances it can solve). The later is more optimistic and gets a better average length of execution runs than model (M2) due to its dangerous behavior. For fairness reasons, we also compared ourselves against APRICODD, which is an approximate algorithm for factored MDPs: parameters impacting the approximation are hard to tune (either huge computation times, or zero qualities) and it is largely outperformed by PPUDD in both time and quality whatever the parameters (curves are not shown since uninformative).Finally, we compared PPUDD on the Rocksample problem (RS) against a recent probabilistic MOMDP planner, APPL[START_REF] Ong | Planning under uncertainty for robotic tasks with mixed observability[END_REF], and a POMDP planner using ADDs, symbolic HSVI[START_REF] Sim | Symbolic heuristic search value iteration for factored pomdps[END_REF]). Both algorithms are approximate and anytime, so we decided to stop them when they reach a precision of 1. Figure6a, where problem instances increase with grid size and number of rocks, shows that APPL runs out of memory at the 8 th problem instance, symbolic HSVI at the 7 th one, while PPUDD outperforms them by many orders of magnitude.Instead of precision, computation time of APPL can be fixed at PPUDD's computation time in order to compare their expected total rewards after they consumed the same CPU time. Surprisingly, Figure6bshows that rewards gathered are higher with PPUDD than with APPL. The reason is that APPL is in fact an approximate probabilistic planner, which shows that our approach consisting in exactly solving an approximate model can outperform algorithms that approximately solve an exact model.

  • T π : S × A × S → L is a possibility transition function s.t. T π (s, a, s ′ ) = π ( s ′ | s, a )is the possibility degree of reaching state s ′ when applying action a in state s;• O is a finite set of observations;• Ω π : S × A × O → L is an observation function s.t. Ω π (s ′ , a, o ′ ) = π ( o ′ | s ′ , a )is the possibility degree of observing o ′ when applying action a in state s ′ ; MDPs are π-MOMDPs with S = S v (state is entirely visible to the agent); π-POMDPs are π-MOMDPs with S = S h (state is entirely hidden).

	• µ : S → L is a preference distribution that models quali-tative agent's goals, i.e. µ(s) < µ(s ′ ) means that s is less preferable than s ′ .
	The influence diagram of a π-MOMDP is depicted in Fig-
	ure 1. This framework includes totally and partially observ-
	able problems: π-

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence