Nadav Voloch
email: voloch@post.bgu.ac.il

Priel Nissim

Mor Elmakies

Ehud Gudes

A Role and Trust Access Control model for preserving privacy and image anonymization in Social Networks

Keywords: Social Networks Privacy, Access control, Trust-based privacy models. 1

Over the last decade Online Social Networks (OSN) privacy has been thoroughly studied in many aspects. Some of these privacy related aspects are trust and credibility involving the OSN user-data conveyed by different relationships in the network. One of OSN major problems is that users expose their information in a manner thought to be relatively private, or even partially public, to unknown and possibly unwanted entities, such as adversaries, social bots, fake users, spammers or data-harvesters. Preventing this information leakage is the target of many OSN privacy models, such as Access Control, Relationship based models, Trust based models and many others. In this paper we suggest a new Role and Trust based Access Control model, denoted here as RTBAC, in which roles, that manifest different permissions, are assigned to the users connected to the Ego-node (the user sharing the information), and in addition, every user is evaluated trust wise by several criteria, such as total number of friends, age of user account, and friendship duration. An interesting extension of the model of image anonymization is also given, where a user that has a certain role with a proper permission can access a partial instance of the data, if a sufficient trust level is not achieved. These role and trust assessments provide more precise and viable information sharing decisions and enable better privacy control in the social network.

Introduction

Online Social Networks (OSN) privacy models have been a source of many researches over the past couple of years. Some of which focus on handling the OSN information sharing instances as an Access Control system, in which there is a selective restriction of access to the network's resources. The permission to access a resource is the main concern of the different models. The decision of giving a certain user authorization to such a resource is usually made by several criteria, based on many different factors.

Access Control models have different variations, some are more widely used than others. [START_REF] Levy | Sharing-habits based privacy control in social networks[END_REF] presents a new model for privacy control based on sharing habits on which, we have preliminary based our research. This model controls the information flow by a graph algorithm that prevents potential data leakage. This paper presents a new privacy model for access control in an OSN, in which the decisions of permission granting combines both pre-defined roles and trust-based factors derived from user-attributes, such as total number of friends, age of user account, and resemblance attributes between the two users. Similar attributes have appeared in a previous work ( [START_REF] Gudes | An Information-Flow Control model for Online Social Networks based on user-attribute credibility and connection-strength factors[END_REF]), which deals with information-flow control, and creates a model for adversary detection. However, in this paper we present specific parametric values for these attributes, which are experimentally based. The model's extension of a partial data visibility is used here in an implementation of image anonymization, in which a certain role that inherently has a permission of seeing images, can see a partial (relatively blurry) image if he does not gain the necessary minimal Trust value for getting the full permission.

The rest of this paper is structured as follows: Section 2 discusses the background for our work, with explanations on the related papers it relies on, Section 3 describes and defines our model thoroughly with several examples of its operation and presents its preliminary evaluation. Section 4 is the model's extension of partial data visibility for image anonymization in the OSN. Section 5 discusses the model and concludes it.

Background and related work

Access Control models, and specifically ones describing OSN privacy, have been studied extensively over the past decade. A major problem, existing especially in OSN, is an information flow to unwanted entities, violating the privacy of individuals. The main Access Control model used in OSN is Role-Based Access Control (RBAC) that has many versions, as presented in [START_REF] Sandhu | Role-based access control models[END_REF], and limits access by creating user-role assignments. The user must have a role that has permission to access that resource.

The most prominent advantage of this method is that permissions are not assigned directly to users but to roles, making it much easier to manage the access control of a single user, since it only must be assigned the right role.

To this model an addition of the Trust factor is done in [START_REF] Lavi | Trust-based Dynamic RBAC[END_REF], and it is based on the network users' interaction history, which could be problematic in assessing relatively unknown new connections. In this paper we circumvent this problem by adding independent user attributes to this estimation. An example of using RBAC specifically in Facebook is done in [START_REF] Patil | Undoing of privacy policies on Facebook[END_REF], that describes the use of roles in it and the possible breaches that can occur due to the flexible privacy settings of the network. [START_REF] Misra | IMPROVE-Identifying Minimal PROfile VEctors for similarity-based access control[END_REF] present a model named IMPROVE-Identifying Minimal Profile Vectors for similarity-based access control. It elaborates on this specific subject, and gives a 30-item list of attributes, some direct and some derived, that define the user information in an OSN.

We have based our Role and Trust Based Access Control (RTBAC) model on the above works, and it is presented in the following section. The novelty of our model is that the relationships and their strengths do not determine Access Control directly , but are used along with other characteristics to compute the trust of an OSN user in accordance with a specific Ego-user.

OSN Role and Trust Based Access Control (RTBAC)

The RTBAC model

The basic idea of the model is that besides the general roles given to different users, each user will be given a certain level of trust, and permissions to different data instances will be authorized only if the trust level passes a certain threshold. In this manner, the generalization disadvantage of RBAC can be solved, and better data distribution can be achieved. We should first emphasize the way, relative to a specific Ego-user, RBAC is generally used in an OSN. A user may belong to multiple hierarchic roles, but all of them are on a single path (as seen in [START_REF]Facebook help: roles[END_REF]). Therefore, when a user, and an Access chosen for it, is the lowest in the hierarchy it has the maximal set of permissions per role. We denote this role as R (U, Ego), but we will use just R as a short notation. The main contribution of RTBAC is the way Trust is computed.

Trust is computed by assigning values of credibility and connection strength to the different users, based on the criteria presented below. A minimum trust value threshold is the core condition of accessing a specific permission. The purpose of combining trust is to provide an additional stage of screening besides the RBAC roles. Another advantage of the model is that the combination of trust elements allows dynamic assignments of permissions to users over time, meaning their trust level can be dropped, and vice versa. The formal definition of the RTBAC model instance is as follows:

An RTBAC instance is a tuple <u_id, R, P(R), UTV, MTV, P(U)> where:

• u_id -the identification of a user connected to the Ego-node.

• R -the assigned user role of u_id, same as in RBAC

• P -An access permission to an OSN data instance In Fig. 1 we can see an example for the model's structure -The Ego-user is the user sharing the information. There are 7 other users in the system in this example, that obtain different roles. In this example, we give a minimal trust value (MTV) of 0.745 for a family member role to access the permission of "Tagging". This value can be altered per role and per permission in other cases. An Example of the trust decision making can be clearly seen in User 6. Users 6 and 7 have a "Family" role, but only User 7 achieves a trust value > 0.745 and gets the "Tagging" permission that User 6

does not obtain.

Criteria choice for Trust estimation

The choice of the attributes, for determining the level of trust for the model, is based on the criteria mentioned in the above sections, and the two main categories of criteria for our model are:

• Followers/Followees Ratio (FFR). The notation given to these factors is u. For example, uAUA is the value for the Age of User Account attribute.

Calculating Trust parameters' values

Setting the values for the Trust variables is done in this model in a scale of 0 to 1, since the decision of sharing information with a certain user is defined as a probability variable, 0 being no sharing willingness at all, 1 being definite sharing willingness.

All the parameters' values presented in this section are based on an experimental evaluation we have performed and is discussed in more detail in section 3.5 of this paper. The threshold values for TF, AUA, FD and MF are presented in Table 1, FFR is defined as a ratio by default, as well as OIR, while if one of these values is larger than 1, it is calculated as 1 for the model.

For the cRA value we take into consideration 10 of the users' attributes, based on the researches presented above (e.g. IMPROVE [START_REF] Misra | IMPROVE-Identifying Minimal PROfile VEctors for similarity-based access control[END_REF]), that resemble the Ego-user's attributes that are gender, age (range), current educational institute, past educational institute, current workplace, past workplace, current town, home-town, current country, home-country.

Let us denote the following factors:

• TAego is the total number of non-null attributes (from the 10 attributes mentioned above) of the Ego-user. The values of these attributes must be defined by non-null values.

• TRAego, other is the total number of non-null resembling attributes (from the 10 attributes mentioned above) of the Ego-user and the other user. The values of these attributes must be defined by non-null values.

Now we can define

cRA: cRA = 𝑇𝑅𝐴𝑒𝑔𝑜,𝑜𝑡ℎ𝑒𝑟 𝑇𝐴𝑒𝑔𝑜 (1)
This value cannot be larger than 1, since the maximal number of common attributes could be the total number of Ego-user's attributes at most. Now we can assess the access permission decisions by defining the total values of user credibility and connection strength in a manner of averaging the different factors noted above.

UTV = 𝑐•|𝑐|+𝑢•|𝑢| |𝑐+𝑢| = 4•𝑐+3•𝑢 7 (4)
The Minimal Trust Value (MTV) set in this model is based on the Trust-based dynamic RBAC model presented above and is altered per role and per permission by the user-preferences if such exist, or by an OSN administration policy, if such exists for these specific cases. It is important to state here that the users were not asked directly about the parameter values, but those were derived from the experimental evaluation that will be described in the following part of this paper. A certain user can set its own trust threshold dependent on his privacy preferences.

The values presented here are validated by the experimental evaluation but are subject to flexible changes by necessity.

In Table 2 we can see an example, portrayed in Fig. 1, where there is a difference between two users that have the same role, but not the same UTV, thus not getting the same permission. The MTV set for this specific role and permission (Family -Tagging) is 0.745, and User 6 achieves a UTV value of 0.44 and does not get the permission, whilst User 7 achieves a UTV of 0.84, thus gets the permission.

In the following parts we will see the model's algorithm, and the experimental evaluation done for determining its different parameters.

Experimental assessment and real OSN data estimation of Trust

As mentioned above, the experimental evaluation of the model's trust parameters consisted of two parts:

A. A validation of the parameters by a survey of 282 OSN users that were asked for the importance of various attributes in their decisions to grant various permissions to their private data. The survey included the quantifiable attributes of user credibility and connection strength. For all these attributes, the request was for the needed threshold value of Trust of a certain user. For example, an average of 245 total friends (TF) and above was considered as a trustworthy user, to which we can share information. The results of the most important ones are presented in Table 1. Two more aspects were examined in the survey: the importance (weight) of every one of the Resembling Attributes (RA) on a scale of 1 to 10, and the importance of every one of the model's Trust attributes.

B. In the second experimental evaluation we attempt to validate the trust computation in a real OSN dataset that included 162 user nodes and their attributes, all were friends of a single ego user. This dataset of user nodes was checked for the model parameters' Trust quantifiable attribute values mentioned in the previous parts. The nodes' UTV was calculated by the formulas presented above, and the average UTV achieved by the 162 users was 0.745. When we set the MTV threshold to 0.5, we get that only 3 users were denied access. The ego user confirmed that these three users should not have been in his friends' role.

4

The model's extension -partial access for data anonymization Our model's algorithm enables the complete access of information to highly trusted users or blocks it completely to undesirable ones. In this section we suggest an extension of the model such that the information access is generalized or anonymized based on the user's trust level and distance from the Ego-user. We demonstrate this idea using image anonymization, but it can also be applied to text, profile attributes and other information instances, similarly. The main idea of the model's extension of partial access is that a certain instance of data is not fully seen or unseen but can be partially scaled in its appearance. This option gives a wider information access, with the benefit of secure data anonymity. In image anonymization this feature helps reducing data leakage from facial recognition algorithms, vastly used in OSN and other Web applications. In Fig. 2 we can see the manifestation of such a partial access,

where Ego-user's profile picture is anonymized in the access granting seen in Fig. 1. For the given scenario we assume the value of 0.7 as the MTV, and the permission handled is the "visible pictures" that User 2 and User 3 obtain. User 1 does not see the image at all (left part of Fig. 2) since it does not have a fitting Role (he is "General" and the relevant Role is "acquaintance"). User 2 has a fitting Role but has a UTV of 0.56, hence he gets a blurrier image (middle part of Fig. 2) then User 3 obtains. User 3 has the fitting Role and the needed Trust value (UTV=0.71), thus he gets the full image (right part of Fig. 2). It is important to state here that this extension of the model is relevant only to these permissions that logically enable partial access.

Permissions of "sharing" or "tagging" are binary by nature, hence cannot allow a partial access model.

Discussion and conclusions

In this paper we have presented an Access-Control model for privacy in OSN. The novelty of our RTBAC model is its combination of User-Trust attributes, based on real OSN characteristics, in an RBAC, that usually grants permissions solely to roles, and by that improving the privacy features of the network. In this manner, it is better than current Role-based models, in which members of the same role (e.g. family or close friend) have the same set of permissions, disregarding their relationship with the Ego-user and other users, and not taking into consideration their dynamic behavior. Our model makes this permission's decision dynamic in time, since these attributes can change during time: The user gains or loses friends, its age of user account grows over time, etc. In addition, the model's extension of data anonymization is an important feature, that helps reducing the data leakage for OSN users, giving the OSN a better privacy infrastructure.

•Fig. 1 .

 1 Fig. 1. RTBAC model example of 7 users. Users 6 and 7 have a "Family" role, but only User 7 achieves a trust value > 0.745 and gets the "Tagging" permission.

•

  Connection strength (c): the connection strength of users is determined by characteristics that indicate their level of closeness such as Friendship Duration (FD), Mutual Friends (MF), Outflow/Inflow Ratio (OIR) and Resemblance Attributes (RA). The notation given to these factors is c. For example, cMF is the value for the Mutual Friends attribute. User credibility (u): the user credibly criterion assesses the user attributes that convey his OSN reputation and trustworthiness. These are Total number of Friends (TF) and Age of User Account (AUA) calculated from the time the user joined the OSN, and

  Wi) were the survey results for the significance (weight) of every attribute-factor (Ui or Ci) in u and c. They could theoretically be altered by other userpreferences or future results. We can now conclude the definition of the model's User Trust Value (UTV), taking into consideration that there are 7 attributes: 4 connection attributes and 3 user attributes (marked as |c| and |u|):

Fig. 2 .

 2 Fig. 2. Visibility of profile picture as seen by the users of Fig.1, with a threshold MTV of 0.7 Left: User 1, Middle: User 2, Right: User 3.

Table 1 .

 1 Threshold values for trust attributes

	TF	AUA (months)	FD (months) MF
	245	24	18	37

Table 2 .

 2 Difference in UTV between same-role users

	User WuTF WuAUA WuFFR WcRA WcFD WcOIR WcMF	u	c	UTV MTV
	6	0.44 0.33 0.89 0.4 0.67 0.13	0.22	0.55 0.36 0.44 0.745
	7	0.78 0.59 0.91 0.8 0.86 0.96	1	0.76 0.91 0.84 0.745

Acknowledgments

The authors would like to thank Eyal Pickholz for his assistance in the part of the model's extension of image anonymization and its software implementation. We also thank the BGU cyber center for supporting this project.


Joshua K Pickard
email: joshua.pickard@inria.fr

Vincent Padois
email: vincent.padois@inria.fr

Milan Hladík
email: milan_hladik@centrum.cz

David Daney
email: david.daney@inria.fr

Efficient Set-Based Approaches for the Reliable Computation of Robot Capabilities

Keywords: Interval analysis, robot capabilities, inner approximation, interval linear system, tolerance solution

To reliably model real robot characteristics, interval linear systems of equations allow to describe families of problems that consider sets of values. This allows to easily account for typical complexities such as sets of joint states and design parameter uncertainties. Inner approximations of the solutions to the interval linear systems can be used to describe the common capabilities of a robotic manipulator corresponding to the considered sets of values. In this work, several classes of problems are considered. For each class, reliable and efficient polytope, n-cube, and n-ball inner approximations are presented.

The interval approaches usually proposed are inefficient because they are too computationally heavy for certain applications, such as control. We propose efficient new inner approximation theorems for the considered classes of problems. This allows for usage with real-time applications as well as rapid analysis of potential designs. Several applications are presented for a redundant planar manipulator including locally evaluating the manipulator's velocity, acceleration, and static force capabilities, and evaluating its future acceleration capabilities over a given time horizon.

I. INTRODUCTION

T HE capability of a robot to autonomously adapt to an open dynamic environment is one of the ultimate challenges of robotics.

One of the keys to solve this challenge lies in the ability to dynamically control the motion of the robot as a function of the prediction of the environment dynamics in order to both optimally achieve the goals assigned to the robot while ensuring safety at all times. In other words, planning and control can no longer be considered as two separated problems solved sequentially. Indeed, this kind of approach works well only for simple robots evolving in static environments and solving basic tasks, where a large amount of time can be spent planning the motion offline and where the control problem consists of tracking, with almost no adaptation, the planned trajectory. Beyond the perception abilities needed to estimate the state of the robot with respect to its environment, dynamic contexts require to adapt the planned motion at all time. For this adaptation to be optimal, it should not be purely reactive but rather adapt the overall plan online, i.e., at each control instant. While the concept of online re-planning is appealing, it raises the question of the real-time tractability of the corresponding optimization problems. As explained in [START_REF] Ibanez | Optimization-Based Control Approaches to Humanoid Balancing[END_REF], in the very challenging case of humanoid robots, accounting for limited computation power, one can choose to make use of rather precise models of the robot's dynamics and constraints but the price to pay for this modeling complexity is the limited time horizon over which planning can be considered, leading to feasible but potentially sub-optimal robot behaviours. On the other hand, one can decide to plan over longer time horizons, for example using optimal control approaches or their receding horizon version such as Model Predictive Control (MPC). In return, one has to make use of simpler models to maintain a low computation complexity for online re-planning to be possible. This is typically the approach taken when planning for locomotion in humanoid robotics: given a target position in Cartesian space, one first computes a desired trajectory for an abstracted version of the system, typically its centre of mass (CoM) and the associated centroidal dynamics. Then one defines a sequence of contacts and associated stances that are both compatible with the desired CoM trajectory and physically viable. Finally, using a more complete model of the system, a whole-body control approach is used to compute the actuation inputs allowing to follow the trajectory joining two consecutive stances and associated contact states [START_REF] Tonneau | An efficient acyclic contact planner for multiped robots[END_REF]. The latter approach seems more appropriate in terms of the optimality of the obtained behaviours but also in terms of the involved computations. Indeed, while recent works on Differential Dynamic Programming [START_REF] Mastalli | Crocoddyl: An efficient and versatile framework for multi-contact optimal control[END_REF] tackle the full model problem over the full horizon, these approaches remain computationally too complex for online re-planning on real robots and it actually does not seem quite necessary to plan precisely joint level actuation over a long time horizon.

If approaches resorting to simplified models seem more appropriate, an abstract model of the system still requires to be connected to a more physically realistic one for control purposes. While this connection can be made through task level abstractions, it is also necessary to account for the low level limits of the robot at the planning level in order to produce plans that can be achieved by the robots given its intrinsic (e.g., joint limits) and extrinsic (e.g., collision avoidance) constraints. Often in robotics, accounting for the joint level limitations at the more abstract level of task description is a matter of manual tuning and heuristics as solving this problem formally and in a computationally efficient manner is complex. Going beyond simple heuristics and assuming constant task level acceleration capabilities (e.g. the ones provided by robot manufacturers), some work have been performed in the past to account for acceleration limits at the joint level while accounting for the potential incompatibilities between these acceleration limits and position ones [START_REF] Prete | Joint position and velocity bounds in discrete-time acceleration/torque control of robot manipulators[END_REF]- [START_REF] Decre | Extending itasc to support inequality constraints and non-instantaneous task specification[END_REF]. While of interest, these works fail short at accounting in a formal way for the true limits of robots which are best expressed at the joint level in terms of joint position, velocity, torque and torque derivative. Indeed, one of the main difficulties with joint level acceleration limits is that they are state dependant. This is all the more true when considering the expression of these limits in Cartesian space as the mappings from joint space to task space, being them at the static or dynamic level, are both state dependant and non-linear. In order to tackle this complexity, there is a need for new methodologies that are able to efficiently, accurately and with a limited computation cost predict the robot's capabilities in static but more importantly in dynamic scenarios. Furthermore, these methodologies should be able to handle imprecise/variable systems by accounting for system complexities such as sets of joint states and design parameter uncertainties to produce reliable results. Accounting for these uncertainties is of high importance when dealing with floating base systems such as humanoids or mobile robots in general [START_REF] Carvalho Filho | The impact of parametric uncertainties on mobile robots velocities and pose estimation[END_REF]. Thus, modeling errors and state changes over a given time horizon should be properly accounted for when computing capabilities.

With this overall motivation in mind, this work presents several classes of problems that can be used to reliably and efficiently compute polytope, n-cube, and n-ball inner approximations of the capabilities of robotic systems, being them imprecise or uncertain.

The descriptions of the capabilities of many robotics systems can be formulated in terms of linear systems of equations

A x = b (1)
with A ∈ R m×n , x ∈ R n , and b ∈ R m . These linear equations may be used to describe specific capabilities of a robotic manipulator for a unique configuration q or state {q, q}. In offline applications, the evaluation of robot capabilities allows to analyze the performance of a given design and may be used during the dimensional synthesis stage of robotic design. In online applications, the current and/or future robot capabilities can be computed and may be used to autonomously re-plan and control the motion of the robot. For example, for serial manipulators at the velocity kinematic level one may consider the:

• velocity kinematics model:

J(q) q = ẋ (2)
where J(q) is the Jacobian matrix, and q and ẋ are the joint and operational velocities respectively. • kinetostatic model

J(q) T f = τ (3)
where f is the operational wrench and τ is the joint torque/force vector.

At the dynamic level, one may also characterize the capabilities of a robot through the:

• forward acceleration model: J(q, q) q + J(q)q = ẍ (4)

where J(q, q) is the time derivative of the Jacobian matrix, and q and ẍ are the joint and operational accelerations respectively. • configuration-space dynamic model:

M(q)q = τ -c(q, q) -g(q) (5)
where M(q) is the mass matrix, c(q, q) is the centrifugal and Coriolis vector and g(q) is the gravity vector. • operational-space dynamic problem:

Λ(q)ẍ = f -µ(q, q) -p(q) (6)
where Λ(q) is the Cartesian mass matrix, µ(q, q) is the centrifugal and Coriolis vector in Cartesian space and p(q) is the gravity vector in Cartesian space.

Due to the many sources of uncertainties that exist (e.g., noisy sensor data, modeling errors), to reliably predict the capabilities of the robot it can be desirable to consider sets of robot models and states. Using interval analysis (see [START_REF] Moore | Interval analysis, ser. Prentice-Hall series in automatic computation[END_REF]- [START_REF] Moore | Introduction to Interval Analysis[END_REF]), it is possible to extend these problems in order to describe a family of problems that consider sets of values (e.g., sets of design parameters, sets of configurations [q], sets of joint velocities [ q], etc.). Figure 1 depicts a family of three-link planar manipulators with sets of link lengths, [l 1 ], [l 2 ], and [l 3 ], and sets of configurations, [q 1 ], [q 2 ], and [q 3 ], and shows the corresponding sets of positions associated with the distal ends of the links for the given configurations (53) and design parameters (51). The set of configurations may be used to model dimensional uncertainties in the system, and may also be used to model the temporal evolution of the system. The set-based approaches presented in this work can be used to reliably predict the robot's various capabilities for these type of problems, where the reliable and efficient evaluation of imprecise/variable systems and their current or future capabilities over a given prediction period provides many avenues for improving the performance and safety of robotic manipulators. Classes of problems may be described in terms of quantifiers which allow to describe reliable inner approximations of the capabilities of a robot over sets of values. Alternatively, reliable outer approximations may also be computed [START_REF] Popova | Outer enclosures to the parametric AE solution set[END_REF]- [START_REF] Popova | Inner and outer bounds for the solution set of parametric linear systems[END_REF], although these types of problems are not considered in this work. Considering velocity kinematics related models, when a set of configurations [q] are considered the Jacobian matrix J becomes an interval matrix [J]. Generally, the evaluation of [J] is overestimated due to the interval wrapping effect [START_REF] Neumaier | The wrapping effect, ellipsoid arithmetic, stability and confidence regions[END_REF] and dependency problem [START_REF] Nedialkov | Interval arithmetic, affine arithmetic, Taylor series methods: Why, what next?[END_REF] and there exists some matrices

J o ∈ [J] such that J o ∈ {J(q) | q ∈ [q]}.
Nevertheless, each J ∈ [J] has associated capabilities and the intersection of these capabilities describes the common capabilities for all configurations q ∈ [q]. This extends to the dynamic models similarly.

The interval analysis framework has proven to be a useful tool for the analysis and synthesis of robotic mechanisms as it guarantees certified numerical solutions to problems [START_REF] Merlet | Interval analysis for Certified Numerical Solution of Problems in Robotics[END_REF]. When combined with classical branch-and-bound approaches, entire parameter spaces can be thoroughly and reliably explored allowing the worst-case conditions throughout the parameter space to be properly understood. Such an approach has been widely used for workspace analysis, e.g., considering flexure-jointed mechanisms [START_REF] Oetomo | An Interval-Based Method for Workspace Analysis of Planar Flexure-Jointed Mechanism[END_REF], evaluating wrench capabilities [START_REF] Gouttefarde | Interval-analysis-based determination of the wrench-feasible workspace of parallel cable-driven robots[END_REF], [START_REF] Pickard | An interval analysis method for wrench workspace determination of parallel manipulator architectures[END_REF] and positioning errors [START_REF] Merlet | Appropriate design of parallel manipulators[END_REF], and computing collision-free poses [START_REF] Kaloorazi | Collision-free workspace of parallel mechanisms based on an interval analysis approach[END_REF] and singularity-free poses [START_REF] Merlet | Interval analysis and robotics[END_REF], [START_REF] Merlet | On the regularity of the inverse jacobian of parallel robots[END_REF].

By considering the intersections of manipulator capabilities for all values in the sets, this allows to compute common capabilities of the robotic manipulator corresponding to the considered sets of values. To reliably describe the capabilities of a robotic manipulator corresponding to a set of values, inner approximations of the intersections of manipulator capabilities must be computed. For a given interval linear system of equations, several classes of problems may be considered. The main contribution of this work is the development of efficient polytope, n-cube, and n-ball inner approximations which are applicable to each class of problem considered. Furthermore, these inner approximations are applied to several relevant robotics problems to demonstrate their capability to easily handle typical complexities such as sets of joint states and design parameter uncertainties.

The remainder of this paper is as follows. First, in Section II the relevant interval notations are introduced. Next, in Section III the classes of interval linear system of equation problems considered in this work are described. In Section IV the polytope, n-cube, and n-ball inner approximations for each class of problem are presented. Several applications are presented in Section V for a redundant planar manipulator to locally evaluate the manipulator's velocity, static force, and acceleration capabilities, and also its future acceleration capabilities over a given time horizon.

II. NOTATION

The interval extension of a variable x is given by

[x] = {x | x ≤ x ≤ x} ( 7
)
where x is the lower bound (infimum) x = inf (x) and x is the upper bound (supremum) x = sup (x) of the interval.

A few terms useful in this work are:

1) The midpoint of an interval is the real value given by

mid([x]) = 1 2 (x + x) (8)
2) The radius of an interval is the real value given by

∆ [x] = 1 2 (x -x) (9)
3) The mignitude of an interval is the real value given by

mig ([x]) = min({|x| | x ∈ [x]}) (10)
4) The magnitude of an interval is the real value given by

mag([x]) = max({|x| | x ∈ [x]}) (11)
5) The absolute value of an interval is the interval given by

|[x]| = [mig ([x]), mag([x])] (12)
Let a vector and matrix be given by x and A respectively. The interval extensions of the vector and matrix are then given by [x] and [A] and the previously described terms may be applied to each element in the vector or matrix. Classes of problems may be described with the ∀ (for all) and ∃ (there exists) quantifiers which allow to describe reliable inner approximations to the interval linear system of equations over the considered sets of values.

III. CLASSES OF PROBLEMS

Several classes of problems are considered in this work which are presented in a general form A x = b. These problems and their corresponding sub-problems are as follows.

A. Problems Ω ∀∃ ([A], [x]) and Ω ∀∃ (A, [x])
The first class of problems considered are of the form

Ω ∀∃ ([A], [x]) = {b | (∀ A ∈ [A])(∃ x ∈ [x])(A x = b)} (13) which applies a set of linear transformations [A] to a set of vectors [x]. The sub-problem Ω ∀∃ (A, [x]) = {b | (∃ x ∈ [x])(A x = b)} (14)
is geometrically a convex polytope [START_REF] Bouchard | On the ability of a cable-driven robot to generate a prescribed set of wrenches[END_REF]- [START_REF] Gouttefarde | Characterization of parallel manipulator available wrench set facets[END_REF]. Therefore, ( 13) is equivalent to the intersection of all sub-problems A ∈

[A]. That is, Ω ∀∃ ([A], [x]) = A∈[A] Ω ∀∃ (A, [x]) (15)
B. Problems Σ ∀∃ ([A], [b]) and Σ ∀∃ (A, [b])
The second class of problems considered are of the form

Σ ∀∃ ([A], [b]) = {x | (∀ A ∈ [A])(∃ b ∈ [b])(A x = b)} (16
) which is precisely the tolerance solution set of the interval linear system as described in [START_REF] Shary | A new technique in systems analysis under interval uncertainty and ambiguity[END_REF]. Considering the subproblem

Σ ∀∃ (A, [b]) = {x | (∃ b ∈ [b])(A x = b)} (17)
which is also geometrically a convex polytope, it is clear that

Σ ∀∃ ([A], [b]) = A∈[A] Σ ∀∃ (A, [b]) (18)

C. Robotics Use Cases

The use cases of each class of problem applied to the relevant robotics problems (2) -( 6) are outlined in Tables I and II. The classes Ω ∀∃ (A, [x]) and Σ ∀∃ (A, [b]) consider a unique configuration q or state {q, q} whereas the classes

Ω ∀∃ ([A], [x]) and Σ ∀∃ ([A], [b]) can consider a set of config- uration [q] or states {[q], [ q]}.

IV. INNER APPROXIMATIONS

A. Ω ∀∃ (A, [x]) Inner Approximations

Geometrically, polytope Ω ∀∃ (A, [x]) represents a so called zonotope [START_REF] Ziegler | Lectures on Polytopes, ser. Graduate Texts in Mathematics[END_REF]. The Ω ∀∃ (A, [x]) polytope can be obtained as the convex hull (conv) of the set of b associated with the

2 n vertices (vert) of [x]. That is, the Ω ∀∃ (A, [x]) polytope can be computed by Ω ∀∃ (A, [x]) = conv({b | (∃ x ∈ vert([x]))(A x = b)}) (19
) An equivalent non-iterative approach called the hyperplane shifting method, proposed in [START_REF] Bouchard | On the ability of a cable-driven robot to generate a prescribed set of wrenches[END_REF] and further improved in [START_REF] Gouttefarde | Characterization of parallel manipulator available wrench set facets[END_REF], may be used as a fast alternative in place of the convex hull routine. It requires to consider sub-matrices formed from all of the possible combinations of m-1 columns of A and directly computes the corresponding set of shifted hyperplanes.

Inner approximations of the largest inscribed n-ball and ncube can be computed from the half-space representation of the Ω ∀∃ (A, [x]) polytope. Let the half-space representation of the Ω ∀∃ (A, [x]), describing the associated set of b, be given by

H b ≤ d (20)
with H ∈ R k×m and d ∈ R k . The hyperplane shifting method provides an efficient means of evaluating the halfspace representation, especially when m is close to n as is common for many robotics problems.

Theorem 1 (Largest inscribed n-cube centered at b c ). If b c belongs to Ω ∀∃ (A, [x]), then the n-cube [c] = b c + r[e] (21)
where [e] is a vector of [-1, 1] intervals and

r = min i=1,...,k -h i b c + d i h i 1 ( 22
)
where h i is the i th row of H and • 1 is the 1-norm, is contained in Ω ∀∃ (A, [x]).
Proof. The Chebyshev center b c of a polytope yielding the largest inscribed n-cube can be determined by solving the linear program

max r subject to h i b c + r h i 1 ≤ d i r ≥ 0 i = 1, . . . , k (23)
The maximum value for r may be computed directly for a given b c as [START_REF] Kaloorazi | Collision-free workspace of parallel mechanisms based on an interval analysis approach[END_REF].

Many extensions have been considered for Theorem 1, especially on the topic of tolerance sensitivity analysis (see [START_REF] Wendell | Tolerance sensitivity analysis: Thirty years later[END_REF], [START_REF] Hladík | Tolerance analysis in linear systems and linear programming[END_REF]).

Theorem 2 (Largest inscribed n-ball centered at b c ). If b c belongs to Ω ∀∃ (A, [x]), then the n-ball B = {b | b -b c 2 ≤ r} (24) with r = min i=1,...,k -h i b c + d i h i 2 ( 25
)
where

• 2 is the 2-norm, is contained in Ω ∀∃ (A, [x]).
Proof. The Chebyshev center b c of a polytope yielding the largest inscribed n-ball can be determined by solving the linear program max r

subject to h i b c + r h i 2 ≤ d i r ≥ 0 i = 1, . . . , k (26)
The maximum value for r may be computed directly for a given b c as [START_REF] Bouchard | On the ability of a cable-driven robot to generate a prescribed set of wrenches[END_REF].

TABLE I INNER APPROXIMATION USE CASES FOR Ω ∀∃ (A, [x]) AND Ω ∀∃ ([A], [x]) Problems Unknown Description of Ω ∀∃ (A, [x]) Description of Ω ∀∃ ([A], [x]) J(q) q = ẋ ẋ { ẋ | (∃ q ∈ [ q])(J(q) q = ẋ)} { ẋ | (∀J(q) ∈ J([q]))(∃ q ∈ [ q])(J(q) q = ẋ)} J(q) T f = τ τ {τ | (∃f ∈ [f ])(J(q) T f = τ )} {τ | (∀J(q) ∈ J([q]))(∃f ∈ [f ])(J(q) T f = τ )} J(q, q) q + J(q)q = ẍ ẍ {ẍ | (∃ q ∈ [ q])( J(q, q) q = ẍ)} {ẍ | (∀ J(q, q) ∈ J([q], [ q]))(∃ q ∈ [ q])( J(q, q) q = ẍ)} +{ẍ | (∃q ∈ [q])(J(q)q = ẍ)} +{ẍ | (∀J(q) ∈ J([q]))(∃q ∈ [q])(J(q)q = ẍ)} TABLE II INNER APPROXIMATION USE CASES FOR Σ ∀∃ (A, [b]) AND Σ ∀∃ ([A], [b]). Problems Unknown Description of Σ ∀∃ (A, [b]) Description of Σ ∀∃ ([A], [b]) J(q) q = ẋ q { q | (∃ ẋ ∈ [ ẋ])(J(q) q = ẋ)} { q | (∀J(q) ∈ J([q]))(∃ ẋ ∈ [ ẋ])(J(q) q = ẋ)} J(q) T f = τ f {f | (∃τ ∈ [τ ])(J(q) T f = τ )} {f | (∀J(q) ∈ J([q]))(∃τ ∈ [τ ])(J(q) T f = τ )} M(q)q = τ -c(q, q) -g(q) q {q | (∃τ ∈ [τ ])(∃ q ∈ [q])(∃ q ∈ [ q]) {q | (∀M(q) ∈ M([q]))(∃τ ∈ [τ ])(∃ q ∈ [q])(∃ q ∈ [ q]) (M(q)q = τ -c(q, q) -g(q))} (M(q)q = τ -c(q, q) -g(q))} Λ(q)ẍ = f -µ(q, q) -p(q) ẍ {ẍ | (∃f ∈ [f ])(∃ q ∈ [q])(∃ q ∈ [ q]) {ẍ | (∀Λ(q) ∈ Λ([q]))(∃f ∈ [f ])(∃ q ∈ [q])(∃ q ∈ [ q]) (Λ(q)ẍ = f -µ(q, q) -p(q))} (Λ(q)ẍ = f -µ(q, q) -p(q))}
As an example, consider the Ω ∀∃ (A, [x]) problem given A = 0.8947 0.6707 0.2409 0.3348 0.3899 0.6958

, [x] =   [-1, 1] [-1, 1] [-1, 1]   . ( 27
)
The following inner approximations of Ω ∀∃ (A, [x]) are given in Figure 2:

• the associated polytope (purple);

• the largest n-cube centered at the origin with r = 0.4686 (red); • the largest n-ball centered at the origin with r = 0.6407 (green); • the largest n-cube with variable center with b c = (0.4855, 0.2823) and r = 0.4686 (dashed line); • the largest n-ball with variable center with b c = (0.2921, 0.1698) and r = 0.6407 (dashed line).

When reliable arithmetic operations are used which account for round-off errors, the computed inner approximations provide a reliable description of the solution of the linear transformation. In this example there is a diagonal line of optimal solutions corresponding to the parallel edges that the variable center inner approximation algorithm can return.

B. Ω ∀∃ ([A], [x]) Inner Approximations

As stated in [START_REF] Neumaier | The wrapping effect, ellipsoid arithmetic, stability and confidence regions[END_REF], the common capabilities are the intersection of the capabilities for all sub-problems A ∈ [A]. Since the capabilities associated with each sub-problem are geometrically convex polytopes, the common capabilities are the intersection of the convex polytopes for all sub-problems.

= (mid([A]) -diag(s) ∆[A]) x 1 -(mid([A]) + diag(s) ∆[A]) x 2 , x 1 , x 2 ≥ 0, x ≤ x 1 -x 2 ≤ x
is solvable for each s ∈ {±1} m , where diag(s) generates a diagonal matrix from the vector s.

Proof. For a fixed b, we have b ∈ Ω ∀∃ ([A], [x]) if and only if the linear system

b = A x, x ≤ x ≤ x (28) is solvable in variable x for each A ∈ [A]
. By [START_REF]Weak and strong solvability of interval linear systems of equations and inequalities[END_REF], this kind of strong solvability is equivalent to solvability of the system from the theorem statement.

The above test requires to solve 2 m linear systems. This can be a large number, however, it can hardly be decreased in general since the problem is intractable.

Theorem 4. The test b ∈ Ω ∀∃ ([A], [x]) is co-NP-hard. Proof. Suppose that [x] is sufficiently large. Then the test b ∈ Ω ∀∃ ([A], [x]) is equivalent to stating that for each A ∈ [A]
there is x such that A x = b. That is equivalent with claiming that the interval linear system [A] x = b is strongly solvable. Strong solvability is, however, known to be co-NP-hard [START_REF] Rohn | Linear programming with inexact data is NP-hard[END_REF]. The real valued right-hand side b of the linear system can be easily deduced.

To make the problem tractable, we first construct an inner approximation of Ω ∀∃ ([A], [x]) by a zonotope, that is, by a set of the form Ω ∀∃ (A, [y]) for some A and [y]. In particular, we will choose

A := mid([A]) and [y] := mid([x]) + [-r, r] ∆[x]. The task is now to compute as large as possible value r ∈ [0, 1] such that Ω ∀∃ (mid([A]), [y]) ⊆ Ω ∀∃ ([A], [x]
). Notice that this need not be satisfied even for r = 0, so we present a sufficient condition below.

Theorem 5. Suppose that mid([A]) has full row rank and put Thus it is sufficient to find [y] such that By choosing an appropriate x, the right-hand side can attain any vector in

r = min i=1,...,n   ∆[x] -|mid([A]) † | • ∆[A] • mag([x]) i ∆[x] i   , (29
Ω ∀∃ (mid([A]), [y]) + [z] ⊆ Ω ∀∃ (mid([A]), [x]) .
[-1, 1](1 -r) ∆[x]. Since the interval vector [z] is symmetric around zero, it is sufficient to compare the radii |mid([A]) † | ∆[z] ≤ (1 -r) ∆[x],
from which the statement follows.

This approach to computing an inner polytope approximation of Ω ∀∃ ([A],

C. Inner Approximations of Σ ∀∃ ([A], [b])

According to [START_REF]Solvability of systems of interval linear equations and inequalities[END_REF], a vector x belongs to

Σ ∀∃ ([A], [b]) (i.e., is a tolerance solution) if an only if |mid([A]) x -mid([b])| ≤ -∆ [A]| x | + ∆ [b] (30)
This allows to quickly verify if a desired property exists locally. Furthermore, the following theorems are proposed for directly computing inner approximations of the local capabilities, which may be used for real-time applications. The problems of computing outer approximations of the tolerable solution set have been addressed in [START_REF] Popova | Outer enclosures to the parametric AE solution set[END_REF].

Theorem 6 (Largest inscribed n-cube centered at x c ). If x c belongs to Σ ∀∃ ([A], [b]) then an n-cube [c] = x c + r[e] (31)
with

r = min i=1,...,m inf ∆ b i -|mid([b i ]) -[a i ]x c | [a i ] 1 (32)
where

[a i ] is the i th row of [A], is contained in Σ ∀∃ ([A], [b]).
The proof for Theorem 6 is given in [START_REF] Shary | Solving the linear interval tolerance problem[END_REF]. Notice that it provides the largest n-cube centered in x c . Notice also that it requires that the right-hand side of ( 32) is evaluated exactly. If we evaluate it by interval arithmetic, it provides a lower bound on the largest cube only. In [START_REF] Popova | Inner estimation of the parametric tolerable solution set[END_REF], the problems of computing inner approximations of the tolerable solution set are also considered.

On the other hand, the test To overcome the above drawbacks, we propose a more general method. It finds the optimal center point of the n-cube and it computes exactly its radius, too.

Theorem 7 (Largest inscribed n-cube with variable center).

The largest inscribed n-cube to

Σ ∀∃ ([A], [b]) reads [c] = x c +r[e]
, where x c , r is an optimal solution to max r (33a)

subject to j y i j ≤ b i , ∀i, (33b)
y i j ≥ a ij (x cj + r), (33c)
y i j ≥ a ij (x cj -r), (33d)
y i j ≥ a ij (x cj + r), (33e)
y i j ≥ a ij (x cj -r), (33f)
j z i j ≥ b i , ∀i, (33g)
z i j ≤ a ij (x cj + r), (33h) z i j ≤ a ij (x cj -r), (33i) z i j ≤ a ij (x cj + r), (33j) z i j ≤ a ij (x cj -r). (33k)
Proof. Our problem reads max r

subject to sup ([a i ](x c +r[e])) ≤ b i ∀i, inf ([a i ](x c +r[e])) ≥ b i ∀i.
Denoting by y i j and z i j the supremum and the infimum of the product [a ij ](x cj + r[-1, 1]), respectively, the resulting optimization model follows.

Notice that ( 33) is a linear programming problem, so it can be solved efficiently. The number of variables is 1 + n + 2mn, so the problem is still polynomially solvable.

Theorem 8 (Largest inscribed n-ball centered at x c ). If x c belongs to Σ ∀∃ ([A], [b]), then the n-ball B = {x | x -x c ≤ r} (34) with r = min i=1,...,m min inf -[a i ]x c + b i [a i ] 2 , inf [a i ]x c -b i [a i ] 2 (35)
where

• 2 is the 2-norm, is contained in Σ ∀∃ ([A], [b]).
Proof. According to [START_REF]Solvability of systems of interval linear equations and inequalities[END_REF], we know that any

x ∈ Σ ∀∃ ([A], [b]) must satisfy {A x | A ∈ [A]} ⊆ [b, b] (36)
Therefore, Σ ∀∃ ([A], [b]) is described by the convex polytope given by the following inequalities

sup ([a i ] x) ≤ b i , sup (-[a i ] x) ≤ -b i , x ∈ R n i = 1, . . . , m (37)
where sup ensures the inequalities are well-defined. In other words, [START_REF] Rohn | Inner solutions of linear interval systems[END_REF] describes the intersection of a set of half-spaces. For a given A ∈ [A], the largest n-ball centered at x c and inscribed to Σ ∀∃ (A, [b]) is computed by the linear program max r

subject to a i x c + r a i 2 ≤ b i , ∀i, -a i x c + r a i 2 ≤ -b i , ∀i, r ≥ 0, from which r = min i=1,...,m min -a i x c + b i a i 2 , a i x c -b i a i 2 .
Now, for the radius of the largest n-ball centered at x c inscribed to

Σ ∀∃ ([A], [b]) we just minimize subject to a i ∈ [a i ].
The theorem provides the largest n-ball which is centered in a given point x c . Notice also that it requires that the right-hand side of ( 35) is evaluated exactly. If we evaluate it by interval arithmetic, it provides a lower bound on the largest ball only. The elements of the right-hand side of [START_REF] Shary | Solving the linear interval tolerance problem[END_REF] fulfill the assumptions of the lemma. Since quasiconcave functions attain the minima on the border of the domain, we have the corollary below; the second item follows from the fact that ( 35) is monotone in some cases. Corollary 1. For every i, j we have:

(1) The right-hand side of ( 35) is attained for a ij ∈ {a ij , a ij }.

(2) If x cj ≥ 0 and a ij ≥ 0, then we can fix a ij := a ij in the first infimum of ( 35).

(3) If x cj ≤ 0 and a ij ≤ 0, then we can fix a ij := a ij in the first infimum of ( 35).

(4) If x cj ≤ 0 and a ij ≥ 0, then we can fix a ij := a ij in the second infimum of ( 35).

(5) If x cj ≥ 0 and a ij ≤ 0, then we can fix a ij := a ij in the second infimum of [START_REF] Shary | Solving the linear interval tolerance problem[END_REF].

Therefore, we may quickly check if x c belongs to Σ ∀∃ ([A], [b]) by using [START_REF] Wendell | Tolerance sensitivity analysis: Thirty years later[END_REF]. If so, the corresponding inscribed n-cube and n-ball are computed directly from [START_REF]Weak and strong solvability of interval linear systems of equations and inequalities[END_REF] and [START_REF] Shary | Solving the linear interval tolerance problem[END_REF] respectively. The proposed theorems are also valid for the Σ ∀∃ (A, [b]) sub-problems.

Theorem 9 (Inscribed n-ball with variable center). Denote s i := sup ( [a i ] 2 ) ∀i. Let r, x c , y be an optimal solution of the linear programming problem max r

subject to mid(a i ) x c +∆ a i y +rs i ≤ b i , ∀i, -mid(a i ) x c +∆ a i y +rs i ≤ -b i , ∀i, r ≥ 0, y ≥ x c , y ≥ -x c . ( 38
)
Then the ball

(34) is contained in Σ ∀∃ ([A], [b]).

Proof. As in the proof of Theorem 8, Σ ∀∃ ([A], [b]

) is described by [START_REF] Rohn | Inner solutions of linear interval systems[END_REF]. The Chebyshev center x c of a polytope can be determined by the linear programming problem which reads max r

subject to sup ([a i ]x c + r [a i ] 2 ) ≤ b i , ∀i, sup (-[a i ]x c + r [a i ] 2 ) ≤ -b i , ∀i, r ≥ 0 (39)
It is hard to express the suprema explicitly, so we estimate them from above, resulting in a lower bound to the maximum inscribed n-ball max r

subject to sup ([a i ]x c ) + rs i ≤ b i , ∀i, sup (-[a i ]x c ) + rs i ≤ -b i , ∀i, r ≥ 0 (40) Since sup ([a i ]x c ) = mid(a i ) x c +∆ a i | x c |,
we equivalently have [START_REF] Chiacchio | Evaluation of force capabilities for redundant manipulators[END_REF], where y substitutes for | x c |.

By the first item of Corollary 1, the largest inscribed n-ball is attained for a vertex of A. This is true not only for the fixed center x c , but even when the center is variable (because we can fix the center at the optimal one). This yields the following method of exponential complexity (with respect to the size of [A]). It remains an open question if the problem is computationally tractable or not.

Theorem 10 (Largest inscribed n-ball with variable center). Let r, x c be an optimal solution of the linear programming problem max r

subject to a i x c +r a i 2 ≤ b i , ∀i, ∀ a i ∈ vert([a i ]), -a i x c +r a i 2 ≤ -b i , ∀i, ∀ a i ∈ vert([a i ]), r ≥ 0. (41

The polytope Σ ∀∃ ([A], [b]

) may be represented as the set of all feasible solutions of a linear programming problem. The corresponding linear program [START_REF] Jaulin | Path planning using intervals and graphs[END_REF] was first presented in [START_REF] Rohn | Inner solutions of linear interval systems[END_REF].

Theorem 11. x ∈ Σ ∀∃ ([A], [b]) if and only if x = x 1 -x 2
is a solution to the system of linear inequalities

A x 1 -A x 2 ≤ b -A x 1 +A x 2 ≤ b x 1 ≥ 0, x 2 ≥ 0 (42)
The proof for Theorem 11 is given in [START_REF] Rohn | Inner solutions of linear interval systems[END_REF]. For example, given A as the transpose from ( 27 • the associated polytope (purple);

• the largest n-cube centered at the origin with r = 18.5082 (red); • the largest n-ball centered at the origin with r = 25.3333 (green);

• the largest n-cube with variable center with x c = (-1.0599, -3.1972) and r = 20.3591 (dashed line); • the largest n-ball with variable center with x c = (-2.5291, -0.6963) and r = 27.8666 (dashed line).

For comparison the polytope Σ ∀∃ (mid([A]), [b]) is also shown which necessarily contains the polytope Σ ∀∃ ([A], [b])

due to [START_REF] Oetomo | An Interval-Based Method for Workspace Analysis of Planar Flexure-Jointed Mechanism[END_REF].

where A † = (A T A) -1 A T , only ensures that the norm of the error b -A x is minimized. This error is zero and (45) has a solution if and only if the set of b belongs to the image (Im) of A. In [START_REF] Chiacchio | Evaluation of force capabilities for redundant manipulators[END_REF] the authors propose finding a reduced polytope that is given by the intersection [b] ∩ Im(A) and apply this method to solve the wrench problem of redundant serial manipulators. This approach has been recently extended to allow for online computation of the polytope [START_REF] Skuric | On-line force capability evaluation based on efficient polytope vertex search[END_REF]. For many robotics applications, this is equivalent to considering only the set of b that do not cause internal motions. For example, when considering the velocity kinematics model, only the joint states resulting in motions at the end-effector are considered, as states in the null space produce only internal motions. The associated x for each vertex of the reduced polytope can be computed from (45) and the convex hull of the resulting set gives the polytope Σ ∀∃ (A, [b]). The Σ ∀∃ (A, [b]) polytope for over-determined systems is given by

Σ ∀∃ (A, [b]) = conv({x | (∃ b ∈ vert([b] ∩ Im(A)))(x = A † b)}) (46)
The proposed n-cube and n-ball theorems (Theorems 6, 7, and 8) are also valid and applicable to the Σ ∀∃ (A, [b]) subproblems.

For example, given A as the transpose from ( 27) and

E. Inner Approximations Summary

The equations associated with each inner approximation for each class of problem are summarized in Table III. Software implementations of the proposed inner approximation algorithms are made available at [START_REF] Pickard | Software: Inner Approximation Algorithms for Interval Linear Systems of Equations[END_REF] for Matlab. To get an estimate of the computational times for typical 7-degree-offreedom redundant robotics applications, for each problem the mean computational times 1 and standard deviations (over 20 runs) evaluated for a random system with n = 7 and m = 6 are provided in Table III. The fixed center point is taken as the origin. It can be noted that the Matlab implementations are not optimized for speed and the computational times can be significantly reduced with more efficient implementations. However, the already low computational times for many of the inner approximations demonstrates the suitability for real-time applications.

V. APPLICATIONS

One application of this work is to improve the reliability of the computed capabilities, since all sources of error can be easily modeled and managed. Methods for reliably modeling sources of error are described within the appropriate design framework [START_REF] Merlet | Appropriate design of parallel manipulators[END_REF], [START_REF] Pickard | Appropriate analysis of the four-bar linkage[END_REF]. This allows to compute certifiable results providing confidence of the calculated capabilities of a manipulator. Other applications of this work are to provide reliable inner approximations of the common capabilities of a robotic manipulator over a given time horizon. This allows to reliably compute local capabilities, in real-time in many cases, that can be used online to evaluate the manipulator's current capabilities as well as its future capabilities within a time horizon.

As a simple example, consider a redundant three-link planar manipulator for a positioning task with point masses m 1 , m 2 , m 3 at distal ends of links of lengths l 1 , l 2 , l 3 . The manipulator is depicted in Figure 6. The manipulator's 2 × 3 Jacobian matrix is given by

J(q) = J 1 -sq 12 l 2 -sq 1 l 1 J 1 -sq 12 l 2 J 1 J 2 + cq 12 l 2 + cq 1 l 1 J 2 + cq 12 l 2 J 2 (47)
where q ijk = (q i + q j + q k ), sq i = sin(q i ), cq i = cos(q i ), J 1 = -sq 123 l 3 , and J 2 = cq 123 l 3 .

The 2 × 3 time derivative of the Jacobian matrix is given by

J(q, q) = -J 6 -J 3 -cq 1 l 1 q1 -J 6 -J 3 -J 6 J 5 -J 4 -sq 1 l 1 q1 J 5 -J 4 J 5 (48)
where qijk = qi + qj + qk , J 3 = cq 12 l 2 q12 , J 4 = sq 12 l 2 q12 , J 5 = J 1 q123 , and J 6 = J 2 q123 . 1 A desktop computer with a AMD Phenom(tm) II X6 1045T 2.70 GHz processor and 16.0 GB of RAM is used to compute mean computational times.

✲

✻ ( ✾ q 1 q 2 l 1 l 2 m 1 m 2 q 3 ◆ m 3 x y ❄ g l 3
Fig. 6. Three-link planar manipulator with point masses at distal ends of links.

The mass matrix, centrifugal and Coriolis vector, and gravity vector are given by

M(q) =   K 7 K 1 + K 3 + K 4 K 2 + K 6 K 1 + K 3 + K 4 2K 5 + K 4 K 5 + K 6 K 2 + K 6 K 5 + K 6 K 6   c(q, q) =   K 10 (K 8 + K 12 ) + K 11 (K 8 + K 9 ) q1 2 (K 8 + K 12 ) + K 9 K 11 -K 9 K 10 + q1 2 (K 8 + K 9 )   g(q) =g   cq 123 l 3 m 3 + l 2 cq 12 m 23 + l 1 cq 1 m 123 cq 123 l 3 m 3 + l 2 cq 12 m 23 cq 123 l 3 m 3   (49) where K 1 = l 1 l 2 m 23 cq 2 K 2 = l 3 m 3 (l 1 cq 23 + l 2 cq 3 ) K 3 = l 3 m 3 (l 1 cq 23 + 2l 2 cq 3 ) K 4 = l 2 2 m 23 + K 6 K 5 = l 2 l 3 m 3 cq 3 K 6 = l 2 3 m 3 K 7 = 2K 1 + 2K 2 + K 4 + l 2 1 m 123 K 8 = l 1 l 3 m 3 sq 23 K 9 = l 2 l 3 m 3 sq 3 K 10 = -(2 q1 q2 + q2 2 ) K 11 = -(2 q1 q3 + 2 q2 q3 + q2 3 ) K 12 = l 1 l 2 m 23 sq 2 (50)
with m ijk = m i +m j +m k , and g is the gravitational constant.

For the following examples, realistic parameters and joint state limits are selected to approximate a simplified planar model of joints 2, 4, and 6 of the Franka Emika Panda robot. The parameter values with assumed uncertainties are To visualize the effects of considering a set of configurations, for

[q] = (1.0, -1.0, 1.0) ± 0.1 rads (53) an approximation of the set of positions associated with the distal ends of the links is depicted in Figure 1. The proposed inner approximations provide a convenient means of evaluating the robot's common capabilities over the corresponding set of poses, provided that the intersection of capabilities is not empty.

A. Evaluating the Velocity Problem

A necessary procedure when analyzing the performance of a robotic manipulator is to evaluate the possible end-effector velocities through the mapping of known joint velocity limits with [START_REF] Tonneau | An efficient acyclic contact planner for multiped robots[END_REF]. The velocity problem is of the class Ω ∀∃ (A, [x]) and the associated inner approximations of section IV-A may be used to evaluate the possible end-effector velocities of the manipulator at a given configuration q. When considering a set of configurations [q], the manipulator's Jacobian matrix becomes an interval matrix and the associated inner approximations of section IV-B may be used.

At the following configurations

[q] = (0.0, -1.5708, 1.8675) ± 0.01 rads (54)

and with the joint velocities [ q] = [ qlim ] the inner approximations -associated polytope with r = 0.9136, largest n-cube centered at the origin with r = 0.4748 m/s, and largest n-ball centered at the origin with r = 0.6657 m/s approximations of Ω ∀∃ (J([q]), [ q]) -are given in Figure 7.

Analysis of the manipulator's velocity capabilities is performed by bisecting the joint configuration space (given in terms of an interval vector [q]) into a set of k sub-intervals [q 1 ], . . . , [q k ] at a desired resolution. Each sub-interval is used to evaluate an inner approximation of the corresponding n-ball centered at the origin, thus the continuous configuration space is completely explored without sampling. Plots of the values of r throughout the configuration space (see Figure 7) can be quickly generated and due to the independence of each subinterval the performance can benefit significantly from parallel computing. Furthermore, if given a desired velocity capability, a branch-and-bound loop can iteratively refine the joint configuration space [q] finding all satisfying configurations for a desired resolution. This has applications for trajectory planning in the redundant configuration space, where feasibility requires a connected path of satisfying configurations and planning involves selection of an optimal path [START_REF] Jaulin | Path planning using intervals and graphs[END_REF]. Note that the use of outer approximations of the manipulator's velocity capabilities, which are outside of the scope of this current work, can provide a complementary test allowing to quickly remove non-satisfying configurations from the branch-andbound loop.

Considering the relationship between the velocity kinematics model (2) and manipulability, the largest n-cube and nball inner approximations can be used to rapidly evaluate manipulability measures that correspond to given sets of robot states.

B. Evaluating the Kinetostatic Problem

Another necessary procedure when analyzing the performance of a robotic manipulator is to evaluate the possible end-effector wrenches through the mapping of known joint torque/force limits with [START_REF] Mastalli | Crocoddyl: An efficient and versatile framework for multi-contact optimal control[END_REF]. The kinetostatic problem is of the class Σ ∀∃ (A, [b]) and the associated inner approximations of section IV-D may be used to evaluate the possible end-effector wrenches of the manipulator at a given configuration q. For a set of configurations [q], the kinetostatic problem is of the class Σ ∀∃ ([A], [b]) and the associated inner approximations of section IV-C may be used.

At the same configurations (54) and with the joint torques [τ ] = [τ lim ], the inner approximations -associated polytope, largest n-cube centered at the origin with r = 67.3479 N, and largest n-ball centered at the origin with r = 85.1640 N approximations Σ ∀∃ J([q]) T , [τ ] -are given in Figure 8. In addition, the joint configuration space is bisected into subintervals and inner approximations of the corresponding n-ball centered at the origin allow to analyze the manipulator's force capabilities.

C. Evaluating the Forward Acceleration Problem

The local operational acceleration capabilities can be determined from the forward acceleration model [START_REF] Prete | Joint position and velocity bounds in discrete-time acceleration/torque control of robot manipulators[END_REF]. The problem can be split into two interval linear systems of equations where each system needs to be solved to give a corresponding set of operational accelerations (see Tables I). The Minkowski sum of the two sets then gives the local operational acceleration capabilities. Inner polytope approximations of the two sets of class Ω ∀∃ (A, [x]) or Ω ∀∃ ([A], [x]) are obtained from: ẍ1 = J(q, q) q ẍ2 = J(q)q (55)

Since each inner polytope approximation is convex, the Minkowski sum of the two sets is easily computed as the convex hull of all combinations of polytope vertices. The inner approximations ( 22) and ( 25) can then be applied. (Top) The associated inner polytope approximations for Ω ∀∃ ( J(q, q), [ qlim ]) and Ω ∀∃ (J(q), [q lim ]). (Bottom) The associated inner approximations for Ω ∀∃ ( J(q, q), [ qlim ]) + Ω ∀∃ (J(q), [q lim ]).

Let J(q, q) and J(q) be evaluated at the same configurations (54) and with the joint velocities

[ q] = (1.0, 1.0, 1.0) ± 0.01 rads/s (56)

As more uncertainties or variabilities in the system are considered, the greater the widths of the intervals in the matrices [A] become and therefore the greater the widths of the vectors [x] must be to in order to determine an inner polytope approximation with r greater than zero. Considering the joint state limits [ qlim ] and [q lim ], the resulting inner polytope approximations of Ω ∀∃ ( J([q], [ q]), [ qlim ]) and Ω ∀∃ (J([q]), [q lim ]) are r = 0.8446 and r = 0.9237, respectively (see Figure 9 top). The inner approximations of the operational acceleration capabilities is Minkowski sum of the two sets (see Figure 9 bottom) with: largest n-cube centered at the origin with r = 5.7386 m/s 2 , and largest n-ball centered at the origin with r = 7.7526 m/s 2 . While uncertainties may be largely ignored from a control point of view, accounting for these uncertainties is the only way to truly certify the capabilities of the system.

D. Evaluating Future Dynamic Capabilities

Let the current state of a robot be given by {q, q, τ } and let the joint state limits be given by the intervals {[q lim ], [ qlim ], [τ lim ]} and the control limit be given by the interval [ τ lim ]. Consider a prediction period interval [t] = [0, t max ]. The future joint torques [τ f ] are bounded by

[τ f ] = (τ + [ τ lim ][t]) ∩ [τ lim ] (57)
The future joint accelerations [q f ] are estimated from joint torque at the current state by

[q f ] = M(q) -1 ([τ f ] -c(q, q) -g(q)) . ( 58
)
The future joint velocities [ qf ] are given by

[ qf ] = q + [q f ][t] ∩ [ qlim ]. (59)
The future joint configurations [q f ] are given by

[q f ] = q + [ qf ][t] + 1 2 [q f ][t] 2 ∩ [q lim ]. (60)
The joint state limit intersections ensure that the limits are not exceeded during the prediction of the future set of states.

It is clear that joint acceleration capabilities are state dependent and therefore if constant joint acceleration limits are enforced, the controller may either require infeasible accelerations from the system or sub-optimally use its actual capabilities. Furthermore, due to the noise associated with the estimation of the current q, enforcing constant joint acceleration limits is difficult in practice. Alternatively, the use of joint torques to evaluate joint acceleration capabilities can provide a much better estimate of the capabilities of the system.

The joint acceleration capabilities achievable during the prediction period [t] can be determined from the configurationspace dynamic model [START_REF] Rubrecht | Motion safety and constraints compatibility for multibody robots[END_REF]. However, the right hand side of (5) should not be overestimated. Therefore, let the effective joint torques be given by [τ e ] = [τ f + cg, τ f + cg], where [cg] = -c([q f ], [ qf ]) -g([q f ]). Inner approximations of the joint acceleration capabilities are then computed from

M([q f ])q = [τ e ]. ( 61
)
The problem is of class Σ ∀∃ ([A], [b]) and the associated inner approximations of section IV-C may be used.

As an example, let the current states be given by ( 54) and (56) and τ = (18.0, 1.0, 2.0) ± 0.01 Nm (62)

Selecting the time [t] = [0, 0.01] s, the corresponding joint acceleration inner approximation polytope, the largest n-cube centered at the origin with r = 2.3382 rad/s 2 , and the largest nball centered at the origin with r = 3.2315 rad/s 2 are shown in Figure 10. For visibility reasons only, the polytope is bounded by the manufacturer's limits [q lim ].

The inner polytope approximation of the joint acceleration capabilities represents a set of valid joint accelerations which better describe the future operational accelerations during a prediction period [t]. This can be used in the form of inequality constraints inside the robot controller, augmenting the manufacturer's default limits, to ensure that the robot's capabilities are properly considered to select valid control actions.

VI. CONCLUSION

Efficient set-based approaches for computing reliable inner approximations of a robot's common capabilities over sets of joint states and with design parameter uncertainties are presented in this work. These approaches allow to not only consider the temporal evolution of the system over a small time horizon when computing the localized capabilities, but also allow to manage uncertainties to handle an imprecise/variable system describing a family of robotic manipulators.

The use of set-based approaches to evaluate capabilities provides many benefits over conventional approaches. One key benefit is the computation of certified inner approximations of the robot's capabilities, allowing these approaches to be used in offline and online scenarios to improve the safety of robotic systems. The ability to automatically handle design parameter uncertainties and other system uncertainties affecting performance (e.g., inertial parameter errors [START_REF] Giftsun | Robustness to Inertial Parameter Errors for Legged Robots Balancing on Level Ground[END_REF]) allows for the use of simpler imprecise/variable models that accurately describe a complex system (e.g., modeling flexurejointed mechanisms [START_REF] Oetomo | An Interval-Based Method for Workspace Analysis of Planar Flexure-Jointed Mechanism[END_REF]). Also, the ability to consider sets of joint states allows to locally evaluate capabilities over a small time horizon, such that the robot's performance in the near future can be better understood. The sets of joint states may also be used to analyze the capabilities along continuous trajectories via the use of branch-and-bound methods, as opposed to the standard sampling-based approach, allowing to properly understand worst-case conditions which can be used to improve the overall performance of the robot.

The low computation costs of many of the proposed inner approximations allow for real-time applications, enabling their use for rapid design analysis as well as their potential integration directly in to the robot controller. Therefore, a future application of this work may be the development of a certifiably safe robot controller which will use a properly formulated imprecise/variable system to safely estimate the robot's true capabilities over a given time horizon. These capabilities may then be used directly in the controller to ensure that each controller action is achievable. Furthermore, by computing and incorporating the robot's deceleration capabilities into the controller, it is be possible to enforce strict braking criteria to guarantee that collaborative systems are safe when in close proximity to a human.

Fig. 1 .

 1 Fig. 1. The sets of positions associated with the distal ends of the links for the set of configurations [q] = (1.0, -1.0, 1.0) ± 0.1 rads for a family of three-link planar manipulators with parameter values [l] = (0.3280, 0.3940, 0.1385) ± 0.001 m. The red, green, and purple regions are the corresponding positions of the distal ends of the first, second, and third links respectively.

Fig. 2 .

 2 Fig. 2. The associated polytope, n-cube, and n-ball inner approximations of Ω ∀∃ (A, [x]).

Theorem 3 .

 3 We have b ∈ Ω ∀∃ ([A], [x]) if and only if the linear system b

  ) where (•) † denotes the Moore-Penrose pseudoinverse. If r ≥ 0, then Ω ∀∃ (mid([A]), [y]) ⊆ Ω ∀∃ ([A], [x]). Proof. We want Ω ∀∃ (mid([A]), [y]) ⊆ Ω ∀∃ (A, [x]) for each A ∈ [A]. That is, for each y ∈ [y] there must be x ∈ [x] such that mid([A]) y = A x. Putting A := mid([A]) -A, we can write it as mid([A]) y + A x = mid([A]) x . When x ∈ [x] and A ∈ [A], the value of A x ranges in the interval [z] := [-1, 1] ∆[A]mag([x]).

  That is, for each y ∈ [y] and z ∈ [z], there must be x ∈ [x] such that mid([A]) y + z = mid([A]) x, or, equivalently z = mid([A])(x -y). If mid([A]) has full row rank, this equation can be deduced from mid([A]) † z = xy .

  [x]) by a set of the form Ω ∀∃ (mid([A]),[y]) is particularly convenient when the intervals in [A] are narrow relatively to those in [x]. In that case, the value of r is close to 1, and the inner approximation is tight. Inner approximations for the largest inscribed n-ball and n-cube in Ω ∀∃ ([A], [x]) may then be computed from the inner polytope approximation Ω ∀∃ (mid([A]), [y]) using Theorems 1 and 2 respectively.As an example, given A and [x] from (27) and adding uncertainties of [-0.01, 0.01] to each matrix element gives the following inner approximation of Ω ∀∃ ([A], [x]) shown in Figure3: • the associated polytope with r = 0.9289 (purple); • the largest n-cube centered at the origin with r = 0.4353 (red); • the largest n-ball centered at the origin with r = 0.5951 (green); • the largest n-cube with variable center with b c = (0.4510, 0.2622) and r = 0.4353 (dashed line); • the largest n-ball with variable center with b c = (0.2714, 0.1577) and r = 0.5951 (dashed line). For comparison the polytope Ω ∀∃ (mid([A]), [x]) is also shown which necessarily contains the polytope Ω ∀∃ ([A], [x]) due to (15).

Fig. 3 .

 3 Fig. 3. The associated polytope, n-cube, and n-ball inner approximations for Ω ∀∃ ([A], [x]). For comparison the polytope Ω ∀∃ (mid([A]), [x]) is also shown.

  [c] ⊆ Σ ∀∃ ([A], [b]) can be simply performed by interval evaluation [A][c] ⊆ [b]. Therefore, we can extend the above inner n-cube [c] by εinflation approach to [c] := [c] + ε[e] and repeat it while the test does not break.

Lemma 1 .

 1 The function f (a) = a T x+b a is quasiconcave on the domain a = 0, a T x + b ≥ 0. Proof. Let α ≥ 0 be fixed. The set of a = 0 satisfying f (a) ≥ α is characterized by a T x + b ≥ α a , which describes a convex set.

)

  Then the ball (34) is the largest ball contained in Σ ∀∃ ([A], [b]).

  ) and adding uncertainties of [-0.01, 0.01] to each matrix element and an arbitrary non-symmetric box [b] approximations of Σ ∀∃ ([A], [b]) are given in Figure 4:

Fig. 4 .

 4 Fig. 4. The associated polytope, n-cube, and n-ball inner approximations of Σ ∀∃ ([A], [b]). For comparison the polytope Σ ∀∃ (mid([A]), [b]) is also shown.

  [b] from (43), the box [b] and corresponding reduced polytope [b] ∩ Im(A), and the following inner approximations of Σ ∀∃ (A, [b]) are given in Figure 5: • the associated polytope (purple); • the largest n-cube centered at the origin with r = 18.8573 (red); • the largest n-ball centered at the origin with r = 25.7800 (green); • the largest n-cube with variable center with x c = (-1.0450, -3.3319) and r = 20.7430 (dashed line); • the largest n-ball with variable center with x c = (-2.5624, -0.7216) and r = 28.3579 (dashed line).

Fig. 5 .

 5 Fig. 5. (Top) The box [b] and the corresponding reduced polytope [b] ∩ Im(A). (Bottom) The associated polytope, n-cube, and n-ball inner approximations of Σ ∀∃ (A, [b]).

[l 1 ]

 1 = 0.328 ± 0.0001 m[l 2 ] = 0.394 ± 0.0001 m [l 3 ] = 0.1385 ± 0.0001 m [m 1 ] = 1.9 ± 0.001 kg [m 2 ] = 1.6 ± 0.001 kg [m 3 ] = 1.3 ± 0.001 kg (51)and the corresponding joint state limits (i.e., [q lim ], [ qlim ], [q lim ], [τ lim ], [ τ lim ]) are taken from the manufacturer'

Fig. 7 .

 7 Fig. 7. (Top) The associated polytope, largest n-cube centered at the origin, and largest n-ball centered at the origin for the example velocity problem Ω ∀∃ (J([q]), [ q]). (Bottom) A plot of the values of r throughout the configuration space (with [q 3 ] = 1.8675 ± 0.01 rads) for the largest n-ball centered at the origin.

Fig. 8 .

 8 Fig. 8. (Top) The associated polytope, largest n-cube centered at the origin, and largest n-ball centered at the origin for the example kinetostatic problem Σ ∀∃ J([q]) T , [τ ] . (Bottom) A plot of the values of r throughout the configuration space (with [q 3 ] = 1.8675 ± 0.01 rads) for the largest n-ball centered at the origin.

Fig. 9 .

 9 Fig. 9.

Fig. 10 .

 10 Fig. 10. Future joint acceleration capability inner approximations during a prediction period [t]. For visibility, the polytope is bounded by the manufacturer's limits [q lim ].

TABLE III INNER

 III APPROXIMATION SUMMARY.

	Approximations	Ω ∀∃ (A, [x])	ms ± std Ω ∀∃ ([A], [x])	ms ± std Σ ∀∃ (A, [b])	ms ± std Σ ∀∃ ([A], [b])	ms± std
	Polytope inner	(19)	56.842	(29) + (19)	56.719	(44) or (46)	187.374	(42)	381.568
	approximation		±1.090		±0.430		±0.982		±3.544
	Largest inscribed n-cube (19) + (22)	1.496	(29) + (22)	1.537	(32)	0.024	(32)	0.024
	centered at a point		±0.033		±0.030		±0.002		±0.001
	Largest inscribed n-cube (19) + (23)	20.748	(29) + (23)	20.807	(33) -exact	30.690	(33) -exact	33.154
	with variable center		±0.389		±0.310		±0.414		±0.675
	Largest inscribed n-ball	(19) + (25)	1.509	(29) + (25)	1.541	(35)	0.036	(35)	0.036
	centered at a point		±0.029		±0.023		±0.004		±0.002
	Largest inscribed n-ball	(19) + (26)	19.872	(29) + (26)	19.883	(38)	17.287	(38)	17.560
	with variable center		±0.322		±0.294		±0.181		±0.434
						(41) -exact	34.701	(41) -exact	48.459
							± 0.466		±0.481

This work was supported by the Czech Science Foundation Grant P403-18-04735S. J. K. Pickard was with Auctus, Inria -IMS (Univ. Bordeaux / Bordeaux


PhD Louis M Viollet
email: louis.viollet@hsc.utah.edu

MD Kathryn J Swoboda
email: kswoboda@mgh.harvard.edu

MD Rong Mao
email: rong.mao@aruplab.comhunter

PhD Hunter Best
email: hunter.best@aruplab.comyounahayouna.ha@aruplab.com

BSc Youna Ha

MD, PhD Annick Toutain
email: annick.toutain@univ-tours.fr

MD Lucie Guyant-Marechal
email: guyant-marechallucie.guyant@chu-rouen.fr

MD Cecile Laroche-Raynaud

MD Karima Ghorab
email: karima.ghorab@chu-limoges.fr

MD Marie Anne Barthez
email: ma.barthez@chu-tours.fr

MD, PhD; Yue Si

MD; Jean Michel Pedespan
email: jean-michel.pedespan@chu-bordeaux.fr

MD Xavier Hernandorena
email: xavierhernandorenaxhernandorena001@ch-cotebasque.fr

PhD; Anne-Sophie Lia

PhD Jean-Francois Deleuze

MSc Cecile Masson
email: cecile.masson@gmail.com

PhD Isabelle Nelson
email: isabelle.nelson@upmc.fr

PharmD Juliette Nectoux

Cecile Laroche
email: raynaudcecile.laroche@chu-limoges.fr

Si Yue

Genedx

Sophie Lia

A novel pathogenic variant in DYNC1H1 causes various upper and lower motor neuron anomalies

Keywords: Spinal Muscular Atrophy, Spastic Paraplegia, Motor neuropathy, Motor neuron disease, Dynein motor complex, Exome, Next Generation Sequencing DYNC1H1, Spinal muscular atrophies, Exome

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

Introduction

Motor neuron disorders from a large spectrum of inherited diseases including spinal muscular atrophies (SMA), familial amyotrophic lateral scleroses (FALS), hereditary spastic paraplegias (HSP) and overlapping phenotypes. Each of these diseases are genetically heterogeneous and are commonly classified by their mode of inheritance, the spatial distribution of muscle weakness, the age at onset, the severity and the occasional presence of additional clinical features. [START_REF] Peeters | Clinical and genetic diversity of SMN1-negative proximal spinal muscular atrophies[END_REF][START_REF] Baets | Genetic spectrum of hereditary neuropathies with onset in the first year of life[END_REF] Autosomal dominant Spinal Muscular Atrophy with Lower limb predominance (SMA-LED; OMIM# 158600) is a clinically well characterized type of SMA, with autosomal dominant inheritance, YUE Si -5 congenital or early childhood onset, lower limb predominant weakness and slow or absent progression. [START_REF] Fleury | A dominantly inherited lower motor neuron disorder presenting at birth with associated arthrogryposis[END_REF][START_REF] Frijns | Dominant congenital benign spinal muscular atrophy[END_REF][START_REF] Van Der Vleuten | Localisation of the gene for a dominant congenital spinal muscular atrophy predominantly affecting the lower limbs to chromosome 12q23-q24[END_REF][START_REF] Mercuri | Congenital form of spinal muscular atrophy predominantly affecting the lower limbs: a clinical and muscle MRI study[END_REF][START_REF] Harms | Dominant spinal muscular atrophy with lower extremity predominance: linkage to 14q32[END_REF] Two genes have been associated with SMA-LED: DYNC1H1 (Dynein Heavy Chain 1), coding for a major component of the Dynein-Dynactin motor complex and BICD2 (Bicaudal D2) a molecular partner of DYNC1H1. [START_REF] Harms | Mutations in the tail domain of DYNC1H1 cause dominant spinal muscular atrophy[END_REF][START_REF] Tsurusaki | A DYNC1H1 mutation causes a dominant spinal muscular atrophy with lower extremity predominance[END_REF][START_REF] Neveling | Mutations in BICD2, which encodes a golgin and important motor adaptor, cause congenital autosomaldominant spinal muscular atrophy[END_REF][START_REF] Oates | Mutations in BICD2 cause dominant congenital spinal muscular atrophy and hereditary spastic paraplegia[END_REF][START_REF] Peeters | Molecular Defects in the Motor Adaptor BICD2 Cause Proximal Spinal Muscular Atrophy with Autosomal-Dominant Inheritance[END_REF][START_REF] Punetha | Exome sequencing identifies DYNC1H1 variant associated with vertebral abnormality and spinal muscular atrophy with lower extremity predominance[END_REF][START_REF] Strickland | Mutation screen reveals novel variants and expands the phenotypes associated with DYNC1H1[END_REF][START_REF] Fiorillo | Novel dynein DYNC1H1 neck and motor domain mutations link distal spinal muscular atrophy and abnormal cortical development[END_REF][START_REF] Peeters | Novel mutations in the DYNC1H1 tail domain refine the genetic and clinical spectrum of dyneinopathies[END_REF][START_REF] Scoto | Novel mutations expand the clinical spectrum of DYNC1H1-associated spinal muscular atrophy[END_REF][START_REF] Niu | A novel DYNC1H1 mutation causing spinal muscular atrophy with lower extremity predominance[END_REF][START_REF] Ding | Identification of a de novo DYNC1H1 mutation via WES according to published guidelines[END_REF][START_REF] Rudnik-Schöneborn | Autosomal dominant spinal muscular atrophy with lower extremity predominance: A recognizable phenotype of BICD2 mutations[END_REF] Mutations in both of these genes cause lower and upper motor neuron diseases. Some DYNC1H1 mutations cause SMA-LED, others cause axonal Charcot Marie Tooth disease (CMT 20 ; OMIM# 614228) and some mutations cause hereditary spastic paraplegia (SPG3 ; OMIM# 182600) [START_REF] Tsurusaki | A DYNC1H1 mutation causes a dominant spinal muscular atrophy with lower extremity predominance[END_REF][START_REF] Strickland | Mutation screen reveals novel variants and expands the phenotypes associated with DYNC1H1[END_REF][START_REF] Peeters | Novel mutations in the DYNC1H1 tail domain refine the genetic and clinical spectrum of dyneinopathies[END_REF][START_REF] Weedon | Exome sequencing identifies a DYNC1H1 mutation in a large pedigree with dominant axonal Charcot-Marie-Tooth disease[END_REF] . Here we studied a large 3generation family with 21 affected members presenting bilateral lower limb weakness and muscle atrophy with neurological findings revealing a variable combination of upper and lower motor neurons defects among the individuals. Using a combined genetic approach, we identified a unique novel N-terminal tail domain heterozygous missense mutation (Ile609Thr) in the gene DYNC1H1 in all these individuals, which suggests a significant role of modifying genes in the neuronal expression pattern of DYNC1H1 gene mutations.

Patients and methods

Data Collection

Patients belong to a large three-generation pedigree with 21 affected individuals with ages ranging from 64 to 13 years (figure1). Patients with history of non-progressive bilateral pelvic girdle muscles weakness since childhood were considered affected. Medical records from 7 clinical centers in France (Tours, Limoges, Bordeaux, Rouen, Bayonne, Paris, Avignon) were reviewed for 18 affected individuals and electrophysiological studies were conducted in 16 of them. Peripheral blood DNA was obtained after informed consent from 20 affected and 15 non affected subjects.

Next generation sequencing (NGS) based multigene panel screening

YUE Si -6

NGS was performed on the proband (II16) using DNA extracted from whole blood. Proband's DNA sample (II16) was captured using the multigene panel for Charcot Marie Tooth diseases (NSPv.20 CMT NimbleGen, developped and validated by ARUP Lab) and sequenced with 2X100 bp paired end on an Illumina 2500 according to manufacturer's recommendation. Sequence variants were called with Genome Analysis Toolkit (v.1.6) and filtered using DbSNP, 1000 Genomes Project, 6500 Exomes and the ARUP internal database. In silico analyses of variants were performed using PolyPhen2 (http://genetics.bwh.harvard.edu/pph2/), SIFT (http://sift.jcvi.org/), and MutationTaster (http://www.mutationtaster.org/) to predict the possible disruption of protein functions.

DNA Sanger sequencing

Amplicon of DYNC1H1 exon 8 was amplified in the DNA of the 20 affected and 10 non affected individuals and sequenced using BigDye® Terminator Cycle Sequencing Kit (Applied Biosystems, Carlsbad, California) on an Applied Biosystems 3730 DNA Analyzer. Primer sequences are available upon request.

Haplotype analysis

A genome-wide scan analysis was performed among the DNAs of 15 patients, using 1,088 microsatellite markers with an average marker distance of 4cM (DeCode Genetics). Haplotype analysis at the candidate 14q32.2-q32.3 chromosomal region was performed in 20 affected individuals. Parametric computerized linkage analysis (MERLIN software) was made at the locus D14s979. For LOD score calculation, we used a model of rare autosomal dominant disease (prevalence 1.10,000), a 100% penetrance and a 0% phenocopy parameter. Allele frequencies at the selected locus were obtained from the online databases for Caucasian population (CEPH).

Results

YUE Si -7

Various neurological phenotypes in the same family

All the individuals examined presented childhood onset proximal weakness without deterioration of motor function over time. None of them had arthrogryposis or feet deformity at birth and all were able to walk independently at time of observation. Neurological examination and electrophysiological studies revealed remarkable differences with a variable combination of lower motor neuron disease symptoms (areflexia, distal muscle wasting, foot deformity, electrical denervation) and upper motor neuron symptoms (hyperreflexia, ankle clonus, abolished somatosensory evoked potentials). These findings are summarized in table 1. Five patients presented a pure lower motor neuron disease with a pattern of chronic denervation, corresponding to the typical SMA-LED phenotype (see patient III16 in table 2 and figure 2A). Five other patients, did not show evidence of denervation but exhibited spasticity in the lower limbs meeting the criteria of a pure hereditary spastic paraplegia (see patient II10 in table 2 and III14 in figure 2B). The other 6 patients presented an intermediate phenotype with lower and motor neuron disease symptoms (see patient III7 in table 2 and figure 2C). Mental function evaluation was not performed but most of the patients presented learning difficulties at school.

Identification of a novel tail domain mutation in the gene DYNC1H1

Next generation sequencing-based multigene panel in patient III16 allowed to identify a heterozygous variant, c.1826T>C, in the coding sequence of exon 8 of gene coding for the Heavy Chain 1 of Cytoplasmic Dynein (DYNC1H1). This variant, not previously reported in the literature or population databases, causes a missense mutation p.Ile609Thr at the protein level in a highly conserved region among vertebrate species. The mutation maps to the N-terminal region which is the dimerization domain at the stem of DYNC1H1, mediating the formation of dynein heavy chain dimers and interactions with dynein intermediate light chains. Ile609Thr is predicted to be pathogenic by the computational prediction programs (SIFT, PolyPhen and MutationTaster).

Whole genome sequencing in patient III16 and III3 showed the same heterozygous variant and YUE Si -8 no other pathogenic variants were identified in the currently known dominant genes that could lead to motor neuron defect. Targeted Sanger sequencing of DYNC1H1 exon 8 further showed the cosegregation of the variant, Ile609Thr, in the 20 affected individuals tested of this family. This variant was absent in the 10 non-affected individuals tested.

Genetic linkage to the DYNC1H1 gene locus on chromosome 14q32.3

Whole genome scanning and haplotype analysis on 20 affected individuals presenting the three previously reported clinical presentations refined the locus of the disease to the same chromosomal region containing the entire sequence of gene DYNC1H1 (14q32.3, between loci D14S1066 and D14S1007), cosegregating with an autosomal dominant pattern. Linkage analysis demonstrated a positive value with a maximum LOD score at marker D14s979 (Zmax=5.30) at the recombination fraction theta = 0.00 (data available on request).

Discussion

Spinal muscular atrophy with autosomal dominance inheritance is a clinically heterogeneous subgroup of hereditary motor neuropathies, involving multiple genes and various molecular pathways. [START_REF] Farrar | The Genetics of Spinal Muscular Atrophy: Progress and Challenges[END_REF] Among them, Spinal Muscular Atrophy with Lower limb predominance and autosomal dominant inheritance (SMA-LED) is a lower motor neuron disease recently described, characterized by almost exclusive involvement of lower limbs, proximal predominance of muscle weakness, frequent distal muscle wasting and mild or absent progression and a typical muscle MRI imaging pattern with a diffuse involvement of the quadriceps and a relative sparing of the adductor compartment 10 ,17 SMA-LED has been initially linked to mutations of gene DYNC1H1, a major component of the Dynein-Dynactin motor protein complex. The 30 reported DYNC1H1 mutations associated to the SMA-LED phenotype, [START_REF] Harms | Mutations in the tail domain of DYNC1H1 cause dominant spinal muscular atrophy[END_REF][START_REF] Tsurusaki | A DYNC1H1 mutation causes a dominant spinal muscular atrophy with lower extremity predominance[END_REF][START_REF] Punetha | Exome sequencing identifies DYNC1H1 variant associated with vertebral abnormality and spinal muscular atrophy with lower extremity predominance[END_REF][START_REF] Strickland | Mutation screen reveals novel variants and expands the phenotypes associated with DYNC1H1[END_REF][START_REF] Peeters | Novel mutations in the DYNC1H1 tail domain refine the genetic and clinical spectrum of dyneinopathies[END_REF][START_REF] Scoto | Novel mutations expand the clinical spectrum of DYNC1H1-associated spinal muscular atrophy[END_REF][START_REF] Niu | A novel DYNC1H1 mutation causing spinal muscular atrophy with lower extremity predominance[END_REF][START_REF] Ding | Identification of a de novo DYNC1H1 mutation via WES according to published guidelines[END_REF] are almost always located in the stem domain of the protein, while mutations located in the motor domain of DYNC1H1 are reported in malformations of cortical development (MCD) and intellectual disability [START_REF] Fiorillo | Novel dynein DYNC1H1 neck and motor domain mutations link distal spinal muscular atrophy and abnormal cortical development[END_REF][START_REF] Willemsen | Mutations in DYNC1H1 cause severe intellectual disability with neuronal migration defects[END_REF][START_REF] Poirier | Mutations in TUBG1, DYNC1H1, KIF5C and KIF2A cause malformations of cortical development and microcephaly[END_REF][START_REF] Hertecant | A novel de novo mutation in DYNC1H1 gene underlying malformation of cortical development and cataract[END_REF] without YUE Si -9 or with limited lower motor neuron involvement. We report in this study a novel DYNC1H1 mutation located in the stem domain, affecting both lower and upper motor neurons at various degrees, with a broad phenotypical range extending from a pure motor neuropathy to a pure spastic paraplegia. In fact, other DYNC1H1 tail domain mutations has already been reported in patients presenting Hereditary Spastic Paraplegia (HPN) [START_REF] Strickland | Mutation screen reveals novel variants and expands the phenotypes associated with DYNC1H1[END_REF] and the involvement of upper motor neurons has already been evoked in SMA-LED [START_REF] Scoto | Novel mutations expand the clinical spectrum of DYNC1H1-associated spinal muscular atrophy[END_REF] or even with MCD23 patients presenting hyperreflexia of the lower limbs. In our study a same DYNC1H1 mutation is associated with either a pure motor neuron disease (SMA-LED), a pure upper motor neuron disease (HSP) or an intermediate phenotype. This suggests that the type of neuronal expression might be influenced by other factors than by the protein variant itself. These factors could be epigenetic or more probably genetic, as suggested by the clustering of pure HSP phenotypes in a same branch of the family studied here (a mother with her 3 sons). Note that this pleotropic effect of a unique DYNC1H1 tail domain mutation has been reported by Tsurusacki et al, in a family with either autosomal dominant axonal CMT or SMA-LED phenotype. [START_REF] Tsurusaki | A DYNC1H1 mutation causes a dominant spinal muscular atrophy with lower extremity predominance[END_REF] A similar combination of upper and lower motor neuron diseases has been reported in the phenotypical spectrum related to gene BICD2 (Bicaudal D Homolog 2) mutations [START_REF] Oates | Mutations in BICD2 cause dominant congenital spinal muscular atrophy and hereditary spastic paraplegia[END_REF][START_REF] Peeters | Molecular Defects in the Motor Adaptor BICD2 Cause Proximal Spinal Muscular Atrophy with Autosomal-Dominant Inheritance[END_REF] , a key adaptor protein interacting with DYNC1H1. BICD2 mutations are responsible for a pure autosomal dominant spinal muscular atrophy phenotype (SMA-LED2), a pure HSP and a phenotype combining lower limbs hyperreflexia and SMA-LED2. [START_REF] Neveling | Mutations in BICD2, which encodes a golgin and important motor adaptor, cause congenital autosomaldominant spinal muscular atrophy[END_REF][START_REF] Oates | Mutations in BICD2 cause dominant congenital spinal muscular atrophy and hereditary spastic paraplegia[END_REF][START_REF] Peeters | Molecular Defects in the Motor Adaptor BICD2 Cause Proximal Spinal Muscular Atrophy with Autosomal-Dominant Inheritance[END_REF] An increasing number of scientific data shows that Golgi functional and structural defects is a common pathophysiological feature of several lower and upper motor neuron diseases. In another hand, Dynein-Dynactin motor protein complex plays a key role in Golgi structure, dynamics and localization. Reported missense DYNC1H1 tail mutations increase BICD2-DYNC1H1 interactions, decreasing the binding of the Dynein-Dynactin motor complex to microtubules in a dominant negative manner. The subsequent impairment of cellular transport and Golgi function in DYNC1H1 related disorders plays probably a major role in motor neurons dysfunction. [START_REF] Peeters | Novel mutations in the DYNC1H1 tail domain refine the genetic and clinical spectrum of dyneinopathies[END_REF][START_REF] Niu | A novel DYNC1H1 mutation causing spinal muscular atrophy with lower extremity predominance[END_REF][START_REF] Martinez-Carrera | Dominant spinal muscular atrophy is caused by mutations in BICD2, an important golgin protein[END_REF] YUE Si -10

II2 II3 II4 II5 II6 II7 II8 II9 II10 II 11 II12 II13 II14 II15 II16 II17 III18 I1 I2 III1 III2 III3 III4 III5 III6 III7 III8 III9 III10 III11 III12 III13 III14 I II15 III16 III17 III18 III19 III20 III21 III22 III23 III24

Figure 1 .YUE Si - 11 Table 1 :

 1111 Figure 1. Pedigree of the 3 generations family with autosomal dominant inheritance. Filled

Figure 2 .

 2 Figure 2. Pictures of 3 patients presenting the SMA-LED phenotype (A-III16), the HSP phenotype

  Mild limitation of walking distance. Thighs and legs muscle wasting. Brisk knee and ankle reflexes with bilateral ankle clonus. Normal superficial sensation at the lower limbs. Decreased distal vibratory sensation at the lower limbs. No upper limbs weakness or atrophy. No intellectual disability. Unable to run. Difficulties for climbing stairs, rising from sitting on the floor and walking on heels. Bilateral flat feet, ankle valgus and Achilles tendon stiffness. Buttocks, thighs and legs muscle wasting. Brisk knee and ankle reflexes with bilateral ankle clonus. No Babinsky or Rossolimo sign. Learning difficulties.

	Patients Gender, age Development	Age at last physical examination Female, 8 yo Distribution of muscle atrophy Patient III16 Normal, walked at 15 months deformity Feet Female, 46 yo Knee reflexes Patient II10 Ankle reflexes	Age at EMG	Lower limbs Patient III7 EMG Lower motor and Male, 5 yo limbs sensory Hip dysplasia at birth. Walked at 18 NCVs months with frequent falls.
	II 5 Neurological examination	42yo	thighs Waddling gait, frequent falls, high arched difficulties for climbing stairs	2+	4+	35yo		neurogenic	normal
	II 8	42yo	A. Individual III16 legs and long walks. Positive Gower's high arched sign. Bilateral flat feet	B. Individual III14 0 3+	41yo		neurogenic	C. Individual III7 normal
	II 10	46yo	legs and thighs hyperlaxity of ankles. Mild leg muscles atrophy. Decreased	ND	2+	4+	46yo		normal	normal
	II 13	44yo	legs knee and ankle reflexes. No Babinsky, no ankle clonus. Mild	ND	ND	ND	44yo		normal	normal
	III 2	4yo	legs intention tremor of the hands.	flat	0	0	4yo		neurogenic	normal
	III 3 Electrophysiological studies Lower limbs electromyography 4yo ND No intellectual disability.	flat Normal lower limbs electromyography and 2+ 3+ 15yo	normal Lower limbs electromyography and normal
	III 4	3yo	thighs and legs and conduction studies showed decreased or absent	flat conduction studies 2+ Somatosensory evoked potentials 1+	ND	ND conduction studies showed decreased ND or absent recruitment with large
	III 7	5yo	legs and thighs recruitment with large amplitude potentials. Normal	flat abolished (provoked by lower limbs nerves 3+ 4+ 4yo stimulation)	neurogenic amplitude potentials. Normal motor normal and sensory nerve conduction
	III 8	17yo	ND motor and sensory nerve	high arched	2+	2+	27yo	neurogenic velocities	normal
			conduction velocities No
	III 9	15yo	ND spontaneous fibrillation	high arched	0	1+	2yo		neurogenic	normal
	III 10 Imaging	17yo	legs and thighs recorded ND		ND Brain and Spine MRI normal 0	1+	3yo	ND	neurogenic	normal
	III 12	19yo	legs and thighs		flat	3+	3+	14yo		normal	normal
	III 13	19yo	legs and thighs		flat	3+	4+	14yo		normal	normal
	III 14	23yo	legs and thighs		yes	2+	4+	18yo		normal	ND
	III 16	5yo	legs		flat	1+	1+	12yo		neurogenic	normal
	III 21	10yo	ND	high arched	1+	3+	10yo		neurogenic	normal