Robotic Arm Rotation: Standing up Is Harder Than You Think

The solution to a RAMP problem, or rotation ordering, is a pair $({ℛ}_{\text{sol}},{𝒟}_{\text{sol}})$, where ${ℛ}_{\text{sol}}=(r_1^{\prime },\mathrm{\dots },r_n^{\prime })$ lists the arms in $ℛ=\{r_1,\mathrm{\dots },r_n\}$ in the order in which they rotate and ${𝒟}_{\text{sol}}=(d_1,\mathrm{\dots },d_n)$, $d_i\in \{𝖢,𝖠\}$, records clockwise/anticlockwise rotation. Properties of a rotation ordering are characterized by two types of constraints (Figure 1) between arms $r_i$ and $r_j$:

• $\mathrm{■}$

  A clockwise/anticlockwise precedence constraint on $r_i$ (involving $r_j$) means $r_j$ must rotate before $r_i$ can rotate in that direction (Figures 1(a) and 1(b)).

• $\mathrm{■}$

  A clockwise/anticlockwise succession constraint on $r_i$ (involving $r_j$) means that if $r_j$ has already rotated, then rotating $r_i$ in that direction would cause a collision, so $r_i$ must rotate before $r_j$ (Figures 1(c) and 1(d)).

We encode constraints in four directed graphs $P_{𝖢},P_{𝖠},S_{𝖢},S_{𝖠}$ on vertex set $ℛ$: $P$ (resp. $S$) encodes precedence (resp. succession), and the subscript indicates rotation direction. In $P_{𝖷}$, an arc $(r_i,r_j)$ means $r_j$ must rotate before $r_i$ if $r_i$ rotates in direction $𝖷$; in $S_{𝖷}$, an arc $(r_i,r_j)$ means $r_i$ must rotate before $r_j$ if $r_j$ rotates in direction $𝖷$. If any such constraint exists, arms $r_i$ and $r_j$ interact.

Given a direction assignment $\delta :{ℛ}^{\prime }\to \{𝖢,𝖠\}$ with ${ℛ}^{\prime }\subseteq ℛ$, we call $\delta$ compatible if there is a rotation ordering in which each $r\in {ℛ}^{\prime }$ rotates according to $\delta (r)$. The associated rotation dependency graph $G_{\delta }$ has vertex set ${ℛ}^{\prime }$ and an arc $(r_i,r_j)$ whenever $r_j\in P_{\delta (r_i)}$ or $r_i\in S_{\delta (r_j)}$. Then $\delta$ is compatible if and only if $G_{\delta }$ is acyclic. If ${ℛ}^{\prime }=ℛ$, any reverse topological ordering of $G_{\delta }$ yields a rotation ordering.

In a horizontal-to-vertical (H–V) instance, all arms start horizontal and must become vertical. We capture the geometry of constraints via flowers (Figure 3): we place eight quarter-circular regions (petals) around an arm’s square, each petal being of type $P_{𝖢},P_{𝖠},S_{𝖢},$ or $S_{𝖠}$. We observe that, for any type in $\{P_{𝖢},P_{𝖠},S_{𝖢},S_{𝖠}\}$, if the midpoint of $r_j$ lies in a petal of that type of $r_i$, then the midpoint of $r_i$ lies in a petal of the same type of $r_j$. Thus every interacting pair appears in exactly one of the four graphs and every constraint is bidirectional. This structural property distinguishes H–V instances from the general case and underlies both hardness and positive results (Section 5).

We now introduce chains, the key structured gadgets used in our hardness proof. A horizontal chain is a sequence $r_1,\mathrm{\dots },r_h$ of horizontal arms whose pairwise interactions use only $P$-constraints, with symmetric constraints only between consecutive arms and no constraints between non-consecutive arms. Analogously, a vertical chain uses only $S$-constraints. Neighboring arms in a chain always rotate in opposite directions (Figure 3).

In a horizontal chain, only the two ends can rotate first; rotations then propagate from the ends toward an arm at the center of the chain, which rotates last. In a vertical chain, any arm may rotate first, but once the first arm and its direction are fixed, the directions and order of all other arms are forced; the pattern is essentially the reverse of that of a horizontal chain. Choosing a rotation direction for some arm $r_i$ in a chain induces a propagation: a forced ordering and directions on a set of constrained arms, including root $r_i$.

A horizontal chain and a vertical chain that share an arm intersect; propagation along one chain may spread to the other through the shared arm. When propagation spreads, we distinguish a main chain (where propagation starts) and a branching chain (where propagation spreads to). All possible local propagation patterns between two intersecting chains fall into eight cases, depending on the geometry and on the chosen root and direction (Figure 4).

Because propagation along a chain has a well-defined direction and order, we represent it by a propagation arrow (Figures 4 and 5): arms at the head rotate first and at the tail rotate last. In our constructions chains are horizontal or vertical, so arrows are rectilinear. Propagation can also travel through a sequence of intersecting chains, possibly stopping at intersections depending on the chosen root and direction; this behavior is captured combinatorially in Section 2.3 and realized geometrically in the reduction to SM-RAMP.

We abstract propagation behavior in the Lighthouse Propagation (LPR) problem. We work on an $(m+1)\times (m+1)$ integer grid, where $m\in {\mathbb{N}}^{+}$. Each lighthouse $L_i$ sits at a grid point $l_i$ and has two bundles $X_i,Y_i$ of directed grid edges. Each bundle is a tree-like rectilinear structure of horizontal and vertical unit-length edges of maximum degree 3, with exactly one horizontal edge incident to the lighthouse; orientations are chosen so that each bundle behaves like a propagation pattern along rectilinear chains. Maximal collinear sequences of edges are grouped into (light) rays, each drawn as an arrow (Figure 6). Bundles must also interact in a restricted way: light rays of different bundles never overlap and only intersect orthogonally at endpoints, mirroring how propagation spreads between chains (Figure 7).

Each lighthouse chooses exactly one of its two bundles to illuminate; all edges in the chosen bundle become light-directed. A directed light cycle is a directed cycle whose edges are all light-directed. A set of illuminated rays induces such a cycle if it contains all its edges. The decision problem Lighthouse Propagation asks, given lighthouses $L_1,\mathrm{\dots },L_n$, where each lighthouse $L_i$ has bundles $X_i,Y_i$, whether there exists a choice function $c$ with $c(L_i)\in \{X_i,Y_i\}$ such that the illuminated rays do not induce a directed light cycle. The reflection count is the maximum number of intersections (reflections) along any light ray.

We show that LPR is $\mathrm{𝖭𝖯}$-complete even when the reflection count is at most 3. The reduction is from Planar 3-Bounded 3-SAT; each lighthouse encodes a variable (choosing $X_i$ vs. $Y_i$ corresponds to setting the variable to true vs. false), and carefully designed clause gadgets force a directed light cycle whenever a clause is not satisfied.

We sketch the reduction proving Theorem 2. We begin with the incidence graph $G(\phi )$ of a planar formula $\phi$, for which a polynomial-size rectilinear embedding is known to exist.

We compute a planar rectilinear embedding $ℰ$ of $G(\phi )$. Each variable–clause incidence is drawn as a rectilinear path whose interior grid points are connectors (straight or elbow). A clause is top/bottom/left/right-positioned with respect to a variable if the path initially goes up/down/left/right; we use $𝖳,𝖡,𝖫,𝖱$ as abbreviations for these four positions.

We scale $ℰ$ by a factor of 8 to obtain ${ℰ}^{\prime }$ and replace each vertex by a square block of size $8\times 8$: a variable block, a clause block, or a connector block. Adjacent vertices in $ℰ$ become blocks that share a side. Each block has four outlets (midpoints of its sides), namely its T-outlet, B-outlet, L-outlet, and R-outlet, through which light rays may enter or exit.

We color-code the light rays to make their bundle assignments explicit. For a lighthouse $L_i$, a light ray is colored red (resp. blue) if it belongs to $X_i$ (resp. $Y_i$).

We briefly justify correctness; full details can be found in the full version of the paper.

Although each block individually satisfies the bundle requirements of a valid LPR instance (Figures 6 and 7), we must first verify that these properties are preserved when the blocks are embedded in the plane.

Next, to prove correctness, we examine the implications of choosing which bundle to illuminate for the light rays within clause blocks (Observation 8); should the illuminated light rays induce a directed light cycle, the blocks are specifically designed to force the directed light cycle to be contained within a clause block (Lemma 9).

We start from an LPR instance of Section 3.1. After a slight local modification to the block structure, we replace each unit segment of each light ray by a small cell, containing a constant-size arrangement of robotic arms, thereby forming an H–V SM-RAMP instance. We define the following cells (Figures 12, 13, 14 and 15):

• $\mathrm{■}$

  Lighthouse cells, which encode the choice between two bundles of a lighthouse by two interacting horizontal chains whose special ends, $r_i^t$ and $r_i^f$, represent truth values.

• $\mathrm{■}$

  Rectilinear cells, replacing straight unit segments of rays by horizontal or vertical chains.

• $\mathrm{■}$

  L cells, replacing a bend between two rays by interacting horizontal and vertical chains.

• $\mathrm{■}$

  T cells, generalizing L cells to replace a degree-3 junction of rays.

To ensure that at each lighthouse exactly one of the two bundles behaves as “chosen”, we augment the variable gadgets with a dummy clause enforcing that one of $r_i^t,r_i^f$ must rotate clockwise and the other anticlockwise. We enlarge each light-ray block to an augmented block of size $40\times 40$, nest the original $8\times 8$ gadget in the center, and attach a dummy 2-clause block representing $(x\vee \overline{x})$ inside the same augmented variable block (Figure 13). The augmented construction still yields an $\mathrm{𝖭𝖯}$-hardness LPR reduction, now from Planar 4-Bounded 3-SAT (original instance plus tautological clauses $(x_i\vee \overline{x_i})$).

Finally, each unit-length square of the light-ray embedding is replaced by one of the four robotic arm cells (lighthouse, rectilinear, L, T), according to the local ray pattern (Figures 14 and 15). The midpoints of robotic arms are aligned on the grid so that chains connect across block boundaries, producing an H–V SM-RAMP instance with polynomially many arms.

Two observations about local structure can be made about the constructed SM-RAMP instances: each robotic arm interacts with only a few others, and the arm cells are designed so that propagation of forced directions along chains mirrors the direction of light rays (Observation 10).

The second part of Observation 10 ensures that exactly one truth-value arm rotates clockwise in each lighthouse cell, which is crucial for the correctness of the reduction:

We now study the parameterized complexity of MAX-SM-RAMP in the two-orientation setting (horizontal or vertical). In MAX-SM-RAMP, the goal is not necessarily to rotate all horizontal arms to the vertical orientation, but rather to decide whether at least $k$ arms can be made vertical by a collision-free sequence of clockwise or anticlockwise rotations.

An arm may be $𝖢$-free, $𝖠$-free, both, or neither; directional freedom is determined purely by whether the relevant sweep sector is unobstructed. To reason about interactions among directionally free arms, we use directional interaction graphs.

A key geometric fact proved earlier is that the flower of any arm contains at most one non-frozen neighbor in each petal. Because frozen arms are never directionally free, this gives an immediate degree bound on the directional interaction graphs.

Let $V_{\mathrm{𝖽𝗂𝗋}}(ℛ)$ denote the set of $\mathrm{𝖽𝗂𝗋}$-free arms. The bounded degree of $G_{\mathrm{𝖽𝗂𝗋}}(ℛ)$ implies:

Such an independent set sweeps disjoint sectors, so its arms can be safely rotated (in any order) in direction $\mathrm{𝖽𝗂𝗋}$.

We can adapt this FPT algorithm into a polynomial kernel using geometric arguments.

We now study 2A-MM-RAMP under a bound $\mathrm{\ell }$ on the total number of allowed rotations, when each arm is restricted to the horizontal or vertical orientation. Unlike in SM-RAMP, where each arm may be rotated at most once and be made vertical, the 2A-MM-RAMP model allows each arm to visit any of its allowed angles, possibly moving away from its target and later returning to it. Thus, short valid sequences may temporarily rotate arms that already match their target angles.

Recall that an arm is frozen if no collision-free sequence of rotations ever allows it to change its angle. If there exists an arm $r_i$ such that ${\alpha }_i\ne {\beta }_i$ and $r_i$ is frozen, then the instance is immediately a no-instance. We henceforth restrict attention to instances in which this does not happen. We now define a static interaction graph on non-frozen arms that captures all potential geometric conflicts.

Let $R$ be the set of all arms and let $R_{\mathrm{nf}}\subseteq R$ denote the set of non-frozen arms in the instance. For each unordered pair of distinct arms $\{r,r^{\prime }\}\subseteq R_{\mathrm{nf}}$, the flower construction and two-orientation model determine whether $r$ and $r^{\prime }$ are in conflict in one of the four constraint graphs $P_{𝖢},S_{𝖢},P_{𝖠},S_{𝖠}$ (that is, whether the midpoint of $r^{\prime }$ lies in a petal of $r$, or vice versa, that induces a constraint when rotating in some direction). We define the union interaction graph as the undirected graph $H=(V(H),E(H))\text{with}V(H)=R_{\mathrm{nf}}$ and where an edge $\{r,r^{\prime }\}$ belongs to $E(H)$ if and only if $r$ and $r^{\prime }$ are adjacent in at least one of $P_{𝖢},S_{𝖢},P_{𝖠},S_{𝖠}$ (restricted to $R_{\mathrm{nf}}$). In other words, $E(H)=E\left(P_{𝖢}[R_{\mathrm{nf}}]\right)\cup E\left(S_{𝖢}[R_{\mathrm{nf}}]\right)\cup E\left(P_{𝖠}[R_{\mathrm{nf}}]\right)\cup E\left(S_{𝖠}[R_{\mathrm{nf}}]\right).$ Thus $\{r,r^{\prime }\}\in E(H)$ precisely when some clockwise or anticlockwise rotation of $r$ or $r^{\prime }$ (between the two allowed angles) can cause a collision between them. The graph $H$ is entirely determined by the positions of the arm midpoints and the two-angle model; it does not depend on the particular configuration (source, intermediate, or target).

By Observation 15, every non-frozen arm $r$ participates in at most eight constraints in total, one per petal of its flower, and each such constraint appears in exactly one of $P_{𝖢},S_{𝖢},P_{𝖠},S_{𝖠}$. Restricting to $R_{\mathrm{nf}}$ can only remove neighbours, and therefore:

Let $D=\{i\in R_{\mathrm{nf}}:{\alpha }_i\ne {\beta }_i\}$ be the set of (necessarily non-frozen) arms whose initial and target orientations differ. Every arm in $D$ must be rotated at least once in any valid solution. Hence, if $|D|>\mathrm{\ell }$, the instance is immediately a no-instance. We therefore assume from now on that $|D|\le \mathrm{\ell }$. For a set $X\subseteq V(H)$ and an integer $r\ge 0$, define the ball $B_r(X)=\{v\in V(H):{\mathrm{dist}}_H(v,X)\le r\},$ where ${\mathrm{dist}}_H(v,X)$ denotes the shortest graph distance between $v$ and a vertex in $X$.

Combining Lemmas 23 and 24, we see that the set $R^{\prime }=B_{\mathrm{\ell }}(D)$ contains every arm that is ever rotated in any valid solution of length at most $\mathrm{\ell }$. Thus all arms outside $R^{\prime }$ remain fixed obstacles; the search for an $\mathrm{\ell }$-bounded solution can be restricted to $R^{\prime }$.