By using AI to develop a unique method for solving the “travelling salesman” problem, researchers hope that it will play a vital role in coming up with an effective solution for various combinatorial problems.
Day-to-day tasks involve travel from one place to another, be it for work, reaching an appointment in time or to deliver an important package at the right address. We are always on the lookout for the shortest, possible route that will make us reach our destination.
In this day and age, where high-performance AI technology (read Google Maps) has the potential to solve most of these problems, we still wonder whether it can come up with an even enhanced solution.
It seems we no longer need to wait. Now, a team of researchers from the Tokyo University of Science have developed an AI chip that promises to solve these issues by identifying the best suitable path in an instant.
Solving for the shortest possible route
The above issue also referred to as the “travelling salesman” problem, was tackled by the researchers in the following way: let’s assume that each possible route i.e. each state in a “travelling salesman” problem is represented by “spin cells” – each having one of two states. By using a circuit which can store the best probable outcome of one spin cell state over another, the relationship between these states (or the shortest possible route between two points) can be obtained.
To achieve this, the researchers arranged the circuits in a two-dimensional array and the spin cells separately in a one-dimensional arrangement. The circuits read the data and a cumulative of this data was then used to switch (or compare) the states of the spin cells. This resulted in a drastic reduction of time required for processing the spin cells.
So, by using a large system containing the same number of spin cells and circuits as the components (or obstacles) present in a real-life problem, the state (or route) that will require the least effort for covering a particular distance can be determined, thus solving the “travelling salesman” problem or any other type of combinatorial optimisation problem.
“We decided to arrange the cells slightly differently to ensure that all spin cells could be connected,” said Professor Takayuki Kawahara of the Department of Electrical Engineering at Tokyo University of Science.
Problem of huge data processing
However, this solution has a drawback. Integrated circuits require pre-processing in order to function as desired. As the scale of the problem increases, the number of components will also do so, which in turn will increase the time for processing data.
Despite this flaw, the researchers are hopeful that this technology will have a future application for a high-performance system to identify optimal solutions from a large number of combinations.
“Our new technique thus represents a fully coupled method,” remarks Prof Kawahara, “and has the potential to solve a (wide range of) travelling salesman problems.”
The authors of the above research presented their findings at the IEEE 18th World Symposium on Applied Machine Intelligence and Informatics (SAMI 2020).
