Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Path 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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS1993

Path planning for robotic truss assembly

A new Potential Fields approach to the robotic path planning problem is proposed and implemented. Our approach, which is based on one originally proposed by Munger, computes an incremental joint vector based upon attraction to a goal and repulsion from obstacles. By repetitively adding and computing these 'steps', it is hoped (but not guaranteed) that the robot will reach its goal. An attractive force exerted by the goal is found by solving for the the minimum norm solution to the linear Jacobian equation. A repulsive force between obstacles and the robot's links is used to avoid collisions. Its magnitude is inversely proportional to the distance. Together, these forces make the goal the global minimum potential point, but local minima can stop the robot from ever reaching that point. Our approach improves on a basic, potential field paradigm developed by Munger by using an active, adaptive field - what we will call a 'flexible' potential field. Active fields are stronger when objects move towards one another and weaker when they move apart. An adaptive field's strength is individually tailored to be just strong enough to avoid any collision. In addition to the local planner, a global planning algorithm helps the planner to avoid local field minima by providing subgoals. These subgoals are based on the obstacles which caused the local planner to fail. A best-first search algorithm A* is used for graph search.

Sanderson, Arthur C.↗
NASA NTRS2019

Real-Time Path Planning for Multi-copters flying in UTM -TCL4

NASA's UAS Traffic management (UTM) -TCL-4 focuses on safely enabling large scale small UAS oper- ations in low altitude airspace in dense urban regions. This paper presents an operational architecture of an autonomous unmanned aerial vehicle operating in TCL4. An on-line path planning scheme is proposed which can effectively plan for feasible paths in real time with TCL-4 constraints. An end to end system is designed and tested in high fidelity Reflection architecture which demonstrates the feasibility of the approach.

Chakrabarty, Anjan↗
NASA NTRS1992

Robot path planning for space-truss assembly

Construction, repair, and maintenance of space-based structures will require extensive planning of operations in order to effectively carry out these tasks. The path planning algorithm described here is a general approach to generating paths that guarantee collision avoidance for a single chain nonredundant or redundant robot. The algorithm uses a graph search of feasible points in position space, followed by a local potential field method that guarantees collision avoidance among objects, structures, and the robot arm as well as conformance to joint limit constraints. This algorithm is novel in its computation of goal attractive potential fields in Cartesian space, and computation of obstacle repulsive fields in robot joint space. These effects are combined to generate robot motion. Computation is efficiently implemented through the computation of the robot arm Jacobian and not the full inverse arm kinematics. These planning algorithms have been implemented and evaluated using existing space-truss designs, and are being integrated into the RPI-CIRSSE Testbed environment.

Muenger, Rolf↗
NASA NTRS1989

Kinematics, controls, and path planning results for a redundant manipulator

The inverse kinematics solution, a modal position control algorithm, and path planning results for a 7 degree of freedom manipulator are presented. The redundant arm consists of two links with shoulder and elbow joints and a spherical wrist. The inverse kinematics problem for tip position is solved and the redundant joint is identified. It is also shown that a locus of tip positions exists in which there are kinematic limitations on self-motion. A computationally simple modal position control algorithm has been developed which guarantees a nearly constant closed-loop dynamic response throughout the workspace. If all closed-loop poles are assigned to the same location, the algorithm can be implemented with very little computation. To further reduce the required computation, the modal gains are updated only at discrete time intervals. Criteria are developed for the frequency of these updates. For commanding manipulator movements, a 5th-order spline which minimizes jerk provides a smooth tip-space path. Schemes for deriving a corresponding joint-space trajectory are discussed. Modifying the trajectory to avoid joint torque saturation when a tip payload is added is also considered. Simulation results are presented.

Gretz, Bruce↗
NASA NTRS1998

Multiobjective Evolutionary Path Planning via Sugeno-Based Tournament Selection

This paper introduces a new tournament selection algorithm that can be used for evolutionary path planning systems. The fuzzy (Sugeno) tournament selection algorithm (STSA) described in this paper selects candidate paths (CPs) to be parents and undergo reproduction based on: (1) path feasibility, (2) the euclidean distance of a path from the origin to its destination, and (3) the average change in the slope of a path. In this paper, we provide a detailed description of the fuzzy inference system used in the STSA as well as some examples of its usefulness. We then use 12 instances of our STSA to rank a population of CPs based on the above criteria. We also show how the STSA can obviate the need for the development of an explicit (lexicographic multiobjective) evaluation function and use it to develop multiobjective motion paths.

Dozier, Gerry↗
NASA NTRSDate not supplied

Formal Verification, Distributed Computing, and Path Planning Algorithms

The safety- and mission-critical nature of much of the work done at NASA requires algorithms and software to be exceedingly reliable. Formal methods techniques are one way of ensuring this high level of robustness. This talk will discuss the development and formal verification of autonomous aircraft path planning algorithms related to the Bellman-Ford shortest path algorithm, including consideration of distributed computation of the algorithm.

Formal Methods↗
NASA NTRS2019

Scheduling and Airport Taxiway Path Planning Under Uncertainty

Congestion and uncertainty on the airport surface are major constraints to the available capacity of the air transport system. This project is to study the problem of planning and scheduling airport surface movement at large airports. Specifically, we focus on the departure time scheduling and taxiway path planning of multiple aircraft under uncertainty. We also developed a simulation tool that is capable of simulating aircraft movement along the taxiway and possible uncertainty during the movement.

Li, Jiaoyang↗
NASA NTRS1987

Task path planning, scheduling and learning for free-ranging robot systems

The development of robotics applications for space operations is often restricted by the limited movement available to guided robots. Free ranging robots can offer greater flexibility than physically guided robots in these applications. Presented here is an object oriented approach to path planning and task scheduling for free-ranging robots that allows the dynamic determination of paths based on the current environment. The system also provides task learning for repetitive jobs. This approach provides a basis for the design of free-ranging robot systems which are adaptable to various environments and tasks.

Wakefield, G. Steve↗
NASA NTRS1987

The use of 3-D sensing techniques for on-line collision-free path planning

The state of the art in collision prevention for manipulators with revolute joints, showing that it is a particularly computationally hard problem, is discussed. Based on the analogy with other hard or undecidable problems such as theorem proving, an extensible multi-resolution architecture for path planning, based on a collection of weak methods is proposed. Finally, the role that sensors can play for an on-line use of sensor data is examined.

Hayward, V.↗
NASA NTRS1999

Long Range Navigation for Mars Rovers Using Sensor-Based Path Planning and Visual Localisation

The Mars Pathfinder mission illustrated the benefits of including a mobile robotic explorer on a planetary mission. However, for future Mars rover missions, significantly increased autonomy in navigation is required in order to meet demanding mission criteria. To address these requirements, we have developed new path planning and localisation capabilities that allow a rover to navigate robustly to a distant landmark. These algorithms have been implemented on the JPL Rocky 7 prototype microrover and have been tested extensively in the JPL MarsYard, as well as in natural terrain.

Laubach, Sharon L.↗
NASA NTRS2022

Dynamic Path Planning Automation Concept for Advanced Air Mobility

Advanced Air Mobility (AAM) aims to develop an air transportation system for novel air vehicles between local, regional, intraregional, and urban places. Safety and efficiency of increasingly complex AAM operations are expected to require extensive use of automation, ranging from controlling the revolutionary new aircraft to managing flights dynamically in the high tempo airspace and aerodrome operations. Both onboard and ground automation will play central roles in assisting AAM operators with managing the flight paths of their fleet. This document presents a concept for dynamic path planning (DPP) automation applicable to AAM and other flight operations. The role of the DPP automation system is fivefold: (1) it creates a flight path with desired qualities of being feasible, deconflicted, harmonized, flexible, and optimal; (2) it monitors the progress of flight in a dynamic operating environment; (3) it supports the user in evaluating continued acceptability of the flight path in changing conditions; (4) it revises the flight path as needed to maintain the desired flight path qualities; and (5) it coordinates the flight path with airspace users and service providers. Key users of the DPP automation system include flight planners, pilots, and airspace service providers The concept allows for the system to be installed onboard the aircraft as well as on the ground. The system responds automatically to the dynamic operating environment to ensure that a safe and operationally acceptable flight path is available throughout the flight.

Vivek Sharma↗
NASA NTRS1989

Enroute flight-path planning - Cooperative performance of flight crews and knowledge-based systems

Interface design issues associated with the introduction of knowledge-based systems into the cockpit are discussed. Such issues include not only questions about display and control design, they also include deeper system design issues such as questions about the alternative roles and responsibilities of the flight crew and the computer system. In addition, the feasibility of using enroute flight path planning as a context for exploring such research questions is considered. In particular, the development of a prototyping shell that allows rapid design and study of alternative interfaces and system designs is discussed.

Smith, Philip J.↗
NASA NTRS2020

Navigation on the Line: Traversability Analysis and Path Planning for Extreme-Terrain Rappelling Rovers

Many areas of scientific interest in planetaryexploration, such as lunar pits, icy-moon crevasses, and Martiancraters, are inaccessible to current wheeled rovers. Rappellingrovers can safely traverse these steep surfaces, but requiretechniques to navigate their complex terrain. This dynamicnavigation is inherently time-critical and communication constraints(e.g. delays and small communication windows) willrequire planetary systems to have some autonomy.Autonomous navigation for Martian rovers is well studiedon moderately sloped and locally planar surfaces, but thesemethods do not readily transfer to tethered systems in nonplanar3D environments. Rappelling rovers in these situationshave additional challenges, including terrain-tether interactionand its effects on rover stability, path planning and control.This paper presents novel traversability analysis and pathplanning algorithms for rappelling rovers operating on steepterrains that account for terrain-tether interaction and theunique stability and reachability constraints of a rapellingsystem. The system is evaluated with a series of simulations andan analogue mission. In simulation, the planner was shown toreliably find safe paths down a 55 degree slope when a stabletether-terrain configuration exists and never recommended anunsafe path when one did not. In a planetary analogue mission,elements of the system were used to autonomously navigateAxel, a JPL rappelling rover, down a 30 degree slope with95% autonomy by distance travelled over 46 meters.

Nesnas, Issa↗
DOE OSTI2024

Efficient generation of grids and traversal graphs in compositional spaces towards exploration and path planning

Abstract Diverse disciplines across science and engineering deal with problems related to compositions, which exist in non-Euclidean simplex spaces, rendering many standard tools inaccurate or inefficient. This work explores such spaces conceptually in the context of materials discovery, quantifies their computational feasibility, and implements several essential methods specific to simplex spaces through a new high-performance open-source library . Most significantly, we derive and implement an algorithm for constructing a novel n-dimensional simplex graph data structure, containing all discretized compositions and possible neighbor-to-neighbor transitions. Critically, no distance or neighborhood calculations are performed, instead leveraging pure combinatorics and order in procedurally generated simplex grids, keeping the algorithm $${\mathcal{O}}(N)$$ O ( N ) , with minimal memory, enabling rapid construction of graphs with billions of transitions in seconds. Additionally, we demonstrate how such graph representations can be combined to homogeneously express complex path-planning problems, while facilitating efficient deployment of existing high-performance gradient descent, graph traversal, and other optimization algorithms.

Krajewski, Adam M. (ORCID:0000000222660099)↗
NASA NTRS2022

A Unifying View of Estimation and Control Using Belief Propagation With Application to Path Planning

The use of estimation techniques on stochastic models to solve control problems is an emerging paradigm that falls under the rubric of Active Inference (AI) and Control as Inference (CAI). In this work, we use probability propagation on factor graphs to show that various algorithms proposed in the literature can be seen as specific composition rules in a factor graph. We show how this unified approach, presented both in probability space and in log of the probability space, provides a very general framework that includes the Sum-product, the Max-product, Dynamic programming and mixed Reward/Entropy criteria-based algorithms. The framework also expands algorithmic design options that lead to new smoother or sharper policy distributions. We propose original recursions such as: a generalized Sum/Max-product algorithm, a Smooth Dynamic programming algorithm and a modified versions of the Reward/Entropy algorithm. The discussion is carried over with reference to a path planning problem where the recursions that arise from various cost functions, although they may appear similar in scope, bear noticeable differences. We provide a comprehensive table of composition rules and a comparison through simulations, first on a synthetic small grid with a single goal with obstacles, and then on a grid extrapolated from a real-world scene with multiple goals and a semantic map.

Francesco A. N. Palmieri↗
NASA NTRS1994

Automated path planning of the Payload Inspection and Processing System

The Payload Changeout Room Inspection and Processing System (PIPS) is a highly redundant manipulator intended for performing tasks in the crowded and sensitive environment of the Space Shuttle Orbiter payload bay. Its dexterity will be exploited to maneuver the end effector in a workspace populated with obstacles. A method is described by which the end effector of a highly redundant manipulator is directed toward a target via a Lyapunov stability function. A cost function is constructed which represents the distance from the manipulator links to obstacles. Obstacles are avoided by causing the vector of joint parameters to move orthogonally to the gradient of the workspace cost function. A C language program implements the algorithm to generate a joint history. The resulting motion is graphically displayed using the Interactive Graphical Robot Instruction Program (IGRIP) produced by Deneb Robotics. The graphical simulation has the potential to be a useful tool in path planning for the PIPS in the Shuttle Payload Bay environment.

Byers, Robert M.↗
NASA NTRS2011

Dynamic Modeling and Soil Mechanics for Path Planning of the Mars Exploration Rovers

To help minimize risk of high sinkage and slippage during drives and to better understand soil properties and rover terramechanics from drive data, a multidisciplinary team was formed under the Mars Exploration Rover (MER) project to develop and utilize dynamic computer-based models for rover drives over realistic terrains. The resulting tool, named ARTEMIS (Adams-based Rover Terramechanics and Mobility Interaction Simulator), consists of the dynamic model, a library of terramechanics subroutines, and the high-resolution digital elevation maps of the Mars surface. A 200-element model of the rovers was developed and validated for drop tests before launch, using MSC-Adams dynamic modeling software. Newly modeled terrain-rover interactions include the rut-formation effect of deformable soils, using the classical Bekker-Wong implementation of compaction resistances and bull-dozing effects. The paper presents the details and implementation of the model with two case studies based on actual MER telemetry data. In its final form, ARTEMIS will be used in a predictive manner to assess terrain navigability and will become part of the overall effort in path planning and navigation for both Martian and lunar rovers.

terramechanics↗
NASA NTRS2007

Improved Path Planning Onboard the Mars Exploration Rovers

A revised version of the AutoNav (autonomous navigation with hazard avoidance) software running onboard each Mars Exploration Rover (MER) affords better obstacle avoidance than does the previous version. Both versions include GESTALT (Grid-based Estimation of Surface Traversability Applied to Local Terrain), a navigation program that generates local-terrain models from stereoscopic image pairs captured by onboard rover cameras; uses this information to evaluate candidate arcs that extend across the terrain from the current rover location; ranks the arcs with respect to hazard avoidance, minimization of steering time, and the direction towards the goal; and combines the rankings in a weighted vote to select an arc, along which the rover is then driven. GESTALT works well in navigating around small isolated obstacles, but tends to fail when the goal is on the other side of a large obstacle or multiple closely spaced small obstacles. When that occurs, the goal seeking votes and hazard avoidance votes conflict severely. The hazard avoidance votes will not allow the rover to drive through the unsafe area, and the waypoint votes will not allow enough deviation from the straight-line path for the rover to get around the hazard. The rover becomes stuck and is unable to reach the goal. The revised version of AutoNav utilizes a global path-planning program, Field D*, to evaluate the cost of traveling from the end of each GESTALT arc to the goal. In the voting process, Field D* arc votes supplant GESTALT goal-seeking arc votes. Hazard avoidance, steering bias, and Field D* votes are merged and the rover is driven a preset distance along the arc with the highest vote. Then new images are acquired and the process as described is repeated until the goal is reached. This new technology allows the rovers to autonomously navigate around much more complex obstacle arrangements than was previously possible. In addition, this improved autonomy enables longer traverses per Sol (a day on Mars), and can make planning drives easier for operators on Earth.

Stentz, Anthony↗