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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRSDate not supplied

A High-Performance Computing GNSS-aware Path Planning Algorithm for Safe Urban Flight Operations

The emergence and development of advanced technologies and vehicle types have created a growing demand for new forms of flight operations. These new and increasingly complex operational paradigms, such as Advanced and Urban Air Mobility (AAM/UAM), present regulatory authorities and the aviation community with several design-and-implementation challenges – particularly for highly autonomous vehicles. An overarching and daunting task is to develop protocols that can integrate these operations without compromising safety or disrupting traditional airspace operations. A shift toward a more predictive, autonomous, risk mitigation capability becomes critical to meet this challenge. This paper proposes and evaluates a computationally-efficient path planning approach to perform pre-flight planning and autonomous in-flight re-routing to minimize exposures to selected hazards. In our evaluation, hazards associated with degraded and missing critical GPS navigation data are considered. In this paper, we first present a high-performance computing path planning approach based on an adapted Bellman-Ford algorithm, developed in the CUDA programming language. Using the adapted path planning algorithm, we test this algorithm when encountering issues with GPS quality, and deliver an implementation that can produce flight paths that minimize exposure to risks, while maintaining a low computational burden. In our evaluation, the computation of periodic and aperiodic path updates are evaluated, prioritizing specific events as triggers for updates, based on changes to satellite availability. These critical events can lead to significant exposure to navigational hazards if not dealt with correctly.

GNSS↗
NASA NTRS1998

Planning Paths Through Singularities in the Center of Mass Space

The center of mass space is a convenient space for planning motions that minimize reaction forces at the robot's base or optimize the stability of a mechanism. A unique problem associated with path planning in the center of mass space is the potential existence of multiple center of mass images for a single Cartesian obstacle, since a single center of mass location can correspond to multiple robot joint configurations. The existence of multiple images results in a need to either maintain multiple center of mass obstacle maps or to update obstacle locations when the robot passes through a singularity, such as when it moves from an elbow-up to an elbow-down configuration. To illustrate the concepts presented in this paper, a path is planned for an example task requiring motion through multiple center of mass space maps. The object of the path planning algorithm is to locate the bang- bang acceleration profile that minimizes the robot's base reactions in the presence of a single Cartesian obstacle. To simplify the presentation, only non-redundant robots are considered and joint non-linearities are neglected.

Doggett, William R.↗
NASA NTRS1993

Fuzzy logic path planning system for collision avoidance by an autonomous rover vehicle

The Space Exploration Initiative of the United States will make great demands upon NASA and its limited resources. One aspect of great importance will be providing for autonomous (unmanned) operation of vehicles and/or subsystems in space flight and surface exploration. An additional, complicating factor is that much of the need for autonomy of operation will take place under conditions of great uncertainty or ambiguity. Issues in developing an autonomous collision avoidance subsystem within a path planning system for application in a remote, hostile environment that does not lend itself well to remote manipulation by Earth-based telecommunications is addressed. A good focus is unmanned surface exploration of Mars. The uncertainties involved indicate that robust approaches such as fuzzy logic control are particularly appropriate. Four major issues addressed are (1) avoidance of a fuzzy moving obstacle; (2) backoff from a deadend in a static obstacle environment; (3) fusion of sensor data to detect obstacles; and (4) options for adaptive learning in a path planning system. Examples of the need for collision avoidance by an autonomous rover vehicle on the surface of Mars with a moving obstacle would be wind-blown debris, surface flow or anomalies due to subsurface disturbances, another vehicle, etc. The other issues of backoff, sensor fusion, and adaptive learning are important in the overall path planning system.

Murphy, Michael G.↗
NASA NTRS2009

A Comparison of Risk Sensitive Path Planning Methods for Aircraft Emergency Landing

Determining the best site to land a damaged aircraft presents some interesting challenges for standard path planning techniques. There are multiple possible locations to consider, the space is 3-dimensional with dynamics, the criteria for a good path is determined by overall risk rather than distance or time, and optimization really matters, since an improved path corresponds to greater expected survival rate. We have investigated a number of different path planning methods for solving this problem, including cell decomposition, visibility graphs, probabilistic road maps (PRMs), and local search techniques. In their pure form, none of these techniques have proven to be entirely satisfactory - some are too slow or unpredictable, some produce highly non-optimal paths or do not find certain types of paths, and some do not cope well with the dynamic constraints when controllability is limited. In the end, we are converging towards a hybrid technique that involves seeding a roadmap with a layered visibility graph, using PRM to extend that roadmap, and using local search to further optimize the resulting paths. We describe the techniques we have investigated, report on our experiments with these techniques, and discuss when and why various techniques were unsatisfactory.

Meuleau, Nicolas↗
NASA NTRS2005

Path Planning Algorithms for the Adaptive Sensor Fleet

The Adaptive Sensor Fleet (ASF) is a general purpose fleet management and planning system being developed by NASA in coordination with NOAA. The current mission of ASF is to provide the capability for autonomous cooperative survey and sampling of dynamic oceanographic phenomena such as current systems and algae blooms. Each ASF vessel is a software model that represents a real world platform that carries a variety of sensors. The OASIS platform will provide the first physical vessel, outfitted with the systems and payloads necessary to execute the oceanographic observations described in this paper. The ASF architecture is being designed for extensibility to accommodate heterogenous fleet elements, and is not limited to using the OASIS platform to acquire data. This paper describes the path planning algorithms developed for the acquisition phase of a typical ASF task. Given a polygonal target region to be surveyed, the region is subdivided according to the number of vessels in the fleet. The subdivision algorithm seeks a solution in which all subregions have equal area and minimum mean radius. Once the subregions are defined, a dynamic programming method is used to find a minimum-time path for each vessel from its initial position to its assigned region. This path plan includes the effects of water currents as well as avoidance of known obstacles. A fleet-level planning algorithm then shuffles the individual vessel assignments to find the overall solution which puts all vessels in their assigned regions in the minimum time. This shuffle algorithm may be described as a process of elimination on the sorted list of permutations of a cost matrix. All these path planning algorithms are facilitated by discretizing the region of interest onto a hexagonal tiling.

Stoneking, Eric↗
NASA NTRS1988

Mobile transporter path planning using a genetic algorithm approach

The use of an optimization technique known as a genetic algorithm for solving the mobile transporter path planning problem is investigated. The mobile transporter is a traveling robotic vehicle proposed for the Space Station which must be able to reach any point of the structure autonomously. Specific elements of the genetic algorithm are explored in both a theoretical and experimental sense. Recent developments in genetic algorithm theory are shown to be particularly effective in a path planning problem domain, though problem areas can be cited which require more research. However, trajectory planning problems are common in space systems and the genetic algorithm provides an attractive alternative to the classical techniques used to solve these problems.

Baffes, Paul↗
NASA NTRS1991

Path planning for assembly of strut-based structures

A path planning method with collision avoidance for a general single chain nonredundant or redundant robot is proposed. Joint range boundary overruns are also avoided. The result is a sequence of joint vectors which are passed to a trajectory planner. A potential field algorithm in joint space computes incremental joint vectors delta-q = delta-q(sub a) + delta-q(sub c) + delta-q(sub r). Adding delta-q to the robot's current joint vector leads to the next step in the path. Delta-q(sub a) is obtained by computing the minimum norm solution of the underdetermined linear system J delta-q(sub a) = x(sub a) where x(sub a) is a translational and rotational force vector that attracts the robot to its goal position and orientation. J is the manipulator Jacobian. Delta-q(sub c) is a collision avoidance term encompassing collisions between the robot (links and payload) and obstacles in the environment as well as collisions among links and payload of the robot themselves. It is obtained in joint space directly. Delta-q(sub r) is a function of the current joint vector and avoids joint range overruns. A higher level discrete search over candidate safe positions is used to provide alternatives in case the potential field algorithm encounters a local minimum and thus fails to reach the goal. The best first search algorithm A* is used for graph search. Symmetry properties of the payload and equivalent rotations are exploited to further enlarge the number of alternatives passed to the potential field algorithm.

Muenger, Rolf↗
NASA NTRS2001

Autonomous path-planning for formation flying-applications

The paper presents a solution to the optimal formation path-planning problem where the formation reconfigurations are required subject to collision avoidance and resource limitation contraints.

formation flying collision-avoidance path-planning↗
NASA NTRS2014

Safe Maritime Autonomous Path Planning in a High Sea State

This paper presents a path planning method for sea surface vehicles that prevents capsizing and bow-diving in a high sea-state. A key idea is to use response amplitude operators (RAOs) or, in control terminology, the transfer functions from a sea state to a vessel's motion, in order to find a set of speeds and headings that results in excessive pitch and roll oscillations. This information is translated to arithmetic constraints on the ship's velocity, which are passed to a model predictive control (MPC)-based path planner to find a safe and optimal path that achieves specified goals. An obstacle avoidance capability is also added to the path planner. The proposed method is demonstrated by simulations.

Ono, Masahiro↗
NASA NTRS2003

A terrain-based path planning method for mobile robots

This paper presents a technique for incorporating terrain traversability data into a global path planning method for field mobile robots operating on rough natural terrain.

path planning traversability terrain assessment↗
NASA NTRS1991

Fuzzy Logic Path Planning System for Collision Avoidance by an Autonomous Rover Vehicle

Systems already developed at JSC have shown the benefits of applying fuzzy logic control theory to space related operations. Four major issues are addressed that are associated with developing an autonomous collision avoidance subsystem within a path planning system designed for application in a remote, hostile environment that does not lend itself well to remote manipulation of the vehicle involved through Earth-based telecommunication. A good focus for this is unmanned exploration of the surface of Mars. The uncertainties involved indicate that robust approaches such as fuzzy logic control are particularly appropriate. The four major issues addressed are: (1) avoidance of a single fuzzy moving obstacle; (2) back off from a dead end in a static obstacle environment; (3) fusion of sensor data to detect obstacles; and (4) options for adaptive learning in a path planning system.

Murphy, Michael G.↗
NASA NTRS1993

A global approach to kinematic path planning to robots with holonomic and nonholonomic constraints

Robots in applications may be subject to holonomic or nonholonomic constraints. Examples of holonomic constraints include a manipulator constrained through the contact with the environment, e.g., inserting a part, turning a crank, etc., and multiple manipulators constrained through a common payload. Examples of nonholonomic constraints include no-slip constraints on mobile robot wheels, local normal rotation constraints for soft finger and rolling contacts in grasping, and conservation of angular momentum of in-orbit space robots. The above examples all involve equality constraints; in applications, there are usually additional inequality constraints such as robot joint limits, self collision and environment collision avoidance constraints, steering angle constraints in mobile robots, etc. The problem of finding a kinematically feasible path that satisfies a given set of holonomic and nonholonomic constraints, of both equality and inequality types is addressed. The path planning problem is first posed as a finite time nonlinear control problem. This problem is subsequently transformed to a static root finding problem in an augmented space which can then be iteratively solved. The algorithm has shown promising results in planning feasible paths for redundant arms satisfying Cartesian path following and goal endpoint specifications, and mobile vehicles with multiple trailers. In contrast to local approaches, this algorithm is less prone to problems such as singularities and local minima.

Divelbiss, Adam↗
NASA NTRSDate not supplied

Path Planning: Differential Dynamic Programming and Model Predictive Path Integral Control on VTOL Aircraft

This paper explores two optimal control approaches, widely used in robotics, to establish their viability as real-time trajectory planners for vehicle configurations envisioned for the emerging aviation sector of Urban Air Mobility (UAM). Differential Dynamic Programming (DDP) enables planning over highly nonlinear dynamics using second-order approximations along a nominal trajectory, and displays quadratic convergence to a local solution. Model Predictive Path Integral (MPPI) is a stochastic sampling-based algorithm that can optimize for general cost criteria, including potentially highly nonlinear formulations, and supports parallel computation through the use of modern GPU hardware. In this work, DDP and MPPI were implemented using model predictive control (MPC), and the results indicate they are able to successfully transition the aircraft over different flight envelopes and generate trajectories unique to UAM vehicles.

Differential Dynamic Programming↗
NASA NTRS1988

A variational dynamic programming approach to robot-path planning with a distance-safety criterion

An approach to robot-path planning is developed by considering both the traveling distance and the safety of the robot. A computationally-efficient algorithm is developed to find a near-optimal path with a weighted distance-safety criterion by using a variational calculus and dynamic programming (VCDP) method. The algorithm is readily applicable to any factory environment by representing the free workspace as channels. A method for deriving these channels is also proposed. Although it is developed mainly for two-dimensional problems, this method can be easily extended to a class of three-dimensional problems. Numerical examples are presented to demonstrate the utility and power of this method.

Suh, Suk-Hwan↗
NASA NTRS2010

Graph-Based Path-Planning for Titan Balloons

A document describes a graph-based path-planning algorithm for balloons with vertical control authority and little or no horizontal control authority. The balloons are designed to explore celestial bodies with atmospheres, such as Titan, a moon of Saturn. The algorithm discussed enables the balloon to achieve horizontal motion using the local horizontal winds. The approach is novel because it enables the balloons to use arbitrary wind field models. This is in contrast to prior approaches that used highly simplified wind field models, such as linear, or binary, winds. This new approach works by discretizing the space in which the balloon operates, and representing the possible states of the balloon as a graph whose arcs represent the time taken to move from one node to another. The approach works with arbitrary wind fields, by looking up the wind strength and direction at every node in the graph from an arbitrary wind model. Having generated the graph, search techniques such as Dijkstra s algorithm are then used to find the set of vertical actuation commands that takes the balloon from the start to the goal in minimum time. In addition, the set of reachable locations on the moon or planet can be determined.

Blackmore, Lars James↗
NASA NTRS1987

Path Planning with obstacle avoidance

The research report here summarizes a solution for two dimensional Path Planning with obstacle avoidance in a workspace with stationary obstacles. The solution finds the shortest path for the end effector of a manipulator arm. The program uses an overhead image of the robot work space and the starting and ending positions of the manipulator arm end effector to generate a search graph which is used to find the shortest path through the work area. The solution was originally implemented in VAX Pascal, but was later converted to VAX C.

Krause, Donald M.↗