T-PRM: Temporal Probabilistic Roadmap for Path Planning in Dynamic Environments
Open access
Date
2022Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Sampling-based motion planners are widely used in robotics due to their simplicity, flexibility and computational efficiency. However, in their most basic form, these algorithms operate under the assumption of static scenes and lack the ability to avoid collisions with dynamic (i.e. moving) obstacles. This raises safety concerns, limiting the range of possible applications of mobile robots in the real world. Motivated by these challenges, in this work we present Temporal-PRM, a novel sampling-based path-planning algorithm that performs obstacle avoidance in dynamic environments. The proposed approach extends the original Probabilistic Roadmap (PRM) with the notion of time, generating an augmented graph-like structure that can be efficiently queried using a time-aware variant of the A* search algorithm, also introduced in this paper. Our design maintains all the properties of PRM, such as the ability to perform multiple queries and to find smooth paths, while circumventing its downside by enabling collision avoidance in highly dynamic scenes with a minor increase in the computational cost. Through a series of challenging experiments in highly cluttered and dynamic environments, we demonstrate that the proposed path planner outperforms other state-of-the-art sampling-based solvers. Moreover, we show that our algorithm can run onboard a flying robot, performing obstacle avoidance in real time. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000560560Publication status
publishedExternal links
Book title
2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)Pages / Article No.
Publisher
IEEEEvent
Subject
Uncertainty; Heuristic algorithms; Probabilistic logic; Real-time systems; Computational efficiency; Trajectory; SafetyOrganisational unit
09559 - Chli, Margarita (ehemalig) / Chli, Margarita (former)
Funding
183720 - Collaborative Vision-based Perception, Towards Intellingent Robotic Teams (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics