A Primal-Dual Heuristic for a Heterogeneous Unmanned Vehicle Path Planning Problem. (11th October 2013)

• Record Type: Journal Article
• Authors: Sundar, Kaarthik; Rathinam, Sivakumar
• Is Part Of: International journal of advanced robotic systems. Volume 10:Number 10(2013)
• Publication Date: 2013-10-11
• Subjects: Unmanned Vehicle -- Hamiltonian Path Problem -- Primal-Dual Method -- Lagrangian Relaxation -- Subgradient Algorithm; Robotics -- Periodicals; Robotics; Periodicals; 629.892
• DOI: 10.5772/56486
• Languages: English
• ISSNs: 1729-8806

Abstract

We consider a path planning problem where a team of Unmanned Vehicles (UVs) is required to visit a given set of targets. The UVs are assumed to carry different sensors, and as a result, there are vehicle-target constraints that require each UV to visit a distinct subset of targets. The objective of the path planning problem is to find a path for each UV such that each target is visited at least once by some vehicle, the vehicle-target constraints are satisfied and the total distance travelled by the vehicles is a minimum. This path planning problem is a generalization of the Hamiltonian path problem and is NP-Hard. We develop a primal-dual heuristic and incorporate the heuristic in a Lagrangian relaxation procedure to find good, feasible solutions and lower bounds for the path planning problem. Computational results show that solutions whose costs are on an average within 14% of the optimum can be obtained relatively quickly for the path planning problem involving five UVs and 40 targets.