What is an agent in artificial intelligence

This is how intelligent agents work - basic strategies

What Makes an Artificial Agent Intelligent?

We humans tend to think of a system as intelligent, especially when and as long as we don't know exactly how it works. When there was no computer that could beat professional chess players, people were convinced that a system had to be really "intelligent" if it could actually defeat the best people in chess on its own.

After the system was built (IBM’s DeepBlue) and was able to beat the best chess players in the world, the perception turned very quickly because it was after alljust was a sophisticated algorithm, combined with a lot of computing power (according to the standards of the time).

Intelligence is what we don't understand

The situation is similar with many other problems that today can apparently be solved naturally with AI algorithms, but which not long ago were certain that intelligence was required to solve them. On the one hand, the perception of intelligence is influenced by whether we fully understand the way in which solutions are found. On the other hand, intelligence always relates to a specific problem, and people are very good at using their intelligence to solve it very many different types of problems to use.

Intelligent agents, on the other hand, are already very good at certain problems to solve, and they can often do this much faster and better than humans. The boundaries of what can be described as intelligent are therefore fluid. An agent who can solve even the most difficult sudoku in a few milliseconds is obviously intelligent at solving sudokus. It is not a self-learning system because it is based on fixed algorithms, but it independently finds the solution for every problem in its domain, even if it has never seen it before.

The strategies that are used for such intelligent agents are the basis for many applications and further developments of artificial intelligence and self-learning systems. It is therefore worth taking a look at how intelligent agents work.

This is how intelligent agents work

The basic strategy of artificial agents can be illustrated well using the example of various games / puzzles. Let's start with the number puzzle Sudoku.

In a table with 9 × 9 fields, which is divided into 9 sub-tables with 3 × 3 fields each, the numbers from 1-9 should be entered in such a way that every number in every row and column and in every sub-table occurs only once. This restriction ensures a relatively clear solution for simple Sudokus, as long as you always have all columns, rows and sub-tables and the numbers already used in view.

The numbers already available for each row, column and sub-table result in a limitation of the possibility space (constraint) for the remaining empty fields of the respective category. So there are only certain numbers left that can be used for these fields.

Possibility rooms of a simple Sudoku

Constraint Propagation - Narrowing down the possible solutions

The first strategy of an intelligent Sudoku agent is therefore to have an always up-to-date overview of the numbers that are still possible for each empty field. Whenever a new number can be entered, the space of the remaining empty fields is updated accordingly, if they are affected by it. This strategy is called Constraint propagation.

Simple Sudokus, in which there is always at least one clear next empty space, can be solved with this strategy alone. With more difficult Sudokus, however, you often come to points where there is no clear next step, but two or more options, of which only one is correct.

The second strategy then applies to both people and machines: the search.

Search - Search strategies of intelligent agents

When an intelligent agent has more than one option for the next step, it begins by trying each option one at a time. The selection of the search algorithm and, if necessary, an evaluation function for the options available, decides on the search sequence and thus also on the efficiency and speed of the search.

One of the simplest variants is the Depth first search. This is a search algorithm that always searches the available decision trees first in the direction of possible end goals. This means that each branch is first searched through to the end before the next branch comes in turn. In contrast, the Breadth first search searches each level of the decision tree completely before searching one level deeper.

Both variants are so-called Brute force Strategies, i.e. one tries to solve a problem with sheer computing power by simply calculating all possible variants to the end. If the search space is simply too large for this, more complex and powerful search algorithms such asUniform Cost Search and A-Star Search for use. In our Sudoku example, a depth-first search is a sufficient strategy to find solutions even for extremely difficult Sudokus. The search can be simplified by useful additional rules:

Of course, it makes sense to first try out the field with the fewest possibilities and start the search through the decision tree there. Furthermore, the constraint propagation can also be improved by using the possibility spaces, for example, with the Naked twinsstrategy further restricts:

Naked Twins - Efficient strategies for combining search and narrowing

If two fields only have the same two numbers as the current possibility space, it is not known which number belongs to which field, but it is clear that all other fields within the affected rows, columns and sub-tables do not contain this number can. Both numbers can therefore be deleted from the scope of all other affected fields.

The intelligent agent's Sudoku algorithm then works in a loop as follows:

  1. Constraint Propagation - Update of the possibility rooms
  2. OnlyChoice - Fill in fields where there is a clear possibility
  3. NakedTwins - Apply further restriction of the possibility spaces
  4. Search - Selection of the field with the fewest possibilities, re-applying the above strategies including search until a solution or an error is returned

As a result, the intelligent Sudoku agent can also solve diagonal Sudokus of the most difficult category in a few milliseconds. The agent's solution process slows down, for example:

How an intelligent agent solves a difficult diagonal Sudoku (display greatly slowed down)

Summary

Searching for and narrowing down the space of possibility are efficient strategies with which specialized intelligent agents can intelligently solve a wide range of problems. Even if these are “only” algorithms, these agents are undeniably very intelligent in solving the problems of their specialty and, above all, much faster, more reliable and better than human agents.

Interestingly, the development of intelligent agents for certain tasks can also lead to the fact that people who previously found this task interesting and were happy to solve it, are hardly interested in the manual solution afterwards. An example is the calculator - or maybe Sudoku as well?


Graphic Depth-First Search vs. Breadth-First Search: UNSW, Sydney

Graphic possibility spaces of a simple Sudoku: By Wikipit CC BY-SA 3.0

/ 1 comment / by Roland Becker