Researchers have developed an optimization technique that combines nature-inspired and hybrid quantum algorithms to solve robot trajectory planning problems at an industrial level, a use of Quantum Technology in action. They’ve achieved excellent problem representation by separating dependent and independent problems and encoding the constraints.
Robot motion planning finds applications in autonomy, automation, and logistics. Typical examples of robot motion planning in automation are welding and applying paint and adhesives to car parts. The challenge of robot motion planning is that many robots are needed for specific operations.
For instance, hundreds of robots are required for a single plant in body and paint shops alone. Their goal, therefore, is to assign robotic tasks sequentially within the given time cycle to balance the load between the robots.
Quantum computers have the potential to address complex issues in nearly every field, particularly those related to chemistry and optimization. The introduction of quantum annealing devices like the Quantum annealers from D-Wave Systems Inc. sparked a surge of interest in creating heuristic techniques to solve discrete problems that are quantum-native optimization issues.
It is yet to be known what hardware and algorithm will bring the quantum advantage, hence, the need to design optimization methods that can bridge the gap until scalable quantum technology becomes accessible.
To achieve this, the researchers used a dualistic approach; one involves designing and implementing a corresponding nature-inspired solution method that can integrate quantum computing hardware into its larger framework and provide business value presently. The other is analyzing and supplying small-scale numerical experiments on quantum annealing hardware. We will talk about the Biased Random-Key Genetic Algorithm, Dual Annealking, and also the Quantum Annealing and QUBO Formalism
Biased Random-Key Genetic Algorithms
Biased random-key genetic algorithms (BRKGA) are a heuristic framework for addressing nature-inspired optimization problems, an improvement over Bean random-key genetic algorithm. BRKGA works because an optimization problem solution may be encoded as a vector in which each element is a real integer produced at random in the range (0, 1]. It can be applied to continuous optimization problems like sequencing.
Suggested extensions for BRKGA are parallel decoding and developing multiple populations.
Dual Annealing
Dual Annealing (DA) is a random nature-inspired optimization algorithm. The researchers applied a DA implementation that is based on Generalized Simulated Annealing (GSA), which combines classical simulated annealing (CSA) and extended fast simulated annealing (FSA) into a single unified algorithm as provided in the SciPy library.
The form of GSA’s visiting distribution is determined by the visiting parameter qv, a modified Cauchy-Lorentz distribution. This dual annealing process of GSA followed by the L-BGFS-B algorithm continues until it converges or quits after reaching maximum iteration, as determined by the method’s hyperparameter maxiter.
The problem will be cast as a QUBO (or equally Ising) Hamiltonian and then transferred onto the QPU to solve a combinatorial optimization problem. Quantum annealing is then used to find a high-quality variable configuration. The result is then linked to a bit-string (of logical variables) correlating with the original optimization problem’s solution.
The procedure is repeated until a configuration of variables that minimize the objective function is found and statistical analysis is performed.
Quantum Annealing And The QUBO Formalism
The two concepts available for quantum computing involve (universal) circuit-based quantum computers and (special-purpose) quantum annealers. Although circuit-based devices can speed up growth for specific applications, current QPUs deliver around one hundred (physical) qubits making it challenging to scale up circuit-based devices.
Also, perfect (logical) qubits must be achieved to unlock such speed ultimately. Quantum annealers, on the other hand, are special-purpose machines built to address particular quadratic combinatorial optimization problems in the (QUBO) category.
QUBO Formalism
The QUBO framework has recently emerged as a vital technique for a wide range of NP-hard combinatorial optimization problems, but with the potential for a substantial variable cost in particular application situations. An example is the maximum cut problem. QUBO will be applied in the robot motion planning.
Quantum Annealing
They used quantum annealing (QA), a method for solving combinatorial optimization problems using special-purpose quantum hardware and employing quantum Monte Carlo software implementations on classical hardware. Here, the solution to the optimization problem is encoded in the ground state of the so-called Hamiltonian Hˆ problem. During the annealing process, the chance of finding a classical configuration converges to a significantly peaked distribution around the HIsing ground state.
The present quantum annealers based on superconducting technology only have limited connectivity, meaning that not every qubit is physically coupled to every other qubit; the on-chip matrix Jij is usually sparse. If the logical connectivity of the problem doesn’t correspond to the underlying hardware, an embedding process will be carried out. The process is meant to integrate physical qubits into one logical qubit that can be used to mimic the physical connection.
Overall, they’ve created an end-to-end optimization pipeline that combines conventional random key methods with quantum annealing to provide a quantum-ready, future-proof solution.
