New! Sign up for our free email newsletter.
Science News
from research organizations

The easy route the easy way: New chip calculates the shortest distance in an instant

Date:
January 23, 2020
Source:
Tokyo University of Science
Summary:
Combinatorial optimization problems are problems that arise in everyday situations, involving the puzzle of determining the shortest route that can be taken between multiple points. Researchers have developed a new chip that uses special components to calculate the shortest distance between up to 22 cities in a very short time.
Share:
FULL STORY

How would you go about returning books to the correct shelves in a large library with the least amount of walking? How would you determine the shortest route for a truck that has to deliver many packages to multiple cities? These are some examples of the "traveling salesman problem," a type of "combinatorial optimization" problem, which frequently arises in everyday situations. Solving the traveling salesman problem involves searching for the most efficient of all possible routes. To do this easily, we require the help of low-power, high-performance artificial intelligence.

To solve this conundrum, scientists are actively exploring the use of integrated circuits. In this method, each state in a traveling salesman problem (for example, each possible route in the delivery truck) is represented by "spin cells," each having one of two states. Using a circuit which can store the strength of one spin cell state over another, the relationship between these states (or to use our analogy, the distance between two cities for the delivery truck) can be obtained. Using a large system containing the same number of spin cells and circuits as the components (or the cities and routes for the delivery truck) in the problem, we can identify the state requiring the least energy, or the route covering the least distance, thus solving the traveling salesman problem, or any other type of combinatorial optimization problem.

However, a major drawback of the conventional way of using integrated circuits is that it requires pre-processing, and the number of components and time required to input the data increase as the scale of the problem increases. For this reason, this technology has only been able to solve the traveling salesman problem involving a maximum of 16 states, or cities.

A group of researchers led by Professor Takayuki Kawahara of the Department of Electrical Engineering at Tokyo University of Science aimed to overcome this issue. They observed that the interactions between each spin cell is linear, which ensured that the spin cells could only interact with the cells near them, prolonging the processing time. "We decided to arrange the cells slightly differently to ensure that all spin cells could be connected," Prof Kawahara explains.

To do this, they first arranged the circuits in a two-dimensional array, and the spin cells separately in a one-dimensional arrangement. The circuits would then read the data and an aggregate of this data was used to switch the states of the spin cells. This would mean that the number of spin cells required and the time needed for processing were drastically reduced.

The authors have presented their findings at the IEEE 18th World Symposium on Applied Machine Intelligence and Informatics (SAMI 2020). "Our new technique thus represents a fully coupled method," remarks Prof Kawahara, "and has the potential to solve a traveling salesman problem involving up to 22 cities." The authors are hopeful that this technology will have future applications as a high-performance system with low power requirements for office equipment and tablet terminals for finding easily find optimal solutions from large numbers of combinations.


Story Source:

Materials provided by Tokyo University of Science. Note: Content may be edited for style and length.


Cite This Page:

Tokyo University of Science. "The easy route the easy way: New chip calculates the shortest distance in an instant." ScienceDaily. ScienceDaily, 23 January 2020. <www.sciencedaily.com/releases/2020/01/200123152500.htm>.
Tokyo University of Science. (2020, January 23). The easy route the easy way: New chip calculates the shortest distance in an instant. ScienceDaily. Retrieved March 28, 2024 from www.sciencedaily.com/releases/2020/01/200123152500.htm
Tokyo University of Science. "The easy route the easy way: New chip calculates the shortest distance in an instant." ScienceDaily. www.sciencedaily.com/releases/2020/01/200123152500.htm (accessed March 28, 2024).

Explore More

from ScienceDaily

RELATED STORIES