A Partial Analysis of the High Speed Autonomous Navigation Problem

This report examines the general problem of high speed autonomous navigation from range image data as it applies to both stereo and lidar sensing systems.

In order to intelligently guarantee its own safety, a high speed vehicle must be able to resolve the smallest obstacle that can present a hazard, process sensory data at a rate commensurate with its speed, respond fast enough to avoid obstacles, and maintain a sufficiently accurate model of the world to enable it to make correct decisions.

These dimensions of the problem are analysed in a nondimensional manner and the implications of satisfying all requirements simultaneously are investigated. In this analysis, it is shown that to adopt a policy of guaranteed vehicle safety is to adopt a computational complexity of O ([TV]^N)for range image processing where T is the vehicle reaction time and V is the velocity.

This result implies that increased vehicle speed will require nonlinear growth in computational bandwidth. Further, it identifies the fundamental tradeoff of finite computing resources as one of speed for either resolution or reliability.

The conclusions of this report are the theoretical justification for the adaptive, real-time controller design of the RANGER cross country navigator.