Personal air transportation on short distances, so-called Urban Air Mobility (UAM), is a trend in modern aviation that raises new challenges as flying in urban areas at low altitudes induces an additional risk to people and properties on the ground. Risk-aware trajectory planning can mitigate the risk by detouring and flying over less populated and thus less risky areas. Existing risk-aware trajectory planning approaches are computationally demanding single-query methods that are impractical for online usage. Moreover, coordinated planning for multiple aircraft is prohibitively expensive. Therefore, we propose to reduce computational demands by determining low-risk areas called safe corridors and creating a roadmap of safe corridors based on multiple least risky trajectories. The created roadmap can be used in graph-based multi-agent planning methods for coordinated trajectory planning. The proposed method has been evaluated in a realistic urban scenario, suggesting a significant computational burden reduction and less risky trajectories than the current state-of-the-art methods.

Dubins tours represent a solution of the Dubins traveling salesman problem (DTSP) that is a variant of the optimization routing problem to determine a curvature-constrained shortest path to visit a set of locations such that the path is feasible for Dubins vehicle, which moves only forward and has a limited turning radius. The DTSP combines the NP-hard combinatorial optimization to determine the optimal sequence of visits to the locations, as in the regular TSP, with the continuous optimization of the heading angles at the locations, where the optimal heading values depend on the sequence of visits and vice versa. We address the computationally challenging DTSP by fast evaluation of the sequence of visits by the proposed windowing surrogate model (WiSM), which estimates the length of the optimal Dubins path connecting a sequence of locations in a Dubins tour. The estimation is sped up by a regression model trained using close to optimum solutions of small Dubins tours that are generalized for large-scale instances of the addressed DTSP utilizing the sliding-window technique and a cache for already computed results. The reported results support that the proposed WiSM enables fast convergence of a relatively simple evolutionary algorithm to high-quality solutions of the DTSP. We show that with an increasing number of locations, our algorithm scales significantly better than other state-of-the-art DTSP solvers.

This paper presents a novel approach to the multigoal trajectory planning for vehicles with curvature-constrained trajectories such as fixed-wing aircraft. In the existing formulation called the Dubins Traveling Salesman Problem (DTSP), the vehicle speed is assumed to be constant over the whole trajectory, and that does not allow adaptation of the turning radius of the trajectory between the target locations. It does not support optimization of the overall flight time of the multi-goal trajectory by exploiting higher speeds for longer turning radii. Therefore, we propose a novel problem formulation called the Variable-Speed Traveling Salesman Problem (VS-TSP) that employs time-efficient trajectories with variable speed based on a generalization of the Dubins vehicle model, allowing multiple turning radii and change of the forward speed of the vehicle. The VS-TSP allows the vehicle to slow down if high maneuverability is necessary and speed up if high-speed turns with a large radius are beneficial to the overall tour cost. Based on the evaluation results for Cessna 172 aircraft model, the proposed VNS-based algorithm with variable speed provides up to about 20 % faster trajectories than a solution of the DTSP with a single turning radius.

In this paper, we address the problem of finding cost-efficient three-dimensional paths that satisfy the maximum allowed curvature and the pitch angle of the vehicle. For any given initial and final configurations, the problem is decoupled into finding the horizontal and vertical parts of the path separately. Although the individual paths are modeled as two-dimensional Dubins curves using closed-form solutions, the final 3D path is constructed using the proposed local optimization to find a cost-efficient solution. Moreover, based on the decoupled approach, we provide a lower bound estimation of the optimal path that enables us to determine the quality of the found heuristic solution. The proposed solution has been evaluated using existing benchmark instances and compared with state-of-the-art approaches. Based on the reported results and lower bounds, the proposed approach provides paths close to the optimal solution while the computational requirements are in hundreds of microseconds. Besides, the proposed method provides paths with fewer turns than others, which make them easier to be followed by the vehicle's controller.

Multi-goal curvature-constrained planning such as the Dubins Traveling Salesman Problem (DTSP) combines NP-hard combinatorial routing with continuous optimization to determine the optimal vehicle heading angle for each target location. The problem can be addressed as combinatorial routing using a finite set of heading samples at target locations. In such a case, optimal heading samples can be determined for a sequence of targets in polynomial time, and the DTSP can be solved as searching for a sequence with the minimal cost. However, the examination of sequences can be computationally demanding for high numbers of heading samples and target locations. A fast rejection schema is proposed to quickly examine unfavorable sequences using lower bound estimation of Dubins tour cost based on windowing technique that evaluates short subtours of the sequences. Furthermore, the computation using small problem instances can benefit from reusing stored results and thus speed up the search. The reported results indicate that the computational burden is decreased about two orders of magnitude, and the proposed approach supports finding high-quality solutions of routing problems with Dubins vehicle.

This paper introduces the Close Enough Orienteering Problem (CEOP) for planning missions with multi-rotor aerial vehicles considering their maximal velocity and acceleration limits. The addressed problem stands to select the most rewarding target locations and sequence to visit them in the given limited travel budget. The reward is collected within a non-zero range from a particular target location that allows saving the travel cost, and thus collect more rewards. Hence, we are searching for the fastest trajectories to collect the most valuable rewards such that the motion constraints are not violated, and the travel budget is satisfied. We leverage on existing trajectory parametrization based on Bézier curves recently deployed in surveillance planning using unsupervised learning, and we propose to employ the learning in a solution of the introduced multi-vehicle CEOP. Feasibility of the proposed approach is supported by empirical evaluation and experimental deployment using multi-rotor vehicles.

Loss of thrust is a critical situation for human pilots of fixed-wing aircraft which force them to select a landing site in the nearby range and perform an emergency landing. The time for the landing site selection is limited by the actual altitude of the aircraft, and it may be fatal if the correct decision is not chosen fast enough. Therefore, we propose a novel RRT* -based planning algorithm for finding the safest emergency landing trajectory towards a given set of possible landing sites. Multiple landing sites are evaluated simultaneously during the flight even before any mechanical issue occurs, and the roadmap of possible landing trajectories is updated permanently. Thus, the proposed algorithm has the any-time property and provides the best emergency landing trajectory almost instantly.

In this paper, we extent an existing self-organizing map (SOM)-based approach for the Dubins traveling salesman problem (DTSP) to solve its multi-vehicle variant generalized for visiting target regions called k-DTSP with Neighborhoods (k-DTSPN). The Dubins TSP is a variant of the combinatorial TSP for curvature-constrained vehicles. The problem is to determine a cost efficient path to visit a given set of continuous regions while the path allows to satisfy kinematic constraints of non-holonomic vehicles. The k-DTSPN is a generalization to determine k such paths, one for each vehicle. Although the k-DTSPN has been addressed by evolutionary methods, the proposed approach is able to provide solutions very quickly in units of seconds on conventional computationally resources which makes the proposed SOM-based approach suitable for on-line planning. The studied problem is motivated by surveillance task in which it is required to quickly provide information about the given set of target locations. Therefore, real computational requirements are crucial properties of the desired k-DTSPN solver. The proposed method meets this requirement and feasibility of the found solutions are demonstrated not only in computer simulations but also with a practical deployment on real aerial vehicles.

In this paper, we consider existing asymptotically optimal inspection planning algorithm in coverage path planning with realistic visibility constraints of standard cameras. Although the existing approach is able to provide an optimal solution with omnidirectional sensing and limited sensing range, it is prohibitively computationally expensive for problems with only few objects to be covered and limited field of view. Based on the analysis of the utilized sampling-based strategy, we propose a heuristic approach to decrease computational requirements in problems with restricted viewing frustum, which is a more realistic model of a digital camera. In addition, we also consider a minimal distance and angle under which the object to be covered is captured by the forward looking camera to make a snapshot of the object with the required details.

This paper introduces an extension of the unsupervised learning method to solve data collection planning problems where particular sensor measurements can be spatially correlated. The problem is motivated by monitoring tasks formulated as the Prize-Collecting Traveling Salesman Problem with Neighborhoods (PC-TSPN). A solution of the PC-TSPN consists of a selection of important sensors, determination of the locations to read data from these sensors, and finding the shortest path to visit the locations. The solution cost is defined as a sum of the travel cost and penalty characterizing additional cost associated to sensors from which data are not retrieved. The penalty represents importance of particular sensor measurements to the quality of the model and existing solutions assume the penalties are constant values. However, for spatially close sensor locations, data from one sensor may contain also information about nearby locations and thus, its penalty depends on locations selected for data collection. The proposed generalization of the PC-TSPN solver allows to consider spatial correlations of sensor measurements and the proposed approach provides better solutions than the previous algorithm with fixed penalties.

In this paper, we address the problem of optimal path planning to visit a set of regions by Dubins vehicle, which is also known as the Dubins Traveling Salesman Problem with Neighborhoods (DTSPN). This problem can be tackled by a transformation to other variants of the TSP or evolutionary algorithms. We address the DTSPN as a problem to find Dubins path to visit a given sequence of regions and propose a simple iterative optimization procedure to find Dubins path visiting the regions. The proposed approach allows to efficiently solve the DTSPN and based on the presented comparison with existing approaches, the proposed algorithm provides solutions of competitive quality to the evolutionary techniques while it is significantly less computationally demanding.