Exact Single-Robot Motion Planning (ExactSingle)¶

The ExactSingle solver computes deterministic, exact motion planning solutions for a single disc or polygonal robot operating among polygonal obstacles. Unlike sampling-based planners (e.g., RRT, PRM), ExactSingle constructs the exact free configuration space using CGAL Minkowski sums and 2D arrangement face overlay decomposition.

Architectural Design & Algorithm Pipeline¶

Base Contract: Inherits directly from Solver.
C-Space Construction: 1. For a disc robot of radius $R$ , expands obstacle polygons by $R$ using Minkowski sums (Ms2). 2. For a polygonal robot, computes the exact Minkowski difference between obstacle polygons and the inverted robot shape.
Arrangement Overlay & Vertical Decomposition: - Inserts expanded C-obstacle boundary curves into a 2D arrangement (Arrangement_2). - Performs vertical decomposition on the arrangement to decompose free faces into trapezoidal cells.
Dual Connectivity Graph Construction: - Creates a dual graph $G = (V, E)$ where nodes $v \in V$ correspond to trapezoid face midpoints and vertical cell walls. - Connects adjacent trapezoid midpoints through valid boundary segment portals.
Path Generation: - Queries point locations for start $\mathbf{q}_{\text{start}}$ and goal $\mathbf{q}_{\text{end}}$ within the arrangement using Arr_trapezoid_ric_point_location. - Runs Dijkstra / $A^*$ search on the dual connectivity graph $G$ . - Constructs a continuous piecewise linear path.

Exact Single-Robot Planning Pipeline¶

Parameters & Configuration¶

ExactSingle Parameters¶
Parameter	Description	Default	Type
`eps`	Approximated offset tolerance for curved Minkowski boundaries	`0.0001`	`float`

Usage Example¶

from discopygal.solvers.exact.exact_single import ExactSingle
from discopygal.solvers_infra import Scene

# Instantiate exact solver
solver = ExactSingle.init_solver(eps=0.0001)
path_collection = solver.solve(scene)

API Reference¶

class discopygal.solvers.exact.exact_single.ExactSingle(eps, **kwargs)¶

Bases: Solver

Exact solution by vertical decomposition for a SINGLE disc/polygon robot. Multiple robot motion planning is not supported. Also any other type besides disc or polygon robot is unsupported

Parameters:: eps (float) – epsilon for approximated offset

connectivity_graph(arr) → tuple[Graph, dict]¶: Get the connectivity graph from a vertical decomposition arrangement

construct_cspace() → Arrangement_on_surface_2¶: Get the (CGAL Polygonal) obstacles and the radius of the robot, and construct the expanded CSPACE arrangement (also with bounding box walls)

find_face_index(arr, p, pl)¶: Get a point and find the index of the face in the arrangement that has it

find_valid_path(g_path, source, target, edge_dict, collision_detector) → Path¶: Convert a graph path to a valid motion planning path. We do that by connecting midpoints of edges we pass - and since the arrangement has circle curves, we might need split some edges in half (for exact motion).

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_arrangement()¶

Return an arrangement (if applicable). Can be overridded by solvers.

Returns:: arrangement
Return type:: Arrangement_2

to_ker_point_2(point) → Point_2¶: Convert TPoint() to Ker.Point_2()

vertical_decomposition(arr)¶: Take an arrangement and add edges to it that represent the vertical decomposition