Often times in multi-target, Unmanned Aerial System (UAS) applications, minimizing energy consumption is a common goal. In simplified cases, this problem can be solved by minimizing the path length between targets using the Traveling Salesman Problem with Neighborhoods (TSPN). However, this method does not take into account the attitude of the UAS. In addition, minimum path length does not always correlate to minimum energy consumption. This research proposes an approach to both problems. A method is proposed to more accurately model multi-target, six-rotor aircraft missions using the Generalized TSPN (GTSPN), which can account for the non-convex characteristics of the neighborhoods created by accounting for variable attitude. To address the energy consumption problem, a heuristic procedure is proposed to solve GTSPN instances using a genetic algorithm approach that incorporates a fine-tuned, dynamic model of a six-rotor to simulate energy consumption. Numerical simulations are performed on randomly generated instances with up to 50 targets to show that the proposed procedure determines tours for a given instance within a 1% standard deviation error from the best-known tour and on average improves the results obtained with the TSPN formulation up to 11.4%.

Often times in mobile robotics, optimizing a sequence of tasks and the paths between those destinations is an essential factor. In simple cases, this problem can be modeled by the well-researched Traveling Salesman Problem (TSP). In more complex situations however, the TSP is not a suitable model. In redundant robotic systems, a robot can assume infinitely many configurations while performing each given task. In these cases, not only is it necessary to optimize the sequence of tasks, but an optimal configuration must be defined for each task as well. This optimization problem can be better modeled by the Traveling Salesman Problem with Neighborhoods (TSPN) in which nodes can move in given domains called neighborhoods. However, one of the limiting factors to the TSPN is that it cannot efficiently solve realistic instances with non-connected neighborhoods. This research proposes an approach to this problem in which the TSPN is extended into a Generalized Traveling Salesman Problem with Neighborhoods (GTSPN) where each node can be located in multiple regions, called neighborhoodsets. An heuristic procedure is proposed to find a near-optimal tour for GTSPN instances using a genetic algorithm approach. Numerical simulations performed on randomly generated instances with up to 300 neighborhoods show that the proposed procedure determines tours for a given instance within a 1% standard deviation error from the best-known tour.

Finding an optimal path for a redundant robotic system to visit a sequence of several goal placements poses two technical challenges. First, while searching for an optimal sequence, infinitely many feasible configurations can be used to reach each goal placement. Second, obstacle avoidance has to be considered while optimizing the path from one goal placement to the next. Previous works focused on solving a discrete formulation of this optimization problem where only few configurations are used to represent each goal placement. We instead model it as a Traveling Salesman Problem with Neighborhoods (TSPN), where each neighborhood is defined as the set of the infinitely many configurations corresponding to the same goal placement. A solution procedure based on a Hybrid Random-key Genetic Algorithm (HRKGA) and bidirectional Rapidly-exploring Random Trees (biRRTs) is then proposed. Finally, experimental tests performed on a 7-Degree Of Freedom (DOF) industrial vision inspection system show that the proposed method is able to drastically reduce the cycle time currently required by the system.