This study informs the design of future multi-agent pathfinding (MAPF) and multi-robot motion planning (MRMP) algorithms by guiding choices based on constraint classification for constraint-based search algorithms. We categorize constraints as conservative or aggressive and provide insights into their search behavior, focusing specifically on vanilla Conflict-Based Search (CBS) and Conflict-Based Search with Priorities (CBSw/P). Under a hybrid grid-roadmap representation with varying resolution, we observe that aggressive (priority constraint) formulations tend to solve more instances as agent count or resolution increases, whereas conservative (motion constraint) formulations yield stronger solution quality when both succeed. Findings are synthesized in a decision flowchart, aiding users in selecting suitable constraints. Recommendations extend to Multi-Robot Motion Planning (MRMP), emphasizing the importance of considering topological features alongside problem, solution, and representation features. A comprehensive exploration of the study, including raw data and map performance, is available in our public GitHub Repository.

In this article, we present a multi-robot task and motion planning method that, when applied to the rearrangement of objects by manipulators, results in solution times up to three orders of magnitude faster than the existing methods and successfully plans for problems with up to 20 objects, more than three times as many objects as comparable methods. We achieve this improvement by decomposing the planning space to consider manipulators alone, objects, and manipulators holding objects. We represent this decomposition with a hypergraph where vertices are decomposed elements of the planning spaces and hyperarcs are transitions between elements. The existing methods use graph-based representations where vertices are full composite spaces and edges are transitions between these. Using the hypergraph reduces the representation size of the planning space for multimanipulator object rearrangement, the number of hypergraph vertices scales linearly with the number of either robots or objects, while the number of hyperarcs scales quadratically with the number of robots and linearly with the number of objects. In contrast, the number of vertices and edges in graph-based representations scales exponentially in the number of robots and objects. We show that similar gains can be achieved for other multi-robot task and motion planning problems.

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.

Sampling-based motion planning is the state-of-the-art technique for solving challenging motion planning problems in a wide variety of domains. While generally successful, their performance suffers from increasing problem complexity. In many cases, the full problem complexity is not needed for the entire solution. We present a hierarchical aggregation framework that groups and models sets of obstacles based on the currently needed level of detail. The hierarchy enables sampling to be performed using the simplest and most conservative representation of the environment possible in that region. Our results show that this scheme improves planner performance irrespective of the underlying sampling method and input problem. In many cases, improvement is significant, with running times often less than 60% of the original planning time.

We present a reactive multi-agent push system for a large set of objects. The behavior for the pushing agents consists of: 1) selecting and updating an object set to push, 2) reaching positions near the objects to start influencing, 3) pushing the objects along a path to the goal region, and 4) regrouping when needed to ensure the group is packed tightly enough. The emergent properties of the behavior allow us to test how effectively a group of agents can push a set of objects through the environment with different strategies.

Rapidly-exploring Random Trees (RRTs) are effective for a wide range of applications ranging from kinodynamic planning to motion planning under uncertainty. However, RRTs are not as efficient when exploring heterogeneous environments and do not adapt to the space. For example, in difficult areas an expensive RRT growth method might be appropriate, while in open areas inexpensive growth methods should be chosen. In this paper, we present a novel algorithm, Adaptive RRT, that adapts RRT growth to the current exploration area using a two level growth selection mechanism. At the first level, we select groups of expansion methods according to the visibility of the node being expanded. Second, we use a cost-sensitive learning approach to select a sampler from the group of expansion methods chosen. Also, we propose a novel definition of visibility for RRT nodes which can be computed in an online manner and used by Adaptive RRT to select an appropriate expansion method. We present the algorithm and experimental analysis on a broad range of problems showing not only its adaptability, but efficiency gains achieved by adapting exploration methods appropriately.

This paper discusses how to generate mobile robots' behaviors using genetic algorithms, GA. The behaviors are built using state machines implemented in a programmable logic device, an FPGA, and they are encoded in such a way that a state machine architecture executes them, controlling the overall operation of a small mobile robot. The behaviors generated by the GA are evaluated according to a fitness function that grades their performance. Basically, the fitness function evaluates the robot's performance when it goes from an origin to a destination. In our approach each individuals' chromosome represents, given a set of inputs coming from the sensors and the current state, the next state and outputs that controls the robot's movements. For each generation the GA needs to evaluate population's individuals, doing this with the real robot it would required to much time, that would be impossible to do. Thus, the GA needs a simulator, as close as it can be to the real robot and its environment. The simulator gets the individuals' chromosomes and executes the algorithm state machine represented by them, it simulates the movements of the robot depending of the output generated in the present state and the simulated robot's sensors. Our objective was to prove that GA is a good option as a method for finding behaviors for mobile robots' navigation and also that these behaviors can be implemented in FPGAs.

Many sampling methods for motion planning explore the robot's configuration space (C-space) starting from a set of configuration(s) and incrementally explore surrounding areas to produce a growing model of the space. Although there is a common understanding of the strengths and weaknesses of these techniques, metrics for analyzing the incremental exploration process and for evaluating the performance of incremental samplers have been lacking. We propose the use of local metrics that provide insight into the complexity of the different regions in the model and global metrics that describe the process as a whole. These metrics only require local information and can be efficiently computed. We illustrate the use of our proposed metrics to analyze representative incremental strategies including the rapidly-exploring random trees, expansive space trees, and the original randomized path planner. We show how these metrics model the efficiency of C-space exploration and help to identify different modeling stages. In addition, these metrics are ideal for adapting space exploration to improve performance.

With the success of randomized sampling-based motion planners such as probabilistic roadmap methods, much work has been done to design new sampling techniques and distributions. To date, there is no sampling technique that outperforms all other techniques for all motion planning problems. Instead, each proposed technique has different strengths and weaknesses. However, little work has been done to combine these techniques to create new distributions. In this paper, we propose to bias one sampling distribution with another such that the resulting distribution out-performs either of its parent distributions. We present a general framework for biasing samplers that is easily extendable to new distributions and can handle an arbitrary number of parent distributions by chaining them together. Our experimental results show that by combining distributions, we can out-perform existing planners. Our results also indicate that not one single distribution combination performs the best in all problems, and we identify which perform better for the specific application domains studied

There are many sampling-based motion planning methods that model the connectivity of a robot's configuration space (C-space) with a graph whose nodes are valid configurations and whose edges represent valid transitions between nodes. One of the biggest challenges faced by users of these methods is selecting the right planner for their problem. While researchers have tried to compare different planners, most accepted metrics for comparing planners are based on efficiency, e.g., number of collision detection calls or samples needed to solve a particular set of queries, and there is still a lack of useful and efficient quantitative metrics that can be used to measure the suitability of a planner for solving a problem. That is, although there is great interest in determining which planners should be used in which situations, there are still many questions we cannot answer about the relative performance of different planning methods. In this paper we make some progress towards this goal. We propose a metric that can be applied to each new sample considered by a sampling-based planner to characterize how that sample improves, or not, the planner's current C-space model. This characterization requires only local information and can be computed quite efficiently, so that it can be applied to every sample. We show how this characterization can be used to analyze and compare how different planning strategies explore the configuration space. In particular, we show that it can be used to identify three phases that planners go through when building C-space models: quick learning (rapidly building a coarse model), model enhancement (refining the model), and learning decay (oversampling - most samples do not provide additional information). Hence, our work can also provide the basis for determining when a particular planning strategy has 'converged' on the best C-space model that it is capable of building

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.

In this paper we investigate how the coverage and connectedness of PRM roadmaps can be improved by adding a connected component (CC) connection step to the general PRM framework. We provide experimental results establishing that significant roadmap improvements can be obtained relatively efficiently by utilizing a suite of CC connection methods, which include variants of existing methods such as RRT and a new ray tracing based method. The coordinated application of these techniques is enabled by methods for selecting and scheduling pairs of nodes in different CCs for connection attempts. In addition to identifying important and/or promising regions of C-space for exploration, these methods also provide a mechanism for controlling the cost of the connection attempts. In our experiments, the time required by the improvement phase was on the same order as the time used to generate the initial roadmap.