# Comment on
“The phase diagram of the multi-matrix
model with ABAB-interaction from
functional renormalization”

Carlos I. Pérez-Sánchez  Faculty of Physics, University of Warsaw
..——————————————————————-–.-ul. Pasteura 5, 02-093 Warsaw, Poland
…………………………————————————————–.-European Union
<EMAIL_ADDRESS>
###### Abstract.

Recently, [JHEP 20 131 (2020)] obtained (a similar, scaled version of) the
($a,b$)-phase diagram derived from the Kazakov–Zinn-Justin solution of the
Hermitian two-matrix model with interactions

$-\operatorname{Tr}\Big{\\{}\frac{a}{4}(A^{4}+B^{4})+\frac{b}{2}ABAB\Big{\\}}\,,$

starting from Functional Renormalization. We comment on something unexpected:
the phase diagram of [JHEP 20 131 (2020)] is based on a $\beta_{b}$-function
that does not have the one-loop structure of the Wetterich-Morris Equation.
This raises the question of how to reproduce the phase diagram from a set of
$\beta$-functions that is, in its totality, consistent with Functional
Renormalization. A non-minimalist, yet simple truncation that could lead to
the phase diagram is provided. Additionally, we identify the ensemble for
which the result of op. cit. would be entirely correct.

##  1\. Main claim and organization

We prove the following: For a Hermitian two-matrix model including the
‘$ABAB$-interaction’ vertex

$\frac{b}{2}\operatorname{Tr}\,(ABAB)=\raisebox{-0.415pt}{\includegraphics[width=49.86867pt]{Listones/Feo_ABAB}}$

the only one-loop, one-particle irreducible (1PI) diagram of order $b^{2}$
that has connected external leg structure—that is, such that it contributes to
a connected-boundary correlation function—is

(1.1)

Its external leg structure is the cyclic word $ABBA$, represented by . This
implies that the $\beta_{b}$-function given in [1, Eq. 3.41], namely

$\displaystyle\beta_{b}\stackrel{{\scriptstyle}}{{=}}(\eta_{A}+\eta_{B}+1)\times
b-\underbrace{\frac{2}{5}\big{[}(5-\eta_{A})+(5-\eta_{B})\big{]}\times\,b^{2}}_{\text{\tiny
1-loop structure $\Rightarrow$ coeff. of $b^{2}$ must be 0}},$ (1.2)

does not have the one-loop structure of the Wetterich-Morris equation in
Functional Renormalization111Here $\eta_{A}$ and $\eta_{B}$ are the anomalous
dimensions for the matrices $A$ and $B$, but this is irrelevant, since the
coefficient of $b^{2}$ should identically vanish. (this is relevant, since the
phase diagram [1, Fig. 1] relies only on $\beta_{b}$). For the quadratic term
$b^{2}$ to be present in this equation, the graph (1.1) would need to have an
external $ABAB$-structure. In other words, for eq. (1.2) to hold, after
‘filling the loop’ in (1.1) and shrinking the disk to a point, the remaining
graph should read, just like the vertex,

Different infrared regulators might lead to different coefficients (containing
non-perturbative information), but the one-loop structure in Functional
Renormalization should be evident; this means that the coefficient of $b^{2}$
in $\beta_{b}$ must vanish.

Next, in Section 2, these statements are presented in detail in Claims 2.1,
2.2 and 2.3 (at the risk of being redundant) and proven. A short (albeit, rich
in examples) user’s guide to colored ribbon graphs (Section 2.1) prepares the
core of this comment (Section 2.2). In Section 3 we further propose a more
generous truncation to obtain the phase diagram. We compute in the large-$N$
limit without further notice.

##  2\. Context, definitions, examples and proofs

The two-matrix model in question has the following partition function222We
respect here the notation of [1], the exception being renaming their
$(\alpha,\beta)$ to $(a,b)$ as to avoid ‘$\beta_{\beta}$’.

$\displaystyle\mathcal{Z}=C_{N}\iint_{\mathcal{H}_{N}\times\mathcal{H}_{N}}\mathrm{e}^{-\frac{N}{2}(\operatorname{Tr}A^{2}+\operatorname{Tr}B^{2})-NS_{\text{int}}(A,B)}\mathrm{d}A\,\mathrm{d}B$
(2.1a) with $C_{N}$ a normalization constant and $\mathrm{d}A$ and
$\mathrm{d}B$ both the Lebesgue measure on the space $\mathcal{H}_{N}$ of
Hermitian $N\times N$ matrices, and interaction $\displaystyle
S_{\text{int}}(A,B)=-\frac{a}{4}\operatorname{Tr}(A^{4}+B^{4})-\frac{b}{2}\operatorname{Tr}(ABAB)\,.$
(2.1b) In 1999, the $ABAB$-model (2.1) was exactly solved by Kazakov and (P.)
Zinn-Justin, who presented in [2, Fig. 4] a phase diagram of right-angled
trapezoidal form for the couplings ($a,b$), called there ($\alpha,\beta$) as
well as in [1]. A consistent phase diagram with trapezoidal form (i.e.
predicting $\approx 1/10$ for both critical exact $a_{\star}=b_{\star}=1/4\pi$
values) is one of the main results presented in [1], who addressed the model
(2.1) using Functional Renormalization. The phase diagram [1, Fig. 1] obtained
from $(\beta_{a},\beta_{b})$ follows from a correct expression for $\beta_{a}$
but also from
$\beta_{b}\stackrel{{\scriptstyle}}{{=}}\big{(}\eta_{A}+\eta_{B}+1\big{)}b-{\frac{2}{5}\left[(5-\eta_{A})+(5-\eta_{B})\right]b^{2}}$,
which is [1, Eq. 3.41]. We prove here that the $\beta_{b}$-function is
incompatible with the well-known333The statement (revisited below) follows
from the form of the Wetterich-Morris equation and appears e.g. in [1, Sec.
3.1 §1] ‘As the full propagator enters, non-perturbative physics is captured,
despite the one-loop structure’. It also appears in several introductory texts
to Functional Renormalization, e.g. [3]. one-loop structure [4] of Wetterich-
Morris Functional Renormalization Group Equation [5, 6]. While the behavior
$\beta_{g}\sim g^{2}+\ldots$ is indeed common for other quartic operators
$g\mathcal{O}$, this does not happen for $b\operatorname{Tr}(ABAB)$. The rest
of the section introduces the terminology (Section 2.1) and proves in detail
the claims (Section 2.2).

###  2.1. Colored ribbon graphs in multi-matrix models by example

Feynman graphs turn out to be useful also for ‘non-perturbative [4]
renormalization’. For sake of accessibility to a broader readership, we
provide in this section an (incomplete) user’s guide to graphs in multi-matrix
models.

The representation of the integrals of matrix models using ribbon graphs (or
fat graphs), famous due to ’t Hooft [7], is of paramount importance both in
physics and mathematics; applications are also worth mentioning [8, 9] (see in
particular its relation to discrete surfaces or maps studied by Brezin-
Itzykson-Parisi-Zuber [10]). The theory of ribbon graphs can be formulated in
an extremely precise way [11], but for the purpose of this comment, the most
important feature is that their vertices have a cyclic ordering—this is
typically depicted with the aid of a disk with some thick strips (half-edges)
disjointly attached to it. Each strip represents a matrix, and these are
adhered (in our convention, clockwise) to the vertex, as in the following
picture:

$g\operatorname{Tr}(AACDBCDB)\leftrightarrow\raisebox{-0.415pt}{\includegraphics[width=73.7146pt]{Listones/Octagono_Disco}}\,\,\,$

where $A,B,C,D$ are matrices of the same ensemble444This vertex will not be
used, this example only aims at explaining the concept with some more
clarity.. Sometimes the disk is omitted, as we often do below, and the
coupling constant (here $g$), too. The rotation of the vertex is conform with
the cyclicity of the trace, but one is not allowed to reflect the picture.

This way, ribbon vertices, unlike ordinary ones, are sensitive to non-cyclic
reorderings of the half-edges (see e.g. [12, Fig. 1 and eq. (18)]). The
representation of the interaction (2.1b) in terms of ribbon (or fat) vertices
reads555In case of color-blindness, we are calling green the lighter lines and
red the darker ones. These represent $A$ and $B$, respectively. :

$\displaystyle-
S_{\text{int}}(A,B)=\raisebox{-0.415pt}{\includegraphics[width=49.86867pt]{Listones/Feo_AAAA}}+\raisebox{-0.415pt}{\includegraphics[width=49.86867pt]{Listones/Feo_BBBB}}+\raisebox{-0.415pt}{\includegraphics[width=49.86867pt]{Listones/Feo_ABAB}}\,$
(2.2)

Since the above graphical representation will be used only as a cross-check,
we ignore the symmetry factors (strictly, we should put a root on one edge of
each interaction vertex) and also absorb the couplings in the vertices. The
cyclic ordering means, in particular, that

$\displaystyle\raisebox{-0.415pt}{\includegraphics[width=44.01306pt]{Listones/Feo_ABAB}}\neq\raisebox{-0.415pt}{\includegraphics[width=44.01306pt]{Listones/Feo_RibbonsABBA}},\mbox{
which faithfully represents the obvious:
$\operatorname{Tr}(ABAB)\equiv\\!\\!\\!\\!\\!/\,\,\operatorname{Tr}(ABBA)$}.$
(2.3)

Edges are also fat (double lines) and consist of pairings of half-edges (which
for Hermitian matrix models cannot have net ‘twists’ ). In order to emphasize
that these arise from propagators, we shade the edges. While for a one-matrix
model all edges are equal—for instance, the next graph arising in a quartic
one-matrix model,

(2.4)

—the new feature in multi-matrix models the coloring of the edges. In the
$ABAB$-model (which contains the $A^{4}$ and $B^{4}$ interactions) the graph
(2.4) is possible in green (implying only the $A$ matrix) or in red (only
$B$), but a coloring of the graph (2.4) in such a way that it contains (at
least one occurrence of) the $ABAB$-vertex is not possible. An example of a
ribbon graph with two such vertices is

(2.5)

in which also the vertices $v_{i}$, edges or propagators666The propagators are
shaded and they respect the color of the associated matrix. $e_{i}$, and faces
$f_{i}$ are depicted (a face is a boundary component of the ribbon graph; here
we have three bounded faces, $f_{1},f_{2},f_{3}$, and one unbounded, $f_{4}$).
The colored ribbon graphs of multi-matrix models, just as their uncolored
version, have a topology determined by the Euler number $\chi$ (where
$\chi=\\#\,$vertices $-\\#\,$edges$\,+\\#\,$faces, in this case clearly
$\chi=2$, corresponding to a spherical topology; this turns out to be
important, since the scaling of the graph amplitudes with the matrix size $N$
is $\sim N^{\chi}$). If we would have an octic interaction vertex
$g\operatorname{Tr}(ABABABAB)$, one of the (several) possible diagrams is

(2.6)

One can verify, by starting at any point of the boundary of the diagram—say,
at the point $P$ in the picture—and by following the arrows, that when one
comes back to $P$, one has already visited the whole boundary once. Therefore,
this fat graph has a single face. In that picture, the arrow with a 45∘ angle
$|\nearrow$ emphasizes the criterion to travel along the circle that defines
the boundary of the face: when one arrives at the disk (marked with the
coupling $g$) one picks the closest single-line, regardless of the color, for
the cyclic order at the vertex determines precisely, which goes next. The
counting of vertices (one), faces (one) and edges (four) exhibits its non-
planarity (i.e. it cannot be draw of a sphere; the best one can do is draw it
without intersections on a surface of genus 2) but below we will find only
planar diagrams.

So far, all examples we presented are vacuum graphs. We now consider also
graphs having half-edges that are not contracted, as in

(2.7)

A face of a ribbon graph is said to be unbroken if no (uncontracted) half-
edges are incident to it; the face is otherwise said to be broken, precisely
by the incident half-edges. (Thus, vacuum graphs can only have unbroken
faces.) In the graph (2.7), the faces $f_{1}$ and $f_{2}$ are unbroken, while
the unbounded face $f_{3}$ is broken by the two red half-edges pointing
northeast and northwest.

Given a (colored) ribbon graph one can forget the cyclic ordering of its
vertices (and if present, the coloring of its edges) and thus obtain a graph
in the ordinary sense. For instance,

$\displaystyle\raisebox{-0.37pt}{
\includegraphics[width=69.0pt]{Listones/Feynman_Ribbons_quartic}}\,\,\mapsto\,\,\raisebox{-0.36pt}{\includegraphics[width=39.0pt]{Listones/einfache}}$
(2.8)

and

$\displaystyle\raisebox{-0.3pt}{
\includegraphics[width=40.0pt]{Listones/Feo_example}}\,\,\mapsto\,\,\raisebox{-0.36pt}{\includegraphics[width=39.0pt]{Listones/project_ordinary_graph}}$
(2.9)

Notice that to the uncontracted half-edges of the ribbon graphs one associates
leaf (degree one vertex). A connected (colored) ribbon graph is said to have a
one-loop structure if its underlying ordinary graph has a one-loop structure,
that is, if the latter has a first Betti number777The first Betti number of a
connected ordinary graph $G$ is $b_{1}(G)=\\#\text{edges of
}G-\\#\text{vertices of }G+1$, so ‘one-loop’ means that the number of edges
equals the number of vertices. Notice that the ‘external edges’ are attached
to a vertex. This definition of $b_{1}$ also matches other conventions, where
external edges have no vertices attached, but then it is given by
$b_{1}(G)=\\#\text{internal edges of }G-\\#\text{vertices of }G+1$ equal to 1;
alternatively, if it has one independent cycle. Therefore (2.9) above has a
one-loop structure, but neither of the following has it:

$\displaystyle\mapsto\quad\raisebox{-0.13pt}{\includegraphics[width=49.0pt]{Listones/ordinary_graph_noloops}}$
(2.10a)
$\displaystyle\mapsto\quad\raisebox{-0.13pt}{\includegraphics[width=40.0pt]{Listones/ordinary_graph_2loops}}$
(2.10b)

for the upper ribbon graph has no loops and the other has three.

A connected (colored) ribbon graph is one-particle irreducible (1PI) if its
underlying ordinary graph is 1PI. An ordinary graph is 1PI if it is neither a
tree—a graph for which there is a unique path between any two given
vertices—nor it can be disconnected by removing exactly one edge. The
(ordinary) graph in (2.10a) is a tree and it can be disconnected by cutting
either the straight or the curved edge. Therefore the fat graph in (2.10a) not
1PI. On the other hand, the ordinary graph in (2.10b) is neither a tree (for
there exist vertices connected by more than one path) and if one removes any
edge, it remains connected. Therefore its primitive ribbon graph in the left
of (2.10b) is 1PI. The next example is not at tree,

(2.11)

but removing one propagator (the green one in position  $(\\!($) disconnects
it, so it is not 1PI.

We now introduce the last concept. The external leg structure of a ribbon
graph with one broken face is obtained by reading off clockwise the cyclic
word formed by the matrices (associated with the half-edges) that break that
face, going around the boundary-loop exactly once. This process is known in
the matrix field theory literature [13] (illustrated in [14, Sec. 5]) and a
generalization to multi-matrix models requires to additionally list the half-
edges respecting the coloring. We illustrate this concept, reusing graphs
previously drawn:

  1. $\bullet$

Concerning the graph (2.7): it has an external leg structure $BB$, since going
along the $f_{3}$ face, one meets twice a red line.

  2. $\bullet$

The graph (2.9) has external leg structure $ABBA$

  3. $\bullet$

The ribbon graph in (2.10a) has external leg structure $AAABAABA$

  4. $\bullet$

That in (2.10b) has external leg structure $AA$

An external leg structure determines in a natural way a new interaction vertex
of matrix models just by ‘taking its trace’. The cyclicity of the external leg
structure yields well-definedness. In the list of external leg structures of 1
through 4, these correspond, to 1. $\operatorname{Tr}(B^{2})$, 2\.
$\operatorname{Tr}(ABBA)$, and 3. $\operatorname{Tr}(AAABAABA)$ and 4.
$\operatorname{Tr}(A^{2})$. The next example probably explains why we
restricted ourselves to graphs with a single broken face,

(2.12)

The face inside the red loop yields $A^{2}$; the same from the outer face.
Thus, the external leg structure of (2.12) is the disjoint union of $A^{2}$
with $A^{2}$. Graphs with more than one broken face will not appear below,
since these lead to multi-traces, in the case of (2.12) to
$\operatorname{Tr}(A^{2})\times\operatorname{Tr}(A^{2})$, and these multi-
trace interactions are not consider in the article we are commenting (but are
treated in [15]). But the idea of a more general setting is depicted in Figure
1.

We are done with the terminology. In the following section we prove the
claims.

###  2.2. Proofs

In the Functional Renormalization Group parlance, one says that the RG-flow
generates the interaction vertices that arise from the external leg structure,
whenever these come from a one-loop graph. The one-loop condition is a
consequence of the ‘supertrace’ present in Wetterich Equation888Without giving
a full description (for that we refer to [15]) we recall that $R_{N}$ is the
infrared regulator; that $\Gamma^{(2)}_{N}$ is the Hessian of the
interpolating effective action $\Gamma_{N}$; and that $t=\log N$ is the RG-
time.
$\partial_{t}\Gamma_{N}=\frac{1}{2}\mathrm{STr}\,\big{\\{}\partial_{t}R_{N}/[R_{N}+\Gamma^{(2)}_{N}]\big{\\}}$.
This makes some of the graphs listed above uninteresting from the viewpoint of
renormalization, as they do not have a one-loop structure. Those which do,
have also some drawbacks: (2.9) has a one-loop structure, and is a graph
generated by the RG-flow in the $ABAB$-model, but that sextic vertex is set to
zero in the truncation that [1] considers. On the other hand, the graph (2.12)
is a Feynman graph containing only vertices of the $ABAB$-model, but it leads
to a double-trace, and so on.

This hopefully slowly starts to convince the reader that the 1PI and the one-
loop conditions heavily restrict the graphs that play a role in the FRG; this
is the flavor of the proofs below, where in fact, we obtain certain kind of
uniqueness. Consider the following graph:

$\displaystyle\mathcal{G}:=\raisebox{-0.415pt}{\includegraphics[width=80.21863pt]{Listones/Feo_RibbonsABAB_ABAB90}}\,\,$
(2.13)

It has a broken face and an unbroken one, and when one glues a disk along the
boundary this happens:

Figure 1. The gray part is an abstract representation of a multi-matrix model
planar graph (after ‘vulcanizing’ the unbroken faces and forgetting everything
but broken faces) with two faces broken by uncontracted half-edges. These
boundaries determine the external leg structure decorating the cylinder (the
two broken faces are interpreted as excised discs from $\mathbb{S}^{2}$ here).
The 4-leg boundary in the upper right corner yields the cyclic word $ABBA$ (or
$AABB$, or$\ldots$); the 6-legged one is $AABABA$ (or $AAABAB,\ldots$). The
external leg structure is the disjoint union of these words.

######  Claim 2.1.

The external leg structure of the graph $\mathcal{G}$ given by (2.13) is
$ABBA$, i.e.

###### Proof.

In $\mathcal{G}$ one has a single broken face (it can be recognized in the
drawing (2.13) as the face that is unbounded). Starting at any point one reads
off at the boundary of such face the word $ABBA$. One could also read off
$BBAA$, $AABB$ or $BAAB$, depending on where one chooses to start. Yet,
nothing changes, since the external leg structure is cyclic by definition. ∎

######  Claim 2.2.

The unique $($connected$\hskip 0.81pt)$ one-loop 1PI graph of order $b^{2}$
having a connected external leg structure is the graph $\mathcal{G}$ defined
by (2.13).

In this statement the connectedness of the external leg structure means that
$\mathcal{G}$ has a single broken face.

###### Proof.

By assumption, the graph has two interaction $ABAB$-vertices; let us name
$V_{1}$ and $V_{2}$ the two copies. The 1PI-assumption constrains the $p$
propagators implied in the graph to $p>1$ (indeed, since the graph should be
connected, and has two interaction vertices, a propagator should connect
these. Should the graph have a single propagator, then removing it would yield
a disconnected graph contradicting the 1PI assumption). On the other hand, the
one-loop condition implies $p<3$ (if $p\geq 3$ then more loops are formed).
Again, since the graph in question is 1PI, the $p=2$ propagators implied in
the graph connect $V_{1}$ with $V_{2}$. If they connect two equal colors, we
get a disconnected external leg structure, i.e. either the graph (2.12) or its
$A\leftrightarrow B$ (i.e. green $\leftrightarrow$ red) version. Therefore, by
assumption, the two propagators connecting $V_{1}$ with $V_{2}$ must have
different color. The only such graph having also a connected external leg
structure is $\mathcal{G}$ defined by (2.13). ∎

It is a Quantum Field Theory folklore result (see e.g. [16] and [17, Sec.
3.3]) that the effective action is the generating functional of 1PI graphs.
Since neither the cyclicity of the vertices999The cyclicity of the vertices is
of course a key feature for the power counting $N^{\chi}$, but this and one-
particle irreducibility are independent properties. nor the coloring of thick
edges has influence on the 1PI property, the effective action in multi-matrix
models generates 1PI colored ribbon graphs; thus, that folklore result remains
true in this setting. Further, the Functional Renormalization Equation governs
the interpolating effective action, hence the 1PI condition is imposed from
the outset101010The exception is the vertices appearing as linear terms in the
$\beta$-functions.. We have, in view of this:

######  Claim 2.3.

For the particular operator $-\frac{b}{2}\operatorname{Tr}(ABAB)$, a quadratic
term $b^{2}$ in $\beta_{b}$ is not possible in Functional Renormalization
$($in other words the coefficient of $b^{2}$ in $\beta_{b}$ vanishes, or in
notation, $[b^{2}]\beta_{b}=0$$)$.

###### Proof.

Wetterich-Morris Equation imposes the one-loop structure on any non-linear
term in the coupling constants (i.e. on any non-vertex) appearing in each
$\beta$-function. For the $\beta_{b}$-function, in particular, a second
condition is that the external leg structure must be $ABAB$. These two
conditions are mutually exclusive. Indeed, by Claim 2.2, the only such
$\mathcal{O}(b^{2})$ graph is $\mathcal{G}$, which, by Claim 2.1, has an
external leg structure $ABBA$.∎

######  Remark 2.4.

Some closely related, but not essential points:

  * $\bullet$

The correlation functions of matrix [13] and tensor field theories are indexed
by boundary graphs [18]. The terminology makes sense graph theoretically but
also geometrically in both the matrix and tensor field [14] contexts. In the
case of matrix models, boundary graphs coincide with what we call here
external leg structure. In matrix models, there are as many $\beta$-functions
as correlation functions, hence the importance of the external leg structure.
The map defined by ‘taking the boundary’ seems also to play a role in other
renormalization theories, like Connes-Kreimer Hopf algebra approach [19]. In
that theory for matrices (related construction appears in [20]) taking the
boundary seems to be the residue map in terms of which one can define the
coproduct of the Hopf algebra (also true [21] for the Ben Geloun-Rivasseau
tensor field theory [22]).

  * $\bullet$

Other graphs might appear for real symmetric matrices, but the ribbons
corresponding to Hermitian matrices remain untwisted, which played a role in
the uniqueness of the graph above. It is not exaggerated to stress the reason
for this rigidity, which is explained by the difference in the propagators of
matrix models in ensembles $\\{M\in M_{N}(\mathbb{K})\mid M^{\dagger}=M\\}$
for different fields $\mathbb{K}$, i.e.

$\displaystyle\langle
M_{ij}M_{kl}\rangle_{\mathbb{K}}=\frac{1}{N}\begin{cases}\displaystyle\frac{1}{2}\Big{(}\begin{array}[]{c}i\\\\[-5.0pt]
j\end{array}\\!\\!\raisebox{-0.3pt}{\includegraphics[width=43.36464pt]{Listones/match}}\begin{array}[]{c}l\\\\[-5.0pt]
k\end{array}+\begin{array}[]{c}i\\\\[-5.0pt]
j\end{array}\\!\\!\raisebox{-0.3pt}{\includegraphics[width=43.36464pt]{Listones/mismatch}}\begin{array}[]{c}l\\\\[-5.0pt]
k\end{array}\Big{)}&\mathbb{K}=\mathbb{R}\,\,(\text{symmetric
real})\\\\[8.61108pt]
\phantom{\displaystyle\frac{1}{2}\bigg{(}}\begin{array}[]{c}i\\\\[-5.0pt]
j\end{array}\\!\\!\raisebox{-0.3pt}{\includegraphics[width=43.36464pt]{Listones/match}}\begin{array}[]{c}l\\\\[-5.0pt]
k\end{array}&\mathbb{K}=\mathbb{C}\,\,(\text{Hermitian})\end{cases}$ (2.14)

##  3\. A proposal to obtain the Kazakov–Zinn-Justin phase diagram

We recall that in [1] the truncation is minimal. Thus, the running operators
are also those in the bare action in eqs. (2.1a)-(2.1b).

In that truncation [1], if one computes correctly, $\beta_{b}\sim b$ (the
value of the vertex); this is not wrong, but only says that such truncation
threw away useful information. In order not to ‘waste’ the $b^{2}$ term, we
propose to add the operator that captures it, so the new effective action
reads:

$\displaystyle\Gamma_{N}[A,B]=\frac{Z}{2}\operatorname{Tr}(A^{2}+B^{2})-\frac{\bar{a}}{4}\operatorname{Tr}(A^{4}+B^{4})-\frac{\bar{b}}{2}\operatorname{Tr}(ABAB)-\bar{c}\operatorname{Tr}(ABBA)\,,$
(3.1)

where bar on quantities means unrenormalized and $Z$ is the (now common) wave
function renormalization. The $ABBA$-operator also respects the original
$\mathbb{Z}_{2}$-symmetries:

$\displaystyle(A,B)\mapsto(B,A),\quad(A,B)\mapsto(-A,B)\,,\quad(A,B)\mapsto(A,-B)\,.$
(3.2)

Now, $b^{2}$ does appear, but in the $\beta_{c}$-function. In fact
$\beta_{c}\sim b^{2}+c^{2}+2ac$, ignoring the contribution ($\propto\,c$) of
the vertex. This relation was obtained with the (‘coordinate-free’) method
presented in [15, around Corollary 4.2]. Removing the symmetry condition
($g_{AAAA}=a=g_{BBBB}$) we initially imposed on the couplings for $A^{4}$ and
$B^{4}$, and writing in full $g_{w}$ for the coupling of
$\operatorname{Tr}\\{w(A,B)\\}$, being $w$ a cyclic word in $A,B$, one
has111111Or
$\beta{(g_{ABBA})}-g_{ABBA}(\eta_{A}+\eta_{B}+1)\sim{g_{AAAA}\times
g_{ABBA}}+g_{BBBB}\times g_{ABBA}+(g_{ABAB})^{2}+{(g_{ABBA})^{2}}$ in case
that colors distract the reader.

$\displaystyle\qquad\qquad\beta{(g_{\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A\color[rgb]{0.84,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.84,0,0}BB\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A})}-g_{\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A\color[rgb]{0.84,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.84,0,0}BB\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A}(2\eta+1)$
$\displaystyle\sim{g_{\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}AAAA}\times
g_{\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A\color[rgb]{0.84,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.84,0,0}BB\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A}}+g_{\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}BBBB}\times
g_{\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A\color[rgb]{0.84,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.84,0,0}BB\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A}$
$\displaystyle\\!\qquad+(g_{\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A\color[rgb]{0.84,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.84,0,0}B\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A\color[rgb]{0.84,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.84,0,0}B})^{2}+{(g_{\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A\color[rgb]{0.84,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.84,0,0}BB\color[rgb]{0,0.67,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.67,0}A})^{2}}\,,$
(3.3a) obtained without the use of graphs. The missing coefficients (hidden in
$\sim$ and implying the anomalous dimension $\eta=-N\partial_{N}Z$) are
regulator-dependent and contain non-perturbative information, but the
essential point is that now each $\beta$-function has a transparent one-loop
structure; to wit, the RHS of (3.3a) corresponds (respecting the order in that
sum121212Of course, the rotation of these graphs plays no role, since only the
cyclic order matters. We display some vertically, and others horizontally for
sake of the reader’s comfort: this way, she or he can start reading the word
from the upper left corner anticlockwise and this order will coincide with the
order of the word in the corresponding coupling constant.) with
$\displaystyle\raisebox{-0.412pt}{\includegraphics[width=43.36464pt]{Listones/Feo_RibbonsA4_AABB90}}\,\,\,+\,\,\,\raisebox{-0.412pt}{\includegraphics[width=43.36464pt]{Listones/Feo_RibbonsB4_AABB90}}\,\,\,+\,\,\raisebox{-0.415pt}{\includegraphics[width=78.9218pt]{Listones/Feo_RibbonsABAB_ABAB90}}\,\,+\,\,\raisebox{-0.415pt}{\includegraphics[width=78.9218pt]{Listones/Feo_RibbonsAABB_AABB90}}\,$
(3.3b)

It is also clear that the cyclic external leg structure of each of these terms
is $ABBA$. Since it is easy to confuse the order of the letters, we stress
that this is already an extended version of the $ABAB$-model to exemplify the
one-loop structure of another coupling constant. But expressions (3.3) also
give the (by Claim 2.2 unique) $\beta$-function where the $b^{2}$ actually has
to sit.

Adding the $ABBA$ operator modifies the flow (for, now,
$\beta_{b}-b(1+2\eta)\sim bc$) but in order to get the desired fixed points,
higher-degree operators might still be required. As pointed out in the
paragraph before [1, Sec. 3.3] when addressing higher-degree operators,
$\operatorname{Tr}[(AB)^{3}]$ is indeed forbidden. However, there are degree-
six operators that do preserve the symmetries (3.2), concretely
$\operatorname{Tr}(ABABAA)$ or $\operatorname{Tr}(ABABBB)$, and contribute to
the $\beta_{b}$-function (see [15, Thm. 7.2], where the RG-flow has been
computed adding these operators), thus enriching the truncation.

######  Remark 3.1.

Some closing points one could learn from [1]:

  * $\bullet$

Notice that if we could somehow make $ABAB$ indistinguishable from $ABBA$,
then the $\beta_{b}$-function [1, Eq. 3.41] would be, in that case, correct;
see (2.3). This happens for a sub-ensemble of pairs of Hermitian matrices
$A,B$ such that $AB$ is Hermitian (for then, $A$ and $B$ commute).

  * $\bullet$

Notice that the graph

(3.4)

would yield the $b^{2}$ term needed in [1, Eq. 3.41]. However, this graph is
not possible, since the Ising operator $\sigma\operatorname{Tr}(AB)$, depicted
with the bicolored bead and responsible for ‘changing color’, is not in the
truncation behind that equation; moreover, if added, it violates two
symmetries in (3.2), on top of $b^{2}$ being screened by $\sigma^{2}$ (that
graph is a one-loop containing four operators: two Ising, two $ABAB$,
alternated). Nevertheless, it seems plausible that the contamination of the
running operators (i.e. considering operators that are not unitary invariant)
might effectively lead to a color-change, as in (3.4).

##  4\. Conclusion

We showed that the connection that [1] established between the Functional
Renormalization Group (FRG) and a phase diagram—identified there with [2, Fig.
4]—relies on a $\beta$-function that does not have the one-loop structure of
the Functional Renormalization Equation. In Section 3 above, we proposed to
extend the minimalist truncation of [1] in order to find a FRG-compatible set
of $\beta$-functions. Accomplishing this proposal would provide a
sound131313This is not is not the same as ‘complete’. Analytic aspects should
still be addressed, but these require more effort. In order for this not to be
in vain, it is a good idea to start from a correct combinatorics. bridge, in
the intention of [1], between the FRG and Causal Dynamical Triangulations [23]
through the $ABAB$-model [24, 25]. Finally, we provided in Remark 3.1 the
condition one would need to add in order for the $\beta_{b}$-function given by
[1, Eq. 3.41] to be correct.

## Acknowledgements

The author was supported by the TEAM programme of the Foundation for Polish
Science co-financed by the European Union under the European Regional
Development Fund (POIR.04.04.00-00-5C55/17-00).

## References

  * [1] A. Eichhorn, A.D. Pereira and A.G. Pithis, _The phase diagram of the multi-matrix model with ABAB-interaction from functional renormalization_ , _JHEP_ 20 (2020) 131 [2009.05111].
  * [2] V.A. Kazakov and P. Zinn-Justin, _Two matrix model with ABAB interaction_ , _Nucl. Phys. B_ 546 (1999) 647 [hep-th/9808043].
  * [3] H. Gies, _Introduction to the functional RG and applications to gauge theories_ , _Lect. Notes Phys._ 852 (2012) 287 [hep-ph/0611146].
  * [4] J. Berges, N. Tetradis and C. Wetterich, _Nonperturbative renormalization flow in quantum field theory and statistical physics_ , _Phys. Rept._ 363 (2002) 223 [hep-ph/0005122].
  * [5] C. Wetterich, _Exact evolution equation for the effective potential_ , _Phys. Lett. B_ 301 (1993) 90 [1710.05815].
  * [6] T.R. Morris, _The Exact renormalization group and approximate solutions_ , _Int. J. Mod. Phys. A_ 9 (1994) 2411 [hep-ph/9308265].
  * [7] G. ’t Hooft, _A Planar Diagram Theory for Strong Interactions_ , _Nucl. Phys._ B72 (1974) 461.
  * [8] J.E. Andersen, L.O. Chekhov, R.C. Penner, C.M. Reidys and P. Sułkowski, _Topological recursion for chord diagrams, RNA complexes, and cells in moduli spaces_ , _Nucl. Phys._ B866 (2013) 414 [1205.0658].
  * [9] J.E. Andersen, L.O. Chekhov, R. Penner, C.M. Reidys and P. Sulkowski, _Enumeration of RNA complexes via random matrix theory_ , _Biochem. Soc. Trans._ 41 (2013) 652 [1303.1326].
  * [10] E. Brezin, C. Itzykson, G. Parisi and J. Zuber, _Planar Diagrams_ , _Commun. Math. Phys._ 59 (1978) 35.
  * [11] R.C. Penner, _Perturbative series and the moduli space of Riemann surfaces_ , _J. Diff. Geom._ 27 (1988) 35.
  * [12] C.I. Pérez-Sánchez, _Surgery in colored tensor models_ , _J. Geom. Phys._ 120 (2017) 262 [1608.00246].
  * [13] H. Grosse and R. Wulkenhaar, _Self-Dual Noncommutative $\phi^{4}$ -Theory in Four Dimensions is a Non-Perturbatively Solvable and Non-Trivial Quantum Field Theory_, _Commun. Math. Phys._ 329 (2014) 1069 [1205.0465].
  * [14] C.I. Pérez-Sánchez, _The full Ward-Takahashi Identity for colored tensor models_ , _Commun. Math. Phys._ 358 (2018) 589 [1608.08134].
  * [15] C.I. Pérez-Sánchez, _On multimatrix models motivated by random Noncommutative Geometry I: the Functional Renormalization Group as a flow in the free algebra_ , _Ann. Henri Poincaré_ (2021)  [2007.10914].
  * [16] R.E. Borcherds and A. Barnard, _Lectures on Quantum Field Theory_ , math-ph/0204014.
  * [17] A. Connes and M. Marcolli, _Noncommutative Geometry, Quantum Fields and Motives_ , American Mathematical Society (2007).
  * [18] V. Bonzom, R. Gurău, J.P. Ryan and A. Tanasă, _The double scaling limit of random tensor models_ , _JHEP_ 09 (2014) 051 [1404.7517].
  * [19] A. Connes and D. Kreimer, _Renormalization in quantum field theory and the Riemann-Hilbert problem. 1. The Hopf algebra structure of graphs and the main theorem_ , _Commun. Math. Phys._ 210 (2000) 249 [hep-th/9912092].
  * [20] A. Tanasă and F. Vignes-Tourneret, _Hopf algebra of non-commutative field theory_ , _J. Noncommutat. Geom._ 2 (2008) 125 [0707.4143].
  * [21] M. Raasakka and A. Tanasă, _Combinatorial Hopf algebra for the Ben Geloun-Rivasseau tensor field theory_ , _Sem. Lothar. Combin._ 70 (2014) B70d [1306.1022].
  * [22] J. Ben Geloun and V. Rivasseau, _A Renormalizable 4-Dimensional Tensor Field Theory_ , _Commun. Math. Phys._ 318 (2013) 69 [1111.4997].
  * [23] J. Ambjørn, J. Jurkiewicz, R. Loll and G. Vernizzi, _Lorentzian 3-D gravity with wormholes via matrix models_ , _JHEP_ 09 (2001) 022 [hep-th/0106082].
  * [24] J. Ambjørn, J. Jurkiewicz, R. Loll and G. Vernizzi, _3-D Lorentzian quantum gravity from the asymmetric ABAB matrix model_ , _Acta Phys. Polon. B_ 34 (2003) 4667 [hep-th/0311072].
  * [25] J. Ambjørn, J. Jurkiewicz and R. Loll, _Renormalization of 3-d quantum gravity from matrix models_ , _Phys. Lett. B_ 581 (2004) 255 [hep-th/0307263].


# Differentiation in a Two-Dimensional Market with Endogenous Sequential
Entry††thanks: Corresponding author email<EMAIL_ADDRESS>Preliminary
draft, do not cite without permission. We greatly appreciate the assistance of
and helpful comments from conference participants at the AAEA Annual Meetings
in Seattle, WA. We are solely responsible for any errors or misunderstandings.

Jeffrey D. Michler  _Department of Agricultural and Resource Economics,
University of Arizona, Tucson, USA_ Benjamin M. Gramig  _Dept. of Agricultural
and Consumer Economics, University of Illinois, Urbana, USA_

(March 2021)

###### Abstract

Previous research on two-dimensional extensions of Hotelling’s location game
has argued that spatial competition leads to maximum differentiation in one
dimensions and minimum differentiation in the other dimension. We expand on
existing models to allow for endogenous entry into the market. We find that
competition may lead to the min/max finding of previous work but also may lead
to maximum differentiation in both dimensions. The critical issue in
determining the degree of differentiation is if existing firms are seeking to
deter entry of a new firm or to maximizing profits within an existing, stable
market.

_JEL Classification_ : D43, L11, L13
_Keywords_ : Spatial competition, Hotelling model, Entry deterence

##  1 Introduction

Despite adages on the importance of location for business profitability,
little work has been done to expand rudimentary one-dimensional economic
models of location choice into a more realistic two-dimensions. Location
choice in these models is often interpreted as taking place in product space
instead of physical space. Yet, despite the multi-dimensional characteristics
of most products, existing models still focus on product differentiation along
a single dimension. The purpose of this paper is to take an exploratory step
in expanding models of product differentiation or location choice into a
second dimension.

The location game was first developed by Hotelling (1929). The game is played
between $n$ firms in one-dimensional space with consumers uniformly
distributed along an interval normalized to $[0,1]$. Firms are homogeneous
with zero production costs. Consumers purchase a single unit of the good from
the firm closest to their location at a uniform price, $p$. If a consumer is
equidistant between two firms, they split their purchases equally between the
two firms. Firms enter the market simultaneously and attempt to maximize
profit. There is no single solution to Hotelling’s game. Rather, solutions are
dependent on the number of firms in the game. It is worth noting that solution
to Hotelling’s game, while optimal for the profit maximizing firm, are not
socially optimal.

A socially optimal configuration can be achieved by imposing the restriction
that firms, once located, cannot move. Additionally, entry in this game is
generally assumed to be sequential. Independently, Hay (1976) and Rothschild
(1976) derived solutions for the sequential entry, fixed location game. When
location is fixed and entry sequential, firms will space themselves at uniform
distances along the line. This solution is distinct from the Hotelling
solution of agglomeration in that it is not only stable but socially optimal.
The mobility constraint is enough to turn an inefficient equilibrium into an
efficient one. For the most part, the literature has neglected to explore the
implications of this transition in equilibriums.

A few papers have attempted to expand the Hotelling model into two dimensions
but this is a small subset of the papers devoted to spatial competition (see
Eiselt et al. 1993 for a good, though dated, review of this literature). Since
Hakimi (1983), most location games in real space have defined the problem in
terms of medianoid and centroid - polygon shaped areas to be maximized. These
problems are computationally complex and without some fixed starting point or
limiting assumption they tend to fall into the NP classification of problems.
The limiting assumption that location, once chosen, is fixed greatly reduce
the problem’s degree of difficulty. Lane (1980) and Veendorp and Majeed (1995)
each have taken this fixed location approach in order to simplify the multi-
dimensional problem. Yet, in both cases while the model accommodates two-
dimensions, the authors make additional assumptions to reduce the problem to
the classic single dimension.

In both one-dimensional and two-dimensional space, when firms enter
simultaneously and are mobile, the location problem is an indefinitely
repeated game and generally lacks pure strategies. When firms enter
sequentially and are mobile, no pure strategy exists on the line and solutions
are generally unattainable in two-dimensional space. However, when firms enter
sequentially and are fixed, a pure strategy exists on the line. Furthermore,
that strategy results in a stable and sometime socially optimal equilibrium.
In the model that follows, we adopt the fixed firm approach to simplify and
solve for a stable equilibrium to the location game in two-dimensions.
Furthermore, we examine the equilibrium to determine if it is socially
optimal.

Our results resemble those derived by Neven (1987) and Gotz (2005) for an
endogenous sequential entry location game. As opposed to the Hotelling Model,
in two-dimensions firms do not agglomerate but attempt to maximize their
differentiation from other firms. As opposed to Veendorp and Majeed (1995),
who argue that firms would maximize differentiation in one dimension while
minimizing differentiation in a second dimension, we find that firms will
sometimes pursue maximimum differentiation in both dimensions. The
characterization of the firm’s location (max or min differentiation) depends
on the potential for subsequent entrants. Similar to the results for a single
dimension in Neven (1987) and Gotz (2005), we find that firms use location as
a deterrence mechanism. In two-dimensions, firms maximize their distance from
other firms along all dimensions when there is no threat of subsequent entry
while ”filling in” gaps in the market space when the threat of a subsequent
entrant arises.

In section 2, we lay out the model for location choice in two-dimensions. In
section 3, we present the results from our numerical simulation, showing the
location choice is a function of the market size . Section 4 contains our
discussion of the results while section 5 concludes.

##  2 The Model

We begin by defining the space over which the location choice is made as well
as how firms are organized in that space. Consider a finite number of
homogeneous firms. Identify each firms as $i\in I=(1,2,...,n)$. The location
of $i$ is $(x_{i1},x_{i2})=\bf{x_{i}}$ in subspace $S$ of two-dimensional
Cartesian space. Let $S$ be a square of unit length. Let
$\bf{X}=(\bf{x_{1}^{T}},\bf{x_{2}^{T}},...,\bf{x_{n}^{T}})^{T}$ be a vector of
$2n$ elements where T is the transpose operator. We define a configuration as
a combination of firm locations in the subspace $C=(\textbf{X},S)$.

###  2.1 Consumers

For consumers, we modify the model developed by Veendorp and Majeed (1995). In
their paper, the authors set up the problem from the firm’s perspective, where
the firm maximizes the difference between price and the cost of delivering the
good from its location at $\bf{x_{i}}$ to the consumer located at
$\bf{\hat{x}}$. In order to facilitate comparability with the recent
literature, especially those of Economides, et al. (2002) and Gotz (2005), we
redefine the problem from the consumer’s perspective.

There is a continuum of consumers uniformily distributed over subspace $S$
with density $M$. Each consumer expresses unit demand so that the density,
$M$, is a measure of the market size. Let consumer location in subspace $S$ be
defined as $(\hat{x}_{1},\hat{x}_{2})=\bf{\hat{x}}$. One can interpret
$\bf{\hat{x}}$ as either the physical location of a type of consumers or as
the most preferred product variety from a set of product varieties $\bf{X}$.

While consumers are heterogeneous by type, they share the same utility
function. Consumer’s utility from purchasing a good from firm $i$ is:

$U_{\mathbf{\hat{x}}}^{i}=a-t\sqrt{(\mathbf{x}_{i}-\mathbf{\hat{x}})^{2}}-p_{i}=a-t\sqrt{(x_{i1}-\hat{x}_{1})^{2}+(x_{i2}-\hat{x}_{2})^{2}}-p_{i}$
$None$

where $a$ is the reservation value for the good, which is common to all
consumers and sufficiently large so as to assure all consumers purchase the
good. $p_{i}$ is the price chareged for the good charged by firm $i$.
Transportation costs, $t$, are normalized to 1, without loss of generality.

###  2.2 Firms

To solve the location problem we must first define the boundaries of the
market to which a firm sells. The boundary points allow us to determining the
market size for each firm, and thus the quantity of the good a firm sells. The
boundary points are defined by the consumer who is indifferent between
purchasing the good from firm $i$ or firm $j$. Following Neven’s (1987) one-
dimensional approach, define
$\alpha_{i,j}=(\mathbf{x}_{i},\mathbf{x}_{j},p_{i},p_{j})$ as the consumer
indifferent between $\mathbf{x}_{i}$ at price $p_{i}$ and $\mathbf{x}_{j}$ at
price $p_{j}$, such that $U_{\alpha_{i,j}}^{i}=U_{\alpha_{i,j}}^{j}$. The
model’s set up allows for differentiation along both axes and contains as a
special case the one dimensional model of Nevens (1987) and Gotz (2005).

In the single dimensional model, a firm’s market share can be completely
characterized by just two consumers. If Firms $i,j,k$ are located sequentially
along the line segment [0,1], then firm $i$’s market share is
$D_{i}=M(\alpha_{i,j}-0)$ while firm $j$’s market share is
$D_{j}=M(\alpha_{j,k}-\alpha_{i,j})$ and firm $k$’s market share is
$D_{k}=M(1-\alpha_{j,k})$. In two dimensions, a firm’s market share is defined
by a vector of indifferent consumers that marks the boundary between two
firms. Furthermore, while along the line a firm will have no more than two
neighboring competitors, on the plane a firm may have $n-1$ neighboring
competitors.

Because of these complications, the simplest method for defining a firm’s
market space in two dimensions is with a Voronoi Polygon. For firm $i$, every
point $\bf{x}$ that is closer to $\mathbf{x}_{i}$ than to $\mathbf{x}_{j}$ is
in the Voronoi polygon $V(\mathbf{x}_{i})$.

$V(\mathbf{x}_{i})=\\{\mathbf{x}:\
\parallel\mathbf{x}_{i}-\mathbf{x}\parallel\ \leq\
\parallel\mathbf{x}_{j}-\mathbf{x}\parallel,\rm\ j\in I\\}$ $None$

Given our assumptions regarding the distribution of consumers, firm $i$’s
market share is

$V_{i}=\alpha M\ \ \ \text{where}\ \ \
\alpha=\\{\alpha:\alpha=\alpha_{i,j},j\in I\\}$ $None$

What Equation (4) says is that one can measure the size of firm $i$’s market
by taking the convex hull of the market space, as defined by the vectors of
consumers indifferent between purchasing the good from $i$ or all of $i$’s $j$
competitors, and multiplying that by the density of consumers.

The firm’s problem then is the following:

$\max_{p_{i},\mathbf{x}_{i}}\pi_{i}=(p_{i}-c)V_{i}-F$ $None$

where $c$ and $F$ are the firm’s marginal and fixed costs of production. We
can set $c=0$ without effecting the generalizability of our results. Each firm
chooses a price and a location to maximize its profit but since price is a
function of the prices and location of other firms, as well as its own
location, the profit function can be re-written in terms of the single choice
variable, $\mathbf{x}_{i}$.

###  2.3 The Location Choice Problem

The location game proceeds as follows: In the first stage, each firm enters
sequentially and chooses a location. After all firms have entered, the second
stage begins in which firms compete on price. While sequential entry is a
natural candidate for a dynamic model, we adopt Neven’s (1987) assumption that
firms’ discount rates are low so that profits earned during the transitory
entry periods are negligible when compared to long run profits. While this
assumption limits the possibly interesting dynamic aspect of the model, it
lends justification for the fixed location assumption. Profits to be gained in
the short run by a move from one location to another are outweighed by the
fixed cost.

Consider, then, the problem for firm $N$, the last firm to enter. The firm can
see the locations of all $N-1$ firms. Since prices are a function of location,
firm $N$ can determine the prices that will prevail at the selected locations.
This reduces firm $N$’s problem to a single unknown and gives rise to a
solution, $\mathbf{x}_{N}(\mathbf{x}_{1},...,\mathbf{x}_{N-1})$, that
specifies the location of firm $N$ in terms of the locations of all other
firms. Thus, each firm has only to solve a single equation in a single
unknown. Using backward induction we continue this process from the last firm
to enter to the first firm to enter. In each case, the location of preceding
firms is known and the location of subsequent firms will be given by the
choice function that we have already solved.

Lane (1980) showed that in one dimension, for a given set of locations a
unique price equilibrium exists. However, there is no proof for the existence
of a unique location equilibrium. This is because the location choice function
is not necessarily a continuous function. The lack of a proof for a unique
location equilibrium does not mean location equilibriums do not exist, only
that we cannot demonstrate that a given equilibrium is the unique equilibrium.
We thus follow the literature and adopt numerical techniques to solve the
dynamic programming problem [See Prescott and Visscher (1977) as well as Lane
(1980)].

##  3 Equilibrium Location Choices

In the location game, the equilibrium depends on the ratio between fixed
costs, $F$, and market size, $M$. We choose to set $F=25$ and vary the market
size. The results show firm locations shifting to deter entry as the market
size increases. These shifts are not continuous nor are they symmetric. As has
been noted since Eaton and Lipsey (1975), when given the opportunity, firms
strategically use location (in physical or product space) to deter entry of
competing firms.

In the interest of brevity, we limit our presentation to two characteristic
location equilibria for each set of firms. The first is immediately after a
firm enters and there is no threat of, and therefore no need to deter, a new
entrant. The second is immediately prior to a new entrant, meaning there is a
need to deter entry. The locations for 1, 2, and 3 firms in two dimensions are
the same as they would be in one dimension. The locations become more
interesting when we move to 4 and more firms.

###  3.1 One, Two, and Three Active Firms

Initially, a single firm can locate anywhere in a square market for small $M$.
Eventually, as the density of the market increases (or equivalently, the size
of the market grows), the firm will have to locate in the center of the market
to deter entry of a second firm. $x_{1}=(1/2,1/2)$. See Figure 1 at back.

While in the Hotelling model, firms locate next to each other in the center of
the market, in two dimensions they locate as far away as possible so that they
can minimize price competition. However, this is only the case when there is
no threat of a third firm entering. The two firms locate closer and closer to
each other as they balance the need to maximize market space with the need to
deter entry of a third firm. Eventually the two firms locate at the thirds.
These, then, are the threshold cases. Case 1 is when a second firm can just
enter the market and firms locate at far ends, such as $x_{1}=(0,1/2)$ and
$x_{2}=(1,1/2)$. Note that there is no unique location equalibrium but rather
a set of possible location equilibrium. This set contains the borders of the
market with the second firm locating the maximum distance from the first
firm’s location. [See Figure 2 for an example]. Case 2 is immediately prior to
entry by a third firm. In this case, firms are located at the thirds on one
axis and at the half on the other, $x_{1}=(1/3,1/2)$ and $x_{2}=(2/3,1/2)$.
See Figure 3 at back.

When considering three active firms, we again have two threshold cases to
consider. One when the third firm just enters the market. The other when a
fourth firm is about to enter but has yet to enter. When a third firm first
enters the market, the locations are
$x_{1}=(.426,.5),x_{2}=(.889,.5),x_{3}=(.074,.5)$. [See Figure 4]. While in
the previous cases, firms located symmetrically and earned equal profits, once
a third firm enters, rents accrue to early entrants. In this case, firm 1
earns excess profits due to the firm’s first mover status. The firm is able to
choose a location that forces the second entrant to locate at the far side of
the market and induces the third entrant to locate in the its ”backyard.”
Thus, firm 1 is able to secure a market share larger than the subsequent
entrants.

As it becomes possible for a fourth firm to enter, all three firms attempt to
defer entry by locating towards the quarter points. At the point where the
three firms cannot stop a fourth firms from entering, they would be at the
following locations: $x_{1}=(1/4,1/2),x_{2}=(3/4,1/2),x_{3}=(1/2,1/2)$. [See
Figure 5]. The first firm is no longer in the central location but chooses an
outside location as does the second firm. The third firm would prefer to
choose a location as far away from firm 1 and 2 as possible (say $(1/2,1)$) in
order to maximize its market share and minimize price competition. However,
the need to deter entry by a fourth firm results in firm 3 locating between
firm 1 and 2. The benefit of such a location for firm 3 is that is blocks
entry by firm 4, guaranteeing it higher profits than if it had located in the
hinterland and allowed entry by a fourth firm.

###  3.2 Four, Five, and Six Active Firms

When a fourth firm enters the market, the equilibrium characteristics change.
With 1-3 firms, firms strove for maximum differentiation on one axis why
accepting minimum differentiation on the other axis. This is due less to
strategic decision making on the part of the firms and more to the geometry of
the space. The locations of two firms can always be connected by a single
vector and thus can never achieve differentiation along both axes. A third
firm could locate off of the vector connecting the first two firms yet these
locations turn out not to be profit maximizing.

With the immediate entry of a fourth firm, each firm locates at the corners of
the market space: $x_{1}=(0,0),x_{2}=(1,1),x_{3}=(0,1),x_{4}=(1,0)$. [See
Figure 6]. This minimizes price competition by maximizing the distance between
each firm. As the need arises to deter the entry of a fifth firm, the first
four firms locate in positions that divide the market equally into quarters:
$x_{1}=(1/4,1/4),x_{2}=(3/4,3/4),x_{3}=(1/4,3/4),x_{4}=(3/4,1/4)$. [See Figure
7]. As was the case with two firms, locations in the four firm case are
symmetric, dividing the market space equally. This result is not only unique
to even numbers of competing firms, it is unique to $N=2,4$. As will be seen,
the symmetric location choices hold in $N=6$ yet these locations no longer
divide the space equally. We conjecture that symmetric locations are a
characteristic for all games with even numbers of firms competing while only
equal profits for all firms only arise in $N=2,4$.

When a fifth firm is just able to enter, the four firms would adopt slightly
”asymmetric” locations, as occurred with firm 1 and 2 when firm 3 was just
able to enter. In this case, firm 1 and 2 select more profitable locations by
shading towards one market boundary. This ensures that firm five does not
locate in their neighborhood but in the neighborhood of firm three and four:
$x_{1}=(.25,.15),x_{2}=(.75,.15),x_{3}=(.25,.65),x_{4}=(.75,.65),x_{5}=(.5,1)$.
[See Figure 8]. When a sixth firm is about to enter, the five competing firms
locate similar to the fifth face of a six-sided die. As with previous cases,
firm accept stiffer price competition amongst themselves as the cost of
deterring the entry of another firm. While the first four firms are able to
secure equal market sizes, firm five, as the last entrant, receives less
profit. Locations are
$x_{1}=(1/4,1/4),x_{2}=(3/4,3/4),x_{3}=(1/4,3/4),x_{4}=(3/4,1/4),x_{5}=(1/2,1/2)$.
[See Figure 9.

When a sixth firm just enters the market, all firms locate along the borders
to try and maximize their distance from each other:
$x_{1}=(0,1/2),x_{2}=(1,1/2),x_{3}=(0,1),x_{4}=(1,0),x_{5}=(0,0),x_{6}=(1,1)$.
[See Figure 10]. As mentioned above, though the locations are symmetric, the
resulting market size is asymmetric. Firm 1 and 2 locate as they did in the
$N=2$ case, forcing the subsequent four firms to take locations in the corners
of the market. The first two entrants earn rents from their early entry into
the market. Subsequent firms are indifferent regarding which corner they
locate in, since they cannot earn more profits in one corner compared to
another. As it became necessary to deter entry of firm 7, the first 6 firms
locate in the interior of the market [See Figure 11].

A curious result is that firms 3,4,5 and 6 prefer this configuration to the
initial configuration when there was no chance of firm 7 entering. A similar
asymmetry in the burden of deterrence can be seen to a lesser extent in the
$N=5$ firm case. This asymmetry in who bears the burden of deterrence was
first noticed in the one dimensional case by Gotz (2005).

##  4 Comparison of Results

Several new insights emerge when we examine endogenous sequential entry in two
dimensions instead of just one. First, for small $N$, specifically $N=1,2,3$,
optimal locations in two dimensions are equivalent to optimal locations in one
dimension. Numerous papers that examine endogenous sequential entry in one
dimension, most prominently Lane (1980) and Veendorp and Majeed (1995), have
conjectured that little insight is to be gained by expansion of the location
problem into two dimensions. Our results show that this conjecture, while
accurate for $N=1,2,3$ is erroneous for $N\geq 4$. Something similar can be
found in Okabe and Suzuki (1987) for the two dimensional simultaneous entry
problem. Eaton and Lipsey (1975) had conjectured that no stable equilibria
exist when firms enter simultaneously into a two dimensional market. Shaked
(1975) had proven this for up to three firms. It was not till Okabe and Suzuki
(1987) that it was demonstrated stable equilibria do exist for large $N$. In
our problem, the equivalence between locations in one and two dimensions for
1, 2, or 3 firms does not carry over for more than 3 firms. We have examined
the cases up to $N=7$ and observe that a pattern develops. However, we can
only conjecture that this pattern carries beyond $N=7$.

Our second insight involves the asymmetry in the burden of entry deterrence.
As noted above, when a firm has just entered the market, the earlier entrants
are able to select preferred locations, earning rents, and forcing the new
entrant into a less preferred location. These rents are diminished by the need
to deter entry by subsequent firms. In their attempt to restrict competition
to a small number of firms, more profitable firms sacrifice profit to less
profitable firms, thereby increasing equity between the operating firms. Thus,
late entrants prefer a market environment where the threat of additional
entrants exist to one that is secure for further competition.

Our third insight involves the social optimality of the location equilibria.
We define social optimality as the minimum total transportation cost:

$F(\bf{X^{*}})=\min_{\bf{X}}F(\bf{X})$ $None$

where
$\bf{X^{*}}=(\bf{x_{1}^{*^{T}}},\bf{x_{2}^{*^{T}}},...,\bf{x_{n}^{*^{T}}})^{T}$.
The problem with such a concept is that $F(\bf{X^{*}})$ is nonconvex so there
is not a unique optimal solution. This is because from the consumer’s
perspective
$(\bf{x_{1}^{*^{T}}},\bf{x_{2}^{*^{T}}},...,\bf{x_{n}^{*^{T}}})^{T}=(\bf{x_{2}^{*^{T}}},\bf{x_{1}^{*^{T}}},...,\bf{x_{n}^{*^{T}}})^{T}$.
Since all firms are homogenous, consumers are indifferent between which firm
they buy from. Not only are socially optimal equilibria not unique, they are
generally not the type of equilibria that arise when firms solve their profit
maximization problem. The only equilibria that are socially optimal are those
that arise to deter entry of an additional firm. Thus, the threat of a new
entrant results in both a more equitable distribution of profits and a
socially optimal configuration of firms.

Finally, the way that firms pursue differentiation in the market is
fundamentally different in two dimensions than it is in one dimension. If we
think of product characteristic space instead of physical space, these results
have very intuitive interpretations. When firms in a market do not have to
worry about the entry of an additional firm they pursue maximum product
differentiation. But, when there is the potential for a new firm to enter the
market, the firms ”move” or ”locate” their products closer to each other. They
do no try to pursue minimum product differentiation but rather accept greater
similarity in product characteristics to ward off further entry. Put another
way, when there is no threat of a new product coming into the market, existing
firms trumpet how different their product is from those of the other operating
firms. When the threat of a new product entering the market arises, firms
shift their strategy to try and ”fill in” the product space. Where before they
”advertised” how their product was different from all others, now they
”advertise” how their product has similar characteristics to all the others.
Basically, no firm wants to leave a gap in the market where a new firm could
enter so all existing firms produce products with some of each characteristic.
This ensures that a new firm cannot enter into the market by claiming ”buy our
product because it has a full compliment of $x$ while that other product has
zero for $x$.” Rather, to keep that new entrant out, existing firms produce a
product that has some level of $x$ so a new entrant cannot slip into an
unexploited product characteristic zone.

##  5 Conclusion

Little beyond intelligent conjecture has been done on location models in two
dimensional space, especially when entry is sequential and the number of firms
is endogenous to the market. This gap in the literature is curious for two
reasons. First, conjectures regarding equilibria in two dimensions for
simultaneous entry were proven to be incorrect (Okabe and Suzuki, 1987). This
paper has attempted to examine conjectures regarding equilibria in two
dimensions when entry is sequential. While the conjectures put forth by the
literature are accurate for $N=1,2,3$ firms, they are inaccurate for larger
numbers of firms. Second, most products have characteristics along more than
one dimension and a model of how firms choose location in two dimensions could
prove useful. Our results show that the two dimensional model leads to
insights not present in the one dimensional model.

Among the insights that arise from our model we believe the most interesting
are the asymmetric burden of deterrence and the shifting approach to product
differentiation. The first insight provides two dimensional verification for a
phenomenon first observed by Gotz (2005) in a single dimension. If we think of
the growth of the market space ($N$) as a dynamic process, then early entrants
capture rents in the form of higher profits. Yet, these rents are eroded as
the market grows and the need to deter new entrants arises. There is a move
towards a more equitable outcome among active firms in an attempt to prevent
more intense competition. The analogy is not completely accurate yet is
suggestive. The second insight fails to verify the results presented in
Veendorp and Majeed (1995). In their model of a two dimensional market they
found firms minimized differentiation along one dimension while maximized
differentiation along a second dimension. While this is the case when the
market has 1, 2, or 3 active firms, it is not when $N\geq 4$. We find that
absent the threat of a new entrant, firms attempt to maximize differentiation
along all dimensions. Only when a new entrant is imminent do we find firms
attempt to ”fill in” the gap in the market space by reducing differentiation
along one dimension.

The model does not lead, generally, to socially optimal equilibria. Even as
the number of firms in the market increase, thus increasing competition, a
socially optimal outcome is not guaranteed. Obviously, for extremely large $N$
there will be so many firms in the market that the difference between the
achieved equilibrium and the socially optimal equilibrium will be trivial.
Yet, it is worth repeating that in a two dimensional market where firms choose
location and price, increased competition does not necessarily lead to
socially optimal equilibria. The fixed cost of entry, the element in the
models of Hay (1976) and Rothschild (1976) that give rise to socially optimal
outcomes on the Hotelling Line, appears to allow firms to capture rents from
early entry into the market.

## References

Economides, N., Howell, J., and S. Meza. 2002. ”Does it Pay to be First?
Sequential

Location Choice and Foreclosure.” Stern School of Business, New York
University.

EC-02-19.

Eiselt, H.A. and G. Laporte. 1996. ”Sequential Location Problems.” _European
Journal of_

_Operational Research_ 96: 217-31.

Eiselt, H.A., Laporte, G., and J.-F. Thisse. 1993. ”Competitive Location
Models: A

Framework and Bibliography.” _Transportation Science_ 27: 44-54.

Gotz, G. 2005. ”Endogenous Sequential Entry in a Spatial Model Revisited.”
_International_

_Journal of Industrial Organization_ 23: 249-61.

Hakimi, S.L. 1983. ”On Locating New Facilities in a Competitive Environment.”
_European_

_Journal of Operational Research_ 12: 29-35.

Hay, D.A. 1976. ”Sequential Entry and Entry-Deterring Strategies in Spatial
Competition.”

_Oxford Economic Papers_ 28: 240-57.

Hotelling, H. 1929. ”Stability in Competition.” _Economic Journal_ 39: 41-57.

Lane, W.J. 1980. ”Product Differentiation in a Market with Endogenous
Sequential Entry.”

_Bell Journal of Economics_ 11: 237-60.

Neven, D.J. 1987. ”Endogenous Sequential Entry in a Spatial Model.”
_International Journal_

_of Industrial Organization_ 5: 419-34.

Okabe, A. and A. Suzuki. 1987. ”Stability of Spatial Competition for a Large
Number of

Firms on a Bounded Two-Dimensional Space.” _Environment and Planning A_ 19:

1067-1082

Prescott, E.C. and M. Visscher. 1977. ”Sequential Locatio Among Firms with
Foresight.”

_Bell Journal of Economics_ 8: 378-93.

Rothschild, R. 1976. ”A Note on the Effect of Sequential Entry on Choice of
Location.”

_Journal of Industrial Economics_ 24: 313-20.

Shaked, A. 1975. ”Non-Existence of Equilibrium for the Two-Dimensional Three-
Firms

Location Problem.” _Review of Economic Studies_ 42: 51-5.

Veendorp, E.C.H. and A. Majeed. 1995. ”Differentiation in a Two-Dimensional
Market.”

_Regional Science and Urban Economics_ 25: 75-83.

## Figures

Figure 1: One Firm with Threat of Entry by Second Firm Figure 2: Two Firms
with No Threat of Entry by Third Firm Figure 3: Two Firms with Threat of Entry
by Third Firm Figure 4: Three Firms with No Threat of Entry byFourth Firm
Figure 5: Three Firms with Threat of Entry by Fourth Firm Figure 6: Four Firms
with No Threat of Entry by Fifth Firm Figure 7: Four Firms with Threat of
Entry by Fifth Firm Figure 8: Five Firms with No Threat of Entry by Sixth Firm
Figure 9: Five Firms with Threat of Entry by Sixth Firm Figure 10: Six Firms
with No Threat of Entry by Seventh Firm Figure 11: Six Firms with Threat of
Entry by Seventh Firm


# Online Bipedal Locomotion Adaptation for Stepping on Obstacles Using a Novel
Foot Sensor

Pezhman Abdolahnezhad1, Aghil Yousefi-Koma1, Amirhosein Vedadi1, Kasra Sinaei1
Behnam Maleki1 and Milad Shafiee2 1Center of Advanced Systems and Technologies
(CAST) School of Mechanical Engineering, College of Engineering, University of
Tehran, Tehran, Iran<EMAIL_ADDRESS>polytechnique fédérale de Lausanne
(EPFL)

###### Abstract

In this paper, we present a novel control architecture for the online
adaptation of bipedal locomotion on inclined obstacles. In particular, we
introduce a novel, cost-effective, and versatile foot sensor to detect the
proximity of the robot’s feet to the ground (bump sensor). By employing this
sensor, feedback controllers are implemented to reduce the impact forces
during the transition of the swing to stance phase or steeping on inclined
unseen obstacles. Compared to conventional sensors based on contact reaction
force, this sensor detects the distance to the ground or obstacles before the
foot touches the obstacle and therefore provides predictive information to
anticipate the obstacles. The controller of the proposed bump sensor interacts
with another admittance controller to adjust leg length. The walking
experiments show successful locomotion on the unseen inclined obstacle without
reducing the locomotion speed with a slope angle of $12^{\circ}$. Foot
position error causes a hard impact with the ground as a consequence of
accumulative error caused by links and connections’ deflection (which is
manufactured by university tools). The proposed framework drastically reduces
the feet’ impact with the ground.

##  I INTRODUCTION

One of the significant advantages of legged robots over other types of mobile
robots, such as wheeled robots, is that they possess the capability of
traversing uneven terrains and functioning in harsh environments [1, 2].
Stabilizing bipedal robots’ gait while operating in an unknown environment,
specifically when they walk on an uneven surface, is crucial for achieving
robust bipedal mobilization. Besides the unknown profile of the ground,
uncertainty, clearance, and errors in actuators, links and joints are other
sources of instability that can mitigate the robot’s body fluctuations even
when walking on perfectly flat surfaces. Another major challenge regarding the
smooth walking of position-controlled robots is the disturbance exerted on the
robot body by contact force impacts from each sole at the beginning of the
support phase [3]. This problem becomes more significant when the walking pace
of the robot increases, so minimizing the effects of ground reaction forces
impact that occurs in the swing sole contact change is essential for reaching
higher walking speeds. Humanoids’ reliable, human-level walking ability
depends on maintaining a smooth and continuous contact change between the
robot’s soles and the ground with minimal contact impact [4]. The most
utilized and venerated criteria for checking the stability of a bipedal robot
is Zero Moment Point (ZMP); this is a necessary condition. Dynamic stability
of walking is not within the scope of this work; however, it is worth
mentioning that the ZMP stability criterion is a necessary but not sufficient
condition for contact wrench stability [5]. As a result of that, when dealing
with position-controlled humanoid robots, the individual contact force
distributed at each sole should be studied to address the sole impact
disturbance problems [6]. Admittance controllers are used to control the
forces, reduced model[7, 8, 9] or torques of the position-controlled humanoid
robots in a effector (wrist or ankle) [10, 11].

Figure 1: Snapshots of Surena V walking on inclined obstacles

Such controllers have been exclusively investigated in recent years. Kajita et
al. designed a framework and analyzed its performance on the HRP4-C robot that
could stabilize the robot that makes slight modifications to the preplanned
walking patterns [12]. Joe et al. demonstrated a posture controller that
adjusts the position and orientation of ankles based on the sensory data that
could be obtained from F/T sensors; the proposed framework allowed the robot
to perfectly adapt its ankle to the unknown ground it is traversing [13]. The
ZMP distributor and force distributor logic used in Joe’s work follows similar
logic to Kajita’s strategy of finding the desired wrench of the planned
walking pattern [13]. Caron et al. utilized another whole-body admittance
controller to stabilize the stair climbing of the HRP4 robot by exploiting the
foot wrench measured data and estimated DCM (divergent component of motion)
and ZMP positions [14].

The aforementioned control strategy does not require the robot to replan its
footsteps. As a result, generating a new set of trajectories for the CoM
(Center of Mass) and the ankles is not necessitated. Since rescheduling gait
patterns is computationally demanding and difficult to implement in real-time
cases, this could be highly beneficial for algorithms that rely on admittance
controllers.

Sygulla et al. introduced a hierarchical control strategy to overcome the
blind walking of bipeds on uneven surfaces. The control strategy has been
tested on Lola humanoid robot. The early contact detection allows their robot
to reduce contact forces on impact whenever the swing leg faces an
unprecedented obstacle. The proposed control scheme by Sygulla relies on the
F/T sensor data and force pad switches mounted to the soles of the robot.
Force pad switches could provide essential data for detecting early contact
[15]. Despite the acceptable performance of Sygulla’s control scheme, relying
on their sensors, the robot can only sense early contacts after the sole comes
into contact with the ground and touches the surface. These force pad switches
can’t determine the distance to the ground at different walking speeds.
Employing proximity push sensors which we will introduce in this paper, could
better predict and absorb impacts from contact force by knowing the distance
to the ground. These types of sensors have already been introduced to walk on
uneven surfaces [16, 17, 18]. Specifically Kang et al. have designed a foot
mechanism for the WABIAN-2R robot consisting of four spikes, each of which has
an optical sensor to detect ground height. They developed a simple P
controller with the feedback of these sensors.

This paper presents a control scheme to assist the lower limb of the bipedal
robot Surena V in minimizing the impact caused by contact forces in swing-
support change. This set of controllers is essential for walking at higher
speeds. The proposed framework also addresses walking stabilization over
uneven surfaces. Several admittance controllers were employed simultaneously
to minimize the fluctuations and disturbances caused by rugged terrains. These
controllers utilize the feedback from F/T sensors mounted to the bottom of
ankle links and four spring-loaded push sensors mounted to the four corners of
each sole. The push sensors enable the robot to better estimate the obstacles
and the surface on which it is walking. Adjustments made by the abovementioned
admittance controllers to the planned trajectories of ankle position and
orientation are essential for increasing the robots walking pace and gait
robustness.

The framework comprises an admittance controller, which is in charge of
manipulating the height of the ankles; this is done by adding its generated
control output to the preplanned trajectories for the ankles. The feedback of
this controller comes from the force component of a couple of three-axis F/T
sensors mounted at the bottom of each sole. Another controller is employed to
boost the ankle height admittance controller’s performance by detecting the
swing ankle’s early contact and adding a controlled output to its preplanned
position based on the data received from push (bump) sensors. The data from
sole bump sensors could also be utilized for altering the orientation of the
sole to adapt the support leg to its adjacent ground.

The lower limb of the Surena V humanoid robot was used for experimental tests
of the framework. Surena humanoid robot has 12 Degrees of Freedom (DoF) in its
lower limb (6 DoFs in each leg). Based on the experiments, it has been
concluded that each controller, ankle height admittance controller, and push
sensor controller, increased the stability of the gait; however, the optimal
performance was achieved when the combined output of all three controllers was
used to modify the preplanned ankle trajectories.

This paper is structured as follows; in the next section, theories related to
walking pattern generation, admittance controllers, and detailed control
schemes are elaborated. Then in the third section, our experimental setup and
results from executing the mentioned control scheme will be presented, and its
performance will be discussed. Finally, in the fourth section, the discussions
are concluded.

##  II Architechture

Figure 2: Control Architecture of Online Adaptation Figure 3: Bump sensors
used in the robot

As illustrated in Figure 2, the control architecture of our robot comprises
two main parts: The trajectory planner and the control framework. The
trajectory planner generates the trajectory of the desired center of mass
(CoM), zero moment point (ZMP), and ankle positions in real time based on the
algorithm presented in [19]. Trajectory parameters have been extracted using
non-dominated sorting genetic algorithm II (NSGA-II) optimization to plan a
trajectory that minimizes energy consumption and enhances stability according
to [20]. The control scheme includes the introduction of a new sensor so-
called bump sensor, and three controllers: Foot Length, Ankle Orientation, and
Admittance ZMP-COM controller, which will be elaborated on in the incoming
sections.

###  II-A Bump Sensor

Four rotary contact sensors are used on the four corners of each foot, as
described in Figure 3. Each of these sensors is bounded with a torsional
spring which it’s torsional constant is about $880\frac{kN.m}{rad}$. Also,
fixed pins are used to prevent bump sensors from moving laterally. It
compresses to 2 cm when the robot’s foot is about to make contact with the
ground and returns to its initial position when the foot is in the swing
phase. One of the purposes of using this new sensor is ankle adaptation.
Another goal is to calculate the actual height of the robot’s feet from the
ground in order to avoid hitting the ground. Compared to the F/T sensor, the
design complexity of the bump sensor is significantly lower. As a result, bump
sensors could be fabricated and utilized conveniently at a much lower cost.

Figure 4: Schematic diagram of foot sensors and their configuration in the
ankle link

###  II-B Foot Length Controller

The foot length controller consists of two layers: the first one is to control
the change of the robot’s leg length by converting contact force into the
ankle’s vertical displacement during walking. For this admittance controller,
the desired forces ($F_{z,d}^{L}$,$F_{z,d}^{R}$) are obtained by distributing
the force by using the desired ZMP, according to the method mentioned in [12]:

$e=(F_{z,d}^{L}-F_{z,d}^{R})-(F_{m}^{L}-F_{m}^{R})$ (1)

$\Delta\dot{z}=k_{p}.e-k_{r}.\Delta z$ (2)

Figure 5: Foot Length Controller

Where $k_{p}$ is a proportional feedback gain, $k_{r}$ is a gain to retrieve
neutral points, and $F_{m}^{L}$,$F_{m}^{R}$ are the real force values of the
robot’s soles, which are measured by force/torque sensors. Using (2), the
value of $\Delta z$ is adjusted to reach the target
$(F_{z,d}^{L}-F_{z,d}^{R})$. The relative height changes are applied to the
ankle height as follows [12]:

$p_{z,mod}^{L}=p_{z,d}^{L}-0.5\Delta z,\hskip
2.84544ptp_{z,mod}^{R}=p_{z,d}^{R}+0.5\Delta z$ (3)

As mentioned in the conclusion of this article [14], the effects of swing foot
touch down impact could not be eliminated solely by the first controller; to
address this cause another controller should accompany the first controller.
This is the reason for using the second layer in this part. Unlike force
sensors, bump sensors perceive incoming contacts before feet reach the ground.
By changing the length of the robot’s legs, this controller ameliorates the
intensity of the touchdown impact swing phase. The actual height of the
robot’s feet ($p_{z,m}^{L}$,$p_{z,m}^{R}$) is measured according to the
average value of the bump sensors. The desired value of the controller input
is the same as the output of the Admittance Force Controller (3), that is
($p_{z,mod}^{L}$,$p_{z,mod}^{R}$):

$p_{z,m}^{L,R}\propto d_{avg}^{L,R}=\frac{d_{A}+d_{B}+d_{C}+d_{D}}{4}$ (4)

$e^{L,R}=p_{z,m}^{L,R}-p_{z,mod}^{L,R}$ (5)

$\Delta\dot{u}^{L,R}=k_{p}e^{L,R}-k_{r}\Delta u^{L,R}$ (6)

This controller (6) works for the left and right foot in a certain range of
single support phase and when the distance between the foot and the ground is
less than 2 cm. The relative height changes $\Delta u$ are applied to the
ankle height as follows:

$p_{z*}^{L}=p_{z,mod}^{L}+\Delta u^{L},\hskip
2.84544ptp_{z*}^{R}=p_{z,mod}^{L}+\Delta u^{R}$ (7)

Figure 5 shows the operation of foot length controller.

Figure 6: Ankle Orientation Controller

###  II-C Ankle Orientation Controller

According to Figure 4, the measured pitch and roll angles between the robot’s
sole and ground ($\alpha_{pitch,m}$,$\alpha_{roll,m}$), are proportional to
the values of four bump sensors as follows:

$\alpha_{pitch,m}\propto d_{B}+d_{C}-d_{A}-d_{D}$ (8)

$\alpha_{pitch,m}\propto d_{A}+d_{D}-d_{C}-d_{D}$ (9)

The ankle orientation controller adapts the sole of the robot’s foot to the
ground surface.

$e_{pitch,roll}^{L,R}=\alpha_{pitch,roll,m}^{L,R}-\alpha_{pitch,roll,d}^{L,R}$
(10)

$\Delta\dot{\theta}_{pitch,roll}^{L,R}=k_{p}\alpha_{pitch,roll,m}^{L,R}-k_{r}\Delta\theta_{pitch,roll}^{L,R}$
(11)

$\alpha_{d}$is the angle we want the sole of the foot to have with the ground.
When the robot walks, the sole of the foot should be parallel to the ground,
so its value is set to zero. The output of the controller,
$\Delta\theta_{pitch,roll}^{L,R}$ is finally added with the desired pitch and
roll values, $\theta_{pitch,d}^{L,R}$, $\theta_{roll,d}^{L,R}$ of the ankle.

$\theta_{pitch,mod}^{L,R}=\theta_{pitch,d}^{L,R}+\Delta\theta_{pitch}^{L,R}\hskip
2.84544pt,\theta_{roll,mod}^{L,R}=\theta_{roll,d}^{L,R}+\Delta\theta_{roll}^{L,R}$
(12)

Figure 6 shows the operation of ankle orientation controller.

###  II-D Admittance ZMP-CoM Controller

In third layer of the control framework, the desired CoM trajectory modifies
according to the ZMP deviations from its reference trajectory. The stability
of this controller has been proven in [21].

$e_{zmp}=r_{d}^{zmp}-r_{m}^{zmp},\hskip
2.84544pte_{com}=x_{d}^{com}-x_{m}^{com}$ (13)

$u=-k_{p}.e_{zmp}+k_{c}.e_{com}$ (14)

Where the $r_{d}^{zmp}$ and $X_{d}^{com}$ are the desired positions from
trajectory planner, $r_{d}^{zmp}$ and $X_{d}^{com}$ are the actual positions
of CoM and ZMP measured from real bipedal robot, respectively. The output of
the ZMP-CoM Controller (14) is the amount of changes in the velocity of the
center of mass, which is finally added to the com position after integration.

$X_{mod}^{com}=\int udt+X_{d}^{com}$ (15)

##  III Experiments and Results

We implemented the discussed controllers on the lower limb of the Surena V
robot and released the source code of it as an open-source project [22]. The
loop rate of the implemented controller is 200 Hz, and it runs on an Intel
Core i7 processor, which works with a frequency of 3.6 GHz and 16 gigabytes of
RAM. We used Robot Operating System (ROS) to share data between the robot and
the main processor. To show the performance of the added sensors and
controllers and their effect on walking, we investigated the robot in high-
speed walking and walking over unforeseen inclined obstacles experiments.
These test results will be discussed in the successive section. The
coefficients of the controllers in this tests were as follows:

TABLE I: Controllers Coefficients Controller | $\mathbf{k_{p}}$ | $\mathbf{k_{r}}$
---|---|---
Foot Length with Force Sensor | 0.00005 | 1
Foot Length with Bump Sensor | 0.005 | 1
Ankle Orientation | 0.0158 | 6
Figure 7: Vertical forces applied to the soles of the robot’s feet in the
presence and absence of the bump sensor controller layer Figure 8: Vertical
distance of the robot’s feet from the ground in the presence and absence of
the bump sensor controller layer

###  III-A Walking at the speed of $1\frac{km}{h}$

As the speed of the robot increases, the destructive effects of the touchdown
impact exacerbates the robot instability. The sensors presented in this
article can help attenuate the effects of these impacts. In this test, the
lower limb of the Surena V robot walked with a step length of 25 cm and a step
time of 0.9 seconds (which is equivalent to moving at 1 km/h). In one of these
tests, the controller that works with the feedback of the bump sensor was
turned off, and in the other, the controller was turned on. Figure 7 shows the
vertical forces measured on the soles of the robot in both tests. Figure 8
also shows the distance of the robot’s feet from the ground measured by the
bump sensor. The impact area in these figures is the end part of the swing
phase and when the robot’s foot hits the ground. As can be seen, when the bump
sensor controller is off, the forces applied to the robot’s feet increase.
These forces appear as a form of impact at the end of the single support
phase, which can be understood from the distance of the robot’s feet from the
ground in Figure 8. These impacts cause vibration in the upper body of the
robot and make it challenging to maintain the robot’s balance. Moreover,
increasing $k_{p}$ in (2) does not solve this problem, and if it exceeds a
limit, it causes vibration in the movement of the robot. In the second test,
where the bump sensor controller is used, these impacts have been
significantly reduced, and the robot ankles have also traveled the modified
trajectory well.

###  III-B Walking on inclined obstacles

Our robot does not use a visual sensor such as camera or LiDAR to perceive the
environment. Therefore, if there is an obstacle on its way that is not
considered in the trajectory planning, it will cause impacts during movement
and loss of robot balance. Also, if this obstacle is inclined, the robot must
adapt its foot orientation. In this experiment, the robot moves on two
inclined obstacles that are not aware of them. The height of these obstacles
is a maximum of 2.5 cm, with a slope of 7 to 12 degrees. Figure 1 shows the
walking of the robot over these obstacles. The ankle orientation controller
plays the main role in adapting the robot’s foot to the ground. Figure 9 and
Figure 10 show the output of this controller, and the angle is given to the
robot while crossing these obstacles. The control output when passing over
these obstacles is more than at other times, which causes the robot’s feet to
adapt.

The most critical weakness of this controller is that if the obstacle does not
collide with the sensors, the controller does not work well, such as moving
the robot on rocks. We plan to solve this problem in future works.

Figure 9: The angle given to the robot’s foot and the output of the controller
while crossing the rolled obstacle Figure 10: The angle given to the robot’s
foot and the output of the controller while crossing the pitched obstacle

##  IV Conclusion

In this paper, we presented a control framework and novel foot sensor for
online foot adaption during locomotion on inclined obstacles and reducing the
impact with the ground during swing to stance transition. We showed that robot
is able to step on inclined obstacles without changing the desired velocity.
Considering that these sensors detect the distance to the ground before
touching the ground, the controller drastically reduces the impact force,
resulting an smooth swing-to-stance transition. Therefore, in addition to
stepping on obstacles, it also compensates for the impact with the ground as a
result of accumulative error due to the deflection of the links and
connections. In future works, we are interested to use these sensors in
combination with an admittance controller with torque feedback so that the
robot can move on intensive rough terrains. Moreover, proposed architecture
reduces the vibration of the robot and increases the accuracy of estimating
the states of the robot. Using this architecture in conjunction with a push
recovery controller[23, 24, 25], we aim to perform locomotion on uneven
terrain in the presence of significant external disturbances.

## References

  * [1] K. Shuuji, H. Hirohisa, H. Kensuke, and Y. Kazuhito, _Introduction to Humanoid Robotics_. Springer Berlin, Heidelberg.
  * [2] D. Wahrmann, T. Knopp, R. Wittmann, A.-C. Hildebrandt, F. Sygulla, P. Seiwald, D. Rixen, and T. Buschmann, “Modifying the estimated ground height to mitigate error effects on bipedal robot walking,” in _2017 IEEE International Conference on Advanced Intelligent Mechatronics (AIM)_. IEEE, 2017, pp. 1471–1476.
  * [3] S. Kajita, T. Nagasaki, K. Kaneko, K. Yokoi, and K. Tanie, “A running controller of humanoid biped hrp-2lr,” in _Proceedings of the 2005 IEEE international Conference on Robotics and Automation_. IEEE, 2005, pp. 616–622.
  * [4] W. Xu, R. Xiong, and J. Wu, “Force/torque-based compliance control for humanoid robot to compensate the landing impact force,” in _2010 First International Conference on Networking and Distributed Computing_. IEEE, 2010, pp. 336–340.
  * [5] H. Hirukawa, S. Hattori, K. Harada, S. Kajita, K. Kaneko, F. Kanehiro, K. Fujiwara, and M. Morisawa, “A universal stability criterion of the foot contact of legged robots-adios zmp,” in _Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006._ IEEE, 2006, pp. 1976–1983.
  * [6] S. Caron, Q.-C. Pham, and Y. Nakamura, “Stability of surface contacts for humanoid robots: Closed-form formulae of the contact wrench cone for rectangular support areas,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2015, pp. 5107–5112.
  * [7] N. Ramuzat, G. Buondonno, S. Boria, and O. Stasse, “Comparison of position and torque whole-body control schemes on the humanoid robot talos,” in _2021 20th International Conference on Advanced Robotics (ICAR)_. IEEE, 2021, pp. 785–792.
  * [8] C. Zhou, Z. Li, X. Wang, N. Tsagarakis, and D. Caldwell, “Stabilization of bipedal walking based on compliance control,” _Autonomous Robots_ , vol. 40, no. 6, pp. 1041–1057, 2016.
  * [9] Z. Li, N. G. Tsagarakis, and D. G. Caldwell, “A passivity based admittance control for stabilizing the compliant humanoid coman,” in _2012 12th IEEE-RAS International Conference on Humanoid Robots (Humanoids 2012)_. IEEE, 2012, pp. 43–49.
  * [10] K. Pfeiffer, A. Escande, and A. Kheddar, “Nut fastening with a humanoid robot,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2017, pp. 6142–6148.
  * [11] A. Q. Keemink, H. van der Kooij, and A. H. Stienen, “Admittance control for physical human–robot interaction,” _The International Journal of Robotics Research_ , vol. 37, no. 11, pp. 1421–1444, 2018.
  * [12] S. Kajita, M. Morisawa, K. Miura, S. Nakaoka, K. Harada, K. Kaneko, F. Kanehiro, and K. Yokoi, “Biped walking stabilization based on linear inverted pendulum tracking,” in _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2010, pp. 4489–4496.
  * [13] H.-M. Joe and J.-H. Oh, “A robust balance-control framework for the terrain-blind bipedal walking of a humanoid robot on unknown and uneven terrain,” _Sensors_ , vol. 19, no. 19, p. 4194, 2019.
  * [14] S. Caron, A. Kheddar, and O. Tempier, “Stair climbing stabilization of the hrp-4 humanoid robot using whole-body admittance control,” in _2019 International conference on robotics and automation (ICRA)_. IEEE, 2019, pp. 277–283.
  * [15] F. Sygulla and D. Rixen, “A force-control scheme for biped robots to walk over uneven terrain including partial footholds,” _International Journal of Advanced Robotic Systems_ , vol. 17, no. 1, p. 1729881419897472, 2020.
  * [16] K. Hashimoto, T. Hosobata, Y. Sugahara, Y. Mikuriya, H. Sunazuka, M. Kawase, H.-o. Lim, and A. Takanishi, “Development of foot system of biped walking robot capable of maintaining four-point contact,” in _2005 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2005, pp. 1361–1366.
  * [17] H.-j. Kang, K. Hashimoto, H. Kondo, K. Hattori, K. Nishikawa, Y. Hama, H.-o. Lim, A. Takanishi, K. Suga, and K. Kato, “Realization of biped walking on uneven terrain by new foot mechanism capable of detecting ground surface,” in _2010 IEEE International Conference on Robotics and Automation_. IEEE, 2010, pp. 5167–5172.
  * [18] A. Yousefi-Koma, B. Maleki, H. Maleki, A. Amani, M. A. Bazrafshani, H. Keshavarz, A. Iranmanesh, A. Yazdanpanah, H. Alai, S. Salehi, _et al._ , “Surenaiv: Towards a cost-effective full-size humanoid robot for real-world scenarios,” in _2020 IEEE-RAS 20th International Conference on Humanoid Robots (Humanoids)_. IEEE, 2021, pp. 142–148.
  * [19] J. Englsberger, C. Ott, and A. Albu-Schäffer, “Three-dimensional bipedal walking control based on divergent component of motion,” _Ieee transactions on robotics_ , vol. 31, no. 2, pp. 355–368, 2015.
  * [20] A. Vedadi, K. Sinaei, P. Abdolahnezhad, S. S. Aboumasoudi, and A. Yousefi-Koma, “Bipedal locomotion optimization by exploitation of the full dynamics in dcm trajectory planning,” in _2021 9th RSI International Conference on Robotics and Mechatronics (ICRoM)_. IEEE, 2021, pp. 365–370.
  * [21] Y. Choi, D. Kim, Y. Oh, and B.-J. You, “Posture/walking control for humanoid robot based on kinematic resolution of com jacobian with embedded motion,” _IEEE Transactions on Robotics_ , vol. 23, no. 6, pp. 1285–1293, 2007.
  * [22] “Surena v walking controllers,” https://github.com/CAST-Robotics/SurenaV˙InitialWalkCodes, accessed: 2022-07-14.
  * [23] 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.
  * [24] 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.
  * [25] 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.