Mohamed Amine Bouguerra
email: mabouguerra@gmail.com

Thierry Fraichard
email: thierry.fraichard@inria.fr

Mohamed Fezari
email: mouradfezari@yahoo.fr

Viability-Based Guaranteed Safe Robot Navigation

Keywords: Provable Safety, Collision Avoidance, Autonomous Navigation, Viability Theory

Guaranteeing safe, i.e. collision-free, motion for robotic systems is usually tackled in the Inevitable Collision State (ICS) framework. This paper explores the use of the more general Viability theory as an alternative when safe motion involves multiple motion constraints and not just collision avoidance. Central to Viability is the so-called viability kernel, i.e. the set of states of the robotic system for which there is at least one trajectory that satisfies the motion constraints forever. The paper presents an algorithm that computes off-line an approximation of the viability kernel that is both conservative and able to handle time-varying constraints such as moving obstacles. Then it demonstrates, for different robotic scenarios involving multiple motion constraints (collision avoidance, visibility, velocity), how to use the viability kernel computed off-line within an on-line reactive navigation scheme that can drive the robotic system without ever violating the motion constraints at hand.

Introduction

It is expected that robotic systems of various kinds and with various roles will increasingly live in human-populated workspaces, the safety of their motion grows in importance accordingly. Safe motion is often equated with the ability of the robot to avoid collision with its surroundings. It is now understood that collision avoidance requires the ability to stay away from what is known as Inevitable Collision States [START_REF] Fraichard | Inevitable collision states. a step towards safer robots[END_REF]. An Inevitable Collision State (ICS) is a state for which no matter what the future trajectory of the robot is, collision will eventually occur. Designing a control system for a robot that is able to compute its inevitable collision states and stay away from them at all time is the key to guaranteed motion safety [START_REF] Martinez-Gomez | An efficient and generic 2d inevitable collision state-checker[END_REF].

The characterization of ICS is intricate since it requires in theory to check for collision every possible trajectory of infinite duration a robot might follow from a given state. A practical answer to this issue is to select a subset of so-called evasive trajectories, and a state is deemed an ICS if none of the evasive trajectories starting from it is collision-free. This results in a conservative approximation of the ICS set whose quality depends essentially on the choice of the evasive trajectories. If not for a good choice, most states may end up labeled as ICS. The problem with this approach is that it is not clear in general how to select the set of evasive trajectories so as to obtain a reasonable approximation of the ICS set. In static workspaces, braking trajectories, i.e. trajectories that drive the robot to a stop, are good candidates. In dynamic workspaces though, even with knowledge of the future behavior of the obstacles, it is all the more challenging to determine an appropriate set of evasive trajectories. Now, there is often more to motion safety than mere collision avoidance. In many cases, the motion of the robot must satisfy various types of constraints in order to be considered safe. For instance, a legged robot should maintain its balance, the speed of an airplane should never go beyond its stalling speed, or a spy robot should stay out of sight of a patrol. No matter what the set of constraints that the robot ought to satisfy, they yield a set of forbidden states that the robot should avoid. The tenet of this paper is that motion safety in general should receive an ICS-like treatment. In other words, the robot should of course avoid the states that violate the constraints, but more importantly, it should avoid the states inevitably leading to them.

To address this key question, this paper considers the Viability framework which is more general than the ICS framework. Viability theory [START_REF] Aubin | Viability Theory: New Directions[END_REF] addresses the following question: how to control dynamical systems subject to viability constraints? Viability constraints define a subset of the state space of the system within which the system should remain. A viable state is guaranteed to have at least one sequence of controls which will keep the system within the viability constraint set indefinitely. Conversely, nonviable states are those where failure is no longer avoidable. Note that when collision avoidance is the only viability constraint, the nonviable states are Inevitable Collision States. The viability kernel of the viability constraints is the set of all its viable states. In this framework, the ability to design a control system for a robot that is able to compute its viability kernel and remain inside it at all times is also the key to guaranteed motion safety.

The characterization of the viability kernel is at least as challenging as the characterization of ICS and the approach adopted in this paper is also to compute a conservative approximation of the viability kernel. The starting point of this paper is an algorithm originally proposed to approximate viability kernels [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF]. This paper builds upon and expands [START_REF] Bouguerra | Safe motion using viability kernel[END_REF], the primary contribution of this paper is the Conservative Viability Algorithm, an adaptation of [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF]'s algorithm designed to make it, (i) conservative, and (ii) able to handle time-varying viability constraints such as moving obstacles. Besides its ability to handle different kinds of safety constraints in a unified manner, the key advantage of the algorithm proposed herein is that, unlike its ICS counterpart, the quality of the conservative approximation is in no way dependent on the choice of an appropriate set of evasive trajectories. This feature comes at the cost of a greater computational complexity though. To demonstrate its versatility and its ability to address different kinds of viability problems, the algorithm proposed has been implemented and used to compute the viability kernel for the case of a double integrator robot in seven scenarios with mixed combinations of workspace (static, moving obstacles) and viability constraint types (collision avoidance, visibility, velocity). To demonstrate the usefulness of the viability kernel computed off-line by the Conservative Viability Algorithm, it is used on-line inside a basic and purely reactive navigation scheme that proved able to control the robot in the different scenarios without ever violating the viability constraints at hand. Note that the viability kernel could just as well be used inside a motion planner in order to compute safe motions.

The paper is organized as follows: §2 reviews the relevant literature. Viability theory and the viability algorithm of [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF] are respectively presented in §3 and §4. Then, §5 and §6 respectively describe how to transform the original algorithm into a conservative one able to handle time-varying viability constraints. Finally, the robotic scenarios demonstrating guaranteed safe navigation in different situations are presented in §7 and §8

Related Works

On the ICS front, although the details may vary, most of the proposed ICS approximation methods rely in essence on the same principle: a subset of evasive trajectories is selected and states are labeled ICS if none of the evasive trajectories are collision-free. In static workspaces, braking trajectories (which drive the robot to a stop), are an obvious choice [START_REF] Bekris | Greedy but safe replanning under kinodynamic constraints[END_REF][START_REF] Seder | Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[END_REF][START_REF] Savino | Inevitable collision states for motorcycle-to-car collision scenarios[END_REF]. When the robot cannot stop, e.g. it is an airplane, circling trajectories have been considered [START_REF] Schouwenaars | Receding horizon path planning with implicit safety guarantees[END_REF][START_REF] Blaich | Motion safety for vessels: An approach based on inevitable collision states[END_REF]. In dynamic workspaces, imitating trajectories (which maintain zero relative velocity with the obstacle), have been proposed in [START_REF] Martinez-Gomez | An efficient and generic 2d inevitable collision state-checker[END_REF]. Whatever the subset of evasive trajectories selected, it is difficult to ensure the quality of the approximation for all situations and not end up with most states conservatively labeled as ICS. This difficulty plus the fact that absolute motion safety requires in general to reason over an infinite time horizon [START_REF] Fraichard | Iterative motion planning and safety issue[END_REF] have led some authors to settle for weaker motion safety guarantees. For instance, [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-ofviews in dynamic environments[END_REF] introduces passive safety: it guarantees that if a collision occurs, the robot will be at rest. A stronger form, friendly passive safety [START_REF] Macek | Towards safe vehicle navigation in dynamic urban scenarios[END_REF][START_REF] Mitsch | On provably safe obstacle avoidance for autonomous robotic ground vehicles[END_REF] ensures that if a collision ever happens the robot will be at rest, and the obstacles could have avoided the collision if they wanted to. Other methods settle to even less, they aim to improve the chance of surviving collisions with no strict guarantees however. They use other types of trajectories: for instance, trajectories that are guaranteed to be collision-free only up to a finite time [START_REF] Frazzoli | Real-time motion planning for agile autonomous vehicles[END_REF][START_REF] Hsu | Randomized kinodynamic motion planning with moving obstacles[END_REF], or trajectories that are collision-free with respect to one obstacle at a time, instead of considering them all at once [START_REF] Chan | Improved motion planning speed and safety using regions of inevitable collision[END_REF][START_REF] Shiller | Adaptive time horizon for on-line avoidance in dynamic environments[END_REF].

On the viability front, several methods have been proposed for the approximation of the viability kernel. For low dimensional systems with non linear dynamics, there are discrete methods such as the viability algorithm [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF], those based on the viscosity solutions for Hamilton-Jacobi partial differential equations [START_REF] Mitchell | A time-dependent hamilton-jacobi formulation of reachable sets for continuous dynamic games[END_REF][START_REF] Lygeros | On reachability and minimum cost optimal control[END_REF], or most recently interval analysis [START_REF] Monnet | Computing an inner and an outer approximation of the viability kernel[END_REF]. For systems whose dynamics can be described as polynomials, more efficient methods based on invariance sets have been used [START_REF] She | Computing an invariance kernel with target by computing lyapunov-like functions[END_REF][START_REF] Korda | Convex computation of the maximum controlled invariant set for polynomial control systems[END_REF]. For linear systems with higher dimensions, Lagrangian techniques can be exploited as in [START_REF] Maidens | Lagrangian methods for approximating the viability kernel in high-dimensional systems[END_REF]. Viability Theory has seen applications in several fields, and mobile robotics is one of them. In [START_REF] Bohórquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF], the problem of a biped that has to maintain its balance while also ensuring passive safety has been addressed using Model Predictive Control. Closer to the work proposed herein, a discrete method based on [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF] was developed in [START_REF] Liniger | Real-time control for autonomous racing based on viability theory[END_REF] for the purpose of safe autonomous racing, i.e. to drive as fast as possible around a predefined track. In [START_REF] Kalisiak | Approximate safety enforcement using computed viability envelopes[END_REF] and [START_REF] Kalisiak | Faster motion planning using learned local viability models[END_REF], machine learning has been deployed to approximate the viability kernel for mobile robots. The purpose in [START_REF] Kalisiak | Faster motion planning using learned local viability models[END_REF] was to filter out unsafe states from the search space, to speed up motion planners, while in [START_REF] Kalisiak | Approximate safety enforcement using computed viability envelopes[END_REF], it was to help augmenting systems' safety by preventing them from entering failure regions. A learning approach is prone to misclassification, which may not be a problem in the first case, but would void safety guarantees in the latter one.

Viability Theory

This section briefly recalls the key concepts of the viability theory, the reader is referred to [START_REF] Aubin | Viability Theory: New Directions[END_REF] for more details. Viability theory is a set of mathematical techniques that address this specific question: how to control dynamical systems subject to viability constraints? Viability constraints generally define a subset of the state space of the system within which the system should remain, e.g. avoiding collisions for a mobile robot, remaining dynamically balanced for a legged robot. A viable state is guaranteed to have at least one sequence of controls which, when applied from said state, will keep the system from failure, i.e. keep it within the viability constraint set indefinitely (Fig. 1). Conversely, nonviable states are those where failure is no longer avoidable. Note that when collision avoidance is the viability constraint then nonviable states are Inevitable Collision States [START_REF] Fraichard | Inevitable collision states. a step towards safer robots[END_REF]. The viability kernel of the constraint set is the set of all its viable states. These concepts can be formalized as follows.

Fig. 1: Main viability concepts: s 1 is viable, s 2 is nonviable.

Let A denote a continuous-time dynamical system whose dynamics is described by differential equations of the form:

ṡ(t) = f (s(t), u(t)) (1)
where s(t) ∈ S is the state of A at time t. The state of A is influenced by a control u(t) ∈ U that can be state-dependent. S and U respectively denote the state space and the control space of A. Viability constraints are characterized by the compact subset K ∈ S within which the system must be kept. Let ũ : [0, t f ] -→ U denote a control trajectory, i.e a time-sequence of controls, t f is the duration of ũ. The set of all possible control trajectories is denoted Ũ. Starting from an initial state s(t 0 ) at time t 0 , a state trajectory s(s(t 0 ), ũ) is derived from a control trajectory ũ by integrating (1). s(s(t 0 ), ũ, t) denotes the state reached at time t. A state trajectory s(s

(t 0 ), ũ) is said to be viable in K on an interval [0, t f ], t f ≤ +∞, if ∀t ∈ [0, t f ], s(s(t 0 ), ũ, t) ∈ K.
Viable states are those for which there exists at least one control trajectory ũ yielding a state trajectory viable in K at all times i.e. on the interval [0, +∞).

The basic problem in the viability theory is to find the viability kernel of K, i.e. the set of all its viable states:

Definition 1 (Viability Kernel) Viab f (K) = {s(t 0 ) ∈ K | ∃ ũ ∈ Ũ : ∀t ≥ 0, s(s(t 0 ), ũ, t) ∈ K} (2)
Once the viability kernel is determined, the next step is to compute the regulation map, the set-valued map s ∈ Viab f (K) R(s) ⊂ U that indicates at each state the set of viable controls that, when applied, will maintain the system inside the viability kernel.

The following section will present the viability algorithm from [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF], that aims at approximating the viability kernel of K for the dynamical system (1) along with providing its corresponding regulation map.

Viability Algorithm

The viability algorithm from [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF] operates in two stages. It first approximates the original continuous problem by discretizing it in time and space. Then, it computes the exact viability kernel for the discretized problem in a recursive way.

Discretization

The problem is first discretized in time. There exist different ways to transform a continuoustime model into its discrete counterpart, the Euler explicit discrete scheme is the most straightforward. Under this scheme, the discrete-time version of the dynamical system (1) is:

s n+1 = g(s n , u n ) = s n + ρf (s n , u n ) u n ∈ U ( 3
)
where ρ is the discrete time step. The state space is then reduced to a finite subset of S, for instance a regular grid of step d, denoted S d . Note that the discrete system (3) cannot be readily defined on the finite grid S d because nothing guarantees that, for all s ∈ S d , the image g(s, u) belongs to S d . To address this issue, g r is introduced, it is the extension of g with an hyperball of radius r:

g r = g + V(r) (4)
where V(r) is the hyperball of radius r. r is chosen such that:

∀s ∈ S d , g r (s, u) ∩ S d = ∅ (5)
An obvious choice is r = d. The control space is also reduced to a finite subset denoted U d . Finally, the discrete and finite dynamical system obtained is:

s n+1 ∈ g r (s n , u n ) = s n + ρf (s n , u n ) + V(d) u n ∈ U d (6)

Computing the Discrete and Finite Viability Kernel

The viability kernel of K d = K ∩ S d for the discrete and finite system ( 6) is computed as follows: K 0 is initialized to K d , and the sequence of subsets K 1 , K 2 , K 3 , ..., K n , ... is recursively defined such that:

K n+1 = {s ∈ K n | ∃u ∈ U d : g r (s, u) ∩ K n = ∅} (7)
This will incrementally refine the grid K d by discarding at each iteration the states from which the system will inevitably leave the grid in the next step. Let

K ∞ = ∞ n=0 K n , it has been established in [32] that K ∞ is the largest subset of K d such that: {∀s ∈ K ∞ , ∃u ∈ U d : g r (s, u) ∈ K ∞ } (8)
or equivalently:

K ∞ = Viab g r (K d ) (9)
and, since K d is finite, there exists a finite integer p such that:

∀n ≥ p : K n = K p (10)
which guarantees the convergence of the recursion. Thus the viability kernel of K d for the discrete and finite system (6) can easily be computed in a finite number of steps using [START_REF] Brias | Accelerating viability kernel computation with cuda architecture: application to bycatch fishery management[END_REF] (see Algorithm 1).

Algorithm 1: Viability Algorithm [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF] Input: Discrete-time dynamical system g r ; Discrete state space S d ; Discrete control space

U d ; Viability constraint set K Output: Viability kernel Viab g r (K d ) 1 K d ← S d ∩ K; 2 n ← 0; 3 K 0 ← K d ; 4 repeat 5 K n+1 ← {s ∈ K n | ∃u ∈ U d (s) : g r (s, u) ∈ K n } 6 n ← n + 1 7 until K n = K n+1 ; 8 return K n
Once the viability kernel Viab g r (K d ) has been computed, it is straightforward to retrieve the discrete regulation map R d which is defined for every state in Viab g r (K d ) as:

R d (s) = {u ∈ U d | g r (s, u) ∈ Viab g r (K d )} (11)
This regulation map provides all the viable controls that are available at each state. Choosing controls belonging to R d ensures that the system will remain in K d at all times. It is important to note that, although the viability kernel Viab g r (K d ) is only an approximation of the viability kernel for the continuous problem Viab f (K), the authors in [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF] proved and gave the conditions for which, the approximated kernel Viab g r (K d ) converges to the actual kernel Viab f (K) as d and ρ go to zero:

lim d,ρ→0 Viab g r (K d ) = Viab f (K) (12)
The reader is referred to [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF] for more details on the convergence issue, as well as the proof of the result stated in (9).

Conservative Viability Algorithm

Despite the convergence results mentioned in §4, the fact remains that the viability kernel Viab g r (K d ) is only an approximation of the exact viability kernel Viab f (K). The main issue is that this approximation is not conservative, i.e. certain states will be labeled by Algorithm 1 as belonging to Viab g r (K d ) when, in truth, they do not belong to Viab f (K). The non conservative nature of Viab g r (K d ) is due to the various discretization assumptions, both in time and space, that have been made in order to obtain the finite and discrete dynamical system [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-ofviews in dynamic environments[END_REF].

To begin with, the time discretization of the continuous dynamical system (1) into (3) using an approximate method such as the Euler explicit scheme yields discrepancies between s(s 0 , u, ρ) and g(s 0 , u) for a starting state s 0 . Such discrepancies directly affects the resulting viability kernel. To avoid this issue, one must resort to an exact time discretization of the system whenever possible.

Then, because of the time discretization, it may happen that both s n and its successor s n+1 belong to K d , but the state trajectory in between leaves K (Fig. 2a). Addressing this issue is easy, it suffices to check whether the state trajectory between s n and s n+1 satisfies the viability constraints.

(a) sn and s n+1 are in K but the state trajectory in between is not.

(b) s n+1 = g(sn, u) is outside K but g r (sn, u) ∩ K d = ∅.
(c) The state trajectory is viable by the algorithm standards but discontinuous in practice. Finally, recall from §4.1, the introduction of the hyperball V(r) to adapt (3) to the finite grid S d . It yields two problems: the first one appears when a state s n has a successor state s n+1 = g(s n , u) that does not belong to K but is such that g r (s n , u) ∩ K d = ∅ (Fig. 2b). In this case, although s n is non viable, it will not be discarded by Algorithm 1. The second problem stems from the fact that a state s n does not have to reach another viable state s n+1 in order to classify as viable, it just has to get close to it. This results in discontinuous state trajectories that might be viable by the algorithm standards but that the actual system may not be able to follow in practice (Fig. 2c).

Algorithm 2: Conservative Viability Algorithm

Input: Exact discrete-time dynamical system g; State space lattice S d ; Discrete control space U d ;

Viability constraint set K Output: Conservative viability kernel Viabg(K d )

1 K d ← S d ∩ K; 2 n ← 0; 3 K 0 ← K d ; 4 repeat 5 K n+1 ← {s ∈ K n | ∃u ∈ U d (s) : g(s, u) ∈ K n and trajectory from s to g(s, u) ⊂ K} 6 n ← n + 1 7 until K n = K n+1 ; 8 return K n
From a viability point of view, it is critical to address these issues in order to obtain a conservative viability kernel Viab g r (K d ). To that end, it is first assumed that an exact time discretization of the system is available. Then, through an appropriate state space discretization, the need of the hyperball V(r) is relaxed: it is achieved by building a state space lattice based on the dynamical model of the system. A state space lattice is a prevalent structure in the field of robot motion planning [START_REF] Donald | Kinodynamic motion planning[END_REF][START_REF] Pancanti | Motion planning through symbols and lattices[END_REF][START_REF] Pivtoraiko | Differentially constrained mobile robot motion planning in state lattices[END_REF] and it consists of a graph whose vertices represent a regular sampling of the state space and whose edges correspond to a carefully crafted set of controls (the case study presented in §7 details how the state space lattice is built for a double integrator system). Now, when S d is a state space lattice, it is not necessary to extend g with V(r) since, by construction, ∀s ∈ S d , g(s, u) ∈ S d , and a conservative viability kernel Viab g (K d ) can actually be computed using Algorithm 2, a slightly modified version of Algorithm 1.

Time-Varying Viability Constraints

The viability constraint set K has been defined as the compact subset of the state space S within which the dynamical system must remain. What happens now when the viability constraints are time-dependent? It is the case for instance when viability is related to the collision avoidance of obstacles that are moving. In robotics, one way to deal with moving obstacles is to cast the problem into the state-time space framework [START_REF] Fraichard | Trajectory planning in a dynamic workspace: a state-time space approach[END_REF], i.e. to add time as an extra dimension to the state space. In this framework, the dynamical system (3) can be rewritten:

(s n+1 , τ n+1 ) = h((s n , τ n ), u n ) = (g(s n , u n ), τ n + ρ) u n ∈ U d ( 13
)
where τ denotes time. In the state-time framework, it becomes possible to consider timedependent viability constraints by defining K as the set of all the tuples (s, τ ) that satisfy the viability constraints. Adapting Algorithm 2 so that it operates in state-time is straightforward.

One problem remains though, K has to be compact (recall that Algorithm 2 relies upon this assumption to converge). Upper-bounding the time dimension by setting a time horizon T h allows to obtain a viability constraint set K which is compact. However, keeping in mind that a state is viable if it exists at least one sequence of controls that keeps the dynamical system in the viability constraint set indefinitely, it is obvious that, whatever the sequence of controls which is applied to the system from a given starting state-time, at some point in time, as soon as τ becomes greater than T h , the state-time (s, τ ) will leave K and the starting state-time will considered as nonviable. In this situation, Algorithm 2 would always return an empty set.

It is however possible to identify two classes of situations where the nature of the timedependent viability constraints are such that it becomes possible to circumvent the problem stated above and to actually compute the viability kernel using Algorithm 2. The two classes of situations are respectively called freezing and periodic, they are presented in the next two sections.

Freezing Case

In this class of situation, it is assumed that the viability constraints stop being time-dependent at a given time T f (imagine moving obstacles either leaving the environment or standing still after T f ). In other words, the following holds:

∀τ > T f : (s, τ ) = (s, T f ) (14)
In this case, the first step is to define the viability constraint set K as the set of all the tuples (s, τ ) for which s satisfies the viability constraints and τ ≤ T f , note that K is compact. The next step is to rewrite the dynamical system (13) as follows:

     (s n+1 , τ n+1 ) = h((s n , τ n ), u n ) = (g(s n , u n ), τ n + ρ) if τ n < T f (s n+1 , τ n+1 ) = h((s n , τ n ), u n ) = (g(s n , u n ), τ n ) if τ n ≥ T f u n ∈ U d (15)
Under [START_REF] Hsu | Randomized kinodynamic motion planning with moving obstacles[END_REF], it can be noted that, whatever the sequence of controls which is applied to the system from a given starting state-time, the time component of the state-time of the system will never be greater than T f . It therefore becomes possible to compute the viability kernel of K using Algorithm 2.

Periodic Case

In this class of situation, it is assumed that the time-dependence of the viability constraints is periodic with a period T p (imagine moving obstacles returning to their initial state and repeating the same motion over and over again). In other words, the following holds:

∀τ > T p : (s, τ ) = (s, τ mod T p ) (16)
In this case, the first step is once again to define the viability constraint set K as the set of all the tuples (s, τ ) for which s satisfies the viability constraints and τ ≤ T p . The next step is to rewrite the dynamical system (13) as follows:

(s n+1 , τ n+1 ) = h((s n , τ n ), u n ) = (g(s n , u n ), (τ n + ρ) mod T p ) u n ∈ U d (17)
Under [START_REF] Kalisiak | Faster motion planning using learned local viability models[END_REF], as in the freezing case, whatever the sequence of controls which is applied to the system from a given starting state-time, the time component of the state-time of the system will never be greater than T p , and it is possible to compute the viability kernel of K using Algorithm 2.

Robotic Case Studies

From this point on, the paper investigates how viability and the viability algorithm can be used in robotic scenarios. The robotic system at hand and the corresponding state space lattice that the viability algorithm requires are respectively presented in §7.1 and §7.2. Various robotic viability constraints are then detailed in §7.3. Finally, Section §8 presents the results obtained on a number of scenarios featuring different sets of robotic viability constraints.

Robot Model

Let A denote a robotic system operating in a workspace W. Henceforth, A denotes a 2D double integrator system whose acceleration a is directly controlled. A state s of A is represented by a tuple (p, v), where p is a 2D position, and v a Cartesian velocity. The motion of A is governed by:

ṗ = v v = a ( 18
)
with |v| ≤ v max and |u| ≤ a max . For a time step ρ, the following discrete state-transition equations are easily derived:

p n+1 = p n + vρ + 1 2 aρ 2 v n+1 = v n + aρ (19)
Eq. ( 19) is the exact discrete-time version of the dynamical system [START_REF] Korda | Convex computation of the maximum controlled invariant set for polynomial control systems[END_REF], the equivalent of (3), that the conservative version of the viability algorithm requires. It is assumed that the body of the robot is a disk.

As simple as this robot model may appear, keep in mind that it is a second-order acceleration-controlled system. In this respect, it is more realistic than the first-order velocitycontrolled systems that are sometimes used, e.g. the notorious "Dubins airplane" [START_REF] Chitsaz | Time-optimal paths for a Dubins airplane[END_REF][START_REF] Owen | Implementing dubins airplane paths on fixed-wing uavs[END_REF]. For a fully-actuated system such as [START_REF] Liniger | Real-time control for autonomous racing based on viability theory[END_REF], a state space lattice can be built according to the method described in [START_REF] Donald | Kinodynamic motion planning[END_REF] which is outlined as follows. Let the set of possible controls U d be restricted to {-a max , 0, a max }, and the time step ρ be chosen such that v max is a multiple of a max ρ. The term (u, ρ)-bang refers to applying a control u ∈ U d for a duration ρ. Let s 0 = (p 0 , v 0 ) denote the origin state, the state space lattice S d is the set of all states s i = (p i , v i ) reachable from s 0 by a sequence of (u, ρ)-bangs. It is straightforward to establish that:

State Space Lattice

p i = p 0 + 1 2 m i a max ρ 2 v i = v 0 + n i a max ρ (20)
where m i , n i ∈ N. Thus, S d is a regular grid which has a spacing of a max ρ 2 in position and a max ρ in velocity. Note that the grid positions p i for odd multiples of a max ρ are offset by 1 2 a max ρ 2 from the grid positions for even multiples of a max ρ (see Fig. 3 for a 1D system example). Note also that, in a space×time perspective, the lattice S d has a constant spacing ρ in the time dimension. This method can be applied to build a state-space lattice for arbitrary fully-actuated robotic systems. The case of under-actuated systems such as car-like vehicle is trickier to handle, however a number of solutions that could be used have been proposed, e.g. [START_REF] Mcnaughton | Motion planning for autonomous driving with a conformal spatiotemporal lattice[END_REF][START_REF] Pancanti | Motion planning through symbols and lattices[END_REF][START_REF] Pivtoraiko | Differentially constrained mobile robot motion planning in state lattices[END_REF][START_REF] Rufli | On the design of deformable input-/state-lattice graphs[END_REF][START_REF] Ziegler | Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios[END_REF]. As soon as the state-lattice had been defined, Algorithm 2 can be applied.

Robotic Viability Constraints

To demonstrate the versatility of Viability, various kinds of robotic-related viability constraints are considered. The first kind is standard collision avoidance ( §7.3.1). The second kind has to do with visibility, it becomes relevant as soon as the robotic system at hand is engaged in pursuit-evasion missions ( §7.3.2). The third and last kind arises when the robotic system is subject to certain restrictions on its velocity, e.g. an airplane robot whose speed is lower-bounded ( §7.3.3).

Collision Avoidance

Let us assume that W contains a set of b fixed and moving objects. Let B i denote such an object, B i (t) denotes the closed subset of W occupied by B i at time t. Likewise, B i ([t 1 , t 2 ]) denotes the space×time region occupied by B i during the time interval [t1, t2]. Note that

B i = B i ([0, ∞)).
Let B denote the union of the workspace objects (both in space and time):

B = b i=1 B i = b i=1 B i ([0, ∞)) = b i=1 t∈[0,∞) B i (t) (21)
In viability terms, the viability constraint set within which A must be kept is the set of states where A is not in collision with any of the workspace obstacles:

K c = {(s(t) ∈ S | A(s(t)) ∩ B(t) = ∅} ( 22
)
with A(s(t)) the closed subset of the workspace W occupied by A when it is in the state s(t).

Visibility

observer Fig. 4: Field of view (grey area) for an observer among obstacles (black areas).

Visibility constraints do arise for robotic systems engaged in pursuit-evasion missions. Such missions generally feature at least an observer and a target. The observer is equipped with sensors allowing it to obtain information about a limited region of W. The region of W that is known by the observer at a given state s(t) is called its field of view and is denoted FOV(s(t)) and its shape depends on the type of sensors available. The unknown regions of W are either out of the sensors' range or occluded (Fig. 4).

The robotic system A can either endorse the role of the observer or the target. When A is the observer, it should always maintain one or more workspace targets B t i within its field of view at all times. The corresponding viability constraint set can be defined in this case as:

K v = {s(t) ∈ S | i FOV(s(t)) ∩ B t i (t) = ∅} (23)
Now, when A is the target, it should always stay out of the field of view of one or more workspace observers B o i at all times. The corresponding viability constraint set can be defined in this case as:

K v = {s(t) ∈ S | i A(s(t)) ∩ FOV(B o i (t)) = ∅} (24)
Other variants could similarly be defined, e.g. the case where the robot target should always stay in the field of view of the workspace observers.

Velocity

Collision avoidance and visibility constraints impose restrictions on the configurations, i.e. positions and orientations, that the robotic system A can take. One could easily imagine situations where constraints are imposed on other components of the system's state, such as its velocity. An example of this would be if the system A is unstoppable, e.g. an airplane, or if W comprises regions with upper-bounded speed, e.g. the roadway. One could also imagine pursuit-evasion cases where an observer can only sense moving targets. In that case, standing still within the observer's field of view would be OK. All such constraints can readily be expressed via the definition of the corresponding viability constraint set.

In the end, no matter how different in nature the various constraints imposed on A are, they are expressed under the form of different viability constraint sets K i and can all be merged to form the final viability constraint set K that will feed Algorithm 2:

K = i K i (25)

Simulation Results

To demonstrate its versatility and its ability to address different kinds of viability problems, the conservative viability algorithm 2 has been implemented for the case of the double integrator system and tailored to handle different workspaces, i.e. static/freezing/periodic, and different viability constraints, i.e. collision avoidance/visibility/velocity. It led to the definition of seven scenarios with mixed combinations of workspace and viability constraint types. The seven scenarios are described below where details about the workspace and the viability constraints are given. For each scenario, Algorithm 2 has been used to compute the conservative and discrete viability kernel Viab g (K d ) and the corresponding regulation map R d . The computed regulation map R d then serves as a look-up table that indicates at each state the available controls that, when applied, will ensure that the system remains inside the viability kernel. A straightforward analysis of Algorithm 2 shows that its time complexity depends on the size of the discrete set of states and the discrete set of controls (line 5). In other words, it grows exponentially with the dimensions of the state and the control spaces. It is not really a problem since it should be kept in mind that the computation of Viab g (K d ) and R d is done off-line and only once for each scenario. In the current implementation (in Python on an average laptop), the running times for the different scenarios range from 6 to 20 minutes. To demonstrate the usefulness of the computed Viab g (K d ) and R d , they have been used within an efficient on-line navigation scheme that is able to drive the system A around its workspace W while always respecting the different viability constraints at hand. The navigation scheme is rather simple and purely reactive: starting from an arbitrary state belonging to the viability kernel Viab g (K d ), the navigation scheme selects, at each time step, the control to apply to A among the viable controls that are available at the current state. The set of viable controls is determined according to the regulation map R d . The choice of the control depends on the task at hand and could be chosen randomly or so as to minimize a given cost function C, e.g. distance to a goal. The control selection algorithm is outlined in Algorithm 3. It has been implemented using ROS1 and GAZEBO2 . For illustration purposes, three snapshots at different times of a typical simulation run3 are given. Each snapshot depicts the workspace (black regions are obstacles), the system's current position and the trail of its trajectory. The 2D slice of the viability kernel corresponding to the current velocity is overlaid on the workspace: the viability kernel is shown in green and its complement in red. In the pursuit/evasion scenarios, the grey areas corresponds to the states where the visibility constraints do not hold because of field of views. In all cases, the scenarios illustrate the ability of a purely reactive viability-based navigation scheme to control A forever without ever violating any of the viability constraints at hand.

Static Workspace

For this scenario, the workspace W contains static obstacles only (Fig. 5a). To emulate an airplane, the velocity of A is lower bounded: v > v min . Besides, the upper bound on A's acceleration |a| ≤ a max and the width of W's corridors are such that it prevents A from flying in circles at any given position in W. In this scenario, the viability constraints are collision avoidance and velocity. The snapshots of Fig. 6 illustrate a typical simulation run.

Freezing Workspace

For this scenario, the workspace W contains one static obstacle region and one moving obstacle that moves downward until it makes contact with the static obstacle, a behaviour resembling a trash compactor (Fig. 5b). The viability constraints are collision avoidance only. However, A has a goal now: it starts on the left side of the compactor and has to reach the right side. In this case, the choice of the control is not random anymore, the navigation scheme selects the control that will drive A closer to its goal. The snapshots of Fig. 7 illustrate a typical simulation run. This scenario is not as simple as it appears, it is similar to the one discussed in [START_REF] Fraichard | Iterative motion planning and safety issue[END_REF]. It is a case where the ICS-based approaches have a hard time finding the right set of evasive trajectories.

Periodic Workspace

Collision Avoidance

For this scenario, the workspace W contains both static and moving obstacles, it comprises two "rooms" and the only way to pass from one to the other is to use a revolving door (Fig. 5c). The revolving door has constant angular velocity and its behavior is periodic. The viability constraints are collision avoidance only. Now, A has a task to accomplish which is to repeatedly pass from one room to the other. To that end, two goal positions are respectively defined in both rooms: when the current goal is reached, the other goal becomes the current goal and so forth. The snapshots of Fig. 8 illustrate a typical simulation run.

Pursuit

For this scenario, the workspace W contains both static and moving obstacles. All moving obstacles are assumed to have a periodic behavior (Fig. 9a). The system A is equipped with an omni-directional sensor and its task now is to keep one of the moving obstacles, the target, within its field of view at all times while avoiding collisions of course. The viability constraints are collision avoidance and visibility. The snapshots of Fig. 10 illustrate a typical simulation run. In this case, the navigation scheme was set to select the control maximizing the distance to the target. For an extra challenge, an additional constraint in the form of a lower-bound on the system's velocity is considered, and the corresponding results are depicted in Fig. 11.

Evasion

For this scenario, the workspace W contains both static and moving obstacles. The moving obstacles have a periodic behavior, they are assumed to be sentinels on patrol duty, they are equipped with omni-directional sensors with a limited field of view (Fig. 9b). To make things more interesting, it is further assumed that the sensors can only detect moving objects. case where the velocity of A is lower-bounded has also been considered, the corresponding results are depicted in Fig. 13.

Discussion and Conclusion

Guaranteeing safe, i.e. collision-free, motion for robotic systems is usually tackled in the Inevitable Collision State (ICS) framework. This paper has explored the use of the Viability framework to address the more general problem of guaranteeing safe robot motion when it involves more than mere collision avoidance. It has first proposed the Conservative Viability Algorithm which is able to compute off-line the viability kernel and the regulation map for a robotic system. In a second stage, it has demonstrated, for seven very different scenarios, how to use the computed viability kernel and the regulation map within an on-line reactive navigation scheme that can drive the robotic system without ever violating the motion constraints at hand (collision avoidance, visibility, velocity). The algorithm proposed is conservative and can handle time-varying motion constraints such as moving obstacles. Although it is in general impossible to compute a non-empty viability kernel in the presence of moving obstacles, two classes of dynamic environments have been identified, freezing and periodic, for which it is possible to compute a valid viability kernel. Accordingly, it becomes possible to guarantee motion safety in the presence of moving obstacles for these two classes of environments. Although guaranteed collision avoidance has already been demonstrated for freezing environments using Inevitable Collision States, it is the first time that a similar result is achieved for periodic environments.

The Viability framework is definitely an interesting alternative to the ICS framework because of its ability to handle different motion constraints in a unified manner. However, this feature comes at the cost of a greater computational complexity that prevents the on-line computation of the viability kernel and the regulation map. Depending on the task at hand, this may or may not be an issue. Note however that a more efficient implementation of the algorithm proposed could be obtained through parallel computing [START_REF] Brias | Accelerating viability kernel computation with cuda architecture: application to bycatch fishery management[END_REF].

Besides the efficiency issue, future works include exploring how the Conservative Viability Algorithm whose formulation is general can handle alternative robotic systems. At a more fundamental level, further investigation into non-freezing and non-periodic environments should be carried out in order to determine whether viability can nonetheless be useful when it comes to guaranteed motion safety in arbitrary dynamic environments. science from University of California Riverside in 1987. He holds a PhD degree in electronics from the Badji Mokhtar University in 2006. His research interests include speech processing, DSP, micro-controller, microprocessor, robotics and human-machine interaction, and rehabilitation.

Fig. 2 :

 2 Fig. 2: Approximation Issues of the Viability Algorithm.

Fig. 3 :

 3 Fig. 3: State space lattice for a 1D double integrator.

Algorithm 3 :

 3 Safe Reactive NavigationInput: Current state s 0 ; Discrete regulation map R d ; Cost function C Output: Next control u * 1 u * ← argmin u∈R d (s 0 ) C(g(s 0 , u)); 2 return u *

  (a) Airplane scenario. (b) Compactor scenario. (c) Revolving door scenario.

Fig. 5 :

 5 Fig. 5: Test workspace scenarios (from left to right: static, freezing and periodic cases).

  (a) τ = 16, vx = 6, vy = 6. (b) τ = 39, vx = -6, vy = -6. (c) τ = 59, vx = 8, vy = 0.

Fig. 6 :

 6 Fig. 6: 2D viability kernel slices of the airplane scenario at different times.

(a) τ = 8 ,

 8 vx = 8, vy = -4. (b) τ = 14, vx = 8, vy = -6. (c) τ = 23, vx = 0, vy = 8.

Fig. 7 :

 7 Fig. 7: 2D viability kernel slices of the compactor scenario at different times.

Fig. 8 :

 8 Fig. 8: 2D viability kernel slices of the revolving door scenario at different times.

Fig. 9 :

 9 Fig. 9: Periodic workspace scenarios with visibility constraints.

Fig. 10 :

 10 Fig. 10: 2D viability kernel slices of the pursuit scenario at different times.

Fig. 11 :

 11 Fig. 11: 2D viability kernel slices of the unstoppable pursuit scenario at different times.

Fig. 12 :

 12 Fig. 12: 2D viability kernel slices of the evasion scenario at different times.

  (a) τ = 2, vx = 0, vy = 8. (b) τ = 17, vx = -8, vy = 8. (c) τ = 39, vx = 8, vy = -6.

Fig. 13 :

 13 Fig. 13: 2D viability kernel slices of the unstoppable evasion scenario at different times.

http://www.ros.org

http://gazebosim.org

Full videos available at http://thierry.fraichard.free.fr/research