Finding optimal paths using networks without learning--unifying classical approaches

Abstract

Trajectory or path planning is a fundamental issue in a wide variety of applications. In this article, we show that it is possible to solve path planning on a maze for multiple start point and endpoint highly efficiently with a novel configuration of multilayer networks that use only weighted pooling operations, for which no network training is needed. These networks create solutions, which are identical to those from classical algorithms such as breadth-first search (BFS), Dijkstra's algorithm, or TD(0). Different from competing approaches, very large mazes containing almost one billion nodes with dense obstacle configuration and several thousand importance-weighted path endpoints can this way be solved quickly in a single pass on parallel hardware.