Kristijan Maček

Dizan Vasquez

Thierry Fraichard

Roland Siegwart

Safe Vehicle Navigation in Dynamic Urban Environments -A Hierarchical Approach

This paper describes the deliberative part of a navigation architecture designed for safe vehicle navigation in dynamic urban environments. It comprises two key modules working together in a hierarchical fashion: (a) the Route Planner whose purpose is to compute a valid itinerary towards the a given goal. An itinerary comprises a geometric path augmented with additional information based on the structure of the environment considered and traffic regulations, and (b) the Partial Motion Planner whose purpose is to ensure the proper following of the itinerary while dealing with the moving objects present in the environment (eg other vehicles, pedestrians). In the architecture proposed, a special attention is paid to the motion safety issue, ie the ability to avoid collisions. Different safety levels are explored and their operational conditions are explicitly spelled out (something which is usually not done).

I. INTRODUCTION

A. Background and Motivations

Autonomous mobile robots/vehicles navigation has a long history by now. Remember Shakey's pioneering efforts in the late sixties [START_REF] Nilsson | Shakey the robot[END_REF]. Today, the situation has dramatically changed as illustrated rather brilliantly by the 2007 DARPA Urban Challenge 1 . The challenge called for autonomous car-like vehicles to drive 96 kilometers through an urban environment amidst other vehicles (11 self-driving and 50 human-driven). Six vehicles finished the race thus proving that autonomous urban driving could become a reality. Note however that, despite their strengths, the Urban Challenge vehicles have not yet met the challenge of fully autonomous urban driving (how about handling traffic lights or pedestrians for instance?).

Another point worth mentioning is that at least one collision took place between two competitors. It was nothing serious but it raises the important issue of motion safety, ie the ability for an autonomous robotic system to avoid collision with the objects of its environment. With robotic systems designed to operate in the real world among human beings in many cases, motion safety becomes critical. The size and the dynamics of the Urban Challenge vehicles make them potentially dangerous for themselves and their environment (especially when driving at high-speed). Therefore, before letting such autonomous systems move among people, it is vital to assert their operational motion safety.

In the last forty years, the number and variety of autonomous navigation schemes that have been proposed is huge (cf [START_REF] Siegwart | Introduction to Autonomous Mobile Robots[END_REF]). In general, these navigation schemes aims at fulfilling two key purposes: reaching a goal while avoiding collision with the objects of the environment. When it comes to collision avoidance, once again, many collision avoidance schemes have been proposed. Their aim of course is to ensure the robotic systems' safety. However the analysis carried out in [START_REF] Th | A short paper about motion safety[END_REF] of the most prominent navigation schemes (ie the ones currently used by robotics systems operating in real environments, eg [START_REF] Borenstein | The vector field histogram -fast obstacle avoidance for mobile robts[END_REF], [START_REF] Minguez | Nearness diagram (ND) navigation: collision avoidance in troublesome scenarios[END_REF], [START_REF] Fox | The dynamic window approach to collision avoidance[END_REF], [START_REF] Fiorini | Motion planning in dynamic environments using velocity obstacles[END_REF]) shows that, especially in dynamic environments, motion safety is not guaranteed (in the sense that it is easy to find situations where collisions will eventually occur). To some extent, this is due to the fact that safety is a concept that is taken for granted. In other words, the meaning of safety is never formally stated and, above all, the operational conditions of such collision avoidance schemes are seldom (if never) spelled out.

B. Contributions and Paper Outline

In the past few years, the Autonomous Systems Lab. of the Swiss Federal Institute of Technology have been active with self-driving cars through the SmartTer initiative 2 . It has developed a navigation architecture that has evolved over the years. The primary purpose of this paper is to present the latest developments of the deliberative part of this navigation architecture. These developments are geared towards autonomous driving in dynamic urban environments with a particular focus on the motion safety issue.

The deliberative part of the architecture features two key modules working together in a hierarchical fashion: the Route Planner (high-level) and the Partial Motion Planner (lowlevel).

The purpose of the Route Planner is to provide the Partial Motion Planner with a valid route towards a given goal. A route in this case comprises a geometric path augmented with additional information based on the structure of the environment considered. Such a route should comply with the standard regulations for vehicles driving in a urban setting. This means that factors such as speed limits and stop signs should be taken into account.

It is up to the Partial Motion Planner to take care of all the gory details of the actual driving. It relies upon the route and a local model of the vehicle's environment (with up to date information about the fixed and the moving objects) in order to determine the next motion command to apply to the vehicle. As the name suggests, a Partial Motion Planning

II. NAVIGATION ARCHITECTURE

Fig. 1 presents an overview of the navigation architecture of the SmartTer platform. It is structured in layers, where, in most cases, higher level components interact with all the lower level layers in the hierarchy. The only exception is the world model, which is directly accessed by all the levels of hierarchy. Given that this paper focuses on route planning and partial motion planning we will just briefly discuss the high-level components and their interaction here. 1) Mission Manager. It is responsible of translating highlevel tasks (eg pick-up a person at an address) into initial and a goal configurations that the vehicle should reach in order to accomplish those tasks. 2) Route planning. It is concerned with finding a global route for the vehicle between the initial and goal configurations given by the mission manager, using information about the static characteristics of the environment (e.g. lane geometry, speed limits). We assume that knowledge about these characteristics is available a priori so that it is possible to perform at least part of the computations off-line.

III. ROUTE PLANNING

The goal of route planning is to exploit prior knowledge about the environment in order to provide local navigation with a feasible and valid path between two points of the environment. In this context, valid means that the path should be collision free and comply with traffic regulations for vehicles driving in a urban setting, where factors such as speed limits and stop signs should be taken into account by the planner.

More specifically, prior knowledge comes in the form of a slightly augmented 3 Route Network Definition File (RNDF) [START_REF]Route network definition file (RNDF) and mission data file (MDF) formats[END_REF]. This information may be seen as a directed graph (see fig 2) where we distinguish between two types of nodes, waypoints, having a special meaning (eg an intersection or a parking entrance) and standard nodes which are used as a piecewise linear approximation to describe higher order curves. Additionally, unstructured, open areas of the environment are described as polygons having entry and exit points that are connected to other nodes of the graph.

0 0 0 1 1 1 ICS free state state time T d π(t k ) π(t k-1 ) t k+2 s(t k+1 ) s(t k ) t k t k+1
From this graph, route planning is straightforward by applying the A* graph search algorithm using the length of the graph's edges as a cost function. Once a path has been found, it is smoothed out in order to guarantee its feasibility. The output of the module consists of a list of configurations

Q g = {q 1 g , • • • , q
Ng g } that the vehicle should reach. Each configuration can be described as a position, orientation and curvature:

q i g = {x i g , y i g , θ i g , κ i g } (1)
Associated with every configuration, there is a constraint vector describing the bounds within which the vehicle's motion is considered as acceptable with respect to the task at hand and the traffic rules (eg speed limits), as well as a Boolean flag wp i , whose value is true when the configuration corresponds to a waypoint and false otherwise:

c i = {r i max , ∆θ i max , ∆κ i max , v i min , v i des , v i max , wp i } (2)
where r i max stands for the maximum distance between the object's actual position and the desired one; ∆θ i max and ∆κ i max are the maximum error tolerated for the heading angle and the curvature, respectively; and v i min , v i des and v i max are the minimum, desired and maximum velocities associated to the given configuration.

IV. PARTIAL MOTION PLANNING

The Partial Motion Planner (PMP) is the core navigational module of the architecture. Its primary purpose is to determine the motion command u that is sent to the vehicle controller at every time cycle. The motion command u must meet the following requirements:

• Feasibility: it must take into account the dynamic constraints of the vehicle; • Goal Convergence: it must eventually drive the vehicle towards the desired goal. • Safety: it must ensure the safety of the vehicle, ie its ability to avoid collisions.

PMP operates iteratively with a time period T d which is determined by the environment (in an environment featuring moving objects, you have a limited time only to decide upon your future course of action otherwise you run the risk of being hit by a moving object). T d constitutes the decision time constraint.

To determine u, PMP (as the name suggests) applies the Partial Motion Planning principle [START_REF] Petti | Partial motion planning framework for reactive planning within dynamic environments[END_REF]: it tries to make the best possible use of the decision time T d available by computing a partial motion towards the goal. To that end, a diffusion technique is used to explore the state×time space of the vehicle and determine a partial motion π that is used during the next time cycle to drive the vehicle towards its goal. Fig. 3 illustrates how PMP operates. Let t k denote the current time instant and the beginning of the k th PMP cycle. The previous PMP cycle has computed the partial motion π(t k-1 ) that starts at time t k . The k th PMP cycle then has to compute π(t k ) that will start at time t k+1 = t k + T d . The process is repeated until the goal is reached.

At every cycle, PMP takes as input an updated model of the environment that comprises:

• the route computed by the Route Planner, ie the list

Q g = {q 1 g , • • • , q
Ng g } and the corresponding constraints Each partial motion π computed respects the dynamic constraints of the vehicle considered thus meeting the Feasibility requirement. By nature, PMP aims at maximizing the lookahead of the navigation process (the exploration of the future is carried out as far as possible given the decision time T d available). In our opinion, this is one way to meet the Goal Convergence requirement. Finally, each partial motion π computed will be safe in a predefined way (for instance, it will be guaranteed that the vehicle always have the possibility to brake down and stop before a collision occurs). This is the answer to the Safety requirement.

c i , i = 1 • • • N g (cf §III), • a list O s of
The next two sections respectively describe the diffusion technique used and how motion safety is handled.

V. DIFFUSION TECHNIQUE

The partial motion, ie the trajectory, that is to be computed for the vehicle can be described as a single parametric curve, eg polynomial or spline curve, or a concatenation of several geometrical primitives such as arcs or clothoids. The kinematic vehicle model is described by the Ackermann model:

ẋ = cos θ v l , ẏ = sin θv l , θ = v l L tan φ , (3)
with {x, y, θ} being the robot pose and {v l , φ} the longitudinal velocity and steering angle. Therefore the full vehicle state at the current navigation cycle t k can be described as:

s(t k ) = {x(t k ), y(t k ), θ(t k ), v l (t k ), φ(t k )} (4)
The dynamic update of the system can be described in the discrete general form:

ṡ(t k ) = f (s(t k ), u d (t k-1 )) (5)
where the dynamic level control input vector u d is the longitudinal acceleration vl (t k-1 ) and the steering rate θ(t k-1 ).

The dynamic update function f encapsulates the physical dynamic model of the vehicle, including inertia and physical forces acting on the vehicle itself.

If a low-level control is implemented separately (cascade control) which handles directly the actuators of the vehicle, ie gas pedal (longitudinal acceleration vl ) and steering wheel torque (steering rate θ), the system function f represents the closed-loop response of the vehicle with low-level control. Therefore, the actual commands issued from the Partial Motion Planning level are the kinematic control reference values:

u = {v l,ref , φ ref } (6)
The control vector u is derived directly from the planned trajectory π at each navigation cycle. Moreover, if the latency of the low-level control is very small in comparison to the navigation cycle T d , the closed-loop vehicle response to a kinematic control reference value u can be described with circular arcs (ie if the steering angle φ ref is kept fixed during time T d . Using arc geometric primitives largely reduces the computational costs that would be incurred if the full numerical integration through the system function f would be performed for possible input u.

In order to explore different possible trajectories, the geometric arc primitives are concatenated in a randomized sampled diffusion scheme, where the trajectory structure grows in a RRT ("Rapidly-Exploring Random Tree") manner [START_REF] Lavalle | Randomized kinodynamic planning[END_REF]. The motion exploration phase starts with the current 00 00 00 11 11 11 Firstly, the newly formed tree T is initialized by its root node τ root , where the information contained in each node is of the form:

s 3 (t k+2 ) s(t k+1 ) s 1 (t k+2 ) O d (t k+2 ) O d (t k+2 + T b ) s(t k ) s 2 (t k+2 ) π(t k-1 ) a 3 (t k+1 , t k+2 ) a 1 (t k+1 , t k+2 ) a 2 (t k+1 , t k+2 ) s 3 (t k+2 + T b ) q goal q rand π(t k ) s(t k+n ) = s ⋆ Fig. 4.
τ = {s, u, w τ ,t τ , d τ } (7)
The s represents the state of the vehicle, u the reference input that induced the state s, w τ the overall cost to reach the node τ, t τ the cumulative time with respect to the root of the tree T and d τ the node depth within the tree. Therefore, τ root which contains the predicted state s(t k+1 ) (PREDICT STATE) for the given control input u(t k-1 ) from the previous navigation cycle and zeroed cost, cumulative time and tree depth. The state prediction for the root node is necessary due to the fact that the currently computed trajectory π(k) will be available only at the end of the current navigation cycle (see Fig. 3). The L 1 contains all the nodes that are appended to the current tree depth d T . The overall computation time t s can only be within the T d span (Table I

.L5).

There are three tree expansion methods implemented in the current PMP scheme: 1) exploration: expansion towards a random configuration in the environment -q rand (Table I.L9-L13); 2) goal search: expansion towards a goal configurationq goal (Table I 3) exhaustive search: extension from a given tree node (state) using a randomized control input -u rand (Table I.L19-L23). These cases are depicted further in Fig. 4. In case 1, the predicted state s(t k+1 ) is expanded towards a random configuration q rand in the workspace (s 1 (t k+2 )), whereas in case 2 the tree T is expanded towards the goal con-figuration q goal (s 2 (t k+2 )). In both cases the function EX-TEND STATE SPACE first finds the node τ near in the tree T which is the closest to the chosen configuration according to a predefined distance metrics and than chooses the nearest feasible command with NEAREST COMMAND function. The case 3 represents the direct search in the control space of currently kinodynamically feasible commands with RAND COM SPACE (s 3 (t k+2 )).

For all the three possible expansion methods, the newly obtained nodes/states and the arcs a that connect them to their predecessor nodes in the tree have to be checked for collision against all the dynamic and static obstacles. This is done by discretizing the connecting arc trajectories a in time and verifying possible polygonal intersections resulting from the vehicle and obstacles intermediate configurations in the EXTEND WITH COLLISION CHECK function. Moreover, if the predecessor of an expanded node is at the depth d τ = 0, additional safety check has to be performed in the function EXTEND WITH SAFETY CHECK (Table I.L32-L40) -the vehicle must be able to come to a full-stop without collision (the state is therefore ICS safe, further details in §VI). In Fig. 4 this is depicted by the example of the break-state s 3 (t k+2 +T b ) originating from state s 3 (t k+2 ), where the collision-check test is performed for the duration of the breaking manoeuvre. The brake time T b is related to the dynamic capabilities of the vehicle, ie max linear deceleration vl,decc :

T b = v l vl,decc (8)
where the longitudinal velocity depends on each given state, in this case s 3 (t k+2 ).

As already mentioned, the diffusion process computation is limited to t s ≤ T d , where at each new computational increment another layer of nodes is added to the tree T . The final depth of T is not determined a-priori, nor how close the best trajectory will be with respect to the goal configuration. In Fig. 4 the final best trajectory is depicted with π(t k ), referring to the navigation cycle when it was computed, whereas the trajectory's final state s(t k+n ) can be arbitrarily far in the future (n is a free parameter).

Regarding the goal search, ie finding a trajectory towards a goal configuration, there are two approaches distinguished here:

1) waypoint following: the current set of waypoints Q g is the next topological node to reach in the environment (see Sec.III), such as an intersection, route crossing, lane changing waypoint, etc.; 2) route following: the current set of waypoints Q g is a collection of intermediate configurations, which together describe a route between topological nodes. In case 1 the cost function of a node to determine the best trajectory is based on a distance metric s -{q g , c q } between the goal waypoint with its constraints and the last state s on a trajectory:

w τ (s) = α g • s -{q g , c q } + α t • t τ (s) (9)
α g and α t are the weighting factors between minimizing the distance to the waypoint and minimizing the cumulative time t τ (s) to reach it, respectively. In case 2 there is more information available based on the environment structure, in the form of a route. These geometrical configurations can be followed with a type of path following technique, with the possibility of deviating from the route based on the tree structure, if the dynamic obstacles trajectories require such evasive manoeuvres. However, in the absence of dynamic obstacles O d and proper route definition according to the a-priori knowledge of static obstacles O s , the vehicle should follow the route as close as possible. Assuming that a path following controller (implementation details on the controller can be found in [START_REF] Solea | Trajectory planning with velocity planner for fully-automated passenger vehicles[END_REF], [START_REF] Macek | Path following for autonomous vehicle navigation with inherent safety and dynamics margin[END_REF]) computes an error function E which describes the discrepancy between a particular vehicle state s and the route Q g , then the cost of a node can be computed in the error terms as:

w τ (s) = Ns j=1 E(s j , Q g ) (10)
where the set of discretized states {s j=1 = s(k + 1) . . . s j . . . s Ns = s} with the associated arcs a forms a trajectory π. The cost calculation step is performed in the INSERT WITH COST function (Tab. I.L44-L47). The best trajectory π⋆ = π(k) which will be applied in the next navigation cycle can be therefore determined from node τ ⋆ with minimum overall cost w τ , iff τ ⋆ = ∅.

VI. SAFETY ISSUES

The purpose of this section is to explore the safety issues related to the navigation scheme proposed. The diffusion technique presented in §V aims at building a tree embedded in the state×time space of the system R and to extract from this tree a partial motion π that is used during the next time cycle to drive the system towards its goal.

The concept of Inevitable Collision State (ICS) 4 [14] and the motion safety criteria introduced in [START_REF] Th | A short paper about motion safety[END_REF] show that it does not suffice that each partial motion π be collision-free to ensure the safety of R. From a theoretical point of view, the safety of R is guaranteed if and only each π is ICS-free up to the time T d (that corresponds to the initial state of the partial motion that is to be computed at the next navigation cycle), because then, at the next navigation cycle, the navigation module always has a safe evasive manoeuvre available. Now, checking whether a given state of π is an ICS or not requires in theory the full knowledge of the environment of R and its future evolution, ie the knowledge of the spacetime W × [0, ∞). In practice however, one has to deal with the sensors' limited field of views and the elusive nature of the future. Knowledge about the environment of R is thus limited both spatially and temporally: it is limited to W p × [0, T p ] where W p ⊂ W denotes the subset of the environment which is perceived and T p the prediction horizon. To further ensure safety with respect to the objects that lie outside of W p , its boundary is treated in a manner similar to [START_REF] Th | Inevitable collision states. a step towards safer robots?[END_REF] or [START_REF] Alami | On the influence of sensor capacities and environment dynamics onto collision-free motion plans[END_REF] as a potentially moving object whose motion direction is unknown but whose velocity is upper-bounded.

W p × [0, T p ] and the objects within, fixed and moving, yields in the state×time space of R a set of ICS which is only an approximation of the true set of ICS generated by W × [0, T p ]. This is the very reason why it is impossible to guarantee an absolute level of safety (absolute in the sense that it can be guaranteed that R will never end up in an ICS and therefore crash eventually). This intrinsic impossibility compels us to settle for weaker levels of safety. Although weaker, the important thing is that such levels of safety will be guaranteed given the information that R knows about its environment, ie given W p × [0, T p ]. We have explored two different levels of safety, they are detailed in the next two sections.

A. Safety Level #1

The first safety level we have seeked to enforce is the simplest one maybe. It guarantees that, should a collision ever occur, R will be at rest. In other words, if a collision is inevitable, it can be guaranteed that R always have the possibility to brake down and stop before the collision occurs. Such a safety level is a form of passive safety in the sense that R will never actively collide with an object. It is henceforth called Passive Safety and denoted by PS.

Under PS, a state s is considered as being safe iff there exists at least one braking manoeuvre starting at s which is collision-free until the time where R has stopped. PS yields the following definition for a safe state:

Def. 1 (Passive Safety): a state s is safe under PS (or p-safe) iff there exists at least one braking manoeuvre starting at s and collision-free until T b , with T b the time where R is at rest (the braking time).

In practice, the function EXTEND.WITH.SAFETY.-CHECK (cf Table I) samples a finite and discrete set of braking manoeuvres and checks them for collision against W p × [0, T p ]. If one collision-free manoeuvre exists the state considered is labeled as p-safe and unsafe otherwise.

B. Safety Level #2

In a way, PS leaves most of the collision-avoidance burden to the other objects. In certain situations however, this is unsatisfactory: R may for instance decide to move on a railway track to reach its goal because, under PS, it is safe to do so (indeed R would have the time to stop before being hit by the train). Unfortunately, the train in spite of its best efforts may not be able to avoid crashing into R because of its own dynamics.

In an environment where the moving objects are assumed to be friendly, ie seeking to avoid collisions, and for which a certain knowledge about their dynamic properties is available, it can be desirable to enforce a stronger level of safety. This second safety level guarantees that, should a collision ever occur, R will be at rest and the colliding object would have had the time to slow down and stop before the collision had it wanted to. This safety level is henceforth called Passive Friendly Safety and is denoted PFS. It yields the following definition for a safe state:

Def. 2 (Passive Friendly Safety): a state s is safe under PFS (or pf-safe) iff there exists at least one braking manoeuvre starting at s and collision-free until T b + T ob , with T b the braking time of R, and T ob the maximum braking time of the moving objects present in the environment.

The conservative nature of Def. 2 should be noted. It is possible in practice to refine it in order for example to take into account the dynamics of the particular moving objects that would collide with R when it follows a particular braking manoeuvre. For the time being, Def. 2 is left as is.

Other safety levels could be proposed. The ultimate one of course is to determine safety with respect to the set of ICS which is defined by W p × [0, T p ]. Given the complexity of characterizing this ICS set, Passive Safety and Passive Friendly Safety constitutes interesting alternatives in the sense that they can be computed efficiently and provide an adequate level of safety.

VII. EXPERIMENTAL PLATFORM

A. SmartTer

The SmartTer is a passenger car equipped for autonomous driving. The system has a localization module based on sensor fusion, in the line of that described in [START_REF] Dissanayake | The aiding of a low-cost strapdown inertial measurement unit using vehicle model constraints for land vehicle applications[END_REF]. To accurately localize the vehicle, four different sensors are used: DGPS, IMU, optical gyro and vehicle sensors (wheel encoders and steering angle sensor). The combination of their measurements allows the estimation of the vehicle's 6 degrees of freedom eg the 3D position (x, y, z) and the attitude (roll, pitch, heading). The details of the localization system used are described in [START_REF] Lamon | The SmartTer -a vehicle for fully autonomous navigation and mapping in outdoor environments[END_REF]. Behind the windscreen we have the camera system, on the sides of the roof we have the tilted laser scanners for corner protection. Currently, the front Sick has been replaced by an Alasca Scanner.

For environment detection we use one IBEO Alasca XT laser scanner mounted at the front of the vehicle and two Sick LMS 291 mounted on the roof to protect the vehicle corners as well as a Sony Camera for vision.

B. Simulator

In order to facilitate system integration and to perform tests where the ground truth is available, we have performed our experiments using the Morsel simulator. Morsel has been developed in our laboratory and is based on the Panda3d engine [START_REF] Goslin | The panda3d graphics engine[END_REF]. Morsel features emulation for the two lower level layers of fig. 1. This includes cameras, range sensors, and standard cinematic models such as Ackermann, differential, etc.

The simulator can be easily extended using Python or C++. Another interesting feature is its ability run in "real" or "virtual" time modes. In the former mode, the simulator will try to produce sensor output at the real frequency; in the second mode time is emulated by putting world events in a priority queue according to their frequency. Since our system uses the Carmen [START_REF] Montemerlo | Carmen: Carnegie mellon robot navigation toolkit[END_REF] library for communications, low-level sensor and actuator driver modules are effectively decoupled from high-level algorithm. This makes it possible to plug the simulator to those algorithms in a transparent fashion.

VIII. SIMULATION RESULTS

Simulation results are presented in a generic environment, where no specific structure is present (eg parking lot), therefore, the navigation scheme based on waypoint following is applicable here (see §V, case 1) for goal search. The dynamic obstacles present in the Scene 1 (Fig. 6) and 2 (Fig. 8) are pedestrians and static and moving vehicles. The estimated obstacle positions and their future trajectories are depicted in navigation snapshots in Fig. 7 and Fig. 9, with the currently active waypoint is drawn as a circular region with a specified orientation (according to the given constraints). The trajectory diffusion starting from the ego-vehicle contains tree nodes that are free of obstacles (green) and prohibited nodes (marked red), whereas the currently best trajectory towards the waypoint is marked in magenta. Note that the given navigation snapshots are based on a certain time instant t k and that the prohibited regions depend on all the future motions of the obstacles. It can be seen from the results that the ego-vehicle is both able to reach the waypoint with the constraints included (Fig. 7), while negotiating moving obstacles, even preventing head-on collisions (Fig. 9).

IX. CONCLUSION AND OUTLOOK

This paper has presented the deliberative part of the navigation architecture for the SmartTer platform, comprising motion planning, which handles the actual execution of the plan while taking into account the dynamic elements of the world. A key aspect of the navigation architecture proposed is that a special attention is paid to the motion safety issue, ie the ability to avoid collisions in dynamic environments, under well defined operational conditions where different safety levels are cast explicitly, which is something that is usually neglected. The architecture has been implemented in both real and simulated platforms, although at the moment of writing, only simulated results are available. On the theoretical side, an interesting research direction is the exploration of more advanced motion prediction techniques in order to improve both the accuracy and the time horizon of our safety checks.

Fig. 1 .

 1 Fig. 1. Overview of the proposed navigation architecture.

Fig. 3 .

 3 Fig. 3. Partial motion planning iterative scheme.

Fig. 5 .

 5 Fig. 5. The SmartTer passenger car equipped for autonomous driving.Behind the windscreen we have the camera system, on the sides of the roof we have the tilted laser scanners for corner protection. Currently, the front Sick has been replaced by an Alasca Scanner.

Fig. 6 .

 6 Fig. 6. World view (scene1)

Fig. 7 .Fig. 8 .Fig. 9 .

 789 Fig. 7. Navigation output (scene1)

  World model. The world model gathers all the available information about the environment, including the vehicle's localization, the environment structure and the current and predicted states of the other objects that are present in the environment. As mentioned above, it is different from other modules because it interacts with all the levels of the hierarchy. The next two sections respectively describe Route Planning and Partial Motion Planning.

	4)
	3) Partial Motion Planning. It is responsible of execut-
	ing routes computed by the route planning module
	including collision avoidance and -for unstructured
	environments-motion planning. It integrates knowl-
	edge about the dynamic elements of the environ-
	ment,and interacts tightly with the world model.

  Os,T d ) 1 ts=0.0, d T =0; 2 s(t k+1 ) ← PREDICT STATE(s(t k ), π(t k-1 )); 3 τroot.init(s(t k+1 ), u(t k-1 ), 0.0, 0.0, d T ); 4 T .init(τroot), L 1 .init(τroot), L 2 =∅, τ⋆=∅; 5 while ts ≤ T d do

	6	for n=1 to |L 1 |
	7	τext ← L 1 .pop();
	8	p ← RAND();
	9	if (p < T .pr)
	10	q rand g	← RAND STATE SPACE(Os);
	11	τnew ← EXTEND STATE SPACE(q rand g	,. . . );
	12	if not (τnew = ∅) then
	13	INSERT WITH COST(τnew, Qg, T , L 2 , d T , τ⋆);
	14	if (T .pr ≤ p < T .pr + T .pg)
	15 16	q rand g τnew ← EXTEND STATE SPACE(q rand ← RAND SELECT(Qg); g	,. . . );
	17	if not (τnew = ∅) then
	18	INSERT WITH COST(τnew, Qg, T , L 2 , d T , τ⋆);
	19	else
	20	u rand ← RAND COM SPACE(u(t k-1 ));
	21	τnew ← EXPAND COM SPACE(τext, u rand ,. . . );
	22	if not (τnew = ∅) then
	23	INSERT WITH COST(τnew, Qg, T , L 2 , d T , τ⋆);
	24	end
	25 d T =d T +1;
	26 swap(L 1 , L 2 );
	27 UpdateTime(ts );
	28 end
	29 if not τ⋆ = ∅ then
	30	return PATH(T , τ⋆);
	31 else return failure;
	36 if not (τnew==∅) then
	37	τnew.dτ =τ.dτ +1;
	38	T ← T ∪ τnew;
	39	return τnew;
	40 else return ∅;
	EXTEND STATE SPACE(q g , T , O d , Os)
	41 τnear ← NEAREST NEIGHBOR(q g , T );
	42 unear ← NEAREST COMMAND(τnear, q g );
	43 return EXTEND COM SPACE(τnear , O d , Os);
	INSERT WITH COST(τ, Qg, T , L, d T , τ⋆)
	44 COMPUTE COST(τ, Qg, τ⋆);
	45 T ← T ∪ τ;
	46 if (τ.dτ ==d T +1) then
	47 L.push(τnew);
			TABLE I
	DIFFUSION PROCESS OF THE PARTIAL MOTION PLANNER

.L14-L18); PMP SEARCH(s(t k ), π(t k-1 ), Qg, O d (t), EXTEND COM SPACE(τ, u, O d , Os) 32 if (τ.dτ == 0) then 33 τnew ← EXTEND WITH SAFETY CHECK(τ, u,O d , Os); 34 else 35 τnew ← EXTEND WITH COLLISION CHECK(τ, u, O d , Os);

http://www.darpa.mil/grandchallenge.

http://www.smart-team.ch

RNDF's have been augmented by including speed limits. Fig. 2. Detail of final DARPA's RNDF file showing waypoints (red), standard nodes (blue) and unstructured areas (green polygons).

A state is an ICS iff a collision eventually occurs no matter how R moves.


Sébastien Bivaud

Sébastien Goeb

Vincent Croué

Paul Dron

Magali Allain

Marc Sallé

Self-Assembled Containers Based on Extended Tetrathiafulvalene

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Self-assembled exTTF Based Containers

Sébastien Bivaud, Sébastien Goeb,* Vincent Croué, Paul I. Dron, Magali Allain and Marc Sallé* LUNAM Université, Université d'Angers, CNRS UMR 6200, Laboratoire MOLTECH-Anjou, 2 bd Lavoisier, 49045 Angers Cedex, France Supporting Information ABSTRACT: Two original self-assembled containers constituted each by six electroactive subunits are described. They are synthesized from a concave tetratopic -extended tetrathiafulvalene (exTTF) ligand bearing four pyridyl units and cis-M(dppf)(OTf)2 (M = Pd or Pt; dppf = 1,1′bis(diphenylphosphino)ferrocene; OTf = trifluoromethanesulfonate) complexes. Both fully characterized assemblies present an oblate spheroidal cavity that can incorporate one perylene molecule.

Encapsulation of organic guests by discrete molecular cages is subject to an intense interest motivated by applications in various fields such as chemical sensing, chemical reactivity in confined space or even guest transport. [START_REF]Molecular Encapsulation: Organic Reactions in Constrained Systems[END_REF] Nevertheless, the synthetic access to the corresponding three-dimensional receptors is often challenging. From this point of view, the metal-driven self-assembly methodology constitutes a fruitful alternative which has led to a wide diversity of metallacages over the last decade. [START_REF] Amouri | [END_REF] On the other hand, the -extended tetrathiafulvalene framework (exTTF) exhibits unique geometric and electronic properties. 3 These peculiar features were recently successfully explored by N. Martín et al. who synthesized various macrocyclic covalent receptors incorporating two exTTF units. The resulting curved cavity display a remarkable affinity for fullerenes encapsulation. 3a,4 On this ground, and in the course of our studies related to the preparation of electron-rich polygons 5 and polyhedra, 6 we were interested in synthesizing metalla-cages based on the fascinating ex-TTF building block. Scheme 1. Synthesis of ligand 1. a) 4-iodopyridine (5 equiv.), cesium carbonate (12 equiv.), tri-tertbutylphosphonium tetrafluoroborate (0.75 equiv.) and palladium (II) acetate (0.25 equiv.), dioxane, reflux, 24h, 70%.

We report herein an expedient synthesis (two steps from the easily available native exTTF) of the first metalla-cages incorporating exTTF units and we demonstrate the ability of the resulting hosts to encapsulate a polyaromatic perylene guest. The tetrapyridyl-exTTF ligand 1 (Scheme 1) was synthesized in one step and in high yield directly from pristine exTTF, through a palladium catalyzed C-H arylation with 4iodopyridine. 7 Single crystals of the tetratopic ligand could be grown by slow diffusion of hexane in a dichloromethane solution of 1 and an X-ray diffraction study (XRD) was carried out (Figure 2a and SI). Ligand 1 displays the usual exTTF derivative butterfly shape 3 in the crystal, illustrated by a 86° dihedral angle between both 1,3-dithiol-2-ylidene mean plans. Scheme 2. Synthesis of cages 2a and 2b. a) cis-M(dppf)(OTf)2 (2 equiv.), nitromethane, 40°C; for 2a, M = Pd, 5 min, 95%; for 2b, M = Pt, 1h, 72%.

The self-assembly process of tetratopic ligand 1 with cis-M(dppf)(OTf)2 (M = Pd or Pt) complexes was carried out in nitromethane at 40°C and was monitored by NMR. In both cases, the reaction converged in less than one hour into a symmetrical discrete species (2a (M = Pd) and 2b (M = Pt)) that could be isolated in high yields (95% and 72% respectively) by precipitation from diethyl ether. Compared to ligand 1, compounds 2a and 2b present two high-field shifted  and  pyridine signals 8 in the 1 H NMR spectrum (Figures 1a,b, S4, S9). One singlet is observed for each of the S12). All these data confirm the formation of only one discrete self-assembled structure in each case. Noteworthy, the diffusion coefficients of 2a and 2b are identical and were extracted from the DOSY experiments (D  3.3 x 10 -10 m².s -1 ). This observation suggests that both self-assembled structures are of similar size, with an estimated hydrodynamic radius of 10.8 Å from the Stokes-Einstein equation (T = 298K), 9 a value which is compatible with the formation of discrete assemblies of the M4L2 type as shown in Scheme 2. ESI-FTICR mass spectrometry experiments were carried out with 2a and 2b and confirm a M4L2 stoichiometry in the gas-phase, as illustrated by the good accordance between isotopic experimental and theoretical patterns (SI), as well as by the characteristic multi-charged peaks corresponding to [M-3OTf] 3+ (m/z = 1588.6 (2a), 1706.7 ( 2b)) [M-4OTf] 4+ (m/z = 1154.3 (2a), 1248.8 (2b)) and [M-5OTf] 5+ (m/z = 964.4 (2b)) species (Figures S17 andS19). Single crystals of 2a and 2b could be grown by slow diffusion of diethyl ether in methanol and acetonitrile respectively. XRD experiments confirm the formation of M4L2 assemblies (Figure 2b,c (2a), Figure S20 (2b) and SI) and show in both cases an internal ovoid cavity of ca 15Å long over 9.5Å width. [START_REF]Distances between both central cycles of the anthraquinone unit and between two facing metal centers respectively[END_REF] The ligand unit preserves its butterfly shape within the self-assembled structures, but exhibits significantly enhanced curvature compared to 1, with a dihedral angle of 56° between the two 1,3-dithiol-2-ylidene mean plans (vs 86° in ligand 1). This value results in the formation of an elongated cavity suitable for inclusion of planar guests. Redox properties of ligand 1, as well as of containers 2a and 2b were studied by cyclic voltammetry (Figure 3). Ligand 1 shows the usual electrochemical behavior of exTTF derivatives, i.e. one two e -oxidation step to the dicationic species 1 2+ (E1 ox = 0.30V) and a poor electrochemical reversibility on the negative scan which is due to a geometrical reorganization from a planar fully aromatic species to a folded neutral derivative upon reduction from 1 2+ to 1. Both self-assemblies 2a and 2b exhibit two successive oxidation waves attributed to the exTTF core (E1 ox = 0.57V (2a), 0.65V (2b)) and to the ferrocene units (E2 ox = 0.80V) respectively, with four electrons exchanged in each case. Compared to ligand 1, oxidation of exTTF appears shifted to higher potential (+0.26V (2a) and +0.34V (2b)) and is not reversible. These two features are attributed to conjunction of two factors: i) coordination to metal centers contributes to reduce the -donating character of redox exTTF units (E1 ox increasing), and ii) the rigid character of the selfassembled structures 2a,b presumably hampers the redoxdriven conformational changes of the exTTF components which is usually observed with isolated exTTF derivatives. Interestingly, no change of the voltammograms was observed upon sequential redox cycling, outlining the chemical robustness of the self-assembled systems 2a,b. A remarkable feature of exTTF-based covalent macrocycles 3a,4 is their ability to bind guests in the cavity defined by the anthracenyl surface of their exTTF components. It is worth noting that in the case of containers 2a and 2b, the cavity surface is defined by the other concave fragment of the exTTF framework, i.e. the one containing both 1,3dithiol rings. Regarding the shape and the size of the ovoid cavity of 2a and 2b, inclusion of planar poly-aromatic guests such as pyrene, coronene and perylene was studied by NMR spectroscopy (Figure 1d, S14, S15, S16). Whereas no effect was observed with pyrene and coronene, the 1 H NMR spectrum of a stoichiometric CD3NO2 mixture of containers 2a (or 2b) and perylene appears notably modified compared to those of the individual components (Figure 1bd,S14,S16). The H and H pyridine signals are upshifted in the case of complexing cages 2a and 2b and become larger, as expected for a rapid exchange at the NMR time scale, which is confirmed by a COSY experiment (Figure S15). Likewise, the b and c perylene protons are fused into a single signal at 7.35 ppm upon encapsulation. Considering the cavity size, a 1:1 binding process was expected, which was confirmed by a ESI-FTICR mass spectrometry study upon analyzing a stoichiometric mixture of both entities (Figure 4 and Figure S18). 11 Peaks at m/z = 1014, m/z = 1305 (2b) and m/z = 1218 (2a) confirms inclusion of one perylene unit into the ovoid cavity. The association constants of the host-guest 1:1 inclusion complexes perylene2a and perylene2b could be determined from DOSY NMR titration experiments in CD3NO2, from a 1/1 ratio of host-guest mixtures (Figure 1d and S13, S15). 12 From these data (Table S1), Ka values of 3.9  0.1 x 10 3 (2a) and 3.2  0.1 x 10 3 (2b) could be calculated. In summary, an expedient two-steps procedure is proposed to reach the first examples of self-assembled 3D structures based on the electron-rich exTTF system. The first step involves a direct tetra-functionalization of pristine exTTF to afford the tetratopic ligand 1. The latter is then engaged in a metal-driven self-assembly procedure to reach stable containers 2a and 2b, which were characterized in solution as well as in the solid-state. Containers 2a and 2b, whose internal cavity is ovoid and is surrounded by six redoxactive electron-donating units, are stable upon successive oxidation-reduction cycling and show a good ability to include one perylene molecule. Considering the recent success of 2D exTTF covalent receptors in host-guest chemistry 4 and regarding the easy synthetic access to ligand 1 as well as to cages 2a and 2b through the metal-assisted strategy, we believe that such results are topical and open promising opportunities towards new 3D receptors designed on purpose for the binding of given neutral molecules.

  19 F and 31 P NMR spectra of 2a and 2b (Figures S5, S6, S10, S11), and the corresponding DOSY NMR spectra exhibit a single alignment of signals (Figures S8,

Figure 1 .

 1 Figure 1. 1 H NMR, downfield region (CD3NO2): a) 1, b) 2a, c) perylene (for assignation of a, b and c signals, see SI), d) DOSY NMR of a mixture of 2a and perylene (1/1, C = 2 x 10 - 3 M).

Figure 3 .

 3 Figure 3. Cyclic voltammogram of ligand 1 (C = 10 -3 M, CH3CN/CH2Cl2, 0.1M nBu4NPF6, 100mV.s -1 , Pt) and of containers 2a and 2b (C = 10 -3 M, CH3CN, 0.1M nBu4PF6, 100mV.s -1 , Cgr), V vs Fc/Fc + .

  3

Figure 2 .

 2 Figure 2. X-Ray crystal structures of: a) ligand 1, b) host structure 2a (lateral view), c) 2a (top view).

Figure 4 .

 4 Figure 4. ESI-FTICR of the stoichiometric mixture of 2b with perylene in CH3CN (C = 10 -3 M).

ACKNOWLEDGMENT

The authors gratefully acknowledge the CNRS and the Région des Pays de la Loire for a PhD grant (SB), as well as the PIAM (Univ. Angers) and the TGE «FT-ICR» (Drs Frédéric Aubriet and Vincent Carré, CNRS-Univ. Lorraine) for their assistance in spectroscopic analyses, and finally the Johnson-Matthey company for their generous providing of palladium and platinum salts.

ASSOCIATED CONTENT

Supporting Information Available: Detailed synthesis protocols, experimental methods, X-ray diffraction studies and additional spectroscopic data for ligand 1 and complexes 2a and 2b. This material is available free of charge via the Internet at http://pubs.acs.org.

AUTHOR INFORMATION

Corresponding Authors marc.salle@univ-angers.fr sebastien.goeb@univ-angers.fr


Jaime Castells

Mohammad Poul Doust
email: mohammad.poul.doust@etu.univ-st-etienne.fr

Luis Galárraga
email: luis.galarraga@inria.fr

Gonzalo Gabriel Méndez

Margarita Ortiz-Rojas

Alberto Jiménez
email: alberto.jimenez@cti.espol.edu.ecgmendez@espol.edu.ec

A Student-oriented Tool to Support Course Selection in Academic Counseling Sessions

Keywords: Learning Analytics, Academic Performance Prediction, Educational Data mining

Course selection and recommendation are important aspects of any academic counseling system. The Learning Analytics community has long supported these activities via automatic, data-based tools for recommendation and prediction. We contribute to this body of research with a tool that allows students to select multiple courses and predict their academic performance based on historical academic data. The tool is intended to be used prior to counseling sessions in which students plan their upcoming semester at the Ecuadorian university ESPOL. This paper presents the tool's design and implementation and discusses its potential to improve the student-counselor discourse.

Introduction

Advising students throughout their educational career is the main duty of any university counseling system [START_REF] Mostafa | A case based reasoning system for academic advising in egyptian educational institutions[END_REF]. An important aspect of academic counseling is the recommendation of courses to students. This task is usually performed by a designated counselor who assists students in selecting the most appropriate courses at a given point of their degree. This is possible thanks to the counselor's knowledge of the academic program as well as her ability to make good use of historical data. Such data can be used to, e.g., identify successful and problematic academic paths or to characterize the difficulty of the available courses [START_REF] Méndez | Techniques for data-driven curriculum analysis[END_REF][START_REF] Mendez | Curricular design analysis: A data-driven perspective[END_REF].

Despite the obvious benefits of academic advising in the mission of universities, course recommendations made by human counselors are not infallible. Recommendations can be inconsistent across counselors (with different counselors providing different advice to the same student), and across students (i.e., the same counselor can give different advice to students with a similar academic history). Recommendations can also be influenced by subjective factors. The perceived difficulty of a given course, for example, may depend on the counselor's personal learning/teaching experience.

To cope with some of these issues, recent research by the Learning Analytics community has proposed solutions to assist counselors in making better decisions [START_REF] Charleer | Learning Analytics Dashboards to Support Adviser-Student Dialogue[END_REF][START_REF] Gutiérrez | Lada: A learning analytics dashboard for academic advising[END_REF]. Nevertheless, course recommendation remains a time consuming activity that often needs to take place within a short period of time [START_REF] Grupe | An internet-based expert system for selecting an academic major: www. mymajors. com[END_REF]. Each student has a different history, a different set of strengths, and different preferences that make her unique. This implies that, for every new student, counselors will likely be confronted to previously unseen scenarios that require a dedicated analysis. Optimizing this task is of vital importance for universities as it incurs time and financial resources.

This paper reports the efforts made in this direction at the Ecuadorian university ESPOL 4 . We address the aforementioned issues with a tool that supports students in preparation for their academic counseling session and helps them decide which courses to take. We present here a prototype of our tool, which allows students to define arbitrary sets of available courses and predicts the student's performance. We also describe the data-oriented approach we took in designing our tool. This includes a description of how our prediction models take into account a student's own academic history, the performance achieved in the past by other students, and several difficulty estimators of the courses under consideration. We finally discuss the challenges and opportunities we have so far identified and present future research directions.

Related Work

Learning Analytics and Educational Data Mining focus on taking advantage of computational tools to collect and analyze educational data [START_REF] Long | Penetrating the fog: analytics in learning and education[END_REF][START_REF] Picciano | The evolution of big data and learning analytics in american higher education[END_REF][START_REF] Qu | Visual analytics for mooc data[END_REF]. Learning Analytics research efforts have sought to support academic programs stakeholders through visual interfaces for several purposes [START_REF] Vieira | Visual learning analytics of educational data: A systematic literature review and research agenda[END_REF]: to understand interactions within learning environments, to support instructional design, to explore learning progress, to understand forum discussions, to promote student reflection, and to identify students at risk of dropping out.

Other contributions from EDM and Machine Learning (ML) focus on the development of algorithms that better predict and discover facts from educational phenomena. Building upon these algorithms, a few tools support academic counseling activities (e.g., [START_REF] Aguilar | Perceptions and Use of an Early Warning System During a Higher Education Transition Program[END_REF][START_REF] Elcullada-Encarnacion | Academic Advising System using Data Mining Method for Decision Making Support[END_REF][START_REF] Roushan | University course advising: Overcoming the challenges using decision support system[END_REF]). Notable examples that take a visual approach in this category include LISSA [START_REF] Charleer | Learning Analytics Dashboards to Support Adviser-Student Dialogue[END_REF][START_REF] Millecamp | A qualitative evaluation of a learning dashboard to support advisor-student dialogues[END_REF], which assists counselors in planning enrollment of first-year students who have previously failed courses. LADA [START_REF] Gutiérrez | Lada: A learning analytics dashboard for academic advising[END_REF] is another counselor-oriented visual dashboard with planning and prediction modules that uses clustering to estimate a student's risk of failing chosen courses.

Both LISSA [START_REF] Charleer | Learning Analytics Dashboards to Support Adviser-Student Dialogue[END_REF][START_REF] Millecamp | A qualitative evaluation of a learning dashboard to support advisor-student dialogues[END_REF] and LADA [START_REF] Gutiérrez | Lada: A learning analytics dashboard for academic advising[END_REF] pay a lot of attention to the needs of academic counselors and policymakers. Less support has been provided to students within the context of academic counseling. KMCD [START_REF] Zhou | Knowledge-based major choosing decision making for remote students[END_REF] was a pioneer work in this space that sought to help students choose their majors. Our tool shares with the VLA tools and systems mentioned above, the goal of helping people gain insight from educational data. However, it mainly aims at supporting students to make more effective decisions. This objective situates our tool within the area of decision support systems, which seek to "help people overcome their biases and limitations, and make decisions more knowledgeably and effectively." [5, p. 3324]. Our tool, on the other hand, takes a visual approach to expedite the course selection and recommendation aspects of the academic counseling system of an actual higher education institution (HEI). To this end, it makes extensive use of EDM and ML techniques to provide personalized academic performance estimations.

Case Study: Academic Counseling at ESPOL

The Escuela Superior Politécnica del Litoral (ESPOL) is an engineering-oriented university in Guayaquil, Ecuador with over 10 000 students in its 32 undergraduate programs. Academic counseling was first established in ESPOL in 1991 with the purpose of helping students detect their strengths and needs, but it was not until 2013 that a formal, systematic academic counseling system was deployed.

Counselors are lecturers chosen by workload availability who are assigned, on average, twenty five students. Counseling sessions take place twice every semester: right before the semester begins for course-recommendation purposes and in the middle of the semester to monitor the student's progress. Each counseling period lasts about two weeks and students must meet with their counselors for a 15-minute session.

A common issue that we have identified through in-house observations at ESPOL is that counselors complain about the duration of the counseling session. They claim sessions hardly take under 15 minutes as students often need more time to decide on the courses they want to take. This is exacerbated when the students face particular issues that need to be addressed during the meeting.

Counselors have also reported that students seldom prepare themselves for the meetings in which they plan their upcoming semester. This lead to rushed decisions made on the fly, while talking to the counselor. These observations suggest that a system aimed to be used by students before they attend their counseling session could alleviate the counselor's workload. Ultimately, this would place more agency on the students' side regarding their academic choices.

Data-oriented Academic Advising

This work makes extensive use of Machine Learning (ML) techniques to generate models that can accurately predict the performance of a student in a given course. To this end, we consider the student's own academic history, her progress and followed academic path, and her target workload. We first describe the data used for our analysis (Sec. 4.1). This is followed by a description of the features that characterize students (Sec. 4.2) and the models we generated (Sec. 4.3).

Data

We analyzed a dataset containing the academic history of 2 543 Computer Science (CS) undergraduate students from ESPOL. This data spans the period 2002-2012. We worked with a simplified version of the CS curriculum previously studied in [START_REF] Méndez | Techniques for data-driven curriculum analysis[END_REF] and [START_REF] Mendez | Curricular design analysis: A data-driven perspective[END_REF]. This academic program is composed of 26 core subjects: seven basic science courses, sixteen of professional instruction, and three from the humanities category.

Feature Selection

Feature selection is the task of selecting the "signals" that provide most information about the variable we aim to predict. An example of a feature in our context is the grade of a student in a given course taken in a previous semester.

Based on our knowledge of the study program and the way students plan their semesters, we tested a set of features that provide information about the performance of students in a course. The list shown below describes the final set of features with which we characterize students:

Previous Grades: If course A is a pre-requisite of course B, it is natural to assume that the topics covered in A are necessary to understand the topics of B. This implies that if a student has performed well in A, she will likely succeed in B. On these grounds, to predict a student's grade in a given course, we used as input features her grades in all the corresponding pre-requisites5 as well as in previous trials of the target course. Since students may have multiple grades associated to a course (in case of failure), we always use the latest obtained grade as features. The only exception to this rule is the target course: if the student has grades from previous trials, we take the most recent of those grades, otherwise we do imputation by considering the average grade among all students that have passed the target course. Course and Semester Difficulty Estimators: Some courses are more difficult or demanding than others, which means that for some of them, students are more likely to obtain lower marks. Our model considers the difficulty of a course j through three different features. First, it characterizes the course's grading standard (α) and its grading stringency (β) as proposed by Caulkins et al. [START_REF] Caulkins | Adjusting GPA to Reflect Course Difficulty[END_REF]. These values are computed according to Equations 1 and 2, where GPA i represents the overall academic performance of student i; r ij is the student's grade in the course; and N j s is the total number of students that have taken the course. In general, the bigger the α j (> 1), the more difficult the course. On the other hand, β estimates how much on average the course j shifts all students' grades up or down. Therefore, the smaller the β is, the easier the course can be considered.

α j = i GP A i 2 i (r ij * GP A i ) (1) β j = i (GP A i -r ij ) N j s (2)
Our model resorts also to the skewness of the distribution (denoted by γ) produced by the distances between the GPAs of all the students that took a given course and their corresponding grade in that course. This estimator is part of the definition of β and has been used in data-driven curricular analyses [START_REF] Méndez | Techniques for data-driven curriculum analysis[END_REF][START_REF] Mendez | Curricular design analysis: A data-driven perspective[END_REF]. All these scores are computed from the academic history.

Failing History: The failing history of a student may convey hints about her skills or attitude towards the topic of a course. Hence, our model defines the repeating frequency of a student in a given course as the number of times the student has taken the course before passing it. This feature is equals to zero when the student intends to take the lecture for the first time.

Generated Models

We built training sets using the aforementioned features for different courses in the study program. For courses with few training points, we built training sets at the level of semesters. We did so by merging the records from courses usually taken together by students (i.e., they have common features) and adding an additional feature that identifies the course the record belongs to.

After testing different models such as linear regression, random forests and gradient boosting trees (GBT), we picked GBT for two reasons. First, it exhibits the best accuracy. Second, it allows us to deliver lowers and upper bounds for predictions by means of quantile regression [START_REF] Koenker | Quantile Regression[END_REF]. On the downside GBT models are not interpretable: one cannot know the exact effect of the input signals on the model's answer. This limitation supposes a problem in our scenario because a mere prediction does not suffice for proper counseling. Counselors always provide explanations for their predictions in order to support their arguments.

To overcome this shortcoming, we resorted to a post-hoc interpretability module. SHAP [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF] is a explanation layer for ML models that relies on game theory to calculate the contribution of each feature (called the Shapley value of the feature) to the answer of a black-box model. SHAP is based on linear attribution, i.e., if we denote by δ y the difference between the grade predicted by a model and the average grade, the Shapley value of a feature x measures the contribution of x to δ y . Our prototype uses SHAP on top of our GBT prediction model to show the features that contributed the most to a predicted grade.

Our Prototype

We integrated the outcomes of our data mining analyses within an interactive interface that enables students to plan out their upcoming semesters. The tool allows to compose sets of courses interactively and predicts for each the range the student's grade would fall in.

Program and Semesters Views

On opening the tool, the Program view shows the student's career program with courses organized into a grid and linked to their corresponding pre-and corequisites (Fig 1a). Courses appear color-coded according to their type (green for basic science, yellow for humanities, and purple for professional training). The grade of the courses that the student has taken appears in green if the course has been passed and in red otherwise. This view also shows the number of times the student took a given course (if greater than one). Courses that have been repeated are depicted as a group of stacked rectangles.

The Semesters view reorganizes the elements of the Program view to show individual enrollment instances. This view uncovers the elements of the stacks that represent repeated courses and depicts when, within her own academic history, the student took each course. Figure 1b shows the academic history of the student of Figure 1a, which spans a period of six semesters.

Prediction Mode

The interface provides a button to enable the prediction mode. Upon activation, courses in the Program view that the student has already passed are disabled. This also happens to those courses that the student would not be able to take because of missing requisites (Fig. 2.A). In the prediction mode, students can select (or deselect), via clicking, courses they may be interested in taking. Each new course selection or deselection triggers the execution of our prediction algorithms. In turn, this updates the content of the Prediction Results view, which shows the performance prediction for each selected course as a range on a horizontal range between 0 and 10 (Fig. 2.B). The range corresponds to the confidence interval of our GBT prediction. We decided against showing here the exact value predicted by our model as a single point. We wanted to convey the fact that the provided prediction is an estimate and, as such, it carries some uncertainty. We also felt that depicting a single value could mislead students and bias their expectations, which would be counterproductive for the goals we pursue.

The tool shows the prediction results in a red-yellow-green divergent color scale with a zero value of 6. This is the minimum grade required to pass a course in ESPOL. Figure 2.B shows the predictions results for a set of four courses. These results are quite optimistic for two of these courses (shown in the green part of the range), regular for one course (shown in between orange and green) and pretty pessimist about another (shown in a redish tone).

An additional view shows a breakdown of the the weekly workload the student would face due to their current course selection (Fig. 2.C). The load decomposition is shown as a bar chart with three categories: theory, autonomous work, and practicals. This visualization is also updated by the user's interactions on the Program view when in the prediction mode.

Supporting Understanding of Predicted Results

In addition to predicting the performance that a student could achieve in a given set of courses, an important goal of our tool is to provide insights on the reasons behind its predictions.

To this end, our current prototype provides access to the historic distribution of grades obtained by all the students that have passed a given course (Fig. 3a). This is possible by moving the mouse pointer onto a course of the Program view when the prediction mode is active. This visualization allows users to get an overall impression of a course's difficulty as it shows how other students from the same academic program usually perform.

The tool also provides an explanation of the factors that may have a critical impact in the student's performance. We provide a visualization of the Shapley values output by our interpretability module discussed in section 4.3. These visual explanations are available through the light blue icon shown to the left of each course on the Prediction Results view (Fig. 2.B).

An example of such visualization for the Human-Computer Interaction (HCI) course is shown in Figure 3b. Two horizontal bar charts show the ten features that have the more positive (green) and negative (red) impact on the predicted performance. The features are sorted by their contribution to the prediction outcome and their name and relative contribution are available through a tooltip that appears on hovering the bars of the visualization. In the depicted example, the feature that most contributes positively to the performance in the HCI course is the grade of Programming Fundamentals. That is, students with a good grade on the latter course are likely to perform well in HCI. On the other hand, the total weekly load of the semester assessed is the main factor that could negatively impact the student performance.

Open Questions and Future Work

Designing and implementing our tool posed several questions. In this section, we discuss some of them and outline directions for future research.

Dealing with curricular modifications: Academic programs are dynamic by nature. Often, courses are split or merged, some are created by the needs of the market and others disappear for similar reasons. Tracing these changes is vital to generate models that are consistent for all the students of an academic program. Some curricular modifications, however, can be particularly problematic. Consider the removal of an important predictor course. Estimating the performance of students who do not have a grade for this course will require a different model. However, the number of students to whom this change applies will be small right after the curricular modification is done. This, in turn, can lead to over-fitting. Improving explanations of predicted performance: Explainability is crucial to produce predictions that can be understood by humans. While we account for this by showing the relative contribution of the features used in our models, our current implementation is far from being explainable. These visualizations are not enough to fully open the AI black boxes we use.

One of our goals in this regard is to provide explanations of the predicted results in natural language. Ideally, this should consider not only the impact of the most prominent features, but also data on what makes a feature more or less understandable. This is a promising venue for future work that we will consider. However, the question of how to translate the models' output into fully human understandable language is out of the scope of this paper. Beyond a simplified program: Our prototype is part of an ongoing effort to improve and optimize the process of academic counseling at ESPOL. As reported in this paper, our tool works with a simplified version of the CS academic program that was valid between 2000 and 2012. Before and after this period, many curricular modifications took place at ESPOL. So, this limitation is mainly due to the unavailability of consistent data. Our immediate plans include to generate prediction models from more recent data. This, however, is not a trivial task as mapping courses among different versions of the curriculum can be challenging. We thus plan to ask for expertise on the transition rules that were applied between the performed curricular modifications. Need of empirical evaluation: Our research aims at supporting a human decision process via automatic prediction. Thus, assessing the perceived benefits of our prototype both on the students' and the counselors' side is of paramount importance. We plan to run several observational studies to gather users' impressions on the system and its usefulness. Pilots in more realistic settings will also be performed. These steps, however, require prediction models that can be used by current students.

Conclusion

This paper presented the design and implementation of a tool that supports students in preparation for the counseling sessions where they plan their upcoming semester. Given a selection of courses, the tool estimates the student's performance on each course. We described the data-driven approach used to generate the prediction models based on several factors such as the student's own academic history, the performance of other students, and several features that characterize the difficulty of courses. This research aims at improving and optimizing ESPOL's academic counseling system.

Fig. 1 :

 1 Fig. 1: Program and semesters view of a student's academic history.

Fig. 2 :

 2 Fig. 2: Prediction mode. Selecting courses on the Program view (A) results in the performance predictions shown in (B). The weekly workload is shown in (C).

  (a) Grades historic distribution (b) Relative impact of features

Fig. 3 :

 3 Fig. 3: Additional views available in the Prediction mode

Escuela Superior Politécnica del Litoral (http://www.espol.edu.ec)

Our results confirm this intuition: The best grade predictor of the performance of a student in a given course is typically her grade in the course's closest pre-requisite.

Acknowledgments

Work funded by the LALA project (grant no. 586120-EPP-1-2017-1-ES-EPPKA2-CBHE-JP). This project has been funded with support from the European Commission. This publication reflects only the views of the authors, and the Commission cannot be held responsible for any use which may be made of the information contained therein.