Systems and methods for automated route planning including approximating a Pareto front

A system for automated route planning comprising:

• a processor and memory storing instructions that, when executed, cause the processor to:
• receive input data relating to a route planning problem for navigating through an operational area containing obstacles, the input data including a starting location, a destination location, obstacle locations, and operative parameters including at least one safety constraint and at least one mission objective, wherein at least two of the operative parameters are in conflict such that improving a first of the at least two operative parameters degrades a second of the at least two operative parameters;
• generate an initial population of candidate routes by applying a reference frame topological graph (RFTG) algorithm that:
• selects obstacle points and a reference point in the operational area;
• constructs reference frame lines extending from each obstacle point through the reference point;
• partitions the operational area into connected regions separated by the reference frame lines and the obstacles;
• generates a topological graph having vertices representing the connected regions and edges representing boundary segments between adjacent connected regions;
• and
• generates a plurality of candidate routes, each candidate route corresponding to a distinct walk through the topological graph from the starting location to the destination location, wherein each distinct walk represents a different homotopy class that navigates around the obstacles in a topologically different manner;
• approximate a Pareto front using a multi-objective evolutionary algorithm (MOEA) that iteratively evaluates and selects routes from the initial population based on the operative parameters, wherein the Pareto front represents routes that balance tradeoffs between the at least two operative parameters that are in conflict;
• apply a spectral clustering algorithm to the Pareto front to:
• construct an affinity matrix representing similarities between routes in the Pareto front;
• calculate a graph Laplacian from the affinity matrix;
• determine eigenvectors corresponding to smallest eigenvalues of the graph Laplacian;
• and
• partition the Pareto front into a predetermined number of clusters, wherein each of the clusters represents a route archetype;
• generate a graphical user interface displaying at least one representative route from each cluster as a selectable navigation option;
• and
• display the graphical user interface on a visual display device.