This page highlights single-agent motion planning guided by machine learning. For multi-agent guidance, visit Multi-Agent Guided Planning.

We focus on sampling-based planners (e.g., PRM/RRT) that learn from workspace structure and past performance to pick better samples and connections. Techniques here adapt to local features, leverage workspace skeletons, and use reinforcement/local learning to choose strategies automatically instead of hand-tuning for each region or environment.

Feature-Sensitive Motion Planning

We propose a feature-sensitive meta-planner that cooperatively applies more specialized planners to map an specific instance. It analizes a region to characterize it so to find the best-suited planning strategy for the region and to decide whether it needs to partition it and repeat the characterization until assigning a planning strategy to each distinct region in the planning space. Then, the meta-planner maps each region with the strategy assigned. Finally, regional maps are combined into a map for the overall problem.

Framework Overview
Framework Overview

Example: 2 DOF point robot in plannar environment

In this instance of the motion planning problem red areas represent obstacles while the free space is in white.

Planning input
Input
Feature-sensitive meta-planner
Characterization and Partitioning
Region partitioning
Mapping in each Region
Combined map
Map Combination

Characterization:

The region is analyzed to find a matching planning strategy. Descriptive features are extracted from the region. Machine learning is used to analize the features and to search for a matching planner.

Partitioning:

If it is not possible to match the region to a good planner, the region is partitioned into subregions. Machine learning techniques are used to decide how to build subregions.

Mapping in each Region:

Each region is mapped with the planning strategy found during its characterization. In the example we see how the free area on the right needs only a few samples to be well-mapped, while the area on the bottom is mapped with many samples around C-obstacles.

Combination:

Specialized methods are used to combine regional solutions into an overall solution. Efficient methods for combination are needed to obtain good performance.

Example: 6 DOF Rigid Body Robot in diverse 3D Environment

Non-homogeneous partition illustration
A non-homogeneous partition
where no single planner would perform well
Cluttered partition illustration
A cluttered partition
An obstacle-based sampling would perform well
Free partition illustration
A free partition
A basic probabilistic roadmap method would perform well
Free partition illustration
The resulting map after applying the best planner in each partition

Presentation Slides

RESAMPL: A Region-Sensitive Adaptive Motion Planner

Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (PRMs) or rapidly-exploring random trees (RRT), have been highly successful in solving many high degree of freedom problems, there are still many scenarios in which we need better methods, e.g., problems involving narrow passages or which contain multiple regions that are best suited to different planners. In this work, we present RESAMPL, a motion planning strategy that uses local region information to make intelligent decisions about how and where to sample, which samples to connect together, and to find paths through the environment. Briefly, RESAMPL classifies regions based on the entropy of the samples in it, and then uses these classifications to further refine the sampling. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. The strategy for connecting samples is guided by the region graph, and can be exploited in both multi-query and single-query scenarios. Our experimental results comparing RESAMPL to previous multi-query and single-query methods show that RESAMPL is generally significantly faster and also usually requires fewer samples to solve the problem.

Adaptive Neighbor Connection

We present an algorithm that considers the performance history in the vicinity of the current connection attempt and uses this information to select good candidates for connection. It thus removes any need to explicitly partition the environment which is burdensome and typically difficult to do. Experimental results show that the method learns and adapts in heterogeneous environments, and finds solution paths faster for single and multi-query scenarios and builds roadmaps with better coverage and connectivity.

Reinforcement learning loop diagram
Reinforcement Learning Example

In this work we use machine learning techniques to intelligently combine and use any existing PRM method. This affords us the opportunity to use all available PRM method irrespective of the problem scenario. We show in our experiments that we are able to remove the overhead of deciding what PRM method to use for a given input problem. We test on a variety of heterogeneous environment including protein folding simulations and we utilize the strengths (ability to generate samples in narrow passages) of these methods when needed while minimizing their weaknesses (time needed to solve a query).

Heterogeneous environment scenarios
Heterogeneous Environment Example

Probabilistic Roadmap Methods (PRMs) are widely used motion planning methods that sample robot configurations (nodes) and connect them to form a graph (roadmap) containing feasible trajectories. Many PRM variants propose different strategies for each of the steps and choosing among them is problem dependent. Planning in heterogeneous environments and/or on parallel machines necessitates dividing the problem into regions where these choices have to be made for each one. Hand-selecting the best method for each region becomes infeasible. In particular, there are many ways to select connection candidates, and choosing the appropriate strategy is input dependent.

In this work, we present a general connection framework that adaptively selects a neighbor finding strategy from a candidate set of options. Our framework learns which strategy to use by examining their success rates and costs. It frees the user of the burden of selecting the best strategy and allows the selection to change over time.

We perform experiments on rigid bodies of varying geometry and articulated linkages up to 37 degrees of freedom. Our results show that strategy performance is indeed problem/region dependent, and our adaptive method harnesses their strengths. Over all problems studied, our method differs the least from manual selection of the best method, and if one were to manually select a single method across all problems, the performance can be quite poor. Our method is able to adapt to changing sampling density and learns different strategies for each region when the problem is partitioned for parallelism.

U-tunnel environment illustration
U-Tunnel Environment
Maze heterogeneous environment
Maze Heterogenous Environment

The U-tunnel environment has a long rigid body robot which behaves much differently than the compact robots in the prior environments. Here, ANC performs significantly better than the other methods in terms of running time and roadmap size and near the best in terms of edges/nodes ratio. Figure 3 provides the learning plot. Again, ANC is able to adapt and learn a good connection strategy.

Learning profile for a U-tunnel environment
Learning Profile for a U-tunnel Environment

The maze environment result plots shows the probability that each connection method is selected in the ANC framework over time for a single representative run. Figure 2 shows that early on R-Closest, K-Rand (Euclidean) is selected. However, as roadmap construction progresses, the success of this method begins to level out and the probability of K-Closest, R-Rand (Euclidean) begins to increase and then levels off.

Learning profile for a maze environment
Learning Profile for a maze Environment

Probabilistic Roadmap Methods (PRMs) solve the motion planing problem by constructing a roadmap (or graph) that models the motion space when feasible local motions exist. PRMs and variants contain several phases during roadmap generation i.e., sampling, connection, and query. Some work has been done to apply machine learning to the connection phase to decide which variant to employ, but it uses a global learning approach that is inefficient in heterogeneous situations.

We present an algorithm that instead uses local learning: it only considers the performance history in the vicinity of the current connection attempt and uses this information to select good candidates for connection. It thus removes any need to explicitly partition the environment which is burdensome and typically difficult to do. Our results show that our method learns and adapts in heterogeneous environments, including a KUKA youBot with a fixed and mobile base. It finds solution paths faster for single and multi-query scenarios and builds roadmaps with better coverage and connectivity given a fixed amount of time in a wide variety of input problems. In all cases, our method outperforms the previous adaptive connection method and is comparable or better than the best individual method.

Local learning region
Local learning region
Local learning scenario
Local learning scenario

The 36 DOF JellyFish environment consist of a robot has three articulated arms attached to a sphere where each arm has 10 links. The aim of this experiment is to see the performance of ANC-Spatial on a highly articulated and complex robot. Different types of obstacles are placed throughout the envi- ronment. We again provide 8 query samples and count how many possible queries can be solved. Roadmap construction is allowed to take 1500 seconds. Figure 6 (bars in red) shows the percentage of queries (6(a)) and the percentage of nodes in the largest connected components (6(b)) using the StraightLine local planner for each method. ANC-Spatial again solves the greatest percent- age of queries with a higher percentage of its nodes in the largest connected component. ANC-Spatial also outperforms ANC in this articulated linkage environment. This environ- ment is prone to bad partitioning choices because a bad partitioning could easily form a narrow passage that cannot be traversed by this highly articulated linkage. Thus it is even more imperative that localized learning regions are dynamic. Figure 6 (bars in green) shows results using the RotateATS local planner. ANC-Spatial also outperforms the other methods in terms of percentage of queries solved. We also have a good percentage of nodes in the largest connected com- ponent. Even a large change in local planners (as evidenced by changes in individual connection method performance) results in small change in ANC-Spatial performance.

36 DOF JellyFish environment
36 DOF JellyFish Environment
36 DOF JellyFish time results
36 DOF JellyFish Time Results
36 DOF JellyFish node results
36 DOF JellyFish Node Results

8 DOF KUKA youBot model with a mobile base: Our image shows an 8 DOF KUKA youBot robot with a mobile base that must pass through doorways while navigating around boxes in an industrial scene. The query requires the robot to move through each room and reach into a cabinet. Our results show the time needed solve the query with different k values (5, 10, 15, 20) and the usage frequency of each individual connection method. Scaled Euclidean and LpSwept shows little change in the time needed with respect to k. Scaled Euclidean is the best performing individual connection method. ANC-Spatial performs comparably for the different k values. We also gave ANC and ANC-Spatial a chance to learn the appropriate k value by providing all instances of the connection methods as input. These are denoted as ANC(all) and ANC-Spatial(all) in Figure 8. ANC-Spatial(all) performs comparable to the best connection methods in the list and is still able to learn well when faced with different k values. ANC, however, has difficulty handling the large number of choices even though it utilizes the one of the best performing individual methods

KUKA youBot environment
KukayouBot Environment
KUKA youBot frequency of usage
KukayouBot Frequency of Usage
KUKA youBot time results
KukayouBot Time Results

Simulating protein folding motions is an important problem in computational biology. Motion planning algorithms such as Probabilistic Roadmap Methods (PRMs) have been successful in modeling the protein folding landscape. PRMs and variants contain several phases (i.e., sampling, connection, and path extraction). Global machine learning has been applied to the connection phase but is inefficient in situations with varying topology, such as those typical of folding landscapes. Results: We present a local learning algorithm that considers the past performance near the current connection attempt as a basis for learning. It is sensitive not only to different types of landscapes but also to differing regions in the landscape itself, removing the need to explicitly partition the landscape. We perform experiments on 23 proteins of varying secondary structure makeup with 52–114 residues. Our method models the landscape with better quality and comparable time to the best performing individual method and to global learning.

Folding landscape potential energy
Folding Landscape
Connection learning on folding landscape
Applying Learning to Computational Biology

Learning methods outperform the best individual connection methods much of the time: ANC-global produces lower weighted pathways than Cluster, Euclidean, and lRMSD for 11 of the 23 proteins, and ANC-local (blue bars) for 19 of the 23 proteins. Notice, however, that the type of learning is important. ANC-local with its local learning is much more successful than ANC- global with its global approach. In fact, ANC-local is the best approach for 18 out of the 23 proteins studied. ANC-local performs as well as or better than the best performing method for 12 out of 23 proteins (52% of the time), while ANC-global performs best for only 3. Just as with quality, the best performing individual connection method varies between proteins: Euclidean is fastest for 11 proteins, Cluster for 2, and lRMSD for 1. Euclidean is most often the fastest method but is the best method in terms of quality for only 1 protein.

Quality results across proteins
Quality Results
Time results across proteins
Time Results

Publications

Updated: