Deep learning-based framework for efficient multigoal shortest path planning in indoor environments

Abstract

Connecting multiple destinations with the shortest overall path in an obstacle-rich indoor environment is a classic problem in robotic path planning. Established solutions, such as A*, ARA*, and RRT*, execute faster when given smaller input maps that exclude extraneous paths. However, removing such paths without losing the ground truth solution is challenging because runtime-efficient approximations can yield detours. This work proposes a deep learning-based search-space reduction pipeline (SRP) that integrates a module called MazeNet to solve indoor navigation tasks with fast runtimes while maintaining accuracy. We transform the indoor environment into a graph representation, reducing the planning task into a graph-based optimization problem known as the Obstacle-Avoiding Rectilinear Steiner Minimum Tree. MazeNet takes compressed images derived from graph abstractions as inputs and uses a recurrent convolutional neural network trained to predict the shortest feasible path connecting all destinations. Within SRP, MazeNet’s output restricts the search space for classical planners. MazeNet solves more complex instances than those seen during training via recurrence with an integrated termination condition. We evaluate MazeNet’s runtime and path-length performance using a variety of planning methods against both exact and approximate graph algorithms in simulations and, after fine-tuning, in real-life floor plans. MazeNet solves all these specific test cases with improved runtimes and no increase in path length. Physics simulation further supports SRP’s feasibility across the tested floor plans, with no collisions recorded during navigation tasks.