elevator_core/dispatch/

rsr.rs

//! Relative System Response (RSR) dispatch — a composite additive
//! cost stack.
//!
//! Inspired by the Otis patent lineage (Bittar US5024295A, US5146053A)
//! and the Barney–dos Santos CGC framework. Unlike those proprietary
//! systems, this implementation is an educational model, not a
//! faithful reproduction of any vendor's scoring.
//!
//! Shape: `rank = eta_weight · travel_time + Σ penalties − Σ bonuses`.
//! All terms are additive scalars, so they compose cleanly with the
//! library's Kuhn–Munkres assignment. Defaults are tuned so the stack
//! reduces to the nearest-car baseline when every weight is zero.
//!
//! What this deliberately leaves out: online weight tuning, fuzzy
//! inference, and stickiness state. Those belong above the trait, not
//! inside a strategy.

use crate::components::{CarCall, ElevatorPhase};
use crate::traffic_detector::{TrafficDetector, TrafficMode};

use super::{DispatchStrategy, RankContext, pair_is_useful};

/// Look up the current [`TrafficMode`] from `ctx.world` and return the
/// scaling factor to apply to the wrong-direction penalty.
///
/// Returns `multiplier` when the mode is `UpPeak` or `DownPeak`, else
/// `1.0`. Also returns `1.0` when the detector resource is missing —
/// keeping the strategy functional in tests that skip `Simulation::new`.
fn peak_scaling(ctx: &RankContext<'_>, multiplier: f64) -> f64 {
    let mode = ctx
        .world
        .resource::<TrafficDetector>()
        .map_or(TrafficMode::Idle, TrafficDetector::current_mode);
    match mode {
        TrafficMode::UpPeak | TrafficMode::DownPeak => multiplier,
        _ => 1.0,
    }
}

/// Additive RSR-style cost stack. Lower scores win the Hungarian
/// assignment.
///
/// See module docs for the cost shape. All weights default to `0.0`
/// except `eta_weight` (1.0), giving a baseline that mirrors
/// [`NearestCarDispatch`](super::NearestCarDispatch) until terms are
/// opted in.
///
/// # Weight invariants
///
/// Every weight field must be **finite and non-negative**. The
/// `with_*` builder methods enforce this with `assert!`; direct field
/// mutation bypasses the check and is a caller responsibility. A `NaN` weight propagates through the multiply-add
/// chain and silently collapses every pair's cost to zero (Rust's
/// `NaN.max(0.0) == 0.0`), producing an arbitrary but type-valid
/// assignment from the Hungarian solver — a hard bug to diagnose.
#[derive(serde::Serialize, serde::Deserialize)]
pub struct RsrDispatch {
    /// Weight on `travel_time = distance / max_speed` (seconds).
    /// Default `1.0`; raising it shifts the blend toward travel time.
    pub eta_weight: f64,
    /// Constant added when the candidate stop lies opposite the
    /// car's committed travel direction.
    ///
    /// Default `0.0`; the Otis RSR lineage uses a large value so any
    /// right-direction candidate outranks any wrong-direction one.
    /// Ignored for cars in [`ElevatorPhase::Idle`] or stopped phases,
    /// since an idle car has no committed direction to be opposite to.
    pub wrong_direction_penalty: f64,
    /// Bonus subtracted when the candidate stop is already a car-call
    /// inside this car.
    ///
    /// Merges the new pickup with an existing dropoff instead of
    /// spawning an unrelated trip. Default `0.0`. Read from
    /// [`DispatchManifest::car_calls_for`](super::DispatchManifest::car_calls_for).
    pub coincident_car_call_bonus: f64,
    /// Coefficient on a smooth load-fraction penalty
    /// (`load_penalty_coeff · load_ratio`).
    ///
    /// Fires for partially loaded cars below the `bypass_load_*_pct`
    /// threshold enforced by [`pair_is_useful`];
    /// lets you prefer emptier cars for new pickups without an on/off cliff.
    /// Default `0.0`.
    pub load_penalty_coeff: f64,
    /// Multiplier applied to `wrong_direction_penalty` when the
    /// [`TrafficDetector`] classifies the current tick as
    /// [`TrafficMode::UpPeak`] or [`TrafficMode::DownPeak`].
    ///
    /// Default `1.0` (mode-agnostic — behaviour identical to pre-peak
    /// tuning). Raising it strengthens directional commitment during
    /// peaks where a car carrying a lobby-bound load shouldn't be
    /// pulled backwards to grab a new pickup. Off-peak periods keep
    /// the unscaled penalty, leaving inter-floor assignments free
    /// to reverse cheaply.
    ///
    /// Silently reduces to `1.0` when no `TrafficDetector` resource
    /// is installed — tests and custom sims that bypass the auto-install
    /// stay unaffected.
    pub peak_direction_multiplier: f64,
    /// Coefficient on the linear waiting-age fairness bonus. Each
    /// candidate stop's rank is reduced by `age_linear_weight · Σ
    /// wait_ticks` across waiting riders at the stop, so stops hosting
    /// older calls win ties without the quadratic blow-up a squared-
    /// wait term would have.
    ///
    /// Default `0.0` at [`new`](Self::new) / serde round-trip (keeps
    /// single-term mutant tests valid and snapshots backward-compatible);
    /// [`tuned`](Self::tuned) / [`default`](Self::default) ship `0.002`,
    /// lighter than ETD's 0.005 because RSR's wrong-direction penalty
    /// and `pair_is_useful` path guard already handle two starvation
    /// patterns that ETD needed the full-strength term for. See the
    /// inline comment at `tuned()` for the harness numbers behind the
    /// calibration.
    ///
    /// Mirrors the Lim 1983 / Barney–dos Santos 1985 CGC lineage
    /// already used in `EtdDispatch::age_linear_weight`; composes
    /// additively with the other penalty-stack terms.
    #[serde(default)]
    pub age_linear_weight: f64,
    /// Maximum candidate stops to consider per car when filling the
    /// assignment cost matrix. Defaults to `Some(50)`; see
    /// [`DispatchStrategy::candidate_limit`] for the rationale.
    #[serde(default = "default_candidate_limit")]
    pub candidate_limit: Option<usize>,
}

/// Serde default for [`RsrDispatch::candidate_limit`] when restoring
/// from a pre-pruning snapshot. Matches
/// [`super::DEFAULT_CANDIDATE_LIMIT`].
#[allow(clippy::unnecessary_wraps)] // serde default needs Option<usize>, not usize
const fn default_candidate_limit() -> Option<usize> {
    Some(super::DEFAULT_CANDIDATE_LIMIT)
}

impl RsrDispatch {
    /// Create a new `RsrDispatch` with the baseline weights
    /// (`eta_weight = 1.0`, all penalties/bonuses disabled).
    ///
    /// This is the **additive-composition baseline** — every penalty
    /// and bonus is zero, so the rank reduces to
    /// [`NearestCarDispatch`](super::NearestCarDispatch) on distance
    /// alone. Useful for tests that want to measure a single term in
    /// isolation (`RsrDispatch::new().with_wrong_direction_penalty(…)`).
    ///
    /// For the opinionated "out-of-the-box RSR" configuration used by
    /// [`BuiltinStrategy::Rsr`](super::BuiltinStrategy::Rsr) and the
    /// playground, use [`RsrDispatch::default`] instead. `Default` ships
    /// with the full penalty stack turned on; `new()` is the empty
    /// canvas you build on top of.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            eta_weight: 1.0,
            wrong_direction_penalty: 0.0,
            coincident_car_call_bonus: 0.0,
            load_penalty_coeff: 0.0,
            peak_direction_multiplier: 1.0,
            age_linear_weight: 0.0,
            candidate_limit: Some(super::DEFAULT_CANDIDATE_LIMIT),
        }
    }

    /// Return the opinionated tuned configuration — equivalent to
    /// [`Default::default`] but usable in `const` contexts.
    ///
    /// See [`RsrDispatch::default`] for the rationale behind each
    /// weight. The tuned stack ships with every penalty/bonus turned
    /// on so picking RSR out of the box is strictly richer than
    /// `NearestCar`, not identical to it.
    #[must_use]
    pub const fn tuned() -> Self {
        Self {
            eta_weight: 1.0,
            // Chosen ≈ one shaft-length travel time on a typical 20-stop
            // commercial bank (≈15s), so a backward pickup costs as much
            // as the trip to serve it. Large enough to dominate the ETA
            // term for a close-but-wrong-direction candidate; small
            // enough that off-peak inter-floor reversals still flip when
            // the demand strongly favours them.
            wrong_direction_penalty: 15.0,
            // Small merge bonus — prefer a car with a matching car-call
            // over spawning a new trip, but not so large it overrides a
            // much closer empty car.
            coincident_car_call_bonus: 5.0,
            // Light load-balancing — prefer empty cars for new work
            // when cars are otherwise tied.
            load_penalty_coeff: 3.0,
            // Strong directional commitment during up-peak / down-peak
            // (lobby-bound loads shouldn't reverse for new pickups).
            // Off-peak stays unscaled for cheap inter-floor reversals.
            peak_direction_multiplier: 2.0,
            // Linear waiting-age fairness. Tuned at 0.002 against the
            // `playground_audit` harness — lighter than ETD's 0.005
            // default because RSR's wrong-direction penalty and
            // `pair_is_useful` path guard already handle two of the
            // starvation patterns ETD needed the full-strength term
            // for. At 0.002 on the audit skyscraper (2 cars, heavy
            // peak), RSR beats SCAN across delivered / avg_wait /
            // max_wait; at 0.005 the same scenario improves further
            // but bleeds a few extra abandonments out of the
            // single-car office run as the age bonus pulls the lone
            // car off fresh demand faster than it can cycle. 0.002
            // is the tighter balance.
            age_linear_weight: 0.002,
            candidate_limit: Some(super::DEFAULT_CANDIDATE_LIMIT),
        }
    }

    /// Set the wrong-direction penalty.
    ///
    /// # Panics
    /// Panics on non-finite or negative weights — a negative penalty
    /// would invert the direction ordering, silently preferring
    /// wrong-direction candidates.
    #[must_use]
    pub fn with_wrong_direction_penalty(mut self, weight: f64) -> Self {
        assert!(
            weight.is_finite() && weight >= 0.0,
            "wrong_direction_penalty must be finite and non-negative, got {weight}"
        );
        self.wrong_direction_penalty = weight;
        self
    }

    /// Set the coincident-car-call bonus.
    ///
    /// # Panics
    /// Panics on non-finite or negative weights — the bonus is
    /// subtracted, so a negative value would become a penalty.
    #[must_use]
    pub fn with_coincident_car_call_bonus(mut self, weight: f64) -> Self {
        assert!(
            weight.is_finite() && weight >= 0.0,
            "coincident_car_call_bonus must be finite and non-negative, got {weight}"
        );
        self.coincident_car_call_bonus = weight;
        self
    }

    /// Set the load-penalty coefficient.
    ///
    /// # Panics
    /// Panics on non-finite or negative weights.
    #[must_use]
    pub fn with_load_penalty_coeff(mut self, weight: f64) -> Self {
        assert!(
            weight.is_finite() && weight >= 0.0,
            "load_penalty_coeff must be finite and non-negative, got {weight}"
        );
        self.load_penalty_coeff = weight;
        self
    }

    /// Set the ETA weight.
    ///
    /// # Panics
    /// Panics on non-finite or negative weights. Zero is allowed and
    /// reduces the strategy to penalty/bonus tiebreaking alone.
    #[must_use]
    pub fn with_eta_weight(mut self, weight: f64) -> Self {
        assert!(
            weight.is_finite() && weight >= 0.0,
            "eta_weight must be finite and non-negative, got {weight}"
        );
        self.eta_weight = weight;
        self
    }

    /// Set the linear waiting-age fairness weight. Composes additively
    /// with the other penalty/bonus terms; `0.0` disables the term.
    ///
    /// # Panics
    /// Panics on non-finite or negative weights. A `NaN` weight would
    /// propagate through `mul_add` and silently collapse the stack;
    /// a negative weight would invert the fairness ordering.
    #[must_use]
    pub fn with_age_linear_weight(mut self, weight: f64) -> Self {
        assert!(
            weight.is_finite() && weight >= 0.0,
            "age_linear_weight must be finite and non-negative, got {weight}"
        );
        self.age_linear_weight = weight;
        self
    }

    /// Set the peak-direction multiplier.
    ///
    /// # Panics
    /// Panics on non-finite or sub-1.0 values. A multiplier below `1.0`
    /// would *weaken* the direction penalty during peaks (the opposite
    /// of the intent) — explicitly disallowed so a typo doesn't silently
    /// invert the tuning.
    #[must_use]
    pub fn with_peak_direction_multiplier(mut self, factor: f64) -> Self {
        assert!(
            factor.is_finite() && factor >= 1.0,
            "peak_direction_multiplier must be finite and ≥ 1.0, got {factor}"
        );
        self.peak_direction_multiplier = factor;
        self
    }

    /// Set the per-car candidate limit for the assignment cost matrix.
    /// `None` disables pruning entirely; defaults to `Some(50)`. See
    /// [`DispatchStrategy::candidate_limit`] for the rationale.
    #[must_use]
    pub const fn with_candidate_limit(mut self, limit: Option<usize>) -> Self {
        self.candidate_limit = limit;
        self
    }
}

impl Default for RsrDispatch {
    /// The opinionated "pick RSR from the dropdown" configuration.
    ///
    /// Defaults to [`RsrDispatch::tuned`] — every penalty and bonus
    /// turned on with values calibrated to a 20-stop commercial bank.
    /// Before this default was tuned, `RsrDispatch::default()`
    /// reduced to the raw [`NearestCarDispatch`](super::NearestCarDispatch)
    /// baseline: picking "RSR" in the playground produced worse
    /// behaviour than picking "Nearest Car" (no direction discipline,
    /// no load balancing, no car-call merging). The tuned default
    /// fixes that without making any term mandatory — consumers
    /// wanting the zero baseline can still call
    /// [`RsrDispatch::new`].
    fn default() -> Self {
        Self::tuned()
    }
}

impl DispatchStrategy for RsrDispatch {
    fn rank(&self, ctx: &RankContext<'_>) -> Option<f64> {
        // `pair_is_useful(ctx, true)` enables the aboard-rider path
        // guard on top of the servability check. Without it, a loaded
        // RSR car gets pulled off the path to its aboard riders'
        // destinations by closer pickups — the same "never reaches
        // the passenger's desired stop" loop that NearestCar
        // specifically fixes. RSR's `wrong_direction_penalty` can
        // mitigate this when configured, but the guard is a
        // correctness floor independent of tuning.
        if !pair_is_useful(ctx, true) {
            return None;
        }
        let car = ctx.world.elevator(ctx.car)?;

        // ETA — travel time to the candidate stop.
        let distance = (ctx.car_position() - ctx.stop_position()).abs();
        let max_speed = car.max_speed.value();
        if max_speed <= 0.0 {
            return None;
        }
        let travel_time = distance / max_speed;
        let mut cost = self.eta_weight * travel_time;

        // Wrong-direction penalty. Only applies when the car has a
        // committed direction (not Idle / Stopped) — an idle car can
        // accept any candidate without "reversing" anything.
        if self.wrong_direction_penalty > 0.0
            && let Some(target) = car.phase.moving_target()
            && let Some(target_pos) = ctx.world.stop_position(target)
        {
            let car_going_up = target_pos > ctx.car_position();
            let car_going_down = target_pos < ctx.car_position();
            let cand_above = ctx.stop_position() > ctx.car_position();
            let cand_below = ctx.stop_position() < ctx.car_position();
            if (car_going_up && cand_below) || (car_going_down && cand_above) {
                // During up-peak/down-peak the directional invariant
                // is load-bearing (a committed car shouldn't reverse
                // to grab a new pickup), so scale the penalty up.
                // Off-peak, the base value still rules — inter-floor
                // traffic wants cheap reversals.
                let scaled = self.wrong_direction_penalty
                    * peak_scaling(ctx, self.peak_direction_multiplier);
                cost += scaled;
            }
        }

        // Coincident-car-call bonus — the candidate stop is already a
        // committed dropoff for this car.
        if self.coincident_car_call_bonus > 0.0
            && ctx
                .manifest
                .car_calls_for(ctx.car)
                .iter()
                .any(|c: &CarCall| c.floor == ctx.stop)
        {
            cost -= self.coincident_car_call_bonus;
        }

        // Smooth load-fraction penalty. `pair_is_useful` has already
        // filtered over-capacity and bypass-threshold cases; this term
        // shapes preference among the survivors so emptier cars win
        // pickups when all else is equal. Idle cars contribute zero.
        if self.load_penalty_coeff > 0.0 && car.phase() != ElevatorPhase::Idle {
            let capacity = car.weight_capacity().value();
            if capacity > 0.0 {
                let load_ratio = (car.current_load().value() / capacity).clamp(0.0, 1.0);
                cost += self.load_penalty_coeff * load_ratio;
            }
        }

        // Linear waiting-age fairness bonus. Pulls stale calls forward
        // without the quadratic blow-up a squared-wait term would have;
        // prevents fresh lobby-side demand from indefinitely preempting
        // older upper-floor waiters. Mirrors ETD's `age_linear_weight`.
        if self.age_linear_weight > 0.0 {
            let wait_sum = super::wait_ticks_sum(ctx.manifest.waiting_riders_at(ctx.stop));
            cost = super::apply_fairness_bonus(cost, self.age_linear_weight, wait_sum);
        }

        // Clamp the running cost to the Hungarian's non-negative floor.
        // Two paths reach here without a guaranteed prior clamp:
        //   1. `age_linear_weight == 0.0` skips the fairness branch
        //      entirely, leaving the coincident-car-call subtraction
        //      unclamped.
        //   2. Even when fairness runs, the coincident-call subtraction
        //      happens before it on a small-eta pairing.
        // Either way, this trailing clamp is the only floor the
        // assigner sees.
        let cost = cost.max(0.0);
        if cost.is_finite() { Some(cost) } else { None }
    }

    fn builtin_id(&self) -> Option<super::BuiltinStrategy> {
        Some(super::BuiltinStrategy::Rsr)
    }

    fn candidate_limit(&self) -> Option<usize> {
        self.candidate_limit
    }

    fn snapshot_config(&self) -> Option<String> {
        ron::to_string(self).ok()
    }

    fn restore_config(&mut self, serialized: &str) -> Result<(), String> {
        let restored: Self = ron::from_str(serialized).map_err(|e| e.to_string())?;
        *self = restored;
        Ok(())
    }
}