Многоквадракоптерная задача назначения заданий (Multi-UAV Task Assignment) Бенчмарк

Бенчмарк для многоквадракоптерной задачи назначения заданий

Введение

Представлен бенчмарк для оценки различных алгоритмов многоквадракоптерной задачи назначения заданий. Расширенная задача ориентирования команды моделируется для определенного типа многоквадракоптерной задачи назначения заданий. Реализованы три интеллектуальных алгоритма: Генетический алгоритм, Оптимизация колонии муравьев и Оптимизация роя частиц. Проведено несколько экспериментов с различными настройками для оценки этих трех алгоритмов. Моделированная задача и результаты оценки образуют бенчмарк, который может использоваться для оценки других алгоритмов, применяемых к многоквадракоптерным задачам назначения заданий.

Обратите внимание, что три алгоритма выполняются на трех ядрах процессора соответственно, что означает отсутствие параллельной оптимизации в этом бенчмарке.

Для получения более подробной информации обратитесь к статье.

K. Xiao, J. Lu, Y. Nie, L. Ma, X. Wang и G. Wang, "Бенчмарк для многоквадракоптерной задачи назначения заданий для расширенной задачи ориентирования команды", 2bk China Automation Congress (CAC), Xiamen, China, 2022, pp. 6966-6970, doi: 10.1109/CAC57257.2022.10054991.Препринт ArXiv arXiv:2003.09700

Использование

1. Входные и выходные данные алгоритма

Входные данные алгоритма включают количество квадрокоптеров (скаляр), скорости квадрокоптеров ($n\times1$ массив), количество целей (скаляр $n$), цели ($(n+1)\times4$ массив, первая строка — депо, первая колонка — позиция x, вторая колонка — позиция y, третья колонка — награда, четвертая колонка — время выполнения задания), и ограничение времени (скаляр). Ниже приведен пример инициализации класса GA в файле ga.py.

def __init__(self, vehicle_num, vehicles_speed, target_num, targets, time_lim)

В классе алгоритма должен быть метод run(), который должен возвращать план назначения заданий (массив, например, [[28, 19, 11], [25, 22, 7, 16, 17, 23], [21, 26, 12, 9, 6, 3], [5, 15, 1], [18, 20, 29]], каждый подмассив — это маршрут квадрокоптера) и затраченное время на вычисления (скаляр).

2. Оценка

Вы можете заменить один алгоритм ниже другим алгоритмом в файле evaluate.py, а затем выполнить команду python evaluate.py. Если вы не хотите оценивать три алгоритма одновременно, вам следует правильно изменить код (это легко).```python ga = GA(vehicle_num, env.vehicles_speed, target_num, env.targets, env.time_lim) aco = ACO(vehicle_num, target_num, env.vehicles_speed, env.targets, env.time_lim) pso = PSO(vehicle_num, target_num, env.vehicles_speed, env.targets, env.time_lim) ga_result = p.apply_async(ga.run) aco_result = p.apply_async(aco.run) pso_result = p.apply_async(pso.run) p.close() p.join() ga_task_assignment = ga_result.get()[0] env.run(ga_task_assignment, 'GA', i + 1, j + 1) re_ga[i].append((env.total_reward, ga_result.get()[1])) env.reset() aco_task_assignment = aco_result.get()[0] env.run(aco_task_assignment, 'ACO', i + 1, j + 1) re_aco[i].append((env.total_reward, aco_result.get()[1])) env.reset() pso_task_assignment = pso_result.get()[0] env.run(pso_task_assignment, 'PSO', i + 1, j + 1) re_pso[i].append((env.total_reward, pso_result.get()[1]))

В функции `Env()` в файле `evaluate.py` используется функция `step` для обучения с подкреплением. Поскольку это ещё находится в разработке, мы не можем предоставить демонстрацию. Если ваш алгоритм использует обучение с подкреплением, вы можете попробовать обучить его с помощью `Env()`. Ваши pull request и issue приветствуются.

## Улучшения

Этот [репозиторий](https://github.com/dietmarwo/Multi-UAV-Task-Assignment-Benchmark) обеспечивает отличные улучшения и может использоваться для высокопроизводительных вычислений. Спасибо [dietmarwo](https://github.com/dietmarwo) за отличную работу.

1) GA использует [numba](https://numba.pydata.org/) для значительного увеличения скорости. Параметры настроены таким образом, чтобы время выполнения оставалось прежним: popsize 50 -> 300, iterations 500 -> 6000. По этой причине GA теперь работает намного лучше по сравнению с оригинальной версией.2) Эксперименты настроены таким образом, чтобы время выполнения для малых размеров задач было сбалансировано. Это означает: увеличенное усилие для GA, уменьшенное усилие для ACO. Для средних/больших размеров задач вы увидите, какие алгоритмы плохо масштабируются: увеличение времени выполнения пропорционально размеру задачи. Избегайте этих алгоритмов для больших задач.

3) Добавляет стандартный алгоритм непрерывной оптимизации: [BiteOpt](https://github.com/avaneev/biteopt) 
    от Aleksey Vaneev — использует ту же функцию приспособленности, что и GA.py. 
    BiteOpt — единственный включенный алгоритм, который хорошо работает с большим размером задачи. 
    Это, безусловно, самая простая реализация, нужно только написать функцию приспособленности, 
    так как мы можем использовать библиотеку непрерывной оптимизации [fcmaes](https://github.com/dietmarwo/fast-cma-es). 
    Выполните `pip install fcmaes`, чтобы использовать её.

4) Использует NestablePool для включения многопоточного процесса BiteOpt: Множество оптимизационных запусков BiteOpt выполняется параллельно, и возвращается лучший результат. Установите `workers=1`, если вы хотите протестировать BiteOpt в однопоточном режиме.5) Все результаты создаются с использованием процессора AMD 5950x с 16 ядрами, использующим все ядра: 29 параллельных потоков BiteOpt, остальные 3 алгоритма остаются однопоточными.

6) Добавлен test_bite.py, где вы можете отслеживать прогресс BiteOpt, применённого к задаче.

7) Дополнен test_mode.py, где вы можете отслеживать прогресс применения fcmaes-MODE к задаче и сравнивать его с BiteOpt для той же самой задачи. fcmaes-MODE является многокритериальным оптимизатором, применённым к многокритериальной вариации задачи. Цели: награда (для максимизации), максимальное время (для минимизации), энергия (для минимизации). Ограничение по максимальному времени из однокритериального случая по-прежнему действует. Расход энергии приближённо определяется как `sum(dt*v*v)`