Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

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

23.01.2020

Scientists have developed the world's first fully coupled AI chip that can solve the traveling salesman problem for 22 cities instantly, something that would take about 1,200 years for a high-performance von Neumann CPU

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?


Scientists have developed the world's first fully coupled AI chip that can solve the traveling salesman problem for 22 cities instantly, something that would take about 1,200 years for a high-performance von Neumann CPU.

Credit: Tokyo University of Science

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.

###

About The Tokyo University of Science

Tokyo University of Science (TUS) is a well-known and respected university, and the largest science-specialized private research university in Japan, with four campuses in central Tokyo and its suburbs and in Hokkaido. Established in 1881, the university has continually contributed to Japan's development in science through inculcating the love for science in researchers, technicians, and educators.

With a mission of "Creating science and technology for the harmonious development of nature, human beings, and society", TUS has undertaken a wide range of research from basic to applied science. TUS has embraced a multidisciplinary approach to research and undertaken intensive study in some of today's most vital fields. TUS is a meritocracy where the best in science is recognized and nurtured. It is the only private university in Japan that has produced a Nobel Prize winner and the only private university in Asia to produce Nobel Prize winners within the natural sciences field.

Website: https://www.tus.ac.jp/en/mediarelations/

About Professor Kawahara from Tokyo University of Science

Prof Takayuki Kawahara obtained his BS, MS, and Ph.D. degrees from Kyushu University, Japan. With his MS degree, he joined Hitachi Central Research Laboratory as a research staff member. After leaving the laboratory as a Chief Researcher, he joined Tokyo University of Science in 2014 to work on developing sustainable electronics. His research group carries out cutting-edge research in the field of ultra-low-power AI devices, circuits, and systems. He is also the corresponding author of this review article. With more than 115 publications to his credit, Prof Kawahara has won numerous international awards, including the prizes for Science and Technology, Development Category, by the Minister of Education, Culture, Sports, Science and Technology.

Part of this article is based on results obtained from a project commissioned by the New Energy and Industrial Technology Development Organization (NEDO), METI, Japan.

Tsutomu Shimizu | EurekAlert!

More articles from Information Technology:

nachricht Skyrmions like it hot: Spin structures are controllable even at high temperatures
14.02.2020 | Johannes Gutenberg-Universität Mainz

nachricht Computer-based weather forecast: New algorithm outperforms mainframe computer systems
13.02.2020 | Johannes Gutenberg-Universität Mainz

All articles from Information Technology >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Skyrmions like it hot: Spin structures are controllable even at high temperatures

Investigation of the temperature dependence of the skyrmion Hall effect reveals further insights into possible new data storage devices

The joint research project of Johannes Gutenberg University Mainz (JGU) and the Massachusetts Institute of Technology (MIT) that had previously demonstrated...

Im Focus: Making the internet more energy efficient through systemic optimization

Researchers at Chalmers University of Technology, Sweden, recently completed a 5-year research project looking at how to make fibre optic communications systems more energy efficient. Among their proposals are smart, error-correcting data chip circuits, which they refined to be 10 times less energy consumptive. The project has yielded several scientific articles, in publications including Nature Communications.

Streaming films and music, scrolling through social media, and using cloud-based storage services are everyday activities now.

Im Focus: New synthesis methods enhance 3D chemical space for drug discovery

After helping develop a new approach for organic synthesis -- carbon-hydrogen functionalization -- scientists at Emory University are now showing how this approach may apply to drug discovery. Nature Catalysis published their most recent work -- a streamlined process for making a three-dimensional scaffold of keen interest to the pharmaceutical industry.

"Our tools open up whole new chemical space for potential drug targets," says Huw Davies, Emory professor of organic chemistry and senior author of the paper.

Im Focus: Quantum fluctuations sustain the record superconductor

Superconductivity approaching room temperature may be possible in hydrogen-rich compounds at much lower pressures than previously expected

Reaching room-temperature superconductivity is one of the biggest dreams in physics. Its discovery would bring a technological revolution by providing...

Im Focus: New coronavirus module in SORMAS

HZI-developed app for disease control is expanded to stop the spread of the pathogen

At the end of December 2019, the first cases of pneumonia caused by a novel coronavirus were reported from the Chinese city of Wuhan. Since then, infections...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

VideoLinks
Industry & Economy
Event News

70th Lindau Nobel Laureate Meeting: Around 70 Laureates set to meet with young scientists from approx. 100 countries

12.02.2020 | Event News

11th Advanced Battery Power Conference, March 24-25, 2020 in Münster/Germany

16.01.2020 | Event News

Laser Colloquium Hydrogen LKH2: fast and reliable fuel cell manufacturing

15.01.2020 | Event News

 
Latest News

Electric solid propellant -- can it take the heat?

14.02.2020 | Physics and Astronomy

Pitt study uncovers new electronic state of matter

14.02.2020 | Physics and Astronomy

Researchers observe quantum interferences in real-time using a new extreme ultra-violet light spectroscopy technique

14.02.2020 | Physics and Astronomy

VideoLinks
Science & Research
Overview of more VideoLinks >>>