Crate deke_multipath 

Optimal ordering and orientation of required robot paths.

Given a set of paths that must each be traversed exactly once — some of which may be reversible or have several interchangeable realizations — this crate chooses one option per required path and orders them to minimise total motion cost, starting at a configuration and optionally ending at one. It returns the full stitched motion: connector segments interleaved with the chosen required paths.

The ordering is an asymmetric generalized TSP (see [agtsp]); cost is any Fn(SRobotQ<N, f64>, SRobotQ<N, f64>) -> f64 scoring a transition between two configurations. weighted_euclidean, planned_path_length and planned_trajectory_time build the common ones (cheap joint distance, planner arc length, retimed trajectory time). The planner passed to plan_multipath is only used to generate connector paths in the output — plan_multipath_straight emits validated straight-line connectors instead.

If you already hold a precomputed option × option cost matrix and want the chosen option index per cluster (rather than stitched paths), call solve_matrix / solve_matrix_multi_start directly.

let settings = MultiPathSettings::new(start);
let cost = weighted_euclidean(weights);
let transition = TransitionPlanner { planner, config: cfg, make_waypoints: make_wp };
plan_multipath(&paths, &cost, &settings, &transition, validator, ctx)

Feature flags

• rayon — use rayon to plan connectors concurrently and to fan out the heuristic’s seed tours. Worth enabling when connector planning is the bottleneck (real collision-checked RRT, where each plan costs milliseconds) or for large heuristic instances; for trivially cheap connectors the thread-pool dispatch can cost more than it saves. The exact Held–Karp solver stays sequential — its layers depend on one another, so it does not parallelize without a structural rewrite. Enabling it adds Sync bounds on the planner, its config, the waypoint builder, and the validator context (all satisfied by the deke planners/validators).

Structs

MultiPathSettings

Knobs for a multipath solve. Build with MultiPathSettings::new.

TransitionPlanner

Everything needed to generate real connector paths with a deke planner. The make_waypoints closure bridges the planner’s associated Waypoints type — for the RRT planners that is |s, e| StartEnd { start: s, end: e }.

Enums

MultipathError

Failure modes specific to multipath solving, layered over DekeError for the underlying planning / validation / path-construction failures that flow up from the deke primitives.

ReqPath

A path that must be traversed exactly once, with the directions or variants the solver is free to choose between. Every variant collapses to a set of directed option paths; the solver picks exactly one option per ReqPath.

Constants

DEFAULT_CELL_BUDGET

Default Held–Karp cell budget: above this many DP cells the solver switches from exact to the nearest-neighbour + 2-opt heuristic. 16 * 1024 * 1024 cells ≈ 256 MB.

Functions

plan_multipath

Solve the ordering and stitch the full motion using transition to plan obstacle-aware connectors between the chosen paths.

plan_multipath_straight

Solve the ordering and stitch the full motion using straight joint-space connectors. Each connector is checked with validator.validate_motion; if a straight line between two required paths is infeasible the solve fails (there is no planner to route around the obstacle).

planned_path_length

Cost function that plans an obstacle-aware connector with planner and scores the transition by the arc length of the resulting path. Use this when ordering should account for how far the robot actually has to travel to route around obstacles, not just the straight-line joint distance.

planned_trajectory_time

Cost function that plans a connector and then retimes it, scoring the transition by the resulting trajectory duration in seconds. This is the metric to minimise when total cycle time is what matters: it folds in the dynamics (velocity/acceleration limits) the retimer enforces, not just geometric distance.

solve_matrix

Solve the asymmetric generalized TSP directly over a precomputed cost matrix, returning the chosen option index per cluster in visiting order and the total cost — without expanding paths or stitching motion. This is the bare ordering core for callers that already have their own cost structure and only want the selection and order back.

solve_matrix_multi_start

Multi-start, top-k variant of solve_matrix: run one solve per starting cluster (each constrained to begin its tour at that cluster) and return the k cheapest tours found, ascending by cost. Useful when a single optimum is not enough — e.g. choosing among near-equal orderings by a downstream metric the cost matrix does not capture.

weighted_distance

Weighted joint-space distance sqrt(Σ (wᵢ·(aᵢ-bᵢ))²). Note this is not SRobotQ::distance, which is unweighted.

weighted_euclidean

Cost function scoring a transition by the weighted joint-space straight-line distance between the two configurations — the cheap, planner-free metric.

Type Aliases

MultipathResult