Satyanarayana G. Manyam

Deepak Prakash Kumar, Swaroop Darbha, Satyanarayana Gupta Manyam et al.

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.

Sai Krishna Kanth Hari, Sivakumar Rathinam, Swaroop Darbha et al.

Persistent monitoring missions require an up-to-date knowledge of the changing state of the underlying environment. 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 paper, we consider the case in which the service station is not co-located 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.

Sivakumar Rathinam, Satyanarayana Gupta Manyam, Yuntao Zhang

This article considers two variants of a shortest path problem for a car-like robot visiting a set of waypoints. The sequence of waypoints to be visited is specified in the first variant while the robot is allowed to visit the waypoints in any sequence in the second variant. Field of view constraints are also placed when the robot arrives at a waypoint, i.e., the orientation of the robot at any waypoint is restricted to belong to a given interval of angles at the waypoint. The shortest path problem is first solved for two waypoints with the field of view constraints using Pontryagin's minimum principle. Using the results for the two point problem, tight lower and upper bounds on the length of the shortest path are developed for visiting n points by relaxing the requirement that the arrival angle must be equal to the departure angle of the robot at each waypoint. Theoretical bounds are also provided on the length of the feasible solutions obtained by the proposed algorithm. Simulation results verify the performance of the bounds for instances with 20 waypoints.

Sai Krishna Kanth Hari, Sivakumar Rathinam, Swaroop Darbha et al.

We consider the problem of planning a closed walk $\mathcal W$ for a UAV to persistently monitor a finite number of stationary targets with equal priorities and dynamically changing properties. A UAV must physically visit the targets in order to monitor them and collect information therein. The frequency of monitoring any given target is specified by a target revisit time, $i.e.$, the maximum allowable time between any two successive visits to the target. The problem considered in this paper is the following: Given $n$ targets and $k \geq n$ allowed visits to them, find an optimal closed walk $\mathcal W^*(k)$ so that every target is visited at least once and the maximum revisit time over all the targets, $\mathcal R(\mathcal W(k))$, is minimized. We prove the following: If $k \geq n^2-n$, $\mathcal R(\mathcal W^*(k))$ (or simply, $\mathcal R^*(k)$) takes only two values: $\mathcal R^*(n)$ when $k$ is an integral multiple of $n$, and $\mathcal R^*(n+1)$ otherwise. This result suggests significant computational savings - one only needs to determine $\mathcal W^*(n)$ and $\mathcal W^*(n+1)$ to construct an optimal solution $\mathcal W^*(k)$. We provide MILP formulations for computing $\mathcal W^*(n)$ and $\mathcal W^*(n+1)$. Furthermore, for {\it any} given $k$, we prove that $\mathcal R^*(k) \geq \mathcal R^*(k+n)$.

Satyanarayana Manyam, Sivakumar Rathinam, David Casbeer et al.

The Dubins interval problem aims to find the shortest path of bounded curvature between two targets such that the departure angle from the first target and the arrival angle at the second target are constrained to two respective intervals. We propose a new and a simple algorithm to this problem based on the minimum principle of Pontryagin.

Satyanarayana Manyam, Sivakumar Rathinam

The Dubins Traveling Salesman Problem (DTSP) has generated significant interest over the last decade due to its occurrence in several civil and military surveillance applications. Currently, there is no algorithm that can find an optimal solution to the problem. In addition, relaxing the motion constraints and solving the resulting Euclidean TSP (ETSP) provides the only lower bound available for the problem. However, in many problem instances, the lower bound computed by solving the ETSP is far below the cost of the feasible solutions obtained by some well-known algorithms for the DTSP. This article addresses this fundamental issue and presents the first systematic procedure for developing tight lower bounds for the DTSP.