problemreductions/rules/
minimumdiscreteplanarinversekinematics_qubo.rs

1//! Reduction from MinimumDiscretePlanarInverseKinematics to QUBO.
2//!
3//! Each sampled orientation becomes a binary one-hot variable. The planar
4//! end-effector coordinates are linear in those selectors, so the squared
5//! distance to the target expands directly into a quadratic objective. One-hot
6//! penalties enforce exactly one orientation per link, and forbidden-pair
7//! penalties enforce the consecutive-joint feasibility relations.
8//!
9//! Reference: Salloum et al. (2025).
10
11use crate::models::algebraic::QUBO;
12use crate::models::misc::MinimumDiscretePlanarInverseKinematics;
13use crate::reduction;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15
16fn block_offsets(block_sizes: &[usize]) -> Vec<usize> {
17    let mut offsets = Vec::with_capacity(block_sizes.len());
18    let mut offset = 0;
19    for &size in block_sizes {
20        offsets.push(offset);
21        offset += size;
22    }
23    offsets
24}
25
26/// Result of reducing MinimumDiscretePlanarInverseKinematics to QUBO.
27#[derive(Debug, Clone)]
28pub struct ReductionMinimumDiscretePlanarInverseKinematicsToQUBO {
29    target: QUBO<f64>,
30    block_offsets: Vec<usize>,
31    block_sizes: Vec<usize>,
32}
33
34impl ReductionResult for ReductionMinimumDiscretePlanarInverseKinematicsToQUBO {
35    type Source = MinimumDiscretePlanarInverseKinematics;
36    type Target = QUBO<f64>;
37
38    fn target_problem(&self) -> &Self::Target {
39        &self.target
40    }
41
42    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
43        self.block_offsets
44            .iter()
45            .zip(&self.block_sizes)
46            .map(|(&start, &size)| {
47                target_solution[start..start + size]
48                    .iter()
49                    .position(|&bit| bit == 1)
50                    .unwrap_or(0)
51            })
52            .collect()
53    }
54}
55
56#[reduction(overhead = { num_vars = "num_orientation_samples" })]
57impl ReduceTo<QUBO<f64>> for MinimumDiscretePlanarInverseKinematics {
58    type Result = ReductionMinimumDiscretePlanarInverseKinematicsToQUBO;
59
60    fn reduce_to(&self) -> Self::Result {
61        let block_sizes: Vec<usize> = self.orientation_samples().iter().map(Vec::len).collect();
62        let block_offsets = block_offsets(&block_sizes);
63        let total_vars: usize = block_sizes.iter().sum();
64        let (gx, gy) = self.target_point();
65
66        let mut x_coeffs = Vec::with_capacity(total_vars);
67        let mut y_coeffs = Vec::with_capacity(total_vars);
68        for (&length, samples) in self.link_lengths().iter().zip(self.orientation_samples()) {
69            for &angle in samples {
70                x_coeffs.push(length * angle.cos());
71                y_coeffs.push(length * angle.sin());
72            }
73        }
74
75        // A violation contributes at least one full penalty unit. This bound
76        // exceeds the largest possible squared distance of any decoded source
77        // configuration, so every QUBO minimizer for a feasible source
78        // instance is one-hot and pair-feasible.
79        let sum_abs_x: f64 = x_coeffs.iter().map(|coeff| coeff.abs()).sum();
80        let sum_abs_y: f64 = y_coeffs.iter().map(|coeff| coeff.abs()).sum();
81        let penalty = 1.0 + (sum_abs_x + gx.abs()).powi(2) + (sum_abs_y + gy.abs()).powi(2);
82
83        let mut matrix = vec![vec![0.0; total_vars]; total_vars];
84        let mut add_upper = |i: usize, j: usize, value: f64| {
85            let (lo, hi) = if i <= j { (i, j) } else { (j, i) };
86            matrix[lo][hi] += value;
87        };
88
89        // Position objective: (X - g_x)^2 + (Y - g_y)^2, dropping the
90        // additive constant g_x^2 + g_y^2.
91        for (idx, (&x_coeff, &y_coeff)) in x_coeffs.iter().zip(&y_coeffs).enumerate() {
92            add_upper(
93                idx,
94                idx,
95                x_coeff * x_coeff - 2.0 * gx * x_coeff + y_coeff * y_coeff - 2.0 * gy * y_coeff,
96            );
97        }
98        for i in 0..total_vars {
99            for j in (i + 1)..total_vars {
100                add_upper(
101                    i,
102                    j,
103                    2.0 * (x_coeffs[i] * x_coeffs[j] + y_coeffs[i] * y_coeffs[j]),
104                );
105            }
106        }
107
108        // One-hot penalty per link: P * (sum_a y_{j,a} - 1)^2.
109        for (&start, &size) in block_offsets.iter().zip(&block_sizes) {
110            for a in 0..size {
111                add_upper(start + a, start + a, -penalty);
112            }
113            for a in 0..size {
114                for b in (a + 1)..size {
115                    add_upper(start + a, start + b, 2.0 * penalty);
116                }
117            }
118        }
119
120        // Forbidden-pair penalties between consecutive links.
121        for (junction, pairs) in self.allowed_pairs().iter().enumerate() {
122            let prev_size = block_sizes[junction];
123            let curr_size = block_sizes[junction + 1];
124            let prev_start = block_offsets[junction];
125            let curr_start = block_offsets[junction + 1];
126
127            let mut allowed = vec![vec![false; curr_size]; prev_size];
128            for &(a_prev, a_curr) in pairs {
129                allowed[a_prev][a_curr] = true;
130            }
131
132            for (a_prev, row) in allowed.iter().enumerate() {
133                for (a_curr, &is_allowed) in row.iter().enumerate() {
134                    if !is_allowed {
135                        add_upper(prev_start + a_prev, curr_start + a_curr, penalty);
136                    }
137                }
138            }
139        }
140
141        ReductionMinimumDiscretePlanarInverseKinematicsToQUBO {
142            target: QUBO::from_matrix(matrix),
143            block_offsets,
144            block_sizes,
145        }
146    }
147}
148
149#[cfg(feature = "example-db")]
150pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
151    use crate::export::SolutionPair;
152    use std::f64::consts::FRAC_PI_2;
153
154    vec![crate::example_db::specs::RuleExampleSpec {
155        id: "minimumdiscreteplanarinversekinematics_to_qubo",
156        build: || {
157            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
158                MinimumDiscretePlanarInverseKinematics::new(
159                    vec![2.0, 1.0],
160                    (2.0, 1.0),
161                    vec![vec![0.0, FRAC_PI_2], vec![0.0, FRAC_PI_2]],
162                    vec![vec![(0, 0), (0, 1), (1, 1)]],
163                ),
164                SolutionPair {
165                    source_config: vec![0, 1],
166                    target_config: vec![1, 0, 0, 1],
167                },
168            )
169        },
170    }]
171}
172
173#[cfg(test)]
174#[path = "../unit_tests/rules/minimumdiscreteplanarinversekinematics_qubo.rs"]
175mod tests;
problemreductions/rules/minimumdiscreteplanarinversekinematics_qubo.rs

problemreductions/rules/
minimumdiscreteplanarinversekinematics_qubo.rs
