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↗
DOE OSTI2023

Motion Planning Algorithms for Safety and Quantum Computing Efficiency

Motion planning remains a fundamental problem in robotics. Sampling-based algorithms use randomization to allow efficient solutions to this complex problem. As mobile robots and autonomous vehicles become more prevalent in everyday life, motion planning must be applied to increasingly challenging scenarios. Safety has become a paramount concern in motion planning for ensuring robotic applications enrich human lives. To date, many motion planning techniques to increase safety in the face of uncertain and dynamic environments have been developed. This dissertation first addresses distributional safety of Rapidly-Exploring Random Trees (RRT) through our algorithm W-Safe RRT. To acknowledge distributional uncertainty and poor modeling, W-Safe RRT uses the Wasserstein metric to provide a probabilistic bound on the distributional distance between a robot and obstacles. Human-interpretable environmental agent classification allows online safety margin adaptation. We propose and analyze an integrating region method for online classification that increases actor labeling accuracy based on behavioral feature values when compared to state of the art methods. The method performs class assignments based on local maximum likelihood in a created behavioral feature-space, allowing a notion of classification uncertainty. Model-based methods with safety guarantees can quickly become computationally in tractable, especially with multiple agents, higher dimensions, and plentiful unknowns. Sampling based algorithms have been parallelized for computation with multi-core computers and GPUs. We consider the use of quantum algorithms and computers for sampling-based motion planning for the first time. Quantum computing performs operations on superpositions of states and can solve certain problems much more efficiently than classical computers, but introduces previously unseen challenges. With Quantum-RRT, we recast the motion planning problem into a database-search structure and use Quantum Amplitude Amplification to find reachable states in the database with a quadratic performance increase over classical methods. We address two error sources with this method: quantum measurement and quantum oracle errors. We then extend this method to Parallel Quantum-RRT, which uses a manager-worker architecture with multiple parallel quantum workers to increase database search efficiency. We compare algorithm architectures and characterize probabilities of multiple workers finding solutions. Lastly, we test in simulation the quantum algorithms against classical versions in a wide variety of scenarios, concluding that a similar parallelization improvement is to be found in the quantum case as was found in the parallelization of classical RRT.

97 MATHEMATICS AND COMPUTING↗
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↗
DOE OSTI2022

Design and Closed‐Loop Motion Planning of an Untethered Swimming Soft Robot Using 2D Discrete Elastic Rods Simulations

Despite tremendous progress in the development of untethered soft robots in recent years, existing systems lack the mobility, model‐based control, and motion planning capabilities of their piecewise rigid counterparts. As in conventional robotic systems, the development of versatile locomotion of soft robots is aided by the integration of hardware design and control with modeling tools that account for their unique mechanics and environmental interactions. Here, a framework for physics‐based modeling, motion planning, and control of a fully untethered swimming soft robot is introduced. This framework enables offline co‐design in the simulation of robot parameters and gaits to produce effective open‐loop behaviors and enables closed‐loop planning over motion primitives for feedback control of a frog‐inspired soft robot testbed. This pipeline uses a discrete elastic rods (DERs) physics engine that discretizes the soft robot as many stretchable and bendable rods. On hardware, an untethered aquatic soft robot that performs frog‐like rowing behaviors is engineered. Hardware validation verifies that the simulation has sufficient accuracy to find the best candidates for sets of parameters offline. The simulator is then used to generate a trajectory library of the robot's motion in simulation that is used in real‐time closed‐loop path following experiments on hardware.

Huang, Xiaonan↗
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.↗
DOE OSTI2022

Multi-Sensor Optimal Motion Planning for Radiological Contamination Surveys by Using Prediction-Difference Maps

Distributed and networked mobile sensor platforms using unmanned aerial and/or ground vehicles to survey areas of interest offer a safer and more efficient method for radiological contamination mapping; however, most applications rely on uniformly sweeping of the area in a raster-type motion without utilizing the information available in a dynamic sense. We have developed a fully autonomous optimal motion planning procedure for networks with two or more mobile sensors. The procedure utilizes well-established concepts of Gaussian processes in combination with control laws based on centroidal Voronoi tessellations to achieve optimal next-iteration sensor movements. A new method of informing optimal motion planning is proposed, whereby the absolute difference between the prior and current full-map prediction, referred to as the prediction-difference map, is used as the spatial density function within each Voronoi cell, providing immediate and iterative feedback for dynamic use of available information. The Gaussian process regression model used to estimate the contamination in unvisited locations also provides prediction uncertainties, and can be used as a quantitative metric to assess the confidence in the calculated contamination map; these estimates and prediction uncertainties are unavailable for standard uniform survey routines as they can only produce maps in the vicinity of observed locations. We present through simulation the achievable performance gains from using this new method by directly comparing to a uniform survey method. Results show that using the prediction-difference maps to inform motion planning procedures offers a faster rate of producing an accurate and convergent map relative to a uniform survey route.

47 OTHER INSTRUMENTATION↗
DOE OSTI2020

Multi-agent motion planning with sporadic communications for collision avoidance

Here, a novel multi-vehicle motion planning and collision avoidance algorithm is proposed and analyzed. The algorithm aims to reduce the amount of onboard calculations and inter-agent communications needed for each vehicle to successfully navigate through an environment with static obstacles and reach their goals. To this end, each agent first calculates a path to the goal by means of an asymptotically optimal rapidly-exploring random tree (RRT*) with respect to the static obstacles. Then, other agents are treated as dynamic obstacles and potential collisions are determined by means of collision cones. Collision cones depend on the position and velocity from other agents and are grown conservatively between inter-agent communications. Based on the available information, each agent determines if a deconfliction maneuver is needed, if it can continue along its current path, or if communication is needed to make a decision about a conflict. With probability one, our algorithm guarantees that the agents keep from colliding with each other. Under an assumption on the existence of a solution for a vehicle to its goal, this algorithm also solves the planning problem with probability one. Simulations illustrate a group of agents successfully reaching their goal configurations and examine how the uncertainty affects the communication frequency of the multi-agent system.

33 ADVANCED PROPULSION SYSTEMS↗
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.↗