Enabling Faster, More Capable Robots With Real-Time Motion Planning

IEEE Spectrum Robotics

This is a guest post. The views expressed here are solely those of the authors and do not represent positions of IEEE Spectrum or the IEEE. Despite decades of expectations that we will have dexterous robots performing sophisticated tasks in the house and elsewhere, the use of robots remains painfully limited, largely due to insufficient motion-planning performance. Motion planning is the process of determining how to move a robot, or autonomous vehicle, from its current configuration (or pose) to a desired goal configuration: For example, how to reach into a fridge to grab a soda can while avoiding obstacles, like the other items in the fridge and the fridge itself. Until recently, this critical process has been implemented in software running on high-performance commodity hardware.


Closing the Loop between Motion Planning and Task Execution Using Real-Time GPU-Based Planners

AAAI Conferences

Many task execution techniques tend to repeatedly invoke motion planning algorithms in order to perform complex tasks. In order to accelerate the perform of such methods, we present a real-time global motion planner that utilizes the computational capabilities of current many-core GPUs (graphics processing units). Our approach is based on randomized sample-based planners and we describe highly parallel algorithms to generate samples, perform collision queries, nearest-neighbor computations, local planning and graph search to compute collision-free paths for rigid robots. Our approach can efficiently solve the single-query and multiquery versions of the planning problem and can obtain one to two orders of speedup over prior CPU-based global planning algorithms. The resulting GPU-based planning algorithm can also be used for real-time feedback for task execution in challenging scenarios.


g-Planner: Real-time Motion Planning and Global Navigation using GPUs

AAAI Conferences

We present novel randomized algorithms for solving global motion planning problems that exploit the computational capabilities of many-core GPUs. Our approach uses thread and data parallelism to achieve high performance for all components of sample-based algorithms, including random sampling, nearest neighbor computation, local planning, collision queries and graph search. The approach can efficiently solve both the multi-query and single-query versions of the problem and obtain considerable speedups over prior CPU-based algorithms. We demonstrate the efficiency of our algorithms by applying them to a number of 6DOF planning benchmarks in 3D environments. Overall, this is the first algorithm that can perform real-time motion planning and global navigation using commodity hardware.


Cooperative, Dynamics-based, and Abstraction-Guided Multi-robot Motion Planning

Journal of Artificial Intelligence Research

This paper presents an effective, cooperative, and probabilistically-complete multi-robot motion planner that enables each robot to move to a desired location while avoiding collisions with obstacles and other robots. The approach takes into account not only the geometric constraints arising from collision avoidance, but also the differential constraints imposed by the motion dynamics of each robot. This makes it possible to generate collision-free and dynamically-feasible trajectories that can be executed in the physical world.The salient aspect of the approach is the coupling of sampling-based motion planning to handle the complexity arising from the obstacles and robot dynamics with multi-agent search to find solutions over a suitable discrete abstraction. The discrete abstraction is obtained by constructing roadmaps to solve a relaxed problem that accounts for the obstacles but not the dynamics. Sampling-based motion planning expands a motion tree in the composite state space of all the robots by adding collision-free and dynamically-feasible trajectories as branches. Efficiency is obtained by using multi-agent search to find non-conflicting routes over the discrete abstraction which serve as heuristics to guide the motion-tree expansion. When little or no progress is made, the routes are penalized and the multi-agent search is invoked again to find alternative routes. This synergistic coupling makes it possible to effectively plan collision-free and dynamically-feasible motions that enable each robot to reach its goal. Experiments using vehicle models with nonlinear dynamics operating in complex environments, where cooperation among robots is required, show significant speedups over related work.


Minimizing Conflicts Between Moving Agents over a Set of Non-Homotopic Paths Through Regret Minimization

AAAI Conferences

This paper considers a game-theoretic framework for motion coordination challenges. The focus of this work is to minimize the number of interactions agents have when moving through an environment. In particular, agents employ a replanning framework and regret minimization over a set of actions, which correspond to different homotopic paths. By associating a cost to each trajectory, a motion coordination game arises. Regret minimization is argued as an appropriate technique, as agents do not have any knowledge of other agents' cost functions. This work outlines a methodology for minimizing the regret of actions in a computationally efficient way. Initial simulation results involving pairs of mobile agents show indications that the proposed framework can improve the choice of non-colliding paths compared to a greedy choice by the agents, without increasing any information requirements.