Robots are increasingly being used in situations such as search and rescue that require robust navigation capabilities, potentially in areas with little or no GPS or other high-quality localization information. As more robots are used in these scenarios, it becomes viable to collaborate between heterogeneous types of robots to leverage their individual strengths while minimizing their weaknesses. More specifically, in a scenario involving unmanned ground and aerial vehicles (UGV, UAV), the ground robot can contribute its high payload capacity to provide computational resources and high accuracy sensors while the aerial robot can bring its high mobility and capability to traverse obstacles to the team. However, in order for the team to benefit from these capabilities, it must be capable of generating a plan for both robots that allows them to collaboratively localize when necessary. Our approach to this problem is to combine a recently developed state lattice planner using controller-based motion primitives (SLC) with planning using adaptive dimensionality (PAD). The SLC planner allows for robust navigation using a wide variety of sensors including in areas with no or limited high-quality localization information while the PAD planner allows us to expand beyond a single robot and generate plans for a team of robots operating in a high dimensional space. We present our results to this combined approach for a UGV/UAV team operating indoors in areas with limited visual features.

Advanced modern humanoid robots often have complex manipulators with a large number of degrees of freedom. Thus, motion planning for such manipulators is a very computationally challenging problem. However, often robotic manipulators allow the wrist degrees of freedom to be controlled independently from the configuration of the rest of the arm. In this paper we show how to split the high dimensional planning problem into two lower-dimensional sub-problems - planning for the main arm joints and planning for the wrist joints, without losing guarantees on completeness. This approach is an extension of our previously developed framework for planning with adaptive dimensionality. Experimentally, we show that this approach is very effective in speeding up planning for robotic arms on Willow Garage's PR2 platform. We compare our algorithm with several popular alternative approaches for performing motion planning for robotic arms. The results we observe illustrate that our algorithm provides a good balance between planning time, planning success rate, path consistency, and path quality.

Incremental graph search methods reuse information from previous searches in order to minimize redundant computation and to find solutions to series of similar search queries much faster than it is possible by solving each query from scratch. In this work, we present a simple, but very effective, technique for performing incremental weighted A* graph search in an anytime fashion. On the theoretical side, we show that our anytime incremental algorithm preserves the strong theoretical guarantees provided by the weighted A* algorithm, such as completeness and bounds on solution cost sub-optimality. We also show that our algorithm can handle a variety of changes to the underlying graph, such as both increasing and decreasing edge costs, and changes in the heuristic. On the experimental side, we demonstrate the effectiveness of our algorithm in the context of (x, y, z, yaw) navigation planning for an unmanned aerial vehicle and compare our algorithm to popular incremental and anytime graph search algorithms.

Mobile manipulation planning is a hard problem composed of multiple challenging sub-problems, some of which require searching through large high-dimensional state-spaces. The focus of this work is on computing a trajectory to safely maneuver an object through an environment, given the start and goal configurations. In this work we present a heuristic search-based deterministic mobile manipulation planner, based on our recently-developed algorithm for planning with adaptive dimensionality. Our planner demonstrates reasonable performance, while also providing strong guarantees on completeness and suboptimality bounds with respect to the graph representing the problem.

Path planning quickly becomes computationally hard as the dimensionality of the state-space increases. In this paper, we present a planning algorithm intended to speed up path planning for high-dimensional state-spaces such as robotic arms. The idea behind this work is that while planning in a high-dimensional state-space is often necessary to ensure the feasibilityof the resulting path, large portions of the path have a lower-dimensional structure. Based on this observation, our algorithm iteratively constructs a state-space of an adaptive dimensionality--a state-space that is high-dimensional only where the higher dimensionality is absolutely necessary for finding a feasible path. This often reduces drastically the size of the state-space, and as a result, the planning time and memory requirements. Analytically, we show that our method is complete and is guaranteed to find a solution if one exists, within a specified suboptimality bound. Experimentally, we apply the approach to 3D vehicle navigation (x, y, heading), and to a 7 DOF robotic arm on the Willow Garage’s PR2 robot. The results from our experiments suggest that ourmethod can be substantially faster than some of the state-of-the-art planning algorithms optimized for those tasks.