SEARCH · Search NASA

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.

SourceResearch connectionFrom yearThrough year

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

At least 19 records

All sources NASA NTRS DOE OSTI

NASA NTRS1989

Planning paths through a spatial hierarchy - Eliminating stair-stepping effects

Stair-stepping effects are a result of the loss of spatial continuity resulting from the decomposition of space into a grid. This paper presents a path planning algorithm which eliminates stair-stepping effects induced by the grid-based spatial representation. The algorithm exploits a hierarchical spatial model to efficiently plan paths for a mobile robot operating in dynamic domains. The spatial model and path planning algorithm map to a parallel machine, allowing the system to operate incrementally, thereby accounting for unexpected events in the operating space.

Slack, Marc G.↗

NASA NTRS2011

Probabilistic Path Planning of Montgolfier Balloons in Strong, Uncertain Wind Fields

Lighter-than-air vehicles such as hot-air balloons have been proposed for exploring Saturn s moon Titan, as well as other bodies with significant atmospheres. For these vehicles to navigate effectively, it is critical to incorporate the effects of surrounding wind fields, especially as these winds will likely be strong relative to the control authority of the vehicle. Predictive models of these wind fields are available, and previous research has considered problems of planning paths subject to these predicted forces. However, such previous work has considered the wind fields as known a priori, whereas in practical applications, the actual wind vector field is not known exactly and may deviate significantly from the wind velocities estimated by the model. A probabilistic 3D path-planning algorithm was developed for balloons to use uncertain wind models to generate time-efficient paths. The nominal 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 particular goal location in the least expected time, utilizing advantageous winds. The solution also enables one to quickly evaluate the expected time-to-goal from any other location and to avoid regions of large uncertainty. This method is designed for balloons in wind fields but may be generalized for any buoyant vehicle operating in a vector field. To prepare the planning problem, the uncertainty in the wind field is modeled. Then, the problem of reaching a particular goal location is formulated as a Markov decision process (MDP) using a discretized space approach. Solving the MDP provides a policy of what actuation option (how much buoyancy change and, if applicable, horizontal actuation) should be selected at any given location to minimize the expected time-to-goal. The results provide expected time-to-goal values from any given location on the globe in addition to the action policy. This stochastic approach can also provide insights not accessible by deterministic methods; for example, one can evaluate variability and risk associated with different scenarios, rather than only viewing the expected outcome.

Wolf, Michael↗

NASA NTRS2022

UAV Path Planning for Wildfires - Sustainably Fighting Wildfires with Automated Path Planning for UAVs

As the severity and frequency of wildfires increase, infrastructure, properties, national parks, animal habitats, and human lives (civilians and firefighters) are put at greater risk. This paper examines the possible application of algorithmic path planning for UAV reconnaissance to reduce damage and safety risks, as aforementioned. When the location of a wildfire is known, UAVs are immediately dispatched from an operating base to fly to the fire and support the firefighters as quickly as possible. Then, the algorithm incrementally analyzes different environmental factors to create a path for the UAV to follow. This work focuses on generating a path for the UAV to follow given a set of polygons representing obstacles. The most important features of this algorithm are its fast response time and obstacle maneuverability. The use of an efficient path planning algorithm could potentially save lives, infrastructure, and acres of forest destruction.

UAV↗

NASA NTRS1990

Path planning control

Viewgraphs on path planning control are presented. Topics covered include: model based path planning; sensor based path planning; hybrid path planning; proximity sensor array; and applications for fuzzy logic.

Mcroberts, Malcolm↗

NASA NTRS1993

A global path planning approach for redundant manipulators

A new approach for global path planning of redundant manipulators is proposed. It poses the path planning problem as a finite time nonlinear control problem. The solution is found by a Newton-Raphson type algorithm. This technique is capable of handling various goal task descriptions as well as incorporating both joint and task space constraints. The algorithm has shown promising preliminary results in planning joint path sequences for 3R and 4R planar robots to meet Cartesian tip tracking and goal endpoint planning. It is robust with respect to local path planning problems such as singularity considerations and local minimum problems. Repetitive joint path solutions for cyclic end-effector tasks are also generated. Eventual goals of this work include implementation on full spatial robots, as well as provision of an interface for supervisory input to aid in path planning for more complex problems.

Seereeram, Sanjeev↗

NASA NTRS1988

Robot path planning using a genetic algorithm

Robot path planning can refer either to a mobile vehicle such as a Mars Rover, or to an end effector on an arm moving through a cluttered workspace. In both instances there may exist many solutions, some of which are better than others, either in terms of distance traversed, energy expended, or joint angle or reach capabilities. A path planning program has been developed based upon a genetic algorithm. This program assumes global knowledge of the terrain or workspace, and provides a family of good paths between the initial and final points. Initially, a set of valid random paths are constructed. Successive generations of valid paths are obtained using one of several possible reproduction strategies similar to those found in biological communities. A fitness function is defined to describe the goodness of the path, in this case including length, slope, and obstacle avoidance considerations. It was found that with some reproduction strategies, the average value of the fitness function improved for successive generations, and that by saving the best paths of each generation, one could quite rapidly obtain a collection of good candidate solutions.

Cleghorn, Timothy F.↗

NASA NTRS2008

Robust Path Planning and Feedback Design Under Stochastic Uncertainty

Autonomous vehicles require optimal path planning algorithms to achieve mission goals while avoiding obstacles and being robust to uncertainties. The uncertainties arise from exogenous disturbances, modeling errors, and sensor noise, which can be characterized via stochastic models. Previous work defined a notion of robustness in a stochastic setting by using the concept of chance constraints. This requires that mission constraint violation can occur with a probability less than a prescribed value.In this paper we describe a novel method for optimal chance constrained path planning with feedback design. The approach optimizes both the reference trajectory to be followed and the feedback controller used to reject uncertainty. Our method extends recent results in constrained control synthesis based on convex optimization to solve control problems with nonconvex constraints. This extension is essential for path planning problems, which inherently have nonconvex obstacle avoidance constraints. Unlike previous approaches to chance constrained path planning, the new approach optimizes the feedback gain as wellas the reference trajectory.The key idea is to couple a fast, nonconvex solver that does not take into account uncertainty, with existing robust approaches that apply only to convex feasible regions. By alternating between robust and nonrobust solutions, the new algorithm guarantees convergence to a global optimum. We apply the new method to an unmanned aircraft and show simulation results that demonstrate the efficacy of the approach.

autonomuys vehicles↗

NASA NTRS1989

Redundancy of space manipulator on free-flying vehicle and its nonholonomic path planning

The nonholonomic mechanical structure of space robots and path planning is discussed. The angular momentum conservation works as a nonholonomic constraint while the linear momentum conservation is a holonomic one. Thus, a vehicle with a 6 d.o.f. manipulator is described as a 9 variable system with 6 inputs. This implies the possibility of controlling the vehicle orientation and the joint variables of the manipulator by actuating the joint variables, but only if the trajectory is carefully planned; however, both of them cannot be controlled independently. It means that by assuming feasible-path planning, a system that consists of a vehicle and a 6 d.o.f. manipulator can be utilized as 9 d.o.f. system. Initially, the nonholonomic mechanical structure of space vehicle/manipulator system is shown. Then a path planning scheme for nonholonomic systems is proposed using Lyapunov functions.

Nakamura, Yoshihiko↗

NASA NTRS1990

Two arm robot path planning in a static environment using polytopes and string stretching

The two arm robot path planning problem has been analyzed and reduced into components to be simplified. This thesis examines one component in which two Puma-560 robot arms are simultaneously holding a single object. The problem is to find a path between two points around obstacles which is relatively fast and minimizes the distance. The thesis involves creating a structure on which to form an advanced path planning algorithm which could ideally find the optimum path. An actual path planning method is implemented which is simple though effective in most common situations. Given the limits of computer technology, a 'good' path is currently found. Objects in the workspace are modeled with polytopes. These are used because they can be used for rapid collision detection and still provide a representation which is adequate for path planning.

Schima, Francis J., III↗

NASA NTRS2007

Trajectory Generation and Path Planning for Autonomous Aerobots

This paper presents global path planning algorithms for the Titan aerobot based on user defined waypoints in 2D and 3D space. The algorithms were implemented using information obtained through a planner user interface. The trajectory planning algorithms were designed to accurately represent the aerobot's characteristics, such as minimum turning radius. Additionally, trajectory planning techniques were implemented to allow for surveying of a planar area based solely on camera fields of view, airship altitude, and the location of the planar area's perimeter. The developed paths allow for planar navigation and three-dimensional path planning. These calculated trajectories are optimized to produce the shortest possible path while still remaining within realistic bounds of airship dynamics.

trajectory↗

NASA NTRS1993

Path planning by querying persistent stores of trajectory segments

We introduce an algorithm for path planning (long duration) paths of dynamical systems, given a persistent object store containing suitable collections of short duration trajectory segments. We also describe experimental results from a proof-of-concept implementation of the algorithm. The basic idea is to interpret a path planning algorithm as a suitable query on a persistent object store consisting of short duration trajectory segments. The query returns a concatenation of short duration trajectory segments which is close to the desired path. The needed short duration segments are computed by using a divide and conquer algorithm to break up the original path into shorter paths; each shorter path is then matched to a nearby trajectory segment which is part of the persistent object store by using a suitable index function.

Grossman, Robert L.↗

NASA NTRSDate not supplied

Energy-Optimized Path Planning for Uas in Varying Winds Via Reinforcement Learning

In this paper we propose a reinforcement learning (RL) algorithm for path planning of Unmanned Aviation Vehicles (UAVs) under varying wind conditions. Solutions to UAV path planning problems are becoming increasingly necessary as autonomous UAVs continue to enter commercial and government spaces. Path-planning is inherently challenging, as UAVs need to account for dynamically changing flying conditions such as weather, obstacle or no-fly zones, degraded vehicle health, and off-nominal battery power consumption. Machine learning methods such as reinforcement learning (RL) have the potential to revolutionize how vehicles navigate in such uncertain environments. In this study, we compute UAV trajectories from a pre-determined starting position to a target cell within a 7X7 grid environment by optimizing parameters for mission assurance and safety limits in addition to the energy consumption and operation time. The UAV navigates the grid by taking actions to move in any of the eight cardinal and inter-cardinal directions, under constant thrust profile. The resultant UAV state is sampled from a probability distribution which accounts for the UAV’s action, local wind velocity, and the presence of obstacles or boundaries. As the unmanned airspace gets more complex due to multiple vehicles and environmental uncertainties, trade-offs between energy consumption, operation time, risk tolerance, and mission assurance need to be made. Our Markov Decision Process (MDP) environment model can capture any combination of these in the optimization objective, making it novel compared to other work in the field.

trajectory planning↗

NASA NTRS1994

Path planning for planetary rover using extended elevation map

This paper describes a path planning method for planetary rovers to search for paths on planetary surfaces. The planetary rover is required to travel safely over a long distance for many days over unfamiliar terrain. Hence it is very important how planetary rovers process sensory information in order to understand the planetary environment and to make decisions based on that information. As a new data structure for informational mapping, an extended elevation map (EEM) has been introduced, which includes the effect of the size of the rover. The proposed path planning can be conducted in such a way as if the rover were a point while the size of the rover is automatically taken into account. The validity of the proposed methods is verified by computer simulations.

Nakatani, Ichiro↗

NASA NTRS2011

Current-Sensitive Path Planning for an Underactuated Free-Floating Ocean Sensorweb

This work investigates multi-agent path planning in strong, dynamic currents using thousands of highly under-actuated vehicles. We address the specific task of path planning for a global network of ocean-observing floats. These submersibles are typified by the Argo global network consisting of over 3000 sensor platforms. They can control their buoyancy to float at depth for data collection or rise to the surface for satellite communications. Currently, floats drift at a constant depth regardless of the local currents. However, accurate current forecasts have become available which present the possibility of intentionally controlling floats' motion by dynamically commanding them to linger at different depths. This project explores the use of these current predictions to direct float networks to some desired final formation or position. It presents multiple algorithms for such path optimization and demonstrates their advantage over the standard approach of constant-depth drifting.

oceanography↗

NASA NTRSDate not supplied

Battery State-of-Health Aware Path Planning for a Mars Rover

A rover mission consists of visiting waypoints to gather scientific samples based on set requirements. However, rovers face operational uncertainties during the mission, affecting the performance of its electrical and mechanical components and overall mission success. Hence, it is critical to have a decision-making framework that is aware of the health state of the components when planning the path of the vehicle. In particular, battery degradation, and consequently the battery State of Health (SOH), can affect the optimality of decisions made by the autonomous system in the long term. This paper presents a decision-making system that incorporates information on the energy drawn from the battery (based on the vehicle’s velocity), terrain conditions, and model-based prognostic modules to assess the impact on the battery’s state of charge (SoC). The decision-making system was formulated as a Markov Decision Process (MDP) to reach the goal destination by sending commands in a determined amount of time while maintaining the battery SoC within the policy stated. The MDP problem was programmed using the open-source framework POMDPs.jl, which has a variety of online and offline solvers. To solve the MDP problem online, we used Monte Carlo Tree Search (MCTS). Results from simulations demonstrate the effect that battery degradation and charging plans have on decision-making.

Prognostics↗

NASA NTRS1989

Vehicle path-planning in three dimensions using optics analogs for optimizing visibility and energy cost

Path planning is an important issue for space robotics. Finding safe and energy-efficient paths in the presence of obstacles and other constraints can be complex although important. High-level (large-scale) path planning for robotic vehicles was investigated in three-dimensional space with obstacles, accounting for: (1) energy costs proportional to path length; (2) turn costs where paths change trajectory abruptly; and (3) safety costs for the danger associated with traversing a particular path due to visibility or invisibility from a fixed set of observers. Paths optimal with respect to these cost factors are found. Autonomous or semi-autonomous vehicles were considered operating either in a space environment around satellites and space platforms, or aircraft, spacecraft, or smart missiles operating just above lunar and planetary surfaces. One class of applications concerns minimizing detection, as for example determining the best way to make complex modifications to a satellite without being observed by hostile sensors; another example is verifying there are no paths (holes) through a space defense system. Another class of applications concerns maximizing detection, as finding a good trajectory between mountain ranges of a planet while staying reasonably close to the surface, or finding paths for a flight between two locations that maximize the average number of triangulation points available at any time along the path.

Rowe, Neil C.↗

NASA NTRS1990

Mobile transporter path planning

The use of a genetic algorithm (GA) 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. Elements of the genetic algorithm are explored in both a theoretical and experimental sense. Specifically, double crossover, greedy crossover, and tournament selection techniques are examined. Additionally, the use of local optimization techniques working in concert with the GA are also explored. 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.

Baffes, Paul↗

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↗