A scalable motion planner for high-dimensional kinematic systems

Sampling-based algorithms are known for their ability to effectively compute paths for high-dimensional robots in relatively short times. The same algorithms, however, are also notorious for poor-quality solution paths, particularly as the dimensionality of the system grows. This work proposes a new probabilistically complete sampling-based algorithm, XXL, specially designed to plan the motions of high-dimensional mobile manipulators and related platforms. Using a novel sampling and connection strategy that guides a set of points mapped on the robot through the workspace, XXL scales to realistic manipulator platforms with dozens of joints by focusing the search of the robot’s configuration space to specific degrees of freedom that affect motion in particular portions of the workspace. Simulated planning scenarios with the Robonaut2 platform and planar kinematic chains confirm that XXL exhibits competitive solution times relative to many existing works while obtaining execution-quality solution paths. Solutions from XXL are of comparable quality to cost-aware methods even though XXL does not explicitly optimize over any particular criteria, and are computed in an order of magnitude less time. Furthermore, observations about the performance of sampling-based algorithms on high-dimensional manipulator planning problems are presented that reveal a cautionary tale regarding two popular guiding heuristics used in these algorithms, indicating that a nearly random search may outperform the state-of-the-art when defining such heuristics is known to be difficult.

Kinodynamic planning for spherical tensegrity locomotion with effective gait primitives

Tensegrity-based robots can achieve locomotion through shape deformation and compliance. They are highly adaptable to their surroundings, and are lightweight, low cost, and physically robust. Their high dimensionality and strongly dynamic nature, however, can complicate motion planning. Efforts to date have primarily considered quasi-static reconfiguration and short-term dynamic motion of tensegrity robots, which do not fully exploit the underlying system dynamics in the long term. Longer-horizon planning has previously required costly search over the full space of valid control inputs. This work synthesizes new and existing approaches to produce dynamic long-term motion while balancing the computational demand. A numerical process based upon quasi-static assumptions is first applied to deform the system into an unstable configuration, causing forward motion. The dynamical characteristics of the result are then altered via a few simple parameters to produce a small but diverse set of useful behaviors. The proposed approach takes advantage of identified symmetries on the prototypical spherical tensegrity robot, which reduce the number of needed gaits but allow motion along different directions. These gaits are first combined with a standard search method to achieve long-term planning in environments where the developed gaits are effective. For more complex environments, the various motion primitives are paired with the fall-back option of random valid actions and are used by an informed sampling-based kinodynamic motion planner with anytime properties. Evaluations using a physics-based model for the prototypical robot demonstrate that modest but efficiently applied search effort can unlock the utility of dynamic tensegrity motion to produce high-quality solutions.

Structure-Guided Protein Transition Modeling with a Probabilistic Roadmap Algorithm

Proteins are macromolecules in perpetual motion, switching between structural states to modulate their function. A detailed characterization of the precise yet complex relationship between protein structure, dynamics, and function requires elucidating transitions between functionally-relevant states. Doing so challenges both wet and dry laboratories, as protein dynamics involves disparate temporal scales. In this paper, we present a novel, sampling-based algorithm to compute transition paths. The algorithm exploits two main ideas. First, it leverages known structures to initialize its search and define a reduced conformation space for rapid sampling. This is key to address the insufficient sampling issue suffered by sampling-based algorithms. Second, the algorithm embeds samples in a nearest-neighbor graph where transition paths can be efficiently computed via queries. The algorithm adapts the probabilistic roadmap framework that is popular in robot motion planning. In addition to efficiently computing lowest-cost paths between any given structures, the algorithm allows investigating hypotheses regarding the order of experimentally-known structures in a transition event. This novel contribution is likely to open up new venues of research. Detailed analysis is presented on multiple-basin proteins of relevance to human disease. Multiscaling and the AMBER ff14SB force field are used to obtain energetically-credible paths at atomistic detail.

Clearance-driven motion planning for mobile robots with differential constraints

This paper presents an approach that integrates the geometric notion of clearance (distance to the closest obstacle) into sampling-based motion planning to enable a robot to safely navigate in challenging environments. To reach the goal destination, the robot must obey geometric and differential constraints that arise from the underlying motion dynamics and the characteristics of the environment. To produce safe paths, the proposed approach expands a motion tree of collision-free and dynamically feasible motions while maintaining locally maximal clearance. In distinction from related work, rather than explicitly constructing the medial axis, the proposed approach imposes a grid or a triangular tessellation over the free space and uses the clearance information to construct a weighted graph where edges that connect regions with low clearance have high cost. Minimum-cost paths over this graph produce high-clearance routes that tend to follow the medial axis without requiring its explicit construction. A key aspect of the proposed approach is a route-following component which efficiently expands the motion tree to closely follow such high-clearance routes. When expansion along the current route becomes difficult, edges in the tessellation are penalized in order to promote motion-tree expansions along alternative high-clearance routes to the goal. Experiments using vehicle models with second-order dynamics demonstrate that the robot is able to successfully navigate in complex environments. Comparisons to the state-of-the-art show computational speedups of one or more orders of magnitude.