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(
43        &self,
44        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
45    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
46        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
47
48        self.block_offsets
49            .iter()
50            .zip(&self.block_sizes)
51            .enumerate()
52            .map(|(link, (&start, &size))| {
53                let mut selected = target_solution[start..start + size]
54                    .iter()
55                    .enumerate()
56                    .filter_map(|(orientation, &bit)| bit.then_some(orientation));
57                match (selected.next(), selected.next()) {
58                    (Some(orientation), None) => Ok(orientation),
59                    (None, _) => Err(crate::rules::ExtractionError::invalid(format!(
60                        "link {link} has no selected orientation"
61                    ))),
62                    (Some(_), Some(_)) => Err(crate::rules::ExtractionError::invalid(format!(
63                        "link {link} has multiple selected orientations"
64                    ))),
65                }
66            })
67            .collect()
68    }
69}
70
71#[reduction(transform = exact {
72    num_vars = "num_orientation_samples",
73})]
74impl ReduceTo<QUBO<f64>> for MinimumDiscretePlanarInverseKinematics {
75    type Result = ReductionMinimumDiscretePlanarInverseKinematicsToQUBO;
76
77    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
78        let block_sizes: Vec<usize> = self.orientation_samples().iter().map(Vec::len).collect();
79        let block_offsets = block_offsets(&block_sizes);
80        let total_vars: usize = block_sizes.iter().sum();
81        let (gx, gy) = self.target_point();
82
83        let mut x_coeffs = Vec::with_capacity(total_vars);
84        let mut y_coeffs = Vec::with_capacity(total_vars);
85        for (&length, samples) in self.link_lengths().iter().zip(self.orientation_samples()) {
86            for &angle in samples {
87                x_coeffs.push(length * angle.cos());
88                y_coeffs.push(length * angle.sin());
89            }
90        }
91
92        // A violation contributes at least one full penalty unit. This bound
93        // exceeds the largest possible squared distance of any decoded source
94        // configuration, so every QUBO minimizer for a feasible source
95        // instance is one-hot and pair-feasible.
96        let sum_abs_x: f64 = x_coeffs.iter().map(|coeff| coeff.abs()).sum();
97        let sum_abs_y: f64 = y_coeffs.iter().map(|coeff| coeff.abs()).sum();
98        let penalty = 1.0 + (sum_abs_x + gx.abs()).powi(2) + (sum_abs_y + gy.abs()).powi(2);
99
100        let mut matrix = vec![vec![0.0; total_vars]; total_vars];
101        let mut add_upper = |i: usize, j: usize, value: f64| {
102            let (lo, hi) = if i <= j { (i, j) } else { (j, i) };
103            matrix[lo][hi] += value;
104        };
105
106        // Position objective: (X - g_x)^2 + (Y - g_y)^2, dropping the
107        // additive constant g_x^2 + g_y^2.
108        for (idx, (&x_coeff, &y_coeff)) in x_coeffs.iter().zip(&y_coeffs).enumerate() {
109            add_upper(
110                idx,
111                idx,
112                x_coeff * x_coeff - 2.0 * gx * x_coeff + y_coeff * y_coeff - 2.0 * gy * y_coeff,
113            );
114        }
115        for i in 0..total_vars {
116            for j in (i + 1)..total_vars {
117                add_upper(
118                    i,
119                    j,
120                    2.0 * (x_coeffs[i] * x_coeffs[j] + y_coeffs[i] * y_coeffs[j]),
121                );
122            }
123        }
124
125        // One-hot penalty per link: P * (sum_a y_{j,a} - 1)^2.
126        for (&start, &size) in block_offsets.iter().zip(&block_sizes) {
127            for a in 0..size {
128                add_upper(start + a, start + a, -penalty);
129            }
130            for a in 0..size {
131                for b in (a + 1)..size {
132                    add_upper(start + a, start + b, 2.0 * penalty);
133                }
134            }
135        }
136
137        // Forbidden-pair penalties between consecutive links.
138        for (junction, pairs) in self.allowed_pairs().iter().enumerate() {
139            let prev_size = block_sizes[junction];
140            let curr_size = block_sizes[junction + 1];
141            let prev_start = block_offsets[junction];
142            let curr_start = block_offsets[junction + 1];
143
144            let mut allowed = vec![vec![false; curr_size]; prev_size];
145            for &(a_prev, a_curr) in pairs {
146                allowed[a_prev][a_curr] = true;
147            }
148
149            for (a_prev, row) in allowed.iter().enumerate() {
150                for (a_curr, &is_allowed) in row.iter().enumerate() {
151                    if !is_allowed {
152                        add_upper(prev_start + a_prev, curr_start + a_curr, penalty);
153                    }
154                }
155            }
156        }
157
158        Ok(ReductionMinimumDiscretePlanarInverseKinematicsToQUBO {
159            target: QUBO::from_matrix(matrix).map_err(|message| {
160                crate::rules::ReductionError::construction::<
161                    MinimumDiscretePlanarInverseKinematics,
162                    QUBO<f64>,
163                >(message)
164            })?,
165            block_offsets,
166            block_sizes,
167        })
168    }
169}
170
171#[cfg(feature = "example-db")]
172pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
173    use crate::export::SolutionPair;
174    use std::f64::consts::FRAC_PI_2;
175
176    vec![crate::example_db::specs::RuleExampleSpec {
177        id: "minimumdiscreteplanarinversekinematics_to_qubo",
178        build: || {
179            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
180                MinimumDiscretePlanarInverseKinematics::new(
181                    vec![2.0, 1.0],
182                    (2.0, 1.0),
183                    vec![vec![0.0, FRAC_PI_2], vec![0.0, FRAC_PI_2]],
184                    vec![vec![(0, 0), (0, 1), (1, 1)]],
185                )
186                .unwrap(),
187                SolutionPair {
188                    source_config: serde_json::json!(vec![0, 1]),
189                    target_config: serde_json::json!(vec![true, false, false, true]),
190                },
191            )
192        },
193    }]
194}
195
196#[cfg(test)]
197#[path = "../unit_tests/rules/minimumdiscreteplanarinversekinematics_qubo.rs"]
198mod tests;
problemreductions/rules/minimumdiscreteplanarinversekinematics_qubo.rs

problemreductions/rules/
minimumdiscreteplanarinversekinematics_qubo.rs
