More Like this

1. Hybrid A* path search with resource constraints and dynamic obstacles

   https://doi.org/10.3389/fpace.2022.1076271  

   Cortez, Alán; Ford, Bryce; Nayak, Indranil; Narayanan, Sriram; Kumar, Mrinal (January 2023, Frontiers in Aerospace Engineering)

   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
2. A New Approach for the Resource Constrained Shortest Path Problem

   https://doi.org/10.1109/TITS.2023.3293039  

   Ren, Zhongqiang; Rubinstein, Zachary B; Smith, Stephen F; Rathinam, Sivakumar; Choset, Howie (January 2023, IEEE Transactions on Intelligent Transportation Systems)

   N/A (Ed.)

   Abstract—The Resource Constrained Shortest Path Problem (RCSPP) seeks to determine a minimum-cost path between a start and a goal location while ensuring that one or multiple types of resource consumed along the path do not exceed their limits. This problem is often solved on a graph where a path is incrementally built from the start towards the goal during the search. RCSPP is computationally challenging as comparing these partial solution paths is based on multiple criteria (i.e., the accumulated cost and resource along the path), and in general, there does not exist a single path that optimizes all criteria simultaneously. Consequently, the search needs to maintain and explore a large number of partial paths in order to find an optimal solution. While a variety of algorithms have been developed to solve RCSPP, they either have little consideration about efficiently comparing and maintaining the partial paths, which reduces their overall runtime efficiency, or are restricted to handle only one resource constraint as opposed to multiple resource constraints. This paper develops Enhanced Resource Constrained A* (ERCA*), a fast A*-based algorithm that can find an optimal solution while satisfying multiple resource constraints. ERCA* leverages both the recent advances in multi-objective path planning to efficiently compare and maintain partial paths, and techniques from the existing RCSPP literature. Furthermore, ERCA* has a functional parameter to broker a trade-off between solution quality and runtime efficiency. The results show ERCA* often runs several orders of magnitude faster than an existing leading algorithm for RCSPP. 

   more » « less
3. Constraint-Driven Optimal Control for Emergent Swarming and Predator Avoidance

   Beaver, L.E.; Malikopoulos, A.A. (May 2023, 2023 American Control Conference)

   In this article, we present a constraint-driven optimal control framework that achieves emergent cluster flocking within a constrained 2D environment. We formulate a decentralized optimal control problem that includes safety, flocking, and predator avoidance constraints. We explicitly derive conditions for constraint compatibility and propose an event-driven constraint relaxation scheme. We map this to an equivalent switching system that intuitively describes the behavior of each agent in the system. Instead of minimizing control effort, as it is common in the ecologically-inspired robotics literature, in our approach, we minimize each agent’s deviation from their most efficient locomotion speed. Finally, we demonstrate our approach in simulation both with and without the presence of a predator. 

   more » « less
4. A Robust Optimal Guidance Strategy for Mars Entry

   Palmer, Emily M.; Rao, Anil V. (August 2022, 2022 AAS/AIAA Astrodynamics Specialist Conference)

   A robust optimal guidance strategy is proposed. The guidance strategy is designed to reduce the possibility of violations in inequality path constraints in the presence of modeling errors and perturbations. The guidance strategy solves a constrained nonlinear optimal control problem at the start of every guidance cycle. In order to reduce the possibility of path constraint violations, the objective functional for the optimal control problem is modified at the start of a guidance cycle if it is found that the solution lies within a user-specified threshold of a path constraint limit. The modified objective functional is designed such that it maximizes the margin in the solution relative to the path constraint limit that could potentially be violated in the future. The method is validated on a path-constrained Mars entry problem where the reference model and the perturbed model differ in their atmospheric density. It is found for the example studied that the approach significantly improves the path constraint margin and maintains feasibility relative to a guidance approach that maintains the original objective functional for each guidance update. 

   more » « less
5. Graph Searching with Predictions

   https://doi.org/10.4230/LIPIcs.ITCS.2023.12  

   Banerjee, Siddhartha; Cohen-Addad, Vincent; Gupta, Anupam; Li, Zhouzi (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Tauman_Kalai, Yael (Ed.)

   Consider an agent exploring an unknown graph in search of some goal state. As it walks around the graph, it learns the nodes and their neighbors. The agent only knows where the goal state is when it reaches it. How do we reach this goal while moving only a small distance? This problem seems hopeless, even on trees of bounded degree, unless we give the agent some help. This setting with "help" often arises in exploring large search spaces (e.g., huge game trees) where we assume access to some score/quality function for each node, which we use to guide us towards the goal. In our case, we assume the help comes in the form of distance predictions: each node v provides a prediction f(v) of its distance to the goal vertex. Naturally if these predictions are correct, we can reach the goal along a shortest path. What if the predictions are unreliable and some of them are erroneous? Can we get an algorithm whose performance relates to the error of the predictions? In this work, we consider the problem on trees and give deterministic algorithms whose total movement cost is only O(OPT + Δ ⋅ ERR), where OPT is the distance from the start to the goal vertex, Δ the maximum degree, and the ERR is the total number of vertices whose predictions are erroneous. We show this guarantee is optimal. We then consider a "planning" version of the problem where the graph and predictions are known at the beginning, so the agent can use this global information to devise a search strategy of low cost. For this planning version, we go beyond trees and give an algorithms which gets good performance on (weighted) graphs with bounded doubling dimension. 

   more » « less