Edy Hourany

Benoit Piranda

Abdallah Makhoul

Julien Bourgeois

Bachir Habib

Detector: Hierarchical Distributed Fault Detection Algorithm for Lattice Based Modular Robots

Modular robots are robots built from multiple modules which can reconfigure the shape of the whole robot. This makes them a promising technology to realize highly adaptable and re-configurable robots. One of the main challenges in modular robotics is to detect and heal the system from a state of partial or complete disconnection. Partial disconnection can be achieved by removing the links between the modules. Complete disconnection can be achieved by removing all the connections between two group of modules. It is important for the modular robots to detect a failure between connections since the mobility and the functionality of the robot depend on it. This paper presents a novel approach to detect disconnections in lattice based modular robots. It detects the disconnections using a hierarchical algorithm. The leader of the system constructs a spanning tree, assigns a coordinate to each module and compares it to detect the disconnections. The simulations shows the ability to detect all partial disconnections. Furthermore, the complexity regarding the number of messages sent is linear against the number of modules in the system.

Introduction

The concept of programmable matter was first introduced by Christopher Langton in 1986 [START_REF] Christopher G Langton | Studying artificial life with cellular automata[END_REF]. The term, "Programmable Matter" itself, was first introduced by Tommaso Toffoli and Norman Margolus [START_REF] Toffoli | Programmable matter: Concepts and realization[END_REF] and has also been used in the context of artificial life, where it is referred to as digital organisms or artificial life.

Programmable matter is not a single robot or machine, but rather a network of all of the above [START_REF] Bassil | Linear distributed clustering algorithm for modular robots based programmable matter[END_REF]. It is a fabric that can change its physical properties in real Edy Hourany, Benoit Piranda, Abdallah Makhoul, Julien Bourgeois FEMTO-ST institute, Univ. Bourgogne Franche-Comté, CNRS, 1 cours Leprince-Ringuet, 25200, Montbéliard, France, e-mail: {first}.{last}@femto-st.fr Bachir Habib Holy Spirit University of Kaslik, Jounieh, Lebanon 446 e-mail: bachirhabib@usek.edu.lb 1 time [START_REF] Moussa | Cluster-based distributed self-reconfiguration algorithm for modular robots[END_REF]. Programmable matter can respond to external or internal cues, or can be triggered by the completion of a task. It can grow and adapt, and self-assemble and self-repair [START_REF] Hourany | Self-reconfiguration of modular robots using virtual forces[END_REF][START_REF] Xue | Improving the morphology and control policy of selfreconfiguring modular robots in dynamic environment (student abstract)[END_REF].

Programmable matter consists of a group of micro-robots, called granular computing elements. Each of these robots can move in space, sense the environment and communicate with each other. Each robot can communicate with its connected neighbor to exchange information about its own location and surroundings, and perform the computation in parallel. The robots are small, and can be manufactured in a highly parallel and distributed fashion. The difference between these robots and a traditional micro-robot is that these robots self-organize into a structure that is not readily predictable, and changes in response to a variety of environmental cues [START_REF] Xue | Improving the morphology and control policy of selfreconfiguring modular robots in dynamic environment (student abstract)[END_REF].

The benefit of programmable matter is that its capabilities are not limited to any particular design or configuration. The robots can be configured in a variety of shapes, sizes, and locations [START_REF] Hourany | Self-reconfiguration of modular robots using virtual forces[END_REF][START_REF] Moussa | Cluster-based distributed self-reconfiguration algorithm for modular robots[END_REF][START_REF] Xue | Improving the morphology and control policy of selfreconfiguring modular robots in dynamic environment (student abstract)[END_REF]. The robots can be added, removed or reorganized without having to re-design and re-manufacture the structure. The robots can even be built from other robots, or robots made from other materials. A programmable matter is more than a collection of objects with the ability to move and change shape.

A very frequent error in modular robots is disconnection. It can be caused by incorrect design, lack of care, or a defective module. Disconnections among robots can lead to collisions or a lack of mobility, which will make the robot unable to perform its function. Disconnections can also cause a loss of autonomy or even the robot's death. Therefore, it is crucial to detect disconnection among modular robots to prevent errors in the overall system. This paper proposes a novel hierarchical disconnection detection algorithm based on spanning tree that detects all partial disconnections in a lattice based modular robotic system.

The remainder of this paper is as follow: Section 2 presents the literature review, Section 3 presents the proposed algorithm, Section 4 shows the simulation results, and finally Section 5 concludes the paper.

Background

Modular robots are mobile robots built from multiple units, usually called modules or particles, capable of interactions with each other. These units are connected by links, which are able to transmit forces between the units. Several architecture arises from this technology such as hybrid architecture, chain architecture, and lattice architecture. Some examples of modular robots are shown in Figure 1.

In modular robotics, the mobility of the modules is often not controlled by the computer itself, but the modules communicate among each other and decide among themselves how to move. Simple tasks such as collision detection, passing obstacles and shape formation become more complex with this approach.

Disconnections among modular robots can occur for a number of reasons: (1) a robot may move off-course, (2) a robot may collide with a fixed structure, (3)

(a) (b) (c) (d) (e) (f) (g) (h) (i)
Fig. 1: Examples of modular robots: Figure 1a represents a polybot introduced in [START_REF] Yim | PolyBot: a modular reconfigurable robot[END_REF]; Figure 1b is a Tripod configuration of CONRO [START_REF] Castano | CONRO: Towards deployable robots with inter-robots metamorphic capabilities[END_REF]; Figure 1c is a Five YaMoR modules [START_REF] Moeckel | YaMoR and Bluemove -An Autonomous Modular Robot with Bluetooth Interface for Exploring Adaptive Locomotion[END_REF]; Figure 1d is a lattice modular robot called ATRON [START_REF] Jorgensen | Modular ATRON: modules for a selfreconfigurable robot[END_REF]; Figure 1e is a Rotating M-Block [START_REF] Romanishin | M-blocks: Momentum-driven, magnetic modular robots[END_REF]; Figure 1f is a 2D Crystalline [START_REF] Rus | A physical implementation of the self-reconfiguring crystalline robot[END_REF] modular robots with extensible arms; Figure 1g is a Superbot [START_REF] Salemi | SUPERBOT: A Deployable, Multi-Functional, and Modular Self-Reconfigurable Robotic System[END_REF] modular robot in a humanoid configuration. Figure 1h M-TRAN [START_REF] Kamimura | A Self-Reconfigurable Modular Robot (MTRAN) -Hardware and Motion Generation Software[END_REF] modular robot in 4-legged configuration; Figure 1i is a SMORES [START_REF] Davey | Emulating self-reconfigurable robots -design of the SMORES system[END_REF] modular robot.

two robots may physically touch each other, (4) two robots may physically touch each other and then become disassociated from the system, and/or (5) a robot may disconnect from the system through no fault of its own. While a modular robotic system is being operated, the system must ensure that all communications remains available. In order to achieve this, it is crucial to detect disconnections among the robots of the system. Such disconnections may, for example, result in the loss of valuable data that is being transferred among the robots, or in the loss of robot operation time.

A modular robotic system can be represented as an undirected graph, but traditional graph algorithms, such as Weakly Connected Components [START_REF] Jean E Dunbar | On weakly connected domination in graphs[END_REF], can't be applied due to the system's distributed nature.

In [START_REF] Youssef | Inducing rules about distributed robotic systems for fault detection & diagnosis[END_REF], the authors presented a machine learning based algorithm to detect faults in distributed robotics system. Their work can be summarized as follows: Creation of data-sets of multi-robot system with faults and failures for the purpose of learning faults.

In [START_REF] R Regin | Fault detection in wireless sensor network based on deep learning algorithms[END_REF], Fault detection over a wireless sensor network in a fully distributed manner. First, they proposed the Convex hull algorithm to calculate a set of extreme points with the neighbouring nodes and the duration of the message remains restricted as the number of nodes increases. Then they proposed a Naïve Bayes classifier and convolution neural network (CNN) to improve the convergence performance and find the node faults.

In [START_REF] Ahmad | Distributed fault detection for modular and reconfigurable robots with joint torque sensing: A prediction error based approach[END_REF] A distributed fault detection scheme for modular and reconfigurable robots (MRRs) with joint torque sensing was proposed. With the proposed scheme, the joint torque command is filtered and compared with a filtered torque estimate derived from the nonlinear dynamic model of MRR with joint torque sensing. Common joint actuator faults are considered with fault detection being performed independently for each joint module.

Modular robotics systems have limited memory and processing resources, a decentralized configuration, and a distributed architecture. Therefore, despite their accuracy and effectiveness, the previously described algorithms will not work. This paper will be presenting a novel algorithm that detects disconnections in lattice based modular robots. The algorithm starts by constructing a spanning tree with the leader as root. Then, starting from the leaves, each module will send the list of none existing neighbors to their parents. Each parent will compare the received list with the list of the existing neighbors to detect any disconnections 3 Detector: disconnection detection This section will introduce the proposed algorithm. Lets start by presenting some definitions and terminologies.

Definitions

Definition 1 (Leader). The leader is a module that was elected, using a leader election algorithm, before the execution of the proposed algorithm.

Definition 2 (Connected Modules). Connected modules are latched neighbors that are able to communicate throw their common interface.

Definition 3 (Partial disconnection).

A partial disconnection is a set of nodes that are not connected to each other but are able to communicate through other common nodes on the system. Figures 3a and3b shows an example of partial disconnection.

Definition 4 (Complete disconnection).

A node is referred to be in a state of complete disconnection when it looses connections with all its neighbors. Making it impossible to be identified by the system and will be in a state of complete isolation. Figures 3c and3d shows an example of complete disconnection.

Definition 5 (Lattice architecture). The units of a lattice architecture link their docking interfaces at points into virtual cells of a regular grid. This network of docking sites is analogous to atoms in a crystal, and the grid to the crystal's lattice. As a result, the kinematical characteristics of lattice robots may be defined by their corresponding crystallographic displacement groups (chiral space groups). Typically, just a few units are required to complete a reconfiguration stage. Lattice designs provide a simpler mechanical design as well as a simpler computational representation and reconfiguration planning that can be scaled more readily to complex systems. Definition 6 (Density). The density of a modular robotic system shows how scattered are the modules. The value of the density ranges between 0 and 1. A system is considered to be dense when its density value is close to 1. The coordinates assigned to the modules does not take into consideration the size of the module. Each module is considered to have one unit size. Equation 1shows how to compute the density in a system. N represents the total number of modules. x max , y max , and z max depicts the maximum coordinates in the lattice and x min , y min , and z min depicts the minimum coordinates in the lattice. Density = N (x maxx min + 1) * (y maxy min + 1) * (z maxz min + 1)

(1)

Definition 7 (Potential neighbors).

A potential neighbor is defined as the not connected side of the robot. Two cases are presented, connection failure or absence of modules. Let's take module B in Figure 2 as an example. Module B in this condition has two potential neighbors: The none existing one on the right side and the disconnected one-Module D-.

The Proposed Algorithm

This section will be describing the proposed solution in details. The algorithm is based on three phases.

• Phase 1: Spanning tree creation and coordinate distribution;

• Phase 2: Neighbors' Data Collection;

• Phase 3: Disconnection detection. Below is a detailed explanation of the phases.

D A B C

Fig. 2: Potential Neighbors

Spanning tree creation and coordinate distribution

The leader of the system initiates the algorithm. It will create a spanning tree containing all the modules in the system. The process starts by sending a recruitment message to all its neighbors. Once a module receives a recruit message, it will change the recruited flag to 1, to prevent future recruitment from other modules. Mark the interface that sends the recruit message as parent interface. Extract the coordinates from the received message and update the coordinates based on the received direction in order to generate its own coordinate. And finally, send a recruit message to all its neighbor except for its parent.

Neighbors' Data Collection

The proposed suggestion to find disconnections in a system is to gather information about the neighbours. The process starts with the leaves. Each leaf will generate the coordinates for its potential neighbors, add those coordinates into a vector -that will be called potentialNeighborsVector -and send this vector to its parent alongside their own ID and coordinates. Each parent will also generate the potential neighbors coordinates, check for possible disconnections -explained in Subsection 3.2.3 -then send the results to its parent. The same process will be repeated until the vector reaches the leader. Figure 4 shows an illustrative example of this phase. Represents a partial disconnection. In Figure 3a. modules A and B are disconnected, but they still are part of the whole system since they can maintain their connection to the system through their neighbors C and D. Figures 3c and3d are in a state of complete disconnection. In Figure 3c, module A is disconnected from module B and module A is not connected to any other module. module A is considered to be in complete disconnection from the system since there is no other way for the system to acknowledge its presence. Same case for Figure 3d.

Disconnection detection

Once a node receives from all its children the vector potentialNeighborsVector, it will compare with the list of coordinates of existing modules. If the node finds potential neighbors coordinates matching with existing modules, then there is a disconnection. Since each node have access to only its children, then the final decision of disconnection is actually at the leader's level.

Simulation Results

The proposed algorithm was implemented and evaluated using VisibleSim [START_REF] Thalamy | Behavioral simulations of lattice modular robots with visiblesim[END_REF] a modular robots simulator. To study the performance of the proposed algorithm, the metrics that were taken into account in the simulations are the number of messages

(2,-1)

Fig. 4: Data collection in a dense system: Module 6 will add to the potentialNeigh-borsVector the following coordinates: (2, 2) and (3, 1), Module 8 will add (3, 0) and Module 9 will add (3, -1) and (2, -2). They will then send this vector to their respective parents 5, 4, and 7. Module 5 will add (1, 2), Module 7 will add (1, -2), and Module 4 will not add anything since all its interfaces are connected. So on until this vector reaches the leader. and the percentage of error detected (number of errors detected by our algorithm on the total number of errors in the system). Multiple simulations where done while varying different components at a time.

The first bash of simulations was for the same number of modules -In those simulations, the number of modules was 1000 -with different densities ranging from 0.18 to 1. All the shapes' configuration were randomly generated -For the exception of the cube since it is the only shape where the density is to its maximum-.

Figure 5 shows that when the density is increasing, the number of messages sent is also increasing. This is due to the fact that when the density is high, the modules are closer to each other, leading to an increased amount of neighbors per module wish will lead to a higher number of messages sent. Further more, Figure 5 shows that whenever the percentage of errors in a system is higher, the number of messages sent is lower. The reason behind this is that when modules are disconnected they can not send messages which will decrease the total number of messages sent.

The second bash of simulations were done for the same density while increasing the number of modules. The chosen density for this simulation was 1, for the reason that it was the value where the system was sending messages the most. Figure 6a shows how the number of messages is increasing linearly with the number of Fig. 5: This figure shows, on a logarithmic scale, how the number of messages sent in a 1000 3D system is changing with the density of the system. Each color represents the percentage of errors that existed in the system during the simulations. It is noticeable that the number of messages is increasing with the density. Furthermore, the number of messages decreases when the percentage of errors is increasing modules. This shows that the complexity of the proposed algorithm, regarding the number of messages sent, is linear. It is also noticeable that when the number of errors is increasing in the system, the number of messages in decreasing. This is due to the fact that some messages are not able to be sent or delivered due to the errors encountered in the system.

During the previous simulations, the simulator collected the total number of errors detected by the proposed algorithm. Figure 6b shows the percentage of errors detected on the Y axes ranging from 90 to 100 against the density, on logarithmic scale, from -2 to -0.4. Five colors are shown on the graph. Each color represents the percentage of errors in the system. Figure 6b shows that for high densities, more errors are detected. A system with low density has less connected modules. Any occurring error might lead to a complete disconnection that is not detected by the proposed algorithm. Therefore, the higher the density the better the detection of errors is.

Conclusion

This paper presented Detector, a novel distributed algorithm for a hierarchical fault detection in modular robots. The proposed algorithm is able to detect partial disconnections in a modular robotic system. To achieve such task, the algorithm creates a spanning tree having the leader as root. Each module generates its coordinates starting from the leader as origin. Then, each module -starting from the leaves -will send the potential coordinates of none connected interfaces to its parent. The parent will also generates the potential neighbors' coordinates and add them to the received list, compare the list of potential neighbors' coordinates with the list of the actual coordinates. Any matching coordinates means a disconnection is found. Then, the parent, sends the remaining results to its parent, so on until it reaches the leader who will have the final decision regarding the existence of disconnections if any.

The simulation results show an elevated rate of disconnection detection specially with a high density system. The accuracy of finding disconnections was ranging from 90% to 100%. Furthermore, the simulations also showed that the complexity of the algorithm regarding the number of exchanged messages remains linear.

Future work should consider the ability to detect if any disconnection happened during the construction of the spanning tree, keep the spanning tree updated during the movement of the robots and also the ability to detect the complete disconnections in a modular robotic system. For example, the addition of different method of communications such a wireless communication can help detect a complete disconnection that leads to an isolation of some modules from the whole system.

Fig. 3 :

 3 Fig. 3: Different examples of Partial and complete disconnections: Figures3a and 3bRepresents a partial disconnection. In Figure3a. modules A and B are disconnected, but they still are part of the whole system since they can maintain their connection to the system through their neighbors C and D. Figures3c and 3dare in a state of complete disconnection. In Figure3c, module A is disconnected from module B and module A is not connected to any other module. module A is considered to be in complete disconnection from the system since there is no other way for the system to acknowledge its presence. Same case for Figure3d.

  (a) This figure shows, on a logarithmic scale, the number of messages sent in the system according to the number of modules in a logarithmic scale. (b) Percentage of errors detected.

Fig. 6 : 2

 62 Fig. 6: 2 Figures side by side

5

 5

Acknowledgements The authors would like to acknowledge the National Council for Scientific Research of Lebanon (CNRS-L) and the Holy Spirit University of Kaslik for granting a doctoral fellowship to Edy Hourany.

This work was partially supported by the ANR (ANR-16-CE33-0022-02), the French Investissements d'Avenir program, the ISITE-BFC project (ANR-15-IDEX-03) and the EIPHI Graduate School (contract "ANR-17-EURE-0002").


Virginie Van Wassenhove
email: virginie.van.wassenhove@gmail.com

Temporal disorientations and distortions during isolation

Keywords: temporal cognition, time perception, human, duration, tapping, rhythm, synchronization Highlights

Understanding how the brain maps time is central to neuroscience, behavior, psychology, and cognition. Just as in spatial navigation, self-positioning in a temporal cognitive map depends on numerous factors that are both exogenous and endogenous (e.g. time of day and experienced durations, respectively). The deprivation of external temporal landmarks can greatly reduce the ability of participants to orient in time and to formulate an adequate endogenous representation of time. However, this area of investigation in humans shows a great paucity of empirical data. This article aims at unearthing some of the experimental work that has systematically explored how humans' awareness of time is affected by varying degrees of isolation protocols. The assessment of the literature on the impact of isolation (broadly construed) on human temporalities may contribute to contextualizing the temporal distortions and disorientations reported during the ongoing worldwide pandemic Covid-19.

 Temporal cognition is central to neuroscience and cognitive science  Isolation is accompanied by systematic temporal disorientations and distortions  Factors selectively affecting temporal cognition in isolation are unknown  Individuals' endogenous biological and behavioral rhythms emerge in isolation  Timing in the absence of external clocks should be carefully investigated Psychological time, taken as the set of internal inferences the brain uses to represent the temporal relations (duration, order, sequence, past, future …) between events (Friedman, 1993, p. 199;[START_REF] Michon | Implicit and explicit representations of time[END_REF], is flexible and adaptive: humans and animals use temporal cognitive maps [START_REF] Gallistel | The organization of learning[END_REF] to anticipate their future [START_REF] Raby | Planning for the future by western scrub-jays[END_REF] and to adapt their behaviors.

The ability to orient oneself in time has long been recognized as a central feature of psychology [START_REF] Cottle | The location of experience: A manifest time orientation[END_REF]) and perspectival [START_REF] Zimbardo | The Stanford time perspective inventory[END_REF]. Experiencing temporal disorientations can be synonymous with future psychological trauma [START_REF] Holman | When time falls apart: The public health implications of distorted time perception in the age of COVID-19[END_REF] and changes in one's temporal phenomenology can indicate emotional distress [START_REF] Droit-Volet | Time and Covid-19 stress in the lockdown situation: Time free,«Dying» of boredom and sadness[END_REF][START_REF] Grondin | Pandemic, Quarantine, and Psychological Time[END_REF][START_REF] Yamada | COVIDiSTRESS Global Survey dataset on psychological and behavioural consequences of the COVID-19 outbreak[END_REF], being in a socially deconstructed state [START_REF] Twenge | Social exclusion and the deconstructed state: Time perception, meaninglessness, lethargy, lack of emotion, and self-awareness[END_REF] and even psychiatric disorders [START_REF] Mengin | Psychopathological consequences of confinement[END_REF]. Clinically, temporal disorientation is an indicator of future cognitive impairments and dementia that implicate memory systems [START_REF] Arzy | Mental time in amnesia: Evidence from bilateral medial temporal damage before and after recovery[END_REF][START_REF] Dumurgier | Time Orientation and 10 Years Risk of Dementia in Elderly Adults: The Three-City Study[END_REF].

The disorientation experienced by patients with Alzheimer's disease [START_REF] Dafni-Merom | A unified brain system of orientation and its disruption in Alzheimer's disease[END_REF] dramatically impact their personal narratives, and patients with lesions in hippocampal structures show diverse temporal impairments [START_REF] Macdonald | Prospective and retrospective duration memory in the hippocampus: Is time in the foreground or background?[END_REF] such as duration distortions [START_REF] Richards | Time reproductions by HM[END_REF]) and difficulty to perform mental time travel [START_REF] Tulving | Elements of episodic memory[END_REF]. H.M., a patient with bilateral hippocampal damage reproduced durations quite accurately up to about 20 seconds of clock time yet estimated 5 minutes of clock time to be equivalent to 40 s [START_REF] Richards | Time reproductions by HM[END_REF]. Clive Wearing, following massive hippocampal damages extending to his temporal and frontal lobes, lived his life in a perpetual present [START_REF] Wilson | Prisoner of consciousness: A state of just awakening following herpes simplex encephalitis[END_REF] lasting a few seconds (7 to 30 seconds). His personal notebook shows that his life reads as a series of non-causal snapshots, preventing him to weave a coherent narrative of his conscious life.

A conscious "present" seems to span a few seconds of clock time but it is impervious to the healthy mind bathed in a continuous stream of endogenous thoughts and exogenous stimulations. Mind wandering too is a form of engagement into temporary disorientation, which engages the default-mode network of the brain and has recently been associated with an individual's degree of perceived loneliness and social isolation [START_REF] Spreng | The default network of the human brain is associated with perceived social isolation[END_REF]. Yet, temporal disorientation can also be sought after when one deliberately immerses into the narrative of a great novel, at a concert, or even immersing in augmentedto-virtual realities [START_REF] Wood | Experiences of time loss among videogame players: An empirical study[END_REF]. What do we know about the effects of isolation on temporal cognition?

In the following, I illustrate how studying the effects of isolation provided insights on how endogenous biological properties eventually shape both temporal perception (the measure of the temporal statistics of events) and cognition (rules and representations used by the brain to compute temporal relations). Human studies focusing on time in isolation have mostly investigated the physiological components of time perception leaving vastly unknown how the construction of temporal cognitive maps may be affected. A short allusion is included, relating changes in time perception and temporal cognition during the lockdown episodes associated with Covid-19.

A biological fabric for time

Temporal cognition does not arise through exogenous causes; rather, it is deeply rooted in one's biological endowment and in the endogenous structuring principles that ultimately form our awareness of self in an ever-changing environment. The neurobiological foundations of temporal cognitive maps making up our phenomenology of time remains largely unknown, yet it would be unsurprising that brain rhythms and biological clocks contribute to the shaping of temporal cognition [START_REF] Buzsáki | Rhythms of the brain[END_REF][START_REF] Gallistel | The organization of learning[END_REF][START_REF] Jones | Time, our lost dimension: Toward a new theory of perception, attention, and memory[END_REF][START_REF] Pöppel | Oscillations as possible basis for time perception[END_REF][START_REF] Pöppel | Oscillations as possible basis for time perception[END_REF][START_REF] Van Wassenhove | Temporal cognition and neural oscillations[END_REF][START_REF] Varela | Present-time consciousness[END_REF]. Over a large spectrum of scales, biological clocks regulate genes, synchronize individuals to their environment and peers, and endow individuals with the ability for timing. Endogenous dynamics are, after all, constitutive of living systems. Attributing endogenous causes to timing is not as intuitive and accepted as it may first appear. Cognitive neuroscience remains heavily influenced by the idea that behaviors result from external causes and stimulations despite massive controversies at the very origin of cognitive sciences. The explanatory power for "thinking matter" in current brain theories do not readily accommodate how mental representations can be generated in the absence of external stimuli [START_REF] Barack | Two views on the cognitive brain[END_REF][START_REF] Krakauer | Neuroscience needs behavior: Correcting a reductionist bias[END_REF]. The need to take the perspective of the brain from within, not the perspective of the world from outside, has been vehemently defended by Buzsáki [START_REF] Buzsaki | The Brain from Inside Out[END_REF]. In this context, understanding time in the brain to understand the mind is quite simply primordial [START_REF] Buonomano | Your brain is a time machine: The neuroscience and physics of time[END_REF]: "[…] the field of neuroscience will have to further mature and embrace the fact that it will not be possible to understand the human mind without describing how the brain tells,

represents, and conceptualizes time. […]"

In the mid-nineteenth century, Aschoff and colleagues [START_REF] Aschoff | Circadian rhythms in man[END_REF] demonstrated that the causes of chronobiology and rhythmic activity in animals (humans included) were endogenous.

Biological clocks govern the periodicities of physiological phenomena, independently of external timing cues. The replicable evidence for this assertion is that in the absence of external timing cues (e.g. day/night cycles) individuals in many species show undamped self-sustained changes in their physiology and behaviors: the core body temperature will continue its periodic changes, and so will periods of wakefulness and sleepiness. In the absence of external timing cues (or Zeitgebers) that synchronize the animals' biological clocks with the external environmental clocks, the animals' physiology will pursue its dynamic variations in free-running mode: biological clocks, including neuronal ones [START_REF] Webb | Intrinsic, nondeterministic circadian rhythm generation in identified mammalian neurons[END_REF], maintain their inherent periodicities and thus naturally run out of phase with the clocks they cannot entrain to. In full darkness, and in the absence of diel cues, intrinsic rhythms maintain their course but will display distinct, endogenously defined periodicities, and readily de-phase with respect to other clocks [START_REF] Aschoff | Desynchronization of human circadian rhythms[END_REF]. These observations are also demonstrated to be species-specific [START_REF] Hazlerigg | Activity patterns in mammals: Circadian dominance challenged[END_REF]. Additionally, Zeitgebers are not solely defined by universal time constants: they are also driven by social interactions in many species [START_REF] Aschoff | Human circadian rhythms in continuous darkness: Entrainment by social cues[END_REF][START_REF] Bloch | The Social Clock of the Honeybee[END_REF][START_REF] Eban-Rothschild | Social influences on circadian rhythms and sleep in insects[END_REF], thereby higher-order complexity regulates the individual's rhythms, a seed for collective behaviors from insects to humans.

Early chronobiology work reporting time distortions during full isolation

Pioneering studies interested in factors affecting chronobiology were conducted in the 1960's, at a time when physiological factors such as body temperature and arousal were deemed primitives of time estimation. In the developing field of chronobiology, questions regarding the emergence of circadian rhythms motivated the studies of animals and humans under ecological and social conditions that largely differed from their ecological settings. Experiments with human volunteers under free-running schedule (or in "timelessness") isolated individuals from any Zeitgebers in caves or in bunkers. Sometimes, experiments focused on the possible link between biological clocks that regulate the physiology of the body, timing behaviors (such as spontaneous tempo or reaction times) and time perception itself (estimation of a lapse of time). [START_REF] Vernon | Time estimations during sensory deprivation[END_REF] conducted two isolation experiments in which they held participants in a dark room from 8 to 96 hours. In the first experiment, a group of participants was asked what day and what time it was before they were released. On average, participants underestimated their confinement time. The authors listed the temporal cues that participants used for their estimation, and a majority of them were food related (eating, hunger) and beard growth (males).

In the second experiment, all participants were confined for 96 hours, and they were asked to individually report when one hour had passed. Unfortunately, the report provides data as cumulative time errors without correcting for the fact that participants' changes in sleep patterns (likely misestimated by participants) also contributed to mis-estimations of elapsed time (see [START_REF] Aschoff | Estimates on the duration of sleep and wakefulness made in isolation[END_REF] and below). Such confounds are detrimental for a clear interpretation of the link between chronobiology and time perception.

Around the same time, Michel Siffre, a French speleologist, pioneered the scientific investigation of the effect of confinement in total isolation: in 1962, he isolated himself 58 days, 70 meters underground in the Scaraffon glacier (Italy). In 1972, he repeated this experiment for 205 days (nearly 7 months!) in Deal Rio (Texas, USA). His physiological (ECG, urine), neurophysiological (electroencephalography (EEG)) and behavioral changes were assessed by the NASA. In the total absence of Zeitgebers, Siffre's biological rhythms adjusted to a circabidian or 48 hours cycle instead of a circadian one. These results controversially suggested the existence of individual endogenous rhythms that may differ from the typical circadian ones.

In 1966, Siffre placed a young man for 174 days in a cave [START_REF] Fraisse | Temporal isolation, activity rhythms, and time estimation[END_REF] and tested his spontaneous tempo and reaction times [START_REF] Oléron | Les variations circadiennes du temps de réaction et du tempo spontané au cours d'une expérience «hors du temps[END_REF]. The recordings showed two main effects of isolation on the temporal production measurements: First, during the entire isolation period, the individual's spontaneous tempo accelerated over time whereas his reaction times decelerated over time.

The authors interpreted these effects as demonstrating a decrease of vigilance over time akin to a "release from inhibition". The second major observation was that the two measurements showed intracircadian fluctuations: specifically, during the subjective mid-day, the spontaneous tempo was slowest and the reaction times fastest, whereas at wake time and before sleep time, the spontaneous tempo was fastest and reaction times slowest.

Following these original scientific expeditions, Chouvet and colleagues [START_REF] Chouvet | Periodicite bicircadienne du cycle veille-sommeil dans des conditions hors du temps. Etude polygraphique[END_REF] tested three more participants in similar cave conditions for 6 months: two were tested according to a free-running schedule, and one was tested using a relative 48 hours controlled schedule. One major question was whether a spontaneous 48 hours cycle would develop (and maintain) in the absence of Zeitgebers. The authors reported a circabidian rhythm, and with it, a lack of proportionality between wake and sleep times. The authors noted that their results differed from the work of Aschoff and colleagues [START_REF] Aschoff | Desynchronization of human circadian rhythms[END_REF], which argued for the preservation of the circadian rhythm in the absence of external cues although a lengthening of the cycles can be seen on the reported graphs [START_REF] Aschoff | Desynchronization of human circadian rhythms[END_REF]. Chouvet and colleagues [START_REF] Chouvet | Periodicite bicircadienne du cycle veille-sommeil dans des conditions hors du temps. Etude polygraphique[END_REF] suggested that a major factor may be the temperature during isolation, as core body temperature holds a long albeit partial explanatory function in time estimation research. [START_REF] François | Contribution à l'étude du sens du Temps. La température interne comme facteur de variation de l'appréciation subjective des durées[END_REF] reported that diurnal changes in body temperature were accompanied by changes of time perception. Following this work, Hoagland constructed the chemical clock hypothesis according to which the body temperature would predict the passage of time felt by individuals. Famously testing his own feverish wife on her perception of time passing, Hoagland replicated the original observation of François in that the higher his wife's bodily temperature was, the faster her counting of time was [START_REF] Wearden | Origins and development of internal clock theories of time[END_REF]: one minute of clock time was about 2 minutes of his wife's perceived time. According to the chemical clock hypothesis, an increased arousal and body temperature would result in an increased cellular metabolic rate, which would speed up the internal clock. Subsequent experiments replicated the effect of body temperature on time perception [START_REF] Fox | Time judgment and body temperature[END_REF][START_REF] Kuriyama | Circadian fluctuation of time perception in healthy human subjects[END_REF][START_REF] Kuriyama | Diurnal fluctuation of time perception under 30-h sustained wakefulness[END_REF][START_REF] Pande | Short-duration judgment in young Indian subjects under 30 h constant wakefulness[END_REF][START_REF] Pexirra | Manipulation of striatal population dynamics using temperature warps judgment of time[END_REF][START_REF] Van Maanen | Core body temperature speeds up temporal processing and choice behavior under deadlines[END_REF] but the reported relation between body temperature and time perception did not follow the Arrhenius equation strongly suggesting that a direct thermodynamics account of time perception was unsupported. Additionally, large inter-individual differences were observed despite comparable body temperatures and the effect of temperature affected only fast time scales, not the longer time scales at which orientation to time evolves [START_REF] Aschoff | Human perception of short and long time intervals: Its correlation with body temperature and the duration of wake time[END_REF].

Body temperature

More recent work showed that the performance of individuals tested on three tasks (motor tapping, duration reproduction and duration discrimination) within a day was stable despite endogenous fluctuations in body temperature [START_REF] Mioni | Relationship between daily fluctuations of body temperature and the processing of sub-second intervals[END_REF]. Hence, while core body temperature appears to affect time perception, the exact nature of this relation remains uncertain and could be parsimoniously accounted for by domain-general modulations of cognitive functions (e.g. decision-making [START_REF] Monteiro | Using temperature to analyse the neural basis of a latent temporal decision[END_REF]) affected by homeostatic instabilities.

Temporal disorientations in isolation studies

Independently of the chronobiology research program, the first empirical study of temporal disorientation was realized by [START_REF] Macleod | An experiment in temporal disorientation[END_REF] who gravitated away from the folk psychology notion of "time sense". Instead, they wished to assess the problem as follows:

"Rather than postulate a mysterious "time sense" the experimental scientist has chosen to assume that orientation in time is a mediate process, resting upon inferences (possibly unconscious in character) from non-temporal sense-data." To test their working hypothesis, they isolated two individuals, one for 48 hours, the other for 86 hours in a soundproof booth and on a free-running schedule. One participant was asked to indicate every time 30 minutes or 1 hour had passed; the other participant was prompted at irregular intervals to provide his time estimation. No other time cues were accessible to the participants. The report provides insights on the participants' experienced awareness of temporal distortions, which interestingly echoed Siffre's own personal diary. For instance, "11:30 a.m. -I am just as much at a loss about the time as I ever was. When I got up I hardly knew what time to report, but when I considered the matter I concluded that ordinarily after a good night's sleep like that I would be likely to wake up first at 7:00 a.m., and then if I turned over and slept far quite a while I probably would wake up again about 8:30. Since that hour would do as well as any other I reported it to you."

There are several observations, which are quite remarkable in these early reports. The first is that there was a general trend towards the underestimation of elapsed time, consistent with the subsequent bulk of studies on time in isolation. The second observation was that the participant irregularly prompted to report elapsed time showed no major disturbances of time estimation compared with the participant who self-initiated his time estimates. A third observation was that general orientation to time was a more reliable measure than duration estimation. According to the reported data, the pattern of results obtained by the participants regularly providing their duration estimates seemed consistent with the later reports of Thor & Crawford [START_REF] Crawford | Circadian activity and noise comparisons of two confined groups with and without reference to clock time[END_REF][START_REF] Schwartz | An Investigation of the Effects of Isolation on Time Perception and Its Physiological Correlates[END_REF] in that morning durations tended to be underestimated. Morning estimations were also consistent with the positive temporal errors reported in MacLeod and Roff [START_REF] Macleod | An experiment in temporal disorientation[END_REF], which indicated that the individual tended to think that it was later than the actual clock time in the morning hours. To the contrary, in the evening, durations were overestimated [START_REF] Crawford | Circadian activity and noise comparisons of two confined groups with and without reference to clock time[END_REF][START_REF] Schwartz | An Investigation of the Effects of Isolation on Time Perception and Its Physiological Correlates[END_REF] and individuals in [START_REF] Macleod | An experiment in temporal disorientation[END_REF] reported that it was earlier than the actual clock time.

The study of Thor & Crawford [START_REF] Crawford | Circadian activity and noise comparisons of two confined groups with and without reference to clock time[END_REF]) confined a group of 30 adults and children in a simulated fallout shelter for 304.6 hours. Participants had no beds, no bathing water, no coffee and no change clothing. They were provided with a restrictive 912 calories a day and drinking water. The light was turned on when more than half of the group awakened, and turned off when the group retired for the night. They reported that morning hours tended to be estimated as being earlier than they actually were, and that evening hours tended to be estimated later than they actually were.

However, a major confounding factor in this experiment was that participants' time estimations were regularly checked twice a day at 9 am and 9 pm (+/-1 hour), effectively pacing the experimental design over the twelve days period and providing participants with regular (even if implicit) Zeitgebers. A similar observation was found in a more recent case study [START_REF] Bonmati-Carrion | Living Without Temporal Cues: A Case Study[END_REF], in which a participant isolated in a bunker for 10 days was prompted to report what time of day it was in the course of the study. The authors reported a systematic delay in the participant's reported clock time as compared to actual clock time: the difference was most pronounced during a constant dim light protocol (up to 5 hours of differences) and least pronounced under a circadian schedule with early wake time (less than 1 hour). The difference between clock time and estimated time was also more pronounced late in the circadian days as compared to early mornings. The authors suggested that this time estimation pattern was dependent on the midpoint sleep duration, which is a marker of individuals' chronotype i.e. endogenous circadian clock properties [START_REF] Roenneberg | What is chronotype?[END_REF][START_REF] Roenneberg | Life between clocks: Daily temporal patterns of human chronotypes[END_REF].

Observations converge on the interpretation that in free-running schedule, and in the absence of Zeitgebers, an intradiurnal effect of duration estimation and passage of time can be found during isolation so that time in the morning may be felt to pass faster than in the evening. Yet, while more recent work imposing a free-running schedule in isolation [START_REF] Pöppel | Diurnal variation of time perception[END_REF] or a 30 hours schedule [START_REF] Kuriyama | Circadian fluctuation of time perception in healthy human subjects[END_REF][START_REF] Kuriyama | Diurnal fluctuation of time perception under 30-h sustained wakefulness[END_REF][START_REF] Pande | Short-duration judgment in young Indian subjects under 30 h constant wakefulness[END_REF] confirmed diurnal variations in participants' duration estimations, the pattern of temporal productions do not fully fit a unitary description of time distortions. In these studies, temporal reproductions in the circadian mornings were longer than temporal reproductions in the circadian afternoons and evenings, observing linear [START_REF] Kuriyama | Circadian fluctuation of time perception in healthy human subjects[END_REF][START_REF] Kuriyama | Diurnal fluctuation of time perception under 30-h sustained wakefulness[END_REF] or non-linear patterns [START_REF] Pande | Short-duration judgment in young Indian subjects under 30 h constant wakefulness[END_REF][START_REF] Pöppel | Diurnal variation of time perception[END_REF].

In a series of experiments dedicated to the study of diurnal variations of time perception [START_REF] Pöppel | Diurnal variation of time perception[END_REF], Pöppel & Giedke trained participants outside a bunker to produce a 10 seconds interval through motor action. The training of participants stopped after a set criterion and participants were subsequently tested during a free-running isolation protocol that lasted several weeks. Among the different tasks, one asked participants to produce the learned 10s interval about 6 to 8 times a day. As a side observation [START_REF] Pöppel | Oscillations as possible basis for time perception[END_REF], the authors reported that each participant slowly drifted away from the set point while in the bunker and in the total absence of Zeitgebers. Most importantly, each individual displayed a different drift so that while two participants produced durations much longer than 10 seconds, the others produced shorter estimates. This observation strongly favored the hypothesis of a coordinate system for time that is individually defined [START_REF] Gallistel | The organization of learning[END_REF][START_REF] Pöppel | Oscillations as possible basis for time perception[END_REF], echoing early observations in chronobiology and crucially emphasizing the need to take an individual perspective to timing.

Early on, Macleod and Roff [START_REF] Macleod | An experiment in temporal disorientation[END_REF] formulated very modern theoretical parallels between one's orientation in space and time, and discussed how duration estimation may be a subordinate function of a temporal orientation system. This point is particularly relevant with respect to current considerations on how the brain may map time building on the computational machinery and neural systems dedicated to mapping space [START_REF] Buzsáki | Memory, navigation and theta rhythm in the hippocampalentorhinal system[END_REF][START_REF] Gallistel | The organization of learning[END_REF][START_REF] Issa | Navigating through time: A spatial navigation perspective on how the brain may encode time[END_REF][START_REF] Macdonald | Prospective and retrospective duration memory in the hippocampus: Is time in the foreground or background?[END_REF]. The authors otherwise legitimately and critically assessed the major limitations of their initial work with the nascent discussions, at their times, on the physiological bases of an internal clock and the developing field of chronobiology.

Siffre [START_REF] Siffre | Hors du temps: L'expérience du 16 juillet 1962 au fond du gouffre de Scarasson par celui qui l'a vécue[END_REF] too had largely underestimated the time he spent isolated underground. He underestimated the 58 days isolated on a free-running schedule and thought he had spent 33 days as if 25 days had gone unregistered. However, the major reason accounting for this gross underestimation was that his sleep-wake cycle elongated to a 48 hours rhythm. In a subsequent experiment testing Mairetet, who was aware of such phenomenon, the researchers agreed to dissociate night sleep from nap sleep, and asked Mairetet to count "sleep-wakefulness cycles" as opposed to days. Due to the development of a circabidian rhythm and the lengthening of his naps, which Mairetet himself did not seem to be aware of, the count also resulted in a gross underestimation of his stay underground: 86 days when he effectively spent 174 days in isolation. Fraisse [START_REF] Fraisse | Temporal isolation, activity rhythms, and time estimation[END_REF] further described the duration estimates that were provided by Mairetet for hours and minutes long durations. For the hours-long durations, Mairetet estimated the time elapsing between temporal landmarks such as waking time and lunch time, or between nap time and diner: there again, they reported a nearly 50% underestimation of clock durations. The puzzled experimenters reasoned that Mairetet provided duration estimates based on his typical routines outside the cave as opposed to keeping track of time per se. In other words, reports may have been made inferential.

For the estimation of shorter durations, three types of tests were used: a verbal estimation of elapsed time between two auditory clicks played over the phone, a temporal reproduction of that same click-to-click duration by pressing on a button for the same amount of time, and a temporal production task in which Mairetet was provided with a verbal duration, which he had to produce by pressing on a button. Fraisse [START_REF] Fraisse | Temporal isolation, activity rhythms, and time estimation[END_REF] reports the ratio of the verbal or motor production over the provided clock time: while the estimation task revealed a nearly perfect score, the production and reproduction tasks systematically lengthened in the course of isolation going from a roughly good performance to a 2.5 fold overestimation. Fraisse [START_REF] Fraisse | Temporal isolation, activity rhythms, and time estimation[END_REF] does not provide a clear interpretation of these results, beyond concluding that Mairetet did experience temporal distortions that cannot be accounted for by mere learning, vigilance or arousal effects. In agreement with these, a series of experiments concluded that neither the sleep-wake cycle, nor the circadian rhythms of body temperature can fully account for the changes observed in time estimations tested in bunkers in full or partial isolations and in total darkness [START_REF] Pöppel | Diurnal variation of time perception[END_REF].

Time perception vs. cognition?

Isolation in controlled laboratory conditions and over short periods of time have been performed by modulating the severity of a participant's sensory deprivation. Sensory deprivation differs from bodily inactivity in that the arousal system, under an increased degree of isolation (as controlled by the amount of delivered stimulation) increases participants' stress and arousal [START_REF] Leiderman | Imagery and sensory deprivation, an experimental study[END_REF][START_REF] Zuckerman | Stress response in total and partial perceptual isolation[END_REF]. Schwartz [START_REF] Schwartz | An Investigation of the Effects of Isolation on Time Perception and Its Physiological Correlates[END_REF] used the "Iron maiden", a water-immersion g-capsule, to deprive participants sensorily for up to 3 hours. While recorded physiological parameters such as heart-rate and skin temperatures showed visible changes in his experiments, no robust changes in time estimations were found as a function of sensory deprivation. The author concluded that short experimental isolations were insufficient to affect timing in a way that is effective in full isolation in caves or bunkers. Still, in total isolation and in sensory deprivation studies, a great majority of participants systematically report experiencing "temporal disorientations". This phenomenon is not solely attributable to perceptual distortions of elapsed time but possibly fed by cognitive distortions of time perspective.

The setting up of temporal orientation requires that an individual be aware of distinct temporalities (in Westerners referred to as past, present, and future) and of their associated chronology (ordinal sequencing of past to present to future). Time perspective builds on the notion that time is personal and subjective [START_REF] Kastenbaum | On the meaning of time in later life[END_REF] and modern psychology embraced the notion of an individual's belief system about his past, present, and future and their interrelations [START_REF] Rokeach | The open and closed mind: Investigations into the nature of belief systems and personality systems[END_REF].

In its initial inception, an individual could display a narrow focus on past, present or future independently of their interconnections and alternatively, the interconnections may prevail to the detriment of one's temporal positioning. Given the importance of assessing future perspectival, Lewin [START_REF] Lewin | Intention, will and need[END_REF] coined the term "time perspective" as "the totality of the individual's views of his psychological future and his psychological past existing at a given time".

Interestingly, it is also at the same historical period that the notion of (temporal) cognitive map was put forward [START_REF] Tolman | Psychology versus immediate experience[END_REF][START_REF] Tolman | Cognitive maps in rats and men[END_REF]. Indeed, the ability to map time is central to daily decisionmaking and future planning while being subjected to various cognitive biases [START_REF] Sanna | Integrating temporal biases: The interplay of focal thoughts and accessibility experiences[END_REF] such as the planning fallacy or the tendency to underestimate the time necessary to finish a task [START_REF] Kahneman | Intuitive prediction: Biases and corrective procedures[END_REF]. In extreme cases of confinement, inmates' emotional states are influenced by their future temporal horizon: men with an indefinite time sentence overall suffer more than those with timed sentences yet inmates with two years sentences suffered more than those with sentences longer than 5 years [START_REF] Farber | Suffering and time perspective of the prisoner[END_REF]. In short, one's lived past and experienced present shape one's well-being, but so do the ability to build future possibilities.

Lockdowns, isolation and the covid pandemic

In recent years, the spread of Covid-19 have forced exceptional worldwide sanitary measures to limit the spread of viral infection: lockdowns became the rule for weeks at a time. Physical and social distancing imposed new rhythms to the world population. As the length and severity of the pandemic could not be anticipated, citizens were also unprepared for the future months to come. Many reported feeling disorientated in time with days seemingly melting into one another, a phenomenon popularly referred to as "blursday". These phenomenological reports converge with some of the empirical work reviewed above that report temporal disorientations in different kinds of isolation protocols in humans. However, and as summarized above, our current knowledge on the effects of isolation on human psychology and (neuro)physiology is quite scarce and largely insufficient to provide clear-cut causal explanations for the temporal distortions reported in the kind of partial isolation we lived through in these historical times.

The precise understanding of factors affecting individuals' awareness of time has been ongoing in concerted international efforts [START_REF] Chaumon | The Blursday Database: Individuals' Temporalities in Covid Times[END_REF][START_REF] Cravo | Time experience in social isolation: A longitudinal study during the first months of COVID-19 pandemic in Brazil[END_REF][START_REF] Droit-Volet | Time and Covid-19 stress in the lockdown situation: Time free,«Dying» of boredom and sadness[END_REF][START_REF] Grondin | Pandemic, Quarantine, and Psychological Time[END_REF][START_REF] Loose | Disrupting times in the wake of the pandemic: Dispositional time attitudes, time perception and temporal focus[END_REF][START_REF] Martinelli | Time and Emotion in the lockdown for the Covid-19 epidemic: The determinants of our experience of time[END_REF][START_REF] Ogden | Distortions to the passage of time during England's second national lockdown: A role for depression[END_REF][START_REF] Ogden | The passage of time during the UK Covid-19 lockdown[END_REF] suggesting that lockdowns too induced temporal distortions and disorientations. Reports during the pandemic went from self-reported difficulties with keeping track of the time of day and of the days themselves to quantitative descriptions of subjective duration expanding and time slowing down [START_REF] Cellini | Changes in sleep pattern, sense of time and digital media use during COVID-19 lockdown in Italy[END_REF][START_REF] Cravo | Time experience in social isolation: A longitudinal study during the first months of COVID-19 pandemic in Brazil[END_REF][START_REF] Droit-Volet | Time and Covid-19 stress in the lockdown situation: Time free,«Dying» of boredom and sadness[END_REF][START_REF] Ogden | Distortions to the passage of time during England's second national lockdown: A role for depression[END_REF][START_REF] Loose | Disrupting times in the wake of the pandemic: Dispositional time attitudes, time perception and temporal focus[END_REF]Martinelli et al., 2020;[START_REF] Ogden | Distortions to the passage of time during England's second national lockdown: A role for depression[END_REF][START_REF] Ogden | The passage of time during the UK Covid-19 lockdown[END_REF]. All surveys confirmed self-reported temporal distortions during lockdowns but did not necessarily converge on their underlying explanatory causes. Changes in felt passage of time during the pandemic appeared to be dependent on how lonely participants felt and no as much on the objective stringency index undergone by participants: the more isolated one felt, the slower time seemed to pass [START_REF] Chaumon | The Blursday Database: Individuals' Temporalities in Covid Times[END_REF]. This rating and phenomenological measurement of felt time during the pandemic converged with more cognitive measures of temporal distance assessing how far in past or future particular life events seem to be: individuals who felt isolated evaluated events to be further away in both their past and future orientations [START_REF] Chaumon | The Blursday Database: Individuals' Temporalities in Covid Times[END_REF].

Conclusions

In lab settings, we design experiments to control for, and separate, confounding factors to single out variable of interests. In this process, we reduce the problem to its basic constituents: the scientific method identifies which variables are necessary and sufficient to replicate a behavioral, perceptual or cognitive effect. Factors affecting a single behavior can be exogenous (stimuli) and arguably easiest to control for in an experiment. Others are endogenous, sometimes oblivious to the participants' own awareness ("unconscious", "implicit") or not easily intelligible to consciousness ("qualia"): these constitute the hard problem of cognition to which psychological time and temporal cognition belong.

Empirical work on the impact of isolation (broadly construed) on subjective temporalities is scarce, but temporal disorientations often evidenced with the deprivation of temporal cues clearly reducing one's ability to orient in time. The study of time in biology is integrative: chronobiology focuses on automatic physiological responses of the body; time perception mostly focuses on the lived present, whether implicit (in the form of temporal expectations [START_REF] Nobre | Anticipated moments: Temporal structure in attention[END_REF]) or intelligible to consciousness (as magnitude estimation or decision-making); memory research focuses on mapping the temporal relations between events stored for future use. Whether this compartmentalization should be regarded as theoretically grounded and operant for understanding temporal cognition and its biological implementation remains largely unexplored even if alluded to [START_REF] Laje | The times of our lives: Interaction among different biological periodicities[END_REF][START_REF] Tucci | Towards an integrated understanding of the biology of timing[END_REF].

That sharing meaningful information through a symbolic system (from bees to humans) can affect chronobiology and the coding of events in a temporal cognitive map highlights the remarkable importance of a top-down approach to temporal cognition. For us humans, sharing future plans using clocks, calendars and agendas (all sophisticated counters and timelines directed towards a quantification of time that is meaningful to the observer) indicate that neither chronobiology nor temporal cognition are fully reducible to the automatisms of well-clocked physical systems. This uniqueness should be a strong driving force for our understanding of minds and behaviors in biological systems.

Acknowledgments: V.vW. received funding from La Diagonale Paris-Saclay and AAP Arts-Sciences-Technologies "Expérimentation 2020" for the project AEON and EXPERIENCE project of the European Commission H2020 Framework Program, Grant No. 101017727.


Zakeye Azaki
email: zakeye.azaki@gipsa-lab.grenoble-inp.fr

Antoine Girard
email: antoine.girard@l2s.centralesupelec.fr

Sorin Olaru
email: sorin.olaru@l2s.centralesupelec.fr

Predictive and Symbolic Control: Performance and Safety for Non-linear Systems

Keywords: Model predictive control, Symbolic control, Recursive feasibility, Controlled invariant set, Terminal constraints, Non-linear systems

Although Model Predictive Control (MPC) has proven its e ciency in the process operation and it is known for its high performance, it also su ers from design limitation. One of the fundamental issues for such an optimization-based technique is the di culty to guarantee recursive feasibility in the absence of terminal constraints, or alternatively, the complexity of design when a certain basin of a raction or a controlled invariant set needs to be certi ed for the closed loop in the most general nonlinear se ing. Based on symbolic control techniques, this paper proposes a simple and guaranteed solution for such problems. As a main result, a Symbolically guided Model Predictive Control scheme is developed. is controller is an improved version of the generic MPC approach such that the recursive feasibility is guaranteed through appending time-varying terminal constraints, carefully designed using the symbolic control approach, to the optimization problem of the original MPC formulation.

INTRODUCTION

Model Predictive Control (MPC) is well established in the control engineering studies as a model-based methodology able to synthesize the control action based on the online solution of an open loop optimal-control problem subjected to physical constraints [START_REF] Mayne | Model predictive control: Recent developments and future promise[END_REF]; [START_REF] Maciejowski | Predictive control: with constraints[END_REF]). ese constraints are de ning safety regions in the state space or restrictions on control variables modelling the saturation of actuators or limitation in the available control energy. MPC becomes, nowadays, one of the most advanced control technique capable to control multivariate plants and it has proven its e ciency in industrial processes, mainly for systems with slow dynamics, as chemical processes [START_REF] Qin | A survey of industrial model predictive control technology[END_REF]).

Aside the practical computational problems related to the implementation of such an optimization-based control, one of the most important theoretical problems in MPC is the recursive feasibility, which deals with the fundamental guarantee that the nominal MPC closed-loop solutions have to remain within a safe set for an inde nite time. Unfortunately, although it is absolutely recommended from a theoretical point of view [START_REF] Mayne | Stabilizing conditions for model predictive control[END_REF]), it is not always easy to construct an MPC controller which has an a priori guarantee of recursive feasibility while maintaining the e ciency of MPC.

ere are few approaches in the literature that suggest a solution for this problem [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF]). In [START_REF] Chmielewski | On constrained in nite-time linear quadratic optimal control[END_REF], the approach focuses on solving the problem by computing a large enough prediction horizon N of the optimization problem while [START_REF] Sznaier | Suboptimal control of linear systems with state and control inequality constraints[END_REF] is project has received funding from the H2020-EU.1.1. research and innovation programme(s) -ERC-2016-COG under grant agreement No 725144.

investigates the relationship between the sub-optimality and the stability. More recent studies [START_REF] Grüne | Nonlinear model predictive control[END_REF]) have shown that choosing the length of the prediction horizon to ensure stability is not a trivial task. Moreover, enlarging the prediction horizon increases the complexity of the optimization problem for MPC and requires more computational power. Other suggested approaches (Lö erg (2012)) append the optimization problem by a maximal controlled invariant terminal constraint set. Unfortunately, the construction of this set is di cult and non-guaranteed to preserve the controlled invariance properties in a general nonlinear framework. e approach proposed in the present paper is to build on the recent advances on symbolic control design (see e.g. [START_REF] Tabuada | Veri cation and control of hybrid systems: a symbolic approach[END_REF]; [START_REF] Belta | Formal methods for discrete-time dynamical systems[END_REF]). Symbolic control is an approach to automatically synthesize certi able controllers, for general nonlinear systems, that handle state and input constraints and various speci cations such as safety, reachability or a ractivity [START_REF] Girard | Least-violating symbolic controller synthesis for safety, reachability and a ractivity speci cations[END_REF]). However, to obtain good performance with symbolic control, one needs very ne partitions which are very costly from the computational viewpoint. In this paper, we develop a novel MPC scheme that we call Symbolically guided Model Predictive Control (SgMPC) where time-varying terminal constraints are appended to classical MPC formulation. e time-varying constraints are carefully designed using symbolic control techniques in such a way that recursive feasibility of the SgMPC controller is guaranteed. Time varying terminal constraints have already been considered in MPC, e.g in [START_REF] Limon | Enlarging the domain of a raction of mpc controllers[END_REF]; [START_REF] Kögel | Stability of nmpc with cyclic horizons[END_REF]; [START_REF] Lazar | Computation of terminal costs and sets for discrete-time nonlinear mpc[END_REF]. In these works, the sequence of terminal constraint is xed a priori and is chosen to be either constant a er some time or periodic. In comparison, the sequence of terminal constraints in our approach is determined dynamically at run-time using a designed feedback mechanism. Finally, let us remark that while most of MPC approaches addresses both safety and stability requirements, in this paper we only deal with safety constraints and leave stability properties for future research.

Paper Organization: is paper is organized as follows. In Section 2, we illustrate the main and general implemented principle to enforce MPC recursive feasibility by time-varying terminal constraints.

e design of suitable terminal constraints using symbolic control techniques is discussed in Section 3. Section 4 presents possible re nements improving the approach presented in Section 3. Finally, Section 5 presents a series of numerical experiments to illustrate the performance and to validate the e ciency of the SgMPC strategy.

Notations: N, Z, R and R + denote the sets of natural, integer, real and non-negative real numbers, respectively. Given a set X we denote 2 X to the set of subsets of X. e empty set is denoted by ∅. For x ∈ R n , we denote by x i its i-th coordinate, i = 1, . . . , n. We de ne a partial order on R n as follows: for x, x ∈ R n x x if and only if x i ≤ x i , for all i = 1, . . . , n. Similarly, x ≺ x if and only if x i < x i , for all i = 1, . . . , n. We denote

[x, x ] = {y ∈ R n | x y x } and [x, x ) = {y ∈ R n | x y ≺ x }. en [x, x ] + [a, b] = [x + a, x + b].

TIME-VARYING TERMINAL CONSTRAINTS FOR RECURSIVE FEASIBILITY IN MPC

In this section, we revisit recursive feasibility in MPC and describe the mechanisms to enforce them using time-varying terminal constraints. We rst present the problem under consideration. en, we establish conditions on the design of timevarying terminal constraints, with the goal to provide theoretical guarantees of recursive feasibility.

System dynamics

Constrained control design is investigated in the current work for discrete-time nonlinear systems, assuming that all the system's states are measurable. e model of the system's dynamics is considered in the following form:

x t+1 = f (x t , u t ) (1) with state x t ∈ R d and control input u t ∈ R m , for time t ∈ N. f : R d × R m → R d is a known and generally nonlinear map, such that f = (f 1 , f 2 , ..., f d ) T .
We employ the notation u = (u 0 , u 1 , ...), with u t ∈ R m , for a potentially in nite control sequence and the notation φ(t, x 0 , u) for the state reached at sampling instant t from the initial state x 0 and under the control sequence u. Given N ≥ 1 as prediction horizon, a control sequence computed at sampling instant t will be denoted as u N t = (u 0|t , ..., u N -1|t ) ∈ R m×N . Given state x t at sampling instant t, the associated predicted trajectory at t ∈ N is denoted

x N t = (x 0|t , x 1|t , ..., x N |t ) where x k|t = φ(k, x t , u N t ), for k = 0, . . . , N .

Model predictive control

Considering the control system (1), the core of an MPC scheme relies on the resolution of an optimal control problem, at each sampling instant t ∈ N. is nite-horizon optimization, over the nite prediction horizon N , takes the following form:

arg min u N t J N (x t , u N t ) = N -1 k=0 (x k|t , u k|t ) + L(x N |t ) (2) subject to    x k|t = φ(k, x t , u N t ), k = 0, ..., N ; x k|t ∈ X, u k|t ∈ U, k = 0, ..., N -1; x N |t ∈ X t .
(3) e control constraint set is U ⊆ R m , while the state constraint set X ⊆ R d . Let us emphasize that in (2)-( 3), the terminal constraint set is time-varying and is described by the set

X t ⊆ X. e function : R d × R m → R is called stage cost or running cost, the function L : X → R is called terminal cost. De nition 2.1. (Feasible control sequence) Given a state x t ∈ X and a terminal constraint set X t ⊆ X, a nite control sequence u N t = (u 0|t , ..., u N -1|t
), with its associated trajectory x N t = (x 0|t , ..., x N |t ), is said to be feasible if:

x k|t ∈ X, u k|t ∈ U, ∀k = 0, ..., N -1; x N |t ∈ X t .
We denote by U f (x t , X t ) the set of all feasible control sequences u N t for state x t ∈ X and terminal constraint set X t ⊆ X.

We assume in the following that U, X and X t are compact sets and that f , and L are continuous functions. en, whenever U f (x t , X t ) = ∅, the optimization problem ( 2)-( 3) admits at least one minimizer, which is denoted by the optimal control sequence u

N * t (x t , X t ) = (u * 0|t , ..., u * N -1|t ).
en, the MPC control action fed to the system can be described as a feedback law

µ N (x t , X t ) = u * 0|t .
e resolution of the optimization problem (2)-( 3) is repeated online, at each sampling instant leading to the following closed-loop behavior

x t+1 = f (x t , µ N (x t , X t )).
(4) A fundamental problem in MPC is that of recursive feasibility.

e optimization problem (2)-( 3) is recursively feasible if it can be shown that U f (x t , X t ) = ∅ at each sampling instant, resulting in a well-posed closed loop-system (4) satisfying both state and input constraints at all time t ∈ N.

A classical way (see e.g. [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF]) to enforce recursive feasibility is to use a controlled invariant set X I ⊆ X as terminal constraint set in (2)-(3), i.e., X t = X I , for all t ∈ N. e larger X I (i.e. the closer to the maximal controlled invariant set) the be er since it provides more freedom in ( 2)-(3) to optimize the performance cost. However, for nonlinear systems and possibly non-convex state and input constraints, large controlled invariant sets may be very complex and typically non-convex, rendering the optimization problem (2)-(3) di cult to solve online.

In the following, we propose an alternative approach that takes advantage of the fact that time-varying terminal constraint sets can be used in the MPC design in (2)-(3). Essentially, we use a simple (e.g. convex) subset X t ⊆ X I as terminal constraint. However, since X t is generally not control invariant itself, it needs to be adapted at each time step in order to ensure recursive feasibility. In the following section, we present an approach to design a suitable sequence of terminal constraint sets ensuring recursive feasibility.

Construction principle for time-varying terminal constraints

Let us assume the existence of a possibly complex (i.e. nonconvex) controlled invariant set X I ⊆ X. Furthermore, assume the existence of a set-valued map T : X I → 2 X I and of a controller C :

X I → U such that ∀x ∈ X I , f (x, C(x)) ∈ T (x).
(5) Let us remark that a trivial choice for T and C is given by T (x) = X I with C being a controller guaranteeing the closedloop invariance properties of X I . However, in the following, we will be interested in maps T such that T (x) are simple, typically convex, sets.

We now describe the construction of the time-varying terminal constraint sets for the optimization problem (2)-(3):

• At sampling instant t = 0, with initial state x 0 ∈ X I , let

u N 0 = (C(x 0|0 ), ..., C(x N -1|0 )) (6
) where x 0|0 = x 0 and

x k+1|0 = f (x k|0 , C(x k|0 )), k = 0, . . . , N -1. Let the terminal constraint set at time t = 0 be de ned as:

X 0 = T (x N -1|0 ).

(7) • For t ∈ N, consider the optimal control sequence at sampling time t,

u N * t (x t , X t ) = (u * 0|t , ..., u * N -1|t
) and the associated predicted trajectory

x N * t = (x * 0|t , ..., x * N |t ). Let u N t+1 = (u * 1|t , ..., u * N -1|t , C(x * N |t )) (8
) and let the terminal constraint set at time t + 1 be de ned as:

X t+1 = T (x * N |t ). (9)
For the sequence of terminal constraint sets constructed above, we can show the following result:

eorem 2.1. Let us assume that there exist a set-valued map T : X I → 2 X I and a controller C : X I → U satisfying the conditions presented in (5) with X I ⊆ X. en, for any initial state x 0 ∈ X I , with the time-varying terminal constraint sets X t selected according to (7) and ( 9):

• MPC optimization problem (2)-( 3) is recursively feasible;

• the control sequences u N t constructed based on ( 6) and ( 8) are feasible at all sampling instants.

Proof. Let us consider an initial state x 0 ∈ X I . Let the control sequence u N 0 be given by ( 6) with its associated predicted trajectory x N 0 = (x 0|0 , ..., x N |0 ). en, according to (5), x k+1|0 ∈ T (x k|0 ) ⊆ X I ⊆ X, ∀k = 0, ..., N -1. Moreover, the terminal constraint given by ( 7) is satis ed:

x N |0 ∈ T (x N -1|0 ) = X 0 . erefore, it follows that the control sequence u N 0 ∈ U f (x 0 , X 0 ). Now, let t ∈ N, let us consider the control sequence u N t+1
given by ( 8) with its associated predicted trajectory x N t+1 = (x 0|t+1 , ..., x N |t+1 ). Obviously, x k|t+1 = x * k+1|t , for all k = 0, . . . , N -1. erefore, from (2)-(3), x k|t+1 ∈ X and x N -1|t+1 ∈ X t ⊆ X I . en, based on (5) it holds

x N |t+1 = f (x N -1|t+1 , C(x N -1|t+1 )) ∈ T (x N -1|t+1 ).
Remarking that from (9),

T (x N -1|t+1 ) = T (x * N |t ) = X t+1 , we obtain that u N t+1 ∈ U f (x t+1 , X t+1 ).
From above, we see that the set of feasible control sequences is non-empty at any time. Hence, recursive feasibility is guaranteed for the MPC optimization problem.

In this section, we proposed a framework for MPC with timevarying terminal constraints and derived design principles ensuring recursive feasibility. e main problem considered in the following sections is that of constructing the map T : X I → 2 X I and controller C : X I → U satisfying (5). is is done using symbolic control techniques.

SYNTHESIS OF TERMINAL CONSTRAINT SETS

BASED ON SYMBOLIC CONTROL Symbolic control (see e.g. [START_REF] Tabuada | Veri cation and control of hybrid systems: a symbolic approach[END_REF]; Belta et al. ( 2017)) is a computational technique for synthesizing controllers for nonlinear systems with state and input constraints. e approach is based on the use of symbolic models, which are nite state / nite input dynamical systems over-approximating the dynamics of the system we want to control. Compared to MPC, most of the computation is carried o ine. Symbolic control is particularly helpful for the computation of controlled invariant. In this section, we show how one can use symbolic models to design the map T and controller C satisfying (5).

Computation of symbolic models

We brie y recall an approach to compute a symbolic model of (1) similar to that presented in [START_REF] Reissig | Feedback renement relations for the synthesis of symbolic controllers[END_REF].

Discretization of states and inputs: Since X is assumed to be compact there exists an interval R X = [x, x) such that X ⊆ R X . We rst start by considering a partition S 0 of R X such that each element s ∈ S 0 is an interval of the form s = [s, s). en, we obtain a partition S of R d de ned as follows S = S 0 ∪ {R d \ R X }. e elements of S are referred to as symbolic states. We also de ne the quantizer σ : R d → S de ned by

∀x ∈ R d , σ(x) = s ⇐⇒ x ∈ s.
e symbolic state constraint set S ⊆ S 0 is de ned as follows

S = {s ∈ S 0 | s ⊆ X}. ( 10
)
We also consider a nite subset of inputs U ⊆ U. e elements of U are referred to as symbolic inputs.

Computation of the symbolic transition relation: e symbolic model is a dynamical system with nite sets of states and inputs S and U , respectively. For an input u ∈ U and an interval s ∈ S 0 , let us denote by f (s, u) an interval such that f (s, u) ⊆ f (s, u). Such interval over-approximations can be computed using interval reachability analysis (see e.g. the various techniques described in [START_REF] Meyer | Interval Reachability Analysis: Bounding Trajectories of Uncertain Systems with Boxes for Control and Veri cation[END_REF]). e dynamics of the symbolic model is given by the transition relation, which is a set-valued map F : S × U → 2 S de ned for all s ∈ S 0 , u ∈ U by

F (s, u) = σ f (s, u) , (11)
and for s

= R d \ R X , u ∈ U , by F (s, u) = S.
en, the symbolic model is the dynamical system given by the di erence inclusion s t+1 ∈ F (s t , u t ) (12) with s t ∈ S, u t ∈ U , for time t ∈ N.

Symbolic design of terminal constraint sets

Let S I be the maximal robust controlled invariant set of ( 12) contained in the symbolic state constraint set S, i.e. the largest subset of S such that ∀s ∈ S I , ∃u ∈ U, such that F (s, u) ⊆ S I . Since S and U are nite sets, there exist algorithms to compute S I in a nite number of iterations (see e.g. [START_REF] Tabuada | Veri cation and control of hybrid systems: a symbolic approach[END_REF]; [START_REF] Girard | Least-violating symbolic controller synthesis for safety, reachability and a ractivity speci cations[END_REF]). en, let us consider a symbolic controller K : S I → U guaranteeing the closed-loop robust invariance property of S I :

∀s ∈ S I , F (s, K(s)) ⊆ S I . ( 13
)
Let us now de ne the set

X I = σ -1 (S I ), (14)
and for all x ∈ X I ,

T (x) = f σ(x), K(σ(x)) , C(x) = K(σ(x)). (15)
en, the following result holds: eorem 3.1. Let X I , T and C be given by ( 14) and ( 15). en, X I is a controlled invariant set included in X. Moreover, for all x ∈ X I , T (x) ⊆ X I , C(x) ∈ U and (5) holds.

Proof. Let x ∈ X I , then C(x) = K(σ(x)) ∈ U ⊆ U by construction. From ( 15), ( 11), ( 13) and ( 14)

T (x) = f (σ(x), K(σ(x))) ⊆ σ -1 (F (σ(x), K(σ(x)))) ⊆ σ -1 (S I ) = X I . Moreover, by (15) f (x, C(x)) = f (x, K(σ(x))) ∈ f (σ(x), K(σ(x))) f (σ(x), K(σ(x))) ⊆ f (σ(x), K(σ(x)) = T (x)
. us, (5) holds. From above, we get that for all x ∈ X I f (x, C(x)) ∈ T (x) ⊆ X I . Hence, X I is a controlled invariant set. Finally, since S I ⊆ S and by (10), we get that

X I = σ -1 (S I ) ⊆ σ -1 (S) ⊆ X.
Hence, it follows from eorem 3.1, that T and C given by ( 15) and synthesized using symbolic control techniques are suitable for the design of time-varying terminal constraints in the MPC problem (2)-(3).

Let us remark that one could also use the control invariant X I in ( 14) as terminal constraint to ensure recursive feasibility of (2)-(3). However, X I is de ned as a union of (possibly many) intervals.

en, this introduces some combinatorial features to (2)-( 3), which makes it very hard to solve online. In comparison, the time-varying constraints given by the map T in (15) are simple intervals and can be easily handled by othe-shelf optimization so ware.

Finally, it is important to remark that all computations described in this section can be carried out o ine and that T and C can be easily stored as lookup tables. In the following, we refer to this approach by Symbolically guided Model Predictive Control (SgMPC).

FURTHER IMPROVEMENTS ON SgMPC

In this section, we report two improvements of the technique described above. e rst one allows us to design larger terminal constraint sets giving more freedom to optimize the behavior. e second one makes it possible to use the symbolic model to optimize the controller C in view of the initialization of the MPC problem (2)-(3).

Enlarged terminal constraint sets

We rst show how to redesign the map T given by ( 15) in order to provide more degrees of freedom for optimization. Consider X I as in ( 14) and C as in ( 15). For all s ∈ S I , let

ρ(s) = max ρ ≥ 0| f (s, K(s)) + ρ[-1, 1] ⊆ X I .
en, let us de ne the map, given for all x ∈ X I by

T (x) = T (x) + ρ(σ(x))[-1, 1]. (16)
An illustration of the map T can be seen in Fig. 1. Let us remark that by design, we have for all x ∈ X I T (x) ⊆ T (x) ⊆ X I . e above inclusions, together with eorem 3.1 lead to the following result: Corollary 4.1. Let X I , T and C be given by ( 14), ( 16) and (15).

en, for all x ∈ X I , T (x) ⊆ X I and (5) holds with T and C.

Hence, using T instead of T makes it possible to use more relaxed terminal constraints, also under the form of intervals, while still guaranteeing recursive feasibility. Moreover, similar to T , the map T can be computed o ine and stored in a lookup table. ere is a lot of freedom in the design of the symbolic controller K. Indeed, there are o en many controllers satisfying (13), i.e. enforcing the closed-loop robust invariance of S I . So it is natural to consider optimizing over the set of possible symbolic controllers.

In particular, symbolic control makes it possible to synthesize controllers rendering S I robustly invariant, while minimizing some receding horizon cost function such as the following:

N -1 k=0 ˆ (s k|t , u k|t ) + L(s N |t )
where ˆ (s, u) = max x∈s (x, u) and L(s) = max x∈s L(x).

is optimization problem is solved in [START_REF] Meyer | Safety control with performance guarantees of cooperative systems using compositional abstractions[END_REF]. Let us remark that this problem can be seen as the symbolic counterpart of ( 2)-(3). One major di erence, though, is that all the computations can be done o ine for our symbolic model ( 12).

en, we can use the optimized controller K to design the state dependent terminal constraint and the initial control sequence guess, that are utilized in SgMPC. All the preceding results are still valid and the performance of SgMPC is improved when it is guided by an optimized symbolic controller (OSC).

NUMERICAL EXAMPLE

Let us consider a discrete-time non-linear system with the state vector x ∈ R 3 and control input vector u ∈ R 2 , such that x= (x 1 , x 2 , x 3 ) T and u= (u 1 , u 2 ) T and the dynamics governed by the following equations:

x 1 (t + 1) = x 1 (t) + u 1 (t) cos(x 3 (t))

x 2 (t + 1) = x 2 (t) + u 1 (t) sin(x 3 (t))

x 3 (t + 1) = x 3 (t) + u 2 (t) (mod 2π) (17)
e trajectories represent the behaviour of a mobile cart with (x 1 , x 2 ) representing the 2D Cartesian coordinates in meter.

x 3 represents the angular orientation of the velocity vector around the x-direction in radians, u 1 is the linear velocity in m/s and u 2 is the angular velocity in rd/s. Note that, by convention we consider that the angle x 3 (t) ∈ [-π, π). e system is subjected to state and control input constraints, such that the state constraint set is

X = (x 1 , x 2 ) T ∈ R 2 x 2 1 -x 2 2 ≤ 4 4x 2 2 -x 2 1 ≤ 16 (18)
and the control input constraint set is

U = [0.2, 2] × [-1, 1]. (19)
For the optimization problem (2)-(3), the prediction horizon was chosen to be N=20 and the stage cost

(x, u)= 100||(x 1 , x 2 ) T -x r || 2 + ||u|| 2 where x r ∈ R 2 is a reference position. e terminal cost is set to L(x) = 100||(x 1 , x 2 ) T -x r || 2 .
In order to construct the symbolic abstraction we have chosen R X = [x, x) with x = (-3.5, -2.6, -π) T , x = (3.5, 2.6, π) T . e following subsections compare the performance of OSC (Optimized Symbolic Control), MPC, and SgMPC with enlarged terminal constraints guided by OSC. For these simulations, we used a symbolic model with 109200 symbolic states and 40 symbolic inputs. Using symbolic control techniques, a control invariant was computed and is shown in Figure 2.

In our rst experiment, we consider a reference x r = (0.5, 0.5) inside the constraint set. Figure 3 shows that the three behaviors are quite acceptable. e reference is tracked correctly by all controllers and all state and input constraints are satis ed. OSC is slightly less accurate than MPC and SgMPC in tracking. e asymptotic performances of MPC and SgMPC are equivalent. e transitory phase of MPC is shorter than that of SgMPC.

In our second experiment, we consider a reference

x r = ( 32/3, 20/3) on the boundary of the constraint set. e simulation results are shown in Figure 4. First, it should be noticed that the simulation of the system controlled by MPC stopped at t = 13 because the optimization became infeasible. In comparison, both OSC and SgMPC are able to enforce the constraints at all time. As for tracking the reference, one can see that the trajectory controlled by OSC remains quite far from the reference x r which is located in the top right corner of the domain. In comparison, SgMPC is much more successful in driving the system close to the reference. Hence, it appears that SgMPC is an interesting alternative to MPC and OSC since it makes it possible to combine high performances with safety constraints. State and inputs signals are for SgMPC are represented on Figure 5. One can check that the control signals are periodic a er some time.

CONCLUSION

e recursive feasibility of NMPC has been revisited in the light of the design enhancements which can be obtained through the symbolic control design. As a main theoretic contribution, we propose the use of time-varying terminal constraints to guarantee the controlled invariance of the feasible set. From the methodological point of view, it is shown that such time-varying constraints can be obtained from a symbolic control. e proposed Symbolically guided Model Predictive Control scheme proves to provide a simple and guaranteed solution for the complex control of nonlinear constrained dynamical systems. In the future, it is planned to extend this approach to provide performance and stability guarantees.

  Figure 1. of the enlarged terminal constraint set construction 4.2 Optimized symbolic controller

Figure 2 .

 2 Figure 2. Controlled invariant X computed using symbolic control techniques.

Figure 3 .

 3 Figure 3. For reference position x r = (0.5, 0.5), closed-loop trajectories with OSC (a), MPC (b), SgMPC (c).

Figure 4 .

 4 Figure 4. For reference position x r = ( 32/3, 20/3), closed-loop trajectories with OSC (a), MPC (b), SgMPC (c).

Figure 5 .

 5 Figure 5. For reference position x r = ( 32/3, 20/3), state and input signals for SgMPC.