This tutorial
-
Discusses how continuous optimization can be applied to a Multi-UAV Task Assignment problem thereby beating other proposed algorithms specifically created to solve this problem.
-
Extends the problem to multiple objectives and shows how this modification can be solved using the fcmaes-MODE algorithm.
Unmanned aerial vehicles (UAVs) have a large application potential in transportation, disaster rescue, reconnaissance and surveillance. Swarms of UAVs can be viewed as distributed intelligent autonomous systems.
There are many variants of the UAV task assignment problem. As an example we will investigate the following variant:
What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a set of targets thereby fulfilling a time limit constraint. Each vehicle has its own speed and the targets have different time costs and rewards.
The chosen variant is suitable for a wide range of multi-UAV task assignment problems. Therefore in https://arxiv.org/pdf/2009.00363.pdf it was chosen as the basis for a benchmark to evaluate different optimization algorithms: https://github.com/robin-shaun/Multi-UAV-Task-Assignment-Benchmark .
Three different algorithms: GA, PSO and ACO, were implemented in a problem specific
way and can be evaluated by executing the benchmark. Additionally a step function
is provided which can support the application of machine learning approaches like
reinforcement learning.
A problem specific optimizer has obvious disadvantages:
-
Additional implementation effort.
-
Harder to adapt for other problem variants.
-
Utilizing the whole CPU (all cores) is difficult. All three implementations are single threaded.
It makes only sense if the performance is superior compared to standard continuous optimizers like BiteOpt, CR-FM-NES or CMA-ES. which are easy to parallelize. CR-FM-NES and CMA-ES converge fast, but can get stuck at local minima. BiteOpt, on the other hand, converges slower but is better at avoiding getting stuck. Therefore we choose the sequences CR-FM-NES→BiteOpt and CMA-ES→BiteOpt as algorithms to test with the UAV problem.
Parallel retry applied to any of the two continuous optimizers outperforms all three algorithms by a big margin as we can see in the diagrams below:
Only for small problems GA can compete. The following diagram shows selected solutions for small, medium and large problem sizes for all six algorithms:
If we apply generic continuous optimization algorithms to this problem, adaption to a different variant means that only the objective function needs to be adapted.
We forked Multi-UAV-Task-Assignment-Benchmark in https://github.com/dietmarwo/Multi-UAV-Task-Assignment-Benchmark and implemented the following enhancements:
-
GA objective function is much faster using numba.
-
We applied numba also to the GA operations (selection, mutation, crossover), see ga.py
-
The fitness function used for GA is adapted and improved for use with continuous optimizers.
-
CR-FM-NES→BiteOpt and CMA-ES→BiteOpt using parallel retry are added as Benchmark and as a stand-alone experiment.
-
Multi-objective MODE parallel retry is added as stand-alone experiment.
Fitness class Optimizer delegates to the fitness function adapted from GA:
@njit(fastmath=True)
def fitness_(x, vehicle_num, vehicles_speed, target_num, targets, time_lim, map):
ins = np.zeros(target_num+1, dtype=numba.int32)
seq = np.argsort(x[vehicle_num-1:]) + 1
gene = (x[:vehicle_num-1]*target_num).astype(numba.int32)
ins[target_num] = 1
for i in range(vehicle_num-1):
ins[gene[i]] += 1
i = 0 # index of vehicle
pre = 0 # index of last target
post = 0 # index of ins/seq
t = 0
reward = 0
while i < vehicle_num:
if ins[post] > 0:
i += 1
ins[post] -= 1
pre = 0
t = 0
else:
t += targets[pre, 3]
past = map[pre, seq[post]]/vehicles_speed[i]
t += past
if t < time_lim:
reward += targets[seq[post], 2]
pre = seq[post]
post += 1
return reward
class Optimizer():
...
def fitness(self, x):
return -fitness_(x, self.vehicle_num, self.vehicles_speed,
self.target_num, self.targets, self.time_lim, self.map)
...Note that we use the np.argsort-trick applied to decision variables in the [0,1]-interval
to generate a sequence of unique indices. This way we need an additional decision variable, but
the results are much better for continuous optimizers.
The complete code is in test_fcmaes.py and fcmaesopt.py Only minor adjustments to the objective function initially created for GA are needed to apply numba for a dramatic speedup.
Instead of only optimizing the overall reward we can add more objectives:
-
used time - to be minimized
-
used energy - to be minimized
By applying a multi-objective algorithm we gain additional knowledge about the tradeoffs associated with these objectives. As a result we could for instance reconsider the time limit for the single objective optimization, if we see that more time means less energy and higher reward. So we adapted the objective function and applied the fcmaes MODE multi-objective optimization algorithm. In the diagrams below you see two 2-dimensional projections of the resulting three dimensional pareto front:
We used about 25 minutes / 8*10^8 evaluations for this optimization. Multi-objective
optimization needs more function evaluations than BiteOpt to find a solution
- as part of the pareto front - with comparable reward. But to reach a reward
achieved by GA, PSO or ACO only a few seconds are required. Note that this
problem doesn’t work well with differential evolution population update. Both single- and multi-objective.
So you have to configure MODE with parameter nsga_update = True.
def get_fitness(vehicle_num, target_num, map_size):
env = Env(vehicle_num,target_num,map_size,visualized=True)
return Fitness(vehicle_num,env.vehicles_speed,target_num,env.targets,env.time_lim)
mo_problem = get_fitness(15,90,1.5e4)
mo_fun = mode.wrapper(mo_problem, nobj)
workers = mp.cpu_count()
# MO parallel optimization retry
xs, ys = modecpp.retry(mo_fun, nobj, 0,
mo_problem.bounds, num_retries=workers, popsize = 512,
max_evaluations = evals, nsga_update = True, workers=workers)The complete code is in test_mode.py
Is it possible to use reinforcement learning to compute a pareto front? It seems so: https://arxiv.org/abs/1908.08342 , it would be interesting to apply this to UAV task assignment and compare results.
Do a git clone https://github.com/dietmarwo/Multi-UAV-Task-Assignment-Benchmark.git
and execute one of the following files:
-
The updated benchmark: evaluate.py
-
Continuous optimizers stand-alone: test_fcmaes.py
-
MODE stand-alone: test_mode.py
MODE can use up to evals = 100000000 with workers=32 and popsize=512 for large problem instances.
Even a fast 16 core CPU like the AMD 5950x needs one hour for the optimization using these parameters.
But this way multi-objective optimization delivers also excellent single-objective results similar to BiteOpt.
Before you implement a problem specific optimization algorithm first check whether a standard continuous optimization algorithm is applicable. Our README contains many example applications where you may be surprised that this approach works. Some of these are scheduling or task assignment related. Advantages are:
-
Parallelization comes for free.
-
Only the objective function has to be implemented.
-
Often the standard algorithms perform better.
-
Algorithm overhead is reduced, since many algorithms are implemented in C++.
-
The CR-FM-NES→BiteOpt sequence has low algorithm overhead and is applicable to other problems like vehicle routing (VRTPW) or MKKP.
Objective function implementation sometimes may be a bit tricky, specifically for problems using discrete arguments. For Multi-UAV Task Assignment both algorithm sequences perform exceptionally good.