Bottleneck Tree & Fréchet Matching Solvers¶

The Bottleneck Tree module implements specialized optimal motion planning algorithms based on the Bottleneck-Tree framework (Solovey et al., 2016). It minimizes bottleneck path metrics (e.g., maximum distance between configurations, maximum clearance deviation) rather than standard additive path length, making it ideal for multi-robot path coordination along pre-defined curves.

Architectural Design & Component Breakdown¶

bottleneck_tree.py: Abstract bottleneck tree search framework. Operates on custom cost maps ( $C: V \times V \to \mathbb{R}$ ) to compute bottleneck-optimal path trees.
frechet_matching.py: Concrete solver applying bottleneck tree search to Fréchet matching across $N$ continuous curves.
three_curve_frechet.py: Sampling-based Fréchet matching solver restricted to exactly three curves, computing reachable free space regions on 3D grid faces.
exact_three_curve_frechet.py: Deterministic counterpart to 3-curve Fréchet matching, computing exact free-space cell boundary arrangements.

Bottleneck Tree & Fréchet Matching Architecture¶

Bottleneck Tree Base Framework¶

class discopygal.solvers.bottleneck_tree.bottleneck_tree.BottleneckTree(num_landmarks_in_parameter_space: int, radius: FT, solver_class, avoid_collisions: bool, grid_size: int, intermediate_path_points: list[list[tuple[float, float]]] = None, **kwargs)¶

Bases: SamplingSolver

Parameters:

num_landmarks_in_parameter_space – How many random points to sample on parameter space
radius – Connection radius of points in parameter space
grid_size – The size of grid in each dimension on parameter space to also add as sampled points
solver_class – Solver algorithm for paths, takes effect only if the intermediate points parameter is completely empty or $None$ (not even $[]$ ). In this case it determines the type of solver that will run at the beginning to generate paths for the robots.
avoid_collisions – Should avoid collisions, Are the robots allowed to collied or not
intermediate_path_points – Path points except of start and end of list of lists of points (point as tuple of two floats)

build_roadmap()¶

Constructs the roadmap of points in the configuration space which a path will be searched on to find a solution. Every sampling solver should implement how to build the roadmap.

Returns:: The built roadmap. Each node represents a point in configuration space (dimension = 2*robots_num)
Return type:: Roadmap

classmethod get_arguments()¶

Return a list of arguments and their description, defaults and types. Can be used by a GUI to generate fields dynamically. Should be overridded by solvers.

Returns:: arguments dict
Return type:: dict

sample_point_in_parameter_space(start_values=None, end_values=None)¶: Sample a point with each coordinate between the given start value and end value pair, i.e. for coordinate i sample a value between start_values[i] and end_values[i].

search_path_on_roadmap()¶

After already constructed a roadmap, plan a path for each robot (i.e. return paths for all the robots) If failed to find a path for each robot return an empty PathCollection (PathCollection())

The search method of the basic class SamplingSolver is simply finding the shortest path according to the weights of the edges (the weight attribute should be called weight)

Returns:: Path collection of motion planning (path for each robot)
Return type:: PathCollection

Frechet Matching Solver¶

An important concrete solver here is the Frechet solver, which handles Frechet matching for any number of curves.

class discopygal.solvers.bottleneck_tree.frechet_matching.FrechetMatching(num_landmarks_in_parameter_space: int, radius: FT, solver_class, avoid_collisions: bool, grid_size: int, intermediate_path_points: list[list[tuple[float, float]]] = None, **kwargs)¶

Bases: BottleneckTree

on_gui_load(gui, layout)¶: Callback that will be called when solver is loaded at Solver Viewer

search_path_on_roadmap()¶

After already constructed a roadmap, plan a path for each robot (i.e. return paths for all the robots) If failed to find a path for each robot return an empty PathCollection (PathCollection())

The search method of the basic class SamplingSolver is simply finding the shortest path according to the weights of the edges (the weight attribute should be called weight)

Returns:: Path collection of motion planning (path for each robot)
Return type:: PathCollection

discopygal.solvers.bottleneck_tree.frechet_matching.solve_frechet_problem(paths, solver_class, with_gui=False, solver_kwargs={})¶

Create a scene (without obstacles) with given polygonal paths as list of points (tuple or Point_2) and solve with using the given solver class and it’s arguments.

Parameters:

paths (list) – The paths of the robots as a list of lists of points. Each point can be a tuple or Point_2
solver_class – The class of the solver to create
with_gui (bool) – should start solver_viewer with the given scene and solver or solve without gui.
solver_kwargs (dict) – Keyword arguments to pass to the solver when initializing it.

Returns:

The solver object after solving the scene

Return type:

Solver

Three Curve Frechet Solver¶

A sampling-based solver for exactly three curves that finds the reachable area on a given face.

class discopygal.solvers.bottleneck_tree.three_curve_frechet.ThreeCurveFrechet(index_of_fixed_robot: int, curves_nodes: list[int, int, int], max_bottleneck: FT, num_of_end_points_per_segment: int, visualize_result=False, **kwargs)¶

Bases: FrechetMatching

analyze_solution(path_collection)¶

Print info about the found solution - path_collection.

Prints: distance of path of each robot, total distance of all paths (sum of all paths) and makespan

Parameters:: path_collection (PathCollection) – The path_collection to print info for

classmethod get_arguments()¶

Return a list of arguments and their description, defaults and types. Can be used by a GUI to generate fields dynamically. Should be overridded by solvers.

Returns:: arguments dict
Return type:: dict

get_end_points()¶: Produce pointes on selected face

search_path_on_roadmap()¶

After already constructed a roadmap, plan a path for each robot (i.e. return paths for all the robots) If failed to find a path for each robot return an empty PathCollection (PathCollection())

The search method of the basic class SamplingSolver is simply finding the shortest path according to the weights of the edges (the weight attribute should be called weight)

Returns:: Path collection of motion planning (path for each robot)
Return type:: PathCollection

Exact Three Curve Frechet Solver¶

Same solver as the one above, except that this one computes the reachable area in an exact way using arrangement face geometry.

class discopygal.solvers.bottleneck_tree.exact_three_curve_frechet.ExactThreeCurveFrechet(index_of_fixed_robot: int, curves_nodes: list[int, int, int], max_bottleneck: FT, num_of_end_points_per_segment: int, visualize_result=False, **kwargs)¶

Bases: ThreeCurveFrechet

compute_initial_feasible_area(nodes: tuple[int], face_direction: FaceDirection) → Arrangement_on_surface_2¶: Returns an arrangement where the faces with data True are the desired area

compute_max_parameter_from_point(center: Point_2, dist: FT, path: Path)¶: Compute the max parameter in $path$ the is still in distance $dist$ from $center$ $int(parameter)$ is the segment index in the path $parameter - int(parameter)$ is the fraction passed in the segment

compute_reachable_area_of_two_robots(nodes: tuple[int], face_direction: FaceDirection) → Arrangement_on_surface_2¶: Returns an arrangement where the faces with data True are the desired area

get_arrangement()¶

Return an arrangement (if applicable). | Can be overridded by solvers. | When dispalying the arrangement faces with data >= 0 will be colored green and faces with data < 0 will be colored red.

Returns:: arrengement
Return type:: Arrangement_2

on_gui_load(gui, layout)¶: Callback that will be called when solver is loaded at Solver Viewer

validate_result() → bool¶: Validate the result arrangement against the result of sampled algorithm

class discopygal.solvers.bottleneck_tree.exact_three_curve_frechet.FaceDirection(*values)¶

Bases: Enum

static axis_to_incoming_face(axis: Axis)¶: Return the direction of the incoming face perpendicular to the given axis

static axis_to_outgoing_face(axis: Axis)¶: Return the direction of the outgoing face perpendicular to the given axis

global_axis_to_local_axis(axis: Axis) → Axis¶: Convert an axis of X,Y,Z to axis X or Y as follows: the horizontal axis is X and the vertical axis is Y

property horizontal_axis: Axis¶: The first parallel axis of the face

nodes_of_neighbor(nodes_of_face: tuple[int, int, int]) → tuple[int, int, int]¶

For a given box return the nodes of the box in the direction of $self$ .

Parameters:: nodes_of_face (tuple[int, int, int]) – The nodes of the box given by it’s bottom-back-left nodes.
Returns:: The neighbor’s nodes
Return type:: tuple[int, int, int]

property vertical_axis: Axis¶: The second parallel axis of the face