|
|
|
|
Motion and Path Planning
|
Efficient Local Planning Using Connection Collision QueryMin Tang, Young J. Kim, and Dinesh Manocha We introduce a novel proximity query, connection collision query (CCQ), and use it for efficient and exact local planning in sampling-based motion planners. Given two collision-free configurations, CCQ checks whether these configurations can be connected by a given continuous path that either lies completely in the free space or penetrates any obstacle by at most a given threshold. Our approach is general, robust, and can handle different continuous path formulations. We have integrated the CCQ algorithm with sampling-based motion planners and can perform reliable local planning queries with little performance degradation, as compared to prior methods. Moreover, the CCQ-based exact local planner is about an order of magnitude faster than prior exact local planning algorithms. |
|
Real-time Motion Planning and Global Navigation Using GPUsJia Pan, Christian Lauterbach, and Dinesh Manocha We present randomized algorithms for solving global motion planning problems that exploit the computational capabilities of many-core graphics processors (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 overall approach can efficiently solve both the multi-query and single-query versions of the problem and obtain considerable speedups over prior CPU-based algorithms. This is the first algorithm that can perform real-time motion planning and global navigation using commodity hardware. |
|
Constraint-based Motion Synthesis for Deformable ModelsWilliam Moss, Ming C. Lin, and Dinesh Manocha We present a goal-directed motion synthesis technique that integrates sample-based planning methods with constraint-based dynamics simulation using a finite element formulation to generate collision-free paths for a deformable model. Our method allows the user to quickly specify various constraints, including a desired trajectory as a sparse sequence of waypoints, and automatically computes a physically plausible path that satisfies geometric and physical constraints. |
|
Path Computation for Part DisassemblyLiangjun Zhang, Young J. Kim, and Dinesh Manocha We present an approach to computing a collision-free path for part disassembly simulation and virtual prototyping of part removal. Our algorithm is based on sample-based motion planning that connects collision-free samples in the configuration space using local planning. We describe techniques to generate samples in narrow passages and efficient local planning algorithms to connect them with collision-free paths. |
|
Retraction-based RRT PlannerLiangjun Zhang and Dinesh Manocha We present a optimization-based retraction algorithm to improve the performance of sample-based planners in narrow passages for three-dimensional rigid robots. The retraction step is formulated as an optimization problem using a distance metric in the configuration space. We use local contact analysis to compute samples near the boundary of C-obstacle and use those samples to improve the performance of rapidly-exploring random tree (RRT) planners in narrow passages. |
|
Complete Motion PlanningLiangjun Zhang, Gokul Varadhan, Young J. Kim, Shankar Krishnan, and Dinesh Manocha We present efficient and practical algorithms for complete motion planning. A complete motion planner either computes a collision-free path from the initial configuration to the final configuration or concludes that no such path exists. |
|
Physics-based Motion PlanningRussell Gayle, Ming C. Lin, and Dinesh Manocha We propose a physics-based motion planning (PMP) approach to motion planning. PMP relies upon motion equations and robot control in order to find a path. The resulting path obeys kinematic and dynamics constraints while also finding a goal; something that configuration-space randomized planners cannot accomplish. Furthermore, motion equations need not be restricted to the robot. The paths or roadmaps themselves can also be controlled in a physically plausible manner to ensure a collision-free path in a dynamic environment. |
|
Local Planning in the Contact SpaceStephane Redon and Ming C. Lin We present a local planning method in contact-space which uses continuous collision detection (CCD). We use the precise contact information provided by a CCD algorithm to enhance a randomized planner by efficiently sampling the contact-space, as well as by constraining the sampling when the roadmap is expanded. |
|
Constraint-based Motion Planning of Deformable RobotsRussell Gayle, Ming C. Lin, and Dinesh Manocha We present a algorithm for motion planning of a deformable robot in a static environment. Our algorithm computes an approximate path using the probabilistic roadmap method (PRM). We use constraint-based planning to simulate robot deformation and make appropriate path adjustments and corrections to compute a collision-free path. Our PRM algorithm takes into account geometric constraints, like non-penetration, and physical constraints, like volume preservation. |
|
Path Planning for Deformable RobotsRussell Gayle, Ming C. Lin, and Dinesh Manocha We present an algorithm for path planning for a flexible robot in complex environments. Our algorithm computes a collision-free path by taking into account geometric and physical constraints, including obstacle avoidance, non-penetration, volume preservation, surface tension, and energy minimization. |
|
Interactive Navigation Using Path PlanningBrian Salomon, Maxim Garber, Ming C. Lin, and Dinesh Manocha We have developed a system for navigation of massive environments using path planning. Our system provides the user with a local driving mode that keeps an avatar constrained to walkable surfaces in the model and a global path planner. Arbitrary configurations are specified by the user and a preprocessed graph is searched for a path between the configurations. The graph is generated using an algorithm based on the visibility probabilistic roadmap (PRM) technique and the runtime path following uses the local driving mode to move the user along the path. |
|
Constraint-based Motion Planning for Virtual PrototypingMaxim Garber and Ming C. Lin We present a framework for motion planning of rigid and articulated robots in complex, dynamic, three-dimensional environments and demonstrate its application to virtual prototyping. It is based on transforming the motion planning problem into the simulation of a dynamical system. Motion of each rigid robot is subject to virtual forces induced by all types of geometric constraints. The resulting algorithm uses all contributing forces to move the robot along the estimated path, while avoiding collision with obstacles and enforcing joint and positional constraints. |
|
Voronoi-based Hybrid Motion PlannerMark Foskey, Maxim Garber, Ming C. Lin, and Dinesh Manocha We present a hybrid path planning algorithm for rigid and articulated bodies translating and rotating in three-dimensional workspace. We compute a Voronoi roadmap in the workspace from a discrete approximation to the generalized Voronoi diagram (GVD) and combine it with bridges computed by a randomized path planner with Voronoi-biased sampling. |
|
Randomized Path PlanningCharles Pisula, Kenneth E. Hoff III, Ming C. Lin, and Dinesh Manocha We present algorithms for sampling near the medial axis and building roadmap graphs for a free-flying rigid body. We initially compute a bounded-error discrete Voronoi diagram of the obstacles in the workspace and use it to generate samples in the free space and use multi-level connection strategies and local planning algorithms to generate roadmap graphs. We also utilize the distance information provided by our Voronoi algorithm for fast proximity queries and sampling the configurations. |
|
Motion Planning Using Generalized Voronoi DiagramsKenneth E. Hoff III, Timothy Culver, John Keyser, Ming C. Lin, and Dinesh Manocha We present techniques for fast motion planning by using discrete approximations of the generalized Voronoi diagram (GVD) computed with graphics hardware. Approaches based on the GVD computation are applicable to both static and dynamic environments of fairly high complexity. The computation of the GVD provides fast proximity query toolkits for motion planning. |
|
Reciprocal Collision Avoidance with Acceleration-velocity ObstaclesJur van den Berg, Jamie Snape, Stephen J. Guy, and Dinesh Manocha We present an approach for collision avoidance for mobile robots that takes into account acceleration constraints. We discuss both the case of navigating a single robot among moving obstacles, and the case of multiple robots reciprocally avoiding collisions with each other while navigating a common workspace. Inspired by the concept of velocity obstacles, we introduce the acceleration-velocity obstacle (AVO) to let a robot avoid collisions with moving obstacles while obeying acceleration constraints. AVO characterizes the set of new velocities the robot can safely reach and adopt using proportional control of the acceleration. We extend this concept to reciprocal collision avoidance for multi-robot settings, by letting each robot take half of the responsibility of avoiding pairwise collisions. Our formulation guarantees collision-free navigation even as the robots act independently and simultaneously, without coordination. Our approach is designed for holonomic robots, but can also be applied to kinematically constrained non-holonomic robots such as cars. We have implemented our approach, and we show simulation results in challenging environments with large numbers of robots and obstacles. |
|
Smooth Navigation for Multiple Differential-drive RobotsJamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha We present a method for smooth and collision-free navigation for multiple independent robots under differential-drive constraints. Our algorithm is based on the optimal reciprocal collision avoidance (ORCA) formulation and guarantees both smoothness in the trajectories of the robots and locally collision-free paths. We provide proofs of these guarantees and demonstrate the effectiveness of our method in experimental scenarios using iRobot Create mobile robots navigating amongst each other. |
|
Navigating Multiple Simple-airplanes in 3D WorkspaceJamie Snape and Dinesh Manocha We consider the problem of collision-free navigation of multiple flying robots in 3D workspace. Our approach extends a simple car to a simple-airplane, with constraints on speed, steering angle, and change in altitude. Our algorithm uses optimal reciprocal collision avoidance (ORCA) to independently compute a local trajectory without collisions or oscillations for each simple-airplane. We consider kinematic and dynamic constraints and use variable reciprocity when choosing velocities to ensure less-constrained simple-airplanes take more responsibility for avoiding collisions. |
|
Independent Navigation of Multiple Mobile RobotsJamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha We present the hybrid reciprocal velocity obstacle (HRVO) for smooth and collision-free navigation of multiple independent mobile robots amongst each other. We build on prior work related to the velocity obstacle (VO) and reciprocal velocity obstacle (RVO) concepts and introduce HRVO for collision avoidance that takes into account the kinematics of each robot and uncertainty in sensor data. |
|
Generalized Velocity ObstaclesDavid Wilkie, Jur van den Berg, and Dinesh Manocha We address the problem of real-time navigation in dynamic environments for car-like robots. The generalized velocity obstacle (GVO) adapts the velocity obstacle (VO) concept to take into account the constraints of a car-like robot. We use the GVO formulation to find controls that will allow collision-free navigation in a dynamic environment. |
|
Optimal Reciprocal Collision AvoidanceJur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and Dinesh Manocha We present a formal approach to reciprocal collision avoidance, where multiple independent mobile robots or agents need to avoid collisions with each other without communication among agents while moving in a common workspace. Our formulation, optimal reciprocal collision avoidance (ORCA), provides sufficient conditions for collision-free motion by letting each agent take half of the responsibility of avoiding pairwise collisions. Selecting the optimal action for each agent is reduced to solving a low-dimensional linear program, and we prove that the resulting motions are smooth. We test our ORCA approach on a team of iRobot Create differential-drive mobile robots, as well as on several dense and complex simulation scenarios in both 2D and 3D workspaces involving thousands of agents, and compute collision-free actions for all of them in only a few milliseconds. |
|
Coordination Using Generalized Social Potential FieldsRussell Gayle, William Moss, Ming C. Lin, and Dinesh Manocha We present a approach to compute collision-free paths for multiple robots subject to local coordination constraints. Our approach generalizes the social potential field method to be applicable to both convex and non-convex polyhedra. Social potential fields are then integrated into a physics-based motion planning framework which uses constrained dynamics to solve the motion planning problem. |
|
Reciprocal Velocity ObstaclesJur van den Berg, Ming C. Lin, and Dinesh Manocha We propose the reciprocal velocity obstacle (RVO) concept for real-time multi-agent navigation in which each agent navigates independently without explicit communication with other agents. RVO is an extension of the velocity obstacle (VO) that takes into account the reactive behavior of the other agents by implicitly assuming that they make similar collision-avoidance reasoning. RVO guarantees safe and oscillation-free motions for each of the agents. |
|
Reactive Deforming RoadmapsRussell Gayle, Avneesh Sud, Ming C. Lin, and Dinesh Manocha We present a algorithm for motion planning of multiple robots amongst dynamic obstacles. The reactive deforming roadmap (RDR) uses deformable links and dynamically retracts to capture the connectivity of the free space. We use Newtonian physics and Hooke's law to update the position of the milestones and deform the links in response to the motion of other robots and the obstacles. |
|
Synthesizing Human Motion in Constrained EnvironmentsJia Pan, Liangjun Zhang, Ming C. Lin, and Dinesh Manocha We present an algorithm to synthesize plausible motions for high-degree-of-freedom human-like articulated figures in constrained environments with multiple obstacles. Our approach is general and makes no assumptions about the articulated model or the environment. |
|
Motion Planning of Human-like RobotsLiangjun Zhang, Jia Pan, and Dinesh Manocha We present a whole-body motion planning algorithm for human-like robots. The planning problem is decomposed into a sequence of low-dimensional subproblems. Our formulation is based on the fact that a human-like model is a tightly-coupled system and uses a constrained coordination scheme to solve the subproblems in an incremental manner. |
|
Principal InvestigatorsResearch Sponsors |
Current MembersPast Members
|
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
