[Rule] MinimumDiscretePlanarInverseKinematics to QUBO

[zhangjieqingithub]

Source

MinimumDiscretePlanarInverseKinematics

Target

QUBO

Motivation

Connects a robotics optimization problem directly to the QUBO hub, enabling brute-force validation inside the library and downstream use of existing QUBO reductions and solvers.

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

Reduction Algorithm

Let the source instance be:

• link lengths l_1, ..., l_n,
• target point g = (g_x, g_y),
• sampled absolute orientations Phi_j = {phi_{j,0}, ..., phi_{j,m_j-1}},
• admissible pair sets A_j for j = 2, ..., n.

For every sampled orientation phi_{j,a}, introduce a binary variable y_{j,a} in {0,1}. Its meaning is:

• y_{j,a} = 1 iff link j selects sample a.

1. One-hot lifting.
   For each link j, replace the m_j-valued source variable x_j by the block y_{j,0}, ..., y_{j,m_j-1}.

2. Workspace coordinates.
   Define
   X(y) = sum_{j=1}^n sum_{a=0}^{m_j-1} l_j cos(phi_{j,a}) y_{j,a},
   Y(y) = sum_{j=1}^n sum_{a=0}^{m_j-1} l_j sin(phi_{j,a}) y_{j,a}.

3. Position-error term.
   Use the quadratic objective
   E_pos(y) = (X(y) - g_x)^2 + (Y(y) - g_y)^2.
   Since X and Y are linear in y, E_pos is quadratic.

4. Exactly-one penalties.
   For each link j, add
   E_onehot(y) = M sum_{j=1}^n (sum_{a=0}^{m_j-1} y_{j,a} - 1)^2.

5. Joint-feasibility penalties.
   For every forbidden adjacent pair (a, b) notin A_j, add
   E_pair(y) = Lambda sum_{j=2}^n sum_{(a,b) notin A_j} y_{j-1,a} y_{j,b}.

6. Final QUBO.
   Minimize
   E(y) = E_pos(y) + E_onehot(y) + E_pair(y).

If M and Lambda are chosen larger than the maximum possible improvement obtainable by violating feasibility, every minimizer is one-hot feasible and respects all pair constraints, and on those feasible assignments E differs from the source objective only by an additive constant.

Size Overhead

Target metric	Formula (using symbols above)
num_vars	sum_{j=1}^n m_j

Validation Method

• Brute-force the source instance and the reduced QUBO on small examples and compare optimal objective values after accounting for the dropped constant term.
• Verify that every decoded optimal QUBO assignment is one-hot feasible and corresponds to a valid source configuration.
• Include examples where a low position-error assignment is invalid because it violates a pair constraint, so the penalty terms are actually tested.

Example

1. Source instance:

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

2. Construction:
   Introduce binary variables in the order
   (y_10, y_11, y_20, y_21).

   The workspace coordinates are

   • X = 2 y_10 + y_20
   • Y = 2 y_11 + y_21

   Hence
   E_pos = (2 y_10 + y_20 - 2)^2 + (2 y_11 + y_21 - 1)^2.

   Add one-hot penalties

   • M (y_10 + y_11 - 1)^2
   • M (y_20 + y_21 - 1)^2

   The only forbidden adjacent pair is (1,0), so add the pair penalty

   • Lambda y_11 y_20

   Taking M = 10 and Lambda = 10, and dropping the additive constant, the QUBO polynomial becomes

   • -14 y_10 - 10 y_11 - 13 y_20 - 11 y_21
   • + 20 y_10 y_11 + 4 y_10 y_20 + 10 y_11 y_20 + 4 y_11 y_21 + 20 y_20 y_21

3. Target instance:
   In the variable order (y_10, y_11, y_20, y_21), the resulting upper-triangular Q matrix is

   [-14, 20,  4,  0]
   [  0,-10, 10,  4]
   [  0,  0,-13, 20]
   [  0,  0,  0,-11]
   

   The assignment y_10 = 1, y_21 = 1, and all other variables 0 is feasible, decodes to the source configuration x = [0,1], and is optimal for this example.

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}
}