Sandstrom, Read Mullan (2020-04). Approximating Configuration Space Topology with Workspace Models. Doctoral Dissertation. Thesis uri icon

abstract

  • Motion planning is an important problem in robotics which addresses the question of how to transition an actor between states in an environment subject to obstacles, kinematic, and other constraints. Exact motion planning is a computationally hard problem, which has prompted the popularity of sampling-based approaches. Algorithms in this family operate in the configuration space of a robot. This abstraction represents the space of possible poses, where feasible poses are termed valid. A solution to the planning constitutes a curve in the valid subset of configurations space, known as the free space. However, computing an explicit representation of the free space is an intractable problem, which renders sampling-based planners blind to its structure. This requires the algorithms to discover the space's topology by randomized sampling and validity checking. We observe that when planning for physical robots, there are frequently strong ties between the physical environment or workspace and the free subspace corresponding to the translational degrees of freedom. When such a relation exists, we can leverage information about the topology of workspace to provide direction to the search in configuration space, thereby significantly reducing the search domain. We present two algorithms which realize this objective. The first, Dynamic Region sampling, employs a topological skeleton of workspace to define the valid paths through the physical environment. This focuses the planner's generation of new samples within specific regions that travel along the skeleton, just ahead of the frontier of known valid configurations. This directs the search for a free space path along the known possibilities in workspace. The regions thus form both a guide for the planner and a mechanism of representing progress in covering the workspace. The second, Topological Nearest-Neighbor Filtering, uses a cell decomposition of the workspace as a means of mapping configurations to neighborhoods in free space. This mapping supports rapid locations of other configurations in neighborhoods that are nearby through connected workspace. This builds a model of connectivity into the nearest-neighbor process, which is a critical component in determining how to attempt connecting known configurations with local plans. The filter both expedites the nearest-neighbor operation and filters out obviously poor choices, promoting a higher rate of successful connection. We show how these methods can improve the robustness and efficiency of sampling-based motion planners in problems where a robot must traverse a complex workspace. We demonstrate that the methods work synergistically with each other to guide both exploration of free space and connection of the roadmap representation, promoting fast feasibility planning in many difficult problems.

publication date

  • April 2020