Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “motion planning”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1998

Hybrid Motion Planning with Multiple Destinations

In our initial proposal, we laid plans for developing a hybrid motion planning system that combines the concepts of visibility-based motion planning, artificial potential field based motion planning, evolutionary constrained optimization, and reinforcement learning. Our goal was, and still is, to produce a hybrid motion planning system that outperforms the best traditional motion planning systems on problems with dynamic environments. The proposed hybrid system will be in two parts the first is a global motion planning system and the second is a local motion planning system. The global system will take global information about the environment, such as the placement of the obstacles and goals, and produce feasible paths through those obstacles. We envision a system that combines the evolutionary-based optimization and visibility-based motion planning to achieve this end.

Clouse, Jeffery↗
NASA NTRS1990

A unified motion planning approach for redundant and non-redundant manipulators with actuator constraints

The term trajectory planning has been used to refer to the process of determining the time history of joint trajectory of each joint variable corresponding to a specified trajectory of the end effector. The trajectory planning problem was solved as a purely kinematic problem. The drawback is that there is no guarantee that the actuators can deliver the effort necessary to track the planned trajectory. To overcome this limitation, a motion planning approach which addresses the kinematics, dynamics, and feedback control of a manipulator in a unified framework was developed. Actuator constraints are taken into account explicitly and a priori in the synthesis of the feedback control law. Therefore the result of applying the motion planning approach described is not only the determination of the entire set of joint trajectories but also a complete specification of the feedback control strategy which would yield these joint trajectories without violating actuator constraints. The effectiveness of the unified motion planning approach is demonstrated on two problems which are of practical interest in manipulator robotics.

Chung, Ching-Luan↗
NASA NTRS1995

Planning Motions To Avoid Moving Obstacles

Method of planning motions of object to prevent collisions with other moving objects derived from concept of collision cones in relative-velocity space. Collision cones computed, then maneuvers chosen to avoid these cones. Method considered prototype of automated method of planning motions in diverse applications, including complex manufacturing tasks involving coordination of multiple robots and controlling land, air, and sea traffic.

Fiorini, Paolo↗
NASA NTRS1997

Hybrid Co-Evolutionary Motion Planning via Visibility-Based Repair

This paper introduces a hybrid co-evolutionary system for global motion planning within unstructured environments. This system combines the concept of co-evolutionary search along with a concept that we refer to as the visibility-based repair to form a hybrid which quickly transforms infeasible motions into feasible ones. Also, this system makes use of a novel representation scheme for the obstacles within an environment. Our hybrid evolutionary system differs from other evolutionary motion planners in that (1) more emphasis is placed on repairing infeasible motions to develop feasible motions rather than using simulated evolution exclusively as a means of discovering feasible motions, (2) a continuous map of the environment is used rather than a discretized map, and (3) it develops global motion plans for multiple mobile destinations by co-evolving populations of sub-global motion plans. In this paper, we demonstrate the effectiveness of this system by using it to solve two challenging motion planning problems where multiple targets try to move away from a point robot.

Dozier, Gerry↗
NASA NTRS2020

Multi-Agent Motion Planning using Deep Learning for Space Applications

State-of-the-art motion planners cannot scale to a large number of systems. Motion planning for multiple agents is an NP (non-deterministic polynomial-time) hard problem, so the computation time increases exponentially with each addition of agents. This computational demand is a major stumbling block to the motion planner's application to future NASA missions involving the swarm of space vehicles. We applied a deep neural network to transform computationally demanding mathematical motion planning problems into deep learning-based numerical problems. We showed optimal motion trajectories can be accurately replicated using deep learning-based numerical models in several 2D and 3D systems with multiple agents. The deep learning-based numerical model demonstrates superior computational efficiency with plans generated 1000 times faster than the mathematical model counterpart.

Madani, Ramtin↗
NASA NTRS2017

Computationally Efficient Motion Planning Algorithms for Agile Autonomous Vehicles in Cluttered Environments

Fast, real-time motion planning of an agile, autonomous vehicle in a cluttered environment, with many geometrically-fixed obstacles, is a very complex problem, especially because of the vehicle dynamics constraints and resource constrained computational capabilities onboard the vehicle. In this paper, we present computationally-efficient versions of our novel motion planning algorithm called the Spherical Expansion and Sequential Convex Programming (SE–SCP) algorithm. The SE–SCP algorithm first uses a spherical-expansion-based randomized sampling algorithm to explore the workspace. Oncea path is found from the start position to the goal position, the algorithm computes a locally optimal trajectory, within its homotopy class for a desired cost function, by solving a sequence of convex optimization problems. Thus, the SE–SCP algorithm is anytime locally optimal and the trajectory is globally optimal if the number of samples tends to infinity. In this paper, we further enhance the computational efficiency of the SE–SCP algorithm using uni-directional and bi-directional rewiring techniques. We also present a detailed proof of the local optimality characteristics of the new SE–SCP algorithms for aspecial case of vehicle dynamics. Simulation examples involving quadrotor and spacecraft help demonstrate the effectiveness of our new algorithms.

Bandyopadhyay, Saptarshi↗
NASA NTRS2016

Fast, Safe, Propellant-Efficient Spacecraft Motion Planning Under Clohessy-Wiltshire-Hill Dynamics

This paper presents a sampling-based motion planning algorithm for real-time and propellant-optimized autonomous spacecraft trajectory generation in near-circular orbits. Specifically, this paper leverages recent algorithmic advances in the field of robot motion planning to the problem of impulsively actuated, propellant- optimized rendezvous and proximity operations under the Clohessy-Wiltshire-Hill dynamics model. The approach calls upon a modified version of the FMT* algorithm to grow a set of feasible trajectories over a deterministic, low-dispersion set of sample points covering the free state space. To enforce safety, the tree is only grown over the subset of actively safe samples, from which there exists a feasible one-burn collision-avoidance maneuver that can safely circularize the spacecraft orbit along its coasting arc under a given set of potential thruster failures. Key features of the proposed algorithm include 1) theoretical guarantees in terms of trajectory safety and performance, 2) amenability to real-time implementation, and 3) generality, in the sense that a large class of constraints can be handled directly. As a result, the proposed algorithm offers the potential for widespread application, ranging from on-orbit satellite servicing to orbital debris removal and autonomous inspection missions.

spacecraft relative motio↗
NASA NTRS1994

Very fast motion planning for highly dexterous-articulated robots

Due to the inherent danger of space exploration, the need for greater use of teleoperated and autonomous robotic systems in space-based applications has long been apparent. Autonomous and semi-autonomous robotic devices have been proposed for carrying out routine functions associated with scientific experiments aboard the shuttle and space station. Finally, research into the use of such devices for planetary exploration continues. To accomplish their assigned tasks, all such autonomous and semi-autonomous devices will require the ability to move themselves through space without hitting themselves or the objects which surround them. In space it is important to execute the necessary motions correctly when they are first attempted because repositioning is expensive in terms of both time and resources (e.g., fuel). Finally, such devices will have to function in a variety of different environments. Given these constraints, a means for fast motion planning to insure the correct movement of robotic devices would be ideal. Unfortunately, motion planning algorithms are rarely used in practice because of their computational complexity. Fast methods have been developed for detecting imminent collisions, but the more general problem of motion planning remains computationally intractable. However, in this paper we show how the use of multicomputers and appropriate parallel algorithms can substantially reduce the time required to synthesize paths for dexterous articulated robots with a large number of joints. We have developed a parallel formulation of the Randomized Path Planner proposed by Barraquand and Latombe. We have shown that our parallel formulation is capable of formulating plans in a few seconds or less on various parallel architectures including: the nCUBE2 multicomputer with up to 1024 processors (nCUBE2 is a registered trademark of the nCUBE corporation), and a network of workstations.

Challou, Daniel J.↗
NASA NTRS1988

Motion planning for a free-flying robot

An investigation is presented of motion planning combining low level control and obstacle avoidance for a free flying robot. This free flying robot is an outgrowth of the concept of an assistant for astronauts on the U.S. Space Station and Shuttle. A motion planner based on the Khatib potential field approach is described. Because of the uncluttered environment in space, it generates a path from representation of known obstacles rather than from a representation of free space. A global planner supplies the low level controller with interim points between the current position and the desired goal position so that the vehicle does not become trapped by local minima, a phenomenon of the potential field approach. Discussion of the feasibility of this system for space applications is presented.

Kaiser, Donald Leo↗
NASA NTRS1987

On Motion Planning and Control of Multi-Link Lightweight Robotic Manipulators

A general gross and fine motion planning and control strategy is needed for lightweight robotic manipulator applications such as painting, welding, material handling, surface finishing, and spacecraft servicing. The control problem of lightweight manipulators is to perform fast, accurate, and robust motions despite the payload variations, structural flexibility, and other environmental disturbances. Performance of the rigid manipulator model based computed torque and decoupled joint control methods are determined and simulated for the counterpart flexible manipulators. A counterpart flexible manipulator is defined as a manipulator which has structural flexibility, in addition to having the same inertial, geometric, and actuation properties of a given rigid manipulator. An adaptive model following control (AMFC) algorithm is developed to improve the performance in speed, accuracy, and robustness. It is found that the AMFC improves the speed performance by a factor of two over the conventional non-adaptive control methods for given accuracy requirements while proving to be more robust with respect to payload variations. Yet there are clear limitations on the performance of AMFC alone as well, which are imposed by the arm flexibility. In the search to further improve speed performance while providing a desired accuracy and robustness, a combined control strategy is developed. Furthermore, the problem of switching from one control structure to another during the motion and implementation aspects of combined control are discussed.

Cetinkunt, Sabri↗
NASA NTRS1995

Robot Motion Planning Among Moving Obstacles

An on-line method is presented for computing the motion of a robot in a dynamic environment subject to the robot dynamics and its actuator constraints. This method is based on the concept of Velocity Obstacle that defines the set of robot velocities that would result in a collision between the robot and a moving obstacle. The problem of motion planning in dynamic environments is addressed.

Robotics Velocity Obstacle↗
NASA NTRS2010

Probabilistic Motion Planning of Balloons in Strong, Uncertain Wind Fields

This paper introduces a new algorithm for probabilistic motion planning in arbitrary, uncertain vector fields, with emphasis on high-level planning for Montgolfiere balloons in the atmosphere of Titan. The goal of the algorithm is to determine what altitude--and what horizontal actuation, if any is available on the vehicle--to use to reach a goal location in the fastest expected time. The winds can vary greatly at different altitudes and are strong relative to any feasible horizontal actuation, so the incorporation of the winds is critical for guidance plans. This paper focuses on how to integrate the uncertainty of the wind field into the wind model and how to reach a goal location through the uncertain wind field, using a Markov decision process (MDP). The resulting probabilistic solutions enable more robust guidance plans and more thorough analysis of potential paths than existing methods.

Wolf, Michael T.↗
NASA NTRS2002

Human motion planning based on recursive dynamics and optimal control techniques

This paper presents an efficient optimal control and recursive dynamics-based computer animation system for simulating and controlling the motion of articulated figures. A quasi-Newton nonlinear programming technique (super-linear convergence) is implemented to solve minimum torque-based human motion-planning problems. The explicit analytical gradients needed in the dynamics are derived using a matrix exponential formulation and Lie algebra. Cubic spline functions are used to make the search space for an optimal solution finite. Based on our formulations, our method is well conditioned and robust, in addition to being computationally efficient. To better illustrate the efficiency of our method, we present results of natural looking and physically correct human motions for a variety of human motion tasks involving open and closed loop kinematic chains.

Non-NASA Center↗
NASA NTRS1992

Distance estimation and collision prediction for on-line robotic motion planning

An efficient method for computing the minimum distance and predicting collisions between moving objects is presented. This problem is incorporated into the framework of an in-line motion-planning algorithm to satisfy collision avoidance between a robot and moving objects modeled as convex polyhedra. In the beginning, the deterministic problem where the information about the objects is assumed to be certain is examined. L(1) or L(infinity) norms are used to represent distance and the problem becomes a linear programming problem. The stochastic problem is formulated where the uncertainty is induced by sensing and the unknown dynamics of the moving obstacles. Two problems are considered: First, filtering of the distance between the robot and the moving object at the present time. Second, prediction of the minimum distance in the future in order to predict the collision time.

Kyriakopoulos, K. J.↗
NASA NTRS1991

Distance estimation and collision prediction for on-line robotic motion planning

An efficient method for computing the minimum distance and predicting collisions between moving objects is presented. This problem has been incorporated in the framework of an in-line motion planning algorithm to satisfy collision avoidance between a robot and moving objects modeled as convex polyhedra. In the beginning the deterministic problem, where the information about the objects is assumed to be certain is examined. If instead of the Euclidean norm, L(sub 1) or L(sub infinity) norms are used to represent distance, the problem becomes a linear programming problem. The stochastic problem is formulated, where the uncertainty is induced by sensing and the unknown dynamics of the moving obstacles. Two problems are considered: (1) filtering of the minimum distance between the robot and the moving object, at the present time; and (2) prediction of the minimum distance in the future, in order to predict possible collisions with the moving obstacles and estimate the collision time.

Kyriakopoulos, K. J.↗
NASA NTRS2009

A Practical Comparison of Motion Planning Techniques for Robotic Legs in Environments with Obstacles

ATHLETE is a large six-legged tele-operated robot. Each foot is a wheel; travel can be achieved by walking, rolling, or some combination of the two. Operators control ATHLETE by selecting parameterized commands from a command dictionary. While rolling can be done efficiently, any motion involving steps is cumbersome - each step can require multiple commands and take many minutes to complete. In this paper, we consider four different algorithms that generate a sequence of commands to take a step. We consider a baseline heuristic, a randomized motion planning algorithm, and two variants of A* search. Results for a variety of terrains are presented, and we discuss the quantitative and qualitative tradeoffs between the approaches.

Smith, Tristan B.↗