# Time to Danger, an Alternative to Passive Safety for the Locomotion of a Biped Robot in a Crowd

Matteo Ciocca, Pierre-Brice Wieber, Thierry Fraichard

► To cite this version:

Matteo Ciocca, Pierre-Brice Wieber, Thierry Fraichard. Time to Danger, an Alternative to Passive Safety for the Locomotion of a Biped Robot in a Crowd. IROS 2023 - IEEE/RSJ International Conference on Intelligent Robots and Systems, Oct 2023, Detroit, United States. pp.1-7, 10.1109/IROS55552.2023.10342001. hal-04200354

HAL Id: hal-04200354

https://inria.hal.science/hal-04200354v1

Submitted on 8 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Time to Danger, an Alternative to Passive Safety for the Locomotion of a Biped Robot in a Crowd

Matteo Ciocca, Pierre-Brice Wieber and Thierry Fraichard

***Abstract***— A biped robot walking in a crowd must avoid falls and collisions at the same time. The latter is usually addressed through *Passive Safety* (PS), which guarantees that the robot is at rest when a collision is inevitable. Since PS may limit the robot's mobility, the purpose of this work is to introduce and explore the novel concept of *Time To Danger* (TTD) as an alternative. For a given robot motion, TTD is the time where the robot enters the region that a person can potentially occupy in the future. After having studied the properties of TTD, a novel locomotion strategy is proposed, which computes an optimal locomotion plan that guarantees balance preservation and TTD maximization, following a receding horizon Model Predictive Control scheme. Controlled experiments in a challenging simulated crowd scenario demonstrate how the novel locomotion strategy outperforms a Passive Safety-based locomotion strategy from a collision avoidance point of view.

## I. INTRODUCTION

For a biped robot moving in a crowd, there are two things that must be avoided: (a) to fall and (b) to collide with people. On the balance front (a), the concept of *capturability* and its instantiation in a capturable terminal constraint provides the guarantee that the robot will always be able to stop in a few footsteps and maintain its balance forever [1]. On the collision front (b), things are more complicated: the concept of *inevitable collision states* [2] shows that it is only with the complete knowledge of the surrounding environment of the robot and its future evolution that it is possible to guarantee *absolute safety*, i.e. no collision ever. In practice, such knowledge can only be obtained in specific cases such as static, freezing or periodic environments [3].

In dynamic and uncertain environments such as crowds, absolute safety is therefore impossible to guarantee [4]. One answer to this problem is to settle for a weaker safety level such as *Passive Safety* (PS), i.e. if a collision is inevitable, it is guaranteed that the robot will be at rest. PS has been studied in [5] and used on several robots [6], [7], [8]. It also corresponds to the emergency stop procedure required for personal care robots [9]. In crowds, PS is doubly interesting: (a) it allows provision of one form of safety guarantee and (b) if every person enforces it then no collision will take place at all [5]. Capturability and PS have been exploited in order to design a locomotion strategy for a biped robot moving in a crowd [10]. This strategy uses Model Predictive Control (MPC) and computes an optimal locomotion plan that guarantees both balance preservation and PS.

PS however has been doubly criticized: (a) it can unreasonably restrict the robot's mobility<fnref n="1" /> and (b) collisions can be caused by the robot if, for instance, it stops right in front of a moving agent and leaves it neither space nor time to react. To address the second criticism, *passive friendly safety* (PFS) has been suggested, i.e. if a collision is inevitable, it is guaranteed that the robot will be at rest and the moving agent will have enough space and time to avoid the collision if it wants to [7], [12]. By stopping the robot earlier and leaving more time for other moving agents to react, PFS reduces collisions but it further restricts the robot's mobility, which explains why PFS is little used.

The purpose of this paper is to explore an alternative to PS and PFS for the locomotion of a biped robot in a crowd with both balance preservation and collision avoidance in mind. The stance taken is to investigate whether maximizing the time that the robot has to replan its motion or that a person has to react can yield less collisions and therefore improve safety. To that end, the novel concept of *Time to Danger* (TTD) is introduced. For a future motion of the biped robot and a given person, TTD is the time where said motion enters the region where the person can potentially be in the future. From a collision point of view, this region is dangerous because the person is somewhere inside it hence the name TTD. Henceforth this region will be called *danger zone*.

The concept of *Time to Reach* a fixed target (TTR) was defined in [13], but TTR and TTD differ in that (a) TTD considers the time to reach danger zones which are time-varying, and (b) while TTR was minimized to help compute reachable sets, TTD is maximized to improve collision avoidance during navigation. TTD is also related to the concept of *Time to Collision* (TTC), introduced as a risk indicator in automated driving [14]. Originally, TTC was the time until impact between two vehicles having constant velocity, later generalized to arbitrary motions [15]. Note how TTD differs from the various *time to* X risk indicators used in automated driving, which correspond to the time left to perform action X in order to avoid a collision [16], [17], [18].

First, the properties of TTD are studied, it is shown that both PS and PFS limit TTD because the robot is constrained to stop before entering the danger zone. It is also shown that TTD can be increased if this constraint is lifted. Then, the paper seeks to establish that lifting this constraint and maximizing TTD will yield a locomotion strategy that does better from a collision avoidance point of view. To

<footnote>† This work has been supported by the French PERSYVAL LabEx (ANR-11-LABX-0025-01) and the EU COMANOID RIA (H2020-RIA-645097).</footnote>

<footnote>‡ Authors are with the Inria Centre at the University Grenoble Alpes.</footnote>

<footnote n="1">¹Yielding the freezing robot problem [11].</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. The dynamics of walking for a biped robot.</figcaption></figure>

that end, the locomotion strategy of [10], henceforth called MPC<sub>PS</sub>, is adapted in order to reach this new objective. It yields a novel locomotion strategy called MPC<sub>TTD</sub> that computes an optimal locomotion plan that guarantees both balance preservation and TTD maximization. Finally, MPC<sub>PS</sub> and MPC<sub>TTD</sub> are benchmarked in a challenging simulated crowd scenario, these controlled experiments demonstrate how MPC<sub>TTD</sub> outperforms MPC<sub>PS</sub>.

The paper is organized as follows: Section II describes the biped robot model and the walking constraints related to balance preservation and collision avoidance. Details about the crowd model used are given in Section III. Time to Danger is defined in Section IV and relevant properties are established. The principles of Model Predictive Control and Lexicographic Programming are summarized in Section V. The two locomotion strategies of interest MPC<sub>PS</sub> and MPC<sub>TTD</sub> are described in Section VI. The experimental results obtained are presented in Section VII and discussed in Section VIII.

## II. BIPED ROBOT MODEL

This section briefly formalizes the constraints for walking, balance preservation and collision avoidance. The dynamic model of the biped robot considered herein exploits the linear relationship between the horizontal motion of the Center of Mass (CoM) and the contact forces applied by the feet on a flat ground<sup>2</sup>. The reader is referred to [20], [21] for a full description of the model.

### A. Dynamics of Walking

The horizontal motion of the CoM $c \in \mathbb{R}^2$ of a biped robot is linearly related to the Center of Pressure (CoP) $p \in \mathbb{R}^2$ of the contact forces when walking with a constant height on a flat ground (see Fig. 1):

$$ \ddot{c} = \omega^2(c - p), \quad (1) $$

where $\omega^2 = g/h$, $h$ is the constant height of the CoM above the ground and $g$ is the norm of the gravity vector. The CoP must reside in the support polygon:

$$ p \in \mathcal{P}(s_j), \quad (2) $$

where $s_j \in \mathbb{R}^2$ is the position of the $j$th footstep on the ground. The CoM must also reside in a closed convex region due to the maximal leg length of the robot:

$$ c \in \mathcal{C}(s_j). \quad (3) $$

Biped robots should not cross their legs while walking. Given two consecutive footstep positions ($s_j, s_{j+1}$) and the region $S$ where the legs do not cross, the following constraints hold:

$$ s_{j+1} \in S(s_j). \quad (4) $$

The biped robot can realize a stable walk by continuously satisfying the walking constraints (2), (3) and (4) in their linearized form [22]:

$$ \text{Walking}(W) \equiv (2) \wedge (3) \wedge (4) \quad (W) $$

### B. Balance Preservation

Balance preservation is related to *capturability*, i.e. the ability of the biped robot to stop after a finite number of footsteps. A biped robot is said to be *0-step capturable* if it can stop and maintain balance indefinitely without having to make any extra footstep [1]. 0-step capturability is achieved by satisfying the following stopping constraint [23]:

$$ \text{Stop}(S) \equiv \dot{\xi} = 0 \quad (S) $$

where $\xi \in \mathbb{R}^2$ is the *capture point*, i.e. where the robot has to step in order to come to a stop, defined as:

$$ \xi = c + \omega^{-1}\dot{c}. \quad (5) $$

### C. Collision Avoidance

Collision between the biped robot and a person in the crowd is avoided if a minimal *separation distance* is enforced:

$$ \|c - z\| \ge \sigma_0, \quad (6) $$

with $z$ the person's position and $\sigma_0$ the separation distance. When both the robot and the person are modeled as disks of respective center $c$ and $z$, and radius $R_{\text{robot}}$ and $R_{\text{person}}$, this non-convex constraint is linearly approximated as follows:

$$ \text{Collision Avoidance (C)} \equiv d \ge \sigma_0 \quad (C) $$

where

$$ d = n^T(c - z). \quad (7) $$

$n \in \mathbb{R}^2$ is the unit normal vector that points from $z$ to $c$. In this case, $\sigma_0 = R_{\text{robot}} + R_{\text{person}}$.

<footnote n="2"><sup>2</sup>Walking on uneven ground could be tackled using similar linear techniques [19].</footnote>
### D. Walking Objectives

Finally, the biped robot can be asked to complete different objectives such as walk at a reference velocity $\dot{c}_{ref}$:

$$ \text{Objective } (O_s) \equiv \dot{c} - \dot{c}_{ref} = 0 \qquad (O_s) $$

or keep the CoP $p$ as close as possible to the center of the foot on the ground $s$ in order to improve the robustness of the robot against perturbations [24]:

$$ \text{Objective } (O_r) \equiv p - s = 0. \qquad (O_r) $$

## III. CROWD MODEL

Before placing a biped robot among real people, it is necessary to evaluate the performance of its locomotion strategy in simulation, which will depend on the simulated crowd behavior. A neutral approach to assess and compare different collision avoidance strategies in exactly the same conditions is to consider a crowd that doesn't react at all to the actual robot motion, a *blind crowd* where the robot is the only one that seeks to avoid collisions. It is further assumed that the robot walks in a direction opposite to the crowd, that people walk at constant velocity, and that collisions among people are disregarded.

It is realistic to assume that the robot can only perceive a subset of its environment, its field of view (FoV), whose shape is arbitrary and depends on the type of sensors used. For the sake of simplicity, occlusions in perception are disregarded, so the robot is aware of all the people present in FoV. Herein, FoV is a disk centered on the robot's CoM $c$ with a radius $R_{max}$ indicating the maximal distance around the robot at which it is capable of perceiving people.

Robot perception having a certain degree of uncertainty, the estimated position $\tilde{z}_i$ and velocity $\dot{\tilde{z}}_i$ of a person $\zeta$ measured by the sensors at time $t_i$ have associated errors with respect to the real position $z_i$ and velocity $\dot{z}_i$:

$$ \tilde{z}_i = z_i - \hat{z}_i, \quad \tilde{\tilde{z}}_i = \dot{z}_i - \hat{\dot{z}}_i. \qquad (8) $$

Given the magnitude of the uncertainty in position $||\tilde{z}_i||$, the real position $z_i$ lies in a circle of radius $||\tilde{z}_i||$ centered at the estimated position $\hat{z}_i$. Furthermore, given the magnitude of the uncertainty in velocity $||\dot{\tilde{z}}_i||$, the radius of this circle increases at a rate $||\dot{\tilde{z}}_i||t$ as it moves with the estimated velocity $\dot{\tilde{z}}_i$. The separation distance (see Section II-C) is modified accordingly to account for perception uncertainties:

$$ \sigma_0 = R_{\text{robot}} + R_{\text{person}} + ||\tilde{z}_i|| + ||\dot{\tilde{z}}_i|| t. \qquad (9) $$

Thus, at a future time $t$, the person $\zeta$ is somewhere inside an area $D_i^\zeta(t)$ that is called the *danger zone for the person $\zeta$* computed at time $t_i$, defined as:

$$ D_i^\zeta(t) \triangleq \text{ball}(\hat{z}_i + \dot{\hat{z}}_i t, R_{\text{person}} + ||\tilde{z}_i|| + ||\dot{\tilde{z}}_i|| t). \qquad (10) $$

**Assumption 1:** $D_i^\zeta(t)$ is a conservative model of the motion of the person $\zeta$, i.e. the set of states reachable by the person $\zeta$ is always included in $D_i^\zeta(t)$ for all future time $t$.

As a result, when updated position and velocity estimates $\hat{z}_{i+1}$ and $\dot{\hat{z}}_{i+1}$ are obtained from the robot's sensors for the

person $\zeta$ at time $t_{i+1}$, they can be taken into account to define a new, refined danger zone $D_{i+1}^\zeta$ which, following the above assumption, satisfies by construction the inclusion:

$$ D_{i+1}^\zeta(t) \subseteq D_i^\zeta(t). \qquad (11) $$

The danger zone for the whole crowd is a simple union:

$$ D_i(t) = \bigcup_{\zeta=1...Z} D_i^\zeta(t), \qquad (12) $$

where $Z$ is the size of the crowd. As a consequence of (11), the following inclusion holds:

$$ D_{i+1}(t) \subseteq D_i(t). \qquad (13) $$

## IV. TIME TO DANGER

Let $\mathcal{R}^\pi(t)$ denote the area occupied by the robot at time $t$ when following a motion plan $\pi \in \Pi$, where $\Pi$ is the set of all possible motions of finite duration starting from the current state of the robot. Time to Danger (TTD) is defined as follows:

**Definition 1 (Time to Danger):** Assuming that the robot starts outside of the danger zone $D(t)$ and follows a motion plan $\pi$, the time when it enters $D(t)$ is:

$$ T^d(\pi) \triangleq \{t^* | \mathcal{R}^\pi(t^*) \cap D(t^*) \neq \emptyset, \forall t < t^*, \mathcal{R}^\pi(t) \cap D(t) = \emptyset\}. \qquad (14) $$

Pushing this Time to Danger as far away in the future as possible, i.e. maximizing $T^d(\pi)$, would provide as much time as possible for the robot to explore options for avoiding or at least reducing the risk related to possible collisions. This could be a control objective worth exploring.

### A. TTD's Basic Lemma

The following lemma establishes that $T^d(\pi)$ do not decrease with time.

**Lemma 1:** Assuming that the robot is outside of the danger zone at time $t_i$, then:

$$ T_{i+1}^d(\pi) \geq T_i^d(\pi), \qquad (15) $$

where $T_i^d(\pi)$ denotes the TTD computed at time $t_i$.

*Proof:* Assume that at time $t$,

$$ \mathcal{R}^\pi(t) \cap D_i(t) = \emptyset. \qquad (16) $$

It derives from (13) that:

$$ \mathcal{R}^\pi(t) \cap D_{i+1}(t) \subseteq \mathcal{R}^\pi(t) \cap D_i(t) = \emptyset. \qquad (17) $$

From Definition 1, it is straightforward to conclude that:

$$ T_{i+1}^d(\pi) \geq T_i^d(\pi). $$

<figure><img src="image_3.png" /></figure>
<figure><img src="image_4.png" /><figcaption>Fig. 2. A simulated 1D scenario where a robot starting from coordinate 0.5 walks away from a person starting from coordinate 1 and moving towards coordinate 0: lifting the PFS or PS constraints allows pushing TTD further back into the future.</figcaption></figure>

## B. TTD and Passive (Friendly) Safety

PS is achieved by imposing that the robot stops before entering the danger zone and stays put thereafter:

$$ \forall t \ge T^d(\pi), \mathcal{R}^\pi(t) = \mathcal{R}^\pi(T^d(\pi)). \quad (18) $$

The set of robot motions that guarantee PS is therefore:

$$ \Pi^{\text{PS}} \triangleq \{\pi \in \Pi \mid \forall t \ge T^d(\pi), \mathcal{R}^\pi(t) = \mathcal{R}^\pi(T^d(\pi))\}, \quad (19) $$

which is by construction a subset of all motions, $\Pi^{\text{PS}} \subseteq \Pi$.

PFS is achieved by imposing additionally that the robot stops and stays put a given duration $T^s \ge 0$ before entering the danger zone<fnref n="3" />:

$$ \forall t \ge T^d(\pi) - T^s, \mathcal{R}^\pi(t) = \mathcal{R}^\pi(T^d(\pi) - T^s). \quad (20) $$

The set of robot motions that guarantee PFS is therefore:

$$ \Pi_{T^s}^{\text{PFS}} \triangleq \{ \pi \in \Pi \mid \forall t \ge T^d(\pi) - T^s, \\ \qquad \mathcal{R}^\pi(t) = \mathcal{R}^\pi(T^d(\pi) - T^s) \}. \quad (21) $$

The following set inclusions are a direct consequence of these definitions:

$$ \Pi_{T^s}^{\text{PFS}} \subseteq \Pi^{\text{PS}} \subseteq \Pi, \quad (22) $$

from which we can immediately deduce that:

$$ \max_{\pi \in \Pi_{T^s}^{\text{PFS}}} T^d(\pi) \le \max_{\pi \in \Pi^{\text{PS}}} T^d(\pi) \le \max_{\pi \in \Pi} T^d(\pi). \quad (23) $$

By constraining the choice of robot motions, PFS and PS result in earlier TTD, providing less time for the robot to explore options for avoiding or at least reducing the risk related to possible collisions. This is illustrated in Fig. 2 where a robot walks away from a person in a simulated 1D scenario: lifting the PFS or PS constraints allows pushing TTD further back into the future.

# V. LEXICOGRAPHIC MODEL PREDICTIVE CONTROL

Lemma 1 shows that $T^d(\pi)$ doesn't decrease with time when the robot follows a fixed motion plan $\pi$ and may actually increase, indicating that the robot would have even more time available to explore options for avoiding or at least reducing the risk related to possible collisions. A simple way to explore such options is to simply look for a potentially better motion plan. The robot could repeatedly re-evaluate its motion plan to actively maximize $T^d(\pi)$, depending on the current situation, following a standard *receding horizon* Model Predictive Control (MPC) strategy.

MPC happens to be widely used for biped locomotion since [25]. Classically, time is discretized in a sequence of time instants $t_i, i \in \mathbb{N}$, where each time interval $[t_i, t_{i+1}]$ has a fixed duration $T$. At each time $t_i$, given the current state $\mathbf{x}_i = (\hat{c}_i, s_i)$ of the robot, where $\hat{c}_i = (c_i, \dot{c}_i, \ddot{c}_i)$ and $s_i$ is the current foot position on the ground, an optimization problem is solved to plan a motion, i.e. a sequence of $N$ control actions $\pi_i = \{u_i, u_{i+1}, \dots, u_{i+N-1}\}$, where $N$ is the *planning horizon*. Following a receding horizon strategy, the first control action $u_i$ is executed and at time $t_{i+1}$, the whole motion planning process is repeated. In our case, $\pi_i$ is a sequence of CoP velocities $\dot{\mathbf{p}}$ and foot positions $\mathbf{s}_j$. Further details can be found in [21].

The different constraints presented in Section II might conflict with one another, e.g. following a reference speed might cause a collision. In such cases, at least one of them must be *relaxed*. To that end, the constraints are expressed as a set of linear inequalities:

$$ E \begin{bmatrix} \mathbf{x} \\ \pi \end{bmatrix} \le d, \quad (24) $$

where $E$ and $d$ are respectively a time-varying matrix and a vector of proper dimensions. Relaxation is then achieved by introducing a possible *violation* $\mathbf{w}$:

$$ E \begin{bmatrix} \mathbf{x} \\ \pi \end{bmatrix} - \mathbf{w} \le d, \quad (25) $$

and minimizing $\|\mathbf{w}\|^2$. Note that all the constraints are satisfied when $\|\mathbf{w}\| = 0$. Constraints can also be hierarchically arranged in *priority levels*, according to their relative importance, and their violations be minimized accordingly, i.e. as a lexicographic least squares problem. By defining $P$ priority levels, the problem can be reformulated as a Lexicographic Program (LexP) [26]:

$$ \text{lex minimize} \quad \{\|\mathbf{w}_1\|^2, \dots, \|\mathbf{w}_P\|^2\} \quad (26a) $$

$$ \text{s.t.} \quad \begin{bmatrix} E_1 \\ \vdots \\ E_P \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \pi \end{bmatrix} - \begin{bmatrix} \mathbf{w}_1 \\ \vdots \\ \mathbf{w}_P \end{bmatrix} \le \begin{bmatrix} d_1 \\ \vdots \\ d_P \end{bmatrix}, \quad (26b) $$

and solved using a fast online LexP solver [27]. This technique has already been used effectively for the control of all kinds of robots, humanoid [28], industrial [29] and self-driving vehicles [30].

<footnote n="3">³See [12] for an example of how $T_s$ can be chosen.</footnote>
# VI. MPC<sub>PS</sub> AND MPC<sub>TTD</sub>

## A. MPC<sub>PS</sub>: Lexicographic Approach to Passive Safety

### Hierarchy 1: Balance and Passive Safety

1. Feasible and Capturable Collision-free Motion: (*W*), (*C*), and (*S*) only at *t*<sub>*i*</sub>+*N*</sub>

2. Min. reference deviation: (*O*<sub>s</sub>) and (*O*<sub>r</sub>)

MPC<sub>PS</sub> is a lexicographic MPC-based locomotion strategy that both guarantees balance preservation and PS for a biped robot [10]. It computes an optimal locomotion plan over a receding horizon, from *t*<sub>*i*</sub> to *t*<sub>*i+N*</sub>, where dynamic feasibility and collision avoidance (with the danger zone *D*) constraints (*W*) and (*C*) must be satisfied at all time while the stopping constraint (*S*) must be satisfied at the end of the horizon *t*<sub>*i+N*</sub> in order to guarantee both balance preservation and PS.

All these constraints are mandatory for the safety of both the robot and the crowd. They are assigned therefore the highest priority level in *Hierarchy 1*. The objectives (*O*<sub>s</sub>) and (*O*<sub>r</sub>) are less important, and assigned therefore a lower priority level, so they will be satisfied only within the constraints of priority level 1.

The solution to this lexicographic problem provides the robot with a dynamically feasible and capturable collision-free motion that stops at time *t*<sub>*i+N*</sub>. At the next time instant *t*<sub>*i+1*</sub>, a new feasible and capturable collision-free motion can be computed again from *t*<sub>*i+1*</sub> to *t*<sub>*i+N+1*</sub>, following a receding horizon MPC strategy. If such a motion is not available, the robot can simply follow the motion already computed from *t*<sub>*i*</sub> to *t*<sub>*i+N*</sub> and stop safely before any collision occurs: capturability and PS are guaranteed.

## B. MPC<sub>TTD</sub>: Lexicographic Approach to TTD Maximization

### Hierarchy 2: Balance and TTD Maximization

1. Feasible and Capturable Motion: (*W*), and (*S*) only at *t*<sub>*i+N*</sub>

2. Collision-free (*C*) only at *t*<sub>*i+1*</sub>

N: Collision-free (*C*) only at *t*<sub>*i+N−1*</sub>

N+1: Collision-free (*C*) only at *t*<sub>*i+N*</sub>

N+2: Min. reference deviation: (*O*<sub>s</sub>) and (*O*<sub>r</sub>)

Following the analysis of Section IV-B, MPC<sub>TTD</sub> is a modification of MPC<sub>PS</sub> that drops the PS guarantee in favor of maximizing TTD. In order to guarantee balance preservation, the dynamic feasibility constraints (*W*) must be satisfied at all time while the stopping constraint (*S*) must be satisfied at the end of the horizon *t*<sub>*i+N*</sub>. These constraints are therefore maintained at the highest priority level in *Hierarchy 2*.

Time: 0s

<figure><img src="image_5.png" /><figcaption>Fig. 3. A typical initial configuration for the crowd scenarios used to evaluate MPC<sub>PS</sub> and MPC<sub>TTD</sub>: the robot starts walking from the left, with a limited field of view, in an opposite direction to the crowd that starts walking from the right. Here, the crowd size is *Z* = 16.</figcaption></figure>

Maximizing TTD means avoiding collisions with the danger zone *D* for as long as possible. This is realized by considering the constraint (*C*) sequentially in time from *t*<sub>*i+1*</sub> to *t*<sub>*i+N*</sub> through as many descending priority levels, 2 to *N* + 1. As in MPC<sub>PS</sub>, the objectives (*O*<sub>s</sub>) and (*O*<sub>r</sub>) are less important, and assigned therefore a lower priority level, so they will be satisfied only within the constraints of higher priority levels.

The solution to this lexicographic problem provides the robot with a dynamically feasible and capturable motion where collision avoidance with the danger zone *D* is satisfied for as long as possible in order to maximize TTD, but without guaranteeing PS.

# VII. EVALUATION OF MPC<sub>PS</sub> AND MPC<sub>TTD</sub>

## A. Robot and Crowd Parameters

The performance of MPC<sub>PS</sub> and MPC<sub>TTD</sub> are evaluated on simulated blind crowd scenarios using the robot model presented in Section II and the crowd model detailed in Section III. The parameters of the biped robot are those of the HRP-2 robot [31], with *R*<sub>robot</sub> = 0.5 m, a field of view radius of 4 m and a reference velocity [0.5, 0] m/s. Simulated crowds are composed of *Z* = 8, 16, 24 or 32 persons with *R*<sub>person</sub> = 0.5 m. People are randomly positioned over an area of 10 × 8 m² in front of the robot, outside of its FoV (see Fig. 3). Their velocity along *x* is −0.5 m/s and their velocity along *y* is picked randomly in [−0.2, 0.2] m/s. Perception uncertainties are ||*z̃*|| = 0, 0.15 or 0.30 m and ||*z̃̇*|| = 0, 0.05 or 0.10 m/s. For each combination of *Z*, ||*z̃*|| and ||*z̃̇*||, 100 crowds are randomly generated, yielding a total of 3600 sample crowds, used to evaluate both MPC<sub>PS</sub> and MPC<sub>TTD</sub> with *N* = 16 and *T* = 1 s. For each sample crowd, the simulation runs for a maximum of 20 s and stops as soon as a collision occurs.
<figure><img src="image_6.png" /><figcaption>Fig. 4. Cumulative collision count along simulation time as a percentage of all 3600 simulations for both MPC<sub>PS</sub> and MPC<sub>TTD</sub> strategies.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 5. Cumulative collision count along relative collision velocity as a percentage of all 3600 simulations for both MPC<sub>PS</sub> and MPC<sub>TTD</sub> strategies.</figcaption></figure>

## B. Simulation Results

The performance criteria considered to evaluate MPC<sub>PS</sub> and MPC<sub>TTD</sub> strategies are (a) the collision count, (b) the collision time, and (c) the relative collision velocity.

1) *Collision Count and Collision Time:* to assess these two criteria, Fig. 4 represents a cumulative collision count as a percentage of all 3600 simulations for both MPC<sub>PS</sub> and MPC<sub>TTD</sub> along simulation time (there were no collisions within the first 5 s). As expected, collisions are delayed when maximizing TTD: the MPC<sub>TTD</sub> curve looks similar to the MPC<sub>PS</sub> curve but shifted to the right, later in time.

A more interesting benefit of MPC<sub>TTD</sub> with respect to MPC<sub>PS</sub> is an 8% reduction in the total number of collisions, which is statistically significant: by the end of the simulation time the MPC<sub>TTD</sub> curve is lower than the MPC<sub>PS</sub> curve, a clear demonstration that the receding horizon MPC strategy takes advantage of the available time before collision to actively reduce the risk of collisions, and a clear proof that maximizing TTD is, indeed, an attractive control objective. In summary, MPC<sub>TTD</sub> outperforms MPC<sub>PS</sub> in terms of both collision count and collision time: less collisions happen, and later.

2) *Relative Collision Velocity:* the kinetic energy transferred to a person can be used as a measure for the risk of injuries [32], and it is directly related to the relative collision velocity. To assess this risk of injuries, Fig. 5 represents a cumulative collision count as a percentage for all 3600 simulations for both MPC<sub>PS</sub> and MPC<sub>TTD</sub> along the magnitude of the relative collision velocity.

With the MPC<sub>PS</sub> strategy, the relative collision velocity is (almost) never larger than the people's own velocity, as expected since PS guarantees that the robot has no velocity at the time of collision. A few small exceptions are observed, however, which correspond to the fact that even with fixed feet on the ground, the robot can have some small residual CoM motion.

By lifting the PS constraint, the MPC<sub>TTD</sub> strategy opens

the possibility for larger relative collision velocities (and therefore larger risk of injuries for people), which are clearly observed here with the MPC<sub>TTD</sub> curve reaching much further to the right than the MPC<sub>PS</sub> curve. This is clearly a negative aspect of this strategy, but this may be an artifact of the blind crowd assumption. In the real world, people would be aware of the robot and it is reasonable to assume that they would seek to actively contribute to collision avoidance. In this respect, MPC<sub>TTD</sub> would provide more time for people to evaluate the risk of collision and act accordingly, as shown above. But to evaluate this behavior, we would need a reactive, *non-blind crowd* model.

On the other side of the plot, on the left, at lower velocities, the MPC<sub>TTD</sub> curve is above the MPC<sub>PS</sub> curve, indicating more occurrences: more than half of the collisions with the MPC<sub>TTD</sub> strategy actually occur with smaller relative collision velocities than with the MPC<sub>PS</sub> strategy. This is due to the fact that maximizing TTD can drive the robot to walk away from people, hence reducing the relative collision velocity. In summary, the benefits of either approaches with respect to relative collision velocity are inconclusive in this blind crowd scenario.

## VIII. DISCUSSION AND CONCLUSION

The MPC<sub>TTD</sub> strategy, which maximizes the Time To Danger, yields fewer collisions, which happen later in time, than the MPC<sub>PS</sub> strategy, which enforces Passive Safety. This result validates both the interest of the notion of Time To Danger as a new tool to address motion safety in dynamic environments, and the capacity of the MPC<sub>TTD</sub> strategy to leverage this notion for improved safety. It comes, however, at a cost: some of the remaining collisions exhibit a much larger relative collision velocity, which is directly related to the risk of injuries for the surrounding crowd. This marks a clear direction of improvement concerning the notion of Time To Danger, to curb in some way the occurrence of collisions with large relative collision velocity. This result
was obtained, however, in the worst possible scenario, with humans that are oblivious to the robot and make no effort in trying to avoid collisions. In the real world, people would be aware of the robot and it is reasonable to assume that they would seek to actively contribute to collision avoidance. In this respect, MPC<sub>TTD</sub> would provide more time for people to evaluate the risk of collision and act accordingly. This needs to be evaluated more carefully with a reactive, non-blind crowd model.

## REFERENCES

[1] T. Koolen, T. De Boer, J. Rebula, A. Goswami, and J. Pratt, “Capturability-based analysis and control of legged locomotion, part 1: Theory and application to three simple gait models,” *The Int. Journal of Robotics Research*, vol. 31, no. 9, pp. 1094–1113, 2012.

[2] T. Fraichard and H. Asama, “Inevitable collision states, a step towards safer robots?” in *IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)*, Oct. 2003.

[3] M. Bouguerra, T. Fraichard, and M. Fezari, “Viability-Based Guaranteed Safe Robot Navigation,” *Journal of Intelligent and Robotic Systems*, vol. 95, no. 2, pp. 459–471, Aug. 2019.

[4] T. Fraichard, “Will the Driver Seat Ever Be Empty?” INRIA, Research Report RR-8493, Mar. 2014. [Online]. Available: https://hal.inria.fr/hal-00965176

[5] S. Bouraine, T. Fraichard, and H. Salhi, “Provably Safe Navigation for Mobile Robots with Limited Field-of-Views in Dynamic Environments,” *Autonomous Robots*, vol. 32, no. 3, pp. 267–283, Apr. 2012.

[6] M. Morisawa, S. Kajita, K. Harada, K. Fujiwara, F. Kanehiro, K. Kaneko, and H. Hirukawa, “Emergency stop algorithm for walking humanoid robots,” in *IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)*, Aug. 2005.

[7] K. Macek, D. Vasquez, T. Fraichard, and R. Siegwart, “Safe vehicle navigation in dynamic urban scenarios,” in *IEEE Int. Conf. on Intelligent Transportation Systems (ITS)*, Oct. 2008.

[8] S. Choudhury, S. Arora, and S. Scherer, “The planner ensemble and trajectory executive: A high performance motion planning system with guaranteed safety,” in *American Helicopter Society Annual Forum*, May 2014.

[9] Int. Organization for Standardization (ISO), “Robots and Robotic Devices - Safety Requirements for Personal Care Robots,” 2014, ISO 13482:2014.

[10] N. Bohorquez, “Design of safe control laws for the locomotion of biped robots,” PhD, Université Grenoble Alpes, Dec. 2018. [Online]. Available: https://tel.archives-ouvertes.fr/tel-02143977

[11] P. Trautman and A. Krause, “Unfreezing the robot: Navigation in dense, interacting crowds,” in *IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)*, Oct. 2010.

[12] S. Mitsch, K. Ghorbal, D. Vogelbacher, and A. Platzer, “Formal verification of obstacle avoidance and navigation of ground robots,” *The Int. Journal of Robotics Research*, vol. 36, no. 12, pp. 1312–1340, 2017.

[13] I. M. Mitchell, “Application of level set methods to control and reachability problems in continuous and hybrid systems,” PhD, Stanford Univ. Aug. 2002.

[14] J. Hayward, “Near misses as a measure of safety at urban intersections,” PhD, Pennsylvania State University, 1971.

[15] ——, “Near-miss determination through use of a scale of danger,” Pennsylvania Transportation and Traffic Safety Center,” Tech. Report, 1972.

[16] S. Lefèvre, D. Vasquez, and C. Laugier, “A survey on motion prediction and risk assessment for intelligent vehicles,” *ROBOMECH Journal*, vol. 1, no. 1, pp. 1–14, 2014.

[17] S. Sontges, M. Koschi, and M. Althoff, “Worst-case analysis of the time-to-react using reachable sets,” in *IEEE Intelligent Vehicles Symp. (IV)*, June 2018.

[18] S. Wagner, K. Groh, T. Kuhbeck, M. Dorfel, and A. Knoll, “Using time-to-react based on naturalistic traffic object behavior for scenario-based risk assessment of automated driving,” in *IEEE Intelligent Vehicles Symp. (IV)*, June 2018.

[19] C. Brasseur, A. Sherikov, C. Collette, D. Dimitrov, and P.-B. Bieber, “A robust linear mpc approach to online generation of 3d biped walking motion,” in *IEEE Int. Conf. on Humanoid Robots (Humanoids)*, Nov. 2015.

[20] P.-B. Bieber, R. Tedrake, and S. Kuindersma, “Modeling and control of legged robots,” in *Springer Handbook of Robotics*, B. Siciliano and O. Khatib, Eds., 2016, pp. 1203–1234.

[21] M. Ciocca, “Balance Preservation and Collision Mitigation for Biped Robots,” PhD, Université Grenoble Alpes, May 2020. [Online]. Available: https://tel.archives-ouvertes.fr/tel-01335571

[22] A. Herdt, H. Diedam, P.-B. Bieber, D. Dimitrov, K. Mombaur, and M. Diehl, “Online Walking Motion Generation with Automatic Foot Step Placement,” *Advanced Robotics*, vol. 24, no. 5-6, pp. 719–737, 2010.

[23] A. Sherikov, “Balance preservation and task prioritization in whole body motion control of humanoid robots,” PhD, Université Grenoble Alpes, May 2016.

[24] P.-B. Bieber, “Trajectory free linear model predictive control for stable walking in the presence of strong perturbations,” in *IEEE Int. Conf. on Humanoid Robots (HUMANOIDS)*, Dec. 2006.

[25] S. Kajita, F. Kanehiro, K. Kaneko, K. Fujiwara, K. Harada, K. Yokoi, and H. Hirukawa, “Biped walking pattern generation by using preview control of zero-moment point,” in *IEEE Int. Conf. on Robotics and Automation (ICRA)*, Sep. 2003.

[26] A. Escande, N. Mansard, and P.-B. Bieber, “Hierarchical quadratic programming: Fast online humanoid-robot motion generation,” *The Int. Jml of Robotics Research (IJRR)*, vol. 33, no. 7, pp. 1006–1028, 2014.

[27] D. Dimitrov, A. Sherikov, and P.-B. Bieber, “Efficient resolution of potentially conflicting linear constraints in robotics,” INRIA, Research Report hal-01183003, Aug. 2015. [Online]. Available: https://hal.inria.fr/hal-01183003

[28] A. Sherikov, D. Dimitrov, and P.-B. Bieber, “Balancing a humanoid robot with a prioritized contact force distribution,” in *IEEE Int. Conf. on Humanoid Robots (HUMANOIDS)*, Nov. 2015.

[29] S. Al Homsi, A. Sherikov, D. Dimitrov, and P.-B. Bieber, “A hierarchical approach to minimum-time control of industrial robots,” in *IEEE Int. Conf. on Robotics and Automation (ICRA)*, May 2016.

[30] A. Blumentals and P.-B. Bieber, “An MPC Approach to Safe Trajectory Generation for an Autonomous Bus,” INRIA, Research Report, 2017.

[31] K. Kaneko, F. Kanehiro, S. Kajita, H. Hirukawa, T. Kawasaki, M. Hirata, K. Akachi, and T. Isozumi, “Humanoid robot HRP-2,” in *IEEE Int. Conf. on Robotics and Automation (ICRA)*, April 2004.

[32] Int. Organization for Standardization (ISO), “Robots and Robotic Devices - Collaborative Robots,” 2016, ISO/TS 15066:2016.