Artificial Intelligence algorithms and Kubernetes

How to create an artificial intelligence algorithm from scratch

These days, everybody knows about Artificial Intelligence, or AI, and has a general idea about how some sub-fields and techniques, like machine learning work. These techniques aim to mimic human learning by computing a function that given a set of labeled entries, that is, with the labels indicating the expected output for each entry, this function will maximize the probability of these expected outputs. Once the function is "trained" or calculated, we can apply the same function to more data and be confident that the result will be the expected one.

This approach relies heavily on having data, even if there are some techniques to create synthetic data that can help apply these techniques even when we do not have enough data.

But is learning the only artificial intelligence tool? No, of course. Even we humans do not always act according to our learned knowledge. Sometimes, we encounter a new issue and do not have old experiences or data to guide our actions. But as humans, we have another important tool. We are able to think, to reason about the world, and use our imagination to create scenarios and anticipate the results of our actions. That is, we are able to plan ahead.

Figure 1.

Machines, too, can plan ahead and reason about the world in which they exist too. There is a field of artificial intelligence appropriately called Automated Planning, where an agent, that is, an abstraction for a machine, a robot, or a program, reads an input that contains a model of the world, creates a plan, and starts applying the plan. In some cases, the agent is able to observe, read from its sensors, and update its perceptions of the world so it can react better.

In this series of articles, we will take a look at this artificial intelligence field implementing a planner as a service using Kubernetes.

We will use the A* algorithm (pronounced A-star), analyze it, and create a small Python version to test it against some problems.
In this post, we will start by talking a bit (just the necessary bits) about the automated planning, and understanding the main concepts so we can then code the algorithm more easily.

Automated Planning and Search problems

Automated Planning is the process of generating plans, an organized set of actions, to achieve a goal. These plans are created by using a representation of the world and applying actions to verify its outcomes. For example, let us consider a problem where we have a machine located in a maze (or a map), as shown in Figure 2. The agent has to reach a certain destination; in the image is cell 5–5. With the representation of the maze, the agent will analyze where each action can lead it so it can chain these reasonings in order to create a sequence of actions that will help it navigate the maze.

Figure 2: Maze problem example: green lines denote a valid plan, that reaches the goal and red ones an invalid plan.

Figure 2 shows two different plans, a valid one (painted in green) and an invalid plan (in red). The agent starts, and it can evaluate which action to take. There are several ways to select which action would be best, generally using heuristics. We will talk about that later, but for now, consider that the agent has a compass and select the action that takes him right. When reaching locations 1–3, it can continue right or take the action leading him down. Eventually, the agent will notice that continuing to go right (red path) will lead him to a wall and a dead-end. On the other hand, if he took the down action at 1–3, he could continue until he reached the goal location.

The agent comes up with a plan by searching in the space of states; that is, let us imagine the set of all possible states, where a state is a configuration of the world. The agent should be able to search a sequence of states that starts in the initial state and ends in the goal state, and the links between these states should be the actions taken by the agent.

Figure 3: searching in the space of states

We can represent a state as a set of predicates that denote the agents’ current location, as well as the wall locations and other features. In this post, we consider a predicate as the minimal element of information, that has a binary value of true or false, for example the predicate agent_at_1_1, representing the location of the agent should have a value of true on the initial state, and it can change if the agent moves. To simplify this, we can use set theory and consider that everything in a set has a value of true, and everything not in the set has a value of false.

The space of states would be the set that contains all of them. Evidently, computing such a set would be inefficient, so we start with the initial state and create the other states as we need them by applying an action to a state and computing the successor states until we reach the goal state. And this is what the search algorithm will do, expanding states until it finds a goal state and the search stops.

Elements of an automated planning problem

We have explained the main concepts of a search problem, and now it is time to explain some other concepts a bit and how we can represent them before we start coding. Due to its simplicity, we will use the maze example. So, before anything else, we should define what is the initial state and the goal state. We will define the initial state as a set of predicates. As we said before, everything that is true in the initial state should be inside this set. We include all predicates known to be true because we will consider that at the beginning of the algorithm, we know everything about the world, what is true and what is not. Imagine that we freeze or take a picture of an instant of time, and this image is the initial state.

initial_state:
  - agent_at_1_1
  - wall_at_2_2
  - wall_at_3_4
  - wall_at_4_5

On the other hand, we can reach the goal from different states, so the goal state is defined as any state that satisfies the goal condition. Because there are a multitude of goal states, an agent can achieve the goal in so many different ways. We will define the goal as a subset of predicates that any state must satisfy (that is, the set representing the state should include) to be considered a goal state. Using sets like this allows us to use the set logic and its operations, which we will see next when considering actions.

goal_condition:
  - agent_at_5_5

An action is an operator that should allow us to represent the agent modifying or interacting with the world. To represent that, and using set theory again, we represent an action as a function that will add and remove predicates:

action 
  - name: move
    cost: 1
    preconditions: agent_at_initial_position, adjacent_initial_position_final_position
    effects: 
      positive: agent_at_final_position
      negative: agent_at_initial_position

An action may initially seem complicated because of all the different fields and parameters, but do not worry, everything will make sense soon. Think of that as a template for an action instead of a real action. First of all, we need a name for an action. Every action also has a cost of application, and an optimal solution is the solution that minimizes the cost.

Next, we need the preconditions that represent where this action can be applied. In the example, we see an action to move between two positions (initial and final position) can only be applied if the agent is in the initial position and the final position is adjacent to the initial position. That makes sense, it means we can only move to adjacent positions. I said before that you should think of this example as a template because, in a real problem like the one shown in Figure 2, there should be an action for each combination of positions. The effects are divided into positive or negative effects, meaning predicates that are added or removed at the resolution of the action. Again, think of it as the set theory, added means that it will become true that the agent is at the final position after executing the action, and removing would mean that the agent is no longer at the initial position.

Usually, the state-of-the-art planners use a language called STRIPS, which is a language similar to the one I explained here, over the syntax of LISP. For clarity, I prefer to use some YAML instead.

A* algorithm pseudo-code

Now we are ready to explain the algorithm, using pseudo-code for now.

Pseudo code for A star algorithm.

Let us start by creating two queues: Open and Closed. The Open list will consist of the states that have been reached by applying an action on a state but have not been expanded yet.

And the closed list contains the states that have been reached and expanded (actions have been applied to them). The open list can be implemented using a PriorityQueue on Python, and ordering the states on the cost. This way, we guarantee that the queue will always return to the state with a the lesser cost.

Notice that the main loop will only stop when either a goal is reached or we visited all states and no solution has been found. For each iteration of the loop, we perform the following operations: (1) get the state with the lesser cost; (2) verify if it is the goal, and in such case, we stop, if not, we continue; (3) we expand the state applying all the actions applicable and compute the costs and the heuristics of the successor states; (4) add the successor states to the Open list if they have not been encountered before; and (5) close the state.

We used that word before heuristics, and now it is time to explain it a bit. A heuristic is some kind of knowledge that we can use to infer solutions to a problem from experience. Generally, we can use a simplified version of the problem to compute an approximate value. For example, for the maze problem, it could be a general direction value. A heuristic only serves to speed up the algorithm, and it is not required. We can set a default value of 0, and the problem would also work, even if it is a bit slower (it will expand more states). In the automated planning community, there are two big heuristics: (1) the Fast Forward heuristic that consists of solving the problem from each state with a different set of actions that do not contain negative effects (that is, only additive actions); and (2) the Causal Graph, that is a representation of which predicates are more important for a goal, and the heuristic value of a state indicates how far we are from having all the predicates from the goal.

Conclusions

I have explained the problem of planning in artificial intelligence and described the A-star algorithm that is the basis for most automated planning solutions.

This post is a bit long because I focused on explaining some basic concepts necessary for the next steps. Although I have yet to show everything here, in the following steps, we will deploy and test it using Python and Kubernetes. Stay tuned for my next article.