Search

In this work, we present Hold Or take Optimal Plan (HOOP), a centralized trajectory generation algorithm for labeled multi-robot systems operating in obstacle-free, two-dimensional, continuous workspaces. Given a team of N robots, each with nth-order dynamics, our algorithm finds trajectories that navigate vehicles from their start positions to non-interchangeable goal positions in a collision-free manner. The algorithm operates in two phases. In the motion planning step, a geometric algorithm finds a collision-free, piecewise-linear trajectory for each robot. In the trajectory generation step, each robot’s trajectory is refined into a higher-order piecewise polynomial with a quadratic program. The novelty of our method is in this problem decomposition. The motion plan, through abstracting away robots’ dynamics, can be found quickly. It is then subsequently leveraged to construct collision avoidance constraints for N decoupled quadratic programs instead of a single, coupled optimization problem, decreasing computation time. We prove that this method is safe, complete, and generates smooth trajectories that respect robots’ dynamics. We demonstrate the algorithm’s practicality through extensive quadrotor experiments.

This article was updated to correct the axes in Figures 4e and 5d.

In this paper, we present a learning approach to goal assignment and trajectory planning for unlabeled robots operating in 2D, obstacle-filled workspaces. More specifically, we tackle the unlabeled multi-robot motion planning problem with motion constraints as a multi-agent reinforcement learning problem with some sparse global reward. In contrast with previous works, which formulate an entirely new hand-crafted optimization cost or trajectory generation algorithm for a different robot dynamic model, our framework is a general approach that is applicable to arbitrary robot models. Further, by using the velocity obstacle, we devise a smooth projection that guarantees collision free trajectories for all robots with respect to their neighbors and obstacles. The efficacy of our algorithm is demonstrated through varied simulations. A video describing our method and results can be found here.

Caves on other planetary bodies offer sheltered habitat for future human explorers and numerous clues to a planet's past for scientists. While recent orbital imagery provides exciting new details about cave entrances on the Moon and Mars, the interiors of these caves are still unknown and not observable from orbit. Multi-robot teams offer unique solutions for exploration and modeling subsurface voids during precursor missions. Robot teams that are diverse in terms of size, mobility, sensing, and capability can provide great advantages, but this diversity, coupled with inherently distinct low-level behavior architectures, makes coordination a challenge. This paper presents a framework that consists of an autonomous frontier and capability-based task generator, a distributed market-based strategy for coordinating and allocating tasks to the different team members, and a communication paradigm for seamless interaction between the different robots in the system. Robots have different sensors, (in the representative robot team used for testing: 2D mapping sensors, 3D modeling sensors, or no exteroceptive sensors), and varying levels of mobility. Tasks are generated to explore, model, and take science samples. Based on an individual robot's capability and associated cost for executing a generated task, a robot is autonomously selected for task execution. The robots create coarse online maps and store collected data for high resolution offline modeling. The coordination approach has been field tested at a mock cave site with highly-unstructured natural terrain, as well as an outdoor patio area. Initial results are promising for applicability of the proposed multi-robot framework to exploration and modeling of planetary caves.

As the usage of 3D models increases, so does the importance of developing accurate 3D shape retrieval algorithms. A common approach is to calculate a shape descriptor for each object, which can then be compared to determine two objects' similarity. However, these descriptors are often evaluated independently and on different datasets, making them difficult to compare. Using the SHREC 2011 Shape Retrieval Contest of Non-rigid 3D Watertight Meshes dataset, we systematically evaluate a collection of local shape descriptors. We apply each descriptor to the bag-of-words paradigm and assess the effects of varying the dictionary's size and the number of sample points. In addition, several salient point detection methods are used to choose sample points; these methods are compared to each other and to random selection. Finally, information from two local descriptors is combined in two ways and changes in performance are investigated. This paper presents results of these experiment, Comment: IS&T/SPIE Electronic Imaging 2012, Proceedings Vol. 8290 Three-Dimensional Image Processing (3DIP) and Applications II, Atilla M. Baskurt; Robert Sitnik, Editors, 82900N Dates: Tuesday-Thursday 24 - 26 January 2012, Paper 8290-22