High-speed Motion with Limited Sensing Range in a Poisson Forest

Inspired by birds flying in dense forests, we consider the problem of motion planning with limited sensing range in a planar forest environment, where the locations of the disc-shaped trees are generated by a homogeneous Poisson process. First, we show that, under some minimal technical assumptions on the dynamics of the robot, the existence of infinite collision-free trajectories exhibits a phase transition with increasing intensity of the Poisson obstacle generation process. We show that the critical threshold is non-trivial, i.e., a finite non-zero number. Second, we propose a novel planning algorithm, based on state lattices, that can navigate the robot with limited sensing range. We show that the probability that the planner fails to traverse an large environment converges to zero exponentially fast with increasing sensing range.