Waypoint Selection
A previous article1 introduced waypoints and trajectory smoothing for UAV swarms. This section focuses on waypoint selection.
The fight path management we propose is about the example of flying a fleet of drones around skyscrapers. The sample space can be considered a grid that must be navigated from one end to another and all intermediary spaces can be thought of as waypoints to occupy on the way to the other end and allowing the fleet to organize themselves around these intermediary points. By treating sub grids within grids as potential candidates to select from, a path can be forged with a sequence of sub grids to forge to the other end and the fleet organizes itself around each sub grid. The sub grids are pre-determined, invariant and uniform in size in each epoch.
Searching for the optimum intermediary point for the flight of the drones translates to the selection of waypoints by way of centroids of the sub grids. Each viable waypoint acts as a vector for various features such as potential gain towards eventual destination, safety, signal strength and wind effects. All information about adjacencies of sub grids as viable paths is known beforehand. Treating sub grids as nodes in a graph, and using depth first traversal for topological sort, it is possible to discover paths between start to finish. The approach outlined here uses a gradient descent method to determine the local optima given the waypoints as vectors. A quadratic form representing the waypoints as vectors is assumed to denote their initial matrix.
The solution to the quadratic form representing the embeddings is found by arriving at the minima represented by Ax = b using conjugate gradient method.
We are given input matrix A, b, a starting value x, a number of iterations i-max and an error tolerance epsilon < 1
This method proceeds this way:
set I to 0
set residual to b - Ax
set search-direction to residual.
And delta-new to the dot-product of residual-transposed.residual.
Initialize delta-0 to delta-new
while I < I-max and delta > epsilon^2 delta-0 do:
q = dot-product(A, search-direction)
alpha = delta-new / (search-direction-transposed. q)
x = x + alpha.search-direction
If I is divisible by 50
r = b - Ax
else
r = r - alpha.q
delta-old = delta-new
delta-new = dot-product(residual-transposed,residual)
Beta = delta-new/delta-old
Search-direction = residual + Beta. Search-direction
I = I + 1
The Jacobi iteration gives eigen values and eigen vectors.
No comments:
Post a Comment