💻 computer science

Ising Acceleration for Multi-Robot Multi-Target Planning

This paper demonstrates that compact CMOS Ising machines can serve as effective low-power accelerators for specific layers of multi-robot multi-target planning, achieving up to 8,000x energy savings in target sharing and 130x overall energy reduction with minimal route quality degradation through a novel hardware-aware mapping pipeline.

Original authors: Ahmet Efe, Recep B. Uludag, Chris H. Kim, Ulya R. Karpuzcu

Published 2026-08-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ahmet Efe, Recep B. Uludag, Chris H. Kim, Ulya R. Karpuzcu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the brain of a fleet of tiny, battery-powered robots. Your job is to send them out to find hidden treasures in a giant, obstacle-filled warehouse. You have to decide three things for every robot: which treasures to grab, in what order to visit them, and how to walk around the boxes without bumping into them. This is a massive puzzle called "combinatorial optimization." It's like trying to solve a Sudoku where the numbers keep moving and the grid keeps changing.

Usually, robots solve these puzzles using standard computer brains. But standard brains are hungry; they guzzle electricity, which is a problem for robots running on small batteries. Recently, scientists have built a new kind of tiny, super-efficient computer chip called an "Ising machine." Think of it not as a calculator that counts step-by-step, but as a physical system that settles into a low-energy state, like a ball rolling down a hill to find the deepest valley. These chips are incredibly fast and use almost no power, but they are also very small and have strict rules about how big a puzzle they can hold. The big question is: Can we squeeze these complex robot planning problems into these tiny, finicky chips to save energy, or are they just too limited?

This paper explores exactly that question. The researchers tried to use a real, compact CMOS Ising chip (a physical device with 45 tiny switches) to help plan routes for multiple robots. They didn't try to force the whole giant puzzle onto the chip at once, because the chip would simply explode under the pressure. Instead, they invented a clever "pipeline" that breaks the big problem into tiny, bite-sized pieces that fit on the chip, solves those pieces, and then stitches the answers back together.

Here is what they found:

The Chip is a Specialist, Not a General Manager: The chip is amazing at generating candidates (possible solutions) for small parts of the problem, but it can't fix broken solutions on its own. The main robot computer (the "host") still has to do the heavy lifting of checking if the answers make sense and putting them together.
Three Layers, Three Different Problems: The planning process has three layers, and each one hits a different wall with the chip:
1. Pathfinding (Finding the way): The chip can solve this very well if you only look at a tiny 5x5 square around the robot at a time. By sliding this window forward, the robot can navigate the whole map. This method used 37 times less energy than a standard computer method.
2. Target Sharing (Who gets what): The chip is great at splitting a group of targets between robots. This method was a massive winner, using 8,000 times less energy than the standard approach.
3. Tour Construction (The order of visits): This was the tricky part. The chip's internal rules (its "coefficient range") were too weak to handle the strict math needed to ensure a robot visits every target exactly once without repeating. The researchers had to use a computer simulation of the chip for this part, which still showed great promise but couldn't run directly on the physical hardware yet.
The "Multi-Mapping" Trick: Since the chip is finicky, the researchers didn't just try to map the problem one way. They tried mapping it in four different ways at once (like trying to fit a square peg in a round hole by squishing it, stretching it, or turning it sideways). They found that no single way worked best every time; using a mix of approaches made the system much more reliable.

In the end, the full system (the "Ising pipeline") managed to create routes that were only 9% worse than the best standard computer methods, but it did so using 130 times less energy. The paper concludes that while these tiny chips can't replace the main robot brain yet, they are perfect "low-power accelerators" for specific, small tasks. If you want your robot to last longer on a battery, you don't need a bigger brain; you just need to let a tiny, efficient helper chip do the heavy lifting for the small, tricky bits of the puzzle.

Technical Summary: Ising Acceleration for Multi-Robot Multi-Target Planning

Problem Statement

Autonomous robotic systems, such as warehouse fleets and search-and-rescue teams, operate under strict energy budgets while facing complex combinatorial planning challenges. The Multi-Robot Multi-Target (MRMT) planning problem involves three interleaved tasks: assigning targets to robots (target sharing), ordering the visit sequence for each robot (tour construction), and finding obstacle-avoiding paths between waypoints (pathfinding).

While classical solvers for these problems are mature, they rely on general-purpose processors that can be energy-prohibitive for battery-powered platforms. Ising machines, which approximately minimize quadratic binary objectives via hardware dynamics, offer a potential low-power alternative. However, current compact CMOS Ising chips face significant constraints: limited spin counts (e.g., 45 spins), narrow integer coefficient ranges, and fixed hardware interfaces. It remains unclear whether these constraints prevent the direct mapping of realistic robotics workloads or if a hardware-aware decomposition strategy can enable effective acceleration.

Methodology

The paper proposes a hardware-aware Ising mapping pipeline that treats the Ising chip not as a standalone planner, but as a low-power candidate-generation accelerator within a classical planning loop. The host processor handles decomposition, validation, scoring, and global stitching, while the Ising chip solves small, decomposed subproblems.

1. Workload Characterization

The authors analyze the three MRMT layers to identify specific hardware bottlenecks:

Pathfinding: Direct formulations (cell-based, edge-based, or time-expanded) exceed the 45-spin budget even for modest grid sizes (e.g., 100+ variables for a 10×10 grid).
Tour Construction: Standard Traveling Salesman Problem (TSP) formulations require $N^2$ variables and strong "one-hot" penalty constraints. While spin counts for small $N$ might fit, the required penalty coefficients often exceed the narrow integer range of CMOS chips, leading to invalid permutations.
Target Sharing: The Multiple TSP (mTSP) formulation scales as $O(RN^2)$ , far exceeding spin budgets.

2. The Multi-Mapping Pipeline

To overcome hardware limits, the pipeline employs a portfolio approach rather than a single deterministic mapping. It generates multiple hardware-compatible variants of a logical problem and selects the best valid candidate based on the original objective function. Key techniques include:

Decomposition: Breaking global problems into chip-sized subproblems (e.g., spatial patches for pathfinding, clusters for tours, recursive splits for sharing).
Spin Merging: Duplicating overloaded logical spins onto extra physical spins to redistribute large couplings and reduce coefficient magnitudes.
Coefficient Quantization: Applying different rules (linear, clipped, rank-based, square-root) to map real-valued coefficients to the chip's limited integer range.
Spin-Budget Branching: Freezing a subset of variables to enumerate assignments for subproblems slightly larger than the spin budget.

3. Layer-Specific Ising Methods

Patch-Sliding Pathfinding: The map is divided into small 5×5 spatial patches. A cell-based QUBO is solved on the patch using spin merging to handle connectivity penalties. The host ranks local targets and stitches valid local paths into a global route.
Clustered Tour Construction: Targets are recursively split into distance-based clusters. Clusters are ordered, and each cluster is solved as a local open TSP. Due to coefficient range limitations preventing direct chip execution, this layer is evaluated using a logical Ising solver (Tabu sampling) with the same 45-spin constraints to project chip performance.
Recursive Target Sharing: Robots and targets are recursively partitioned using distance-weighted graph cuts. Coefficient quantization is applied to the split objectives. The host fixes anchor nodes to guide splits and assigns "robotless" bundles to the robot with the minimal marginal cost increase.

Key Contributions

Hardware-Aware Characterization: The paper identifies that different planning layers stress different hardware limits: pathfinding and target sharing are primarily spin-limited, while tour construction is limited by coefficient range due to permutation constraints.
Multi-Mapping Pipeline: A novel framework that decomposes problems into chip-sized subproblems and evaluates a portfolio of mappings (via spin merging, quantization, and branching) to recover useful candidates from limited hardware.
Three Ising-Based Planning Methods:
- Patch-sliding pathfinding with spin merging.
- Clustered tour construction with spin-budget branching (evaluated logically).
- Recursive target sharing with coefficient quantization and batching.
End-to-End Evaluation: An experimental assessment on a real 45-spin all-to-all connected CMOS Ising chip, demonstrating that the pipeline can produce competitive routes with significantly lower energy consumption.

Experimental Results

Experiments were conducted on 10×10 grid worlds with 20% obstacle density, using a 45-spin CMOS Ising chip (8 parallel cores) and a classical host (Intel i7-12700).

Pathfinding: The Ising pipeline solved 996/1000 instances with median path lengths matching classical baselines (BFS, A*, GBFS). It achieved a 37× energy reduction (14 µJ vs. 523 µJ for A*) at the cost of higher latency (1.6 ms vs. 35 µs).
Tour Construction: Using a logical Ising backend to project chip performance, the method achieved a median optimality gap of 0.0% (matching exact brute force) and a mean gap of 1.63%, outperforming nearest-neighbor and 2-opt. Projected energy was 770× lower than 3-opt.
Target Sharing: The recursive Ising method achieved a median total route cost of 29.0, compared to 28.0 for the strongest classical baseline (Sequential Single-Item Auction, SSA). It achieved an 8,000× energy reduction (9 µJ vs. 73 mJ).
End-to-End Pipeline: The full Ising pipeline produced routes within 9% of a strong classical baseline (SSA + 3-opt + A*) while consuming 130× less energy. The primary bottleneck was pathfinding latency due to the sequential nature of the patch-sliding approach.
Multi-Mapping Efficacy: The study confirmed that no single mapping rule (spin merging style or quantization method) dominates; evaluating a portfolio of mappings significantly improved success rates and robustness.

Significance and Claims

The paper claims that compact CMOS Ising machines can be effective accelerators for specific parts of the robotics planning stack, provided the system is designed around the hardware's constraints. The authors emphasize that:

Direct global mapping is insufficient: Realistic planning problems exceed current spin and coefficient limits.
Candidate Generation vs. Global Solving: The most effective role for near-term Ising hardware is generating candidates for local combinatorial subproblems, while classical logic manages decomposition, validation, and global consistency.
Hardware-Aware Design is Critical: Spin count, coefficient range, and decode validity are not merely implementation details but fundamental determinants of which planning layers can be offloaded.
Energy Efficiency: The proposed pipeline demonstrates that significant energy savings (up to 8,000× in specific layers) are achievable, making Ising acceleration attractive for energy-constrained robotic platforms, even if latency remains a trade-off.

The work concludes that as CMOS Ising chips scale in spin count and precision, the proposed pipeline can be extended to larger patches and more integrated planning systems, but current utility relies on a hybrid, hardware-aware architecture.