People have always had to solve tricky problems. But with the accumulation of more and more data, new challenges have emerged that are often too complex for us. This is where Clasp comes in – a computer program developed by Potsdam computer scientist Torsten Schaub and his team. For Clasp, problems can hardly be difficult enough: From the best possible course schedule for an entire university or the optimal organization of a huge warehouse, to the autonomous composition of musical works, there is little the program cannot do. The trickier the problem, the better.
Torsten Schaub is Professor of Knowledge Processing and Information Systems at the University of Potsdam. It was by mere coincidence that he learned of his program’s biggest success so far: At the annual Artificial Intelligence Conference in New York in 2016, researchers of the Canadian University of British Columbia presented a highly complex problem – and the tool they intended to use for its solution, Clasp. The researchers had been commissioned by the US Federal Communications Commission (FCC) to organize the redistribution and auction of broadcasting licenses in the United States. What sounds quite straightforward turned out to be an enormous challenge: Existing frequencies had to be split up into new ones while avoiding interferences. In addition, the large number of frequencies had to be available at almost the same time to be put up for auction. The resulting mathematical formula contained millions of variables. Just the thing for Clasp, as it turned out!
AI searching for conflicts
Clasp is a conflict-driven answer set solver. “A universal problem solver,” as Schaub puts it. “It solves the most diverse combinational optimization problems, the ones that are particularly knowledge-intensive and contain many variables.” That is why Clasp is considered artificial intelligence. While for a long time, software did only exactly what it had been programmed for, AI systems such as Clasp unfold their full potential when “fed” with a problem. “A normal computer program isn’t intelligent, it doesn’t make decisions, as the solution path is laid down in its program code,” Schaub explains. But Clasp is different. “We just define the problem, the solution path is found autonomously.” This is possible because the system consists of mathematical algorithms capable of learning from mistakes. Not only can Clasp deal with mistakes, it actually depends on them. “When solving a task, the system starts at an early point to look at conflicts and draw conclusions from them. As soon as a conflict occurs, it jumps back to the root of the conflict, enriches the problem with the new information, and continues its calculations,” Schaub says.
“At the very beginning, we used a lot of classic combinatory tasks such as the problem of the travelling salesman.” We also included Sudoku puzzles among the early training tasks. Today, this example is used to introduce students to the topic. “They can easily relate to it, since everyone is a Sudoku expert in one way or another,” Schaub says with a smile. But soon the first real applications began. For instance, information scientists at the University of Potsdam teamed up with biologists in the analysis of biological networks. With the help of Clasp, the researchers drew up timetables for entire universities that had to combine rooms, times, and professors for several thousand courses. And the results outdid those of any other program to this day. Over the years, students, PhD candidates, and staff members have applied Clasp in more and more fields to solve problems as diverse as the control of robot swarms, optimum shelf space allocation, route-planning for logistics operators, the design of embedded systems in vehicles, or the autonomous composition of musical works. Some years into its development, Schaub and his team began to stabilize the system. It was ready for everyday applications.
Now in worldwide use
Since Clasp and some “related” solver systems were developed as part of a project funded by the German Research Foundation (DFG), they have been open-source and free since the beginning. Over the years, they have been downloaded more than 160,000 times. “Today, our software is so popular that I can’t even tell who is using it,” Schaub states. In any case, it is well-known for being used in the configuration of the open-source operating system Linux. Clasp makes the decision on what versions of what components may be uploaded to a certain computer to make it run smoothly. But it did not take long before businesses discovered the potential of the system. In the redistribution of net frequencies in the US in the summer of 2016, it did a good job and helped save several billion dollars.
The success of Clasp is based on two important features: First, the system is among the world’s most efficient, as Schaub explains. It is now able to solve problems containing several million conditions and variables. Second, it has a modeling language that precedes the actual program which enables the user to formulate the task for the AI comparatively succinctly and comprehensibly. The problem definition by which Clasp solves Sudokus is just seven lines long. “When the problem to be solved by the system is formulated well, Clasp becomes a powerful tool,” Schaub explains. “It is predestined for such tasks as it combines knowledge representation with processing.”
An intelligent pocket calculator
What exactly makes AI intelligent? For Schaub, this is a matter of perspective. “When I was 4 or 5 years old, my dad gave me a pocket calculator. To me, it seemed highly intelligent,” he says with a smile. “At the end of the day, the AI we program works like a pocket calculator. A very good one, of course.”
Schaub first encountered what is making headlines as AI today in his first year as a student of computer science at the Technical University of Darmstadt in the 1980s. A summer program in logic programming got him hooked. The fact that he stuck with it is now paying off. “For me, it is highly satisfying that we have moved from basic ideas to industrial production. When I came to Potsdam in 1997, we discussed basics, how to deal with incomplete information, for instance. Today, we develop systems that can be practically applied,” Schaub proudly reports. “In 20 years from pure theory to practice. That’s a giant leap.” Despite all that, AI research is still in its infancy. It has not yet reached industrial production. Developers again and again face major challenges when adapting systems developed in theory for practical applications. This is why contacts to the business community that actually uses Clasp are so important for Schaub and his team. “Our research is application-driven, as this is where new fundamental questions arise,” he says. “After all, our task is to make the technology suit a large variety of users, from big corporations to small enterprises.”
Starting a business to facilitate practical application
It is for this very reason that Schaub und his team founded “Potassco Solutions” in early 2018. “As we saw more and more companies using Clasp, we as its developers of course wanted to be involved,” Schaub says. For two reasons the company is a matter very dear to his heart: It offers former students, PhD candidates, and staff at the chair a career perspective. But first and foremost, it provides an opportunity to bring the development of Clasp forward while continuing relevant basic research beyond the DFG project. “Synergies with the research group inspire work at ‘Potassco Solutions’, and vice versa.”
One of the first projects was to set up a shift schedule for a major railway company – with 6,000 employees working morning, afternoon, and evening shifts. In doing so, Clasp had to incorporate numerous parameters: full-time and part-time work, holidays, workloads at various times of the day, and many more. After about a month, all conditions had been collected and the problem formulated. Then Clasp came in. It took the system half an hour to put together what an employee had been working on for a whole week. “The final plan was absolutely correct, even the work guidelines were factored in,” Schaub says. And it opened up many more possibilities. To give just one example, proposals were made on how to improve the shift system to reduce accumulated overtime.
Right from the outset, “Potassco Solutions” was designed as a global company. It now has eight branch offices on three continents. “We want to spread our knowledge – as we took Clasp out into the world from the very beginning,” Schaub says. But sooner or later, regional cooperation should follow, he underlines. After all, Potassco, the name of the platform on which AI systems like Clasp run and where the company got its name from, stands for “Potsdam Answer Set Solving Collection”.
The Company
“Potassco Solutions” was founded by Torsten Schaub and some of his colleagues and former staff members in early 2018. The company’s objective is to market Clasp and refine the AI system through concrete application problems.
The Project
Since 2007, Clasp has been developed within the framework of two DFG-funded projects as a solver for answer set programming, or ASP. ASP is a descriptive problem-solving paradigm with a focus on compact knowledge representation. Over the years, it has been developed into a universal problem solver. For one of the key publications on Clasp in the Artificial Intelligence Journal in 2012, Torsten Schaub and his co-authors Martin Gebser and Benjamin Kaufmann were presented with the “Prominent Paper Award 2018”. The award recognizes papers that have had a substantial impact over the past seven years.
Development of highly efficient sequential and parallel systems for model-based problem solving by result set programming (2008–2012)
Advanced Solving Technology for Dynamic and Reactive Applications (2012–2018)
The systems are freely accessible under: https://potassco.org
The traveling salesman problem is one of the best-known combinatorial optimization problems. The task is to find the shortest possible route for visiting several cities, while ensuring that no city is visited twice and the salesman returns to the original city. If you do not take the terms “city” and “route” literally, but mathematically, they describe a widespread mathematical problem that appears in many contexts, from route planning to the design of microchips and genome sequencing. The more additional conditions are added to the “route”, the more complex the problem gets. By the way, there are 43,589,145,600 possibilities for the traveling salesman to visit the 15 largest cities in Germany – and only one of them is the correct solution to the problem.
The Researcher
Prof. Dr. Torsten Schaub studied computer science at the Technical University of Darmstadt, where he also earned his doctorate. He has been the Professor of Knowledge Processing and Information Systems at the University of Potsdam since 1997.
E-Mail: torstenuuni-potsdampde
Text: Matthias Zimmermann
Translation: Monika Wilke
Published online by: Alina Grünky
Contact to the online editorial office: onlineredaktionuuni-potsdampde