Shortest Paths Through 3-Dimensional Cluttered Environments

Abstract

This paper investigates the problem of finding shortest paths through 3-dimensional cluttered environments. In particular, an algorithm is presented that determines the shortest path between two points in an environment with obstacles which can be implemented on robots with capabilities of detecting obstacles in the environment. As knowledge of the environment is increasing while the vehicle moves around, the algorithm provides not only the global minimizer – or shortest path – with increasing probability as time goes by, but also provides a series of local minimizers. The feasibility of the algorithm is demonstrated on a quadrotor robot flying in an environment with obstacles.