Việc điều phối tự động các nhiệm vụ giữa nhiều thiết bị bay không người (UAV) trong môi trường động là một bài toán tối ưu tổ hợp phức tạp, đòi hỏi cân nhắc đồng thời nhiều yếu tố như khoảng cách di chuyển, giới hạn năng lượng, ràng buộc thời gian thực hiện và mức độ ưu tiên của từng nhiệm vụ. Thuật toán tối ưu bầy kiến (Ant Colony Optimization – ACO), lấy cảm hứng từ hành vi tìm đường của đàn kiến, nổi bật nhờ khả năng khám phá hiệu quả không gian nghiệm lớn mà không cần đạo hàm hay giả định tuyến tính — đặc biệt phù hợp với bài toán phân bổ phi cấu trúc và đa mục tiêu như vậy.

Cấu trúc mô hình toán học

Bài toán được mô hình hóa dưới dạng một đồ thị có hướng G = (V, E), trong đó:

• Tập đỉnh V bao gồm tất cả các nhiệm vụ T = {t₁, t₂, ..., tₙ} và một nút "trạm xuất phát" s (đại diện cho vị trí cất cánh hoặc trạm điều khiển).
• Mỗi cạnh eᵢⱼ ∈ E nối từ nhiệm vụ tᵢ đến tⱼ mang trọng số cᵢⱼ, biểu thị chi phí khi UAV chuyển từ vị trí nhiệm vụ i sang j — thường là thời gian bay hoặc tiêu thụ năng lượng ước tính dựa trên khoảng cách Euclid và vận tốc tối đa của UAV.
• Mỗi UAV uₖ được gán một chuỗi con các nhiệm vụ liên tiếp (một "tuyến hành trình"), sao cho tổng chi phí tuyến không vượt quá giới hạn pin Bₖ và tổng khối lượng công việc không vượt quá khả năng tải Wₖ.

Thiết kế thành phần ACO cho bài toán

Để áp dụng ACO, cần xác định năm thành phần then chốt:

1. Biểu diễn nghiệm

Mỗi "con kiến" xây dựng một nghiệm dưới dạng dãy các chỉ số nhiệm vụ: π = [t_{i₁}, t_{i₂}, ..., t_{iₘ}]. Sau đó, nghiệm này được phân nhóm thành các chuỗi con bằng thuật toán phân vùng động (dynamic partitioning), sao cho mỗi chuỗi thỏa mãn ràng buộc năng lượng và tải. Số lượng chuỗi tương ứng với số UAV được sử dụng.

2. Thông tin heuristics

Hàm thông tin ηᵢⱼ được định nghĩa là nghịch đảo của chi phí di chuyển: ηᵢⱼ = 1 / (cᵢⱼ + ε), với ε = 1e−6 tránh chia cho 0. Ngoài ra, có thể tích hợp hệ số ưu tiên pⱼ của nhiệm vụ j vào: ηᵢⱼ = pⱼ / (cᵢⱼ + ε).

3. Luật chuyển trạng thái

Mỗi kiến chọn nhiệm vụ tiếp theo từ tập hợp khả thi allowed (các nhiệm vụ chưa được gán và vẫn đảm bảo ràng buộc nếu thêm vào tuyến hiện tại) theo xác suất:

prob(j) = (tau(i,j)^alpha * eta(i,j)^beta) / sum_k_in_allowed(tau(i,k)^alpha * eta(i,k)^beta);

Trong đó α = 1.5, β = 2.0 là tham số điều chỉnh mức độ phụ thuộc vào kinh nghiệm (pheromone) và tri thức cục bộ (heuristic).

4. Cập nhật thông tin

Sau mỗi vòng lặp, thông tin trên các cạnh được cập nhật hai lần:

• Bay hơi: tau(i,j) = (1 − rho) * tau(i,j), với rho = 0.1.
• Tăng cường: Với mỗi kiến k có chi phí tuyến là Lₖ, lượng thông tin bổ sung trên cạnh (i,j) là Δtauᵢⱼᵏ = Q / Lₖ nếu cạnh nằm trong tuyến của kiến k, ngược lại bằng 0. Tổng cộng: tau(i,j) = tau(i,j) + Σ Δtauᵢⱼᵏ.

5. Xử lý ràng buộc

Khi kiến cố gắng thêm nhiệm vụ mới vào tuyến đang xây dựng, hệ thống kiểm tra tức thì:

• Nếu tổng thời gian bay từ vị trí hiện tại đến nhiệm vụ mới và quay về trạm vượt quá Bₖ / vₖ, nhiệm vụ bị loại khỏi tập allowed.
• Nếu khối lượng dữ liệu thu thập từ nhiệm vụ vượt quá Wₖ, cũng loại bỏ nhiệm vụ đó.

Không sử dụng phương pháp phạt hay sửa hậu kỳ — thay vào đó, ràng buộc được tích hợp trực tiếp vào cơ chế lựa chọn, đảm bảo mọi nghiệm sinh ra đều khả thi.

Triển khai minh họa trên MATLAB

Dưới đây là hàm chính tạo tuyến cho một kiến đơn lẻ, đảm bảo tuân thủ ràng buộc năng lượng:

function [route, cost] = buildAntRoute(pheromone, heuristic, distMat, energyLimit, speed, taskLoad, maxLoad)
    nTasks = size(distMat, 1);
    visited = false(1, nTasks);
    route = [];
    currentEnergy = energyLimit;
    currentPos = 0; % 0 represents depot
    
    while any(~visited)
        allowed = find(~visited);
        if isempty(allowed), break; end
        
        % Compute transition probabilities
        probs = zeros(size(allowed));
        for idx = 1:length(allowed)
            j = allowed(idx);
            travelCost = distMat(currentPos + 1, j) / speed;
            if currentEnergy < travelCost || taskLoad(j) > maxLoad
                probs(idx) = 0;
            else
                probs(idx) = (pheromone(currentPos + 1, j)^1.5) * ...
                             (heuristic(currentPos + 1, j)^2.0);
            end
        end
        
        if all(probs == 0)
            break; % No feasible move
        end
        probs = probs / sum(probs);
        nextTask = allowed(randsample(length(allowed), 1, true, probs));
        
        route = [route, nextTask];
        visited(nextTask) = true;
        currentEnergy = currentEnergy - distMat(currentPos + 1, nextTask) / speed;
        currentPos = nextTask;
    end
    
    % Calculate total cost (time)
    cost = 0;
    if ~isempty(route)
        cost = distMat(1, route(1)) / speed; % depot to first task
        for i = 1:length(route)-1
            cost = cost + distMat(route(i), route(i+1)) / speed;
        end
        cost = cost + distMat(route(end), 1) / speed; % last task back to depot
    end
end

Thuật toán hoàn chỉnh sẽ khởi tạo m kiến, chạy song song qua maxIter thế hệ, và giữ lại giải pháp tốt nhất toàn cục sau mỗi vòng cập nhật thông tin. Độ phức tạp thời gian xấp xỉ O(m · n² · maxIter), phù hợp để triển khai trên nền tảng nhúng hoặc máy chủ trung tâm trong thời gian thực.