Anytime Informed Multi-Path Replanning Strategy for Complex Environments

Abstract

In many real-world applications (e.g., human-robot collaboration), the environment changes rapidly, and the intended path may become invalid due to moving obstacles. In these situations, the robot should quickly find a new path to reach the goal, possibly without stopping. Planning from scratch or repairing the current graph can be too expensive and time-consuming. This paper proposes MARS, a sampling-based Multi-pAth Replanning Strategy that enables a robot to move in dynamic environments with unpredictable obstacles. The novelty of the method is the exploitation of a set of precomputed paths to compute a new solution in a few hundred milliseconds when an obstacle obstructs the robot’s path. The algorithm enhances the search speed by using informed sampling, builds a directed graph to reuse results from previous replanning iterations, and improves the current solution in an anytime fashion to make the robot responsive to environmental changes. In addition, the paper presents a multithread architecture, applicable to several replanning algorithms, to handle the execution of the robot’s trajectory with continuous replanning and the collision checking of the traversed path. The paper compares state-of-the-art sampling-based path-replanning algorithms in complex and high-dimensional scenarios, showing that MARS is superior in terms of success rate and quality of solutions found. An open-source ROS-compatible implementation of the algorithm is also provided.

Keywords

• Anytime search
• dynamic environments
• informed planning
• motion planning
• path replanning
• sampling-based algorithms