AI expands capacity of the ‘Travelling Salesman’ problem

The ‘Travelling Salesman’ problem is essentially a problem of combinatorial optimization, or simply, finding the most efficient route between two points out of all possible options. To tackle this, researchers at the Tokyo University of Science have used integrated circuits (ICs) to formulate a high-performance low-power AI-mapping system that can find the point of maximum efficiency.

The system allots a particular ‘spin cell’ to each possible ‘state’ in the problem and places them on a circuit to map their strength. Comparing all spin cells reveals the one that spends the least amount of energy on the circuit. This is the optimized solution to the problem – in other words, the shortest route.

Additionally, processing time is much reduced by placing the circuits in a two-dimensional array and the spin cells separately in a one-dimensional arrangement. This helps in overcoming the problem of scale as well. Currently, ICs require pre-processing, and as the number of components and inputs increase, the comparison of spin cycles takes an even greater amount of time and energy. Avoiding the issue of placement has allowed the maximum states to rise from 16 to 22, with possibilities for further increase.