Inspired by birds flying through cluttered environments, Karaman and Frazzoli showed that high-speed flight through an ergodic random forest exhibits an ultimate speed limit: above a critical speed, almost surely no infinite collision-free trajectory exists for a single bird. This paper formulates a corresponding bulk-transport problem for many birds. We construct an explicit directed corridor network in a Poisson disk forest and impose a common temporal headway at its waypoints. The maximum current equals a minimum vertex-cut capacity and is achieved by repeated flight along vertex-disjoint paths. The same schedule maximizes completed traversals at every finite horizon, with constant forward speed and no internal waiting. For a forest belt of fixed depth, exact transverse superadditivity yields an almost-sure deterministic current-density limit. A uniform shape theorem for an asymmetric planar dual identifies the current when depth and width grow together. For diverging depth bounded by a constant times width, this current equals the width-first, depth-second limit and is independent of the positive aspect ratio. When diagonal corridors are available, bulk current is positive at sufficiently low obstacle intensity and zero at sufficiently high intensity. For stochastic demand, an upstream admission queue is stable at every rate below the finite-network capacity.
Figures & tables
Fig. 1: An illustrative Poisson forest and its open corridor graph. Gray disks are trees; light solid segments are open corridors. Heavy paths form a maximum vertex-disjoint family, and squares mark a minimum waypoint cut. Blocked corridors are omitted. The computation gives K=2 , so repeated launches attain current 2/H . The square symbols identify a capacity obstruction.
We study finite-horizon queue peaks in generalized switches, a standard stochastic-network model in which many queues share constrained service resources. Arrivals may be dependent, nonstationary, and responsive to the system history; the only load condition is uniform interior slack, meaning the conditional mean arrival vector stays in a fixed contraction of the capacity region. We show that this slack reshapes the finite-time peak law for drift-minimizing scheduling policies such as MaxWeight. The square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold, the running maximum grows only logarithmically with the horizon, both with high probability and in expectation. The mechanism is self-normalization: in the current queue direction, the projected fluctuation scale is normalized by the stabilizing drift scale. This removes capacity geometry from the logarithmic coefficient, while geometry remains in the threshold. Matching lower bounds show that both the logarithmic term and a geometric threshold are unavoidable. When finite-time state-space collapse is available, the threshold can be sharpened using local bottleneck geometry. For generalized input-queued switches, we obtain finite-time peak bounds with tight logarithmic coefficients. Simulations illustrate the two-phase envelope, local geometric refinements, and variance-sensitive improvements predicted by the theory.
When performing parallel data transmission through a network using multiple paths, it is practically important to minimize the maximum transmission time among the selected paths. This study addresses an online problem in which k paths from an origin vertex to a destination vertex must be selected at each time step within a network represented as a directed graph. Here, the number of paths going through each edge in each parallel data transmission is limited to its capacity, and the time required for transmission is determined stochastically. We formulate the semi-bandit problem of selecting a set of paths to minimize the maximum traversal time among the selected paths and propose an algorithm to solve it.
Shunsuke Aoki, Atsuyoshi Nakamura
Graduate School of Information Science and Technology, Hokkaido University Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido, 060-0814, Japan
Target interception in crowded environments requires reaching a moving objective while navigating among multiple uncertain human agents. Since human navigation intent is not directly observable, the robot must reason over multiple possible future interaction outcomes. We formulate interception in crowds as a partially observable Markov decision process and solve it online using tree search under a fixed computational budget. In this setting, the action-space structure directly shapes the search tree and how computational effort is allocated. We perform a controlled comparison between a sequential path-speed planner, which first plans a spatial path and then modulates speed along it, and a unified planner that jointly branches over steering and speed within tree search. Across simulations with up to 200 humans, both approaches perform similarly at low crowd density but diverge sharply as density increases. At the highest crowd density, the sequential planner has a safe-interception rate 31 percentage points lower and requires 44% more time than the unified steering-speed planner, revealing a structural limitation of spatial restriction. Project webpage: https://tic-planning.github.io/
Himanshu Gupta, Kelvin Aladum, Nisar Ahmed +2
Dept. of Aerospace Engineering Sciences, University of Colorado Boulder, USA · Dept. of Computer Science, University of Colorado Boulder, USA