期刊名称：International Journal of Advanced Robotic Systems
印刷版ISSN：1729-8806
电子版ISSN：1729-8814
出版年度：2013
卷号：10
期号：10
页码：349
DOI：10.5772/56486
语种：English
出版社：SAGE Publications
摘要：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.
Loading...
