Solvers Infrastructure

The solvers infrastructure contains the core building blocks used by all motion planners in DiscoPygal. It defines the scene representation contracts, roadmap graph structures, configurable strategy interfaces (samplers, metrics, nearest neighbors), graph search engines, and path verification utilities.

Architecture and Inter-File Relations

  • Solver.py: Abstract base class Solver establishing the standard lifecycle (load_scene() -> _solve() -> solve()) and data classes (Scene, Robot, Obstacle, Path, PathCollection).

  • SamplingSolver.py: Subclasses Solver to provide common infrastructure for roadmap- and tree-based sampling planners, delegating roadmap generation and path queries.

  • roadmap.py & implicitroadmap.py: Graph container classes managing node configurations and edge connections. Integrates sampling strategies, spatial indexing backends, and distance metrics.

  • samplers.py: Strategy hierarchy (Sampler) providing uniform, bounding-box, grid, and Halton sampling algorithms.

  • metrics.py: Distance policy hierarchy (Metric) implementing L_1, L_2, L_\infty, weighted, and composite tensor metrics.

  • nearest_neighbors.py: Spatial search interface (NearestNeighbors) wrapping CGAL k-d trees and brute-force backends.

  • search_algo.py: Graph search algorithms (A^*, Dijkstra, BFS, Bidirectional A^*) operating on roadmap structures.

  • verify_paths.py: Post-execution validator ensuring generated paths are collision-free and respect start/goal bounds.

Module Documentation