K-th shortest collision-free path planning

Abstract

A hierarchical approach is formulated for the shortest collision-free path construction problem. The new concepts of k-th neighborhood, k-th visibility graph and k-th shortest path are introduced. The proposed approach generalizes some earlier algorithms and allows for incremental improvement of the planned path.