Guaranteed Escape for a Bouncing Robot in Pipe Chains
January 01, 1970
Abstract
We study the symmetric bouncing of a point robot within orthogonally-joined rectangles with equal width, which we refer to as pipes. We provide an exhaustive case analysis of every trajectory pattern inside a single rectangular pipe segment, identifying the conditions under which the robot exits. We then extend the analysis to L-shaped pipes and, more generally, to linear chains of \(k\) orthogonally connected pipe segments. We prove exit guarantees for the special angle \(\alpha = \pi/4\). Furthermore, these results extend to pipes with curved joints.
1 Introduction↩︎
A bouncing robot is a mobile robot that moves in straight lines and reflects off obstacles like a billiard ball. We consider such a robot within an orthogonal pipe: an environment composed of axis-aligned rectangular corridors connected orthogonally, where their openings are placed end to end (at the corners of the each rectangle in the pipe), so that there exactly two openings in the entire composite polygon; see Figure 3. The robot has no sensors to detect openings except by physically reaching them with an angle \(\alpha > 0\). When it hits a wall, it bounces symmetrically; if it hits a corner, it stops. We assume there is an opening of length equal to the pipe’s width on the boundary through which the robot can escape. The central problem is to decide how the robot should move so that it is guaranteed to find the exit.
This problem connects with billiards and dynamical systems [1]–[3]. In robotics, bouncing robots have been explored as minimalistic agents for coverage and exploration, relevant to sensor-denied environments such as pipes and ducts [4]. Kundu et al. [5] presented an algorithm guaranteeing escape from a single rectangle under co-prime side lengths. This result is extended to arbitrary side lengths by Kundu et al. in [6]. Escaping orthogonal pipe systems, however, remained open.
We start with an exhaustive case analysis of every trajectory pattern inside the End Block of a rectangular pipe segment (Table 1), which we define as the unit square at the pipes closed end, which one edge of which is the exit, and we identify the exact conditions on the initial angle \(\alpha\) and position \(y_0\) under which the robot exits. This enumeration is the technical foundation for handling junctions between pipe segments. We apply it to characterize the trajectories in L-shaped pipes (two corridors joined orthogonally) and extend to linear chains of \(k\) orthogonally connected segments, proving exit guarantees under various conditions on the angle and length of the segments.
2 Background and Related Work↩︎
Definition 1 (Symmetric Bounce). When a robot collides with a wall, it undergoes a symmetric bounce. The incident angle* is the angle between the incoming trajectory and the wall’s normal; the reflected angle is the angle between the outgoing trajectory and the wall’s normal. A symmetric bounce requires the incident angle to equal the reflected angle, following the classical specular reflection law.*
2.0.0.1 Robot model.
We model the robot as a point moving at unit speed in a two-dimensional orthogonal pipe environment with no interior obstacles. The robot has no sensors to detect openings or measure distances; its only interaction with the environment is through collisions with the boundary. The robot traverses a straight-line trajectory until it collides with a wall or corner. Upon hitting a corner, the robot terminates its motion. When colliding with a wall, the robot undergoes a symmetric bounce (Definition 1). Following reflection, the robot resumes straight-line motion along the new trajectory determined by the reflection angle until it encounters another wall or corner. This behaviour follows the classical billiard reflection law [3].
2.0.0.2 The unfolding method.
A key concept in analyzing bouncing trajectories is the unfolding method [7]: instead of reflecting the robot’s path at each wall, one reflects the rectangle across the wall, producing an infinite tiling of the plane by copies of the rectangle. In this unfolded plane, the robot’s trajectory becomes a single straight line, and openings on the boundary correspond to periodically spaced “holes” in the tiling. See Figure 6 and Figure 7 in Appendix B for reference. The robot escapes if and only if its trajectory intersects one of the holes. This is closely related to classical equidistribution results for billiard trajectories [8].
2.0.0.3 Related work.
The foundational paper [4] formalized bouncing robots as minimalistic agents that interact with the environment only through collisions, establishing bouncing as a viable primitive for coverage and navigation. More recently, [9] studied how uncontrolled or partially controlled dynamical systems can be steered by exploiting boundary interactions; these strategies can be viewed through the lens of universal plans [10]. Building on the unfolding method, Kundu et al. [5] proved that for co-prime side lengths, a carefully chosen angle ensures consecutive bounce distances never exceed \(1\), so any unit-length gap is detected; [6] subsequently removed the co-primality requirement. Beyond single rooms, [11] showed that a bouncing robot with constant memory can systematically traverse all corridors of a rectilinear polygon. Nilles et al. [12] relaxed deterministic reflection, analyzing nondeterministic bouncing with angular uncertainty. Visibility with reflection in orthogonal polygons [13], [14] and specular-reflection visibility in general polygons [15] provide complementary geometric intuition for why repeated reflections can effectively search an environment. The same specular-reflection dynamics underlie classical optics problems: O’Rourke and Petrovici [16] study how a beam, which moves symmetrically like the robot, can be progressively narrowed by a sequence of mirrors, and Eppstein [17] shows that the eventual fate of a light ray in an axis-parallel-and-diagonal “mirror maze” is decidable in polynomial time. These results are close in spirit to our setting, where the pipe walls act as mirrors and the question is whether a ray reaches a designated opening; the diagonal-mirror analysis of [17] is especially relevant to the \(\alpha=\pi/4\) model. Our analysis builds on [6] but differs in focus: rather than constructing a global escape strategy, we provide an exhaustive End Block case analysis (Table 1) that is the technical foundation for handling pipe junctions, which is not addressed in prior work. Our analysis builds on [6] but differs in focus: rather than constructing a global escape strategy, we provide an exhaustive End Block case analysis (Table 1) that is the technical foundation for handling pipe junctions, which is not addressed in prior work.
3 Problem Definition and Single-Segment Analysis↩︎
The pipe system consists of pipes interconnected orthogonally at their endpoints, forming a cohesive network referred to simply as a “pipe chain”. The two terminal pipes each feature an opening, thereby providing the entire system with exactly two openings, one at each end.
The robot enters the system via one of these openings. The process terminates if the robot exits through either opening. The robot’s objective is to traverse the system by entering through one opening and exiting through the other.
We model the robot as a point undergoing symmetric bounces (Definition 1) in a two-dimensional rectangular pipe of dimensions \(L \times 1\) (scaled so the pipe width is \(1\)), with \(L \geq 2\).
We consider a pipe with an opening on the left side and an opening on the bottom at the right end (Figure 1). Let \(l_0\) denote the horizontal distance from the left opening to the left edge of the right opening. The robot starts at height \(y_0 \in [0,1]\) with angle \(\alpha \in (0, \pi/2)\) measured clockwise from the vertical. Between consecutive bounces on opposite walls, the robot travels a horizontal distance of \(\tan\alpha\).
We define the End Block (EB) as the unit square \([l_0,\, l_0+1]\times[0,1]\) at the right end of the pipe, whose bottom edge is the exit. We write \(\operatorname{Rem}(a,b) = a - b\lfloor a/b\rfloor\). The horizontal distance from the last bounce on the bottom wall before the EB to the EB’s left boundary is \(\epsilon_B = \operatorname{Rem}(y_0 \tan\alpha + l_0,\; 2\tan\alpha)\), and the last bounce on the top wall is \(\epsilon_T = \operatorname{Rem}(\frac{(l_0 - (1-y_0)\tan\alpha)}{2\tan\alpha})\). See Figure 1. Since two adjacent sides of the EB are open, the robot can make at most two reflections within the EB before exiting or returning.
Remark 1. The case \(\alpha = \pi/4\) (\(\tan\alpha = 1\)) guarantees exit from any single rectangular pipe segment [6] and, consequently, from any pipe chain (Theorem 3). It is therefore treated as a guaranteed-exit case.
By Remark 1, the case \(\alpha = \pi/4\) is a guaranteed-exit case and excluded from the conditional classification in Table 1.
3.1 End Block Classification↩︎
The following theorem, whose proof appears in the Appendix, enumerates all possible trajectories inside the EB (see Figure 2).
Theorem 1 (Complete classification). Assume the robot has entered the End Block from either the bottom or the top. Then exactly one of the nine bouncing patterns in Table 1 occurs. Moreover, the sequence Bottom \(\to\) Side \(\to\) Top \(\to\) Exit (Case 4) is impossible.
| Case | Sequence | Exit? | Condition (\(t = \tan\alpha\)) |
|---|---|---|---|
| 1 | Bot\(\to\)Top | ✔ | \(t \le (1{+}\epsilon_B)/2\), \(\alpha < \pi/4\) |
| 2 | Bot\(\to\)Top\(\to\)Side | ✔ | \((1{+}\epsilon_B)/2 < t \le 1{+}\epsilon_B\) \(\dagger\) |
| 3 | Bot\(\to\)Top\(\to\)Side | \(\times\) | \((1{+}\epsilon_B)/2 < t \le 1{+}\epsilon_B\) \(\dagger\) |
| 4 | Bot\(\to\)Side\(\to\)Top | — | Impossible |
| 5 | Bot\(\to\)Side\(\to\)Top | \(\times\) | \(1{+}\epsilon_B < t \le 2{+}\epsilon_B\) |
| 6 | Bot\(\to\)Side | \(\times\) | \(t > 2{+}\epsilon_B\) |
| 7 | Top\(\to\)Side | \(\times\) | \(t \le (1{+}\epsilon_T)/2\) |
| 8 | Top\(\to\)Side | ✔ | \(t > (1{+}\epsilon_T)/2\) |
| 9 | Top\(\to\)(direct) | ✔ | Depends on \(x\)-position and exit |
\(\dagger\) Cases 2 & 3 share the same \(\alpha\)-range; exit depends on starting point.
The proof of Theorem 1 relies on two supporting lemmas. Lemma 1 determines whether the first bounce is on the top wall (\(\tan\alpha \le 1 + \epsilon_B\)) or the side wall (\(\tan\alpha > 1 + \epsilon_B\)). Lemma 2 then determines, when the first bounce is on the top wall, whether the path exits immediately (\(2\tan\alpha \le 1 + \epsilon_B\)) or hits the side wall (\(2\tan\alpha > 1 + \epsilon_B\)). The impossibility of Case 4 is proved by showing the required conditions are contradictory. Full proofs appear in the Appendix.
Lemma 1 (First Bounce). The first bounce is on the top wall iff \(\tan\alpha \le 1 + \epsilon_B\); on the right side wall iff \(\tan\alpha > 1 + \epsilon_B\).
Lemma 2 (Top-First Sequences). If the first bounce is on the top wall, the path exits immediately (Case 1) iff \(2\tan\alpha \le 1 + \epsilon_B\), and hits the side wall (Cases 2 & 3) iff \(2\tan\alpha > 1 + \epsilon_B\).
3.2 Periodicity and Density↩︎
Following [6], we recall two key facts about bouncing in rectangles that we will need for the chain analysis. Let the pipe be the rectangle \([0,L]\times[0,H]\), and let a ray start at \((0,y_0)\) with direction \(\alpha \in (0,\pi/2)\). Using these definitions we have Lemmas 3–4 and Remark 2.
Lemma 3 (Periodic Case [6]). The sequence of \(x\)-coordinates at which the ray contacts the bottom boundary is periodic iff \(H\cot\alpha / L \in \mathbb{Q}\). Equivalently, there exist coprime \(p,q > 0\) with \(\tan\alpha = (H/L)(q/p)\).
When the slope is rational with \(s/(2L) = a/b\) in lowest terms (where \(s = 2H\cot\alpha\)), the trajectory has period exactly \(b\); exit through an opening of positive length is decidable by checking whether any of the \(b\) bounce positions lies in the exit interval.
Remark 2 ([6]). When \(H\cot\alpha / L \notin \mathbb{Q}\), the bounce positions are aperiodic and dense in \([0,L]\). Consequently, any exit of positive length is eventually reached.
Lemma 4 (Shallow Angle Exit). If a bouncing robot travels inside a rectangular pipe segment with a relative angle \(\alpha \le \pi/4\), it is guaranteed to reach the exit.
Proof. When \(\alpha = \pi/4\), this follows from [11]. When \(\alpha < \pi/4\), we have \(2\tan\alpha < 2 \le 1 + \epsilon_B + 1\), so the robot falls into Case 1 or Case 9 of Table 1, where it always exits regardless of \(y_0\). ◻
4 Bouncing in Pipe Chains↩︎
We now analyze linear chains of orthogonally connected pipe segments, which subsume L-shaped pipes as the case \(k=2\).
Definition 2 (Linear Pipe Chain). A linear pipe chain* of length \(k\) is \(\mathcal{P} = R_1 \cup \cdots \cup R_k\) where each \(R_i\) is a rectangle of width \(1\) and length \(L_i \ge 2\). Odd-indexed segments are horizontal and even-indexed segments are vertical. Adjacent segments share a unit-length junction \(J_i\), and the chain has terminal openings at the free ends of \(R_1\) (entrance) and \(R_k\) (exit).*
The simplest case \(k=2\) is the L-shaped pipe (Figure 4): a horizontal segment \(R_1\) joined orthogonally to a vertical segment \(R_2\). When the robot crosses the junction, the wall orientations swap and the relative angle is complemented (formalised in Observation 1 below). Thus if the robot exits \(R_1\) with angle \(\alpha > \pi/4\), the relative angle in \(R_2\) becomes \(\pi/2 - \alpha < \pi/4\), and by Lemma 4 exit from \(R_2\) is guaranteed.
4.1 Angle Propagation↩︎
When the robot crosses a junction, the wall orientations swap, complementing the angle. We first record this single-junction property, then generalize.
Observation 1. When a bouncing robot moves from \(R_i\) to \(R_{i+1}\), its relative reflection angle* changes by \(\pi/2\). More precisely, if the robot travels in \(R_i\) with relative angle \(\alpha\) measured with respect to the horizontal walls of \(R_i\), then upon entering \(R_{i+1}\) the corresponding relative angle (measured with respect to the walls of \(R_{i+1}\)) equals \[\alpha' \;=\; \frac{\pi}{2}-\alpha.\]*
Lemma 5 (Angle Alternation). Let the robot enter \(R_1\) with relative angle \(\alpha \in (0, \pi/2)\). The relative angle in \(R_i\) is \(\alpha_i = \alpha\) if \(i\) is odd and \(\alpha_i = \pi/2 - \alpha\) if \(i\) is even. In particular, if \(\alpha = \pi/4\) then \(\alpha_i = \pi/4\) for all \(i\).
Proof. At each junction \(J_i\), the two wall directions are exchanged because \(R_{i+1}\) is oriented orthogonally to \(R_i\). By Observation 1, the relative angle transforms as \(\alpha_{i+1} = \frac{\pi}{2} - \alpha_i\). The closed-form expression follows by induction: if \(\alpha_1 = \alpha\), then \(\alpha_2 = \pi/2 - \alpha\), \(\alpha_3 = \pi/2 - (\pi/2 - \alpha) = \alpha\), and so on. ◻
4.2 Transition Maps↩︎
The unfolding method yields an explicit formula for the robot’s entry position into the next segment, generalising the single-segment analysis.
Definition 3 (Segment Transition Map). For segment \(R_i\) with length \(L_i\) and relative angle \(\alpha_i\), define \(T_i : [0,1] \to [0,1]\) by \(T_i(y_i) = 1 - | ((y_i + L_i \tan\alpha_i) \bmod 2) - 1 |\), provided the robot exits \(R_i\) through junction \(J_i\).
Theorem 2 (Entry Point Propagation). If the robot exits \(R_i\) through \(J_i\), the entry position into \(R_{i+1}\) is \(y_{i+1} = T_i(y_i)\).
Proof. The proof applies the unfolding method to eliminate reflections at the top and bottom walls of \(R_i\). In the unfolded domain, the robot travels along the straight line \(y(x) = y_i + x \tan\alpha_i\). At the far end \(x = L_i\), the unfolded transverse coordinate is \(y^* = y_i + L_i \tan\alpha_i\). Folding back into \([0,1]\) via reduction modulo \(2\) and reflection gives \(y_{i+1} = 1 - |(y^* \bmod 2) - 1|\), which is \(T_i(y_i)\). ◻
Definition 4 (Chain Transition Map). The chain transition map from the entrance of \(R_1\) to the entrance of \(R_{j+1}\) is the composition \[\Phi_j = T_j \circ T_{j-1} \circ \cdots \circ T_1.\] Thus \(y_{j+1} = \Phi_j(y_0)\), provided the robot successfully exits each intermediate segment.
Remark 3. Each map \(T_i\) is piecewise linear on \([0,1]\). The parameter \(\delta_i = L_i \tan\alpha_i \bmod 2\) determines the translation amount. When \(\delta_i\) is irrational, iteration of the underlying circle rotation produces an equidistributed sequence by Weyl’s theorem. When \(\delta_i\) is rational, the orbit is periodic.
Figure 7 illustrates the unfolding: a single traversal from entrance to exit corresponds to a straight line across one unfolded square of side length \(L_1 + 2d + L_2\), and each additional pass corresponds to entering an adjacent copy, so after \(n\) passes the trajectory is a line across \(n\) stacked squares.
4.3 Exit Guarantees↩︎
Theorem 3 (Exit for \(\alpha = \pi/4\)). A bouncing robot with initial angle \(\alpha = \pi/4\) exits every segment of a linear pipe chain on its first pass.
Proof. By Lemma 5, the relative angle is \(\pi/4\) in every segment. By Lemma 4, a robot with angle \(\alpha \leq \pi/4\) is guaranteed to exit any single rectangular pipe segment.
We proceed by induction on the number of segments \(k\).
Base case (\(k = 1\)): The robot exits \(R_1\) by the single-segment guarantee.
Inductive step: Assume the robot exits any chain of \(k-1\) segments. In a chain of \(k\) segments, the robot exits \(R_1\) and enters \(R_2\) at some position \(y_1 = T_1(y_0)\) with angle \(\alpha_2 = \pi/4\). The remaining chain \(R_2, \ldots, R_k\) is itself a linear chain of \(k-1\) segments, and by the inductive hypothesis the robot exits it. ◻
For \(\alpha \neq \pi/4\), not every segment is guaranteed on a single pass:
Lemma 6 (Guaranteed vs.Conditional Segments). Consider a linear pipe chain with initial angle \(\alpha \in (0, \pi/2)\), \(\alpha \neq \pi/4\). Segments where the effective relative angle is at most \(\pi/4\) are guaranteed segments: the robot always exits on its first pass, regardless of entry position (by Lemma 4). Segments where the effective relative angle exceeds \(\pi/4\) are conditional segments: whether the robot exits depends on the entry position \(y_i\) and the specific conditions of Table 1.
By Lemma 5: if \(\alpha < \pi/4\), odd-indexed segments are guaranteed and even-indexed segments are conditional; if \(\alpha > \pi/4\), even-indexed segments are guaranteed and odd-indexed segments are conditional.
Theorem 4 (Exiting Irrational Slopes). Let the robot enter segment \(R_i\) with relative angle \(\alpha_i\) such that \(\frac{\cot\alpha_i}{L_i} \notin \mathbb{Q}\). Then the sequence of bounce points on the boundary of \(R_i\) is dense, and the robot’s trajectory eventually intersects any exit of positive length.
Proof. By Remark 2, when \(\frac{\cot\alpha_i}{L_i} \notin \mathbb{Q}\), the sequence of bounce positions is dense. Since any exit of positive length is a non-degenerate interval, the trajectory must eventually intersect it. ◻
Suppose that for every segment \(R_i\) in the chain, \(\frac{\cot\alpha_i}{L_i} \notin \mathbb{Q}\). A sufficient condition is \(\tan\alpha \notin \mathbb{Q}\) with all \(L_i\) rational. Then the robot is guaranteed to exit the entire chain, regardless of initial position \(y_0\).
Proof. By Theorem 4, whenever the robot is in a segment with irrational effective slope, it will eventually exit through any opening of positive length. At each segment \(R_i\), the robot may exit forward through \(J_i\) or backward through \(J_{i-1}\); by density the robot will eventually hit both exits. Since the chain is finite and acyclic, the robot cannot remain trapped in any bounded subsection indefinitely: the trajectory must eventually propagate to \(R_k\) and exit. ◻
For a linear chain where every segment has rational effective slope \(\frac{\cot\alpha_i}{L_i} \in \mathbb{Q}\), the question of whether the robot exits the chain is decidable. In each segment, the trajectory is periodic, so the set of possible entry points into each segment is finite. Since the chain is finite and each segment contributes finitely many states, reachability of the terminal exit is decidable by exhaustive enumeration.
Definition 5 (Single-Pass Traversal). A robot traverses the chain in a single pass* if, starting from the entrance of \(R_1\), it sequentially exits \(R_1\) through \(J_1\), then \(R_2\) through \(J_2\), and so on, reaching the terminal exit at \(R_k\) without ever re-entering a previously visited segment.*
Theorem 5 (Single-Pass Sufficient Conditions). The robot traverses the chain in a single pass if, for every segment \(R_i\), the entry position \(y_i\) and relative angle \(\alpha_i\) satisfy an exit condition from Table 1. Concretely, single-pass traversal holds if:
\(\alpha_i \leq \pi/4\) for all \(i\) (i.e., \(\alpha = \pi/4\)), or
for each conditional segment \(R_i\) (where \(\alpha_i > \pi/4\)), one of Cases 1, 2, 8, or 9 of Table 1 holds, i.e., the End Block analysis yields an exit rather than a miss.
The entry position \(y_i\) is computed iteratively as \(y_i = T_{i-1}(y_{i-1})\) via Theorem 2.
Proof. By induction on \(k\). The base case \(k=1\) is a single-segment exit: if \(\alpha_1 \leq \pi/4\), this is guaranteed by Lemma 4; if \(\alpha_1 > \pi/4\), one of the exit cases from Table 1 must hold by hypothesis. For the inductive step, the robot exits \(R_1\) and enters \(R_2\) at \(y_1 = T_1(y_0)\) with angle \(\alpha_2 = \pi/2 - \alpha\). The remaining chain \(R_2, \ldots, R_k\) is a chain of \(k-1\) segments; by hypothesis the exit conditions hold for each, and by the inductive hypothesis the robot traverses them in a single pass. ◻
4.4 Backtracking Dynamics↩︎
When the robot fails to exit a conditional segment on its first pass, it returns to the previous segment through the junction it entered from. This gives rise to a richer dynamical system in which the robot may oscillate between segments before eventually exiting.
Definition 6 (Return Map). If the robot enters \(R_i\) at transverse position \(y_i\) but misses the End Block exit, it returns through \(J_{i-1}\) at some position \(y_i^{\mathrm{ret}}\). Define the return map \(\overline{T}_i : [0,1] \to [0,1]\) by \(\overline{T}_i(y_i) = y_i^{\mathrm{ret}}\).
The return map \(\overline{T}_i\) is computed by the same unfolding method used for the forward transition \(T_i\). The total horizontal distance traveled in \(R_i\) before return depends on which miss case from Table 1 applies (Cases 3, 5, 6, or 7), each producing a different effective path length before the robot exits backward.
Definition 7 (Global State). The global state* of the robot at any junction \(J_i\) is the triple \((i, y, d)\), where \(i\) is the junction index, \(y \in [0,1]\) is the transverse position, and \(d \in \{+, -\}\) indicates the direction of travel (\(+\) for forward, \(-\) for backward in the chain).*
Theorem 6 (Composite Dynamical System). The robot’s motion through the chain defines a dynamical system on the state space \(\mathcal{S} = \{1, \ldots, k-1\} \times [0,1] \times \{+,-\}\). The dynamics are:
If the robot is at \(J_i\) traveling forward (\(d=+\)), it enters \(R_{i+1}\). If it exits \(R_{i+1}\) forward through \(J_{i+1}\), the new state is \((i{+}1, T_{i+1}(y), +)\); if it misses and returns through \(J_i\), the new state is \((i, \overline{T}_{i+1}(y), -)\).
If the robot is at \(J_i\) traveling backward (\(d=-\)), it re-enters \(R_i\). If it exits \(R_i\) backward through \(J_{i-1}\), the new state is \((i{-}1, \overline{T}_i(y), -)\); if it exits forward through \(J_i\), the new state is \((i, T_i(y), +)\).
Proof. This follows from the definitions of \(T_i\) and \(\overline{T}_i\) combined with the End Block classification (Table 1), which determines whether the robot exits forward or backward from each segment. ◻
Theorem 7 (Exit for Dense Trajectories). Let \(\alpha\) be such that \(\tan\alpha \notin \mathbb{Q}\) and all segment lengths \(L_i\) are rational. Then the robot eventually exits the chain through the terminal exit at \(R_k\).
Proof. Under these conditions, the effective slope is irrational in every segment. By Theorem 4, the trajectory is dense in every segment the robot visits.
By the End Block analysis (Table 1), for any conditional segment \(R_i\), the set of entry positions \(y_i\) that yield a forward exit is a non-degenerate interval (or union of intervals) in \([0,1]\). We claim that the sequence of entry positions into any given segment over repeated passes is equidistributed. Each time the robot enters \(R_i\), it enters at a position determined by the composed transition and return maps from previous segments. Since these maps are irrational rotations (modulo folding), the sequence of entry positions is dense in \([0,1]\) by Weyl’s theorem. Therefore, there exists a pass on which \(y_i\) falls in the exit interval, and the robot exits forward.
Applying this argument inductively along the chain: the robot eventually passes through \(J_1\), then eventually through \(J_2\), and so on, until it exits through the terminal exit of \(R_k\). ◻
The results of this subsection are summarized in Table 2.
| Condition on \(\alpha\) | Guarantee | Ref. |
|---|---|---|
| \(\alpha = \pi/4\) | Always exits (single pass) | Thm [thm:pi495chain] |
| \(\alpha < \pi/4\) | Odd guaranteed; even conditional | Lem [lem:dichotomy] |
| \(\alpha > \pi/4\) | Even guaranteed; odd conditional | Lem [lem:dichotomy] |
| Irrational slope, \(L_i \in \mathbb{Q}\) | Always exits (multi-pass) | Thm [thm:irrational95chain] |
| Rational slope | Decidable in finite time | Cor [cor:rational95chain] |
4.5 Bouncing within a Circular Pipe↩︎
Theorem 8. If the pipes are connected with circular joints, a robot entering the pipe system will definitely exit.
Proof. Consider Figure 5. If a robot hits the inner wall of the pipe at an angle \(\theta\) to the normal, it subtends an angle of \(\frac{\pi}{2}-\theta\) with the tangent, and the reflected ray makes an angle of \(\frac{\pi}{2}+\theta\) with the tangent. Note that it is impossible for the robot to approach exactly perpendicular to the tangent (i.e.\(\theta = \frac{\pi}{2}\)), since the joints are connected orthogonally to the pipe, nor can it travel exactly along the tangent (i.e.\(\theta = 0\)). Hence, \[\frac{\pi}{2} > \theta > 0 \implies \frac{\pi}{2} > \frac{\pi}{2} - \theta > 0,\] and furthermore, \[\frac{\pi}{2} + \theta > \frac{\pi}{2} > \frac{\pi}{2} - \theta.\] Therefore, after every reflection off the inner wall, the reflected ray makes a strictly larger angle with the tangent than the incident ray. In particular, the robot can never return to the same side of the normal from which it bounced, so it must advance in the same direction after each inner-wall reflection.
By an analogous argument, if the robot instead bounces off the outer wall, it likewise continues to advance in the same direction. Consequently, within every circular joint, the robot strictly advances in its original direction of travel. Since no circular joint can reverse or redirect the robot, it continues to advance in the direction it entered. Thus, a robot traversing a pipe system connected by circular joints will always exit. ◻
5 Conclusion↩︎
We presented a complete classification of bouncing trajectories inside the End Block of a rectangular pipe segment (Table 1), and used it to analyze linear chains of \(k\) orthogonally connected pipe segments. We proved that the bouncing angle alternates with period 2 along the chain (Lemma 5), that a robot at angle \(\alpha = \pi/4\) always exits in a single pass (Theorem 3), that irrational slopes guarantee exiting (Theorem 4), that a robot always exits a pipe with a circular joint, and that rational slopes yield decidable exit (Corollary [cor:rational95chain]). Other works exploring this topic include [3], [5], [11]. Future directions include branching pipe systems (T-shaped pipes), cyclic networks, pipes of non-uniform width, and strategies for choosing optimal initial angles.
Appendix↩︎
A. Proofs for Single-Segment Analysis↩︎
Proof of Lemma 1. The horizontal distance required to reach height \(y=1\) from \(y=0\) is exactly \(\tan\alpha\). Starting from \(x=-\epsilon_B\), the horizontal coordinate at \(y=1\) is \(x_{top} = \tan\alpha - \epsilon_B\). The top wall is bounded by \(x \le 1\). Thus, the bounce occurs on the top wall \(\iff\) \(\tan\alpha - \epsilon_B \le 1 \iff \tan\alpha \le 1 + \epsilon_B\). Conversely, if \(\tan\alpha - \epsilon_B > 1\), the path intersects \(x=1\) at a height \(y < 1\). ◻
Proof of Lemma 2. By symmetric bounce, the horizontal distance between two bottom contacts (or virtual bottom contacts) is \(2\tan\alpha\). The projected landing point on the bottom axis is \(x_{land} = 2\tan\alpha - \epsilon_B\).
The robot exits (\(0 < x_{land} \le 1\)) without hitting the side wall if \(x_{land} \le 1\). This yields \(2\tan\alpha - \epsilon_B \le 1 \iff 2\tan\alpha \le 1 + \epsilon_B\).
If \(x_{land} > 1\), the path intersects the Right Side wall (\(x=1\)) before reaching the bottom. In this case \(2\tan\alpha > 1 + \epsilon_B\).
◻
Proof of Theorem 1 (Impossibility of Case 4). For a path to hit the Side wall first (Lemma 1), we require: \[\label{eq:side95first} \tan\alpha > 1 + \epsilon_B\tag{1}\] Upon hitting the side wall at height \(h_r < 1\), the robot reflects leftward. The horizontal distance to the top wall is \(\tan\alpha(1-h_r)\), and then to the bottom is \(\tan\alpha\). The projected landing coordinate \(x_{final}\) on the bottom axis (moving left from \(x=1\)) is given by: \[x_{final} = 1 - (2\tan\alpha - (1 + \epsilon_B)) = 2 + \epsilon_B - 2\tan\alpha\] For a valid Exit, we strictly require \(x_{final} > 0\) (inside the End Block). \[2 + \epsilon_B - 2\tan\alpha > 0 \iff \tan\alpha < 1 + \frac{\epsilon_B}{2}\] However, Equation (1 ) states \(\tan\alpha > 1 + \epsilon_B\). Since \(\epsilon_B \ge 0\), it is impossible to satisfy \(\tan\alpha > 1 + \epsilon_B\) and \(\tan\alpha < 1 + \epsilon_B/2\) simultaneously. Thus, Case 4 is impossible. ◻
Proof of Theorem 1 (Full). We determine the direction of travel from the reflection law: bouncing off a horizontal wall reverses the vertical component, while bouncing off a vertical wall reverses the horizontal component. The robot enters the End Block either from the bottom or the top.
Bottom entry. Suppose the robot enters \(\mathcal{R}\) from the bottom (i.e., \(\epsilon_B \le \tan\alpha\)).
Bottom \(\to\) Top \(\to\) Exit. The robot bounces on the top wall and then immediately bounces into the bottom exit region iff \[0 < \tan\alpha \le \frac{1 + \epsilon_B}{2}.\]
Bottom \(\to\) Top \(\to\) Side. The robot bounces on the top wall and then bounces on the right side wall iff \[\frac{1 + \epsilon_B}{2} < \tan\alpha \le 1 + \epsilon_B.\] After the side bounce, the subsequent bottom bounce lies either:
in the exit region \((0,1]\) (Exit), or
in \((-\infty,0]\) (Miss).
Bottom \(\to\) Side first. If the first bounce is on the side wall, i.e., \[\tan\alpha > 1 + \epsilon_B,\] then:
Bottom \(\to\) Side \(\to\) Top \(\to\) Exit is impossible;
Bottom \(\to\) Side \(\to\) Top \(\to\) Miss occurs iff \[1 + \epsilon_B < \tan\alpha \le 2 + \epsilon_B;\]
Bottom \(\to\) Side \(\to\) Side \(\to\) Miss occurs iff \[\tan\alpha > 2 + \epsilon_B.\]
Top entry. Suppose the robot enters EB from the top. Let \(\epsilon_T\) be the signed horizontal coordinate of the next virtual bottom bounce after the initial top bounce, which is exactly \(\operatorname{Rem}\frac{(l_0 - (1-y_0)\tan\alpha)}{2\tan\alpha}\).
Top \(\to\) Side \(\to\) Exit. The robot first bounces on the side wall and afterwards bounces into the bottom exit region iff \[0 < \epsilon_T \le \frac{1 + \epsilon_T}{2}.\]
Top \(\to\) Side \(\to\) Miss. The robot bounces on the side wall and then makes a bottom bounce outside the exit region iff \[\epsilon_T > \frac{1 + \epsilon_T}{2}.\]
Top \(\to\) Exit (no side bounce). The robot travels directly into the exit. We can solve explicitly for the value of \(\alpha\) in this case, given our initial point. We begin with an initial position \(P = (P_x, 1)\). \[\alpha_{min} = \tan^{-1}\!\left(\frac{-1}{L-E - P_x}\right), \qquad \alpha_{max} = \tan^{-1}\!\left(\frac{-1}{L - P_x}\right).\]
Thus every possible bounce sequence inside EB corresponds to exactly one row of Table 1, and the sequence Bottom \(\to\) Side \(\to\) Top \(\to\) Exit is provably impossible. ◻
B. Figures↩︎
A specular bounce off a wall is geometrically identical to letting the trajectory continue straight while reflecting the pipe across that wall. Since the robot moves at \(\pi/4\), every unit of travel advances it equally along the pipe and across it, so traversing a pipe of length \(L\) also accumulates \(L\) of cross-travel, spread over \(L/d\) bounces (Fig. 6). Unfolding those bounces turns the zig-zag into a single diagonal, and the \(L/d\) reflected copies tile an \(L\times L\) square whose main diagonal is the unfolded path. For an L-shaped chain we unfold each arm in turn (Fig. 7): the horizontal arm reflects across its top/bottom walls into an \(L_1\times L_1\) square, the corner contributes a \(d\times d\) square, and the vertical arm reflects across its left/right walls into an \(L_2\times L_2\) square. The three squares meet corner-to-corner along the diagonal of an \((L_1+d+L_2)\)-square, so escape reduces to asking whether that straight diagonal reaches the unfolded exit.
References↩︎
Toronto Metropolitan University, Toronto, ON M5B 2K3, Canada,
{bahoo,ahmad.kamaludeen,somnath.kundu}@torontomu.ca↩︎