[Model] MinimumDiscretePlanarInverseKinematics

[zhangjieqingithub]

Motivation

Adds a robotics-facing optimization problem that connects naturally to the existing QUBO hub via a concrete sampled-angle formulation.

Definition

Name: MinimumDiscretePlanarInverseKinematics
Reference: Hadi Salloum, Sergei Savin, Yaroslav Kholodov, Gleb Ryzhakov, Mirko Farina, and Ivan Oseledets, "Quantum annealing for inverse kinematics in robotics", Scientific Reports 16(1):4244, 2025, https://doi.org/10.1038/s41598-025-34346-z

Given:

• positive link lengths l_1, ..., l_n,
• a target point g = (g_x, g_y) in R^2,
• for each link j, a finite set of candidate absolute orientations Phi_j = {phi_{j,0}, ..., phi_{j,m_j-1}},
• for each j = 2, ..., n, an admissible pair set A_j contained in {0, ..., m_{j-1}-1} x {0, ..., m_j-1},

choose indices a_j in {0, ..., m_j-1} such that (a_{j-1}, a_j) in A_j for every j = 2, ..., n, minimizing

|| sum_{j=1}^n l_j (cos(phi_{j,a_j}), sin(phi_{j,a_j})) - g ||_2^2.

The pair sets A_j encode local joint-feasibility between consecutive links; for example, they can enforce joint limits on the relative angle phi_{j,a_j} - phi_{j-1,a_{j-1}}.

Variables

• Count: n, one variable per link
• Per-variable domain: x_j in {0, ..., m_j-1}
• Meaning: x_j = a means link j uses sampled absolute orientation phi_{j,a}

Schema (data type)

Type name: MinimumDiscretePlanarInverseKinematics
Variants: none initially

Field	Type	Description
link_lengths	list of positive reals	the link lengths l_1, ..., l_n
target_point	pair of reals	the target point g = (g_x, g_y)
orientation_samples	list of angle lists	the sampled absolute orientations Phi_j for each link
allowed_pairs	list of pair sets	the admissible pair sets A_j for j = 2, ..., n

Complexity

• Best known exact algorithm: O(prod_{j=1}^n m_j) by exhaustive enumeration over all sampled orientation choices; with uniform sample count m, this is O(m^n)
• References: definition/discretization style from Salloum et al. (2025), https://doi.org/10.1038/s41598-025-34346-z ; broader IK optimization context from Hongkai Dai, Gregory Izatt, and Russ Tedrake, "Global inverse kinematics via mixed-integer convex optimization", International Journal of Robotics Research 38(12-13):1420-1441, 2019, https://doi.org/10.1177/0278364919846512

Extra Remark

Using absolute link orientations instead of local joint angles is deliberate: after one-hot lifting, the workspace position becomes linear in the binary selector variables, which makes the companion QUBO reduction genuinely quadratic.

Reduction Rule Crossref

• [Rule] MinimumDiscretePlanarInverseKinematics to QUBO #995 [Rule] MinimumDiscretePlanarInverseKinematics to QUBO

How to solve

• It can be solved by (existing) brute force.
• It can be solved by reducing to QUBO via [Rule] MinimumDiscretePlanarInverseKinematics to QUBO #995.
• Other, refer to ...

Example Instance

Take:

• link_lengths = [2, 1]
• target_point = (2, 1)
• orientation_samples = [[0, pi/2], [0, pi/2]]
• allowed_pairs = [{(0,0), (0,1), (1,1)}]

So the second link may either keep the first link's orientation or turn counterclockwise by pi/2.

Expected Outcome

An optimal configuration is:

• x = [0, 1]

This means:

• link 1 uses angle 0,
• link 2 uses angle pi/2.

The resulting end-effector position is
(2 cos 0, 2 sin 0) + (cos(pi/2), sin(pi/2)) = (2, 0) + (0, 1) = (2, 1),

so the optimal objective value is 0.

BibTeX

@article{Salloum2025IKQUBO,
  title={Quantum annealing for inverse kinematics in robotics},
  author={Salloum, Hadi and Savin, Sergei and Kholodov, Yaroslav and Ryzhakov, Gleb and Farina, Mirko and Oseledets, Ivan},
  journal={Scientific Reports},
  volume={16},
  number={1},
  pages={4244},
  year={2025},
  doi={10.1038/s41598-025-34346-z},
  url={https://doi.org/10.1038/s41598-025-34346-z}
}

@article{DaiIzattTedrake2019GlobalIK,
  title={Global inverse kinematics via mixed-integer convex optimization},
  author={Dai, Hongkai and Izatt, Gregory and Tedrake, Russ},
  journal={The International Journal of Robotics Research},
  volume={38},
  number={12-13},
  pages={1420--1441},
  year={2019},
  doi={10.1177/0278364919846512},
  url={https://doi.org/10.1177/0278364919846512}
}

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	Novel problem not yet in reduction graph; connects to QUBO via planned rule #995
Non-trivial	Pass	Discrete sampled-angle IK with admissible pair constraints — distinct feasibility/objective from any existing model
Correctness	Pass	Both cited papers verified; brute-force complexity O(prod m_j) is correct by direct enumeration
Well-written	Pass	All template sections substantive; symbols defined before use; example is concrete and round-trip-testable

Overall: 4 passed, 0 failed, 0 warnings

---

Usefulness

• pred show MinimumDiscretePlanarInverseKinematics returns "Unknown problem" — the model is new.
• The issue lists a concrete planned reduction in the "Reduction Rule Crossref" section: #995 [Rule] MinimumDiscretePlanarInverseKinematics to QUBO, which is currently open. This satisfies the orphan-node check — the model has a planned edge into the existing reduction graph (QUBO hub).
• "How to solve" checks both brute-force and reduction to QUBO via [Rule] MinimumDiscretePlanarInverseKinematics to QUBO #995. Direct ILP solving is not claimed, so the ILP-companion-rule requirement is not triggered.
• Motivation is concrete (robotics inverse kinematics) and matches the cited Salloum 2025 application context.

Non-trivial

The feasibility structure (per-step admissible pairs A_j ⊆ {0,...,m_{j-1}-1} × {0,...,m_j-1} encoding consecutive-link joint feasibility) plus the geometric L2 objective on the forward-kinematics endpoint is structurally distinct from every model currently in the catalog (verified via pred list; no Kinematics/IK/Robotics models exist). It is not a repackaging of CSP/SAT/QUBO/MaximumIndependentSet/etc. — the per-link discrete domains can each have different cardinalities m_j, and the objective is quadratic in the one-hot lifts (which is exactly what makes the QUBO companion rule work).

Correctness

Reference 1 — Salloum et al. 2025

• WebSearch + WebFetch (PMC mirror PMC12858918) confirm:
  • Title: "Quantum annealing for inverse kinematics in robotics"
  • Authors: Hadi Salloum, Sergei Savin, Yaroslav Kholodov, Gleb Ryzhakov, Mirko Farina, Ivan Oseledets
  • Scientific Reports, Volume 16, Article 4244 (2025), DOI 10.1038/s41598-025-34346-z
• Paper content matches the issue's formulation: linear binary approximation discretizes joint angles into equidistant samples represented as one-hot vectors; forward kinematics is expressed in absolute link orientations; objective minimized is squared L2 distance from achieved end-effector position to target. This matches the issue's definition and the "Extra Remark" explaining the absolute-orientation choice.

Reference 2 — Dai, Izatt, Tedrake 2019

• WebSearch confirms: "Global inverse kinematics via mixed-integer convex optimization", IJRR 38(12-13):1420-1441, DOI 10.1177/0278364919846512. Cited as broader IK-optimization context only (not as the source of the discretization), which is an appropriate framing.

Complexity claim — O(prod_{j=1}^n m_j) (or O(m^n) uniform) for exhaustive enumeration over per-link sample choices, with the constant-time admissible-pair check, is trivially correct: the search space is the product of per-link discrete domains.

Worked example verified by hand:

• link_lengths=[2,1], target=(2,1), Phi=[[0, pi/2],[0, pi/2]], A_2={(0,0),(0,1),(1,1)}.
• Feasible configurations: (0,0)→(3,0) obj 2, (0,1)→(2,1) obj 0, (1,1)→(0,3) obj 8.
• Optimum x=[0,1] with objective 0 matches the issue's claim. There are 2 suboptimal feasible solutions in addition to the optimum, which is enough to make a closed-loop test non-trivial.

Well-written

Information completeness — all required Model template sections present and substantive: Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance, Expected Outcome, plus BibTeX block.

Definition completeness — input fields, feasibility constraints ((a_{j-1}, a_j) in A_j for j=2,...,n), and objective (squared L2 distance) are all stated as precise mathematical conditions with explicit quantifiers.

Symbol/notation consistency — l_j, m_j, phi_{j,a}, Phi_j, A_j, x_j, a_j, g=(g_x,g_y), n are all defined before first use; Variables and Schema sections reuse the same names from the Definition. Naming follows convention: Minimum prefix for the optimization problem.

Schema feasibility — proposed data types (lists of positive reals, pair of reals, list of angle lists, list of pair sets) cleanly cover the stated domain.

Example quality — small enough to brute-force by hand, exercises the defining structure (multiple feasible configurations including suboptimal ones, non-trivial admissible-pair constraints), and the expected outcome is given as a concrete optimal solution with verified objective value 0.

Recommendations

• None blocking. The "Extra Remark" rationale (absolute orientations → endpoint linear in one-hot variables → naturally quadratic after substitution into the squared-L2 objective) is a nice piece of context to keep — it justifies why the QUBO companion rule in [Rule] MinimumDiscretePlanarInverseKinematics to QUBO #995 is genuinely quadratic rather than higher-degree.

[isPANN]

/review-structural — commit 41972d8 (post-impl, code-quality + bug sweep)

Verdict: pass — model lines up with issue spec; no correctness bugs; only minor test/HCI nits.

Issue compliance

• Mathematical definition matches issue: yes — squared end-effector error, per-link sampled absolute orientations, consecutive-pair admissibility A_j ⊆ {0..m_{j-1}-1} × {0..m_j-1}, indices a_j ∈ {0..m_j-1}. Constructor enforces all the stated cardinality/finite/positivity conditions.
• Schema fields match: yes — link_lengths (Vec<f64>), target_point ((f64,f64)), orientation_samples (Vec<Vec<f64>>), allowed_pairs (Vec<Vec<(usize,usize)>>) match the four fields in the issue 1:1 (names, types, descriptions).
• Canonical example: ok — canonical_model_example_specs instance with link_lengths=[2,1], target=(2,1), Phi=[[0,π/2],[0,π/2]], A_2={(0,0),(0,1),(1,1)}, optimal_config=[0,1], optimal_value=0.0 matches the issue example exactly. Search space size = 4 (well within the ≤16 deceptive-size guideline).

Structural checklist

• File src/models/misc/minimum_discrete_planar_inverse_kinematics.rs: PASS
• inventory::submit! (ProblemSchemaEntry + ProblemSizeFieldEntry): PASS
• Serialize/Deserialize derive: PASS
• impl Problem for MinimumDiscretePlanarInverseKinematics with type Value = Min<f64>, dims() = per-link m_j (correctly non-binary), variant_params![]: PASS
• #[cfg(test)] #[path = "..."] test link + test file with 6 test functions (≥3 required): PASS
• mod + pub use in src/models/misc/mod.rs; canonical-example chain wired in mod.rs:321: PASS
• declare_variants! with complexity "total_configurations" referencing the inherent getter total_configurations(): PASS
• CLI: 4 new fields in CreateArgs, included in flag_map() and all_data_flags_empty(), with two new parsers parse_f64_pair_value and parse_nested_pair_list_value in schema_support.rs: PASS. Alias resolution handled via registry (no explicit resolve_alias arm needed).
• Paper: display-name entry, problem-def block with worked example + pred-commands + figure caption. The reduction-rule to QUBO ([Rule] MinimumDiscretePlanarInverseKinematics to QUBO #995) is intentionally not in this commit. PASS.

Semantic review

• evaluate(): returns Min(None) for any infeasible config (length mismatch, out-of-range index, forbidden consecutive pair), Min(Some(squared_distance)) otherwise. Correct given Min aggregate semantics (None is the identity that gets absorbed by any Some).
• dims(): returns [m_1, ..., m_n] (non-binary), matching the per-variable domain in the issue.
• is_feasible/end_effector/squared_distance form a clean small ladder; no duplicate feasibility branching.
• Math verified by hand on the four canonical configs: (0,0)→(3,0)→2, (0,1)→(2,1)→0, (1,1)→(0,3)→8, (1,0) infeasible — all match unit tests and the paper table.
• Constructor's is_finite guards on lengths/target/angles eliminate the only realistic NaN trap for Min<f64> (partial_cmp panic on NaN).
• Size-field getter name num_links matches the ProblemSizeFieldEntry listing.

Findings

• Blockers (correctness): none.
• Nits (quality/HCI):
  • No dedicated CLI parser test for parse_f64_pair_value or parse_nested_pair_list_value — coverage relies on indirect end-to-end paths. Adding two small unit tests in problemreductions-cli/src/commands/create/tests.rs (good/bad input each) would lock in error messages like "Invalid (f64,f64) pair ..." and "Invalid pair 'X': expected i-j".
  • CLI flag help for --allowed-pairs uses | to separate junctions but the canonical 2-link example has only one junction, so the | syntax is never exercised by the canonical --example. A multi-junction example in the help string would make the format unambiguous to users.
  • is_valid_solution is a thin alias for is_feasible; only one call site in tests. Either drop it or document why both exist (probably future-proofing for reduction targets that need a separate notion).
  • total_configurations() is used as the variant complexity, but with m_j varying per link the resulting upper bound prod m_j is data-dependent rather than a closed-form. This is consistent with the issue's O(prod m_j) statement; just worth noting that other complexity strings in the codebase use closed-form f(n) expressions.