In this article, a new model for 3D motion planning, applicable to aerial vehicles, is proposed to connect an initial and final configuration subject to pitch rate and yaw rate constraints. The motion planning problem for a curvature-constrained vehicle over the surface of a sphere is identified as an intermediary problem to be solved, and it is the focus of this paper. In this article, the optimal path candidates for a vehicle with a minimum turning radius$r$moving over a unit sphere are derived using a phase portrait approach. We show that the optimal path is$CGC$or concatenations of$C$segments through simple proofs, where$C = L, R$denotes a turn of radius$r$and$G$denotes a great circular arc. We generalize the previous result of optimal paths being$CGC$and$CCC$paths for$r \in (0, \frac{1}{2}]\bigcup \lbrace \frac{1}{\sqrt{2}}\rbrace$to$r \leq \frac{\sqrt{3}}{2}$to account for vehicles with a larger$r$. We show that the optimal path is$CGC, CCCC,$for$r \leq \frac{1}{\sqrt{2}},$and$CGC, CC_\pi C, CCCCC$for$r \leq \frac{\sqrt{3}}{2}.$Additionally, we analytically construct all candidate paths and provide the code in a publicly accessible repository.

In this paper, we propose a new modeling approach and a fast algorithm for 3D motion planning, applicable for fixed-wing unmanned aerial vehicles. The goal is to construct the shortest path connecting given initial and final configurations subject to motion constraints. Our work differs from existing literature in two ways. First, we consider full vehicle orientation using a body-attached frame, which includes roll, pitch, and yaw angles. However, existing work uses only pitch and/or heading angle, which is insufficient to uniquely determine orientation. Second, we use two control inputs to represent bounded pitch and yaw rates, reflecting control by two separate actuators. In contrast, most previous methods rely on a single input, such as path curvature, which is insufficient for accurately modeling the vehicle's kinematics in 3D. We use a rotation minimizing frame to describe the vehicle's configuration and its evolution, and construct paths by concatenating optimal Dubins paths on spherical, cylindrical, or planar surfaces. Numerical simulations show our approach generates feasible paths within 10 seconds on average and yields shorter paths than existing methods in most cases.

Hybrid fuel Unmanned Aerial Vehicles (UAV), through their combination of multiple energy sources, offer several advantages over the standard single fuel source configuration, the primary one being increased range and efficiency. Multiple power or fuel sources also allow the distinct pitfalls of each source to be mitigated while exploiting the advantages within the mission or path planning. We consider here a UAV equipped with a combustion engine-generator and battery pack as energy sources. We consider the path planning and power-management of this platform in a noise-aware manner. To solve the path planning problem, we first present the Mixed Integer Linear Program (MILP) formulation of the problem. We then present and analyze a label-correcting algorithm, for which a pseudo-polynomial running time is proven. Results of extensive numerical testing are presented which analyze the performance and scalability of the labeling algorithm for various graph structures, problem parameters, and search heuristics. It is shown that the algorithm can solve instances on graphs as large as twenty thousand nodes in only a few seconds. Note to Practitioners—The problem and algorithms proposed in this paper are relevant to constrained planning problems in general and specifically to those focused on widespread usage of small aerial vehicles in congested, urban environments. We are concerned here with the path planning of hybrid-fuel aerial vehicles in a noise-aware manner. This is motivated by the increasing usage of aerial vehicles, envisioning a probable future restriction on noise production in certain airspaces and the planning of such vehicles in those airspaces. We explore this novel problem, and present an approach to quickly find the optimal path and power plan in the presence of the noise constraints. The approach here is a discrete one, where the solution is a discrete set of edges and discrete generator settings which must be smoothed to obtain control inputs for a real system. The discrete approach allows solutions to be found quickly while giving up the true optimal trajectory that can be found when considering from a continuous framework. In practice, environment sampling and graph construction will greatly affect time-to-solve and as overall solution quality relative to a continuous approach to the trajectory and generator control.

In this article, we consider a multi-agent path planning problem in a partially impeded environment. The impeded environment is represented by a graph with select road segments (edges) in disrepair impeding vehicular movement in the road network. A primary vehicle, which we refer to as a convoy, wishes to travel from a starting location to a destination while minimizing some accumulated cost. The convoy may traverse an impeded edge for an additional cost (associated with repairing the edge) than if it were unimpeded. A support vehicle, which we refer to as a service vehicle, is simultaneously deployed to assist the convoy by repairing edges, reducing the cost for the convoy to traverse those edges. The convoy is permitted to wait at any vertex to allow the service vehicle to complete repairing an edge. The service vehicle is permitted to terminate its path at any vertex. The goal is then to find a pair of paths so the convoy reaches its destination while minimizing the total time (cost) the two vehicles are active, including any time the convoy waits. We refer to this problem as the Assisted Shortest Path Problem (ASPP). We present a generalized permanent labeling algorithm (GPLA) to find an optimal solution for the ASPP. We also introduce additional modifications to the labeling algorithm to significantly improve the computation time and refer to the modified labeling algorithm as GPLA*. Computational results are presented to illustrate the effectiveness of GPLA* in solving the ASPP.Note to Practitioners—One motivation for this work is to improve the efficiency of autonomous warehouse operations, where multiple robots need to coordinate their plans. Take for example two robots operating in a warehouse where one robot is moving goods and the second robot is making repairs or clearing obstructions (fallen goods, objects left by workers, etc.) along the way. The presented algorithm’s underlying structure is relatively simple and the algorithm itself does not require special software or solvers. The algorithm generates sub-optimal solutions as it progresses and terminates with the optimal solution. A large class of problems involving asynchronous actions between two or more agents can be handled using the presented algorithm or an extension of it. In this paper we restrict ourselves to two agents. A limitation of the presented algorithm and its possible extensions is the memory required as the graph representing the problem grows in size. We compare our work against an algorithm with similar approach (centralized$A^*$) and show that the presented algorithm is superior in both memory and computational time. We also present results on relatively large graphs to show the algorithm has practical value. This work can also be applied to rescue missions for people to escape wildfires, flooding or other natural disasters. A robotic agent can scout ahead for impacted pathways and assist victim(s) find the best path to escape to safety.

In this article, we propose a new formation scheme for a leader-follower unmanned aerial vehicle (UAV) system inspired by a human pilot's behavior wherein the formation geometry does not necessarily remain fixed as the vehicles maneuver. In other words, the position and the orientation of the follower with respect to the leader are subject to change as they maneuver while satisfying some constraints. Our strategy ensures that the follower UAV maintains a desired fixed relative distance with respect to the leader UAV, whereas its orientation with respect to the leader UAV may change to reduce its control effort and provide it with a tactical advantage. We call this new relational maneuvering scheme flexible since the set of feasible positions for the follower UAV is not fixed, as is common in close proximity two-ship formations in air-to-air combat. By assigning the follower UAV's linear and angular velocities as its control inputs, our approach tries to emulate a human pilot's behavior in UAVs by taking anticipatory maneuvers when the leader UAV makes aggressive turns. The proposed flexible-geometry formation scheme is robust to the leader's maneuver changes since the follower UAV's control law does not need the information of the leader's angular speed control and only uses relative measurements. This makes the design lucrative even when the vehicles are heterogeneous, global measurements are unavailable, or if the leader UAV is noncooperative. Finally, we present multiple simulations to highlight the merits of the flexible formation control laws.

In this article, we consider a perimeter defense problem in a planar conical environment in which$M$identical vehicles, each having a finite capture radius, seek to defend a concentric perimeter from mobile intruders. The intruders are released at the circumference of the environment at arbitrary times and in any number. Upon release, each intruder moves radially toward the perimeter with fixed speed. We provide a worst-case analysis of this problem. Specifically, we present acompetitive analysisapproach to this problem by measuring the performance of decentralized and cooperative online algorithms for the vehicles against arbitrary inputs, relative to an optimal offline algorithm that has information about entire intruder release sequence in advance. We first establish a necessary condition on the problem parameters that guarantees finite competitiveness ofanyalgorithm. We then design and analyze three decentralized and two cooperative online algorithms and characterize parameter regimes in which they have finite competitive ratios. Specifically, our first two decentralized algorithms are provably 1 and 2-competitive, respectively, whereas our third decentralized algorithm exhibits different competitive ratios in different regimes of problem parameters. Our first cooperative algorithm is 1.5-competitive and our second cooperative algorithm exhibits different competitive ratios in different regimes of problem parameters. Finally, we provide multiple numerical plots in the parameter space to reveal additional insights into the relative performance of our algorithms and discuss an extension to the case of heterogeneous vehicles.

For a given set of orbits, the Orbiting Dubins Traveling Salesman Problem (ODTSP) involves finding Dubins tour that is tangential to each orbit at some point. We consider a shortest Arc-to-Arc Dubins (ATAD) path problem that arrives in solving lower bound to the ODTSP. Given an initial and a final arc, the objective of ATAD is to find the shortest Dubins path such that the initial and final point lie on the given two arcs, and the path is tangential to the arcs. We analyze the six Dubins modes and the degenerate cases to find local minima. We present the optimal solution for the ATAD, along with an algorithm that uses this solution to compute tight lower bounds for the ODTSP. We test the lower bounding algorithm on several random instances and report the results. Using this algorithm, we show that the percent gap between upper and lower bounds is less than 10% for most instances.

This work presents a Multiple Depot Traveling Salesman Problem with revisit period constraints. The revisit period constraints are relevant to persistent routing applications, where these constraints represent maximum time between successive visits to a target. This problem is first posed as a Mixed Integer Linear Program. The coupling constraints in the primal problem are then relaxed via Lagrangian relaxation. Minimizing the resulting Lagrangian over the primal variables can be separated into an individual subproblem for each salesman. An algorithm to solve the subproblems to near-optimality that scales well for larger instances is presented. The dual function is then maximized, where three different dual update methods are studied: the subgradient method, the ellipsoid algorithm, and a bundle algorithm. Further, a primal reconstruction algorithm is presented to reconstruct feasible solutions from the solution of the dual algorithm. The quality of these solutions are compared to the optimal solutions obtained from the CPLEX MILP optimizer. The results of extensive numerical testing show that the dual algorithm presented was computationally efficient, capable of finding high quality solutions, and scale well compared to CPLEX. Further, it was seen that the bundle method used showed better convergence than the other update methods within the dual algorithm. Note to Practitioners— This work was motivated by the problem of routing UAVs in the presence of timing constraints, specifically motivated by military applications. This problem has constraints on the frequency at which targets are visited, such that high priority targets must be visited more frequently. Similar prior work exists in the literature for a variety of routing problems for different timing or resource constraints. Techniques which are successful on one set of constraints may be less useful when applied to different constraints. We present a Lagrangian based approach to the multiple depot traveling salesman variant. The results show the utility of a Lagrangian based technique to this problem, as both the solution quality and computation time scale well with problem size. The Lagrangian based technique presented here is seen to provide, on average, high quality solutions with improved computational time over a branch-and-bound algorithm, which solves the problem exactly. While the solutions returned from the algorithm are on average of good quality, they do exhibit some variance. Alternative algorithms may give more consistent results. The technique presented in this paper is general and may be applied to other routing problems where the revisit period constraints are applied. Future research includes application of this method to dynamic environments, where the targets’ states are unknown to the UAVs except when being monitored. Further, alternative techniques can be developed for this problem and compared to both the branch-and-bound and the Lagrange algorithm presented here.

Persistent monitoring missions require an up-to-date knowledge of the changing state of the underlying environment. Unmannned aerial vehicles (UAVs) can be gainfully employed to continually visit a set of targets representing tasks (and locations) in the environment and collect data therein for long time periods. The enduring nature of these missions requires the UAV to be regularly recharged at a service station. In this article, we consider the case in which the service station is not colocated with any of the targets. An efficient monitoring requires the revisit time, defined as the maximum of the time elapsed between successive revisits to targets, to be minimized. Here, we consider the problem of determining UAV routes that lead to the minimum revisit time. The problem is NP-hard, and its computational difficulty increases with the fuel capacity of the UAV. We develop an algorithm to construct near-optimal solutions to the problem quickly when the fuel capacity exceeds a threshold. We also develop lower bounds to the optimal revisit time and use these bounds to demonstrate (through numerical simulations) that the constructed solutions are, on an average, at most 0.01% away from the optimum.

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.

In this article, we introduce a cooperative path planning algorithm for a cardinal and a support robot where the cardinal robot is unable to traverse a subset of edges in a network until the support robot has first traversed them. This subset of edges represent paths in an environment that are initially unavailable to the cardinal robot and require the assistance of the support robot. A (2 + α)-approximation algorithm (where α is the supremum of the ratio of the travel time of the support robot versus the travel time of the cardinal robot) is presented for this problem and is applied to various types of networks in order to examine the quality of the solutions it produces. We then conclude by discussing some potential future work concerning variations of this problem.

In this paper, we consider a trajectory planning problem where an autonomous vehicle aims to rendezvous with another cooperating vehicle in minimum time. The first vehicle has kinematic constraints, consequently feasible trajectories must have a maximum curvature less than a specified limit. Rendezvous is said to occur at the instant that the two vehicles are collocated with the same heading. We propose a technique to construct a trajectory, composed of piecewise quadratic Bézier curves, that satisfies the vehicle motion constraints and achieves rendezvous in minimum time. The methodology begins by finding safe flight corridors, which are constructed from sequences of triangles using constrained Delaunay triangulation of the feasible space; the triangles define the bounds of Bézier curves. We formulate the necessary constraints for continuity and feasibility as functions of the control points that define the Bézier curves, and the resulting optimization problem is solved using a nonlinear programming solver. The techniques developed were tested using simulated scenarios, and we present the results which highlight the efficacy of the proposed solution approach. Furthermore, the algorithm was implemented and tested in a field test and those results are presented.

This article addresses a persistent monitoring problem (PMP) that requires an unmanned aerial vehicle (UAV) to repeatedly visit n targets of equal priority. The UAV has limited onboard fuel/charge and must be regularly serviced at a depot. Given a fixed number of visits, k, for the UAV to the targets between successive services, the objective of the PMP is to determine an optimal sequence of visits such that the maximum time elapsed between successive visits to any target is minimized. This planning problem is a generalization of the traveling salesman problem and is NP-hard. We characterize the optimal solutions to this problem for different values of k and develop algorithms that can compute the optimal solutions relatively fast. Numerical results are also presented to corroborate the performance of the proposed approach.

This paper considers a cooperative vehicle routing problem for an intelligence, surveillance, and reconnaissance mission in the presence of communication constraints between the vehicles. The proposed framework uses a ground vehicle and an unmanned aerial vehicle (UAV) that travel cooperatively and visit a set of targets while satisfying the communication constraints. The problem is formulated as a mixed-integer linear program, and a branch-and-cut algorithm is developed to solve the problem to optimality. Furthermore, a transformation method and a heuristic are also developed for the problem. The effectiveness of all the algorithms is corroborated through extensive computational experiments on several randomly generated instances. This paper is motivated by an intelligence, surveillance, and reconnaissance mission involving a single unmanned aerial vehicle (UAV) and a ground vehicle, where the vehicles must coordinate their activity in the presence of communication constraints. The combination of a small UAV and a ground vehicle is an ideal platform for such missions, since small UAVs can fly at low altitudes and can avoid obstacles or threats that would be problematic for the ground vehicle alone. This paper addresses the coordinated routing problem involving these two vehicles and presents an algorithm to obtain an optimal solution for this problem, fast heuristics to obtain good feasible solutions, and also a transformation method to transform any instance of this cooperative vehicle routing problem to an instance of the one-in-a-set traveling salesman problem.

As of late, hierarchical Fuzzy Inference Systems (hFIS) have received considerable attention because of their ability to control complex decision-making procedures. Although the performance of hFISs appears to be extremely effective in complex scenarios, there is a question about the differences between the hierarchical and single FISs (sFIS) and the relationship between the two. In this work, a transformation is derived which converts a Mamdani type hFIS into its equivalent sFIS representation. This is accomplished by equating their output membership functions. The equivalency between the outputs of the two representations is proven using a Satisfiability Modulo Theories (SMT) solver approach. Furthermore, we provide a detailed development procedure and results are presented which demonstrate the ease of implementation of the transformation as well as a wide applicability to meaningful large-scale problems.

We consider a team of miniature unmanned air vehicles (MUAVs) in a multi-static radar scenario. Time delay and Doppler measurements made at the UAVs are transmitted to a base station which is tracking a target. The base then transmits heading commands to the MUAVs to reduce the tracking error. Optimal solutions that attempt to minimize a function of the error covariance or maximize the observability of the system are computationally difficult to implement. We present a simpler approximate method that yields a closed-form solution and performs comparably to the optimal approaches.