Đề xuất SOTA của nhóm: HA-ALNS và RS-HA-ALNS cho Multi-UAV SAR

Câu hỏi trung tâm

Từ paper Risk-Sensitive Mean-Field Control of Large-Scale UAV Swarms, nhóm có thể xây một thuật toán mới nào cho bài toán chọn tuyến bay và thời gian hover nhằm tối đa xác suất phát hiện dưới ngân sách, đồng thời xử lý bất định của xác suất phát hiện?

Kết luận ngắn

Đề xuất xuyên suốt report tuần 1–10 là một decomposition hai tầng:

1. OHR giải chính xác phân bổ số lần hover khi tuyến đã cố định.
2. HA-ALNS dùng ALNS để tìm tuyến, nhưng mọi ứng viên được chấm bằng OHR và chèn ô theo giá bóng của thời gian.
3. RS-HA-ALNS mở rộng HA-ALNS sang trường hợp xác suất phát hiện $g$ bất định, dùng tiêu chí entropic risk cùng họ log–exp với Sayeed et al. nhưng áp dụng vào reward/PoD, không sao chép controller Riccati của paper.

Cách dùng từ “SOTA”

Báo cáo nội bộ cho thấy HA-ALNS đứng đầu trong tập thuật toán và protocol mà nhóm đã thử. Chưa nên viết “SOTA chung cho Multi-UAV SAR” nếu chưa có benchmark rộng hơn, mã baseline gốc và đánh giá độc lập. Cách diễn đạt an toàn là: “phương pháp đề xuất đạt kết quả tốt nhất trong protocol của nhóm và vượt hai baseline công bố được cài lại”.

Các nguồn trong scope

Nguồn	Vai trò
Risk-Sensitive Mean-Field Control of Large-Scale UAV Swarms	Nguồn cho tiêu chí nhạy rủi ro, entropy duality, scalability và kiến trúc phân tán
report/BaoCao_Tuan1-2.md	Formalization ban đầu, baseline, NP-hardness, submodularity và benchmark nhỏ
report/BaoCao_Tuan3-6.md	OHR, giá bóng, HA-ALNS, ablation và sensitivity
report/BaoCao_Tuan7-9.md	RS-HA-ALNS, so sánh phương pháp công bố, scalability, case study
report/BaoCao_CuoiKy_Tuan10.md	Tổng hợp phương pháp, kết quả và giới hạn cuối kỳ

Các path report/... ở trên thuộc repository /Users/vinhlq2512/code/multi-uav-sar, nằm ngoài vault.

Hai bài toán không giống nhau

Thành phần	Sayeed et al. 2026	Bài toán của nhóm
Đối tượng	Swarm lớn bám trường thảm hoạ động	Nhiều UAV tìm nạn nhân/mục tiêu trên bản đồ xác suất
Biến quyết định	Control input liên tục/phản hồi	Phân vùng, thứ tự waypoint, tuyến và số lần hover
Mục tiêu	Giảm tracking error, delay, energy, risk exposure	Tăng Probability of Detection trong ngân sách thời gian
Bất định	Nhiễu lan truyền thảm hoạ, cảm biến và động lực	Sai số dùng chung theo lớp địa hình trong $g$
Công cụ chính	Risk-sensitive Riccati, mean-field, consensus	Team Orienteering, OHR, ALNS, shadow price
Scalability	Theo số UAV $N$	Theo số ô, số ứng viên và số vòng ALNS
Metric	Coverage, time, energy, connectivity, path length	PoD, ETD, CVaR, worst case, runtime

Vì protocol và metric khác nhau, hai hệ không được xếp chung vào một leaderboard.

Dòng phát triển tuần 1–10

Tuần 1–2: formalization và baseline

• Mỗi ô $i$ có xác suất tiên nghiệm $p_i$ và xác suất phát hiện trong một lần quan sát $g_i$.
• Với tổng số lần quan sát $H_i$, đóng góp xác suất phát hiện là:

$$p_i\left[1-(1-g_i{)}^{H_i}\right].$$

• Bài toán chứa Team Orienteering nên NP-hard.
• Reward có diminishing returns theo số lần quan sát, tạo cấu trúc submodular.
• Nhóm xây baseline ngẫu nhiên, lawnmower, partition/concentric sweep, greedy và greedy có hover; branch-and-bound dùng cho instance rất nhỏ.

Tuần 3–6: OHR và HA-ALNS

Lợi ích biên của lần quan sát thứ $h+1$ tại ô $j$ là:

$$m_{h,j}=p_j(1-g_j{)}^h{g}_j.$$

Với tuyến cố định và thời lượng mỗi lần hover như nhau, số slot hover còn lại của UAV $k$ là $M_k$. OHR chọn đúng $M_k$ lợi ích biên lớn nhất. Vì $m_{h,j}$ giảm theo $h$, tập được chọn luôn là một prefix hợp lệ ở mỗi ô.

Ngưỡng ${\eta }_k$ là lợi ích nhỏ nhất trong tập đang chọn; giá bóng theo một giây là:

$${\mu }_k=\frac{{\eta }_k}{{\tau }_k}.$$

HA-ALNS dùng OHR làm bộ chấm tuyến và chỉ chèn ô khi lợi ích ròng dương sau khi trừ giá cơ hội của thời gian bay/hover.

Tuần 7–9: RS-HA-ALNS

Mỗi lớp địa hình $c$ có $g_c$ bất định theo posterior Beta. Một kịch bản $s$ là một vector $g^s$ dùng chung cho mọi ô cùng lớp, vì lỗi detector trên một loại nền có tương quan.

Vì nhóm tối đa hoá reward ${\mathrm{PoD}}_s(x)$, thước đo entropic được viết với dấu âm:

J_\theta(x) =-rac{1}{\theta} \log\left( \frac{1}{S}\sum_{s=1}^{S} e^{-\theta\operatorname{PoD}_s(x)} \right).

Khi $\theta \to 0$, $J_{\theta }$ tiến về PoD kỳ vọng. Khi $\theta$ tăng, các kịch bản PoD thấp nhận trọng số lớn hơn. Đây là cùng họ hàm mũ với paper Sayeed et al., nhưng dấu và đại lượng được đổi vì nhóm tối đa hoá reward thay vì tối thiểu hoá cost.

Đạo hàm sinh trọng số soft-min:

$$w_s=\frac{e^{-\theta {\mathrm{PoD}}_s(x)}}{{\sum }_r{e}^{-\theta {\mathrm{PoD}}_r(x)}}.$$

Lợi ích biên có trọng số vẫn giảm theo $h$:

$${\bar{m}}_{h,j}=\sum _{s=1}^S{w}_s{p}_j(1-g_j^s{)}^h{g}_j^s,$$

nên chứng minh top-$M_k$ của OHR vẫn giữ nguyên.

Tuần 10: đóng gói thành đóng góp hoàn chỉnh

Report cuối kỳ đặt tên hai thuật toán:

• HA-ALNS: Hover-Aware Adaptive Large Neighborhood Search.
• RS-HA-ALNS: Risk-Sensitive HA-ALNS.

Đóng góp hợp lý nhất để trình bày không phải “một ALNS mới” đơn thuần, mà là:

Bài toán NP-hard ở tầng tuyến
        ↓
Tách subproblem hover có nghiệm chính xác OHR
        ↓
Đưa nghiệm chính xác đó vào evaluation của ALNS
        ↓
Dùng shadow price để cắt ứng viên/chèn nhanh
        ↓
Giữ cấu trúc OHR dưới entropic scenario reweighting

Thuật toán đề xuất

HA-ALNS

Khởi tạo bằng Greedy có hover
→ 2-opt
→ chèn ô theo giá bóng
→ OHR chấm tuyến và phân bổ hover tối ưu
 
Lặp:
  chọn destroy operator thích nghi
  chọn repair operator thích nghi
  2-opt
  chèn theo giá bóng
  bỏ ô không nhận slot hover từ OHR
  nhận lời giải theo simulated annealing
  cập nhật trọng số operator

Các destroy operator gồm random, worst, cluster và segment; repair gồm greedy/noisy. OHR là oracle chính xác bên trong heuristic tuyến.

RS-HA-ALNS

Rút S kịch bản g theo posterior Beta
Khởi tạo trọng số kịch bản đều
 
Lặp R vòng ngoài:
  lập bảng lợi ích biên có trọng số
  chạy HA-ALNS với tổng ngân sách vòng lặp được giữ cố định
  chấm PoD trên mọi kịch bản
  tăng trọng số cho kịch bản xấu bằng soft-min exponential
 
Trả lời giải có J_theta tốt nhất

Phân tích độ phức tạp và bảo đảm

Thành phần	Độ phức tạp report nêu	Trạng thái bảo đảm
OHR trên tuyến cố định	$O(n_{k}H)$ bằng selection	Tối ưu chính xác cho subproblem hover khi mỗi slot có cùng chi phí
2-opt	$O(n^2)$ theo lượt	Cải thiện cục bộ, không bảo đảm tối ưu toàn cục
Một vòng HA-ALNS	$O(qCn+n^2)$	Heuristic khả thi; không có approximation ratio toàn cục
Lập bảng rủi ro	$O(SNH)$ mỗi vòng ngoài	Giữ tính giảm dần của lợi ích biên
Toàn bài toán	NP-hard	Chỉ subproblem hover có chứng minh tối ưu

Đây là câu chuyện DAA mạnh: exact inner problem + heuristic outer problem, kèm proof về cấu trúc giảm dần và đánh giá thực nghiệm cho phần không có bảo đảm toàn cục.

Kết quả nhóm báo cáo

Các con số sau là reported từ report tuần 7–10; chưa được chạy lại trong lượt tạo note này.

So sánh trên SAREnv

Thuật toán	PoD trung bình	HA-ALNS hơn tương đối	Ghi chú protocol
Greedy có hover	0.421 ± 0.216	13.2%	Deterministic
LHC-GW-CONV	0.396 ± 0.204	20.2%	Bản nhóm cài lại
ACO-MTS	0.374 ± 0.203	27.3%	Bản nhóm cài lại, 10 seed
HA-ALNS	0.476 ± 0.246	—	30 seed mỗi kịch bản

Report ghi nhận Friedman ${\chi }^2=422.4$, $p<0.001$; Wilcoxon–Holm cho ba so sánh trên đều $p<0.001$. HA-ALNS thắng trên 60/60 kịch bản so với LHC-GW-CONV, ACO-MTS và Greedy có hover.

Ablation

Biến thể	Thay đổi PoD so với đầy đủ	Diễn giải
Bỏ OHR, mỗi ô nhìn đúng một lần	-7.04%	Thành phần đóng góp rõ nhất
Chỉ destroy ngẫu nhiên	-1.06%	Đa dạng operator có ích
Bỏ 2-opt	-0.10%	Không khác biệt có ý nghĩa trong protocol này
Bỏ trọng số thích nghi	+0.07%	Không đo được lợi ích
Chèn theo tỉ số thay shadow price	+0.15%	PoD tương đương nhưng report ghi runtime chậm hơn

Đánh đổi rủi ro ở $\theta =16$

Chỉ số SAREnv	Danh nghĩa	RS-HA-ALNS	Thay đổi report nêu
PoD kỳ vọng	0.4734	0.4610	-2.62%
Độ lệch chuẩn	0.0382	0.0284	-26%
CVaR 10%	0.3967	0.4025	+1.45%
Worst case	0.3145	0.3285	+4.45%

Kết luận đúng là có đánh đổi, không phải cải thiện miễn phí. $\theta$ tăng vừa phải nâng đáy và giảm biến động nhưng làm giảm PoD trung bình; report cho rằng vùng $\theta =8$ đến $16$ hợp lý hơn $\theta =30$.

Điểm mới so với paper Sayeed et al.

1. Chuyển tiêu chí nhạy rủi ro từ control cost của trường thảm hoạ sang reward PoD của một kế hoạch tìm kiếm.
2. Mô hình hoá nguồn bất định cụ thể là detection probability $g$ theo lớp địa hình, với tương quan dùng chung trong cùng lớp.
3. Chứng minh entropic scenario weighting vẫn bảo toàn diminishing marginal gains, nên OHR tiếp tục giải chính xác subproblem hover.
4. Kết hợp oracle hover chính xác với ALNS cho tầng tuyến NP-hard.

Đây là suy luận/phát triển của nhóm, không phải đóng góp được paper Sayeed et al. tuyên bố.

Protocol và fairness khi gọi SOTA

Câu hỏi fairness	Trạng thái
Cùng dataset/split?	Có trong báo cáo nhóm trên 60 scenario SAREnv và bộ tổng hợp riêng
Cùng metric?	Có sau khi baseline được điều chỉnh sang PoD
Mã baseline gốc?	Không; LHC-GW-CONV và ACO-MTS là bản nhóm cài lại
Hyperparameter retuning công bằng?	Report nói chưa tinh chỉnh sâu cho baseline
Cùng compute budget?	Cùng cỡ, nhưng không hoàn toàn đồng nhất thuật toán
Nhiều seed?	Có cho HA-ALNS/ACO-MTS; baseline tất định không cần seed
Benchmark độc lập thứ hai?	Có bộ tổng hợp kiểu RescueNet, nhưng cách sinh là của nhóm
Đánh giá ngoài nhóm?	Chưa có evidence
Mã/kết quả được chạy lại trong lượt này?	Chưa

Vì vậy claim nên gắn scope rõ ràng.

Câu chữ đề xuất cho báo cáo và slide

Nhóm đề xuất HA-ALNS, một decomposition hai tầng trong đó OHR phân bổ hover tối ưu cho mỗi tuyến cố định, còn ALNS tìm kiếm trên không gian tuyến và dùng giá bóng để chèn ứng viên hiệu quả. Trên 60 kịch bản SAREnv theo protocol của nhóm, HA-ALNS đạt PoD cao nhất trong chín phương pháp được so sánh, vượt Greedy có hover 13.2%, LHC-GW-CONV 20.2% và ACO-MTS 27.3%. RS-HA-ALNS mở rộng phương pháp sang bất định của xác suất phát hiện bằng tiêu chí entropic; tại $\theta =16$, nó nâng worst-case 4.45% và giảm độ lệch chuẩn 26%, đổi lại giảm PoD kỳ vọng 2.62%. Các baseline công bố là bản nhóm cài lại, nên kết quả này chứng minh ưu thế trong protocol đã đánh giá, chưa phải claim SOTA phổ quát.

Khoảng trống nghiên cứu

• Đo $g$ thật theo loại địa hình thay cho bảng giả định.
• Dùng observation model có tương quan theo thời gian/góc nhìn; giả thiết các lần nhìn độc lập có thể lạc quan.
• Thêm false positive, mục tiêu di chuyển, quay về bãi, tránh va chạm và liên lạc.
• So sánh bằng mã baseline gốc hoặc protocol do bên thứ ba duy trì.
• Tìm cận trên chặt hơn hoặc approximation guarantee cho bài có hover.
• Với swarm hàng chục UAV, có thể nghiên cứu kiến trúc lai: mean-field/consensus cho phân vùng và ràng buộc kết nối ở tầng macro; HA-ALNS/OHR cho tuyến–hover ở tầng micro. Đây mới là hướng tương lai, chưa phải kết quả đã có.

Câu hỏi review

1. Vì sao OHR tối ưu khi tuyến đã cố định?
2. Tại sao bài toán tổng vẫn NP-hard dù subproblem hover có nghiệm chính xác?
3. Giá bóng ${\mu }_k$ giúp chèn ô như thế nào?
4. Tại sao trọng số entropic không phá tính diminishing returns của lợi ích biên?
5. Phân biệt claim “best in evaluated protocol” với “state of the art”.
6. Sayeed et al. ảnh hưởng RS-HA-ALNS ở đâu, và không ảnh hưởng ở đâu?

Liên kết

• Risk-Sensitive Mean-Field Control of Large-Scale UAV Swarms
• Design and Analysis of Algorithms - Phân tích thuật toán Multi-UAV SAR