Hybridization Graph Solvers (HGraph)

The HGraph (Hybridization Graph) module provides meta-solver capabilities that combine candidate solution paths from multiple runs or distinct base solvers into an optimal hybrid path. HGraph decomposes candidate paths into valid segments, constructs a hybridization graph of intersecting subpaths, and solves for the shortest bottleneck or total length path across all candidate combinations.

Architectural Design & Meta-Factory Pattern

  • Meta-Class Pattern: Uses MetaHGraphSolver.make_hgraph_solver_class(BaseSolver) to dynamically generate a hybrid solver class wrapping an underlying planner.

  • Component Interactions: 1. Executes the underlying base solver (e.g., PRM or RRT) to generate initial candidate paths. 2. Extracts path segments and computes segment-to-segment intersections using discopygal.geometry_utils.collision_detection. 3. Constructs an H-graph where vertices represent path intersection points and edges represent valid path sub-segments. 4. Runs graph search to extract an optimal composite path superior to any individual candidate solution.

digraph hgraph_pipeline { rankdir=TB; node [fontname="Helvetica", fontsize=10, margin="0.15,0.1"]; edge [fontname="Helvetica", fontsize=9]; candidates [label="Multiple Candidate Paths\n(from Base Solver runs)", shape=ellipse, style=filled, fillcolor="#E3F2FD", color="#1565C0"]; intersect [label="Segment Intersection & Portal Analysis\n(discopygal.geometry_utils)", shape=box, style="filled,rounded", fillcolor="#BBDEFB", color="#1976D2"]; hgraph_build [label="Hybridization Graph (HGraph) Construction\n(discopygal.solvers.hgraphs)", shape=box, style="filled,rounded", fillcolor="#C8E6C9", color="#2E7D32"]; search [label="Shortest Path Search on Hybrid Graph\n(search_algo.a_star)", shape=box, style="filled,rounded", fillcolor="#FFF3E0", color="#E65100"]; output [label="Optimal Hybrid Path Collection\n(PathCollection)", shape=ellipse, style=filled, fillcolor="#CE93D8", color="#7B1FA2"]; candidates -> intersect; intersect -> hgraph_build; hgraph_build -> search; search -> output; }

Hybridization Graph (HGraph) Pipeline

Concrete HGraph Solvers

  1. HGraph for PRM: discopygal.solvers.hgraphs.HGraph_PRM Combines candidate paths generated by repeated PRM roadmap queries.

  2. HGraph for RRT: discopygal.solvers.hgraphs.HGraph_RRT Combines candidate paths generated by repeated RRT tree expansions.

API Reference

class discopygal.solvers.hgraphs.HGraph(solver_class: <module 'discopygal.solvers_infra.Solver' from 'C:\\Users\\ofeqor\\dev\\discopygal\\src\\discopygal\\solvers_infra\\Solver.py'>, num_paths, neighborhood_distance, **kwargs)

Bases: SamplingSolver

A generic HGraph Solver. Receives a solver class which is the specific solver that is used to construct each path and for the local connector.

Parameters:

  • solver_class (Solver) – The specific solver class to use for the HGraph algorithm (to construct the paths and for the local connector).

  • num_paths – The number of solutions (paths) to construct

  • neighborhood_distance (FT) – The radius of the local neighborhood to seek and connect optional bridges.

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

get_potential_bridges(path1, path2)

Return all pairs of points between two paths that are close enough to connect a bridge between them.

Parameters:
local_connector(v1, v2, roadmap)

Use solver_class to locally connect to points v1 and v2, on roadmap

Parameters:

  • v1 (Point_d) – First point

  • v2 (nx.Graph) – Second point

  • roadmap – The roadmap to add the edges of the local path

class discopygal.solvers.hgraphs.HGraph_PRM(**kwargs)

Bases: MetaHGraphSolver

solver_class

alias of PRM

class discopygal.solvers.hgraphs.HGraph_RRT(**kwargs)

Bases: MetaHGraphSolver

solver_class

alias of RRT

class discopygal.solvers.hgraphs.MetaHGraphSolver(**kwargs)

Bases: HGraph

A meta class to create specific HGraph solvers (HGraph solver based on specific solver class)

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

static make_hgraph_solver_class(solver_class)
Create a specific HGraph solver class from given solver_class.
Name of the class will be: HGraph_<solver_class_name>
Parameters:

solver_class – The solver class to make a HGraph solver based on it

Returns:

The new created solver class

Return type:

HGraph