path op• Data kinds: image2d × matrix → table
• Call: import fullseye as fs; fs.ledger.car_hybrid_astar(occupancy, poses, radius=1.0, cell=1.0, step=None, n_theta=72, allow_reverse=True, footprint=None, clearance=0.0, reverse_penalty=0.0, switch_penalty=0.0, steer_penalty=0.0, shot_every=None, max_expansions=200000, return_tree=False, method='exact') (to call the implementation directly, import carpath; carpath.car_hybrid_astar(occupancy, poses, radius=1.0, cell=1.0, step=None, n_theta=72, allow_reverse=True, footprint=None, clearance=0.0, reverse_penalty=0.0, switch_penalty=0.0, steer_penalty=0.0, shot_every=None, max_expansions=200000, return_tree=False, method='exact'); from the registry, opsgraph.get("car_hybrid_astar"))
• GPU: none (CPU reference implementation only)
Hybrid A* (Dolgov, Thrun, Montemerlo and Diebel 2010): a car's path through an occupancy grid.
occupancy is a 2-D grid (> 0.5 = obstacle); cell (row, col) covers metres x in [col*cell, (col+1)*cell), y in [row*cell, (row+1)*cell). poses is [[x, y, theta], [x', y', theta']] (start, goal) in metres/radians. The car has minimum turning radius radius; footprint=(length, width, rear_offset) is a rectangle in rear-axle coordinates (None = point car with clearance metres kept from obstacles). Motion primitives are {left, straight, right} × {forward, reverse if allow_reverse} arcs of step metres (default 1.01·sqrt(2)·cell, so each primitive leaves its cell); states are pruned per discrete cell (col, row, theta bin of 2π/n_theta). Cost = path length + reverse_penalty·(reversed length) + switch_penalty per gear change + steer_penalty per steering change (all default 0, so the cost is the geometric length). The heuristic is the obstacle-free Reeds–Shepp length (Dubins when reversing is disallowed), admissible because every penalty is non-negative. At the start node, and then every shot_every expansions (default None = adaptive: a node with cost-to-go h tries when the expansion count is a multiple of ceil(h / step), so nodes near the goal try every time, as in the paper), the shortest analytic path from the node to the goal is collision-checked, and the search ends when that shot is free. On an obstacle-free grid the first shot succeeds and the result equals the Reeds–Shepp (Dubins) length exactly; with obstacles the result is never below it (lower_bound). Cell pruning makes Hybrid A* an approximation of the optimum among all feasible paths, as in the paper. method="exact" (default) preserves the original expansion order. method="fast" uses a platform-stable priority rounded to 1e-9, rejects dominated branches before collision checking, and reuses at most eight analytic candidates computed by the heuristic; it may return different waypoints with the same cost.
Returns points (N, 3) poses along the path (start, tree part, analytic shot to the goal), length (metres), cost, lower_bound (Reeds–Shepp/Dubins length start→goal), segments [(kind, gear, length)] of the whole path, n_expanded, n_generated, closed_by_shot (True when the analytic expansion ended the search; False when the goal cell itself was popped), shot_from (pose where the shot started), tree ((K, 3) expanded poses, only when return_tree).
Raises ValueError: grid not 2-D or empty; poses not (2, 3) finite, outside the grid or in collision; radius/cell/step not positive, n_theta < 4, negative penalties; the goal is unreachable (open set exhausted) or max_expansions was hit (reported, never a partial path).
• Sample-data catalog (download URLs / licences) — 2-D uses skimage.data (BSD/public domain) plus synthetic images; 3-D lists download URLs for real data sources (Stanford, PDS, …).
• Operator provenance and references — the sources of the research/methods this op family came from.
• The canonical algorithm (author, year) and its uses are named in the family usage guide above.
• poc_car_parking — py -3.11 examples/poc_car_parking.py
• poc_driving_school — py -3.11 examples/poc_driving_school.py
table as input)graph_edge_consensus · graph_core_persistence · tree_morphometry · tree_sholl · tree_run_length
path)car_dubins_path · car_reeds_shepp_path
*Provenance: carpath.py — GRAPH operator registry. This per-op note is generated by tools/opdocs.py md (do not hand-edit).*
© 2026 Kazufumi Furuse — Fullseye operator documentation. Licensed under Apache-2.0.