Browsing by Author "Yadlapalli, Sai Krishna"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Combinatorial Path Planning for a System of Multiple Unmanned Vehicles(2011-02-22) Yadlapalli, Sai KrishnaIn this dissertation, the problem of planning the motion of m Unmanned Vehicles (UVs) (or simply vehicles) through n points in a plane is considered. A motion plan for a vehicle is given by the sequence of points and the corresponding angles at which each point must be visited by the vehicle. We require that each vehicle return to the same initial location(depot) at the same heading after visiting the points. The objective of the motion planning problem is to choose at most q(? m) UVs and find their motion plans so that all the points are visited and the total cost of the tours of the chosen vehicles is a minimum amongst all the possible choices of vehicles and their tours. This problem is a generalization of the wellknown Traveling Salesman Problem (TSP) in many ways: (1) each UV takes the role of salesman (2) motion constraints of the UVs play an important role in determining the cost of travel between any two locations; in fact, the cost of the travel between any two locations depends on direction of travel along with the heading at the origin and destination, and (3) there is an additional combinatorial complexity stemming from the need to partition the points to be visited by each UV and the set of UVs that must be employed by the mission. In this dissertation, a sub-optimal, two-step approach to motion planning is presented to solve this problem:(1) the combinatorial problem of choosing the vehicles and their associated tours is based on Euclidean distances between points and (2) once the sequence of points to be visited is specified, the heading at each point is determined based on a Dynamic Programming scheme. The solution to the first step is based on a generalization of Held-Karp?s method. We modify the Lagrangian heuristics for finding a close sub-optimal solution. In the later chapters of the dissertation, we relax the assumption that all vehicles are homogenous. The motivation of heterogenous variant of Multi-depot, Multiple Traveling Salesmen Problem (MDMTSP) derives form applications involving Unmanned Aerial Vehicles (UAVs) or ground robots requiring multiple vehicles with different capabilities to visit a set of locations.Item On the information flow required for the scalability of the stability of motion of approximately rigid formation(Texas A&M University, 2005-08-29) Yadlapalli, Sai KrishnaIt is known in the literature on Automated Highway Systems that information flow can significantly affect the propagation of errors in spacing in a collection of vehicles. This thesis investigates this issue further for a homogeneous collection of vehicles. Specifically, we consider the effect of information flow on the propagation of errors in spacing and velocity in a collection of vehicles trying to maintain a rigid formation. The motion of each vehicle is modeled using a Linear Time Invariant (LTI) system. We consider undirected and connected information flow graphs, and assume that that each vehicle can communicate with a maximum of q(n) vehicles, where q(n) may vary with the size n of the collection. The feedback controller of each vehicle takes into account the aggregate errors in position and velocity of the vehicles, with which it is in direct communication. The controller is chosen in such a way that the resulting closed loop system is a Type-2 system. This implies that the loop transfer function must have at least two poles at the origin. We then show that if the loop transfer function has three or more poles at the origin, and if the size of the formation is sufficiently large, then the motion of the collection is unstable. Suppose l is the number of poles of the transfer function relating the position of a vehicle with the control input at the origin of the complex plane, and if the number (q(n)l+1)/(nl) -> 0 as n -> (Infinity), then we show that there is a low frequency sinusoidal disturbance with unity maximum amplitude acting on each vehicle such that the maximum errors in spacing response increase at least as much as O (square_root(n^l/(q(n)^(l+1)) ) consequence of the results presented in this paper is that the maximum of the error in spacing and velocity of any vehicle can be made insensitive to the size of the collection only if there is at least one vehicle in the collection that communicates with at least O(square_root(n)) other vehicles in the collection.