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.

Anytime Informed Multi-Path Replanning Strategy for Complex Environments

Tonola, Cesare
Primo
Membro del Collaboration Group
;
Faroni, Marco
Secondo
Membro del Collaboration Group
;
Beschi, Manuel
Penultimo
Membro del Collaboration Group
;
Pedrocchi, Nicola
Ultimo
Membro del Collaboration Group
2023

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.
2023
Istituto di Sistemi e Tecnologie Industriali Intelligenti per il Manifatturiero Avanzato - STIIMA (ex ITIA)
Robots Collision avoidance
Trajectory
Heuristic algorithms
Computer architecture
Motion planning
Directed graphs
Path planning
File in questo prodotto:
File Dimensione Formato  
prod_476693-doc_194903.pdf

Open Access dal 11/01/2023

Descrizione: Anytime Informed Multi-Path Replanning Strategy for Complex Environments
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 1.82 MB
Formato Adobe PDF
1.82 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/445149
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 4
social impact