Minimum time multi-UGV surveillance
2008 (English)In: OPTIMIZATION AND COOPERATIVE CONTROL STRATEGIES / [ed] Hirsch MJ; Commander CW; Pardalos PM; Murphey R, Berlin: Springer Verlag , 2008, 31-45 p.Conference paper (Refereed)
This paper addresses the problem of concurrent task- and path planning for a number of surveillance Unmanned Ground Vehicles (UGVs) such that a user defined area of interest is covered by the UGVs' sensors in minimum time. We first formulate the problem, and show that it is in fact a generalization of the Multiple Traveling Salesmen Problem (MTSP), which is known to be NP-hard. We then propose a solution that decomposes the problem into three subproblems. The first is to find a maximal convex covering of the search area. Most results on static coverage use disjoint partitions of the search area, e.g. triangulation, to convert the continuous sensor positioning problem into a discrete one. However, by a simple example, we show that a highly overlapping set of maximal convex sets is better suited for minimum time coverage. The second subproblem is a combinatorial assignment and ordering of the sets in the cover. Since Tabu search algorithms are known to perform well on various routing problems, we use it as a part of our proposed solution. Finally, the third subproblem utilizes a particular shortest path sub-routine in order to find the vehicle paths, and calculate the overall objective function used in the Tabu search. The proposed algorithm is illustrated by a number of simulation examples.
Place, publisher, year, edition, pages
Berlin: Springer Verlag , 2008. 31-45 p.
, LECTURE NOTES IN CONTROL AND INFORMATION SCIENCES, ISSN 0170-8643 ; 381
Boolean functions, Ground vehicles, Intelligent vehicle highway systems, Learning algorithms, Optimal control systems, Optimization, Routing algorithms, Sensor networks, Sensors, Set theory, Tabu search, Trees (mathematics), Unmanned vehicles, Area of interests, Combinatorial assignments, Concurrent tasks, Continuous, Convex sets, Discrete, Disjoint partitions, Minimum times, Objective functions, Path planning, Positioning, Routing problems, Search areas, Shortest paths, Simulation examples, Tabu search algorithms, Traveling salesman, Unmanned Ground Vehicles
IdentifiersURN: urn:nbn:se:kth:diva-10061DOI: 10.1007/978-3-540-88063-9_2ISI: 000265134800002ScopusID: 2-s2.0-54349098250ISBN: 978-3-540-88062-2OAI: oai:DiVA.org:kth-10061DiVA: diva2:202394
8th International Conference on Cooperative Control and Optimization, Gainesville, FL, JAN 30-FEB 01, 2008
QC 201006222009-03-102009-03-102011-11-21Bibliographically approved