# The Fermat–Torricelli problem in normed spaces

Daniil A. Ilyukhin

###### Abstract

The article studies a generalization of the classical Fermat–Torricelli
problem to normed spaces of arbitrary finite dimension. Necessary and
sufficient conditions for the uniqueness of the solution of the
Fermat–Torricelli problem for any $n$ points in a fixed space are obtained,
and more precise conditions for normed planes and three-dimensional spaces are
presented. In addition, examples of the application of the criterion in the
norms given by regular polyhedra are given.

##  1 Introduction

The problem of finding a point that minimizes the sum of distances from it to
a given set of points in a metric space was first mentioned in the 17th
century. In 1643 Fermat posed a problem for three points on the Euclidean
plane, and in the same century Torricelli proposed a solution to this problem
([4]).

Figure 1: The design proposed by Torricelli. The point $T$ is the solution of
the problem for the given points $A,B,C$ ([15])

Since then, various generalizations of this problem have been considered. The
problem was formulated for an arbitrary number of points, the dimension of the
space, as well as the norm given in this space. The simplicity of the
formulation allows us to consider the problem even in an arbitrary metric
space. For example, the problem for four points on the Euclidean plane was
solved by D. Fagnano ([3], [12]). And for the case of five points, it was
proved that the problem is unsolvable in radicals, the proof is given in [1]
and [6]. In addition, there is a generalized problem in which the vertices are
considered together with some positive values, called weights. You can read
about the development of the weighted problem in the works [16], [17], [14].
In particular, the existence and uniqueness of the solution of such a problem
for three points on the Euclidean plane were proved ([12]).

This article will consider the classic version of the problem: finding a point
for which the minimum sum of distances to elements of a subset of a metric
space is reached. We will call such a formulation _generalized
Fermat–Torricelli problem_ (or simply _Fermat–Torricelli problem_). The work
is based on the article [13], which describes the application of a geometric
approach to the problem and presents some new results that are obtained in the
framework of real finite-dimensional normed spaces, called _Minkowski spaces_.

The purpose of this work is to find a necessary and sufficient condition for
the uniqueness of the solution of the Fermat–Torricelli problem for any $n$
points in an arbitrary Minkowski space.

I would like to express my gratitude to my scientific adviser, Doctor of
Physical and Mathematical Sciences Professor A.A.Tuzhilin and Doctor of
Physical and Mathematical Sciences Professor A.O.Ivanov for posing the problem
and constant attention to the work.

##  2 The Fermat–Torricelli problem and solving methods

All statements in this section will be formulated for the Minkowski space, so
this will not be specified.

######  Definition 2.1.

A point $x_{0}$ is called a _Fermat–Torricelli point_ for points
$A=\\{x_{1},\ldots,x_{n}\\}$ if $x=x_{0}$ minimizes $\sum_{i=1}^{n}|xx_{i}|$.
The set of all such points will be denoted by $\operatorname{ft}(A)$.

From the properties of the function $\sum_{i=1}^{n}|xx_{i}|$, one can obtain
the following assertion about the set of solutions of the Fermat–Torricelli
problem, see for example [5].

######  Proposition 2.2.

Let $A=\\{x_{1}$,…, $x_{n}\\}$ be points in space. Then $\operatorname{ft}(A)$
is a non-empty, compact and convex set.

We give two examples of solving the Fermat–Torricelli problem on a plane. The
figure 2 shows the vertices of an equilateral triangle, first in the Euclidean
plane, and then in the norm given by a regular hexagon. In the first case, the
set of solutions contains a single point constructed in such a way that the
angles between the rays coming out of it in the direction of the vertices of
the triangle are equal. In the second case, we specify the location of the
points of the given set: let one of them be at the origin, and the other two —
at neighboring vertices of the unit circle. Under such conditions, the set of
solutions will include all points of the constructed triangle, including the
interior and boundaries.

Figure 2: Examples of solutions to the Fermat–Torricelli problem on the
Euclidean plane and on the $\lambda$-plane

Now the geometric method for constructing the solution of the
Fermat–Torricelli problem will be presented. To use it, along with the
original space $X$, one must consider its dual space $X^{*}$, which consists
of linear functionals.

######  Definition 2.3.

A functional $\varphi\in X^{*}$ is called _norming for a vector_ $x\in X$ if
$\|\varphi\|=1$ and $\varphi(x)=\|x\|$ .

It is easy to see that the elements of the space $X$ obtained by multiplying
the vector $x$ by a positive number $k$ have the same set of norming
functionals. That is, the set of such functionals can be described using
points of the unit sphere. Consider norming functionals on some normed plane.

The figure 3 shows a section of the unit circle $S$ containing both a
flattened and a smooth section. Let us construct norming functionals for
vectors starting at zero and ending at a point lying on $S$. At the point $z$
the unit circle has a single support line, then for the corresponding vector
there is a unique norming functional $\varphi_{4}$, its level line coincides
with this support line. Internal flattening points $xy$ also correspond to
vectors with a unique norming functional. At the point $x$ the unit circle has
more than one reference line. Each of them defines a norming functional, that
is, for a vector with an end in $x$, there are infinitely many norming
functionals. The functionals $\varphi_{1}$ and $\varphi_{2}$ are given by the
limit positions of the reference line, while $\varphi_{3}$ is an arbitrary
one.

Figure 3: Construction of norming functionals along the support lines to the
unit circle

The following theorem is a criterion for a certain point to belong to the set
of solutions of the Fermat–Torricelli problem.

######  Theorem 2.4 ([7], [10]).

Let $x_{0}$, $x_{1}$, …, $x_{n}$ be points in space and $x_{0}\neq x_{i}$ for
$i=1,...,n$. Then $x_{0}$ is a Fermat–Torricelli point for
$A=\\{x_{1},...,x_{n}\\}$ if and only if each vector $x_{i}-x_{0}$,
$i=1,...,n$, has a norming functional $\varphi_{i}$ such that
$\sum_{i=1}^{n}\varphi_{i}=0$.

Let us give the simplest example of using this theorem on the Euclidean plane.
Let’s consider three points on a circle, located at an equal distance from
each other, and suppose that the origin of coordinates is the solution of the
Fermat–Torricelli problem for them. For each of the points $x_{1},x_{2},x_{3}$
there is a unique support line, which is the level line $\varphi_{i}=1$ of
some functional. The three constructed lines form an equilateral triangle and
are equidistant from the origin, therefore, the sum of the functionals they
define is equal to zero. By the 2.4 theorem, the point $p=0$ belongs to the
set of solutions.

Figure 4: The origin of coordinates belongs to the solution set for points
$x_{1},x_{2},x_{3}$

Assume that a point is found that is a solution for the set $A$. Now, using
the functionals from the 2.4 theorem, we can construct the entire set
$\operatorname{ft}(A)$. To do this, we introduce a new object.

######  Definition 2.5.

Let a functional $\varphi\in X^{*}$ and a point $x\in X$ be given. Define
_cone_ $C(x,\;\varphi)=x-\bigl{\\{}a:\;\varphi(a)=\|a\|\bigr{\\}}$.

Let’s consider two examples of constructing a cone on the Manhattan plane
(figure 5). Let the functional $\varphi_{1}$ be given by the support line
intersecting the unit circle at one point, and $\varphi_{2}$ be the line
containing the flattening. The set
$\bigl{\\{}a:\;\varphi_{1}(a)=\|a\|\bigr{\\}}$ is a ray that leaves the origin
and passes through this point. For the second functional, this will be a whole
set of rays intersecting all flattening points. In both cases, we then reflect
the constructed set relative to the origin of coordinates and shift it by
parallel translation so that the vertex hits the given point.

Figure 5: Construction of cones on the Manhattan plane

######  Theorem 2.6 ([7]).

Let $A=\\{x_{1}$, …, $x_{n}\\}$ be points in space and
$p\in\operatorname{ft}(A)\setminus A$. By the 2.4 theorem, for each vector
$x_{i}-p$, $i=1,...,n$, there exists a norming functional $\varphi_{i}$ such
that $\sum_{i=1}^{n}\varphi_{i}=0$. Then
$\operatorname{ft}(A)=\cap_{i=1}^{n}C(x_{i},\;\varphi_{i})$.

The 2.4 and 2.6 theorems constitute a geometric method for finding a solution
to the Fermat–Torricelli problem. To describe the application of this theorem,
let’s consider in more detail the example with the vertices of an equilateral
triangle in the hexagonal norm (figure 6).

First, let’s find at least one solution. Take
$p=\frac{1}{3}(x_{1}+x_{2}+x_{3})$ and use the 2.4 theorem to prove that
$p\in\operatorname{ft}(A)$. To do this, consider the vectors
$x_{1}-p,x_{2}-p,x_{3}-p$ and construct their norming functionals. Since they
lie in the same directions with internal flattening points, then for each of
the vectors $x_{i}-p$ there is exactly one functional $\varphi_{i}$ whose
level line contains the corresponding flattening. The flattenings are
equidistant from the origin and form an equilateral triangle; therefore, the
sum of the functionals constructed from them is equal to zero, and the
condition of the theorem is satisfied.

Figure 6: Construction of a complete set of solutions for points
$x_{1},x_{2},x_{3}$ on a plane with hexagonal norm

Now let’s use the 2.6 theorem to find all solutions. Let us construct a cone
given by the functional $\varphi_{2}$ and the vector $x_{2}-p$. Since the
functional is norming for all flattening points, the set
$\bigl{\\{}a:\;\varphi_{2}(a)=\|a\|\bigr{\\}}$ is a set of rays emanating from
the origin and passing through the flattening points , that is, an angle whose
sides contain two adjacent vertices. Now we will reflect the angle relative to
the origin and perform a parallel translation so that the vertex of the angle
is at the point $x_{2}$. After a similar construction of two other cones, we
obtain that their intersection is the entire triangle $x_{1}x_{2}x_{3}$.

######  Remark 2.7.

The statement of 2.6 theorem does not depend on the choice of the point $p$
and the functionals $\varphi_{i}$.

The geometric method gives a general description of the solutions of the
Fermat–Torricelli problem for various given sets - this is the intersection of
some cones with vertices located at the points of this set. In the case of a
plane, this observation allows us to formulate the following statements:

######  Proposition 2.8 ([13]).

Let in space the points of the set $A=\\{x_{1}$, …, $x_{2k+1}\\}$ be located
on one straight line in the order of their numbering. Then
$\operatorname{ft}(A)=\\{x_{k+1}\\}$. If $A=\\{x_{1}$, …, $x_{2k}\\}$, then
$\operatorname{ft}(A)=\overline{x_{k}x_{k+1}}$.

##  3 Uniqueness criterion

###  3.1 Criterion for $n$ points in a space of dimension $d$

Let $X$ be a Minkowski space of dimension $d$. In $X$ we pose the
Fermat–Torricelli problem for $n$ points. If $x_{i}\in X,1\leq i\leq n$, then
the solution is the set $\operatorname{ft}(x_{1},\ldots,x_{n})$, which
includes all points $x\in X$ at which the minimum of the function
$\sum_{i=1}^{n}|xx_{i}|$.

Consider the unit sphere $S$ of the space $X$.

######  Definition 3.1.

Face of a unit sphere is its intersection with some supporting hyperplane. If
the linear span of the points of a face is a subspace $X$ of dimension $k$,
then such a face is called $(k-1)$-dimensional.

######  Definition 3.2.

Take a finite set of faces of the unit sphere $S$ of the Minkowski space. For
each of them, we choose a supporting hyperplane $\pi_{i}$ that intersects $S$
only along this face. Let the hyperplane $\pi_{i}$ define the level surface
$\varphi_{i}=1$ of some linear functional $\varphi_{i}$. If there is a set of
supporting hyperplanes such that the sum of the constructed functionals is
equal to zero, then we will call such a set of faces _consistent_.

It follows from the definition that if we take one point from each face of a
consistent set, then we obtain a set of points for which $x=0$ is one of the
solutions to the Fermat–Torricelli problem. Depending on the dimensions of the
faces included in the set and their mutual arrangement, it is possible to
obtain various types of solutions, including unique and non-unique ones. It
turns out that the problem of finding in the space $X$ a set of points with a
non-unique solution is equivalent to the existence in this space of a
consistent set of faces with certain properties.

######  Theorem 3.3.

Let $X$ be a Minkowski space of dimension $d$.

If $n\geq 3$ is odd, then in the space $X$ there are $n$ points for which the
solution of the Fermat–Torricelli problem is nonunique if and only if $X$ has
a consistent set of $n$ faces of the unit sphere $S$ for which the following
condition is satisfied:

  * •

The intersection of the linear spans of all faces included in this consistent
set contains a line.

If $n\geq 4$ is even, then in the space $X$ the solution of the
Fermat–Torricelli problem is unique for any $n$ points that do not lie on one
straight line if and only if the unit sphere is strictly convex.

###### Proof.

Let $n$ be odd.

Sufficiency. Let us prove that if such a consistent set $A$ exists, then there
exists a set of points for which the solution of the Fermat–Torricelli problem
is not unique. Take one interior point from each face. Let these be points
$x_{1},\ldots,x_{n}$. By the 2.4 theorem, the point $x=0$ is one of the
solutions. By the 2.6 theorem, the complete solution is the intersection of
the cones coming out of the vertices and containing the point $x=0$. Moreover,
a $(k+1)$-dimensional cone emerges from the $k$-dimensional face. By
assumption, there exists a line $l$ that belongs to the linear span of any
face in $A$, that is, to the linear span of any cone. Then each of these cones
contains some one-dimensional neighborhood of the point $x=0$ on the line $l$.
Therefore, the intersection of all cones also contains a neighborhood of zero.
The solution is not unique.

Necessity. Let the space $X$ contain $n$ points $x_{1},\ldots,x_{n}$ for which
the solution of the Fermat–Torricelli problem is not unique. Let the point $p$
be included in the solution. Then the solution for the points $x_{i}-p$ is
also not unique, and $x=0$ is one of the solutions. By the 2.6 theorem, the
set $\operatorname{ft}(x_{1}-p,\ldots,x_{n}-p)$ is the intersection of some
cones $C_{1},\ldots,C_{n}$ coming out of the points $x_{i}-p$. Let us consider
the norming functionals by which the cones are constructed, namely, the
intersections of the unit sphere with the supporting hyperplanes
$\varphi_{i}=1$. We get $n$ faces, which obviously make up a consistent set.
Since the solution is non-unique and is an intersection of cones, it contains
some non-empty segment containing $x=0$. Each cone also contains this segment.
Then the linear span of the cone contains a line containing this segment.
Therefore, the intersection of the linear spans of all faces contains a line.

Let $n$ be even.

Let the norm be strictly convex. Then the solution of the Fermat–Torricelli
problem for any $n$ points is the intersection of one-dimensional cones with
vertices at these points. Since the vertices do not lie on the same line, the
cones can only intersect at one point, that is, the solution is always unique.

Let the unit sphere contain a face that is not a point. Take in it any
$\frac{n}{2}$ distinct interior points $x_{1},\ldots,x_{\frac{n}{2}}$.
Consider the solution set for $\pm x_{1},\ldots,\pm x_{\frac{n}{2}}$. For each
of the points, we define a functional whose level surface is a reference
hyperplane defining the face to which the point belongs. Since the faces are
opposite and contain the same number of points, the sum of the functionals is
equal to zero. By the theorem, 2.4 $x=0$ is one of the solutions. The complete
solution is the intersection of the cones. All cones have the same dimension,
lie in the same subspace of the same dimension, and contain the point $x=0$ as
an interior point. Thus, the intersection of all cones contains some
neighborhood of zero of the corresponding dimension. The solution is not
unique.

The theorem has been proven. ∎

######  Remark 3.4.

Since the entire space is the linear span of a face of maximum dimension, in
the condition of the theorem one can consider the intersection of only non-
maximal faces. Thus, if a consistent set consists of only maximal faces, then
the additional condition is automatically satisfied.

If the dimension of the space $d$ is equal to $2$ or $3$, then the equivalent
condition can be refined. Let’s consider these two cases in more detail.

###  3.2 Criterion for $n$ points on the plane

Let $X$ be the Minkowski plane. The Fermat–Torricelli problem for $n$ points
is posed in $X$. The unit circle $S$ has only two types of faces. We will call
them points and flattenings.

######  Proposition 3.5.

If in $X$ there is a consistent set of faces of the unit circle, consisting of
$n$ flattenings, then in this plane there are points $x_{1},\ldots,x_{n}$ for
which the set $\operatorname{ft}(x_{1},\ldots,x_{n})$ \- is a non-degenerate
polygon.

###### Proof.

Let $x_{1},\ldots,x_{n}$ be interior flattening points from a consistent set.
Then, taking the functionals $\varphi_{1},\ldots,\varphi_{n}$ from the
definition of 3.2, by the theorem 2.4 we get that $p=0$ belongs to
$\operatorname{ft}(x_{1},\ldots,x_{n})$. By the 2.6 theorem,
$\operatorname{ft}(x_{1},\ldots,x_{n})$ is the intersection of the cones
emerging from the points $x_{1},\ldots,x_{n}$. Since all functionals contain
flattenings, all cones are non-degenerate angles. Moreover, each of them
contains some full-dimensional neighborhood of zero due to the fact that the
points $x_{i}$ are not boundaries of flattenings. Therefore, the cones at the
intersection form a polygon. ∎

Figure 7: The first non-uniqueness condition for $n=3$

######  Proposition 3.6.

If in $X$ there is a consistent set of faces of the unit circle, consisting of
$n-1$ flattening and one point, then in this plane there are
$x_{1},\ldots,x_{n}$ for which the set of solutions
$\operatorname{ft}(x_{1},\ldots,x_{n})$ is a non-degenerate segment.

###### Proof.

Let the points $x_{1},\ldots,x_{n-1}$ be interior flattening points, and
$x_{n}$ be a point from a consistent set. Similarly to the previous proof, we
get that $p=0$ belongs to $\operatorname{ft}(x_{1},\ldots,x_{n})$. The cones
emerging from $x_{1},\ldots,x_{n-1}$ contain a neighborhood of zero, and a ray
passes from the point $x_{n}$ and passes through the origin. Consequently, at
the intersection we obtain a non-degenerate segment. ∎

######  Proposition 3.7.

Let $2\leq k\leq n-1$. If there is a consistent set of faces of the unit
circle in $X$, consisting of $k$ flattenings and $n-k$ points, and the linear
span of the points is a straight line, then there are $x_{1},\ldots,x_{n}$ in
this plane for which the set of solutions
$\operatorname{ft}(x_{1},\ldots,x_{n})$ is a non-degenerate segment.

###### Proof.

Let $x_{1},\ldots,x_{k}$ be interior flattening points, and
$x_{k+1},\ldots,x_{n}$ be points from a consistent set. The functionals
$\varphi_{1},\ldots,\varphi_{n}$ from the definition of 3.2 satisfy the 2.4
theorem, and the point $x=0$ belongs to
$\operatorname{ft}(x_{1},\ldots,x_{n})$ . By the 2.6 theorem, the solution
$\operatorname{ft}(x_{1},x_{2},x_{3})$ is the intersection of $k$ rays
containing the origin and lying on the same line, and $n-k$ non-degenerate
angles, each of which contains a neighborhood of zero . We get a segment. ∎

Figure 8: The third non-uniqueness condition for $n=3$

######  Theorem 3.8.

If $n\geq 3$ is odd, then in the normed plane the solution of the
Fermat–Torricelli problem is unique for any $n$ points if and only if any
consistent set of faces of the unit circle consists of at most $n-2$
flattenings and the dimension of the linear span of face-points is equal to
$2$.

If $n\geq 4$ is even, then in the normed plane the solution of the
Fermat–Torricelli problem is unique for any $n$ points that do not lie on one
straight line if and only if the norm is strictly convex.

###### Proof.

In both statements, the necessity follows from the propositions 3.5, 3.6, and
3.7. Let us prove sufficiency. Let $n$ be odd and there are points
$x_{1},\ldots,x_{n}$ for which the set of solutions of the Fermat–Torricelli
problem is not unique. Since the solution is the intersection of cones, it is
either a polygon or a segment. In the case of a polygon, all cones are non-
degenerate angles. Consider the functionals defining the cones. Their level
lines contain flattenings of the unit circle, which obviously constitute a
consistent set of faces.

A segment can be obtained by the intersection of at least one non-degenerate
angle and rays lying on the same straight line. If all cones are rays, then
all points of $x_{i}$ lie on the same straight line, but by the proposition
2.8 in this case the solution is unique. Similarly, we consider the
functionals defining the cones. Since all degenerate cones lie on the same
straight line, the points of intersection of the unit circle and the level
lines of the functionals also lie on the same straight line. That is, the
linear span of the points of the consistent set is equal to $1$.

The statement for even $n$ follows from the 3.3 theorem.

∎

###  3.3 Criterion for $n$ points in three-dimensional space

Let $X$ be a three-dimensional Minkowski space. The Fermat–Torricelli problem
for $n$ points is posed in $X$.

######  Theorem 3.9.

If $n\geq 3$ is odd, then there are $n$ points in the three-dimensional
Minkowski space $X$ for which the solution of the Fermat–Torricelli problem is
nonunique if and only if $X$ contains a consistent set of $n$ faces of the
unit sphere $S$, for which the following conditions are satisfied:

  * •

The intersection of the linear spans of the face-points included in this
consistent set contains a line,

  * •

For any pair of face-point and face-segment included in this consistent set,
the dimension of their linear span is $2$,

  * •

The intersection of the linear shells of the segment faces included in this
consistent set contains a straight line.

If $n\geq 4$ is even, then in three-dimensional Minkowski space the solution
of the Fermat–Torricelli problem is unique for any $n$ points that do not lie
on one straight line if and only if the norm is strictly convex.

###### Proof.

Let $n$ be odd.

Sufficiency. Let there be a consistent set of $n$ faces for which all
conditions are satisfied. Let us construct a solution of the Fermat–Torricelli
problem for a set of interior points of given faces. By the 2.4 theorem, the
point $x=0$ is included in the solution. The complete solution is the
intersection of some cones coming out of the vertices and containing $x=0$ as
an interior point.

Let the consistent set have face-points. The linear span of such a face is a
straight line containing the point itself and $x=0$. Based on the first
condition imposed on a consistent set, this line coincides for all its points.
Let this be a straight line $l$. The intersection of all one-dimensional cones
coming out of face-points contains a non-empty segment lying in $l$ and
containing $x=0$ as an interior point.

Linear spans of faces of the second type are planes containing two-dimensional
cones emerging from these elements. By assumption, each such plane contains
all point-faces, and hence the line $l$ on which they lie. There is a non-
empty segment lying in $l$ and containing $x=0$ as an interior point, which
lies in each of the two-dimensional cones. We get that the intersection of all
one-dimensional and two-dimensional cones contains at least a segment. If
there are no faces-points in a consistent set, then by assumption we take as a
line $l$ any line lying at the intersection of the planes.

Since the intersection of three-dimensional cones includes some full-
dimensional neighborhood of the point $x=0$, their intersection with the
resulting segment is not unique. That is, the intersection of all cones
contains at least a segment. Sufficiency has been proven.

Necessity. Let the space $X$ contain $n$ points $x_{1},\ldots,x_{n}$ for which
the solution of the Fermat–Torricelli problem is not unique. Let the point $p$
be included in the solution. Then the solution for the points $x_{i}-p$ is
also not unique, and $x=0$ is one of the solutions. By the 2.6 theorem, the
set $\operatorname{ft}(x_{1}-p,\ldots,x_{n}-p)$ is the intersection of some
cones $C_{1},\ldots,C_{n}$ coming out of the points $x_{i}-p$. Let us consider
the norming functionals by which the cones are constructed, namely, the
intersections of the unit sphere with the support planes $\varphi_{i}=1$. We
obtain a consistent set of faces of the unit sphere. Let us determine what
conditions are imposed on this set.

All one-dimensional cones coming out of point-faces must lie on the same
straight line, otherwise their intersection will contain only the point $x=0$.
In other words, the intersection of the linear spans of these faces is this
straight line. Let this be a straight line $l$.

Two-dimensional cones emerge from the faces-segments. Since the solution is
not unique, let their intersection contain a non-empty segment containing
$x=0$. Let also this segment belong to the line $l$ if the consistent set
contains points and such a line is constructed. Then the linear span of any
face-segment, that is, the plane containing the corresponding cone, contains
the line containing this segment. We have found that the intersection of the
linear spans of the segment faces contains a straight line. In the presence of
face-points, this will be a straight line $l$. Hence, a plane containing a
face-segment contains any face-point. That is, the linear span of any pair of
face-point and face-segment has dimension $2$. All conditions on the
consistent set are satisfied.

The statement for even $n$ follows from the 3.3 theorem.

∎

##  4 Regular polyhedra and three-dimensional normed spaces

The article [9] showed the application of the criterion on lambda planes —
normed planes defined by regular polygons. Consider the problem in some three-
dimensional spaces.

######  Assumption 4.1.

There are only five regular polyhedra: tetrahedron, cube, octahedron,
icosahedron and dodecahedron. Four of them, all except the tetrahedron, set
the norm in three-dimensional space.

Let’s check whether the solution of the Fermat–Torricelli problem is unique
for any three points in the given spaces. To do this, it is necessary to study
the consistent sets of faces existing in them.

######  Lemma 4.2.

If three faces of the unit sphere of the Minkowski space constitute a
consistent set, then they are pairwise disjoint.

###### Proof.

Each face from the consistent set corresponds to a functional whose level
surface contains the given face. The sum of the functionals of all faces is
equal to zero. If some two faces have a common point, then the sum of their
functionals at this point is equal to $2$. Then the third functional takes the
value $-2$ at this point, and it is not norming. Contradiction. ∎

######  Proposition 4.3.

In a normed space given by a regular cube, there are three points for which
the solution of the Fermat–Torricelli problem is not unique. Moreover, if the
solution is not unique, then it is a segment.

###### Proof.

Let $X$ be the space under consideration. Consider in $X$ all possible
variants of consistent sets.

Let there be a consistent set in $X$, and let at least two of them be two-
dimensional faces. By the 4.2 lemma, they have no common points. Hence, they
are opposite, and the sum of their functionals is equal to zero. But then the
third functional is zero. Contradiction.

Let a consistent set contain exactly one two-dimensional face. It cannot share
points with either of the other two faces. If the remaining two faces are cube
edges, then they belong to the opposite two-dimensional face and are not
adjacent. The functional corresponding to a two-dimensional face takes the
value $-1$ on both edges. Then each of the other two functionals is equal to
zero on the other edge. This means that their level planes make an angle of
$45$ degrees with the neighboring faces of the cube. The planes intersect in a
straight line on which the sum of two functionals is equal to $2$. However,
the first functional takes the value $-\frac{3}{2}$ on this line. The sum of
functionals is not equal to zero. Contradiction. The second and third faces
also cannot be an edge and a point or two points, since in this case their
linear span does not contain a line, as it should be in the criterion
condition.

Let the matched set consist of three edges. If some two edges belong to the
same face, then the third necessarily belongs to the opposite one. Let it be
symmetrical to one of the first two. Then the problem is reduced to
constructing functionals for three vertices of the square that defines the
norm on the plane. Such functionalities exist. Let the level lines of the
functionals corresponding to the symmetric vertices intersect on the extension
of the diagonal of the square at the point of the norm $2$. And the level line
of the third functional passes through the remaining vertex perpendicular to
this diagonal. Then the sum of the functionals is equal to zero. The
functionals for the cube edges are constructed similarly. The intersection of
the linear shells of the edges is a straight line. Taking three arbitrary
interior points on these edges, in the solution we obtain a non-empty segment
lying on this line.

If the third edge is non-parallel, then the intersection of the line spans of
all edges is a point. If no pair of edges belongs to the same face, then again
we get a point at the intersection of their linear envelopes. The criterion
condition is not fulfilled.

If a consistent set consists of two edges and a point, then this point must
lie in the same two-dimensional subspace with each of the edges. In this case,
we get that the point is the end of one of the two edges. If a consistent set
consists of one edge and two vertices, then the line passing through the
vertices is the diagonal of the cube, and it must lie in the same plane as the
edge, but there is no such edge.

Thus, in $X$ there are only consistent sets consisting of three parallel
edges, and the solution of the Fermat–Torricelli problem is either a segment
or a point. The statement is proven.

∎

######  Proposition 4.4.

In a normed space given by a regular octahedron, the solution of the
Fermat–Torricelli problem is unique for any three points.

###### Proof.

In a normed space, in which the unit sphere is a regular octahedron, the norm
for a point with coordinates $a=(x,y,z)$ is given by the formula
$\|a\|=|x|+|y|+|z|$. Then for the points $a_{i}=(x_{i},y_{i},z_{i})$ and the
point $a=(x,y,z)$ we have

$\sum_{i=1}^{n}|aa_{i}|=\sum_{i=1}^{n}\|a-a_{i}\|=\sum_{i=1}^{n}(|x-x_{i}|+|y-y_{i}|+|z-z_{i}|)=\sum_{i=1}^{n}|x-x_{i}|+\sum_{i=1}^{n}|y-y_{i}|+\sum_{i=1}^{n}|z-z_{i}|$

That is, the problem is reduced to one-dimensional, and according to 2.8 the
solution for three points located on the same straight line is unique. The
assertion has been proven. ∎

######  Proposition 4.5.

In a normed space given by a regular dodecahedron, there are three points for
which the solution of the Fermat–Torricelli problem is not unique. Moreover,
if the solution is not unique, then it is a segment.

###### Proof.

Consider in $X$ all possible variants of consistent sets. For convenience, we
introduce notation and formulations for the elements of the dodecahedron.
$f_{i}$ are used to designate two-dimensional faces. The edge belonging to the
faces $f_{i},f_{j}$ will be denoted by $e_{i,j}$, and the vertex belonging to
the faces $f_{i},f_{j},f_{k}$ will be denoted by $v_{i,j,k}$. The faces
$f_{1}$ and $f_{12}$ are called top and bottom respectively. Edges and
vertices belong to the equator of the dodecahedron if they do not intersect
with the top and bottom faces.

Figure 9: Regular dodecahedron sets the norm in three-dimensional space

Assume that a consistent set contains at least two two-dimensional faces. By
the 4.2 lemma, they cannot be adjacent and opposite, so we will assume that
these are the faces $f_{1}$ and $f_{7}$. If the third element of the
consistent set is also a two-dimensional face, then it can only be $f_{9}$ or
$f_{10}$. Since they are located symmetrically with respect to the first two
faces, they simultaneously complement or do not complement them to a
consistent set. But if they complement, then their functionals must match, and
this is not true.

Let the third element be an edge. All edges except $e_{9,10}$ are symmetrical
with respect to the two considered faces, so they cannot be included in the
consistent set. The functional of the edge $e_{9,10}$ is equal to $-1$ at the
vertex $v_{2,6,7}$. At the same vertex, the functional of $f_{7}$ is equal to
$1$, but the functional of $f_{1}$ is not equal to zero. The sum of
functionals is not equal to zero.

Let the third element be a vertex. Similar to the previous reasoning, it
suffices to check only the vertex $v_{4,9,10}$. In this case, at the vertex
$v_{2,6,7}$ the sum of the functionals is again not equal to zero.

Consider the variant when the consistent set contains a single face $f_{1}$.
Let the other two elements be edges. If one of the edges belongs to the bottom
face, then the zero level of the functional of the second edge passes through
it. But in this case it is one of the edges adjoining the top face, which is
impossible by the 4.2 lemma. Let one of the edges connect the equator and the
bottom face. But then any of the remaining edges has a symmetric relative to
the considered face and edge and cannot complement them to a consistent set.
Then both edges must belong to the equator, and they are symmetrical about the
center. The plane passing through these edges is the zero level of the $f_{1}$
face functional, but is not parallel to it, which is impossible.

Let the face $f_{1}$ be complemented by an edge and a vertex lying in the same
plane. The subspaces defined by edges from the equator contain only vertices
that are the ends of the edge itself and the opposite edge. Each of them is
symmetrical to itself. Similarly, the edge of the bottom face also cannot be
included in the consistent set. There are edges between the bottom face and
the equator. It suffices to check the edge $e_{8,9}$ and the vertex
$v_{5,6,11}$. In this case, on the line connecting the vertices $v_{5,6,11}$
and $v_{3,8,9}$ the face functional $f_{1}$ is equal to zero. But this line is
not parallel to the plane of the face. Contradiction.

If the face $f_{1}$ is complemented by two symmetrical vertices, then this is
necessarily a pair of vertices from the equator. But the straight line passing
through them is not parallel to the plane of the face. A contradiction, since
the face functional on this line must be equal to zero.

There are variants of consistent sets that do not contain a single face. Let
us assume that a consistent set consists of three edges whose intersection of
subspaces contains at least a line. Let two of them be opposite, for example
$e_{1,4}$ and $e_{7,12}$. Their common two-dimensional subspace defines the
zero level of the third edge functional. Only the edges $e_{2,6}$ and
$e_{9,10}$ are parallel to this plane. They are symmetrical, so it suffices to
consider the first.

Figure 10:

Let the level of the functional $\varphi_{1}$ pass through the edge $e_{2,6}$
and make equal dihedral angles with neighboring faces. The functional levels
$\varphi_{2}$ and $\varphi_{3}$ contain the edges $e_{1,4}$ and $e_{7,12}$
respectively. In the plane of these two edges, the sum of the functionals is
equal to zero. Now consider a plane containing the edge $e_{2,6}$ and the
midpoints of the edges $e_{1,4}$ and $e_{7,12}$. The section of the
dodecahedron by this plane is shown in 10. Since the sum of the functionals is
equal to zero, the point of intersection of the level lines $\varphi_{2}=1$
and $\varphi_{3}=1$ belongs to the line $\varphi_{1}=-2$. Let $\alpha$ be the
dihedral angle between the level $\varphi_{1}=0$ and the face, and $\beta$ be
the angle between the levels $\varphi_{1}=0$ and $\varphi_{2}=1$. If
$\beta>\alpha$, then such functionals exist, and so does a consistent set of
corresponding edges. We will prove that this is indeed the case. The angle
$\alpha$ is half the dihedral angle of a regular dodecahedron, i.e.

$\alpha=\frac{1}{2}\arccos{(-\frac{1}{\sqrt{5}})}$

The lengths of the edges $e_{2,6}$ and $e_{9,10}$ are equal to $a=1$. The
lengths of the remaining sides of the resulting hexagon in the section are
equal to the height of a regular pentagon, that is,
$b=\frac{\sqrt{5+2\sqrt{5}}}{2}$. Calculate the legs of a right triangle with
hypotenuse $b$ and acute angle $\alpha$:

$c=b\cos{\alpha}=\frac{1}{2}\sqrt{\frac{3+\sqrt{5}}{2}},d=b\sin{\alpha}=\frac{1}{2}\sqrt{\frac{7+3\sqrt{5}}{2}}$

Now we can calculate the tangent of the angle $\beta$:

$\tan{\beta}=\frac{2d}{c+\frac{a}{2}}=\frac{\sqrt{\frac{7+3\sqrt{5}}{2}}}{\frac{1}{2}\sqrt{\frac{3+\sqrt{5}}{2}}+\frac{1}{2}}=2$

Since $\arctan{2}>\frac{1}{2}\arccos{(-\frac{1}{\sqrt{5}})}$, then
$\beta>\alpha$, and the edges of the dodecahedron form a consistent set. Since
the two-dimensional subspaces defined by these three edges intersect along a
straight line, this set gives non-unique solutions to the Fermat–Torricelli
problem, moreover, belonging to some straight line, that is, segments.

If among the three edges of the dodecahedron there is not a single pair of
opposite ones, then the two-dimensional subspaces containing the edges
intersect no more than at a point.

A consistent dodecahedron set cannot consist of two edges and a vertex, so in
this case the vertex must lie in the same plane with each edge. We get that
the edges are opposite, and the vertex is the end of one of the edges, which
is impossible by the lemma 4.2.

Also, there is no consistent set of one edge and two vertices lying in the
same plane. If so, then by the lemma 4.2, the vertices are the ends of the
edge opposite the given one. Using the picture 10, let’s say that the edge
$e_{2,6}$ is being considered, and the vertices are the endpoints of the edge
$e_{9,10}$. Then the level lines of the functionals $\varphi_{2}$ and
$\varphi_{3}$ pass through these vertices and intersect at the lines
$\varphi_{1}=-2$. It can be seen from the figure that this is not possible.

Thus, the dodecahedron has only consistent sets consisting of three edges.
Moreover, if a non-unique solution is obtained, then this is a segment. The
assertion has been proven.

∎

######  Proposition 4.6.

If the unit sphere of a three-dimensional normed space is a prism, then for
any $n\geq 2$ there are $n$ points for which the solution of the
Fermat–Torricelli problem is not unique.

###### Proof.

Consider a normed plane whose unit circle coincides with the base of the
prism. In this normed plane, we take any consistent set and the functionals
defining it. Let us draw the level lines of these functionals at the two bases
of the prism. A unique set of support planes passes through them, defining $n$
functionals in the original space. Their sum is equal to zero, and the linear
span of the faces contains a line. The condition of the criterion 3.9 is
satisfied, and the assertion is proved. ∎

## References

  * [1] Bajaj C. 1988, ‘‘The algebraic degree of geometric optimization problems.‘‘, Discr. Comput. Geom., 3, 177–191.
  * [2] Bannikova A. G., Ilyutko D. P., Nikonov I. M. 2016, ‘‘The Length of an Extremal Network in a Normed Space: Maxwell Formula‘‘, Journal of Mathematical Sciences, 214:5, 593–608.
  * [3] Boltyanski V., Martini H., Soltan V. 1999, ‘‘Geometric methods and optimization problems.‘‘, Kluwer Acad. Publ.
  * [4] Brazil M., Graham R. L., Thomas D. A., Zachariasen M. 2013, ‘‘On the History of the Euclidean Steiner Tree Problem.‘‘
  * [5] Cieslik D. 1988, ‘‘The Fermat-Steiner-Weber-problem in Minkowski spaces.‘‘, Optimization 19, 485–489.
  * [6] Cockayne E. J., Melzak Z. A. 1969, ‘‘Euclidean constructibility in graph-minimization problems‘‘, Math. Mag., 42, 206–208.
  * [7] Durier R., Michelot C. 1985, ‘‘Geometrical properties of the Fermat-Weber problem.‘‘, Europ. J. Oper. Res. 20, 332–343.
  * [8] Ilyukhin D. A. 2022, ‘‘The Fermat–Torricelli problem in the case of three-point sets in normed planes‘‘, ArXiv e-prints, arXiv:2210.04374.
  * [9] Ilyukhin D. A. 2022, ‘‘The Fermat–Torricelli problem in the case of three-point sets in normed planes‘‘, Chebyshevskii Sbornik. T. 23(5): 72-86.
  * [10] Ivanov A. O., Tuzhilin A. A. 2002, ‘‘Branching geodesics in normed spaces‘‘, Izvestiya: Mathematics, 2002, 66:5, 905–948.
  * [11] Jarník V., Kössler M. 1934, ‘‘O minimálních grafech obsahujících n daných bodu‘‘, Ĉas, Pêstování Mat. (Essen) Т. 63: 223—235.
  * [12] Kupitz Y. S., Martini H. 1997, ‘‘Geometric aspects of the generalized Fermat–Torricelli problem.‘‘, Bolyai Society Mathematical Studies 6, 55-127.
  * [13] Martini H., Swanepoel K. J., Weis G. 2002, ‘‘The Fermat–Torricelli problem in normed planes and spaces.‘‘, Journal of Optimization Theory and Applications 115, 283-314.
  * [14] Nguyen S. D. 2018, ‘‘Constrained Fermat-Torricelli-Weber Problem in real Hilbert Spaces‘‘, ArXiv e-prints, arXiv:1806.04296.
  * [15] Torricelli E. 1919, ‘‘De maximis et minimis.‘‘ Opere di Evangelista Torricelli, Faenza, Italy.
  * [16] Uteshev A. Y. 2014, ‘‘Analytical solution for the generalized Fermat–Torricelli problem‘‘, The American Mathematical Monthly 121(4), 318–331.
  * [17] Zachos A. N. 2014, ‘‘An analytical solution of the weighted Fermat-Torricelli problem on the unit sphere‘‘, ArXiv e-prints, arXiv:1408.6495.


# SURENA 4: Towards A Cost-effective Full-size Humanoid
Robot for Real-world Scenarios

Aghil Yousefi-Koma1,†, Behnam Maleki1,†, Hessam Maleki1,†, Amin Amani1,†
Mohammad Ali Bazrafshani1,† Hossein Keshavarz1,†,Ala Iranmanesh 1,†, Alireza
Yazdanpanah1,†
Hamidreza Alai1,†, Sahel Salehi1,†, Mahyar Ashkvari1,†, Milad Mousavi1,†, and
Milad Shafiee Ashtiani1,† $\dagger$ All authors equally contributed to the
paper.1Center of Advanced Systems and Technologies (CAST) School of Mechanical
Engineering, College of Engineering, University of Tehran, Tehran, Iran.
<EMAIL_ADDRESS>
###### Abstract

This paper describes the hardware, software framework, and experimental
testing of SURENA 4 humanoid robotics platform. SURENA 4 has 43 degrees of
freedom (DoFs), including seven DoFs for each arm, six DoFs for each hand, and
six DoFs for each leg, with a height of 170 cm and a mass of 68 kg and
morphological and mass properties similar to an average adult human. SURENA 4
aims to realize a cost-effective and anthropomorphic humanoid robot for real-
world scenarios. In this way, we demonstrate a locomotion framework based on a
novel and inexpensive predictive foot sensor that enables walking with 7cm
foot position error because of accumulative error of links and connections’
deflection(that has been manufactured by the tools which are available in the
Universities). Thanks to this sensor, the robot can walk on unknown obstacles
without any force feedback, by online adaptation of foot height and
orientation. Moreover, the arm and hand of the robot have been designed to
grasp the objects with different stiffness and geometries that enable the
robot to do drilling, visual servoing of a moving object, and writing his name
on the white-board.

##  I INTRODUCTION

In recent years, many accomplishments have been carried out in the field of
humanoid robotics. The humanoid robots such as Atlas from Boston Dynamics and
Asimo from Honda are two frontiers, however, there is not technical
information available about these humanoid robots which highly rely on two
famous companies with massive sources of funding. The other full-size humanoid
robots such as Hubo[1], HRP robots family[2, 3], Jaxon[4], iCub[5],
Walkman[6], Valkyrie[7], Digit[8], TORO[9], Talos[10] are in a same level of
promising performances, so-called classic full-size humanoid robots.

All of these classic full-size humanoid robots have been developed by
collaboration with industrial companies[9, 6, 3, 10]. They were made by
advanced manufacturing systems to be rigid enough and have a minimum
deflection for applying the rigid body dynamics algorithms for locomotion
planning and control. The mechanical links of humanoid robots that are built
by students or by small manufacturers are made by bending or cutting and the
whole structure is fragile. By contrast, the classic humanoid robots use cast
mechanical links with high rigidity and lightweight using the most advanced
mechanical CAD. It was obvious that the cast links should have such
properties, but the links were too expensive to be developed by university
projects[11].

Moreover, the conventional position-controlled humanoid robots include 6-axis
Force/Torque sensors at the end-effectors of the legs and arms to control the
forces and torques[1, 2, 3, 12, 13]. Additionally, recently developed torque-
controlled humanoid robots include rotary torque sensors at each joints[9, 10]
which are expensive. Therefore, the Force/Torque sensors and the quality of
manufacturing are two important characteristics that will increase the cost of
humanoid robots drastically. For example, the cost of the Talos humanoid robot
developed recently by Pal-Robotics company is about one million
Euro.111https://spectrum.ieee.org/automaton/robotics/humanoids/talos-humanoid-
now-available-from-pal-robotics

Figure 1: The SURENA 4 humanoid robot

Although the force-torque sensors and high-quality manufacturing could be
necessary for exploiting the whole dynamic of the system in disaster scenarios
and athlete-type scenarios[14], there are many real-world scenarios that
humanoid robots do not need aggressive locomotion behaviors. As an example,
consider the scenarios in which there are narrow corridors and the humanoid
robot should pick and place some objects from one place in a factory to
another room by climbing stairs. While the advancement of recent years is
showing conventional humanoid robots will be able to do such scenarios in near
future[15], the main challenge for employing these robots is their high
cost[16] and it is the main reason that there exist a few research
institutions that are developing humanoid robots.

In this paper, we present SURENA 4, a full-size humanoid robot that has been
targeted for real-world scenarios under uncertainty. SURENA does not have
Force/Torque sensors and has been developed by a non-expensive manufacturing
process that is available in the universities. Considering these two factors
reduces the cost of the humanoid robot drastically, however, it will decrease
the controllability of the locomotion and manipulation because of considerable
deflection of the links of the robot and the lack of force feedback. The
deflection of the link causes a high amount of error for the foot position and
orientation and this error leads to the high impact of the foot on the ground
and as a consequence falling of the robot. One solution for tackling this
problem after impact is using a balance recovery algorithm [17, 18, 19] based
on estimated CoM[20], however, it’s reasonable to avoid impact beforehand
instead of using a balance recovery after impact. For solving this problem, we
propose a novel and cheap predictive foot sensor based on incremental encoders
and a control framework for adapting the configuration of the swing foot for a
smooth landing. This foot sensor facilitates dynamically locomotion with a
high amount of error in the foot position and orientation as well as enabling
the robot to walk on unknown obstacles.

For the manipulation task, controlling the force for grasping different
objects with different stiffness is important, and SURENA does not include any
Force/Torque sensor in hands. For tackling these challenges, we have designed
and implemented a hand based on the current feedback for grasping objects with
different stiffness so that the robot is able to drill a hole and write his
name on the white board.

##  II Mechanical Design

###  II-A Design Concepts OF SURENA 4 Humanoid Robot

SURENA 4 has been developed with the goal of establishment of key technologies
to have a cost-effective humanoid robot for real-world scenarios. The main
design concepts of SURENA 4 are:

  * •

Lower price

  * •

Minimizing of the overall mass

  * •

Center of mass(CoM) height as high as possible

  * •

Anthropomorphic design

In order to realize the cost-effective feature, we didn’t use any force/torque
sensor in the robot that are expensive. Instead of that, we used the available
facilities in the university that are not the most advanced tools. Therefore,
the manufactured parts and connections have deflection causes high amount of
error in the foot trajectory in swing mode. To tackle this challenge, we
designed a novel and inexpensive predictive foot sensor that enables the robot
to walk under this disturbances. To minimize the mass and inertia, we have
developed a compact actuator module. The details of these design concepts have
been elaborated in the next sections.

Figure 2: The design of the configuration of SURENA 4 a) The structure and components design b) The kinematic structure and degrees of freedom  TABLE I: Overview of SURENA 4 joint specifications.(Y=Yaw, R=Roll, P=Pitch) joint | motor | ratio | ${\dot{q}}_{max}$ | ${\tau}_{max}$ | range ∘
---|---|---|---|---|---
hip R | $RD50\times 14$ | 120 | 25 rpm | 60 Nm | -25..30
hip P | $RD50\times 14$ | 80 | 38 rpm | 40 Nm | $\pm 90$
hip Y | $RD50\times 14$ | 120 | 25 rpm | 60 Nm | $\pm 45$
knee P | RD450 | 50 | 60 rpm | 72 Nm | 0..135
ankle R | $RD50\times 08$ | 100 | 50 rpm | 27 Nm | $\pm 25$
ankle P | $RD50\times 08$ | 100 | 50 rpm | 27 Nm | -75..40
waist P | $RD70\times 18$ | 100 | 20 rpm | 120 Nm | -10..20
waist Y | MX106 | - | 45 rpm | 8 Nm | -15..15
shoulder P | $RD50\times 08$ | 120 | 50 rpm | 35 Nm | -90..45
shoulder R | $RD50\times 08$ | 120 | 50 rpm | 35 Nm | -10..90
shoulder Y | $RD38\times 06$ | 100 | 100 rpm | 10 Nm | -45..45
elbow P | $RD38\times 06$ | 100 | 100 rpm | 10 Nm | -90..-5
wrist Y | MX106 | - | 45 rpm | 8 Nm | -60..60
wrist R | MX106 | - | 45 rpm | 8 Nm | -25..25
wrist P | MX106 | - | 45 rpm | 8 Nm | -25..25
neck Y | MX106 | - | 45 rpm | 8 Nm | -60..60
neck R | MX106 | - | 45 rpm | 8 Nm | -15..15
neck P | MX106 | - | 45 rpm | 8 Nm | -15..25
fingers | PQ12 | - | 10 mm/s | 50 N | -
Figure 3: Driving unit integrating motor, harmonic-drive gear, incremental and
absolute position sensors. (here: Knee joint pitch axis)

###  II-B Lower-body

In design process of the legs, the important requirement is having highly
integrated module with the anthropomorphic characteristic in addition to low
mass and inertia and yet stiff structure. The legs of the SURENA 4 humanoid
robot are designed with 6 DoFs at each leg. The mechanical and kinematic
structure of the leg has been shown in the Fig. 2. There are 3 DoFs in the
hip, 1 in the knee and 2 in the ankle. The structural parts are made of an
magnesium alloy (AZ91) and optimized using FEM-based optimization and
iterative process to reduce the weight of the robot and having minimum
deflection at the same time.

We used a four bar mechanism for the ankle pitch axis to bring up the CoM as
much as possible Fig. 2. This mechanism allowed for a relatively slim ankle
design and decreased the shank’s inertia. The ankle pitch actuator is mounted
right below the knee, which allows for a comparably slim and strong ankle
design and decreases the leg’s inertia.

We identified the required joint torques and velocities by performing standard
motions (e.g. walking under different velocities) in simulations and
accordingly selected the actuation parameters (i.e. choice of motors and
gears). Table. I summarizes SURENA IV’s joint specifications.

###  II-C Actuator design

In order to meet the requirements of legged locomotion, the development of
compact and lightweight joint drives is crucial. We use BLDC brush-less
motors, because of their high power-to-weight ratio. The motors come as kit
motors, which provides a space and weight-saving integration into the joint.
The joints employ Harmonic-Drive gears as a gearbox. Their advantages are well
known and include no-backlash and high reduction ratios at a low weight. The
compact design of Harmonic-Drive component sets allows a space-saving
integration. All harmonic-drives are custom lightweight versions with a
T-shaped Circular Spline which is, in our experience, the best trade-off
between weight and loading capacity. The Wave Generators, modified for low
inertia and weight, are made from aluminum or steel. Angular measurement is
done incrementally on motor-side for commutation and again absolutely on the
load-side for calibration of the robot. Fig. 3 shows the components and design
structure of the knee joint pitch axis drive.

###  II-D Upper-body

In order to perform the required tasks, the following necessary features for
upper-body of SURENA 4 are considered:

  * •

Lower price

  * •

Ability to grasp various objects

  * •

Ability to make human like gestures

  * •

Light weight

  * •

Anthropomorphic design

Figure 4: The novel wrist mechanism to replicate the spherical joint

The upper body of the robot consists of the arm, hand and from waist to head.
In total, it consists of 31 DoFs. Each arm has 7 DoFs which make it redundant
and each hand includes 6 DoFs, two of which is for thumb and one for each
finger. In addition, the waist has 2 DoFs and neck has 3 DoFs as it has been
illustrated in Fig. 2. In the following, we describe the arm and hand design
in more details.

  * •

Arm design

The arm, along with the forearm, has 7 degrees of freedom. Shoulder roll and
shoulder pitch actuator are located on the shoulder joint, shoulder yaw
actuator is attached along the arm which exerts minimum load on it, although
remained intersected with the other two. Therefore, at the end of the
actuator, secondary support is used to tolerate the torque produced during
rotational motion of the actuator. Elbow has a rotation about pitch axis which
is quite clear. However, the forearm is the challenging part. As shown in Fig.
4 the challenge is to design a 3-DoF wrist while keeping their axis
intersected. The problem has been solved by converting rotary motion into a
linear motion and then convert it into rotary motion about a perpendicular
axis. Combination of rotation about pitch and roll axes makes the wrist joint
act like a spherical joint with minimum clearance. In the whole arm structure,
the combination of aluminum alloy and carbon fiber composite is used.

Figure 5: The design and fabrication of the hand and fingers of the robot

  * •

Hand design

Each robot’s hand has been designed to have a similar shape and performance to
human. It has six independent degrees of freedom. This design is done in a
modular manner so that each finger is an independent unit which can be removed
and repaired. In this case, for the purpose of reducing the number of
communication wires, an intermediate PCB is used at the back of the hand, in
which all sensors and actuators of the hand are connected to it and position
control of the fingers which ends up in making different gestures is done by
the micro controller mounted on it. In addition, six current sensors are used
to manage force control process by a threshold that is set for grasping
objects with different stiffness. This process has been implemented by a micro
controller which is mounted on this local board. Fig. 5 shows the design of
the hand and the 6-bar mechanism of the fingers in SURENA 4 humanoid robot.

Figure 6: The motion planning and control architecture

##  III MOTION PLANNING AND CONTROL

The Fig. 6 shows the proposed control architecture developed for SURENA 4. It
includes different layers that are described in the following sections.

###  III-A Motion Planning and Trajectory Optimization Layer

We propose a walking pattern generator for the SURENA 4 humanoid robot that
enables the robot to walk dynamically with lower peaks in the torque profile
of the ankle motors, which allows us using smaller motors with the purpose of
making the robot similar to the human morphology.

While various motion planning methods are developed based on full-dynamic
equations of the robot, the results of most of these planners are smooth
trajectories for the CoM but not a smooth motion for the pelvis of the robot,
and the motor trajectories calculated based on these methods would include
sharp changes that would be challenging for the low-level PID controllers to
accurately follow them. This might cause unwanted task-space trajectories or
leads to failure. Our method is based on the parameterization of the task-
space by polynomials to guarantee smooth motion of the robot, and the
coefficients are calculated by optimization of the ZMP derived from the full-
dynamic equation. Solving Inverse Kinematics between the desired planned
motions for the feet and the pelvis in each iteration gives the desired angles
of the joints.

Figure 7: The different control and phases of the height and orientation
adaptation of the swing foot based on the predictive foot sensor Figure 8:
The predictive foot sensor can predict the contact 1.5cm before contact event
a)Side view b)Bottom view

###  III-B Online Adaptation and Control System Layer

Some major challenges in controlling cost-effective humanoid robots are the
presence of deflections in parts and clearances in joints, especially in the
SS phase. In Fig. 9, deflections and clearances of the SURENA 4 humanoid robot
are shown. These phenomena are common among humanoid robots produced in
Universities, due to the low-cost manufacturing process and materials. During
the SS phase, the swing leg acts as a cantilever beam, and the early collision
of the swinging foot with the ground makes fast walking a challenge even on
flat terrain.

The humanoid robots should also be able to autonomously walk on uneven
terrain, especially when the variations are small and hard to be detected by
LiDAR sensors or Cameras. A novel controller method alongside new-inexpensive
contact sensors in the foot is exploited to effectively overcome the
aforementioned challenges. The controller is able to modify both position and
orientation of the swinging foot during the last moments of the SS phase (Fig.
8), to avoid the severe collision of the foot with the ground during dynamic
walking as follows:

  * •

Four rotary contact sensors are used on the four corners of each foot as
described in Fig. 8. These sensors are attached to encoders at their end, and
the distance of the four corners of the swinging foot to the ground would be
reported accurately when they are less than 1.5 cm as it is depicted in Fig.
8. Therefore, the average distance of the four corners and the relative pitch
and roll angles of the foot to the ground are fed back into the controlling
algorithm:

$d_{avg}=\frac{d_{A}+d_{B}+d_{C}+d_{D}}{4}$ (1)
$Pitch_{avg,rel}:\phi_{avg}\propto[\frac{d_{B}+d_{C}}{2}-\frac{d_{A}+d_{D}}{2}]/2$
(2)
$Roll_{avg,rel}:\alpha_{avg}\propto[\frac{d_{A}+d_{B}}{2}-\frac{d_{C}+d_{D}}{2}]/2$
(3)

Figure 9: The deflection and clearance of the connections leads to about 7 cm
error in swing foot motion while the motors are on and tracking the zero
position, a)Top view, b)Front view. The accompanying video illustrates this
problem. Figure 10: Walking on the unknown obstacle with a height of 1cm. The
accompanying video demonstrates this capability.

  * •

Due to the deflections in parts and clearances in the joints (as shown in Fig.
9), the relative angle between the swinging foot and the ground would have
errors during the SS phase. The calculated average feedback of the relative
angles is used in a cumulative controller to make the foot angles follow the
desired values by directly manipulating the ankle joints angles (pitch and
roll) trajectories. In each iteration (k), the cumulative errors are
calculated as follows:

$\phi_{CE}(k+1)=\phi_{CE}(k)+[\phi_{Des}(k+1)-\phi_{Avg}(k+1)]$ (4)
$\alpha_{CE}(k+1)=\alpha_{CE}(k)+[\alpha_{Des}(k+1)-\alpha_{avg}(k+1)]$ (5)

By simply adding the cumulative error to the desired Pitch and Roll angles in
the ankle joint, the input of the low-level controller modified as follows:

$\alpha_{input}(k+1)=\alpha_{des}(k+1)+\alpha_{CE}(k+1)$ (6)
$\phi_{input}(k+1)=\phi_{des}(k+1)+\phi_{CE}(k+1)$ (7)

  * •

It is important to note that the effects of deflections and clearances
disappear during the DS phase, and the swinging foot would act as the stance
foot in the next step. The changes in pitch and roll angles of the ankle joint
should be reduced to zero to prevent falling in future steps. This happens
during the initial moments of the DS phase when the robot is stable and no
longer requires the additional angles provided by the controller. The timeline
schematic of the ankle controller is provided in Fig. 7.

  * •

The early collision of the swinging foot with the ground happens due to the
deflections in parts and clearances in the joints. Unlike the angle
controller, the position controller manipulates the planned height motion of
the swinging foot (z-direction) to reduce the shocking effect of severe
collision during dynamic walking. A small threshold (20%) is also considered
to give the controller enough space and time to lay down the foot. When
$d_{avg}$ reaches the threshold earlier than expected by the planned
trajectories, the controller stops the foot and modifies the planned motion
with new polynomials to make the foot slowly lay down on the ground.

The experiments show that SURENA 4 is able to autonomously walk on surfaces
with bounded variations in elevation (1cm) and slope ($3^{\circ}$) with its
highest speed. The snapshots of the robot walking on uneven terrain are shown
in Fig. 10.

Figure 11: Left: Gripping objects with the different geometries and stiffness.
Right: Different tasks by using the combination of whole-body motion
generation, gripping and visual perception(The accompanying video shows the
performance).

###  III-C Upper-body Motion Generation and Control

We defined the visual servoing task that robots detects and follows the
position of an object (i.e. water bottle) with camera on his head and tracks
the position of the bottle by arm to reach the bottle and then proceed with
mentioned gripping algorithm to grasp the object. In addition, the robot is
able to write his name on the white board thanks to the anthropomorphic design
of the hand and arms in addition to the whole-body inverse-kinematic
controller. In Fig.11, the examples of manipulation tasks is shown.

In addition, the grasping of the objects with different stiffness and
geometries has been shown in Fig. 11.

##  IV DEVELOPMENT OF SOFTWARE AND ELECTRONICS ARCHITECTURE

Figure 12: The electronic and communications

Fig. 12 shows the electrical system and the communication protocols that have
been used in SURENA4 humanoid robot. The electronic system consists of two
major parts, the main processor and the FPGA board. The main processor
generates and sends data to actuators through the FPGA board. Afterward, the
FPGA board collects data from sensors and encoders that indicate the position
of each actuator and sends them back to the main processor. The total delay of
this procedure is 5 milliseconds. Hence, the frequency of executing the
control loop is 200 Hz.

###  IV-A Main processor

The main processor is a computer box that includes a core i7 CPU, 32 GB RAM,
and a 1060 NVidia GPU. This computer is responsible for decision making,
generating movement data, image and audio processing.

###  IV-B FPGA board

The FPGA board connects the main processor to actuators and sensors. This
board consists of a Xilinx ZYNQ-7020 that include FPGA and two ARM Cortex A9
processors. Using FGPA allows us to communicate with a large number of
interfaces simultaneously. The connection between the main processor and the
FPGA board is through a Gigabit Ethernet via UDP protocol. The connection
between the FPGA board and the motor driver is established via CAN protocol.
We used a separate CAN controller to drive each motor by the CAN interface to
reach real-time communication.

###  IV-C Software architecture

Communication between different parts of the control application is
accomplished by the Robot Operating System (ROS) framework. The SURENA 4
control system consists of four main ROS nodes: simulation node, motor control
node, motion planner node, and state estimation node.

Several simulators are available under ROS such as Gazebo which is widely
used, however, Gazebo is relying on the ODE dynamic engine that based on our
experience is not the best simulator for the biped robot walking that depend
on dynamic contact switching. As it has been illustrated in the Fig. 13 the
simulation has been done in both Choreonoid and Gazebo. In our experience,
Choreonoid that is based on the AistSimulator[21] Dynamic Engine provides a
better result and more meaningful simulations with respect to the real
experiment.

Figure 13: Simulation environments:a) Simulation of SURENA walking in Gazebo,
b) Simulation of SURENA slope climbing in the Choreonoid

##  V Conclusions

In this paper, we have presented a cost-effective humanoid robot with an
anthropomorphic design. The robot components have been manufactured by the
university facilities where connections and links have deflections and
clearance that causes a high amount of error of about 7 cm of the foot
trajectory tracking in task-space in swing mode.This will cause severe impact
with ground and falling will happen as a consequence. We presented a novel
predictive foot sensor in addition to a full dynamic optimization-based motion
planning that enables not only walking with a high amount of foot trajectory
error but also locomotion on uneven terrain without any force feedback. This
feature facilitates the development of a humanoid robot with non-expensive and
simple available manufacturing tools and still robust to a high amount of
unknown uncertainty that reduces drastically the price of developing humanoid
robots. In addition, we presented an anthropomorphic hand and arm design which
enable the robot to do different tasks such as grasping objects with different
stiffness and geometries, drilling, visual servoing of moving objects, and
writing his name on the white-board without any force feedback and only by
current feedback of the customized hand actuators.

## ACKNOWLEDGMENT

The authors would like to thank the industrial design and artificial
intelligence groups respectively for developing the cover and the perception
of the robot.

## References

  * [1] T. Jung, J. Lim, H. Bae, K. K. Lee, H.-M. Joe, and J.-H. Oh, “Development of the humanoid disaster response platform drc-hubo+,” _IEEE Transactions on Robotics_ , vol. 34, no. 1, pp. 1–17, 2018.
  * [2] K. Kaneko, F. Kanehiro, M. Morisawa, K. Akachi, G. Miyamori, A. Hayashi, and N. Kanehira, “Humanoid robot HRP-4 - Humanoid robotics platform with lightweight and slim body,” in _IEEE Int. Conf. Intell. Robot. Syst._ , 2011\.
  * [3] K. Kaneko, H. Kaminaga, T. Sakaguchi, S. Kajita, M. Morisawa, I. Kumagai, and F. Kanehiro, “Humanoid robot hrp-5p: An electrically actuated humanoid robot with high-power and wide-range joints,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 1431–1438, 2019.
  * [4] K. Kojima, T. Karasawa, T. Kozuki, E. Kuroiwa, S. Yukizaki, S. Iwaishi, T. Ishikawa, R. Koyama, S. Noda, F. Sugai, _et al._ , “Development of life-sized high-power humanoid robot jaxon for real-world use,” in _2015 IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids)_. IEEE, 2015, pp. 838–843.
  * [5] N. G. Tsagarakis, G. Metta, G. Sandini, D. Vernon, R. Beira, F. Becchi, L. Righetti, J. Santos-Victor, A. J. Ijspeert, M. C. Carrozza, and D. G. Caldwell, “ICub: The design and realization of an open humanoid platform for cognitive and neuroscience research,” _Adv. Robot._ , 2007.
  * [6] N. G. Tsagarakis, D. G. Caldwell, F. Negrello, W. Choi, L. Baccelliere, V. G. Loc, J. Noorden, L. Muratore, A. Margan, A. Cardellino, L. Natale, E. Mingo Hoffman, H. Dallali, N. Kashiri, J. Malzahn, J. Lee, P. Kryczka, D. Kanoulas, M. Garabini, M. Catalano, M. Ferrati, V. Varricchio, L. Pallottino, C. Pavan, A. Bicchi, A. Settimi, A. Rocchi, and A. Ajoudani, “WALK-MAN: A High-Performance Humanoid Platform for Realistic Environments,” _J. F. Robot._ , 2017.
  * [7] N. A. Radford, P. Strawser, K. Hambuchen, J. S. Mehling, W. K. Verdeyen, A. S. Donnan, J. Holley, J. Sanchez, V. Nguyen, L. Bridgwater, _et al._ , “Valkyrie: Nasa’s first bipedal humanoid robot,” _Journal of Field Robotics_ , vol. 32, no. 3, pp. 397–419, 2015.
  * [8] A. Aggarwal, “Digit humanoid robot,” https://www.agilityrobotics.com/meet-digit, May 2020.
  * [9] J. Englsberger, A. Werner, C. Ott, B. Henze, M. A. Roa, G. Garofalo, R. Burger, A. Beyer, O. Eiberger, K. Schmid, _et al._ , “Overview of the torque-controlled humanoid robot toro,” in _2014 IEEE-RAS International Conference on Humanoid Robots_. IEEE, 2014, pp. 916–923.
  * [10] O. Stasse, T. Flayols, R. Budhiraja, K. Giraud-Esclasse, J. Carpentier, J. Mirabel, A. Del Prete, P. Souères, N. Mansard, F. Lamiraux, _et al._ , “Talos: A new humanoid research platform targeted for industrial applications,” in _2017 IEEE-RAS 17th International Conference on Humanoid Robotics (Humanoids)_. IEEE, 2017, pp. 689–695.
  * [11] S. Kajita, H. Hirukawa, K. Harada, and K. Yokoi, _Introduction to humanoid robotics_. Springer, 2014, vol. 101.
  * [12] H. Jeong, K. Lee, W. Kim, I. Lee, and J.-H. Oh, “Design and control of the rapid legged platform gazelle,” _Mechatronics_ , vol. 66, p. 102319, 2020\.
  * [13] T. Buschmann, S. Lohmeier, and H. Ulbrich, “Humanoid robot lola: Design and walking control,” _Journal of physiology-Paris_ , vol. 103, no. 3-5, pp. 141–148, 2009.
  * [14] T. Kamioka, H. Kaneko, T. Takenaka, and T. Yoshiike, “Simultaneous optimization of zmp and footsteps based on the analytical solution of divergent component of motion,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 1763–1770.
  * [15] A. Kheddar, S. Caron, P. Gergondet, A. Comport, A. Tanguy, C. Ott, B. Henze, G. Mesesan, J. Englsberger, M. A. Roa, _et al._ , “Humanoid robots in aircraft manufacturing: The airbus use cases,” _IEEE Robotics & Automation Magazine_, vol. 26, no. 4, pp. 30–45, 2019.
  * [16] P. Kopacek, “Cost oriented humanoid robots,” _IFAC Proceedings Volumes_ , vol. 44, no. 1, pp. 12 680–12 685, 2011.
  * [17] M. Shafiee, G. Romualdi, S. Dafarra, F. J. A. Chavez, and D. Pucci, “Online dcm trajectory generation for push recovery of torque-controlled humanoid robots,” in _2019 IEEE-RAS 19th International Conference on Humanoid Robots (Humanoids)_. IEEE, 2019, pp. 671–678.
  * [18] M. Shafiee-Ashtiani, A. Yousefi-Koma, R. Mirjalili, H. Maleki, and M. Karimi, “Push recovery of a position-controlled humanoid robot based on capture point feedback control,” in _2017 5th RSI International Conference on Robotics and Mechatronics (ICRoM)_. IEEE, 2017, pp. 126–131.
  * [19] M. Shafiee-Ashtiani, A. Yousefi-Koma, and M. Shariat-Panahi, “Robust bipedal locomotion control based on model predictive control and divergent component of motion,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 3505–3510.
  * [20] H. Alai, F. A. Shirazi, and A. Yousefi-Koma, “New approach to center of mass estimation for humanoid robots based on sensor measurements and general lipm,” in _2018 6th RSI International Conference on Robotics and Mechatronics (IcRoM)_. IEEE, 2018, pp. 388–393.
  * [21] S. Nakaoka, “Choreonoid: Extensible virtual robot environment built on an integrated gui framework,” in _2012 IEEE/SICE International Symposium on System Integration (SII)_. IEEE, 2012, pp. 79–85.