Two robots moving geodesically on a tree

We begin our investigation in the case of $k=3$ arms, though the methods here generalize to higher values of $k$. In this subsection, $G$ always refers to the $\operatorname{Y}$-graph, and $\operatorname{F}_{\varepsilon}$ always refers to the $2$-point ordered $\varepsilon$-configuration space of $G$, considered with the $\ell_{2}$ metric.

We define the following partition of $\operatorname{F}_{\varepsilon}\times\operatorname{F}_{\varepsilon}$.

We turn our attention to the total cut locus $\mathscr{C}$ of $\operatorname{F}_{\varepsilon}$. By Proposition 4, the total cut locus is contained in $X_{1}^{-}\cup X_{2}^{-}$. If $(a,b)\in X_{i}^{-}$, $i=1,2$, any path from $a$ to $b$ must undergo an orientation switch, in which an empty arm is used to allow the particles to reconfigure; for example, an orientation switch is necessary for the configuration depicted in the right side of Figure 4. If $G$ is a star graph with $k>3$ arms, then any $(a,b)$ which requires an orientation switch is an element of the total cut locus, because one always needs to designate which empty arm is used for the orientation switch. In the case of the $\operatorname{Y}$ graph with $k=3$ arms, not all of $X_{2}^{-}$ is contained in $\mathscr{C}$. In particular, the arm used for the orientation switch is pre-determined by the relative locations of $a$ and $b$, so $(a,b)$ is only in $\mathscr{C}$ when there is not a preferred particle which moves onto the free arm to let the other pass. We will formalize these ideas now.

As there exists a GMPR on the complement of the total cut locus, the $\ell_{2}$ case of Theorem 1(a) is a consequence of the following:

As $\mathscr{C}=(X_{1}^{-}\cup X_{2}^{-})\cap\mathscr{C}$, we first consider the spaces $X_{1}^{-}$ and $X_{2}^{-}$ separately.

All points of $X_{2}^{-}$ require orientation switches, but not all points are in the total cut locus. Assume momentarily that $a_{1}$ lies on the top arm, that none of $a_{2}$, $b_{1}$, or $b_{2}$ lies above $a_{1}$, and that points not on the top arm lie on the bottom arm. Then there are three possible permutations of the $a_{i}$ and $b_{i}$, from top to bottom: $a_{1}b_{2}b_{1}a_{2}$, $a_{1}b_{2}a_{2}b_{1}$, and $a_{1}a_{2}b_{2}b_{1}$ (it is possible that $a_{1}=b_{2}$ or $a_{2}=b_{1}$ or $a_{2}=b_{2}$). Other permutations beginning with $a_{1}$ have agreeing orientation and are not elements of $X_{2}^{-}$.

Considering cases dictated by the three possible permutations, as well as the number of $a_{i}$ and $b_{i}$ which lie on each arm, we see that there is a unique geodesic in the following cases:

• $\bullet$

  if the closed top arm (i.e. including the vertex) contains exactly three of the $a_{i}$ and $b_{i}$, or if the closed bottom arm contains exactly three of the $a_{i}$ and $b_{i}$, then a geodesic is uniquely determined. See Figure 8 (left and center) for two possible configurations – other possibilities permute the $a_{i}$ and $b_{i}$ but have similar behavior.

• $\bullet$

  if $a_{1}$ and $a_{2}$ share the open top arm and $b_{1}$ and $b_{2}$ share the open bottom arm, there exists a unique geodesic (see Figure 8, right).

Note that in the case of $k>3$ arms, all such points lie in the total cut locus, because an arm choice is necessary – see Section 2.3 for further discussion.

Similar arguments may be made in the cases which do not adhere to our specific assumptions. For example, if $b_{1}$ lies above $a_{1}$, there is a symmetry swapping the particles. If either $a_{2}$ or $b_{2}$ lie above $a_{1}$, there is a symmetry swapping the initial configuration with the final configuration, and the unique geodesic is the reversed geodesic from the above case. Finally, the same arguments can be made with respect to any of the three arms.

Thus it remains to consider the case in which $a_{1}$ and $b_{2}$ share an open arm, and $a_{2}$ and $b_{1}$ share a different open arm. As such, we define

A point of $X_{2}^{opp}$ is depicted in Figure 9, left. For $(a,b)\in X_{2}^{opp}$, every path from $a$ to $b$ must undergo an orientation switch, and paths from $a$ to $b$ may be distinguished based on which particle moves through the vertex first for the orientation switch (i.e. to enter the empty arm so that the other particle may pass). We refer to a path such that the $i$th particle passes through the vertex first as a path of type $i$.

We claim that for each particle $i$, there exists a unique length-minimizing type $i$ path. Indeed, any length-minimizing type $1$ path must pass through the point $p\in X$ depicted in Figure 9, right. Now $(a,p)$ and $(p,b)$ are in the complement of the total cut locus by Proposition 4, so there are unique geodesics connecting $a$ to $p$ and $p$ to $b$. Their concatenation is the unique length-minimizing type $1$ path from $a$ to $b$. Similarly, there is a unique length-minimizing type $2$ path from $a$ to $b$.

For at least one value of $i$, the unique length-minimizing type $i$ path is the minimal geodesic from $a$ to $b$. Occasionally these two paths have equal length, in which case the point $(a,b)$ is in the total cut locus. Such points are characterized by a certain algebraic condition relating the distances from $a_{1}$, $a_{2}$, $b_{1}$, and $b_{2}$ to the vertex, but it is not necessary to determine this condition explicitly. Instead, we simply define

and $X_{2}^{n}=X_{2}^{-}-X_{2}^{eq}$. We have shown that $X_{2}^{n}$ is disjoint from the total cut locus $\mathscr{C}$, despite the fact that orientation switches are needed for all points of $X_{2}^{-}$. However, with $k>3$ arms, every orientation switch requires a choice of empty arm to use for the switch, so $X_{2}^{n}$ is part of the total cut locus for star graphs (see Section 2.3).

Finally, we prove Proposition 5, that there exists a GMPR on the total cut locus $\mathscr{C}$.

We are now equipped to study the geodesic motion planning problem on a star graph $G$, with $k>3$ arms emanating from a single vertex. The techniques are similar to those for the case $k=3$, and many of the results from the previous section will be used.

Let $\operatorname{F}_{\varepsilon}$ be the $2$-point ordered $\varepsilon$-configuration space of $G$. In addition to the subsets of $\operatorname{F}_{\varepsilon}\times\operatorname{F}_{\varepsilon}$ defined in Defintion 3, we consider the set $X_{4}$ consisting of points $(a,b)\in\operatorname{F}_{\varepsilon}\times\operatorname{F}_{\varepsilon}$ such that there exist four arms of $G$ occupied. Given $(a,b)\in X_{4}$, we say that a path from $(a,b)$ is type $i$ if the $i$th particle passes through the vertex first. Recall that type $i$ paths were defined in Section 2.2 for elements of $X_{2}^{opp}$; however, for $(a,b)\in X_{2}^{opp}$, the particle which moves through the vertex first does so to allow the other to pass, whereas for $(a,b)\in X_{4}$, the particle which moves through the vertex first may travel directly to its destination.

For each particle $i$, there is a unique length-minimizing path among those of type $i$. At least one of these is a geodesic. As in the case of $X_{2}$, we define:

and $X_{4}^{n}=X_{4}-X_{4}^{eq}$ (see Figure 11). Thus by definition, $X_{4}^{eq}=X_{4}\cap\mathscr{C}$.

Recall the discussion prior to Lemma 7: with $k>3$ arms, $X_{2}^{n}$ belongs to the total cut locus, since any orientation switch requires a choice of empty arm, and, unlike the situation on the $\operatorname{Y}$-graph, there are now multiple such choices.

Now the sets $X_{4}^{n}$ and $X_{4}^{eq}$, together with $X_{3}\cup X_{2}^{+}\cup X_{2}^{eq}\cup X_{2}^{n}\cup X_{1}^{+}\cup X_{1}^{-}$, partition $\operatorname{F}_{\varepsilon}\times\operatorname{F}_{\varepsilon}$. The following result establishes three GMPRs on $\operatorname{F}_{\varepsilon}\times\operatorname{F}_{\varepsilon}$.

We compare to the situation of the $\operatorname{Y}$-graph. There, the sets $X_{4}^{n}$ and $X_{4}^{eq}$ do not exist, the complement of the total cut locus is $X_{3}\cup X_{2}^{+}\cup X_{1}^{+}\cup X_{2}^{n}$, and we exhibited a GMPR on $X_{1}^{-}\cup X_{2}^{eq}$. With more than three arms, one cannot define compatible GMPRs on $X_{1}^{-}$ and $X_{2}^{eq}$. So we instead show that the GMPR on $X_{2}^{eq}$ is compatible with that on the complement of the total cut locus, that $X_{4}^{eq}$ admits a GMPR compatible with that on $X_{1}^{-}$, and that $X_{2}^{n}$ admits a GMPR.

With the $\ell_{2}$ analysis complete, we now turn our attention to the $\ell_{1}$ metric on $\operatorname{F}_{\varepsilon}$.

The $\ell_{2}$-case of Theorem 1 follows from Propositions 5 and 8, and so it remains to consider the $\ell_{1}$-case. To distinguish between geodesics in various metrics, we will use the terminology “$\ell_{i}$-geodesic” to refer to a geodesic in $(\operatorname{F}_{\varepsilon},\ell_{i})$.

To adapt the $\ell_{2}$ argument to $\ell_{1}$, the general idea is as follows: we will use essentially the same partition as in the $\ell_{2}$ case, apart from small modifications to the decompositions of $X_{2}$ and $X_{4}$. In particular, the sets $X_{2}^{eq}$, $X_{2}^{n}$, $X_{4}^{eq}$, and $X_{4}^{n}$, which were previously defined in terms of the $\ell_{2}$ metric, will be redefined in terms of the $\ell_{1}$ metric. The actual GMPRs, which by definition map a point $(a,b)$ to an $\ell_{1}$-geodesic from $a$ to $b$, will always follow local $\ell_{2}$-geodesics; that is, paths which locally, but perhaps not globally, minimize $\ell_{2}$-distance.

In particular, we recall that most points $(a,b)\in\operatorname{F}_{\varepsilon}$ lie in the $\ell_{1}$ total cut locus: unless one particle stays fixed throughout a minimizing trajectory, one can perturb any $\ell_{1}$-length-minimizing path, by changing the speed of one of the particles, without changing the $\ell_{1}$-length. Even pausing one particle does not penalize the $\ell_{1}$-length; as long as a motion from $a$ to $b$ does not involve unnecessary backtracking, the motion corresponds to an $\ell_{1}$-geodesic. It follows that if an $\ell_{2}$-geodesic $\gamma$ follows a direct path from $a$ to $b$, as is the case when $(a,b)\in X_{1}^{+}\cup X_{2}^{+}$, then $\gamma$ is also an $\ell_{1}$-geodesic. More generally, we have the following.

Lemma 9 establishes that all $\ell_{2}$-geodesics are $\ell_{1}$-geodesics, except perhaps $\ell_{2}$-geodesics from $a$ to $b$ for points $(a,b)\in X_{2}^{opp}\cup X_{4}$. In the next example we give explicit points of $X_{2}^{opp}$ and of $X_{4}$ such that Lemma 9 fails. We recall that for $(a,b)\in X_{2}^{opp}\cup X_{4}$, a path from $a$ to $b$ is type $i$ if the $i$th particle passes through the vertex first. For $(a,b)\in X_{2}^{opp}$, and for each particle $i$ and empty arm $j$, there is a unique $\ell_{2}$-length minimizing path among those of type $i$ using arm $j$ for the orientation switch. For $(a,b)\in X_{4}$, no orientation switch is necessary, but for each particle $i$, there is a unique type $i$ $\ell_{2}$-length minimizing path.

We reiterate the intuitive motion planning strategy in the $\ell_{1}$-case: if $(a,b)\in X_{2}^{opp}\cup X_{4}$ has the property that all $\ell_{1}$-minimizing geodesics are of type $i$, then choose an $\ell_{1}$-geodesic $\gamma_{i,2}$ (which may not be an $\ell_{2}$-geodesic). Now we will formalize these rules, defined on the following sets:

Note that $(X_{2}^{eq})_{1}$ and $(X_{4}^{eq})_{1}$ are defined in the same manner as $X_{2}^{eq}$ and $X_{4}^{eq}$, with “$\ell_{1}$-geodesic” in place of “$\ell_{2}$-geodesic”. Also analogous to the $\ell_{2}$ case, we define $(X_{2}^{n})_{1}=X_{2}^{-}-(X_{2}^{eq})_{1}$ and $(X_{4}^{n})_{1}=X_{4}-(X_{4}^{eq})_{1}$.

We define the following GMPRs on these new sets. We note that, qualitatively, all rules exactly match those in the $\ell_{2}$ case, as presented in Sections 2.2 and 2.3; the only difference is that the actual paths are only locally $\ell_{2}$-length minimizing and may not be $\ell_{2}$-geodesics.

When studying compatibility issues in the following proof of Theorem 1, it is important to note that for $G=\operatorname{Y}$ and $(a,b)\in(X_{2}^{n})_{1}-X_{2}^{opp}$, the path chosen by the above rule is the unique $\ell_{2}$-geodesic, which is an $\ell_{1}$-geodesic by Lemma 9. Also by Lemma 9, all $\ell_{2}$ geodesics on $X_{1}\cup X_{2}^{+}\cup X_{3}$ are $\ell_{1}$-geodesics, so we define the GMPRs on these sets to use the same geodesics as used in the $\ell_{2}$ case.

We are now prepared to formalize the proof of Theorem 1 in both the $\ell_{1}$ and $\ell_{2}$ cases.