A Clustering-Based Approach for Cooperative Tasks Scheduling of Heterogenous Multi-Agent

This study proposes a computationally efficient method for near-optimal scheduling of cooperative tasks among heterogeneous multi-agents. A routing problem is formulated to maximize profit (priority) for task completion and minimize makespan with reduced task processing times, with coordination among agents. To address the curse of dimensionality inherent in the scheduling problem, the Cluster-First Route-Second (CFRS) heuristic is introduced. The K-means clustering algorithm, with repeated restarts across various initial conditions, is applied to geographically cluster tasks. MILP-based grouping and routing of agents are performed within a compact search space by generating possible paths on a per-cluster basis. The heterogeneity of agents and various practical constraints (e.g., fuel, the number of groups, and the number of agents) improve the accuracy of mission planning. A numerical case study and a performance comparison with the optimal solution demonstrate the effectiveness of the proposed approach.