Drone Path Optimization with DEAP (Genetic Algorithm Example)

Drone Path Optimization with DEAP (Genetic Algorithm Example)

Drone path optimization is an essential problem in various applications, including delivery systems, surveillance, and agricultural monitoring.

One common problem is to find the shortest or most efficient path for a drone to travel between several waypoints (points of interest), which is a variation of the well-known Traveling Salesman Problem (TSP).

This example demonstrates how to solve a simplified version of the drone path optimization problem using the DEAP (Distributed Evolutionary Algorithms in $Python$) library with a genetic algorithm.

Problem Definition

We will solve the problem of a drone needing to visit a set of predefined waypoints and return to the starting point.

The goal is to minimize the total travel distance while visiting each waypoint exactly once.

This is equivalent to solving the TSP but applied in a drone context, where each waypoint is a geographical coordinate (x, y).

Genetic Algorithm Approach

A genetic algorithm ($GA$) is suitable for this type of optimization because of its ability to explore large search spaces.

In GA, we represent the possible solutions (paths) as individuals in a population.

The individuals evolve over generations based on their fitness, which in this case is the total travel distance of the path.

Steps

  1. Representation: Each individual in the population is a list of integers representing the order in which the drone visits the waypoints.
  2. Fitness Function: The fitness function calculates the total distance traveled by the drone. The shorter the total distance, the better the solution.
  3. Selection: Use tournament selection to choose the best individuals from the population.
  4. Crossover: Implement ordered crossover to combine two parent solutions and produce offspring.
  5. Mutation: Use a swap mutation to randomly change the order of the waypoints in an individual.
  6. Evolution: Repeat the selection, crossover, and mutation processes for multiple generations to evolve better solutions.

Example Code with DEAP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import random
import numpy as np
from deap import base, creator, tools, algorithms

# Generate random coordinates for waypoints
NUM_WAYPOINTS = 10
waypoints = np.random.rand(NUM_WAYPOINTS, 2) * 100  # Waypoints in 2D space (x, y)

# Calculate the distance between two points
def distance(p1, p2):
    return np.sqrt(np.sum((p1 - p2) ** 2))

# Fitness function: Total distance for the drone to visit all waypoints and return to start
def evaluate(individual):
    total_distance = 0
    for i in range(len(individual) - 1):
        total_distance += distance(waypoints[individual[i]], waypoints[individual[i + 1]])
    # Return to starting point
    total_distance += distance(waypoints[individual[-1]], waypoints[individual[0]])
    return (total_distance,)

# Set up the DEAP framework
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))  # Minimize total distance
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("indices", random.sample, range(NUM_WAYPOINTS), NUM_WAYPOINTS)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Genetic algorithm operators
toolbox.register("mate", tools.cxOrdered)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evaluate)

# Parameters
POPULATION_SIZE = 300
CXPB, MUTPB, NGEN = 0.7, 0.2, 100  # Crossover, Mutation, Generations

# Main function
def main():
    # Create an initial population
    population = toolbox.population(n=POPULATION_SIZE)
    
    # Run the genetic algorithm
    halloffame = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("min", np.min)
    stats.register("avg", np.mean)
    
    algorithms.eaSimple(population, toolbox, cxpb=CXPB, mutpb=MUTPB, ngen=NGEN, 
                        stats=stats, halloffame=halloffame, verbose=True)
    
    # Best solution
    best_individual = halloffame[0]
    print("Best individual (path):", best_individual)
    print("Best fitness (total distance):", evaluate(best_individual)[0])

if __name__ == "__main__":
    main()

Explanation of the Code

  1. Waypoints: We generate random waypoints in a $2D$ space using np.random.rand().
    These represent the locations the drone needs to visit.
  2. Distance Calculation: The function distance() computes the Euclidean distance between two waypoints.
  3. Fitness Function: The evaluate() function computes the total travel distance for a given order of waypoints (represented by an individual).
    The individual starts at the first waypoint, visits all other waypoints, and returns to the starting point.
  4. Genetic Algorithm Setup:
    • Individuals: Each individual represents a possible order in which the drone visits the waypoints.
    • Selection: Tournament selection is used to choose individuals for crossover.
    • Crossover: Ordered crossover (cxOrdered) is used to combine two parents while maintaining valid waypoint orders.
    • Mutation: The mutation function randomly swaps two waypoints in the path to introduce variation.
  5. Evolution: The population evolves over $100$ generations, with crossover occurring $70$% of the time and mutation $20$% of the time.
  6. Best Solution: After the evolution, the best individual (path) is displayed, along with its total travel distance (fitness).

Running the Code

When you run the code, the genetic algorithm evolves the population over generations, and you will see output showing the best and average fitness values for each generation. After the evolution completes, the best path and its corresponding total distance will be printed.

Result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
gen	nevals	min    	avg    
0  	300   	370.117	613.888
1  	231   	369.707	545.362
2  	221   	323.565	509.15 
3  	228   	323.565	496.39 
4  	245   	323.565	482.039
5  	224   	333.775	466.763
6  	217   	333.775	453.389
7  	229   	302.401	448.986
8  	230   	309.616	453.986
9  	223   	280.492	448.145
10 	248   	280.492	437.156
11 	234   	279.178	431.206
12 	225   	279.178	432.828
13 	223   	279.178	427.017
14 	225   	279.178	411.918
15 	229   	279.178	403.974
16 	237   	279.178	397.017
17 	232   	279.178	375.884
18 	231   	279.178	389.703
19 	229   	279.178	375.877
20 	254   	279.178	384.408
21 	221   	279.178	372.023
22 	231   	279.178	369.89 
23 	225   	279.178	367.805
24 	235   	279.178	361.98 
25 	233   	279.178	348.047
26 	214   	279.178	337.942
27 	239   	279.178	339.483
28 	212   	279.178	329.376
29 	236   	279.178	337.442
30 	230   	279.178	334.522
31 	240   	279.178	349.702
32 	228   	279.178	343.505
33 	236   	279.178	346.411
34 	229   	279.178	337.819
35 	230   	279.178	331.493
36 	232   	279.178	326.055
37 	232   	279.178	315.221
38 	242   	279.178	317.901
39 	247   	279.178	319.78 
40 	220   	279.178	317.454
41 	223   	279.178	322.569
42 	215   	279.178	319.193
43 	227   	279.178	316.175
44 	226   	279.178	322.37 
45 	222   	279.178	305.492
46 	241   	279.178	319.94 
47 	236   	279.178	318.08 
48 	228   	279.178	318.667
49 	214   	279.178	311.566
50 	237   	279.178	319.163
51 	240   	279.178	323.339
52 	218   	279.178	315.869
53 	233   	279.178	316.79 
54 	223   	279.178	316.664
55 	228   	279.178	316.682
56 	228   	279.178	319.589
57 	222   	279.178	318.324
58 	223   	279.178	313.142
59 	223   	279.178	311.497
60 	222   	279.178	321.154
61 	237   	279.178	316.062
62 	235   	279.178	318.168
63 	222   	279.178	320.646
64 	232   	279.178	315.187
65 	235   	279.178	314.302
66 	247   	279.178	313.788
67 	226   	279.178	310.027
68 	229   	279.178	318.217
69 	238   	279.178	320.111
70 	248   	279.178	323.46 
71 	220   	279.178	314.051
72 	227   	279.178	314.123
73 	221   	279.178	318.087
74 	228   	279.178	323.188
75 	227   	279.178	315.978
76 	230   	279.178	319.116
77 	226   	279.178	317.263
78 	214   	279.178	317.908
79 	222   	279.178	317.084
80 	240   	279.178	331.903
81 	256   	279.178	326.126
82 	243   	279.178	317.302
83 	235   	279.178	321.809
84 	227   	279.178	314.31 
85 	219   	279.178	313.892
86 	236   	279.178	322.307
87 	232   	279.178	322.76 
88 	230   	279.178	319.549
89 	216   	279.178	322.411
90 	228   	279.178	320.033
91 	234   	279.178	318.53 
92 	235   	279.178	314.02 
93 	219   	279.178	314.744
94 	223   	279.178	322.867
95 	231   	279.178	314.336
96 	208   	279.178	326.721
97 	221   	279.178	320.099
98 	215   	279.178	319.931
99 	218   	279.178	309.452
100	215   	279.178	318.16 
Best individual (path): [5, 9, 0, 2, 6, 1, 7, 4, 8, 3]
Best fitness (total distance): 279.1776451064892

The genetic algorithm ($GA$) has successfully found an optimized solution for the drone path optimization problem.
Let’s break down the results in detail:

Generational Summary

  • Generations (gen): The algorithm ran for a total of $100$ generations.
    Each generation represents one iteration of the genetic algorithm, where the population of potential solutions evolves through selection, crossover, and mutation.
  • Evaluations (nevals): This column represents how many individuals were evaluated in each generation.
    The typical number is around $220$-$250$ evaluations per generation.
  • Minimum Fitness (min): The “min” column represents the fitness of the best individual in each generation.
    Fitness in this context is the total travel distance for the drone’s path (lower is better since we are minimizing distance).
    The best fitness starts at $370.117$ in generation $0$ and improves steadily, eventually reaching the optimal value of $279.178$ around generation $11$.
  • Average Fitness (avg): The “avg” column shows the average fitness of all individuals in the population for that generation. This provides an indication of the overall quality of the population.
    Initially, the average fitness starts around $613.888$, and as the generations progress, it improves significantly to about $318.160$ by the end.

Key Observations

  1. Initial Population: In the first generation, the best individual has a total distance of $370.117$, and the average distance of the population is much higher at $613.888$.
    This suggests that the initial population was quite far from the optimal solution, which is typical in $GA$.

  2. Rapid Improvement: By generation $9$, the best individual already achieves a total distance of $280.492$.
    From generation $11$ onwards, the best solution achieves a total distance of 279.178, which remains the minimum for the rest of the evolution process.
    This shows that the algorithm found an optimal or near-optimal solution early in the process.

  3. Stabilization: After generation $11$, the best individual does not improve further, and the population’s average fitness continues to improve but stabilizes.
    This means that while many individuals in the population are becoming closer to the optimal solution, the algorithm is no longer finding a significantly better path.

  4. Best Path: The final result gives the best path found by the algorithm:

    1
    [5, 9, 0, 2, 6, 1, 7, 4, 8, 3]

    This is the sequence of waypoints the drone should visit to minimize its travel distance. The total distance traveled for this path is 279.178 units.

Conclusion

The genetic algorithm performed well in solving the drone path optimization problem.
After $100$ generations, it found an optimal path with a total travel distance of 279.178.

The algorithm quickly converged to this solution within the first $10$-$20$ generations, indicating efficient exploration of the solution space.

The result demonstrates how $GA$s can be an effective method for solving complex optimization problems like the Traveling Salesman Problem ($TSP$) applied to drone navigation.

If needed, this process can be extended to include additional constraints such as energy usage, obstacles, or even dynamic weather conditions, which would further challenge the optimization.

Extensions

  • Wind and Battery Constraints: In more realistic drone optimization problems, you might need to incorporate constraints like wind speed, battery life, and no-fly zones.
    These can be added as part of the fitness function or as additional constraints in the GA.
  • 3D Coordinates: If the drone operates in $3D$ space, the waypoints can be extended to include altitude $(x, y, z)$, and the distance function would need to account for this.

This example showcases how genetic algorithms, through $DEAP$, can be effectively applied to optimize complex path-planning problems such as drone navigation.