DiscoPygal Architecture Overview

This document is a technical architecture manual for DiscoPygal: how the system is decomposed into layers, which module owns which responsibility, how a scene becomes a verified solution, and where to plug in when extending the framework.

DiscoPygal is a Python framework for 2D single- and multi-robot motion planning. It is built on top of CGAL (through the CGALPY bindings), so exact rational arithmetic is available all the way from the geometric primitives up to the planners.

Two distributions live in this repository:

• src/discopygal — the installable library package.

• tools/ — standalone desktop applications (Solver Viewer, Scene Designer) that are consumers of the library, shipped alongside it rather than inside it.

System Architecture & Layering Model

The stack isolates low-level geometric arithmetic from planning algorithms, and both of those from the user interface. Each layer depends only on the layers beneath it.

System Architecture & Layering Model

Note

discopygal.solvers_infra imports discopygal.gui.color for the default robot and obstacle colors. This is the one place where the infrastructure layer reaches “sideways” into the GUI package, and it is a pure constants dependency — no Qt widgets are involved in loading a scene.

Package Map & Inter-Module Dependencies

Subpackages and File Breakdown

Subpackage	Core Files	Responsibilities & Dependencies
discopygal.bindings	__init__.py	Imports two CGALPY builds and re-exports their kernel, arrangement, polygon and spatial-search types. Subclasses Ker.FT and Ker.Segment_2 to add Python arithmetic and constructor conveniences. Depended on by every other layer.
discopygal.geometry_utils	collision_detection.py, conversions.py, arrangement_operations.py, bounding_boxes.py, transform.py, display_arrangement.py	Collision predicates, type conversions between CGAL/Python/tensor representations, arrangement construction and overlay, scene bounding boxes, and polygon offsetting. Depends on bindings.
discopygal.solvers_infra	__init__.py, Solver.py, SamplingSolver.py, roadmap.py, implicitroadmap.py, samplers.py, metrics.py, nearest_neighbors.py, search_algo.py, verify_paths.py, operations_counter.py, heuristic_parser.py, tensor_solver/	Scene data model, abstract solver contracts, roadmap graphs, and the pluggable sampler / metric / nearest-neighbor strategies. Depends on bindings, geometry_utils and gui.color.
discopygal.solvers	rrt/, prm/, exact/, staggered_grid/, lattice_solver/, bottleneck_tree/, revolving_areas/, hgraphs.py, mapf.py	Concrete planners, plus the solver registry in __init__.py that discovers and loads solver classes by name. Depends on solvers_infra.
discopygal.experiments	scenarios_runner.py, run_experiment.py, __init__.py	Batch execution of solvers over scenario suites with per-run timeouts and process isolation; aggregates results into pandas frames. Depends on solvers and solvers_infra.
discopygal.gui	gui.py, GraphicsScenePlus.py, MainWindowsPlus.py, Worker.py, color.py, logger.py, RDisc.py, RPolygon.py, RSegment.py, …	PySide6 building blocks: a base GUI window class, a zoomable graphics scene, a QRunnable worker, and one wrapper class per drawable CGAL shape.
tools/ (top-level, not part of the package)	solver_viewer/, scene_designer/, ui_helpers.py	End-user applications built on discopygal.gui. Added to sys.path separately by docs/conf.py and by the entry-point scripts.

Detailed File Outlines & Component Relations

1. CGALPY Bindings Layer (discopygal.bindings)

__init__.py is the single bridge between the compiled CGALPY extension modules and the rest of the Python code. Its defining characteristic is that it loads two CGALPY builds and merges them into one namespace:

The two CGALPY builds

Alias	Build	Role
CGALPY_SEG	…_aos2SegVeHeFePl_bso2_ch2_ms2_pol2_ss2	Segment arrangement traits. The default everywhere no circular arc is involved. It is also the only build shipping the Minkowski sums module (Ms2).
CGALPY_CS	…_aos2CsVeHeFePl_bso2_ch2_pol2_ss2	Circle-segment traits. The only build that can hold circular arcs (expanded discs, approximated offsets). Its types are exported with a _circle suffix.

Both builds share the same kernel, polygon and spatial-search types, so Point_2, Point_d and Polygon_2 are unambiguous. The arrangement traits, however, cannot be mixed within a single arrangement or overlaid with one another — choosing the right flavour is a real design constraint for any solver that builds arrangements.

• Exported CGAL modules: Ker (kernel), Aos2 / As2 (arrangements, segment and circle-segment traits), Pol2 (polygons), Ss (spatial search), Bso2 (boolean set operations), Ms2 (Minkowski sums).

• Exported types: Point_2, Point_d, Segment_2, Line_2, Circle_2, Vector_2, Polygon_2, Polygon_with_holes_2, Polygon_set_2, Arrangement_2, Arrangement_on_surface_2, X_monotone_curve_2, Curve_2, TPoint, Kd_tree, K_neighbor_search, Fuzzy_sphere, Aff_transformation_2, FT, Gmpq.

• Python-side subclasses:

  • FT(Ker.FT) — overrides the arithmetic dunders (__add__, __sub__, __mul__, __truediv__ and their in-place/reflected forms, generated by the create_method / create_imethod helpers) so exact field elements interoperate with plain Python int and float. It also accepts str, converting through float first.

  • Segment_2(Ker.Segment_2) — constructor conveniences over the raw binding.

2. Geometric Utilities Layer (discopygal.geometry_utils)

• ``collision_detection.py`` — the workhorse of validity checking.

  • Classes: ObjectCollisionDetection (built per robot from the scene’s obstacles; exposes is_point_valid() and is_edge_valid()), ArrTraits (a NamedTuple selecting the arrangement flavour for a given robot/obstacle combination, via scene_traits()).

  • Functions: collide_two_robots(), collide_disc_with_disc(), collide_disc_with_polygon(), collide_disc_with_rod().

  • Relations: Roadmap holds one ObjectCollisionDetection per robot; verify_paths.py rebuilds them independently to re-validate a finished solution.

• ``conversions.py`` — the bridge between single-robot 2D primitives and the composite configuration space.

  • Functions: Point_2_to_xy() / xy_to_Point_2(), FT_to_float() / float_to_FT() / to_FT(), Polygon_2_to_array_of_points() / array_of_points_to_Polygon_2(), create_segment_2(), to_TPoint(), point_to_coordinate().

  • Tensor multiplexing: Point_2_list_to_Point_d() and Point_d_to_Point_2_list() (and the generalized Point_k_list_to_Point_d() / Point_d_to_Point_k_list()) pack per-robot configurations into one Point_d and unpack them again. This pair is what makes multi-robot planning a single-graph search.

  • Serialization: graph_to_dict() / graph_from_dict() and arrangement_to_dict() / arrangement_from_dict() make roadmaps and arrangements picklable — required for sending results across process boundaries.

• ``arrangement_operations.py`` — 2D arrangement construction and algebra.

  • Constructors: empty_arrangement(), copy_arrangement(), make_arrangement_polygon_from_points(), make_rectangle_arrangement(), make_ellipse_arrangement(), make_conic_curve_arrangement().

  • Algebra: overlay_arrangements(), union_arrangements(), intersect_arrangements(), intersect_arrangement_with_segment(), add_segment_to_arrangement(), clean_redundant_curves().

  • Analysis: project_curve_to_axis() / project_arrangement_to_axis() (with the Axis enum), maximum_point_of_curve() / minimum_point_of_curve(), find_local_minimal_points(), find_monotone_area_of_curve() / find_monotone_area_of_arrangement(), ellipse_max_min_points(), solve_quadratic(), union_intervals(), mark_true_all_bounded_faces().

  • Relations: the backbone of the exact solvers and of the bottleneck-tree / Fréchet family, which reason on free-space arrangements rather than on samples.

• ``bounding_boxes.py`` — calc_scene_bounding_box(scene) returns the BoundingBox enclosing all robots and obstacles. load_scene() calls it and hands the result to the sampler, which is how sampling domains get scoped.

• ``transform.py`` — offset_polygon(polygon, offset), used to grow obstacles by a robot’s radius (configuration-space obstacles).

• ``display_arrangement.py`` — debug visualizer. GUIArrangement plus display_arrangement() render an arrangement in a standalone Qt window, with per-curve-type converters (segment_to_qt_args(), circle_segment_to_qt_args(), ellipse_segment_to_qt_args()).

3. Solver Infrastructure Layer (discopygal.solvers_infra)

• ``__init__.py`` — the scene data model. This is where the domain objects live (a common misconception is that they live in Solver.py).

  • Robots: Robot (abstract, carries start, end, data and a stable _obj_id that survives serialization), RobotDisc, RobotPolygon, RobotRod.

  • Obstacles: Obstacle, ObstacleDisc, ObstaclePolygon.

  • Scene: Scene — robots + obstacles + metadata, with a documented JSON serialization format (__class__-tagged dicts, resolved by load_object_from_dict()).

  • Solutions: PathPoint, Path (points + metric), PathCollection (dict of robot → path; pads paths to equal length and computes time lengths).

  • Rendering helper: SceneDrawer.

• ``Solver.py`` — the abstract base contract.

  • Classes: Solver; the Trait enum and add_traits() class decorator, which declare what a solver accepts (ACCEPTS_MULTIPLE_ROBOTS, ACCEPTS_DISC_ROBOT, ACCEPTS_ROD_ROBOT, …) so the GUI can filter solvers against the loaded scene.

  • Lifecycle: load_scene() stores the scene and computes the bounding box; _solve() is the abstract hook each planner implements; solve() is the non-overridable public entry point that loads (if given a scene), delegates to _solve(), and optionally calls analyze_solution().

  • Introspection: get_arguments() returns {name: (label, default, type)}; init_solver() / init_default_solver() build an instance from string arguments by casting through that table. This is what lets the Solver Viewer generate parameter forms with no solver-specific UI code.

  • Bounding box policy: bounding_margin_width_factor — 0 for a tight box, NO_BOUNDING_BOX (-1, the default) for none.

• ``SamplingSolver.py`` — base class for sampling-based planners.

  • Holds the three injected strategies: nearest_neighbors_class (default NearestNeighbors_sklearn), metric (default Metric_SumDist) and sampler (default Sampler_Uniform).

  • Overrides ``load_scene()`` to also multiplex all robot starts/ends into self.start / self.end as Point_d, and to call build_roadmap().

  • build_roadmap() is abstract; init_roadmap() is a convenience constructor; search_path_on_roadmap() runs a shortest-path query over the roadmap graph (via the networkx wrappers has_path(), shortest_path(), shortest_path_length()) and de-multiplexes the tensor path back into a PathCollection.

• ``roadmap.py`` — Roadmap stores sampled configurations and motion edges in a networkx Graph (or DiGraph when is_directed). All vertices are Point_d of dimension (single-robot dimension) × (number of robots). It composes a Sampler, a Metric, a per-robot ObjectCollisionDetection, and a NearestNeighbors backend wrapped in NearestNeighborsCached. Key methods: is_point_valid(), add_point(), add_sampled_point(), and collision-checked edge insertion.

• ``implicitroadmap.py`` — ImplicitRoadmap, for search spaces too large to materialize: neighbors are generated on demand rather than stored.

• ``samplers.py`` — Sampler (abstract: set_scene(), sample(), update_params()), Sampler_Uniform, SamplerWithAngle (adds an orientation coordinate, for rod robots), Sampler_Elliptical (for informed / focused sampling).

• ``metrics.py`` — Metric (abstract, with MetricNotImplemented for unsupported point types), Metric_Euclidean, Metric_SumDist (sum of per-robot distances — the multi-robot default), RodDisplacementMetric. Metrics expose both a distance function and a matching sklearn/CGAL metric name so the nearest-neighbor backends stay consistent with edge weights.

• ``nearest_neighbors.py`` — NearestNeighbors (interface: fit(), k_nearest(), neighbors_in_radius()), NearestNeighbors_sklearn, NearestNeighbors_CGAL (CGAL Kd_tree), NeighborsFinder, and NearestNeighborsCached — a decorator that batches insertions and defers the expensive fit() until a query actually needs it.

• ``search_algo.py`` — GraphNode and Graph(ImplicitRoadmap), implementing multi-heuristic MRMH-A* over an implicit multi-resolution roadmap, with one Fibonacci heap per heuristic and round-robin queue selection. Note that ordinary sampling solvers do not go through this module — they use the networkx shortest-path helpers in SamplingSolver.py.

• ``heuristic_parser.py`` — parses the heuristic specifications used by search_algo.Graph.

• ``verify_paths.py`` — verify_paths(scene, paths) returns (bool, reason). It re-checks every robot’s edges against the obstacles, asserts all paths share a length, tests every pair of robots for collision at every time step, and confirms the endpoints match each robot’s declared start/end.

• ``operations_counter.py`` — OperationsCounter, a class-level profiling registry with the count_calls() decorator and count_call_context() context manager. Solver.__init__ clears it, so every solver run starts from zero.

• ``tensor_solver/`` — TensorSolver(SamplingSolver) and TensorRoadmap. The tensor approach builds one 2D roadmap per robot, then searches the tensor product of those roadmaps rather than a single composite roadmap. TensorSolver inverts the usual hooks: subclasses implement build_robot_roadmap(robot) and search_tensor_roadmap() instead of build_roadmap().

4. Concrete Solvers Layer (discopygal.solvers)

__init__.py is a registry, not just a re-export. DEFAULT_SOLVER_CLASSES maps module paths to the solver names they export; import_default_solvers() walks it through try_import(), which tolerates missing optional dependencies (notably RevolvingAreas, which needs the external RA package). get_available_solvers() lists every registered Solver subclass and get_solver_class(name) resolves one by name. import_solver_from_file(path) loads user-written solvers at runtime — this is how the Solver Viewer opens a solver that is not part of the distribution.

• ``rrt/`` — rrt.py (RRT), rrt_star.py (RRT_star), birrt.py (BiRRT), lbt_rrt.py (LBT_RRT), informed_rrt_star.py (Informed_RRT_star), drrt.py (dRRT), drrt_star.py (dRRT_star), ao_drrt.py, contact_guided_rrt.py (Contact_Guided_RRT). The dRRT family builds on TensorSolver; the rest on SamplingSolver.

• ``prm/`` — prm.py (PRM, BasicRodPRM), prm2.py (PRM2, PRM3), prm_rod.py. Classic build-then-query roadmaps.

• ``exact/`` — exact_single.py (ExactSingle). Constructs the free-space arrangement directly with arrangement_operations and plans on its dual graph; no sampling, and complete.

• ``staggered_grid/`` — staggered_grid.py (StaggeredGrid), staggered_grid_base.py, staggered_grid_drrt.py (dRRTStaggeredGrid, dRRTStarStaggeredGrid, StaggeredGridMinPath). Deterministic staggered-grid sampling instead of random sampling.

• ``lattice_solver/`` — latticebase.py, anstar_solver.py (anstar_lattice), staggered_grid_solver.py (staggered_lattice). Lattice discretizations searched with the MRMH-A* machinery of search_algo.py.

• ``bottleneck_tree/`` — bottleneck_tree.py, frechet_matching.py (FrechetMatching), three_curve_frechet.py (ThreeCurveFrechet), exact_three_curve_frechet.py (ExactThreeCurveFrechet). Bottleneck / Fréchet curve-matching planners.

• ``revolving_areas/`` — revolving_areas_solver.py (RevolvingAreas), revolving_areas_basic_solver.py, plus path-combination strategies (path_combiners.py, path_combiners_factory.py, path_combiner_mode.py) and local utilities. Optional: requires the external RA package.

• ``hgraphs.py`` — HGraph and MetaHGraphSolver, the hierarchical-graph meta-solvers exported as HGraph_PRM and HGraph_RRT.

• ``mapf.py`` — GridMAPFSolver, grid-based multi-agent pathfinding.

5. Experiments Layer (discopygal.experiments)

• ``scenarios_runner.py`` — the batch engine.

  • run_scenarios(scenarios, results_root_path, extra_result_handlers, resume_latest) is the top-level driver; repeat_scenario() handles repetitions and returns a pandas.DataFrame; run_single_scenario() executes one configuration.

  • Process isolation: run_single_scenario_process() runs the solver in a separate multiprocessing process communicating over input/output queues, so a crashing or hanging solver cannot take down the batch. TimeoutException enforces per-run limits.

  • Resumability: get_latest_dir() and get_results_experiment_path() support picking up an interrupted experiment run.

  • run_solver(solver, scene) is the thin timing wrapper around solver.solve().

• ``run_experiment.py`` — CLI entry point. load_scenarios_and_handlers() reads a scenario file, and get_chunk_slice(chunk_index, number_of_chunks, n) splits the suite so large experiments can be sharded across machines.

• ``__init__.py`` — Experiment_CompareFunctions, a helper for comparing implementations across a scenario suite.

6. GUI Toolkit Layer (discopygal.gui)

• ``gui.py`` — GUI, the base class that applications subclass alongside their generated Qt Ui_* form.

• ``GraphicsScenePlus.py`` — GraphicsScenePlus, a QGraphicsScene extended with the drawing helpers DiscoPygal needs.

• ``MainWindowsPlus.py`` — main-window scaffolding (zoom, pan, view management).

• ``Worker.py`` — Worker(QRunnable) and WorkerSignals, for running work off the Qt event loop within the same process.

• Drawable wrappers — one class per CGAL shape rendered on the canvas: RDisc, RDiscRobot, RPolygon, RPolygonWithHoles, RSegment, RSegment_angle, RCircleSegment, RText.

• ``color.py`` — the PREDEFINED_COLORS table and HSV serialization used by scenes. ``logger.py`` — the logging surface the GUI writes into.

7. Applications Layer (tools/)

• ``solver_viewer/`` — the interactive solver runner.

  • solver_viewer_main.py — SolverViewerGUI (main window), SolverDialog (parameter form, generated from get_arguments()), start_gui() and main(). import_solver_file() loads external solver files.

  • solve_process() is the function executed in a separate multiprocessing.Process. Results flow back over result_queue and log records over log_queue, with a stop_event for cancellation. Arguments are pickle-checked before spawning so failures surface as a dialog rather than a crash in the child.

  • solver_viewer_gui.py (generated Qt form), serializers.py, visuals.py, theme.py, logger_adapter.py (forwards child-process log records to the GUI), solver_viewer_headless.py (no-UI batch mode).

• ``scene_designer/`` — the scene authoring tool: scene_designer_main.py, scene_designer_gui.py, object_drawer.py, object_editor.py, object_selector.py, grid.py, preferences_dialog.py. Produces the JSON scene files consumed by Scene.

Data Flow Lifecycle: From Scene to Rendered Solution

The diagram traces a sampling-based solve, which is the common case.

Operational Data Flow Lifecycle

Exact solvers (ExactSingle) short-circuit the middle of this pipeline: instead of sampling into a Roadmap, they build a free-space arrangement with arrangement_operations and search its dual graph, rejoining the flow at PathCollection.

Key Architectural Patterns

1. Template Method — Solver exposes a final solve() that loads the scene, delegates to the abstract _solve(), and optionally analyzes the result. Solvers override _solve(), never solve(). SamplingSolver adds a second tier by overriding load_scene() to call the abstract build_roadmap(), and TensorSolver adds a third by implementing build_roadmap() in terms of build_robot_roadmap() and search_tensor_roadmap().

2. Strategy — sampling (Sampler), distance (Metric) and spatial indexing (NearestNeighbors) are injected through SamplingSolver.__init__ and forwarded into Roadmap. Swapping a sampling distribution or a distance function requires no change to planning logic. Note that the nearest-neighbor class is injected, not an instance — Roadmap instantiates one per roadmap.

3. Composite Configuration Space — a multi-robot state is one Point_d of dimension . Point_2_list_to_Point_d and Point_d_to_Point_2_list in discopygal.geometry_utils.conversions are the multiplex/de-multiplex boundary, and they are the reason a multi-robot problem reduces to a single graph search.

4. Registry / Plugin Discovery — discopygal.solvers discovers solver classes by name through DEFAULT_SOLVER_CLASSES and get_solver_class(), and loads third-party solvers at runtime via import_solver_from_file(). Optional dependencies degrade to a warning rather than an import error.

5. Introspective Parameters — get_arguments() returns {name: (label, default, type)}, and init_solver() casts raw strings through it. The Solver Viewer’s parameter dialog and the experiment runner’s scenario files are both generated from this one table, so a new solver parameter needs no UI or config-format change.

6. Out-of-Process Execution — both the Solver Viewer (solve_process()) and the experiment runner (run_single_scenario_process()) execute solvers in separate OS processes with queue-based IPC. This keeps heavy CGAL computation off the Qt event loop, allows hard cancellation and timeouts, and contains crashes. The cost is that everything crossing the boundary must pickle — which is why conversions.graph_to_dict() / arrangement_to_dict() exist and why robots carry a stable _obj_id for matching returned paths back to scene objects.

7. Dual-Traits Geometry — the two CGALPY builds (segment vs. circle-segment arrangement traits) are merged into one namespace but must not be mixed inside a single arrangement. collision_detection.scene_traits() selects the correct flavour for a given robot/obstacle pair.

Extension Guidelines for Developers

• A new planning algorithm — subclass Solver for a general algorithm, SamplingSolver for a roadmap/tree algorithm, or TensorSolver for a per-robot-roadmap algorithm. Implement _solve() (or build_roadmap() / build_robot_roadmap() respectively), declare parameters in get_arguments() — remembering to update() with super().get_arguments() — and annotate the class with @add_traits(...) so the GUI can match it against scenes. Register it in DEFAULT_SOLVER_CLASSES, or just load the file from the Solver Viewer.

• A custom sampler — subclass Sampler and implement sample(); override set_scene() if you need scene-dependent precomputation.

• A custom metric — subclass Metric and implement its distance function, raising MetricNotImplemented for point types you do not support.

• A nearest-neighbor backend — implement the NearestNeighbors interface (fit(), k_nearest(), neighbors_in_radius()). Pass the class, not an instance; Roadmap will wrap it in NearestNeighborsCached.

• A new robot or obstacle type — add the class to discopygal.solvers_infra with to_dict() / from_dict(), extend collision_detection with the matching predicates, and add a drawable wrapper in discopygal.gui.

Related Documentation

• CGALPY Bindings

• Geometry Utilities

• Solvers Infrastructure

• Solvers

• Experiments Utilities

• GUI Documentation

• Solver Viewer

• Scene Designer