This paper proposes a mechanism to fine-tune convex approximations of probabilistic reachable sets (PRS) of uncertain dynamic systems. We consider the case of unbounded uncertainties, for which it may be impossible to find a bounded reachable set of the system. Instead, we turn to find a PRS that bounds system states with high confidence. Our data-driven approach builds on a kernel density estimator (KDE) accelerated by a fast Fourier transform (FFT), which is customized to model the uncertainties and obtain the PRS efficiently. However, the non-convex shape of the PRS can make it impractical for subsequent optimal designs. Motivated by this, we formulate a mixed integer nonlinear programming (MINLP) problem whose solution result is an optimal$n$sided convex polygon that approximates the PRS. Leveraging this formulation, we propose a heuristic algorithm to find this convex set efficiently while ensuring accuracy. The algorithm is tested on comprehensive case studies that demonstrate its near-optimality, accuracy, efficiency, and robustness. The benefits of this work pave the way for promising applications to safety-critical, real-time motion planning of uncertain dynamic systems.Note to Practitioners—This study is motivated by the realization of safety-critical real-time motion planning for a dynamic system under uncertainties. A popular method used to guarantee the safe operation of uncertain dynamic systems is reachability analysis. However, this method may not work well in the face of the following challenges: unbounded uncertainties, unknown distributions, generality, convexity, and efficiency. To address these issues, we first present a data-driven approach to model arbitrary unknown uncertainties and obtain a set encompassing the system states with high confidence; Then we propose an algorithm to efficiently find a tight convex polygon approximation for the set. This clearly benefits real motion planning. When considering collision avoidance in motion planning, a tight convex approximation allows a larger feasible search area which may provide a better-planned trajectory. Also, the efficiency of the algorithm ensures that the motion planning can be realized in real-time.

In this article, we first propose an algorithm to find a probabilistic reachable set (PRS) that bounds system states given a prescribed confidence level. Then, we establish an optimization framework using mixed integer linear programming, where the solution identifies a convex polytope that approximates the PRS. Utilizing this formulation, we have devised a heuristic algorithm aimed at efficiently determining its solution without compromising significant accuracy. Through case studies, we have tested this heuristic algorithm, showcasing its simultaneous benefits in terms of efficiency, accuracy, near-optimality, and robustness. The positive outcomes of this research lay the foundation for potential applications in the real-time, safety-critical motion planning of dynamic systems under uncertainties.

Unmanned aerial vehicles (UAVs) based mobile edge computing (MEC) systems have attracted increasing research attention recently. They can provide on-demand computing services for ground users (GUs) without relying on any communication infrastructures and have the potential to provide better computing services with lower latency, compared with the conventional ground-based MEC or cloud-based systems. Considering the limited battery capacity of the UAVs, existing studies on UAV-based MEC have focused on using UAVs to serve GUs over small areas so that all tasks can be completed during a single flight. In this paper, we aim to remove this restriction and expand the range of users the UAV-based MEC system can serve, by integrating charge stations into the system. A joint task scheduling, routing, and charging problem is then formulated with the objective to minimize the total energy consumption, total service time, and total energy charged simultaneously. To solve this problem, we develop a mixed-integer programming (MIP) model and an equivalent mixed-integer linear programming (MILP) model. Comparative numerical studies demonstrate the optimal solutions found by the proposed approaches.

Chance-constrained optimization provides a promi- sing framework for solving control and planning problems with uncertainties, due to its modeling capability to capture randomness in real-world applications. In this paper, we consider a UAV trajectory planning problem with probabilistic geo-fence, building on the chance-constrained optimization approach. In the considered problem, randomness of the model, such as the uncertain boundaries of geo-fences, is incorporated in the formulation. By solving the formulated chance-constrained optimization with a novel sampling based solution method, the optimal UAV trajectory is achieved while limiting the probability of collision with geo-fences to a prefixed threshold. Furthermore, to obtain a totally collision-free trajectory, i.e., avoiding the collision not only at the discrete time-steps but also within the entire time horizon, we build on the idea of an iterative scheme. That is, to iterate the solving of the chance-constrained optimization until the collision with probabilistic geo-fence is avoided at any time within the time horizon. At last, we validate the effectiveness of our method via numerical simulations.

The concept of Urban Air Mobility (UAM) proposes to use revolutionary new electrical vertical takeoff and landing (eVTOL) aircraft to provide efficient and on-demand air transportation service between places previously underserved by the current aviation market. A key challenge for the success of UAM is how to manage large-scale autonomous flight operations with safety guarantee in high-density, dynamic and uncertain airspace environments. In this paper, a safety assured decentralized online guidance algorithm with airborne self-separation capability is proposed and analyzed for multi-aircraft autonomous flight operations under uncertainties. The problem is formulated as a multi-agent Markov Decision Process with continuous action space and is solved by a customized decentralized online algorithm based on Monte Carlo Tree Search (MCTS). To guarantee the safety of real-time autonomous flight operations in uncertain environments, the formulation of loss of chance constrained separation is introduced and integrated with the proposed MCTS algorithm. In addition, Gaussian process regression along with Bayesian optimization is employed to discretize the continuous action space, which helps shorten the flight time. A comprehensive numerical study shows that the proposed algorithm can provide safe onboard guidance with guaranteed low near mid-air collision probability in uncertain and high-density airspace environments.

In recent years, we have witnessed a growing use of unmanned aerial vehicles (UAVs) in a variety of civil, commercial and military applications. Among these applications, many require the UAVs to scan or survey one or more regions, such as land monitoring, disaster assessment, search and rescue. To realize such applications, path planning is a key step. Although the coverage path planning (CPP) problem for a single region has been extensively studied in the literature, CPP for multiple regions has gained much less attention. This multi-regional CPP problem can be considered as a variant of the (multiple) traveling salesman problem (TSP) enhanced with CPP. Previously, we have studied the case of a single UAV. In this paper, we extend our previous studies to further consider multiple UAVs with energy constraints. To solve this new path planning problem, we develop two approaches: 1) a branch-and-bound (BnB) based approach that can find (near) optimal tours and 2) a genetic algorithm (GA) based approach that can solve large-scale problems efficiently under different objectives. Comprehensive theoretical analyses and computational experiments demonstrate the promising performance of the proposed approaches in terms of optimality and efficiency.

Drone fleet operators must be able to land the whole fleet in short notice. In practical operations, landing spots are usually much fewer than airborne drones. When many drones gravitate toward the limited landing spots simultaneously, congestion management becomes a challenge. This paper characterizes the fleet landing problem using mixed integer programming techniques and proposes a series of computational enhancements to reduce the solution time from hours to seconds. The solution algorithms are implemented in a software prototype for traffic management, and are thoroughly validated via extensive numerical examples and field simulations. For a fleet of 18 drones navigating at the same altitude layer within a 4-square kilometer area, all routing and trajectory computations can be completed in less than 5 seconds, and the entire fleet is able to complete landing at three pre-planned landing spots within about 3 minutes. Therefore, the models and algorithms are suitable for practical use.