Clustering-Based Algorithms for Multivehicle Task Assignment in a Time-Invariant Drift Field
Clustering-Based Algorithms for Multivehicle Task Assignment in a Time-Invariant Drift Field
复制标题
时不变漂移场中基于聚类的多车辆任务分配算法
DOI：
10.1109/lra.2017.2722541
复制
发表时间：
2017-10-01
影响因子：
5.2
通讯作者：
Cao, Ming
中科院分区：
文献类型：
--
作者：
Bai, Xiaoshan;Yan, Weisheng;Cao, Ming
研究了多车辆任务分配问题，其中多个分散的车辆需要访问时不变漂移场中的一组目标位置，同时试图最小化总行程时间。利用最优控制理论，我们首先设计了一个路径规划算法，以最小化每个车辆在漂移场中的两个给定位置之间行驶的时间。路径规划算法为目标分配提供成本矩阵，并且一旦目标位置被分配给车辆就生成路线。然后，我们提出了几种聚类策略来分配目标，我们使用两个度量来确定访问顺序的目标聚类到每个车辆。主要用于指定车辆在任意两个目标位置之间行驶的最短时间，成本矩阵使用路径规划算法获得，并且由于漂移场的时不变电流而通常是不对称的。我们表明，聚类策略之一，可以获得一个最小的成本树形的不对称目标车辆图的两个顶点之间的有向边的权重是最小的旅行时间从一个顶点到其他尊重的方向。使用图论中的工具，找到了最优解的下限，该下限可用于测量解与最优解的接近程度。此外，通过将目标聚类策略与目标访问度量相结合，我们得到了几个任务分配算法。其中，两个算法保证所有的目标位置将在一个可计算的最大旅行时间内访问，这是最多的两倍时，成本矩阵是对称的最佳。最后，数值模拟表明，该算法可以快速导致一个解决方案，是接近最优。
This paper studies the multivehicle task assignment problem where several dispersed vehicles need to visit a set of target locations in a time-invariant drift field while trying to minimize the total travel time. Using optimal control theory, we first design a path planning algorithm to minimize the time for each vehicle to travel between two given locations in the drift field. The path planning algorithm provides the cost matrix for the target assignment, and generates routes once the target locations are assigned to a vehicle. Then, we propose several clustering strategies to assign the targets, and we use two metrics to determine the visiting sequence of the targets clustered to each vehicle. Mainly used to specify the minimum time for a vehicle to travel between any two target locations, the cost matrix is obtained using the path planning algorithm, and is in general asymmetric due to time-invariant currents of the drift field. We show that one of the clustering strategies can obtain a min-cost arborescence of the asymmetric target-vehicle graph where the weight of a directed edge between two vertices is the minimum travel time from one vertex to the other respecting the orientation. Using tools from graph theory, a lower bound on the optimal solution is found, which can be used to measure the proximity of a solution from the optimal. Furthermore, by integrating the target clustering strategies with the target visiting metrics, we obtain several task assignment algorithms. Among them, two algorithms guarantee that all the target locations will be visited within a computable maximal travel time, which is at most twice of the optimal when the cost matrix is symmetric. Finally, numerical simulations show that the algorithms can quickly lead to a solution that is close to the optimal.