Tools for User Modification of Optimal Roadmaps
Abstract
Robotic motion planning is a ubiquitous field of study, with innumerable applications in sci-
ence, engineering, and beyond. At its core, however, motion planning is infeasible for many
complex problems. Sampling-based algorithms address this issue by building an approximate
model of the planning space, while optimal planners extend this to provide desirable guaran-
tees on solution features (e.g., shortest paths). Unfortunately, these guarantees can require
the creation of dense, cumbersome planning graphs. Automatic refinement algorithms can
help to sparsify these dense graphs, though they may be costly themselves if they affect the
quality of the original solution. In another direction, harnessing human intuition with user-
guided planning strategies has also shown promise. In this research, we seek to combine the
unique strengths of human and machine reasoning with a foundational, interactive toolset
for graph modification and, thus, to overcome some weaknesses inherent in either alone. We
provide a visual interface that allows the user to modify a pre-computed planning graph
by adding, removing, and adjusting vertices and edges as desired, with reciprocal feedback
from the planner on the feasibility of each operation. This provides a more adaptable way
to improve graph quality–e.g., by sparsifying particular areas based on the unique dynamics
of the environment, which are easily and naturally conceptualized by human instinct. In
experiments, we found our tools to be quite helpful in improving some measures of graph
quality, while their benefits on others dependended on the intuitiveness of the user interface.
Citation
Julian, Nicole Violet (2014). Tools for User Modification of Optimal Roadmaps. Undergraduate Research Scholars Program. Available electronically from https : / /hdl .handle .net /1969 .1 /157582.