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 at the Tokyo University of Science have developed a new chip that uses special components to calculate the shortest distance between up to 22 cities in a very short time.
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.
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.
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.
Who needs maps? Facebook has scored an impressive feat involving AI that can navigate without any map.
Facebook’s wish for bragging rights, although they said they have a way to go, were evident in its blog post, “Near-perfect point-goal navigation from 2.5 billion frames of experience.”
Long story short, Facebook has delivered an algorithm that, quoting MIT Technology Review, lets robots find the shortest route in unfamiliar environments, opening the door to robots that can work inside homes and offices.”
And, in line with the plain-and-simple, Ubergizmo‘s Tyler Lee also remarked: “Facebook believes that with this new algorithm, it will be capable of creating robots that can navigate an area without the need for maps…in theory, you could place a robot in a room or an area without a map and it should be able to find its way to its destination.”
Erik Wijmans and Abhishek Kadian in the Facebook Jan. 21 post said that, well, after all, one of the technology key challenges is “teaching these systems to navigate through complex, unfamiliar real-world environments to reach a specified destination—without a preprovided map.”
Facebook has taken on the challenge. The two announced that Facebook AI created a large-scale distributed reinforcement learning algorithm called DD-PPO, “which has effectively solved the task of point-goal navigation using only an RGB-D camera, GPS, and compass data,” they wrote.
DD-PPO stands for decentralized distributed proximal policy optimization. This is what Facebook is using to train agents and results seen in virtual environments such as houses and office buildings were encouraging. The bloggers pointed out that “even failing 1 out of 100 times is not acceptable in the physical world, where a robot agent might damage itself or its surroundings by making an error.”
Beyond DD-PPO, the authors gave credit to Facebook AI’s open source AI Habitat platform for its “state-of-the-art speed and fidelity.” AI Habitat made its open source announcement last year as a simulation platform to train embodied agents such as virtual robots in photo-realistic 3-D environments. Facebook said it was part of “Facebook AI’s ongoing effort to create systems that are less reliant on large annotated data sets used for supervised training.”
(Douglas Heaven in MIT Technology Review: While Facebook trained bots for three days inside AI Habitat, “Others have taken a month or more to train bots in a similar task, but Facebook massively sped things up by culling the slowest bots from the pool so that faster ones did not have to wait at the finish line each round.”)
InfoQ had said in July that “The technology was taking a different approach than relying upon static data sets which other researchers have traditionally used and that Facebook decided to open-source this technology to move this subfield forward.”
Jon Fingas in Engadget looked at how the team worked toward AI navigation (and this is where that 25 billion number comes in). “Previous projects tend to struggle without massive computational power. Facebook taught a virtual agent to handle point-to-point navigation for the equivalent of 80 years of human experience—that’s about 2.5 billion steps.”
The result was an algorithm smart enough in indoor environments to choose the right fork in the path (as opposed to wasting time backtracking) and quickly recognize errors if headed in the wrong direction.
Heaven, in his MIT Technology Review item, was also helpful in putting the number in context. “Facebook trained bots for three days inside AI Habitat, a photorealistic virtual mock-up of the interior of a building, with rooms and corridors and furniture. In that time they took 2.5 billion steps—the equivalent of 80 years of human experience.”
Researchers focused on projects centered around assistive robots consider navigation features crucial. “Navigation is essential for creating AI agents and assistants that help people in the physical world, from robots that can retrieve an object from a desk upstairs, to systems that help people with visual impairments, to AI-powered assistants that present relevant information to people wearing augmented reality glasses,” Wijmans and Abhishek Kadiana wrote.
The authors made their case for a world less reliant on maps, too. Maps, they argued, “become outdated the moment they are created. Most real-world environments evolve—buildings and structures change, objects are moved around, and people and pets are in constant flux.”
What’s next? “We hope to build on DD-PPO’s success by creating systems that accomplish point-goal navigation with only camera input—and no compass or GPS data.”
Why no compass or GPS data? In a Jan. 21 post, Wijmans and Kadian said that “compass and GPS data can be noisy or simply unavailable in indoor spaces. We will also apply DD-PPO-trained models to different tasks.”
Fingas in Engadget was impressed over their “distributed reinforcement learning algorithm that not only reaches its destination 99.9 percent of the time without using maps, but can do so with just a three percent deviation from the ideal path.”
Actually, said Heaven in MIT Technology Review, “Mapless route-finding is essential for next-gen robots like autonomous delivery drones or robots that work inside homes and offices.”
Fingas had this to say about the technology in general: It is still “very young. It has yet to handle outdoors or complex situations, and it doesn’t handle long-distance navigation well if it has to lose sensors.” Nonetheless, Fingas noted Facebook was sharing its work in hopes of further advances.
Source:
Tokyo University of Science
