Please enable JavaScript.
Coggle requires JavaScript to display documents.
Waveguide Routing Studies and Design, Search Algorithms - Coggle Diagram
Waveguide Routing Studies and Design
Constrains
Functional
connect an origin to a destination
specific orientations
manufactturing
formed bends: straight sections of the waveguide have a length larger than the width of the pliers
any straight section of a waveguide must have a minimal length (about 5 millimetres)
Conflict-avoidance
not conflict with an existing component or another waveguide of the payload
operability
a minimal distance must be respected
between a flange and the first bend
minimal distance must be respected between two waveguides (about 5 millimetres)
attachability
global attachability constraints that depend only on the sequence of bends used in the waveguide and are therefore intrinsic constraints
wall-dependent attachability constraints that depend on the walls on which the segments of the waveguide are routed. These constraints are said to be extrinsic.
Objectvie: Minimised length
methodologies
Cell Decomposition Approaches
the routing environment is discrete into a set of cells C
Regular grid / Quad Tree / Convex decomposition
Maze routing algorithms
(MRA): breadth-first search
LEE's algorithm: to solve 2D routing problems;
Similar to Dijkstra;s algorithm in the adjacency graph
Starting from the source cell, the best route for a pipe is computed by exploring in an adjacency graph of cells.
the undiscovered cells in the neighbourhood of a frontier until the target is reached.
Variants
more efficient. consume less memory
Knowledge based Engineering
Eg. the A* algorithm introduced by HART
Genetic algorithm
Genetic representation of a solution
chromosome represents a candidate route, defined as a vector of states;
five possible values: right/left/ up and down
potential energy assigned to each cell to guide the pipe
a function to generate new solutions
fitness function: satisfaction of constraints
selection function
crossover function
mutation function
Ant Colony Optimisation
decomposed into regular cubic cells and a potential energy is allocated
using individual ants that randomly route the pipe in the adjacency graph of cells.
Particle Swarm Optimisation
Contraint programming formulation
Line Search Algorithms
Skeleton Approach (SkA)
visibility graph
Voronoi's diagram
escape graph:
similar to Dijkstra's method in single route problem
Parametric Models
pattern routing
Search Algorithms
Efficiency evaluation
Completeness
optimality
time complexity
space complexicity