|
|
|
|
Motion and Path Planning
|
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. |
|
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. |
|
Reciprocal Collision AvoidanceJur van den Berg, Stephen J. Guy, Ming C. Lin, and Dinesh Manocha We present techniques for fast and robust collision avoidance for multiple robots or agents moving around obstacles and amongst each other. ClearPath introduces the idea of formulating multi-agent collision avoidance as a convex optimization problem, and uses that to perform fast avoidance computation. ClearPath also exploits both data-level parallelism (SIMD) and thread-level parallelism. Optimal reciprocal collision avoidance (ORCA) is a formulation for collision avoidance using linear programming. ORCA provides guaranteed collision avoidance for multiple independent robots. |
|
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. |
|
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.
