An official website of the United States government
This paper considers resource constrained path planning for a Dubins agent. Resource constraints are modeled as path integrals that exert a path-dependent load on the agent that must not exceed an upper bound. A backtracking mechanism is proposed for the Hybrid-A* graph search algorithm to determine the minimum time path in the presence of the path loading constraint. The new approach is built on the premise that inadmissibility of a node on the graph must depend on the loading accumulated along the path taken to arrive at its location. Conventional hybrid-A* does not account for this fact, causing it to become suboptimal or even infeasible in the presence of resource constraints. The new approach helps "reset'' the graph search by backing away from a node when the loading constraint is exceeded, and redirecting the search to explore alternate routes to arrive at the same location, while keeping the path load under its stipulated threshold. Backtracking Stopping criterion is based on relaxation of the path load along the search path. Case studies are presented and numerical comparisons are made with the Lagrange relaxation method to solving equivalent resource-constrained shortest path problems.
more »
« less
Hybrid A* path search with resource constraints and dynamic obstacles
This paper considers path planning with resource constraints and dynamic obstacles for an unmanned aerial vehicle (UAV), modeled as a Dubins agent. Incorporating these complex constraints at the guidance stage expands the scope of operations of UAVs in challenging environments containing path-dependent integral constraints and time-varying obstacles. Path-dependent integral constraints, also known as resource constraints, can occur when the UAV is subject to a hazardous environment that exposes it to cumulative damage over its traversed path. The noise penalty function was selected as the resource constraint for this study, which was modeled as a path integral that exerts a path-dependent load on the UAV, stipulated to not exceed an upper bound. Weather phenomena such as storms, turbulence and ice are modeled as dynamic obstacles. In this paper, ice data from the Aviation Weather Service is employed to create training data sets for learning the dynamics of ice phenomena. Dynamic mode decomposition (DMD) is used to learn and forecast the evolution of ice conditions at flight level. This approach is presented as a computationally scalable means of propagating obstacle dynamics. The reduced order DMD representation of time-varying ice obstacles is integrated with a recently developed backtracking hybridA∗ graph search algorithm. The backtracking mechanism allows us to determine a feasible path in a computationally scalable manner in the presence of resource constraints. Illustrative numerical results are presented to demonstrate the effectiveness of the proposed path-planning method.
more »
« less
- Award ID(s):
- 2132798
- PAR ID:
- 10484159
- Publisher / Repository:
- Frontiers in Aerospace Engineering
- Date Published:
- Journal Name:
- Frontiers in Aerospace Engineering
- Volume:
- 1
- ISSN:
- 2813-2831
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper explores the nexus of two emerging Internet of Things (IoT) components in precision agriculture, which requires vast amounts of agriculture fields to be monitored from air and soil for food production with efficient resource utilization. On the one hand, unmanned aerial vehicles (UAVs) have gained interest in agricultural aerial inspection due to their ubiquity and observation scale. On the other hand, agricultural IoT devices, including buried soil sensors, have gained interest in improving natural resource efficiency in crop production. In this work, the path loss and fading characteristics in wireless links between a UAV and underground (UG) nodes (Air2UG link) are studied to design a UAV altitude optimization solution. A path loss model is developed for the Air2UG link, including fading in the channel, where fading is modeled using a Rician distribution and validated using the Kolmogorov-Smirnov test. Moreover, Rician-K is found to be dependent on the UAV altitude, which is modeled with a Gaussian function with an RMSE of 0.4-1.3 dB. Furthermore, a novel altitude optimization solution is presented to minimize the bit error rate (BER). Results show that the lowest possible altitude does not always minimize the BER. Optimizing the altitude reduces the Air2UG link BER by as much as 8.6-fold. Likewise, altitude optimization can minimize the impacts of increasing burial depth on the BER. Our results and analysis are the first in this field and can be exploited to optimize the altitude and resources of a UAV node to communicate with the sensors embedded in the soil efficiently.more » « less
-
Navigation among dynamic obstacles is a fundamental task in robotics that has been modeled in various ways. In Safe Interval Path Planning, location is discretized to a grid, time is continuous, future trajectories of obstacles are assumed known, and planning takes place offline. In this work, we define the Real-time Safe Interval Path Planning problem setting, in which the agent plans online and must issue its next action within a strict time bound. Unlike in classical real-time heuristic search, the cost-to-go in Real-time Safe Interval Path Planning is a function of time rather than a scalar. We present several algorithms for this setting and prove that they learn admissible heuristics. Empirical evaluation shows that the new methods perform better than classical approaches under a variety of conditions.more » « less
-
null (Ed.)The main objective of an unmanned aerial vehicle (UAV) path planning is to generate a flight path that links a start point to an endpoint in an indoor space avoiding obstacles. Path planning is essential for many real-life applications such as an autonomous car, surveillance mission, farming robots, unmanned aerial vehicles package delivery, space exploration, and many others. To create an optimal path, we need to adopt a specific criterion to minimize the distance the UAV must travel such as the Euclidean distance. In this paper, we provide our initial idea of creating an optimal path for indoor UAV using both A* and the Late Acceptance Hill Climbing (LAHC) algorithms. We are adopting an indoor search environment with various complexity and utilize the Probabilistic Roadmap algorithm (PRM) as a search space for both algorithms. The basic idea following PRM is to generate random sample points in the space and search these points for an optimal path. The developed results show that the LAHC algorithm outperforms the A* algorithm.more » « less
-
This paper presents a novel mission-oriented path planning algorithm for a team of Unmanned Aerial Vehicles (UAVs). In the proposed algorithm, each UAV takes autonomous decisions to find its flight path towards a designated mission area while avoiding collisions to stationary and mobile obstacles. The main distinction with similar algorithms is that the target destination for each UAV is not apriori fixed and the UAVs locate themselves such that they collectively cover a potentially time-varying mission area. One potential application for this algorithm is deploying a team of autonomous drones to collectively cover an evolving forest wildfire and provide virtual reality for firefighters. We formulated the algorithm based on Reinforcement Learning (RL) with a new method to accommodate continuous state space for adjacent locations. To consider a more realistic scenario, we assess the impact of localization errors on the performance of the proposed algorithm. Simulation results show that the success probability for this algorithm is about 80% when the observation error variance is as high as 100 (SNR:-6dB).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3389/fpace.2022.1076271
