Robot problems as QUBOs#

Robot problems posed as binary optimisation (QUBO), ready for classical and quantum solvers.

Three problems that a robot team actually has, each with its encoding, the true objective (without the penalty terms) and a feasibility check, so a solver’s answer can be judged on the robot’s terms and not only on the QUBO energy:

  • multi_robot_allocation(): assign every task to one robot at the lowest total cost, optionally balancing the load.

  • grasp_selection(): pick exactly k grasp candidates of high quality that do not conflict (for example because they need the same finger or the same contact point).

  • slot_scheduling(): give every robot that shares a workspace a time slot so that robots whose motions conflict never move together (graph colouring with a fixed number of slots).

The encodings are the standard penalty formulations of Lucas (2014); what this module adds is the robot vocabulary, the true objectives and the decoding.

Classes

RobotProblem

A robot problem with its QUBO encoding.

Functions

multi_robot_allocation

Assign every task to exactly one robot.

grasp_selection

Choose exactly k grasps of high total quality that do not conflict.

slot_scheduling

Give every robot a time slot so that conflicting robots never share one.
class RobotProblem(name, qubo, objective, feasible, decode)[source]#

Bases: object

A robot problem with its QUBO encoding.

Variables:

  • name (str)

  • qubo (Qubo) – The encoding; variable order is documented by each builder.

  • objective (callable) – objective(x): the true objective of a bit string (lower is better), without penalties.

  • feasible (callable) – feasible(x): whether the bit string satisfies the problem’s hard constraints.

  • decode (callable) – decode(x): the bit string in the robot’s vocabulary (who does what, which grasps, which slots).

Parameters:
optimum()[source]#

Exhaustive optimum of the true objective over feasible bit strings (n at most 22).

Returns:

multi_robot_allocation(costs, balance=0.0, penalty=None)[source]#

Assign every task to exactly one robot.

Parameters:

  • costs (array_like) – costs[r, t]: cost of robot r doing task t (travel time, energy, …).

  • balance (float, optional) – Weight of a load-balancing term \(\lambda \sum_r (\sum_t x_{r,t})^2\) that discourages piling tasks on one robot (0 ignores balance).

  • penalty (float, optional) – One-robot-per-task penalty (default: large enough to dominate the costs).

Returns:

RobotProblem – Variable \(x_{r,t}\) has index r * n_tasks + t. objective is the total cost plus the balance term.

Examples

>>> import numpy as np
>>> from quantum_mind.computing import multi_robot_allocation
>>> p = multi_robot_allocation(np.array([[1.0, 5.0], [4.0, 2.0]]))
>>> x, value = p.optimum()
>>> p.decode(x), value
({0: [0], 1: [1]}, 3.0)
grasp_selection(quality, conflict, k, penalty=None)[source]#

Choose exactly k grasps of high total quality that do not conflict.

Minimises \(-\sum_i q_i x_i + \sum_{i<j} c_{ij} x_i x_j\) subject to \(\sum_i x_i = k\).

Parameters:

  • quality (array_like) – quality[i]: quality of grasp candidate i (for example a force-closure margin), higher is better.

  • conflict (array_like) – Symmetric (n, n) matrix; conflict[i, j] > 0 is the cost of choosing both i and j.

  • k (int) – Number of grasps to choose.

  • penalty (float, optional) – Cardinality penalty (default: large enough to dominate).

Returns:

RobotProblem – Variable i is grasp i. objective is \(-\sum q_i x_i + \sum c_{ij} x_i x_j\).

slot_scheduling(conflicts, n_slots, penalty=None)[source]#

Give every robot a time slot so that conflicting robots never share one.

Parameters:

  • conflicts (array_like) – Symmetric 0/1 (n, n) matrix; conflicts[i, j] = 1 if robots i and j must not move together.

  • n_slots (int) – Number of time slots available.

  • penalty (float, optional) – One-slot-per-robot penalty (default 2 times the number of conflicts plus 2).

Returns:

RobotProblem – Variable \(x_{i,s}\) has index i * n_slots + s. objective is the number of conflicting pairs that share a slot (0 is a valid schedule).