Maxime Sainte

Eric Lucet

A modified Hybrid Reciprocal Velocity Obstacles approach for multi-robot motion planning without communication

Ensuring a safe online motion planning despite a large number of moving agents is the problem addressed in this paper. Collision avoidance is achieved without communication between the agents and without global localization system. The proposed solution is a modification of the Hybrid Reciprocal Velocity Obstacles (HRVO) combined with a tracking error estimation, in order to adapt the Velocity Obstacle paradigm to agents with kinodynamic constraints and unreliable velocity estimates. This solution, evaluated in simulation and in real test scenario with three dynamic unicycle type robots, shows an improvement over HRVO.

I. INTRODUCTION

Most of the autonomous guided vehicles (AGV) use guides such as tapes or magnets but it is not the only method as Amazon Robotics, Cimcorp and Seegrid introduced AGVs that were not restrained by guides. Those solutions, adopted by Amazon for example [START_REF] Rolfsen | Amazon's growing robot army keeps warehouses humming[END_REF] aim at improving productivity by integrating unmanned distribution activities in the warehouse management system.

In order to allow these robots to navigate freely, a feasible motion must be produced. Several constraints need to be taken into account such as kinematics, dynamics and obstacle avoidance. Moreover, in a shared workspace, the robot motion planning must take into consideration other robots which are active agents.

Motion planning approaches can be classified in two categories. Reactive approaches, such as the Dynamic Window Approach (DWA) [START_REF] Fox | The dynamic window approach to collision avoidance[END_REF], consider the best motion that can be chosen at a certain time instant. On the other hand, trajectory planning method, such as Timed-Elastic-Bands (TEB) [START_REF] Roesmann | Trajectory modification considering dynamic constraints of autonomous robots[END_REF], plan the motion over a certain horizon of time. This category tends to produce smoother resulting trajectory and give results closer to optimality. For multi-robot motion planning, many trajectory generation approaches are centralized and use optimization [START_REF] Panda | An improved gravitational search algorithm and its performance analysis for multirobot path planning[END_REF], [START_REF] Augugliaro | Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach[END_REF], [START_REF] Mellinger | Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams[END_REF]. However, the robustness relies on the central intelligence and on the communication between this intelligence and the robots. Furthermore, centralized approach suffer from scaling, as increasing the number of robots increases the computational load on the central computer.

Decentralized approaches such as the Receding Horizon Planning [START_REF] Filho | Multi-robot motion planning: A modified receding horizon approach for reaching goal states[END_REF] or the Decentralized Multi-Agent Rapidlyexploring Random Tree (DMA-RRT) [START_REF] Desaraju | Decentralized path planning for multi-agent teams in complex environments using rapidly-exploring random trees[END_REF] allow to generate a trajectory for multiple agents but rely on communication as estimating the trajectory of another active agent is a complex task.

a CEA, LIST, Interactive Robotics Laboratory, Gif-sur-Yvette, F-91191,France * corresponding author: eric.lucet@cea.fr Reactive methods, while resulting in less smooth trajectories, offer the advantage of only requiring the current state of the other agents implying that they can be achieved using only sensing and no communication. The Velocity Obstacles (VO) approach [START_REF] Fiorini | Motion planning in dynamic environments using velocity obstacles[END_REF] allows reactive local collision avoidance. Knowing the relative positions and velocities of moving obstacles, a set of forbidden velocities is created. Choosing a velocity oustide of those forbidden velocities leads to an avoidance of moving obstacles. This approach has been expanded to take into account uncertainty in the position and velocity of obstacles, Uncertainty-aware Velocity Obstacles (UVO), and has been combined with a global planner, Rapidly-exploring Random Belief Tree (RRBT) [START_REF] Yang | Anytime rrbt for handling uncertainty and dynamic objects[END_REF]. However, active agents also participate in the collision avoidance process. This aspect, overlooked by the VO approach, results in oscillations. Those oscillations are partly removed by Reciprocal Velocity Obstacles (RVO) [START_REF] Van Den Berg | Reciprocal velocity obstacles for real-time multi-agent navigation[END_REF] and further reduced by Hybrid Reciprocal Velocity Obstacles (HRVO) [START_REF] Snape | The hybrid reciprocal velocity obstacle[END_REF] that indroduce an implicit choice on which side an agent should pass. RVO was turned into a probabilistic approach [START_REF] Gopalakrishnan | Prvo: Probabilistic reciprocal velocity obstacle for multi robot navigation under uncertainty[END_REF] which is an effective means of dealing with uncertainty in position, velocity and actuation compared to bounding approaches [START_REF] Claes | Collision avoidance under bounded localization uncertainty[END_REF].

Once the VOs, RVOs or HRVOs are built, a speed must be chosen and applied to the agent. To this end, a solution is Clearpath [START_REF] Guy | Clearpath: highly parallel collision avoidance for multiagent simulation[END_REF]. This algorithm finds an admissible speed that is the closest to the preferred one for the agent. To do so, it classifies the intersection points of the VOs as inside or outside of the VOs and extracts the segments that are outside of the VOs. It then returns the point from the outside segments that is the closest to the preferred velocity. Another solution to select an admissible speed is to sample the velocity space [START_REF] Claes | Multi robot collision avoidance in a shared workspace[END_REF] and score the samples.

Optimal Reciprocal Collision Avoidance (ORCA) is both a VO formulation and a speed choice method. VOs are turned into half planes reducing the problem of finding the velocity the closest to the preferred one to a linear program.

The study performed by J. A. Douthwaite et al. [START_REF] Douthwaite | A comparative study of velocity obstacle approaches for multi-agent systems[END_REF] compares the different VO formulations and concludes ORCA performs the best in an ideal setting but is outperformed by HRVO in the presence of sensor noise.

In the following, the required VO principles are first briefly introduced. Based on them, the proposed method is then developed and evaluated in simulation and real test scenarios. The velocity obstacle approach [START_REF] Fiorini | Motion planning in dynamic environments using velocity obstacles[END_REF] allows a local reactive collision avoidance of moving obstacles.

Considering two moving agents in a two dimensional space represented in Fig. 1(a), with Agent A defined by its velocity -→ v A and footprint A and B by -→ v B and B, the definition of a velocity obstacle is:

V O A|B = - → v |∃t > 0, t( - → v --→ v B ) ∈ B ext
Where B ext is the mapping of B in the configuration space of A: B ext = B⊕-A. The construction of the velocity obstacle can be achieved by constructing the collision cone which is the smallest cone with its apex at the origin containing B ext as illustrated in Fig. 1(b). The collision cone is then translated by -→ v B to become the velocity obstacle for A induced by B, V O A|B , as illustrated in Fig. 1(c).

In other words, the velocity obstacle is the set of velocities that would lead to collisions if chosen for A assuming:

• A instantly applies the chosen velocity and keeps it over an infinite time horizon • B keeps a constant velocity over an infinite time horizon On the contrary, if A chooses a velocity outside of V O A|B , collisions will be avoided under the same assumptions. Those assumptions are strong and seldom fulfilled in practice. Instead, the velocity obstacle algorithm is run at a high frequency to overcome the assumption that both agents will keep the same speed over an infinite time horizon.

B. Reciprocal Velocity Obstacles (RVO) and Hybrid Reciprocal Velocity Obstacles (HRVO)

The VO representation was designed for an agent avoiding passive moving obstacles but can cause oscillations when an agent is avoiding another active agent. This is due to the fact that VO forces an agent to take care of the whole collision avoidance.

To counter this behavior, RVO were designed [START_REF] Van Den Berg | Reciprocal velocity obstacles for real-time multi-agent navigation[END_REF]. An agent is now allowed to choose the average between its current velocity and the collision free velocity chosen out of the VO leading to the following definition:

RV O A|B = - → v |2 - → v --→ v A ∈ V O A|B
Therefore, the cone of collision defined for velocity obstacles is translated by

-→ v A + -→ v B 2
. This leads to each agent taking care of half of the avoidance and removes some oscillations that occurred when using the VO.

However, RVO can still cause oscillations that occurs when both agents choose to pass on the same side. Those oscillations called reciprocal dances can be observed with humans too. The HRVO [START_REF] Snape | The hybrid reciprocal velocity obstacle[END_REF] solve this issue by introducing an implicit agreement on the side on which the avoidance will be performed. It is constructed by expanding the RVO to a chosen boundary of the VO, forcing the crossing to be on a certain side. The side on which to expand the RVO is chosen as the opposite side of which -→ v A lies compared to the centerline of the RVO. For symmetry reasons, the other agent also chooses the same side.

C. Static obstacles

Since it has no velocity, the VO corresponding to a static obstacle has its apex at the origin, preventing all motion towards this obstacle. As a consequence, it needs to be truncated by a certain factor τ , the time horizon over which collisions will be avoided with that obstacle.

V O A|B,τ = - → v |∃t > τ, t( - → v --→ v B ) ∈ B ext
τ must be greater than the current deceleration time of the robot to ensure that the robot is able to stop before colliding with the obstacle.

III. PROPOSED METHOD

A. Modification of inter-robot collision avoidance

HRVOs allow the robots to implicitly agree on which side to pass. However, the quality of the choice relies on an accurate speed estimation of the agents. To eliminate this restrictive dependence, the robots are given an incentive to pass on the right side by modifying the HRVO.

The first modification is the choice on which side the leg of the HRVO is extended. It is fixed so that the second leg of the RVO in trigonometric order is changed and the first one remains the same, as seen in Fig. 2(a). This modification, called Left Hybrid Reciprocal Velocity Obstacles (LHRVO), gives the incentive to pass on the right side most of the time. However, when two robots have opposite speeds in a head to head encounter for example, or when the two robots are stopped, the RVO and the VO are overlapped. Therefore, the LHRVO is translated along the first leg as seen in Fig. 2(b). This gives a further incentive to pass on the right in all situations. This second construction is the Translated Left Hybrid Reciprocal Velocity Obstacles (TLHRVO).

B. Static obstacle estimation

To collect information about the environment the robot uses depth sensors such as Lidar or a RGB-D camera. The data resulting from the depth sensor is then mapped onto a two-dimensional occupancy grid representing the close surrounding of the robot. Most local planners can use the occupancy grid as is but it is not possible with velocity obstacles which require a geometrical representation of the obstacles footprints. To this end, obstacles are clustered using Density-Based Spatial Clustering of Applications with Noise (DBSCAN) [START_REF] Ester | A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[END_REF] and are extracted as polygons by taking the convex-hull of a cluster with Graham's algorithm [START_REF] Graham | An efficient algorith for determining the convex hull of a finite planar set[END_REF]. Finding the convex hull is easier than finding the concave polygon and does not impact the resulting VO.

C. Constraints and tracking error estimates of a unicycle robot

The following unicycle dynamic model is considered:

           ẋ = v cos θ ẏ = v sin θ θ = ω ω = a ω v = a v (1)
While the unicycle can perform forward motion due to the fact that ẋ cos θ + ẏ sin θ = v, it cannot move laterally as:

ẋ sin θ -ẏ cos θ = 0 (2)
This second equation, that constrains the kinematics and that cannot be integrated, is a nonholonomic constraint.

Moreover, the robot is assumed to have the following constraints on accelerations:

a v min ≤ a v ≤ a v max -a ω max ≤ a ω ≤ a ω max (3)
and the following speed limitations:

0 ≤ v ≤ v max -ω max ≤ ω ≤ ω max (4)
The VO approach was initially created for holonomic agents with dynamic constraints [START_REF] Fiorini | Motion planning in dynamic environments using velocity obstacles[END_REF]. As a consequence, the VO paradigm cannot be used the way it was originally thought as it would lead to a risk of collision. Indeed, in this paradigm, the chosen velocity, which is out of the VOs, is only ensured to be collision free if applied instantaneously to the robot. However, the nonholonomic nature of the unicycle model (2), the speed limit imposed (4) and the dynamic constraint (3) imply that the chosen velocity cannot be reachable instantly.

An approach is to consider that the nonholonomic robot will attempt to follow the speed that was chosen in the velocity obstacle paradigm but will have a tracking error [START_REF] Alonso-Mora | Optimal reciprocal collision avoidance for multiple nonholonomic robots[END_REF]. Instead of computing the tracking error after choosing a speed, the allowed tracking error is bounded thus limiting the admissible velocity space. Knowing that the error will be inferior to this bound, all the Minkowski sums used to build the VOs are expanded by this maximum tracking error allowed by performing another Minkowski sum with a disk of radius the maximum tracking error. This approach, which was applied to ORCA [START_REF] Alonso-Mora | Reciprocal collision avoidance for multiple car-like robots[END_REF], can also be applied to the considered velocity obstacles formulation.

To store the information about the tracking error, a set of maps is generated. The coordinates of a map are v x and v y , the coordinates that would be used as input for the controller. The value of the cell given by a certain pair (v x , v y ) is tracking error(v x , v y , v 0 , w 0 ). It is important to note that the tracking error does not depend on the position and orientation of the robot. As a consequence, the maps are invariant by translation and rotation. However, the error depends on the initial linear and angular velocities. This implies that a map must be generated for each initial condition. In practice the initial conditions are sampled uniformly. Fig. 3(a) shows an example of a map for a robot with v 0 = 0 and w 0 = 0.

This tracking error is obtained by numerically solving the differential equations using Runge-Kutta method allowing the use of any controller. As the generation of the tracking error maps is quite long, it is done offline. Online, knowing the maximum tracking error allowed, a polygon of allowed velocities is extracted from the map corresponding to the current speed of the robot, its outline being displayed in blue dotted lines in Fig. 3(b).

D. Speed choice in the velocity obstacle paradigm

Before making any speed choice in the velocity space, the preferred velocity, -→ v pref , must be determined. This preferred velocity is computed using the global plan as an indication. A point from the global plan is chosen using a look ahead distance. The direction of this point in the robot's frame is kept for the chosen speed which will have a norm proportional to the distance to the look ahead point, saturated in order not to exceed v max .

Once the velocity space has been restricted due to static obstacles, other robots and the kinematic and dynamic constraints of the robot, a speed must be extracted from the admissible speeds. The Clearpath algorithm is not demanding computationally. However, it tends to switch abruptly from one intersection point to another as only the euclidean distance to the preferred speed is considered when comparing the different points.

To counter this behavior, a scoring function is applied and takes into account the following elements:

• distance to the preferred speed The proposed algorithm to perform the speed choice, that we called Clearpath with Tracking Error (CTE), builds a list of potential velocities from the intersections of the VOs, the projections of the preferred speed on the VOs' legs, the intersections of the VOs with the tracking error polygon and the the points from the tracking error polygon. From the list of potential velocities, all the ones that are within the tracking error polygon and outside of the VOs are added to the list of admissible velocities and are scored. The speed with the best score is returned.

Once the speed has been chosen, it needs to be transformed before being applied to the robot. A lower level proportional controller is in charge of adapting the wheels velocities to reach the wanted linear and angular velocities (v, w). To determine (v, w), an approach similar to the one proposed by J. Alonso-Mora et al. [START_REF] Alonso-Mora | Optimal reciprocal collision avoidance for multiple nonholonomic robots[END_REF] is used.

v = ||v chosen || 2 , if | θ H T | < ω max 0, otherwise w = θ H T , if | θ H T | < ω max sign(θ H )ω max , otherwise
θ H is the angle between the heading of the robot and the chosen speed. T is a parameter representing the duration to reach the wanted orientation over which the robot rotates on the spot.

The linear and angular accelerations that this command would imply are then computed and (v, ω) are adapted so that the acceleration fits in the saturation bounds defined by Eq. ( 3).

IV. EXPERIMENTS

The solution is implemented in C++ in the ROS navigation stack 1 . Each robot performs its own localization using the Kullback-Leibler Divergence-sampling Monte Carlo Localization from the ROS package amcl 2 . The package obstacle detector 3 is used by the robots to detect and track moving obstacles using data from the depth sensors.

To evaluate the proposed solution, experiments were performed in both simulation and in real world settings. For each setting, two experiments were considered. The first one only focuses on the avoidance of static obstacles while the second one focuses on multi-robot collision avoidance with three robots (see attached video).

A. Simulations

The Gazebo engine was used to perform the simulations. The simulated robot is a Turtlebot 2. Its parameters are summarized in Table I. 1) Static obstacles avoidance: Although the primary focus of VO is not the avoidance of static obstacles, it is a prerequisite for which it is relevant to assess performance of the proposed solution against the state of the art. Thus, the first experiment was performed with two static unmapped obstacles that are the two blue cylinders. The proposed solution is compared to the TEB approach from the package teb local planner 4 , which was configured to follow the constraints from Table I.

A trajectory generation approach cannot perform multirobot collision avoidance without communication since it needs the planned trajectory of other robots. On the other hand, a reactive approach only requires the current state of the world. The goal of this experiment is to evaluate the loss of performance of the proposed reactive approach compared to a trajectory generation approach in regards to static obstacle avoidance. The results, gathered in Table II, show that the TEB approach is around 4% faster, which remains quite similar. It also leads to a smoother resulting trajectory. This is explained by the fact that the VO approach is reactive and only finds the optimal command until the next iteration. Taking into account the distance and angle to the previous chosen speed in the scoring of the admissible speeds allows the VO approach to have lower accelerations. On the other hand, the TEB package is set up to optimize travel time and we can assume it could use much less acceleration by changing the objective function used in the optimization.

2) Multi-robot collision avoidance: The second experiment was performed with three robots navigating in open space so that they can detect and track each other. The robots were given navigation goals so that they would all meet approximately at the same time with conflicting paths, as displayed in Fig. 4.

The moving obstacle detection faces some issue with the ego motion of the robot leading to false positives or inaccurate speed estimates. Table III gathers the results from fifty successive runs for each VO formulation. Fixing the choice on which side to pass using either LHRVO or TLHRVO greatly reduces the amount of collisions in the case of unreliable speed estimates. This is due to the fact that the HRVO formulation performs a choice on which side to pass based on the speed estimates and on the RVO centerline. TLHRVO causes less collisions than LHRVO because it is 4

B. Real world experiments

Similar experiments were performed on Turtlebots 3 waffle pi [22]. All the computations were done on the Raspberry pi 3 B+. The parameters used for the robots are summarized in Table IV. 1) Static obstacles avoidance: An experiment was performed with only one Turtlebot 3 and static obstacles conflicting with its path. The results from this experiment are summarized in Table V. Both methods were highly perturbed by sensor noise leading to the robot stopping. This behavior was particularly frequent for the VO approach. However, the TEB approach suffered from it as well as, during one run, the robot remained stuck until the it entered in a recovery behavior. This run was not taken into account for Table V. In 2) Multi-robot collision avoidance: An experiment was performed with the three Turtlebots positioned on the corners of a square. They were given the opposite corner as a navigation goal ten times for each VO formulation, see Fig. 5. The results are gathered in Table VI. Acceleration, both linear and angular, is much higher than in simulation due to sensor noise and more frequent false positives in moving obstacles detection. HRVO leads to collisions due to the fact that the choice on which side to pass is not reliable with the detection and tracking of moving obstacles used. The two modifications, LHRVO and TLHRVO, make this choice safe thus resulting in no collisions. TLHRVO yields slower travel times since it is more conservative in regards to restricting the velocity space.

V. CONCLUSIONS A modified online motion planning solution based on VO was presented for a multi-robot system. A static obstacle estimation was presented to convert the data from a depth sensor to a polygonal form usable by the VO approach. The consideration of the tracking error allows this method to rigorously take into account the kinematic and dynamic constraints of the nonholonomic robot and to keep the collision free nature of the VO paradigm. Furthermore, the polygon representing the velocities that are admissible in regards to the maximum allowed tracking error is used for a fast sampling of velocity space. Lastly, the adaptation of HRVO to give the incentive to pass on a certain side allows a much more reliable collision avoidance in a setting where the velocity estimates of the other agent are unreliable. While this proposed algorithm sees a slight decrease in performance when faced against a trajectory generation method in a setting with just static obstacles, this complete approach allows decentralized real-time dynamic collision avoidance without inter-agent communication. Furthermore, the computations are light enough to run on a single board computer at a frequency sufficiently high to avoid dynamic obstacles.

Related works show that the VO approach is prone to deadlocks when the number of agents increases [START_REF] Claes | Multi robot collision avoidance in a shared workspace[END_REF] or when the environment becomes too cluttered. To solve this specific problem not addressed in this paper, a higher level decision unit could be set up for conflict resolution.

Finally, the integration of this algorithm in parallel with a trajectory generation and tracking method would give it its full meaning. Indeed, most of the time the multi-agent aspect is not problematic since only some portions of the robots' trajectories end up being conflicting. Using a trajectory generation method to perform navigation and handing over to the VO approach when the intended velocities are no longer safe would allow to benefit from the advantages of the trajectory planning while maintaining the safety the proposed solution approach provides in a setting without communication and multiple agents.

Fig. 1 :

 1 Fig. 1: Velocity obstacle faced by agent A

Fig. 2 :

 2 Fig. 2: Velocity Obstacles constructions for inter-agent collision avoidance

Fig. 3 :

 3 Fig. 3: Tracking error map and admissible velocities.

Fig. 4 :

 4 Fig. 4: Resulting rajectories example for a simulation with three robots (using LHRVO)

Fig. 5 :

 5 Fig. 5: Experiment with three Turtlebots 3. From left to right, top to bottom.

  • angle to the preferred speed • distance to the previous speed • angle to the previous speed • distance to the speed chosen by Clearpath without considering dynamic and kinematic constraints • angle to the speed chosen by Clearpath without considering dynamic and kinematic constraints Algorithm 1 CTE Input preferred velocity v pref , tracking error polygon Pte and a list of VOs Lvo Output velocity to apply v chosen 1: if admissible(v pref ) then admissible(v pref ) return true if v pref is inside Pte and outside of all the VOs of Lvo

	2:	admissible velocities.append(v pref )
	3: end if
	4: for all velocity obstacle vo1 in Lvo do
	5:	for all velocity obstacle vo2 in Lvo deprived of vo1 do
	6:	potential velocities.append(intersections(vo1,vo2))
	7:	end for
	8:	potential velocities.append(intersections(vo1,Pte))
	9:	potential velocities.append(projectionss(v pref ,vo1))
	10: end for	projections points(v pref ,vo 1 ) returns the
			velocities resulting from the projection of
			v pref on the legs of vo 1
	11: potential velocities.append(points(Pte))
	12: for all potential velocity vpot in potential velocities do
	13:	if admissible(vpot) then
	14:	admissible velocities.append(vpot)
	15:	end if
	16: end for
	17: if admissible velocities is empty then
	18:	v chosen ← (0, 0)
	19: else
	20:	v chosen ←best score(admissible velocities)
	21: end if	best score(admissible velocities)
			returns the velocity with the highest score
	22: return v chosen	of admissible velocities

TABLE I :

 I Settings used for the simulated Turtlebot 2

	Setting	Value
	vmax	0.5 m/s
	ωmax	1.25 rad/s
	a v min	-1 m•s -2
	av max	1 m•s -2
	aω max	4 rad•s -2
	local planner frequency	10Hz
	global planner frequency	1Hz

TABLE II :

 II Performance with static obstacles over ten successive simulation runs. al and aa are respectively the average absolute linear and angular accelerations.

		VO, τ = 1s	TEB
		mean	std	mean	std
	al (m • s -2 )	0.08	0.04	0.11	0.09
	aa (rad • s -2 )	0.41	0.13	0.90	0.36
	travel time (s)	36.9	0.46	35.4	2.4

  Christoph Rösmann. teb local planner http://wiki.ros.org/teb local planner. Accessed: 2019-12-04.

TABLE III :

 III Performance with three Turtlebots 2 in simulation over 50 successive run. All values but the collisions are averaged over the three robots. al and aa are respectively the average absolute linear and angular accelerations.

		HRVO	LHRVO	TLHRVO
		mean	std	mean	std	mean	std
	al (m • s -2 )	0.11	0.06	0.10	0.05	0.11	0.06
	aa (rad • s -2 )	0.54	0.29	0.50	0.22	0.53	0.31
	travel time (s)	23.1	3.91	21.0	1.55	21.2	1.29
	collisions	14		6		3

TABLE IV :

 IV Settings used for the Turtlebot 3

	Setting	Value
	vmax	0.26 m/s
	ωmax	1.82 rad/s
	a v min	-2.5 m•s -2
	av max	2.5 m•s -2
	aω max	3.2 rad•s -2
	local planner frequency	10Hz
	global planner frequency	1Hz

TABLE V :

 V Performance with one Turtlebot 3 and static obstacles over ten successive runs. al and aa are respectively the average absolute linear and angular accelerations.

		VO, τ = 1s	TEB
		mean	std	mean	std
	al (m • s -2 )	0.26	0.23	0.13	0.12
	aa (rad • s -2 )	0.86	0.81	0.92	0.52
	travel time (s)	20.2	3.46	18.0	1.55

TABLE VI :

 VI Performance with three Turtlebots 3 over ten successive simulation runs. All values but the collisions are averaged over the three robots. al and aa are respectively the average absolute linear and angular accelerations.

		HRVO	LHRVO	TLHRVO
		mean	std	mean	std	mean	std
	al (m • s -2 )	0.26	0.22	0.23	0.20	0.25	0.20
	aa (rad • s -2 )	0.64	0.44	0.84	0.35	0.80	0.42
	travel time (s)	27.4	1.7	27.5	2.2	29.4	3.0
	collisions	2		0		0

Eitan Marder-Eppstein.

2D navigation stack ROS. http://wiki.ros.org/navigation. Accessed: 2019-12-04.[START_REF] Fox | The dynamic window approach to collision avoidance[END_REF] Brian P. Gerkey. amcl ROS. http://wiki.ros.org/amcl. Accessed: 2019-12-05.[START_REF] Roesmann | Trajectory modification considering dynamic constraints of autonomous robots[END_REF] Mateusz Przybyla. obstacle detector. https://github.com/tysik/obstacle detector. Accessed: 2020-01-07.


Rui Dai

Srijan Das

Franc ¸ois Bremond

Learning an Augmented RGB Representation with Cross-Modal Knowledge Distillation for Action Detection

In video understanding, most cross-modal knowledge distillation (KD) methods are tailored for classification tasks, focusing on the discriminative representation of the trimmed videos. However, action detection requires not only categorizing actions, but also localizing them in untrimmed videos. Therefore, transferring knowledge pertaining to temporal relations is critical for this task which is missing in the previous cross-modal KD frameworks. To this end, we aim at learning an augmented RGB representation for action detection, taking advantage of additional modalities at training time through KD. We propose a KD framework consisting of two levels of distillation. On one hand, atomic-level distillation encourages the RGB student to learn the sub-representation of the actions from the teacher in a contrastive manner. On the other hand, sequence-level distillation encourages the student to learn the temporal knowledge from the teacher, which consists of transferring the Global Contextual Relations and the Action Boundary Saliency. The result is an Augmented-RGB stream that can achieve competitive performance as the two-stream network while using only RGB at inference time. Extensive experimental analysis shows that our proposed distillation framework is generic and outperforms other popular cross-modal distillation methods in action detection task.

Introduction

Learning representation from untrimmed videos for action detection is a challenging vision task. Action detection aims at categorizing all the frames corresponding to every action occurring in an untrimmed video. The two main challenges for action detection are to tackle composite action patterns and fine-grained details [47]. These challenges are especially difficult in cases of real-world scenarios, where actions are densely distributed and overlapping each other [START_REF] Yeung | Every moment counts: Dense detailed labeling of actions in complex videos[END_REF]. To address these challenges, a typical setting, called two-stream network [START_REF] Simonyan | Twostream convolutional networks for action recognition in videos[END_REF], consists in combining RGB with additional modalities like optical flow [41,[START_REF] Xu | G-tad: Sub-graph localization for temporal action detection[END_REF], 3D poses [START_REF] Zolfaghari | Chained multi-stream networks exploiting pose, motion, and appearance for action classification and detection[END_REF][START_REF] Das | Vpn: Learning videopose embedding for activities of daily living[END_REF] to take into account the complementary nature of each modality. However, using such setting is contingent upon the availability of multiple modalities and of expensive processing resources. The cost of computing additional modalities could be prohibitive, especially for long untrimmed videos. These constraints limit the usage of multi-modal action detection methods for real-world applications.

Previous studies [START_REF] Gupta | Cross modal distillation for supervision transfer[END_REF][START_REF] Hafner | A cross-modal distillation network for person re-identification in rgb-depth[END_REF] have shown that cross-modal Knowledge Distillation (KD) is an effective mechanism to avoid the computation of the additional modalities during test time, while preserving the complementary information from the additional modalities. However, most previous works [START_REF] Crasto | MARS: Motion-Augmented RGB Stream for Action In CVPR[END_REF][START_REF] Nuno | Modality distillation with multiple stream networks for action recognition[END_REF][START_REF] Nuno | Distillation multiple choice learning for multimodal action recognition[END_REF] in the video understanding domain have investigated solely the classification of short trimmed videos [28,50,[START_REF] Kuehne | Hmdb: a large video database for human motion recognition[END_REF]. In these works, each video corresponds to a single action and the distillation framework infuses the aggregated knowledge of an action instance from one modality into another. In contrast to trimmed videos, untrimmed videos contain rich sequential knowledge with complex temporal relations. Untrimmed videos in realworld scenarios tend to have cluttered background and mul-tiple correlated actions either in sequence [36] or in parallel [START_REF] Yeung | Every moment counts: Dense detailed labeling of actions in complex videos[END_REF][START_REF] Gunnar | Hollywood in homes: Crowdsourcing data collection for activity understanding[END_REF]. Therefore, distillation mechanisms tailored for classification tasks and extended for detection tasks lack in capturing fine-grained details along the temporal dimension. Now the question remains, what should be the right strategy to distillate cross-modal knowledge for action detection in untrimmed videos?

In this work, we propose a distillation framework to combine cross-modal information for detecting actions with high precision and minimal resource. The goal is to reach the two-stream performance while using only the RGB stream at inference time. The proposed distillation framework consists of a traditional teacher-student network architecture which operates in a Seq2Seq fashion [START_REF] Piergiovanni | Temporal gaussian mixture layer for videos[END_REF][START_REF] Dai | Tan: Temporal aggregation network for dense multi-label action recognition[END_REF], thanks to three new distillation losses dedicated to the action detection task as illustrated in Fig. 1. The first loss in our formulation is the Atomic KD loss, which enables the RGB student network to mimic the feature representation of every individual snippet from the teacher network in a contrastive manner. This loss-term extends the crossmodal KD mechanism fabricated for the classification tasks to the temporal domain [START_REF] Luo | Graph distillation for action detection with privileged modalities[END_REF], by transferring the knowledge only between one-to-one corresponding snippets of different modalities. As a snippet is often shorter than the action instance in an untrimmed video, so this loss encourages a transfer of sub-representation [START_REF] Gu | Ava: A video dataset of spatio-temporally localized atomic visual actions[END_REF] of the action, for example, "raising arm" in the "drinking" action. Here, such sub-representation w.r.t. the entire video corresponds to an atomic piece of knowledge within the complete action feature distribution. However, the untrimmed video is composed of a sequence of snippets, distilling only the atomic representation is not sufficient for learning discriminative action representation. Thus, distillation mechanisms dedicated to represent specifically an action within an untrimmed video are required.

We therefore introduce two loss-terms for sequence-level KD so as to transfer the cross-snippet relations between different modalities. Firstly, we propose a Global Contextual Relation loss to transfer the contextual information of the sequence between modalities. In our work, contextual information is defined as the embedding of the correlation between all the snippet features. Thanks to this loss term, every student snippet feature can learn in the latent space from all the correlated teacher snippets within the untrimmed videos (Fig. 1). With this loss-term, detecting one action in a snippet can benefit from the information in the correlated snippets (corresponding to related actions, e.g. take and eat sandwich) across modalities, resulting in better action detection performance. Secondly, we propose another KD loss to distillate the boundary saliency from the teacher to RGB student network, dubbed Boundary Saliency loss. This ensures a more precise action boundary detection of the RGB student which is prone to imprecise action boundary detection due to weak temporal signals. In an untrimmed video, the start and end moments of the action are more salient than other parts (see Fig. 1). Intuitively, the feature variation across consecutive snippets in the video can reflect such saliency of the action boundaries. Therefore, learning this variation from a modality that can better capture the movement (e.g. optical flow, 3D poses) encourages the RGB stream representation to be more sensitive to the action boundaries.

Contributions. To summarize, we take a step towards the little-explored but crucial, cross-modal KD for action detection. We build a Seq2Seq KD framework for action detection with a novel formulation. This formulation consists of an atomic-level KD loss and two sequence-level KD losses. The three loss terms in our formulation are jointly optimized in an end-to-end fashion. To the best of our knowledge, we are the first to propose a formulation containing sequential KD loss for the action detection task. We perform comprehensive experiments on five benchmarks. Our joint formulation significantly improves the vanilla RGB baseline (up to +6.8% improvement on MultiTHUMOS w.r.t. vanilla-RGB) and achieves the Twostream performance while using only RGB at inference time. The consistent improvement on all these datasets corroborates the effectiveness and robustness of our distillation framework.

Related work

In this section, we briefly review the action detection architectures and the state-of-the-art cross-modal distillation methods.

Action Detection

Depending on the density of annotation, there are two kinds of dataset for action detection: (1) Sparsely labeled [START_REF] Jiang | THUMOS challenge: Action recognition with a large number of classes[END_REF][START_REF] Ghanem | Activitynet: A largescale video benchmark for human activity understanding[END_REF]36] and (2) Densely labeled [START_REF] Yeung | Every moment counts: Dense detailed labeling of actions in complex videos[END_REF][START_REF] Gunnar | Hollywood in homes: Crowdsourcing data collection for activity understanding[END_REF]8] datasets. In the community, most action detection approaches [START_REF] Zhao | Temporal action detection with structured segment networks[END_REF][START_REF] Gao | Turn tap: Temporal unit regression network for temporal action proposals[END_REF][START_REF] Xu | G-tad: Sub-graph localization for temporal action detection[END_REF] are custom-made for the sparsely labeled datasets. As densely labeled datasets include finegrained actions occurring concurrently, they are more challenging and close to real-world scenarios [START_REF] Yeung | Every moment counts: Dense detailed labeling of actions in complex videos[END_REF]. Concerning the popular action detection approaches, anchor-based methods [61,3,[START_REF] Gao | Turn tap: Temporal unit regression network for temporal action proposals[END_REF] are inspired by the two-stage object detection framework, which leverages a set of pre-defined anchors to generate action proposals along with another classification stage. However, anchor-based methods require a large number of anchors for generating the proposals and hence under-perform on densely labeled datasets [61, 5]. To handle the above issues, some methods [START_REF] Piergiovanni | Temporal gaussian mixture layer for videos[END_REF][START_REF] Lea | Temporal convolutional networks for action segmentation and detection[END_REF][START_REF] Dai | Selfattention temporal convolutional network for longterm daily living activity detection[END_REF]51,[START_REF] Dai | Pdan: Pyramid dilated attention network for action detection[END_REF] borrow the Seq2Seq framework from Natural Language Processing [START_REF] Das | Looking deeper into time for activities of daily living recognition[END_REF] to action detection. Seq2Seq methods are composed of a visual encoder to encode the primary spatiotemporal features, an efficient temporal filter to model the temporal information and a classifier to perform the framelevel action detection. This framework "interprets" the im-age sequence into a sequence of prediction scores. Framelevel action detection can be seen as a class-specific actionness detector. By referring to actionness-based methods [START_REF] Zhao | Temporal action detection with structured segment networks[END_REF][START_REF] Xiong | A pursuit of temporal accuracy in general activity detection[END_REF][START_REF] Chen | Afnet: Temporal locality-aware network with dual structure for accurate and fast action detection[END_REF], the action proposals can be generated from the frame-level detection results. Seq2Seq based approaches perform well on both types of dataset, especially for the densely annotated one [START_REF] Piergiovanni | Temporal gaussian mixture layer for videos[END_REF][START_REF] Dai | Tan: Temporal aggregation network for dense multi-label action recognition[END_REF]. To build a generic distillation framework that can tackle both dataset types, we thus rely on the Seq2Seq paradigm. Furthermore to incorporate the appearance and motion based information, the state-of-the-art sequence based approaches make use of two-stream architectures [41,[START_REF] Piergiovanni | Temporal gaussian mixture layer for videos[END_REF].

In order to avoid the expensive computation of two-stream architectures, cross-modal distillation methods [START_REF] Crasto | MARS: Motion-Augmented RGB Stream for Action In CVPR[END_REF][START_REF] Nuno | Modality distillation with multiple stream networks for action recognition[END_REF] and fast Optical Flow (OF) detectors [START_REF] Kantorov | Efficient feature extraction, encoding and classification for action recognition[END_REF]52,[START_REF] Sun | Optical flow guided feature: A fast and robust motion representation for video action recognition[END_REF][START_REF] Zhao | Dance with flow: Two-in-one stream action detection[END_REF] have been introduced for video classification tasks.

However, the fast OF detector techniques are modality-specific with relatively low performance [START_REF] Crasto | MARS: Motion-Augmented RGB Stream for Action In CVPR[END_REF]. Therefore, we propose to dig deeper into cross-modal distillation mechanisms for learning compact action representations for long continuous videos.

Cross-Modal Knowledge Distillation

The primary goal of Knowledge Distillation (KD) is to distill the information of a model learned from a teacher network into a student network. Many KD studies [23,[START_REF] Chen | Learning efficient object detection models with knowledge distillation[END_REF][START_REF] Park | Relational knowledge distillation[END_REF]56,[START_REF] Liu | Structured knowledge distillation for semantic segmentation[END_REF] explored transferring the knowledge from large complex models to small simpler models, i.e. model compression. In this work, we focus on cross-modal KD, where the difference between the teacher and student models mostly relies on input modalities rather than network architectures. In the video domain, Garcia et al. [START_REF] Nuno | Modality distillation with multiple stream networks for action recognition[END_REF] developed a distillation framework for action classification with a four-step process that hallucinates depth features into RGB frames. Similarly, MARS [START_REF] Crasto | MARS: Motion-Augmented RGB Stream for Action In CVPR[END_REF] trains a RGB network in a single step, by back-propagating a linear combination of a OF distillation and classification losses through the entire network. Recently, Luo et al. [START_REF] Luo | Graph distillation for action detection with privileged modalities[END_REF] proposed a Graph Distillation (GD) method that can be applied to the action detection task. This method utilizes sliding windows to process untrimmed videos and distillates the knowledge of every window by minimizing the cosine distance in a mutual learning manner. GD aims at exploiting the privileged modalities and thus relies on a significant number of modalities. In contrast, our framework aims at effectively performing the distillation from the available modalities. Moreover, GD transfers knowledge only between the corresponding snippets (i.e. window), but does not consider the relations across snippets in the distillation, which is critical for handling a sequence of actions. Thus, to better tackle distillation for action detection, we propose a new formulation with three loss-terms. More specifically for transferring knowledge along the temporal dimension in the untrimmed video, we introduce a sequence-level distillation Figure 2. The proposed distillation framework. On the top, we present an example of a batch size (B) of 2 untrimmed videos (V) for both student (S) and teacher (T ) networks. In this example, the input includes a pair of positive videos and a pair of negative videos. The sequence-level distillation and classification losses are employed only for positive pairs, while atomic-level distillation leverages both positive and negative pairs. On the bottom, we present the atomic-level distillation.

mechanism. Thanks to it, the network can be effective even with few additional modalities.

Proposed Distillation Framework

In this section, we first describe the overall architecture of our approach. We then detail the different losses in the proposed framework.

Overall Architecture

An overview of the architecture is shown in Fig. 2. In this work, the knowledge transfer occurs between the teacher and student networks. As discussed in Sec. 2.1, both networks are composed of a visual encoder and a temporal filter, following the Seq2Seq paradigm. For the visual encoder, we use I3D [2] to encode the spatio-temporal information of a snippet for RGB and Optical Flow (OF). Similar to previous action detection methods [START_REF] Abu | Ms-tcn: Multistage temporal convolutional network for action segmentation[END_REF]65], sequences of 16 frames are encoded to a single feature vector representation. The encoded feature maps of a video are then fed to the temporal filter. The choice of the temporal filter is flexible, since we can choose any well-known temporal model [START_REF] Piergiovanni | Temporal gaussian mixture layer for videos[END_REF][START_REF] Lea | Temporal convolutional networks for action segmentation and detection[END_REF][START_REF] Hochreiter | Long shortterm memory[END_REF]. Here, we set a 5-layer SS-TCN [START_REF] Abu | Ms-tcn: Multistage temporal convolutional network for action segmentation[END_REF] as default temporal filter, which is based on Dilated-TCN [START_REF] Lea | Temporal convolutional networks for action segmentation and detection[END_REF]. Both student and teacher have the same type of temporal filter with the same settings (i.e. dilation rate and channel size). In the training phase, the knowledge distillation is performed from the output feature of the teacher network towards the student network. Similar to [START_REF] Piergiovanni | Temporal gaussian mixture layer for videos[END_REF][START_REF] Dai | Tan: Temporal aggregation network for dense multi-label action recognition[END_REF], this output feature map is further classified and grouped as a class-wise actionness detector for detecting the actions.

The input of teacher network is flexible to variant costly modalities (e.g. OF, 3D poses). By default, we chose the teacher network as OF stream, whereas the student network as RGB stream. In the following sections, we express the feature representation of a video indexed i with F r (i, t, c), where r ∈{T , S} represents the teacher T and student S; t ∈ [1, T ] represents the snippet index and T the length of the video in snippets; c ∈ Z C represents the channel index, C is the channel size. This expression can be used for representing feature of a video or a snippet. For example, F r (i, :, :) and F r (i, t, :) represent the feature map of a video i and the feature vector of a snippet for video i at time step t, respectively. For an augmented RGB representation, the distillation is performed in two levels. First, we perform distillation at atomic-level to distillate the elementary representation of an action. Second, we perform a sequence-level distillation to distillate (i) the salient relations among the snippets, and (ii) the significant temporal variations across the snippets indicating action boundaries.

Atomic-level Distillation

To transfer the knowledge between two video sequence, firstly, we adapt and integrate the "representation loss" [START_REF] Luo | Graph distillation for action detection with privileged modalities[END_REF] in our overall formulation, dubbed Atomic KD loss. This loss term encourages the student to mimic the feature representation of every individual snippet feature of the teacher network. Our formulation is different from the previous work [START_REF] Luo | Graph distillation for action detection with privileged modalities[END_REF] that minimizes the cosine distance between the snippet features. Inspired by the recent success on contrastive learning [55, [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF][START_REF] Van Den Oord | Representation learning with contrastive predictive coding[END_REF], we build our model using a contrastive strategy to enhance the atomic-level knowledge imitation.

As shown in Fig. 2, let [F S (i, t, :), F T (i, t, :)] represents a pair of training snippets from same video i at time t but across different modalities for the teacher and student networks. Let F T (j, t, :) be another snippet representation from a randomly chosen video j of the teacher stream and having a different label. We define the pair [F S (i, t, :), F T (j, t, :)] as positive when i = j, otherwise negative. We aim at pushing closer the representations F S (i, t, :) and F T (i, t, :), while pushing apart F S (i, t, :) and F T (j, t, :), which can be seen as a binary classification task that tries to maximize the log-likelihood of the mutual information between the student and teacher representations. In practice, the loss is updated by batches with a batch size B. If N negative pairs exist for each positive pair, then the number of samples in a batch of P positives is given by B = (N +1)P (see Fig. 2). To measure the mutual information between the student and the teacher, we compute:

L Atomic = 1 PT i=j T t=1
log[ exp F T (j,t,:) ⊤ F S (i,t,:) exp F T (j,t,:) ⊤ F S (i,t,:

) +ϕ ]+ 1 T i̸ =j T t=1
[log(1 -exp F T (j,t,:) ⊤ F S (i,t,:) exp F T (j,t,:) ⊤ F S (i,t,:) +ϕ )]

where PT represents total number of positive snippets, ϕ is the ratio of the negative snippets to the cardinality of snippets in the training set. Note that, this loss term is accompanied by a linear combination with the other distillation losses and the class-wise entropy loss (i.e. supervised learning).

As the length of an action instance is often larger than a snippet, with atomic-level distillation, the teacher network transfers only the sub-representation of the actions [START_REF] Gu | Ava: A video dataset of spatio-temporally localized atomic visual actions[END_REF]. Next, we propose a novel sequence-level distillation mechanism which has been neglected in the state-of-the-art methods.

Sequence-level Distillation

Sequence-level distillation transfers cross-snippet knowledge between different modalities in an untrimmed video by incorporating contextual information and taking benefit from the variations of cross-modal representation along action boundaries. Consequently, we propose two sequence-level distillation losses: (1) Global Contextual Relation, (2) Boundary Saliency, to improve action detection performance. Note that both sequence-level distillation losses are applied only between positive video pairs, corresponding to P videos.

Global Contextual Relation

For sequence-level distillation, firstly, we propose to transfer contextual knowledge between modalities of the entire video. Intuitively, the detection of one given action could be supported by the detection of other related actions, which may be distant in the untrimmed video [41]. Hence, the representation of an action snippet could benefit from the contextual information across other snippets in the video pertaining to another modality. But the challenge in modeling such contextual relationships is the high complexity of the model for taking into account all the snippets in a video in relation with a single snippet. Therefore, we propose an embedding that projects the student-teacher features in a space where the global contextual relations among all actions are computed.

For the global contextual relation loss, we compute the Channel Covariance Matrix (Cov) of the sequence of snippets. Our motivation for using channel covariance is: (1) At each time instant, the channel contains the latent representation of actions, thus channel covariance embeds the relation between action events in a video; (2) Though the videos and action events have a high variation in length, the channel size is fixed. This results in channel covariance being a more robust representation.

Providing a feature map of the video, Cov encodes the variance within each channel and the covariance between all channels over the whole video. Each element in the matrix reflects the correlation between two channels, which can characterize the specific activation patterns along time of an action class. Thus, the covariance matrix captures the relations between snippets along time and indicates whether a salient relation exists (i.e. which may be related to an action), while being computationally optimal. Here, the Cov is formulated as:

Covr(i) = 1 T -1 T t=1 [Fr(i, t, :) -µ i ][Fr(i, t, :) -µ i ] T (2)
such that r ∈ {T , S}, and µ i represents the mean value of all the channels in the feature map F r (i, :, :) of a video i.

The covariance matrix Cov r ∈ R C×C is a symmetric matrix and thus it is determined by C(C+1) 2 values. We apply a filter mask extracting all the entries on and above the diagonal of the covariance matrix. We reshape these values in the form of a vector G r (i):

Gr(i) = mask[Covr(i)] (3)
where mask(.) is the filter mask operation. The obtained feature vector G r represents the channel covariance of the video. We then enforce a distillation loss in the embedded space from the frozen teacher to the student over the positive video pairs (P). This is performed by minimizing the mean square error, which is formulated as the Global Contextual Relation loss:

L Global = 1 P P i=1 ||G T (i) -G S (i)|| 2 (4)
The differential property of equation 2 enables to train our teacher-student framework jointly with the other losses.

Boundary Saliency

The boundary saliency loss term is used in our formulation to learn comparatively precise boundaries for action detection. In an untrimmed video, we find that the starting and ending of the action are more salient than other parts [34], that brings us crucial information to detect the transition of an action to another action or background. Intuitively, the sharp variation across consecutive snippets in the video can reflect such saliency of the action boundaries, which is a cross-snippet knowledge. Transferring the knowledge of feature evolution along time encourages the features to be more sensitive at the action start and end, thus assisting the class-wise actionness detector in the student network to detect precise boundaries of the action instances. Such an approach is especially effective when the modality processed at the teacher network provides pertinent boundary information. For instance, modalities which are sensitive to motion (e.g. OF, 3D poses) are able to bring a significant benefit from this loss term. In addition, this loss-term also encourages to retain the temporal consistency across the different modalities.

In practice, we first define the variation between consecutive snippets as V ar(i) for video i, which is formulated as:

V arr(i) = 1 T -1 T -1 t=1 C c=1 [Fr(i, t + 1, c) -Fr(i, t, c)] (5)
where r ∈ {T , S}. Then, we define the Boundary Saliency loss as the L1 distance between the frozen teacher and the student network over the P positive pairs, which is formulated as:

L Boundary = 1 P P i=1 |V ar T (i) -V ar S (i)| (6)
With both sequence-level distillation losses, the student network learns two types of cross-snippet information from the other modalities. Below, we summarize the training procedure section.

Training and Testing

To sum up, firstly, we train the teacher networks with the classification (Cls) loss, i.e cross-entropy. The weights of the teacher network is then frozen followed by training the student network. During training, multiple distillation losses are jointly optimized with classification loss for the end task, i.e. action detection. On one hand, the atomic distillation is trained in a contrastive manner (with positive and negative pairs), whereas the sequence-level distillation losses are performed in a non-contrastive manner by utilizing only the positive pairs in a batch. The overall objective is formulated as: [START_REF] Dai | Pdan: Pyramid dilated attention network for action detection[END_REF] where α i are the loss weighting factors determined during the validation step. L Cls represents the cross-entropy classification loss. We call the educated-student network as Augmented-RGB. During inference time, we only use RGB videos as input to detect the actions and up-sample the predicted logits to the same temporal resolution as the ground truth to perform the evaluation.

L total = L Cls + α 1 L Atomic + α 2 L Global + α 3 L Boundary

Experimental Analysis

To corroborate the effectiveness of our proposed KD framework, we perform an exhaustive experimental analysis for the action detection task.

Dataset Description

We evaluate our framework on five action detection datasets: Charades [47], PKU-MMD [36], TSU [8], THU-MOS14 [START_REF] Jiang | THUMOS challenge: Action recognition with a large number of classes[END_REF], and MultiTHUMOS [START_REF] Yeung | Every moment counts: Dense detailed labeling of actions in complex videos[END_REF]. These datasets contain videos of different types: (1) sport and daily living ). We only target the second one in this paper.

All the datasets are evaluated by the mean Average Precision (mAP). We evaluate the per-frame mAP on densely labeled datasets following [START_REF] Yeung | Every moment counts: Dense detailed labeling of actions in complex videos[END_REF]47].

Implementation Details

For extracting the additional modalities, Optical Flow (OF) is obtained using TVL1 [START_REF] Sánchez Pérez | TV-L1 Optical Flow Estimation[END_REF], the 3D Poses are extracted using LCRNet++ [44]. In this work, we adapt the 5-layer SSTCN [START_REF] Abu | Ms-tcn: Multistage temporal convolutional network for action segmentation[END_REF] as the temporal filter, the output channel size C is 256. While training the teacher-student framework, we use Adam optimizer [START_REF] Diederik | Adam: A method for stochastic optimization[END_REF] with an initial learning rate of 0.001, and we scale it by a factor of 0.3 with a patience of 10 epochs. The network is trained for 300 epochs with a mini-batch B of 16 videos for Charades, 8 videos for PKU-MMD, THUMOS, and 4 videos for the TSU dataset. N is set to 1, P as B 2 and α i =[300, 100, 5]. We use binary cross-entropy for multi-label classification (i.e. class-wise actionness). For sparsely-labeled datasets: THUMOS14 and PKU-MMD, following [START_REF] Luo | Graph distillation for action detection with privileged modalities[END_REF][START_REF] Dai | Tan: Temporal aggregation network for dense multi-label action recognition[END_REF], a post-processing step is performed to generate the action boundaries.

Ablation Study

Firstly, we discuss about the effectiveness of the losses proposed in our distillation framework. Tab. 1 shows the comparison of action detection performance on Charades and PKU-MMD (IoU=0.1). This table also shows the impact of progressively integrating the KD losses in our distillation framework. The vanilla-RGB is the network trained using only L Cls without distillation. Compared to vanilla RGB, while training with L Atomic , L Global , L Boundary independently obtains an improvement of +3.1, 4.1, 3.5% mAP on PKU-MMD respectively. The action detection performance is further improved by the convex combination of any two losses w.r.t. their individual counter-parts. This shows the complementary functionalities of the proposed losses. Also, note that the combination of the sequence losses contributes higher than the atomic loss. This observation supports the importance of the sequence-level losses for action detection. Finally, when trained with all the three losses, the student outperforms all the baselines (+2.3%, +5.9% w.r.t. vanilla RGB stream on Charades and PKU-MMD). These results show that both our design choices and different losses contribute to the overall performance of our approach.

In Tab. 2, we show that our distillation mechanisms perform better at feature-level than at logit-level. The primary reason behind this trend is that we are performing crossmodal distillation, where the frozen teacher may underperform compared to the student network (e.g. OF on Charades and PKU-MMD) w.r.t. the different modalities. As the logits represent the classification scores, they may introduce noise from the weak teacher via KD into the RGB student.

Analysis of our Distillation Framework

In this section, we further analyze our distillation framework in different aspects. Comparison with popular cross-modal KD methods: Tab. 3 presents a comparison of our extended atomic distillation with state-of-the-art cross-modal KD methods, learning from OF. These baseline methods [START_REF] Hoffman | Learning with side information through modality hallucination[END_REF][START_REF] Crasto | MARS: Motion-Augmented RGB Stream for Action In CVPR[END_REF][START_REF] Nuno | Modality distillation with multiple stream networks for action recognition[END_REF][START_REF] Wang | Learning deep structure-preserving image-text embeddings[END_REF] using traditional losses like MSE and cosine distance are actually designed for classification tasks. For the comparative analysis with our L Atomic , we adapt them following [START_REF] Luo | Graph distillation for action detection with privileged modalities[END_REF] for the task of action detection. L Atomic consistently outperforms all the baseline methods on Charades and PKU-MMD datasets (+1.6%, +3.1% w.r.t. vanilla RGB stream on Charades and PKU-MMD). Performance with different Temporal filters: In Tab. 4, our distillation framework is implemented with different temporal filters to confirm its robustness. The experiments are performed with a student network learning from a teacher network pre-trained with OF on Charades dataset. The results show that both SSTCN [START_REF] Abu | Ms-tcn: Multistage temporal convolutional network for action segmentation[END_REF] and TGM [START_REF] Piergiovanni | Temporal gaussian mixture layer for videos[END_REF] consistently improve the performance of RGB stream and achieve the competitive performance of two-stream network. Analyzing our framework with different modalities: In Tab. 5, we validate that our proposed method is generic and can be effective with different modalities. For experimentation, we perform distillation from OF and 3D Poses. For 3D poses, the teacher consists of 2s-AGCN [START_REF] Shi | Two-stream adaptive graph convolutional networks for skeleton-based action recognition[END_REF] as visual encoder followed by the temporal filters for detecting actions. In datasets like Charades, most actions involve human-object interactions with prominent motion patterns and in datasets like PKU-MMD, most actions have similar appearance with variant motion over time. Thus, OF stream provides more salient information than Pose stream on these datasets. Whereas 3D Poses are robust to the change of the view-points and thus, significantly improves the action detection performance in cross-view settings (see Tab. 5). Furthermore, with a multi-teacher network with OF and [START_REF] Nuno | Modality distillation with multiple stream networks for action recognition[END_REF] 22.7 81.5 +L M ARS [START_REF] Crasto | MARS: Motion-Augmented RGB Stream for Action In CVPR[END_REF] 23.5 81.7 +L GD [START_REF] Luo | Graph distillation for action detection with privileged modalities[END_REF] 23.3 82.2 +L Atomic (Ours)

23.9 82.7 Poses, the RGB stream now dubbed as Pose + OF Augmented RGB learns some additional information (+2.6%, +6.7%, +4.5%, +4.9% w.r.t. vanilla RGB stream on Charades, PKU-MMD, TSU-CS, TSU-CV respectively).

Inference time & Complexity: Fig. 3 shows the precision vs inference time per video on Charades dataset. The inference time includes the time of extracting the additional modalities and the processing time of the visual encoder and temporal filter. We find that Two stream RGB + TVL1 [START_REF] Zach | A duality based approach for realtime tv-l 1 optical flow[END_REF] achieves high precision on Charades, but at the expense of a high computational cost. In this work, we use TVL1 to obtain the OF modality. Although there are methods [START_REF] Kantorov | Efficient feature extraction, encoding and classification for action recognition[END_REF]52] that generate OF at higher speed, these methods perform significantly worse than TVL1 [START_REF] Crasto | MARS: Motion-Augmented RGB Stream for Action In CVPR[END_REF]. Similarly, the computation of accurate 3D Poses is not real-time, and hence doubles the video processing time [44]. With these modalities in training phase, our proposed framework avoids estimating these modalities at test time while keeping the performance of two-stream network. The processing speed at the inference phase (I3D+SSTCN) is about 140 fps using 4 GPUs, thus can be seen as a real-time processing. Concerning complexity, as we have the same type of temporal filter and encoder for teacher and student, the Augmented-RGB stream retains the same number of parameters as the vanilla RGB stream at inference time, whereas two stream network doubles the number of parameters often causing over-fitting [59].

Qualitative Analysis

With Global Contextual Relation loss, the student learns the relationships among the action instances of the teacher network along with retaining the student's individual representation. As shown in Fig. 4, with only L Global , the channel covariance representation of Augmented-RGB is closer to the one of RGB+OF. Hence, the Augmented-RGB achieves performance close to the one of the two-stream network. We also compare the performance of RGB stream with Boundary Saliency distillation and vanilla RGB stream. In Fig. 5, we find that the network with L Boundary detects tighter temporal boundaries of the actions compared to the vanilla network. To further show how two sequence-level distillation losses are complementary, we compare APs for a student that is trained with only L Global or L Boundary on Charades in Fig. 6. We find that L Boundary improves more the actions with high variation across time (e.g. Throw pillow), L Global improves more the actions with relatively longer duration (e.g. Holding mirror). While learning from L Global +L Boundary , the student improves all action types, reflecting how these two loss-terms complement each other. Fig. 7 shows the class-wise actionness result of the vanilla-RGB and Augmented-RGB in a densely labeled video along with the action detection results. We notice that the Augmented-RGB detects tight action boundary w.r.t. the vanilla-RGB, e.g. use cupboard, walk. Thanks to our distillation methods, the Augmented-RGB now predicts the use drawer action which is miss detected in vanilla-RGB.

Comparison with the State-of-the-Art

In Tab. 6, we compare other action detection methods with our Augmented-RGB on PKU-MMD. Recall that our distillation mechanisms are build on SSTCN. While one method [START_REF] Li | Skeleton-based action recognition with convolutional neural networks[END_REF] using Poses achieves very high performance, this method is skeleton-based and applicable only for specific datasets (i.e. NTU-RGBD [START_REF] Shahroudy | Ntu rgb+d: A large scale dataset for 3d human activity analysis[END_REF], PKU-MMD [36]), where high quality 3D Poses are available. In contrast, our method is generic and does not rely on Poses at inference time while being more effective compared to other RGB based SoA methods, such as Graph Distillation [START_REF] Luo | Graph distillation for action detection with privileged modalities[END_REF] (+2.6%, +2.4%, +4.6% for 0.1, 0.3, 0.5 IoU), which utilizes the same temporal filter but more modalities (e.g. depth) at training time compared to our method.

To show the generalization of our method, we also evaluate our distillation framework on Charades and TSU-CS, MultiTHUMOS and THUMOS in Table 7. For all these comparisons, the student network is distilled with teacher pre-trained with OF in the training phase, as Poses are not always available. For a fair comparison with our Augmented-RGB, Vanilla-RGB and Two-stream networks are implemented using SSTCN. In this table, we find that, anchor-based methods (e.g. AFNet) perform decently on sparsely-labeled datasets, while failing on densely labeled datasets due to the combinatorial explosion of proposals. On the other hand, Seq2Seq architectures are stable on both types of dataset. With the help of our proposed distillation method, the Augmented-RGB achieves the competitive Two-stream performance on all the datasets (+2.3, 3.6, 6.8, 7.2 w.r.t. vanilla-RGB on Charades, TSU, Multi-THUMOS, THUMOS14 respectively). We observe that the performance improvement on THUMOS which consists of sport videos, is significant due to strong motion patterns resulting to an effective OF based teacher network. Thus, Augmented-RGB while using only RGB at inference, performs on par with Two-stream network for the task of action detection.

Conclusion

In this work, we have introduced a novel distillation framework for action detection. This generic framework combines three novel learnable losses to better benefit from the cross-modal information in untrimmed videos. To the best of our knowledge, we are the first to propose a formulation with sequence-level distillation in this task. Thanks to this framework, we can improve the performance of vanilla RGB networks and make it possible to detect actions in real-time with high precision, even in case of densely labeled datasets. Experiments on five datasets show that the proposed method can effectively infuse different modalities into RGB. For instance, the Augmented-RGB network achieves the Two-stream network performance while using only RGB at inference time.

Figure 1 .

 1 Figure 1. Proposed cross-modal distillation framework for action detection. Our distillation framework is composed of three loss terms corresponding to different types of knowledge to transfer across modalities. LAtomic: Atomic KD loss; L Global : Global Contextual Relation loss; L Boundary : Boundary Saliency loss.

Figure 3 .

 3 Figure 3. Precision vs Inference time per video on Charades.

Figure 4 .

 4 Figure 4. Channel Covariance. We visualize the Covariance matrix of a video for the vanilla RGB, vanilla OF, the two-stream RGB+OF, and the Augmented-RGB (L Global ). For better visualization, we normalize the matrix to [0,1] and set a threshold of 0.5.

Figure 5 .

 5 Figure 5. Action boundary detection: (1) Ground truth indicates if it is action or background at this frame. (2) The boundaries detected without L Boundary , (3) The boundaries detected with L Boundary .

Figure 6 .

 6 Figure 6. Difference of Average Precision for two sequence-level distillation losses on Charades dataset. G: L Global , B: L Boundary .

Figure 7 .

 7 Figure 7. Class-wise actionness with the detection results.

Table 1 .

 1 Ablation study for the proposed framework on Charades and PKU-MMD (CS) datasets. For PKU-MMD we consider IoU=0.1.

		L Atomic L Global L Boundary Charades PKU-MMD
	Teacher-OF	-	-	-	18.6	68.4
	Vanilla-RGB	-	-	-	22.3	79.6
	Two-stream	-	-	-	24.8	83.4
	Atomic	✓	-	-	23.9	82.7
		-	✓	-	23.8	83.7
	Sequence	-	-	✓	23.4	83.1
		-	✓	✓	24.2	84.2
	Mixture	✓ ✓	✓ -	-✓	24.4 24.2	84.3 83.7
	Total	✓	✓	✓	24.6	85.5
	videos, (2) short and long videos, (3) densely and sparsely
	labeled videos. Note: there are two settings on Charades:
	(1) video-level action classification, (2) frame-level action
	detection (Charades v1 localize [47]

Table 2 .

 2 Feature-level and logit-level distillation. The student learns from OF stream. For PKU-MMD, we set IoU=0.1.

		Charades PKU-MMD
	Logit	23.7	84.9
	Logit+Feature 24.2	85.4
	Feature (Ours) 24.6	85.5

Table 3 .

 3 Comparison with cross-modal KD methods and LAtomic on Charades and PKU-MMD datasets. For PKU-MMD, IoU=0.1.

		Charades	PKU-MMD
	Vanilla-RGB	22.3	79.6
	+L Hall

Table 4 .

 4 Ablation for different temporal filters: SS-TCN and TGM on the Charades. The models learn from the OF.

		SSTCN TGM
	Vanilla-RGB	22.3	18.9
	Two Stream	24.8	21.5
	Augmented-RGB	24.6	21.2

Table 6 .

 6 Event-based mAP on PKU-MMD (CS) dataset. Only the last five rows utilize RGB at inference time. Note that Graph distillation (GD) learns from more than 4 modalities while our method learns from OF and Pose.

				mAP@tIoU (θ)
			Method	0.1 0.3 0.5
			JCRRNN [33]	45.2 -32.5
	Test modality	Poses RGB	Convolution Skeleton [36] 49.3 31.8 12.1 Skeleton boxes [1] 61.3 -54.8 Wang and Wang [57] 84.2 --Li et al. [32] 92.2 -90.4 Deep RGB [36] 50.7 32.3 14.7 Qin and Shelton [43] 65.0 51.0 29.4 GRU+GD [38] 82.4 81.3 74.3 SSTCN+GD 83.7 82.1 76.5
			Augmented-RGB	86.3 84.5 81.1

Table 7 .

 7 Comparison with State-of-the-Art action detection methods. Our method learns only from OF. The cells in white are the two stream results (RGB+OF), while the cell in orange represents using only RGB at Inference time. We report frame-based mAP and event-based mAP for the dense and sparse labeled datasets respectively. The IoU is 0.5 for THUMOS14.

	Type	Model	Charades	Dense TSU-CS	MultiTHUMOS	Sparse THUMOS14
		R-C3D [61]	12.7	8.7	-	28.9
	Anchor	TAL [3] G-TAD [62]	--	--	--	42.8 40.2
		AFNet [5]	13.1	-	-	49.5
		TAN [10]	17.6	-	33.3	46.8
		WSGM [15]	18.7	-	-	32.8
		TGM [42]	21.5	26.7	44.3	53.5
	Seq2Seq	Vanila-RGB [14]	22.3	29.2	37.8	46.1
		Two-stream	24.4	33.5	44.4	53.7
		Augmented-RGB	24.6	32.8	44.6	53.3

Acknowledgements. This work has been supported by the French government, through the 3IA Côte d'Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002. The authors are also grateful to the OPAL infrastructure from Université Côte d'Azur for providing resources and support.


Nicolas Bredeche
email: nicolas.bredeche@upmc.fr

Jean-Marc Montanier
email: jmmontanier@sobankrobotics.com

Simon Carrignon
email: simon.carrignon@bsc.es

Benefits of Proportionate Selection in Embodied Evolution: a Case Study with Behavioural Specialization

Keywords: •Computer systems organization → Robotics, •Computing methodologies → Arti cial intelligence, evolutionary robotics, embodied evolution, swarm robotics

We, as well as others, have already shown in previous works that reproductive isolation and a large population size are critical to achieve behavioral specialization in embodied evolutionary robotics. Here, we extend our previous work from [3] by experimentally demonstrating that tness-proportionate and rank-based selection operators largely outperform other selection operators when it comes to evolving behavioral specialization.

INTRODUCTION

Embodied evolution (EE), as a sub eld of evolutionary robotics, is dedicated to the design of distributed on-line learning algorithms for swarm/collective robotics [START_REF] Doncieux | Evolutionary robotics: What, why, and where to[END_REF][START_REF] Richard A Watson | Embodied evolution: Distributing an evolutionary algorithm in a population of robots[END_REF]. One major challenge is posed by the acquisition of behavioral specialization, i.e. where two (or more) sub-parts of a group of robots can evolve di erent decisionmaking strategies when required. As shown in previous works, this is far from trivial and may only be achieved under very speci c conditions.

In our own previous work [START_REF] Montanier | Behavioral specialization in embodied evolutionary robotics: Why so di cult[END_REF], we showed that reproductive isolation plays a major role to help bootstrap and maintain more than one genotypic signature in the population. * Corresponding author

In this paper, we extend our previous work to consider proportionate selection operators, either based on absolute tness values (i.e. tness proportionate selection) or relative tness values (i.e. rank-based selection). While other selection methods are now generally preferred by the community, proportionate selection retains an interesting feature when it comes to embodied evolution: by design, these selection methods are able to maintain polymorphism (i.e. population with more than one family of genotypes) by sampling from the whole population rather than from a truncated part.

We claim, and show in the following, that proportionate selection methods o er very e cient o -the-shelf solutions to achieve behavioral specialization in embodied evolutionary robotics.

METHOD

We use the exact same method we previously described in [START_REF] Montanier | Behavioral specialization in embodied evolutionary robotics: Why so di cult[END_REF] 1 . We provide a short summary here.Khepera-like robots are placed in a round environment where two resources can be found. Each robot may forage energy from one particular resource, but both resources must be foraged to allow the whole population to survive (i.e. each resource can only feed half the population). Foraging energy from resources serves two purposes: (1) to compute the tness value of the robot and (2) to enable the robot to move (i.e. a robot is removed from the experiment if its energy level drops to zero).

Each robot is driven by a simple perceptron (hyperbolic tangent activation function, no hidden layer) that maps sensory inputs to two motor output neurons (le and right motor speed). Perceptron's weights are evolved, as well as a particular gene, termed skill , that de nes the capacity to synthesize energy from each resource (i.e.

skill ∈ [-1, +1] , with each extreme value de ning a particular ability to synthesize from one of the two resources). e rationale is that to forage energy from one resource, a robot must both stand in the area where the resource is available and to be able to synthesize energy from it (which depends on the value of skill ).

e evolutionary algorithms used are simplistic versions of embodied evolution, with exchange of genetic material occuring in an on-line, distributed fashion among robots which are close enough to one another. A comparaison between several selection operators was performed in our original work, including random selection (as implemented in mEDEA [START_REF] Bredeche | Environment-driven embodied evolution in a population of autonomous agents[END_REF]) and performance-based selection (tournament and elitist selection operators).

We devise four experimental simulation setups, each de ned by the population size considered (either 200 or 500 robots) and the position of the resources with respect to one another (the SeperateEnv environment, where resources are found in di erent areas, and the more challenging ColocateEnv environment, where resources are co-located). In all setups, evolutionary adaptation is expected to converge towards an equilibrium between two families of genotypes, each specialized on one resource, whether reproductive isolation is possible or not.

In this paper, we implement tness-proportionate and rankbased selection operators. To some extent, proportionate selection operators share with random selection the propensity to sample from the whole population. ey also share with other performancebased selection operators the incentive to bias selection towards be er performance w.r.t. the objective function. e take-home message of this paper is thus the following: proportionate selection operators are very relevant when it comes to evolve behavioural specialization, thanks to a population-wide sampling method and performance-biased selection. is message, of course, has to be considered in conjunction with previous results [START_REF] Montanier | Behavioral specialization in embodied evolutionary robotics: Why so di cult[END_REF]: reproductive isolation and a large population size still play important roles in the outcome of evolutionary adaptation.

RESULTS

An open issue is that there is no clear distinction as to what is best between tness-proportionate and rank-based selection methods as each excels in speci c setups. Given the only di erence concerns the weight given to each individual using either absolute or relative tness values, there may be an optimal way to distribute the selection probability over the population, e.g. using a particular of non-linear rank-based tness assignement method. But the shape of this particular function may well depend on the task and the environment at hand.

Table 1 (

 1 resp. Table2) gives results with 200 (resp. 500) robots per population, for both environments. Each run falls in one of three categories, whether evolutionary adaptation completely failed (extinct), succeeded partly (one group, which implies only half the population was able to survive) or succeeded completely (two groups, meaning the whole population survived, with each group foraging energy from a particular resource).

				# runs
	selection	environment 2 groups 1 group extinct
	random	separateEnv	18	32	0
	tournament-5	separateEnv	8	37	5
	tournament-20 separateEnv	3	35	12
	elitist	separateEnv	1	31	18
	tness-prop	separateEnv	28	22	0
	rank-prop	separateEnv	13	37	0
	random	collocateEnv	2	42	6
	tournament-5	collocateEnv	1	33	16
	tournament-20 collocateEnv	0	16	34
	elitist	collocateEnv	0	18	32
	tness-prop	collocateEnv	1	44	5
	rank-prop	collocateEnv	4	46	0

Table 1 :

 1 Classi cation of the outcome of runs with a population of 200 robots. Classes are determined using the value of the skill's gene. 50 runs per experiment. Results in bold are new, other results are taken from[START_REF] Montanier | Behavioral specialization in embodied evolutionary robotics: Why so di cult[END_REF].Results clearly show that proportionate selection methods retain the bene ts of pure environment-driven selection (cf. random selection) and bene ts from optimizing a user-de ned objective function in even the most di cult collocateEnv environment.is is particularly prominent when the population size is large as selection pressure (resp. genetic dri ) is weaker (resp. stronger) in smaller populations. With a large population, proportionate selection methods outperform other methods by a large margin in the more di cult ColocateEnv environment, i.e. when there is no reproductive isolation to help evolve separate species in separate locations.

	# runs

Table 2 :

 2 Classi cation of the outcome of runs with a population of 500 robots. Classes are determined using the value of the skill's gene. 50 runs per experiment. All results are new.

h p://journal.frontiersin.org/article/10.3389/frobt.2016.00038/full

ACKNOWLEDGMENT

is work is supported by the European Union's Horizon 2020 research and innovation programme under grant agreement No.640891.