Leveraging Single-Goal Predictions to Improve the Efficiency of Multi-Goal Motion Planning with Dynamics

Abstract

Multi-goal motion planning requires a robot to plan collision-free and dynamically-feasible motions to reach multiple goals, often in unstructured, obstacle-rich environments. This is challenging due to the complex dependencies between navigation and high-level reasoning, requiring the robot to explore a vast space of feasible motions and goal sequences. Our approach combines machine learning and Traveling Salesman Problem (TSP) solvers with sampling-based motion planning. Machine learning predicts distances and directions between locations, considering obstacles and robot dynamics, which the TSP solver uses to compute promising tours. Sampling-based motion planning expands a motion tree to follow the tours along the predicted directions. We demonstrate the effectiveness of our approach through experiments with vehicle and snake-like robot models operating in unstructured environments with multiple goals.