Motion planning tasks are often innately invariant to certain geometric transformations, or in other words, symmetric. This property, however, is not always reflected in learned policies that are trained on these tasks. Although this asymmetry can be addressed through data augmentation or additional training samples, doing so comes at a cost of increased training time. Instead of trying to remedy this issue during the learning process, we leverage this disparity during execution. We propose the symmetry exploitation policy, an augmentation in the post-hoc execution stage of RL policies. During the planning stage, we present the learned policy with an invariant, geometrically transformed version of the observation as an alternate perspective of the state. This allows the policy to produce multiple possible actions for a single state, and choose the action with the highest estimated value. Unlike other symmetry exploitation methods for learning solutions in motion planning, this method completely bypasses the need for additional training. We show the effect of the symmetry exploitation policy on DQN, A2C, and PPO policies, in three motion problems with different dimensions, observation types, and symmetries. The results show that by exploiting the symmetry of the task, a trained model achieves improved performance and better generalization, and can achieve comparable results to retraining, augmentation, or extended training, without incurring any additional training time. The efficacy is most prominent in more complex tasks, as 89 of the 100 models involved in the case study improve when using the method.

The virtual sliding joystick input method for touchscreen devices is widely used for games on mobile devices. Existing studies compare virtual joysticks to other input methods, but do not consider potential impacts of large differences in player control precision. For example, previous work has not investigated the ways in which the style of use by the player and the variations in available devices could affect the sensitivity (degree of heading change per touch displacement) in choosing a direction for the game character. In this paper, we present gameplay data from an ongoing study to determine what effects, if any, these factors have on player game performance. While different common touch patterns were observed on the joystick itself that would lead to differing input sensitivity levels, the players’ actual performance in a fast-paced, complex, dynamic obstacle avoidance game was not significantly changed. This suggests virtual joysticks are robust to differences in players and the physical devices themselves, at least for the motion-based obstacle avoidance game featured in this work.

Safely navigating environments with obstacles that move stochastically cannot be guaranteed by automation, due to the motion planning becoming computationally intractable. One way to improve safety is to add a defensive escort agent that can clear paths by interacting with obstacles. When such systems also involve human-automation collaboration in the form of shared control, the addition of a defensive escort agent raises the questions about how humans interact with multiple agents with different roles. Here, we consider the human’s role in a defensive escort problem where they can decide when and how to share control with the either primary or defensive agent. We implement this study within a mobile study platform designed for the investigation of different control schemes in a navigation and collision-avoidance task. We present a pilot study to demonstrate the potential for insight into this particular problem, and we find not only do humans perform better when controlling the defender than the payload, but they also actively choose to control the defender when given the choice.

Serious games rely on sensory cues from the system of interest to guide players in performing a specific task. For instance, a serious game used in research and education is interactive molecular docking, where players try to bind a small molecule (ligand) to a protein (receptor) exploring the high-dimensional space of possible molecular conformations. Players are guided by a score that depends on how strongly the two molecules attract or repel each other, and by visual inspection of the three-dimensional protein surface in search of cavities where the ligand may fit. In addition, some interactive molecular docking games can also display molecules according to the charge distribution on their surface, where positively and negatively charged regions are shown in different colors. It is assumed that this color scheme helps players, since attraction and repulsion of charges contribute to the electrostatic energy between the molecules, and thus the score. In this paper we test whether adding charge information as a visual cue contributes to higher scores and exploration of more favorable energy states. For two distinct sets of ligand-receptor pairs, to test our hypothesis we compare two models: One in which players have no electrostatic information, and the other where electrostatic colors are displayed, and players are told to match parts of the molecules that may attract each other based on their colors. We collect player data and cluster energy values into states, which are treated as Markov states. Transitions between states are interpreted as players making significant changes to the score and position of the molecules, with observation of different transition probabilities corresponding to distinct exploration patterns between the two models.

When a learning solution is needed for different robots, a model is often trained for each robot geometry, even if the robotic task is the same and the robots are structurally similar. In this paper, we address the problem of transfer learning of swept volume predictors for the motion of articulated robots with similar geometric structure. The swept volume is a scalar value corresponding to the space occupied by an entire motion of the robot. Swept volume has many applications, including being an ideal distance measure for sampling based motion planners, but it is expensive to compute. We address this learning problem through a multitask network where a common input is used to learn multiple related tasks. In this work a single network learns the kinematic-geometric information common among robots. In order to identify the properties of our multitask network favorable for transfer, we evaluate transfer properties of several shared layers, number of robots in multitask training, and feature layers. We demonstrate positive transfer results with a training set that is a fraction of the data size used in the multitask and baseline training. All the robots considered are 7-DOF manipulators with links with a variety of lengths and shapes. We also present a study of the weights and activations of the trained networks that show high correlation with the transferability patterns we observed.

This Workshop on the Algorithmic Foundations of Robotics (WAFR) Special Issue of the IEEE Transactions on Automation Science and Engineering (T-ASE) brings together eight extended articles from the thirteenth WAFR. While these eight articles span several application domains, they demonstrate advances in automation through algorithmic development and analysis. Nomination to this Special Issue was done in coordination with the entire program committee and guest edited by the four WAFR Co-Chairs. The articles in this Special Issue highlight cutting-edge research in general tools for motion planning, learning, control, manipulation, sensor-based planning, and robotic design.

Computation of the volume of space required for a robot to execute a sweeping motion from a start to a goal has long been identified as a critical primitive operation in both task and motion planning. However, swept volume computation is particularly challenging for multi-link robots with geometric complexity, e.g., manipulators, due to the non-linear geometry. While earlier work has shown that deep neural networks can approximate the swept volume quantity, a useful parameter in sampling-based planning, general network structures do not lend themselves to outputting geometries. In this paper we train and evaluate the learning of a deep neural network that predicts the swept volume geometry from pairs of robot configurations and outputs discretized voxel grids. We perform this training on a variety of robots from 6 to 16 degrees of freedom. We show that most errors in the prediction of the geometry lie within a distance of 3 voxels from the surface of the true geometry and it is possible to adjust the rates of different error types using a heuristic approach. We also show it is possible to train these networks at varying resolutions by training networks with up to 4x smaller grid resolution with errors remaining close to the boundary of the true swept volume geometry surface.

Determination of ligand binding pathways is an important factor to predict drug efficacy in drug discovery. Ligand-receptor binding involves the motion of many degrees of freedom, which can make binding pathways difficult to discover with traditional methods. Interactive molecular docking tools can allow users to explore the high dimensional energy landscape of the ligand-receptor system with rigid molecular models to determine low energy ligand states and pathways to binding. To introduce the effect of ligand flexibility in molecular docking with rigid body models, we use ensembles of distinct ligand conformation states that can be swapped during exploration. Our method emulates ligand flexibility effects in rigid body docking at no extra computational cost. Our automated method simulates user search performance with a path optimization algorithm. We find that allowing the algorithm to include different ligand conformations in its search for states of lower energy can result in optimized low energy pathways with reduced search times in difficult areas near energy barriers. This method can be adapted to include molecular flexibility effects in interactive rigid body molecular docking running in commodity hardware, such as molecular docking games.

Deep Reinforcement Learning (RL) has recently emerged as a solution for moving obstacle avoidance. Deep RL learns to simultaneously predict obstacle motions and corresponding avoidance actions directly from robot sensors, even for obstacles with different dynamics models. However, deep RL methods typically cannot guarantee policy convergences, i.e., cannot provide probabilistic collision avoidance guarantees. In contrast, stochastic reachability (SR), a computationally expensive formal method that employs a known obstacle dynamics model, identifies the optimal avoidance policy and provides strict convergence guarantees. The availability of the optimal solution for versions of the moving obstacle problem provides a baseline to compare trained deep RL policies. In this paper, we compare the expected cumulative reward and actions of these policies to SR, and find the following. 1) The state-value function approximates the optimal collision probability well, thus explaining the high empirical performance. 2) RL policies deviate from the optimal significantly thus negatively impacting collision avoidance in some cases. 3) Evidence suggests that the deviation is caused, at least partially, by the actor net failing to approximate the action corresponding to the highest state-action value.

Mobile gaming has become a popular pastime in recent years making it a viable avenue for crowdsourcing data collection with scientific games. We present one such application of scientific games on mobile devices by adapting an existing molecular docking game with a user interface suitable for this platform. In this initial study, players explore the state space of molecular interactions, and data is collected to be used in molecular motion planning. The results were compared to states collected from an automated Gaussian sampler commonly used in motion planning. Players were able to contribute states that could aid planners in finding molecular motion pathways with energies lower than the automated sampler. However, there remain challenges to the players’ ability to reach states in difficult areas due to the lack of molecular flexibility and guidance towards exploration over simply finding the lowest energy state.

We present PRM-RL, a hierarchical method for long-range navigation task completion that combines sampling-based path planning with reinforcement learning (RL). The RL agents learn short-range, point-to-point navigation policies that capture robot dynamics and task constraints without knowledge of the large-scale topology. Next, the sampling-based planners provide roadmaps which connect robot configurations that can be successfully navigated by the RL agent. The same RL agents are used to control the robot under the direction of the planning, enabling long-range navigation. We use the Probabilistic Roadmaps (PRMs) for the sampling-based planner. The RL agents are constructed using feature-based and deep neural net policies in continuous state and action spaces. We evaluate PRM-RL, both in simulation and on-robot, on two navigation tasks with non-trivial robot dynamics: end-to-end differential drive indoor navigation in office environments, and aerial cargo delivery in urban environments with load displacement constraints. Our results show improvement in task completion over both RL agents on their own and traditional sampling-based planners. In the indoor navigation task, PRM-RL successfully completes up to 215 m long trajectories under noisy sensor conditions, and the aerial cargo delivery completes flights over 1000 m without violating the task constraints in an environment 63 million times larger than used in training.

Identifying collision-free paths over long time windows in environments with stochastically moving obstacles is difficult, in part because long-term predictions of obstacle positions typically have low fidelity, and the region of possible obstacle occupancy is typically large. As a result, planning methods that are restricted to identifying paths with a low probability of collision may not be able to find a valid path. However, allowing paths with a higher probability of collision may limit detection of imminent collisions. In this paper, we present Dynamic Risk Tolerance (DRT), a framework that dynamically evaluates risk tolerance, a function which is formulated as a time-varying upper bound on the acceptable likelihood of collision for a given path. DRT is implemented with forward stochastic reachable sets to predict the exact distribution of obstacles in a scalable manner over an arbitrarily long time window. In effect, DRT identifies actions that balance risks posed by both near and far obstacles. We empirically compare DRT to other state of the art methods that are capable of generating real-time solutions in highly crowded environments, and demonstrate the success rates for DRT that is 46% higher than the best performing comparison method, in the most difficult problem tested.

This study presents Busy Beeway, a mobile game platform to investigate human-automation collaboration in dynamic environments. In Busy Beeway, users collaborate with automation to evade stochastically moving obstacles and reach a series of goals, in game levels of increasing difficulty. We are motivated by the need for reliable navigation aids in stochastic, dynamic environments, which are highly relevant for self-driving vehicles, UAVs, underwater and surface vehicles, and other applications. The proposed mobile game platform is agnostic to the particular algorithm underlying the autonomous system, can be used to evaluate both fully autonomous as well as human-in-the-loop systems, and is easily deployable, for large, remote user studies. This last element is key for rigorous study of human factors in navigation aids. Through a small 32--user study, we evaluate preliminary findings regarding the relative efficacy of collaborative and fully autonomous navigation, the relationship between success rate and users' learned trust in the automation (gathered via pre- and post-experiment surveys), and tolerance to error (for decisions made by the automation and by the user). This study validates the feasibility of Busy Beeway as a platform for human subject studies on human-automation collaboration, and suggests directions for future research in human-aided planning in difficult environments.

One of the primary challenges for autonomous robotics in uncertain and dynamic environments is planning and executing a collision-free path. Hybrid dynamic obstacles present an even greater challenge as the obstacles can change dynamics without warning and potentially invalidate paths. Artificial potential field (APF)-based techniques have shown great promise in successful path planning in highly dynamic environments due to their low cost at runtime. We utilize the APF framework for runtime planning but leverage a formal validation method, Stochastic Reachable (SR) sets, to generate accurate potential fields for moving obstacles. A small number of SR sets are computed a priori, then used to generate a potential field that represents the obstacle's stochastic motion for online path planning. Our method is novel and scales well with the number of obstacles, maintaining a relatively high probability of reaching the goal without collision, as compared to other traditional Gaussian APF methods. Here, we demonstrate our method with up to 900 hybrid dynamic obstacles and show that it outperforms the traditional Gaussian APF method by up to 60% in the holonomic case and up to 20% in the unicycle case.

Manual derivation of optimal robot motions for task completion is difficult, especially when a robot is required to balance its actions between opposing preferences. One solution has been proposed to automatically learn near optimal motions with Reinforcement Learning (RL). This has been successful for several tasks including swing-free UAV flight, table tennis, and autonomous driving. However, high-dimensional problems remain a challenge. We address this dimensionality constraint with PrEference Appraisal Reinforcement Learning (PEARL), which solves tasks with opposing preferences for acceleration controlled robots. PEARL projects the high-dimensional continuous robot state space to a low dimensional preference feature space resulting in efficient and adaptable planning. We demonstrate that on a dynamic obstacle avoidance robotic task, a single learning on a much simpler problem performs real-time decision-making for significantly larger, high-dimensional problems working in unbounded continuous states and actions. We trained the agent with 4 static obstacles, while the trained agent avoids up to 900 moving obstacles with complex hybrid stochastic obstacle dynamics in a highly constrained space using only limited information about the environment. We compare these tasks to traditional, often manually tuned solutions for these high-dimensional problems.

Motion planning in stochastic dynamic uncertain environments is critical in several applications such as human interacting robots, autonomous vehicles and assistive robots. In order to address these complex applications, several methods have been developed. The most successful methods often predict future obstacle locations in order identify collision-free paths. Since prediction can be computationally expensive, offline computations are commonly used, and simplifications such as the inability to consider the dynamics of interacting obstacles or possible stochastic dynamics are often applied. Online methods can be preferable to simulate potential obstacle interactions, but recent methods have been restricted to Gaussian interaction processes and uncertainty. In this paper we present an online motion planning method, Runtime Stochastic Ensemble Simulation (Runtime SES) planning, an inexpensive method for predicting obstacle motion with generic stochastic dynamics while maintaining a high planning success rate despite the potential presence of obstacle position error. Runtime SES planning evaluates the likelihood of collision for any state-time coordinate around the robot by performing Monte Carlo simulations online. This prediction is used to construct a customized Rapidly Exploring Random Tree (RRT) in order to quickly identify paths that avoid obstacles while moving toward a goal. We demonstrate Runtime SES planning in problems that benefit from online predictions, environments with strongly-interacting obstacles with stochastic dynamics and positional error. Through experiments that explore the impact of various parametrizations, robot dynamics and obstacle interaction models, we show that real-time capable planning with a high success rate is achievable in several complex environments.

Computational modeling is an important tool for the study of complex biochemical processes associated with cell signaling networks. However, it is challenging to simulate processes that involve hundreds of large molecules due to the high computational cost of such simulations. Rule-based modeling is a computational method that can be used to model these processes with reasonably low computational cost, but traditional rule-based modeling approaches do not include details of molecular geometry. The incorporation of molecular geometry into biochemical models can more accurately capture details of these processes, and may lead to insights into how geometry affects the products that form. Furthermore, geometric rule-based modeling can be used to complement other computational methods that explicitly represent molecular geometry in order to quantify binding site accessibility and steric effects. In this work, we propose a novel implementation of rulebased modeling that encodes details of molecular geometry into the rules and the binding rate constant associated with each rule. We demonstrate how the set of rules is constructed according to the curvature of the molecule. We then perform a study of antigen-antibody aggregation using our proposed method. We first simulate the binding of IgE antibodies bound to cell surface receptors Fc RI to various binding regions of the shrimp allergen Pen a 1 using a previously developed 3D rigid-body Monte Carlo simulation, and we analyze the distribution of the sizes of the aggregates that form during the simulation. Then, using our novel rule-based approach, we optimize a rule-based model according to the geometry of the Pen a 1 molecule and the data from the Monte Carlo simulation. In particular, we use the distances between the binding regions of the Pen a 1 molecule to optimize the rules and associated binding rate constants. We perform this procedure for three molecular conformations of Pen a 1 and analyze the impact of conformation on the aggregate size distribution and the optimal rule-based model. We find that the optimized rule-based models provide information about the average steric hindrance between binding regions and the probability that IgE-Fc RI receptor complexes will bind to these regions. In addition, the optimized rule-based models provide a means of quantifying the variation in aggregate size distribution that results from differences in molecular geometry.

Highly dynamic environments pose a particular challenge for motion planning due to the need for constant evaluation or validation of plans. However, due to the wide range of applications, an algorithm to safely plan in the presence of moving obstacles is required. In this paper, we propose a novel technique that provides computationally efficient planning solutions in environments with static obstacles and several dynamic obstacles with stochastic motions. Path-Guided APF-SR works by first applying a sampling-based technique to identify a valid, collision-free path in the presence of static obstacles. Then, an artificial potential field planning method is used to safely navigate through the moving obstacles using the path as an attractive intermediate goal bias. In order to improve the safety of the artificial potential field, repulsive potential fields around moving obstacles are calculated with stochastic reachable sets, a method previously shown to significantly improve planning success in highly dynamic environments. We show that Path-Guided APF-SR outperforms other methods that have high planning success in environments with 300 stochastically moving obstacles. Furthermore, planning is achievable in environments in which previously developed methods have failed.

Physical stochastic disturbances, such as wind, often affect the motion of robots that perform complex tasks in real-world conditions. These disturbances pose a control challenge because resulting drift induces uncertainty and changes in the robot's speed and direction. This paper presents an online control policy based on supervised machine learning, Least Squares Axial Sum Policy Approximation (LSAPA), that generates trajectories for robotic preference-balancing tasks under stochastic disturbances. The task is learned offline with reinforcement learning, assuming no disturbances, and then trajectories are planned online in the presence of disturbances using the current observed information. We model the robot as a stochastic control-affine system with unknown dynamics impacted by a Gaussian process, and the task as a continuous Markov Decision Process. Replacing a traditional greedy policy, LSAPA works for high-dimensional control-affine systems impacted by stochastic disturbances and is linear in the input dimensionality. We verify the method for Swing-free Aerial Cargo Delivery and Rendezvous tasks. Results show that LSAPA selects an input an order of magnitude faster than comparative methods, rejecting a range of stochastic disturbances. Further, experiments on a quadrotor demonstrate that LSAPA trajectories that are suitable for physical systems.

Motion planning in stochastic dynamic environments is difficult due to the need for constant plan adjustment caused by the uncertainty of the environment. There are many motion planning problems, including flight coordination and autonomous vehicles, that require an algorithm to predict obstacle motion and plan safely. In this paper, we propose Stochastic Ensemble Simulation (SES)-based planning, a novel framework to efficiently predict and produce safe trajectories in the presence of stochastic obstacles. The stochastic obstacles can be introduced in several ways including stochastic motion or position/speed uncertainty. SES-based planning works by first predicting an obstacle's future position offline through an ensemble of Monte Carlo simulations. These runs simulate the stochastic obstacle dynamics and store the simulation results in temporal snapshots of predicted positions. An online planner then uses this output to identify a predicted collision-free direct path to the goal. If the direct path is not expected to be collision-free, a more expensive tree-based planner is used. Our experiments show SES-based planning outperforms other methods that have high planning success in environments with 900 stochastically moving obstacles. Furthermore, our method plans trajectories with an 80% success rate for a 7 DOF robot in an environment with 250 stochastic moving obstacles and 50 obstacles with speed/position uncertainty. This complex problem is currently beyond the capability of several comparison methods.

One of the many challenges in designing autonomy for operation in uncertain and dynamic environments is the planning of collision-free paths. Roadmap-based motion planning is a popular technique for identifying collision-free paths, since it approximates the often infeasible space of all possible motions with a networked structure of valid configurations. We use stochastic reachable sets to identify regions of low collision probability, and to create roadmaps which incorporate likelihood of collision. We complete a small number of stochastic reachability calculations with individual obstacles a priori. This information is then associated with the weight, or preference for traversal, given to a transition in the roadmap structure. Our method is novel, and scales well with the number of obstacles, maintaining a relatively high probability of reaching the goal in a finite time horizon without collision, as compared to other methods. We demonstrate our method on systems with up to 50 dynamic obstacles.

Many biological processes, including immune recognition, enzyme catalysis, and molecular signaling, which is still an open problem in biological sciences. We present Molecular Tetris, a game in which a player can explore the binding between a protein receptor and ligand. This exploration is similar to the game Tetris with atomic forces guiding best fits between shapes. This game will be utilized for crowdsourced haptic-guided motion planning. Haptic touch devices enable users to feel the interactions of two molecules as they move the ligand into an appropriate binding site on the receptor. We demonstrate the method on a critical piece of human immune response, ligand binding to a Major Histocompatibility Complex (MHC) molecule. Through multiple runs by our users, we construct a global roadmap that finds low energy paths to molecular docking sites. These paths are comparable to a highly-biased roadmap generated by Gaussian sampling around the known bound state. Our users are able to find low energy paths with both a specialized force-feedback device and a commodity game console controller.

Attaining autonomous flight is an important task in aerial robotics. Often flight trajectories are not only subject to unknown system dynamics, but also to specific task constraints. This paper presents a motion planning method for generating trajectories with minimal residual oscillations (swing-free) for rotorcraft carrying a suspended loads. We rely on a finite-sampling, batch reinforcement learning algorithm to train the system for a particular load. We find criteria that allow the trained agent to be transferred to a variety of models, state and action spaces and produce a number of different trajectories. Through a combination of simulations and experiments, we demonstrate that the inferred policy is robust to noise and the unmodeled dynamics of the system. The contributions of this work are 1) applying reinforcement learning to solve the problem of finding swing-free trajectories for rotorcraft, 2) designing a problem-specific feature vector for value function approximation, 3) giving sufficient conditions for successful learning transfer to different models, state and action spaces, and 4) verification of the resulting trajectories in both simulation and autonomous control of quadrotors with suspended loads.

In this paper, we present a problem where a suspended load, carried by a rotorcraft aerial robot, performs trajectory tracking. We want to accomplish this by specifying the reference trajectory for the suspended load only. The aerial robot needs to discover/learn its own trajectory which ensures that the suspended load tracks the reference trajectory. As a solution, we propose a method based on least-square policy iteration (LSPI) which is a type of reinforcement learning algorithm. The proposed method is verified through simulation and experiments.

Probabilistic Roadmap Methods (PRMs) have been shown to work well at solving high Degree of Freedom (DoF) motion planning problems. They work by constructing a roadmap that approximates the topology of collision-free configuration space. However, this requires an accurate model of the robot's workspace in order to test if a sampled configuration is in collision or not. In this paper, we present a method for roadmap construction that can be used in workspaces with uncertainties in the model. For example, these can be inaccuracies that are caused by sensor error when an environment model was constructed. The uncertainty is encoded into the roadmap directly through the incorporation of non-binary collision detection values, e.g., a probability of collision. We refer to this new roadmap as a Safety-PRM because it allows tunability between the expected safety of the robot and the distance along a path. We compare the computational cost of Safety-PRM against two planning methods for environments without modeling errors, basic PRM and Medial Axis PRM (MAPRM), known for low computational cost and maximizing clearance, respectively. We demonstrate that in most cases, Safety-PRM produces high quality paths maximized for clearance and safety with the least amount of computational cost. We show that these paths are tunable for both robot safety and clearance. Finally, we demonstrate the applicability of Safety-PRM on an experimental system, a Barrett Whole Arm Manipulator (WAM). On the WAM, we demonstrate the mapping of expected collision to robot speeds to enable the robot to physically test the safety of the roadmap and use torque estimation to make roadmap modifications.

BECCA (a Brain-Emulating Cognition and Control Architecture software package) was developed in order to perform general reinforcement learning, that is, to enable unmodeled embodied systems operating in unstructured environments to perform unfamiliar tasks. It accomplishes this through automatic paired feature creation and reinforcement learning algorithms. This paper describes an implementation of BECCA on a seven Degree of Freedom (DoF) Barrett Whole Arm Manipulator (WAM) undergoing a series of experiments designed to test the reinforcement learner's ability to adapt to the WAM hardware. In the experiments, the following is demonstrated, 1) learning to transition the WAM between states, 2) learning to perform at near optimal levels on one, two and three dimensional navigation tasks, 3) applying learning in simulation to hardware performance, 4) learning under inconsistent, human-generated reward, and 5) combining the reinforcement learner with Probabilistic Roadmap Methods (PRM) to improve scalability. The goal of the paper is to demonstrate both the scalability of the BECCA reinforcement learning approach using different formulations of the state space and to show the approach in this paper operating on complex physical hardware.

Probabilistic Roadmap Methods (PRMs) are one of the most used classes of motion planning methods. These sampling-based methods generate robot configurations (nodes) and then connect them to form a graph (roadmap) containing representative feasible pathways. A key step in PRM roadmap construction involves identifying a set of candidate neighbors for each node. Traditionally, these candidates are chosen to be the k-closest nodes based on a given distance metric. In this paper, we propose a new neighbor selection policy called LocalRand(k,K'), that first computes the K' closest nodes to a specified node and then selects k of those nodes at random. Intuitively, LocalRand attempts to benefit from random sampling while maintaining the higher levels of local planner success inherent to selecting more local neighbors. We provide a methodology for selecting the parameters k and K' . We perform an experimental comparison which shows that for both rigid and articulated robots, LocalRand results in roadmaps that are better connected than the traditional k-closest policy or a purely random neighbor selection policy. The cost required to achieve these results is shown to be comparable to k-closest.

Since planning environments are complex and no single planner exists that is best for all problems, much work has been done to explore methods for selecting where and when to apply particular planners. However, these two questions have been difficult to answer, even when adaptive methods meant to facilitate a solution are applied. For example, adaptive solutions such as setting learning rates, hand-classifying spaces, and defining parameters for a library of planners have all been proposed. We demonstrate a strategy based on unsupervised learning methods that makes adaptive planning more practical. The unsupervised strategies require less user intervention, model the topology of the problem in a reasonable and efficient manner, can adapt the sampler depending on characteristics of the problem, and can easily accept new samplers as they become available. Through a series of experiments, we demonstrate that in a wide variety of environments, the regions automatically identified by our technique represent the planning space well both in number and placement. We also show that our technique has little overhead and that it out-performs two existing adaptive methods in all complex cases studied.

There are many randomized motion planning techniques, but it is often difficult to determine what planning method to apply to best solve a problem. Planners have their own strengths and weaknesses, and each one is best suited to a specific type of problem. In previous work, we proposed a meta-planner that, through analysis of the problem features, subdivides the instance into regions and determines which planner to apply in each region. The results obtained with our prototype system were very promising even though it utilized simplistic strategies for all components. Even so, we did determine that strategies for problem subdivision and for combination of partial regional solutions have a crucial impact on performance. In this paper, we propose new methods for these steps to improve the performance of the meta-planner. For problem subdivision, we propose two new methods: a method based on ‘ gaps’ and a method based on information theory. For combining partial solutions, we propose two new methods that concentrate on neighboring areas of the regional solutions. We present results that show the performance gain achieved by utilizing these new strategies.