Avoidance Critical Probabilistic Roadmaps for Motion Planning in Dynamic Environments
Abstract
Motion planning among dynamic obstacles is
an essential capability towards navigation in the real-world.
Sampling-based motion planning algorithms find solutions by
approximating the robot’s configuration space through a graph
representation, predicting or computing obstacles’ trajectories,
and finding feasible paths via a pathfinding algorithm. In this
work, we seek to improve the performance of these subproblems
by identifying regions critical to dynamic environment navi-
gation and leveraging them to construct sparse probabilistic
roadmaps. Motion planning and pathfinding algorithms should
allow robots to prevent encounters with obstacles, irrespective
of their trajectories, by being conscious of spatial context
cues such as the location of chokepoints (e.g., doorways).
Thus, we propose a self-supervised methodology for learning
to identify regions frequently used for obstacle avoidance from
local environment features. As an application of this concept, we
leverage a neural network to generate hierarchical probabilistic
roadmaps termed Avoidance Critical Probabilistic Roadmaps
(ACPRM). These roadmaps contain motion structures that
enable efficient obstacle avoidance, reduce the search and
planning space, and increase a roadmap’s reusability and
coverage. ACPRMs are demonstrated to achieve up to five
orders of magnitude improvement over grid-sampling in the
multi-agent setting and up to ten orders of magnitude over a
competitive baseline in the multi-query setting.
an essential capability towards navigation in the real-world.
Sampling-based motion planning algorithms find solutions by
approximating the robot’s configuration space through a graph
representation, predicting or computing obstacles’ trajectories,
and finding feasible paths via a pathfinding algorithm. In this
work, we seek to improve the performance of these subproblems
by identifying regions critical to dynamic environment navi-
gation and leveraging them to construct sparse probabilistic
roadmaps. Motion planning and pathfinding algorithms should
allow robots to prevent encounters with obstacles, irrespective
of their trajectories, by being conscious of spatial context
cues such as the location of chokepoints (e.g., doorways).
Thus, we propose a self-supervised methodology for learning
to identify regions frequently used for obstacle avoidance from
local environment features. As an application of this concept, we
leverage a neural network to generate hierarchical probabilistic
roadmaps termed Avoidance Critical Probabilistic Roadmaps
(ACPRM). These roadmaps contain motion structures that
enable efficient obstacle avoidance, reduce the search and
planning space, and increase a roadmap’s reusability and
coverage. ACPRMs are demonstrated to achieve up to five
orders of magnitude improvement over grid-sampling in the
multi-agent setting and up to ten orders of magnitude over a
competitive baseline in the multi-query setting.
Research Areas
