Genetic programming to optimize 3D trajectories

STATUS: Working.

Finding the optimal trajectory in a 3D space is an ongoing research topic with applications such as optimizing an underwater route for a submarine robot or a flight route for drones. The problem becomes challenging as soon as the 3D space has barriers like danger zones or protected spaces. Those barriers can be modelled as features in GIS. A research gap to be closed is to combine the trajectory optimization techniques with GIS-modelled 3D barriers. Namely, the produced 3D-routes from the optimization techniques need a validation process to ensure that no barriers are crossed. Since many validations are necessary, one requirement is a fast computation.

The aim of this thesis is to solve the trajectory optimization problem with the artificial intelligence technique called "Genetic Programming" (GP). The produced trajectories are to be converted into geographical lines, which are tested for any interference with GIS-modelled 3D barriers.

Based on Hildemann (2020) and Hildemann & Verstegen (2023) 3D-Flight-Route-Optimization

How to use

Install all required packages (tested in Python 3.10 and 3.11)
Update configuration in cfg/default.yml
Pass additional arguments via command line (optional)
Provide/check test data in data/test_data_2d.py and data/test_data_3d.py
run main.py

Trajectory Optimisation
Study Area
Genetic Programming
- Parameters
Solution Transformation
Solution Validation
The Cost Function
Elitism
2-Dimensional Results
3-Dimensional Results

Trajectory Optimisation

Study Area

From CityOfNewYork/nyc-geo-metadata

Genetic Programming

Using Distributed Evolutionary Algorithms in Python

Parameters

Parameter	Type	Description
barriers	`str`	geofences dataset
origin	`str`	start point
destination	`str`	end point
global_max	`float`	global upper height limit
global_min	`float`	global lower height limit
enable_3d	`Bool`	allow navigation in 3 dimensions
ngen	`int`	number of generations to evolve through
nsegs	`int`	number of line vertices to use in solution validation
pop_size	`int`	population size to use in GP
cxpb	`float`	probability of two individuals reproducing
mutpb	`float`	probability of an individual mutating
max_height	`int`	height limit for function trees
max_length	`int`	length limit for function trees
init_min	`int`	minimum height for new trees
init_max	`int`	maximum height for new trees
mut_min	`int`	minimum height for mutation subtree
mut_max	`int`	maximum height for mutation subtree
elitism	`Bool`	implement elitism
dbl_tourn	`Bool`	use double tournament selection
tournsize	`int`	number of individuals per tournament
parsimony_size	`float`	weight of size in double tournament
fitness_first	`Bool`	evaluate fitness first in double tournament
patience	`int`	number of generations to wait for improvement
hof_size	`int`	number of individuals to save in HallOfFame
seed	`int`	random seed
multiproc	`str`	multiprocessing to use
chunksize	`int`	chunksize parameter for multiprocessing
threshold	`float`	max fitness to plot (factor of direct distance)
adaptive_mode	`Bool`	quantitatively validate trajectories
validation_3d	`str`	3D validation method to use
invalidity_cost	`exp`	penalty for intersection with `adaptive_mode=False`
intersection_cost	`exp`	penalty for intersection with `adaptive_mode=True`
delete_invalid	`Bool`	delete invalid solutions
no_log	`Bool`	don't save GP log
no_record	`Bool`	don't record results to table
verbose	`Bool`	output progress to console
no_plot	`Bool`	don't save results png
save_gif	`Bool`	save results gif
save_wkt	`Bool`	save result geometry as wkt
short_gif	`Bool`	only show stepwise improvement in gif
map_zoom	`float`	zoom level for solution map
sol_txt	`Bool`	save solution as txt
sol_png	`Bool`	save solution tree as png

Solution Transformation

Solution Validation

2-D validation is a simple intersection check using shapely

3-D intersection method can be specified in cfg:

Method Name	Description
`delaunay`	Uses `scipy.spatial.Delaunay.find_simplex` to check if line vertices plot within simplices
`shapely`	Uses `shapely` `intersection()`,then checks if the intersecting geometry lies within a min-max `z` range
`hulls_equal`	Uses `scipy.spatial.ConvexHull` to compare hulls with and without line vertices
`linprog`	Uses `scipy.spatial.ConvexHull` and simplex linprog
`triangles`	Uses the Möller–Trumbore algorithm to find intersections of lines and triangulated meshes

The Cost Function

Validation is dependent on non-intersection with barriers. Fitness is dependent on the length of the path and the solution size.

Also considered:

Path variation in z-dimension (less=better)
Solution evolve-time (earlier=better)

Elitism

Elitism can be activated via the elitism parameter. The number of elite individuals injected into the subsequent generation is determined by the HallOfFame size and is recommendeed to be 5-10% of the pop_size.