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.

# use deke_multipath::*;
# use deke_types::{SRobotQ, SRobotPath, Planner, Validator};
# fn go<'ctx, const N: usize, P, V, MW>(
#     paths: Vec<ReqPath<N>>, planner: &P, cfg: &P::Config, make_wp: MW,
#     validator: &V, ctx: &V::Context<'ctx>, start: SRobotQ<N, f64>, weights: SRobotQ<N, f64>,
# ) -> MultipathResult<Vec<SRobotPath<N, f64>>>
# where P: Planner<N, f64> + Sync, P::Config: Sync, V: Validator<N, (), f64>,
#       V::Context<'ctx>: Sync,
#       MW: Fn(SRobotQ<N, f64>, SRobotQ<N, f64>) -> P::Waypoints + Sync {
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).