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.

The evolution in AI from 1990 to 2010

In the year 1990 no robotics was available. The only thing what was visible during this decade were classical computing machinery which includes home computers, supercomputers and even the Internet. Until 1990 it was unclear how to program Artificial Intelligence.

On the other hand, from 2010 AI was evolving quickly and many robots were developed and existing models were improved. So the natural question is: what exactly happened in the meantime which enabled AI and robotics?

The surprising situation is, that from a computer science perspective no measurable progress was made since 1990. Even if the amount of RAM in a typical workstation has improved, and even hard drives had become larger, there was no invention available like an AI chip or a revolutionary robot algorithms. Some attempts were made to create dedicated AI programming languages, and even parallel microprocessors were created for running neural networks – but all these innovations didn't resulted in artificial intelligence.

What was created instead is located outside of computer science and it was the discovery of AI related puzzles. Perhaps it makes sense to explain this idea in detail. A puzzle in the classical sense is a thinking game, for example the rubics cube is a 3d cube with random color surfaces, while, while a sliding puzzle like 15 puzzle contains of numbers on cells which can be moved in 2d space. There are word puzzles which are called crossword puzzles and jigsaw picture puzzles.

An AI related puzzle is a certain puzzle which was invented to investigate the subject of robotics and intelligent machines. These AI related puzzles were invented from 1990 to 2010 in a high amount of diversity. There are AI Related puzzles in a physical world which is about mechanical robots and also in a virtual environment which can be realized as video games. The creation of a certain AI related puzzle describes the reality from a different standpoint. This standpoint allows to define what AI is about.

Entry level AI puzzles are the mentioned 15 puzzle problem, chess based puzzles and the traveling salesman problem. None of these puzzles has to do with computer science in the classical sense which includes computer hardware, software or algorithms, but its invented outside of computer science. Computers are only used to solve these problems.

More advanced AI related puzzles are OCR datasets used for neural network training, the visual question answering challenge, and robotics competitions like micromouse and robocup. What all these puzzles have in common is, that they fit on a single sheet of paper. The document constains the instruction what the puzzle is about. For example it consists of a map for a robot navigation task or explains what the rules of the robocup competition are. These instructions can be convertted into a computer science project which includes building of mechanical hardware and programming the robot software. So we can say, that AI puzzĺes are a meta technology which allows to create new AI related technology.

Let me give an example: A single puzzle description for the micromouse robot competition can be used as a starting point for a dozens of concrete projects. Some of the robots are realized with the Arduino microcontroller, while other are using Lego Mindstorms technology. Some of the projects might be programmed in Assembly language or with neural networks or with the C/C++ language. These detail decisions are taken place within classical computer science but they are not important for the AI problem directly. The only thing which counts is the AI puzzle itself.

The advancement in AI from 1990 to 2010 can be entirely explained with the invention of better AI puzzles. Early problems like tictacto or chess puzzles are resulting only in low quality AI projects, while later puzzles like “Mario AI”, deep learning datasets and instruction following problems in robotics are generating more advanced AI innovation. So we can say, that the main question in AI is “What sort of puzzle has to be solved?”

3a1b Top down robotics

< 3a1a What is a robot?

A less common approach in realizing robots is working with the top down method. In contrast, to bottom up robotics, intelligence is not defined as the ability to solve problems, but it is the judgment about the behavior of other who have to solve problems. Top down robotics is equal to implement a referee in software who decides which player has won the game.

The perhaps most often used example for top down evaluation function is available for the 15 puzzle game. The 15 puzzle game is implemented together with the manhattan distance scoring function to measure who far a certain position is away from the goal state. It is up to the player in the game how to minimize the costs.

 

• Production systems http://www.cs.mun.ca/~oram/cs3754/AI6.pdf
• Top down Artificial Intelligence with evaluation functions for different games