We consider a Generalized, Multiple Depot Hamiltonian Path Problem (GMDHPP) and show that it has an algorithm with an approximation ratio of 3/2 if the costs are symmetric and satisfy the triangle inequality. This improves on the 2-approximation algorithm already available for the same.

# Your search: "author:Rathinam, Sivakumar"

## filters applied

## Type of Work

Article (5) Book (0) Theses (0) Multimedia (0)

## Peer Review

Peer-reviewed only (0)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (5) UC Davis (0) UC Irvine (0) UCLA (0) UC Merced (0) UC Riverside (0) UC San Diego (0) UCSF (0) UC Santa Barbara (0) UC Santa Cruz (0) UC Office of the President (5) Lawrence Berkeley National Laboratory (0) UC Agriculture & Natural Resources (0)

## Department

University of California Institute of Transportation Studies (5) Institute of Transportation Studies at UC Berkeley (5)

## Journal

## Discipline

## Reuse License

## Scholarly Works (5 results)

This paper extends the Held-Karp’s lower bound available for a single Travelling Salesman Problem to the following symmetric Multiple Depot, Multiple Travelling Salesman Problem (MDMTSP): Given k salesman that start at di

This paper extends the well known Held-Karp's lower bound available for a single Travelling Salesman Problem to the multiple depot case. The LP-relaxation of a symmetric multiple vehicle, multiple depot problem is shown to be lower bounded by an infinite family of bounds. Each lower bound can be computed in a tractable way using a matroid intersection algorithm. When the costs of travelling between any two locations satisfy triangle inequality, it is shown that there exists a 2-approximation algorithm for solving the multiple depot, multiple TSP. These results are useful in solving the following path planning problem of UAVs: Given a set of UAVs, their starting locations, a set of final UAV locations, a set of destinations to visit and the cost of travelling between any two locations, find a path for each UAV such that each destination is visited once by any one UAV and the total cost travelled by all the UAVs is minimum.

Inspecting and monitoring oil-gas pipelines, roads, bridges, canals are very important in ensuring the reliability and life expectancy of these civil systems. An autonomous Unmanned Aerial Vehicle (UAV) can decrease the operational costs, expedite the monitoring process and be used in situations where a manned inspection is not possible. This paper addresses the problem of monitoring these systems using an autonomous UAV based on visual feedback. A single structure detection algorithm that can identify and localize various structures including highways, roads, and canals is presented in the paper. A fast learning algorithm that requires minimal supervision is applied to obtain detection parameters. The real time detection algorithm runs at 5 Hz or more with the onboard video collected by the UAV. Both hardware in the loop and flight results of the vision based control algorithm are presented in this paper. An UAV equipped with a camera onboard was able to track a 700 meter canal based on vision several times with an average cross track error of around 10 meters.

Multi-vehicle systems are naturally encountered in civil and military applications. Cooperation amongst individual "miniaturized" vehicles allows for flexibility to accomplish missions that a single large vehicle may not readily be able to accomplish. While accomplishing a mission, motion planning algorithms are required to efficiently utilize a common resource (such as the total fuel in the collection of vehicles) or to penalize a collective cost function (such as to minimize the maximum time taken by the vehicles to reach their intended target). The objective of this paper is to present a constant factor approximation algorithm for planning the path of each vehicle in a collection of vehicles, where the motion of each vehicle must satisfy non-holonomic constraints.