Introduction
DRM-connect is an algorithm for motion planning and replanning, and is a combination of dynamic reachability maps (DRM) with lazy collision checking and a fallback strategy based on the RRT-connect algorithm, which is used to repair the roadmap through further exploration.
Trajectory planning and replanning in complex environments often reuses very little information from previous solutions. This is particularly evident when the motion is repeated multiple times with only a limited amount of variation between each run. Graph-based planning offers fast replanning at the cost of significant pre-computation, while probabilistic planning requires no pre-computation at the cost of slow replanning.
We attempt to offer the best of both by proposing the DRM-connect algorithm.
Algorithm
Offline, an approximate Reeb graph is constructed from the trajectories of prior tasks in the same or similar environments.
For a new planning or replanning query, DRM-connect searches this Reeb graph for a trajectory to complete the task (checking collisions lazily). If no path is found, DRM-connect iterates between attempting to repair the disconnected subgraphs through a process similar to RRT-connect (operating on multiple graphs, rather than trees) and searching for paths through the graph. Since DRM-connect is probabilistically complete, the likelihood of a successful trajectory being returned approaches one as time tends to infinity.
Further work will incorporate online updates of the Reeb graph, as well as testing DRM-connect for humanoid whole body motion planning (~30 dimensional state space).
Watch the video below and read the paper for more details!
Login to post a comment