Using multi-layer distance maps for motion planning on surfaces with moving obstacles

Abstract

This paper presents a new algorithm for planning the time-optimal motion of a robot traveling with limited velocity from a given location to a given destination on a surface in the presence of moving obstacles. Additional constraints such as space variant terrain traversability and fuel economy can be accommodated. A multilayer distance map is defined and applied in computing optimal trajectories. The multilayer distance map incorporates constraints imposed by the moving obstacles, surface topography and terrain traversability. It is generated by an efficient numerical curve propagation technique.