np hard problems as terra incognita

Computer science is an academic discipline with a long tradition. Its core elements are programming languages and algorithms. .Endless amount of source code was written in multiple programming languages, there are even esoteric languages available like Intercal and Befunge which are examples for computer art. Unfortunately, computer science consists of a seldom described weakness which are np hard problem.

An np hard problem is a mathematical challenge which can't be solved with existing programming languages nor algorithms. That means, modern languages like C++ in combination with modern 64bit operating systems like Linux isn't powerful enough to determine the shortest route for 15 cities or find the shortest sequence for solving the rubik's cube puzzle. What makes the situation more complicated is, that even after adding more RAM to a computer, np hard problems remain unsolvable.

One possible explanation why computer science is ignoring np hard problems might be, that its useless to invest ressources into problems, which can't be solved. If 100 researchers in the past have independent from each other tried to solve the Traveling salesman problem, and all of them have failed, it doesn't make much sense if additional researchers are trying to solve the same problem. .np hard problems can be compared to the perpetuum mobile in mechanical engineering which is also described as a dead end.

On the other hand there is a discipline available which is devoted to np hard problems. This discipline is called Artificial intelligence and its main problem is to solve all these unsolvable problems like rubik's cube, path planning and motion planning. Its important the difference between computer science which is only about polynomial problems vs. Artificial intelligence which is only about np hard problems. Both disciplines are trying to achieve different goals and they are operating with opposite tools.

Computer science vs artificial intelligence

AI was created as part of classical computer science, but both disciplines are operating with different assumptions. Computer science is a well defined engineering discipline which is successfully solving real world problems. For example a mathematician has a need for an electronic calculator and the machine is build and programmed by computer scientists. Or a statistician likes to store data in a table and computer scientists are programming a database which can solve this task. The result is, that doing computer science results mostly into successful projects which are evolving over the years, in the sense that todays computer have more memory and can sum up numbers faster.

In contrast, it remains unclear what the goal of Artificial intelligence is. The missing goal is a structural problem and the only way to solve it is to define goals by itself. That means, the AI community has to find objectives including the solution by itself. There is no higher instance available which has a need for robot hand or vision system, but these projects have to be formulated from scratch.

Let me give some example for self created goals only available within AI research: line following robot, robocup rescue, Tetris playing AI software, chess AI, scene recognition in motion capture recording.

All these problems have only a sense within the AI community. In the reality, nobody has a need for a line following robot or a Tetris playing AI. The only reason why these projects are researched is because of the hope for new knowledge what thinking is about. Especially in the past, successful AI research was always connected to a certain project, for example to build a machine which can play chess. A certain problem allows to benchmark an algorithm. Either the computer is able to do so or not.

In contrast, additional computer science has no need for artificial constructed problems. Computer science has no lack in existing well defined problems, but the missing resource is how to solve all these problems with better hardware and improved algorithms. AI is working the opposite way. There are endless amount of hardware and software but a lack of well defined problems.

Its a bit paradox, but AI engineers have a certain understanding about their tools. A tool isn't a computer e.g. a Unix workstation, but a tool is a problem formulation, e.g. the 15 puzzle problem or the traveling salesman problem is a tool. These tools are helping to guide the discussion into a certain direction. For example, the 15 puzzle problem is a great choice for introducing heuristics, which is not available in classical search algorithms.

The second paradox situation is, that AI isn't evolving in terms of better hardware or more intelligent software, but AI is evolving in terms of well formulated problems. In the year 2025 there are more such problems available than 20 years ago. A very recent problem is Visual question answering which was first described in 2015. The VQA challenge has evolved from similar challanges which are text based question answering which was available since 2000s. Its likely, that in 20 years from now, more advanced robotics problems are available unknown today.

How to identify Artificial Intelligence technology?

Computer science in the past was operating with certain tools which were developed once and reused frequently. These tools were located in hardware, software and algorithms and are similar to cooking recipe a blueprint how to build technology from scratch. For example, a 32bit microchip is designed with a hardware description language like VHDL, while the Unix operating system is written in the programming language C. If someone has access to the VHDL file or the c source code he can create a copy of the technology because he has a better understanding how the system is working.

A naive assumption is to translate this model towards the Artificial Intelligence domain, which is a subpart of computer science. AI can be located in hardware, software or algorithms, at least under the assumption of the computer science bias. So its natural to ask for dedicated AI hardware and AI software, in the hope to get access to advanced robotics technology.

Unfortunately, AI works quite different from the computer science paradigm. Even if dedicated AI tools were developed, for example AI related FPGA chips and AI related software libraries, there is something missing to build a robot. This something else is unknown and because of inability to locate the magic ingredient, AI wasn't realized over decades. It was unknown how exactly an AI machine or tool has to look like so it was impossible to find such tools.

With more advanced knowledge about the AI subject its possible to describe with more details what the recipe is for creating robots. The missing ingredient is a multimodal dataset. That is a .csv file which contains of motion capture data in combination with natural language annotation like “jump”, “Walk”, “stand up”. Such a dataset can be used as the core element and a robot control system can be developed around this dataset.

This description for an AI tool looks a bit uncommon because it doesn't fit to existing categories in computer science. 'Its not a hardware description, it is not an algorithm and its not the source code for a computer program. But a multi modal dataset is simply a sensor recording, similar to a temperature log file from a weather station. The usefulness will become visible only on a second look. A multimodal dataset creates a machine learning problem. The question is which sort of neural network can learn the data and how to interpolate the missing data. The attempt to answer these questions results into a robotics project.

In contrast to a numerical dataset, a multimodal dataset consists of natural language annotation in the natural language of English. These annotation transform a robot control problem into a text adventure. The textual layer is the birds eye perspective towards a problem. Every robot control problem can be interpreted as a text adventure which consists of nouns, verbs and adjectives. Natural language is the best tool to describe the reality. Let me give an example:

A kitchen robot will perceive objects like table, plate, apple and bread. Also a kitchen robot can do actions like open, close, grasp and transfer. The natural language including its vocabulary is used to identify the parts of the reality. The robot cointrol system has to memorize the same words, otherwise the human to machine interaction will fail.

In classical computer science there is no need to utilize natural language. A pocket calculator and even advanced workstation computers are working fine without knowing any vocabulary. Words from the reality like “apple” “bread” and so forth are never included in the VHDL hardware description and they aren't stored in computer programs. Sometimes these words are available as commentary, but they are not important for running the software itself. In other words, classical computers are working fine without any interaction with a human.

In contrast, a robot control system operates with the opposite paradigm. A robot is mostly a user-interface which is using the same lexicon as a human. Its impossible to build a kitchen robot without 100 and more kitchen words.

Walking downstairs

 

Isometric traffic junction with map key

 

The guess naming game

 

Its a language game for researching grounded language. The user enters a word like “green” and the computer has to highlight all the objects in the GUI which fits to the word. These game rules allow to benchmark if a certain visual dictionary was learned correctly because the computer has to map the entered textual word to the shown graphical representation on the screen.

The main advantage of the guess naming game is, that it can be realized in under 300 lines of code in Python. It explains on an example what the symbol grounding problem is about.

AI as search for a problem

 In the history of AI development it was mostly unclear, what exactly AI is about. In the 1980s a common definition was, that AI has to do with search in the problem space. But this definition fits only to small subsection of AI which is state space search in games. And search algorithms like A* can't be applied to more complex problems.

A possible improved definition is, that AI has to do with search for the problems. This definition shifts the focus away from algorithm centric solving of existing challenges towards an explorative search for new problems.

Example problem might be the 8 puzzle problem, chess puzzles, path finding in a maze, or the VQA problem (visual question answering). The assumption is, that more advanced AI techniques can be unlocked by inventing more advanced puzzles first.

Let me given an example. Suppose the self selected problem to solve is the 8 queens problem. Under such a constraint, the following debate consists of a mathematical problem description, and a comparison of different algorithms which are mostly back tracking algorithms. The decision to solve the 8 queen problem results into a certain bias.

By selecting other problems the discussion space gets modified. Especially by selecting language games like Visual question answering, the debate gets modified drastically. Instead of describe only search based algorithms, new topics have to be discussed like vocabulary definition or grounded language. These new subjects are not available in classic problems like the 8 queen problem.

So we can say, that no hard subjects within computer science like hardware, software, algorithms or programming language are creating the discourse space for Artificial Intelligence, but the debate gets influenced by the preference for certain AI problems. The decision for or against certain problems affects the discovery of possible problem solving techniques. If the attempt is to solve only the 15 puzzle problem, a certain sort of computer program is the result. But if the task is to solve problems with grounded language like the instruction following problem, more advanced algorithms are needed.

The main question which has to answered by the AI community is, what are the advantages and disadvantages of a certain problem category. The traveling salesman problem was popular in the 1980s because it can be described easily and can be converted into an mathematical algorithm. The main disadvantage of this problem is, that even the algorithm has found the shortest route, the same algorithm can't control a real robot because robotics has to be described with different problems.

The holy grail is perhaps an AI problem, which can be described easily but fits to a variety of real world robotics problems. If it matches to the reality, the algorithms used for solving the problem can be adapted to real world scenarios.

A review of AI puzzles

Puzzle problems are the framework in which the search for Artificial Intelligence takes place. The evolution from easier to more advanced understanding of AI is strongly connected to the evolution of AI puzzle problems. There are certain categories available:

1. easy: traveling salesman problem, chess problems, tictactoe game, Knight's tour, path planning
2. medium: 15 puzzle problem, piano movers problem, Tetris playing AI agent, pacman AI agent
3. advanced: dataset driven machine learning
4. hard: Visual question answering, instruction following, multimodal machine learning

Let us describe first the easy category. This sort of problems has the longest tradition in the AI literature and the problems including possible algorithms are described in high amount of papers. Nearly every introduction course in computer science, mention or explains the traveling salesman problem. It has become a standard challenge for investigating the performance of algorithms.

Most of the problem from the easy category can be solved with a backtracking algorithms. In case of chess problems, the algorithms needs improvement from an evaluation function but the main principle is to traverse the state space.

The problems from the medium section are less often explained and they are requiring sophisticated heuristics. The first puzzle in the section, the “15 puzzle problem” is used exclusively to explain the advantages of an evaluation function, namely the manhattan distance, while the other problems like “pacman AI agent” will need a finite state machine or an advanced behavior tree. Its not possible to solve the problem in the medium category with easy to implement backtracking algorithms because of the larger size of the state space.

The two remaining categories, advanced and hard, are only seldom described in the literature. The first papers about the subjects were published since the year 2000. For VQA related problems, the first written description is even available since 2010.

What all these problem categories have in common is, that they do not require software or hardware in terms of computer science. But the problems can be discussed independently of computer science. A typical problem description fits on a single piece of paper which reads like the description for a board game. So we can say, that the problems belong to the umbrella term of game theory. The complex reality gets simplified into game rules and the player can take decision inside the rule system.