fcmaes - a Python 3 gradient-free optimization library

Multi-UAV Task Assignment

This tutorial:

Shows how continuous optimization can be applied to a Multi-UAV Task Assignment problem and outperform specialized algorithms proposed for this benchmark.
Extends the problem to multiple objectives and shows how to solve that variant with the fcmaes MODE algorithm.

Motivation

Unmanned aerial vehicles (UAVs) are used in transportation, disaster rescue, reconnaissance, and surveillance. A swarm of UAVs can be seen as a distributed autonomous system.

There are many variants of the UAV task assignment problem. Here we look at the following one:

What is the best set of routes for a fleet of vehicles to visit a set of targets while satisfying a time limit? Each vehicle has its own speed, and each target has its own time cost and reward.

This variant is suitable for a wide range of multi-UAV task assignment problems. For that reason, https://arxiv.org/pdf/2009.00363.pdf used it as the basis for a benchmark that compares different optimization algorithms: https://github.com/robin-shaun/Multi-UAV-Task-Assignment-Benchmark .

The benchmark includes three problem-specific algorithms: GA, PSO, and ACO. It also provides a step function that can support machine learning approaches such as reinforcement learning.

A problem-specific optimizer has obvious disadvantages:

Additional implementation effort.
Harder to adapt for other problem variants.
Using the whole CPU is difficult. All three implementations are single-threaded.

This extra work only makes sense if the performance is clearly better than that of standard continuous optimizers such as BiteOpt, CR-FM-NES, or CMA-ES, which are easy to parallelize. CR-FM-NES and CMA-ES converge quickly, but they can get stuck in local minima. BiteOpt converges more slowly, but it is better at escaping them. For this reason, we test the sequences CR-FM-NES→BiteOpt and CMA-ES→BiteOpt on the UAV problem.

With parallel retry, both continuous optimization sequences outperform all three specialized algorithms by a wide margin, as shown below:

Only on small problems can GA compete. The next diagram shows selected solutions for small, medium, and large problem sizes for all six algorithms:

This is the main practical advantage. If we use generic continuous optimizers, adapting to a different problem variant usually means changing only the objective function.

Implementation

We forked Multi-UAV-Task-Assignment-Benchmark to https://github.com/dietmarwo/Multi-UAV-Task-Assignment-Benchmark and added the following enhancements:

GA objective function is much faster using numba.
We also applied numba to the GA operations selection, mutation, and 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 with parallel retry are added to the benchmark and as stand-alone experiments.
Multi-objective MODE parallel retry is added as a stand-alone experiment.

Single Objective Continuous Fitness

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)
...

Here we use the np.argsort trick on decision variables in the [0,1] interval to generate a sequence of unique indices. This requires one additional decision variable, but it works much better for continuous optimizers.

The complete code is in test_fcmaes.py and fcmaesopt.py Only minor changes to the objective function originally created for GA are needed to apply numba and get a large speedup.

Multiple Objectives

Instead of optimizing only the overall reward, we can add more objectives:

used time - to be minimized
used energy - to be minimized

This gives more insight into the tradeoffs between objectives. For example, if more time leads to less energy use and higher reward, we may want to reconsider the time limit used in the single-objective setup. We therefore adapted the objective function and applied the fcmaes MODE multi-objective optimizer. The diagrams below show two 2-dimensional projections of the resulting 3-dimensional Pareto front:

We used about 25 minutes and 8*10^8 evaluations for this optimization. Multi-objective optimization needs more function evaluations than BiteOpt to find a solution on the Pareto front with comparable reward. But it only needs a few seconds to reach rewards achieved by GA, PSO, or ACO. Note that this problem does not work well with differential evolution population update, in either the single-objective or multi-objective setting. MODE therefore has to be configured with 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

Can reinforcement learning be used to compute a Pareto front? It seems possible: https://arxiv.org/abs/1908.08342 . It would be interesting to apply that approach to UAV task assignment and compare the results.

How to replicate the 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

For large problem instances, MODE can use up to evals = 100000000 with workers=32 and popsize=512. Even on a fast 16-core CPU such as the AMD 5950x, optimization with these parameters takes about one hour. At that setting, multi-objective optimization also delivers excellent single-objective results similar to BiteOpt.

Conclusion

Before implementing a problem-specific optimization algorithm, first check whether a standard continuous optimizer is applicable. Our README contains many examples where this works well, including scheduling and task assignment problems. The 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 such as vehicle routing (VRTPW) or MKKP.

Implementing the objective function can still be tricky, especially for problems with discrete arguments. For Multi-UAV Task Assignment, both algorithm sequences perform exceptionally well.