IMAGINE having to solve a jigsaw puzzle with 1 million pieces, without knowing what the final picture is supposed to look like.
It is a challenge that computer designers and logistics planners grapple with every day. Now a version of DeepMind鈥檚 game-playing artificial intelligence can come up with a more efficient solution.
The method might have applications in networking problems including routing traffic through cities, couriering deliveries across a country and designing more efficient computer chips.
Advertisement
Gregory Diamos and his colleagues at Baidu Research鈥檚 Silicon Valley AI Lab developed their algorithm based on DeepMind鈥檚 AlphaGo Zero AI, which has a superhuman level of play in Chinese strategy game Go.
The team set the algorithm to work on a maths problem called graph colouring. This involves colouring in the nodes of a network, or graph, using as few shades as possible while ensuring no adjoining nodes share a hue.
In real life, colours could represent resources to be allocated, ranging from transistors in a computer chip to the aircraft available for commercial flights.
鈥淚t has a wide range of applications, including the best postal routes for thousands of deliveries鈥�
Diamos鈥檚 team trained the AI on graphs from various fields, including on social networks and circuit design. Some of the training graphs were much larger than those corresponding to a game of Go, which lasts up to a few hundred moves.
The AI was 10 per cent more efficient at colouring big graphs than existing programs.
People tend to be better than computer programs at solving network problems, says Diamos, but the sheer scale of some graphs makes the task impossible to do by hand. Building a computer processor, say, requires billions of transistors to be laid out. 鈥淚t鈥檚 like building a skyscraper one grain of sand at a time,鈥� he says.
Diamos thinks AlphaGo solves the problem in a similar way to people. 鈥淚t can play a lot of games and build upon what it鈥檚 learned to make a better decision next time,鈥� he says ().
Graph colouring is related to another task known as the travelling salesman problem, which involves determining the shortest possible route for a salesperson to visit a number of places and return to their city of origin. It also has a wide range of applications in logistics, including the best postal routes for thousands of deliveries.
While this AI wasn鈥檛 tested on the travelling salesman problem, the algorithm might also perform well at it, says Le Song at the Georgia Institute of Technology. 鈥淚t鈥檚 a family of problems,鈥� he says. 鈥淎lthough none of them are the same exactly, they have some similar characteristics.鈥�
Creating an algorithm that can optimise graphs of different sizes and types is still a limitation in the field, says Song.
鈥淵ou get much better performance if you train on graphs that are similar to the graphs that you want the algorithm to be used for,鈥� says Diamos.
鈥淓ven with these algorithms like AlphaGo, it鈥檚 really unlikely we鈥檙e getting anywhere close to the best solution,鈥� he says, because of the sheer size of the graphs. 鈥淏ut we can at least make an improvement over what we鈥檙e currently doing.鈥�
