Artificial Intelligence

---

Shortcut to this page: ntrllog.netlify.app/ai

Info provided by Artificial Intelligence: A Modern Approach and Professor Francisco Guzman (CSULA)

What is AI?

Well, it kinda depends on what we think makes a machine "intelligent". Is it the ability for the machine to act like a human? Or is it the ability for the machine to always do the mathematically-optimal thing? And is intelligence a way of thinking or a way of behaving? These are the four main dimensions that researchers are using to think about AI.

Acting humanly: The Turing test approach

Let's say we ask a question to a computer and some people and get back their responses. If we can't tell whether the responses came from a person or from a computer, then the computer passes the Turing test.

Thinking humanly: The cognitive modeling approach

While the Turing test is just focused on the computer's results, some people are more interested in the computer's process. When performing a task, does a computer go through the same thought process as a human would?

Thinking rationally: The "laws of thought" approach

The world of logic is pretty much, "if these statements are true, then this has to be true". If we give a computer some assumptions, can it reason its way to a correct conclusion?

Acting rationally: The rational agent approach

A computer agent is defined to be something that can operate autonomously, perceive their environment, persist over a prolonged time period, adapt to change, and create and pursue goals. A rational agent acts to achieve the best outcome.

There's a subtle distinction between "thinking" rationally and "acting" rationally. Thinking rationally is about making correct inferences. (What's implied here is that there is some (slow) deliberate reasoning process involved.) But it's possible to act rationally without having to make inferences. For example, recoiling from a hot stove, which is more of a reflex action than something you come to a conclusion about.

So AI is the science of making machines act rationally, a.k.a. doing the right thing. The "right" thing is specified by us to the agent as an objective that it should complete. This way of thinking about AI is considered the standard model.

Beneficial machines

But the problem with the standard model is that it only works when the objective is fully specified. In the real world, it's hard to specify a goal that is complete and correct. For example, if the primary goal of a self-driving car is safety, then, of course, it's safest to just not leave the house at all, but that's not helpful; there needs to be some tradeoff. Inherently, there is a value alignment problem: the values put into the machine must be aligned with our values. That is, the machine's job shouldn't be to just complete its objective; it should also consider the costs, consequences, and benefits that would affect us.

Agents and Environments

A little more formally, an agent perceives its environment through sensors and acts upon that environment through actuators. Its percept sequence is the complete history of everything it has ever perceived. The agent looks at its percept sequence (and its built-in knowledge) to determine what action to take.

Let's take a look at a robotic vacuum cleaner. Suppose the floor is divided into two squares `A` and `B`, and that the vacuum cleaner is on square `A`. We can create a table that (theoretically) lists all the percept sequences and the actions that (we think) should be taken for each one.

Percept sequence	Action
Square `A` is clean	Move right
Square `A` is dirty	Clean
Square `B` is clean	Move left
Square `B` is dirty	Clean
Square `A` is clean, Square `A` is clean	Move right
Square `A` is clean, Square `A` is dirty	Clean
`vdots`	`vdots`
Square `A` is clean, Square `A` is clean, Square `A` is clean	Move right
Square `A` is clean, Square `A` is clean, Square `A` is dirty	Clean
`vdots`	`vdots`

In this very simplified scenario, it's pretty easy to see what the right actions should be. But in general, it's a bit harder to know what the correct action should be.

Good Behavior: The Concept of Rationality

So how can we know what the "right" action should be? How do we know that an action is "right"?

Performance Measures

Generally, we assess how good an agent is by the consequences of its actions (consequentialism). If the resulting environment is desirable, then the agent is good. (good bot)

A performance measure is a way to evaluate the agent's behavior in an environment. We have to be a little bit thoughtful about how we come up with a performance measure though. For the vacuum cleaner, it might sound like a good idea to measure performance by how much dirt is cleaned up in an eight-hour shift. The problem with this is that a rational agent would maximize performance by repeatedly cleaning up the dirt and dumping it on the floor. A better performance measure would be to reward the agent for a clean floor. For example, we could give it one point for each clean square, incentivizing it to maximize the number of points (and thus the number of clean squares).

As we can see, it's better to come up with performance measures based on what we want to be achieved in the environment, rather than what we think the agent should do.

Rationality

Formally, for each possible percept sequence, a rational agent should use the evidence provided by the percept sequence and its built-in knowledge to select an action that maximizes its performance measure (definition of a rational agent). We can assess whether an agent is rational by looking at four things:

• the performance measure that defines success
• the agent's prior knowledge of the environment
• the actions that the agent can perform
• the agent's percept sequence to date

For our vacuum cleaner:

• the performance measure awards one point for each clean square
• the "geography" of the environment is known (but not the dirt distribution)
• the actions are moving right, moving left, and cleaning
• the agent's percept sequence consists of what square it's at and whether it's clean

Under these circumstances, we can expect our vacuum cleaner to do at least as well as any other agent.

Omniscience, learning, and autonomy

One thing that's been sorta glossed over is that the agent doesn't know what will actually happen if it performs an action, i.e., it's not omniscient. So it's more correct to say that a rational agent tries to maximize expected performance.

In order to be able to maximize expected performance, the agent needs to be able to gather information and learn.

If an agent only relies on its built-in knowledge, then it lacks autonomy. In order to be autonomous, the agent should build on its existing knowledge by learning. By being able to learn, a rational agent can be expected to succeed in a variety of environments.

The Nature of Environments

A task environment is the problem that we are trying to solve by using a rational agent.

Specifying the task environment

We can specify a task environment by specifying the performance measure, the environment, and the agent's actuators and sensors (PEAS). Yes, these are the four things we listed out when defining how an agent can be rational. The vacuum cleaner example was fairly simple though, so we can look at something more complicated, like an automated taxi.

• performance measure: correct destination, minimize fuel consumption, minimize time/cost, minimize impact on other drivers, maximize passenger safety and comfort, maximize profits
• environment: roads, traffic, obstacles, police, pedestrians, passengers, weather
• actuators: steering, accelerator, brake, signal, horn, display screen, speech
• sensors: cameras, speedometer, GPS, accelerometer, radar, microphone, touchscreen

Properties of task environments

A task environment can be fully observable or partially observable. If the agent's sensors give it access to the complete state of the environment, then the task environment is fully observable. Noisy and inaccurate sensors would make it partially observable. Or maybe the capability simply isn't available. For example, a vacuum with a local sensor can't tell whether there is dirt in other squares and an automated taxi can't know what other drivers are thinking. Basically, if the agent has to make a guess, then the environment is partially observable.

A task environment can be single-agent or multiagent. This one's pretty self-explanatory.

A task environment can be deterministic or nondeterministic. If the next state of the environment is completely determined by the current state and the agent's action, then it is deterministic. If something unpredictable can happen, then it is nondeterministic. For example, driving is nondeterministic because traffic cannot be predicted exactly. But if you want to argue that traffic is predictable, then some more reasons that driving is nondeterministic are that the tires may blow out unexpectedly or that the engine may seize up unexpectedly.

A task environment can be episodic or sequential. Classifying images is episodic because classifying the current image doesn't depend on the decisions for past images nor does it affect the decisions of future images. Chess and driving are sequential because the available moves depend on past moves, and the next move affects future moves.

A task environment can be static or dynamic. A static environment doesn't change while the agent is deciding on its next action, whereas a dynamic one does. Driving is dynamic because the other cars are always moving. Chess is static. As time passes, if the environment doesn't change, but the agent's performance score does, then the environment is semidynamic. Timed chess is semidynamic.

A task environment can be discrete or continuous. This refers to the state of the environment, the way time is handled, and the percepts and actions of the agent. Chess has a finite number of distinct states, percepts, and actions, which means it is discrete. Whereas in driving, speed and location range over continuous values.

A task environment can be known or unknown. (Well, strictly speaking, not really.) This is not referring to the environment itself, but to the agent's knowledge about the rules of its environment. In a known environment, the outcomes (or outcome probabilities) for all actions are given.

The Structure of Agents

Now we get to go over the more technical aspects of how agents work.

Recall that an agent function maps percept sequences to actions. An agent program is code that implements the agent function. This program runs on some sort of computing device with sensors and actuators, referred to as the agent architecture.

In general, the architecture makes the percepts from the sensors available to the program, runs the program, and sends the program's action choices to the actuators.

Agent programs

A simple way to design agent programs is to have them take the current percept as input and return an action. Here is some sample pseudocode for an agent program:

Theoretically though, TABLE-DRIVEN-AGENT does do what we want, which is to implement the agent function. The challenge is to write programs that do this without using a table.

Simple reflex agents

This is the simplest kind of agent. A simple reflex agent selects actions based only on the current percept; it ignores the rest of the percept history. Here's an agent program that implements the agent function for our vacuum:

Simple reflex behaviors can be modeled as "if-then" statements. If the car in front is braking, then initiate braking. Because of their structure, they are called condition-action rules (or situation-action rules or if-then rules).

REFLEX-VACUUM-AGENT is specific to the world of just two squares. Here's a more general and flexible way of writing agent programs:

This approach involves designing a general-purpose interpreter that can convert a percept to a state. Then we provide the rules for specific states.

While simple reflex agents are, well, simple, they only work well in fully observable environments. The state of the environment has to be easily identifiable, otherwise the wrong rule and action will be applied. For example, it may be hard for the agent to tell if a car is braking or if it's just the taillights that are on.

For our vacuum example, suppose the vacuum didn't have a location sensor. Then it won't know which square it's on. If it starts at square `A` and chooses to move left, it will fail forever (and likewise if it starts at square `B` and chooses to move right).

Infinite loops like these often happen in partially observable environments and can be avoided by having the agent randomize its actions. Randomization can be rational in some multiagent environments, but it is usually not rational in single-agent environments.

Model-based reflex agents

To deal with partial observability, the agent can keep track of the part of the world it can't see now. In order to do this, the agent needs to maintain some sort of internal state that depends on the percept history. For a car changing lanes, the agent needs to keep track of where the other cars are if it can't see them all at once.

In order to update its internal state, the agent needs to know "how the world works". When the agent turns the steering wheel clockwise, the car turns to the right (effect of agent action). When it's raining, the car's camera can get wet (how the world evolves independent of agent's actions). This is a transition model of the world.

The agent also needs to know how to interpret the information it gets from its percepts to understand the current state of the world. When the car in front of the agent brakes, there will be several red regions in the forward-facing camera image. When the camera gets wet, there will be droplet-shaped objects in the image. This knowledge is called a sensor model.

A model-based agent uses the transition model and sensor model to keep track of the state of the world.

Goal-based agents

Sometimes, having information about the current state of the environment is not enough to decide what to do. For example, knowing that there's a fork in the road is not enough; the agent needs to know whether it should go left or right. The correct decision depends on the goal.

Goal-based decision making is different from following condition-action rules because it involves thinking about the future. A reflex agent brakes when it sees brake lights because that's specified in the rules. But a goal-based agent brakes when it sees brake lights because that's how it thinks it will avoid hitting other cars.

Utility-based agents

While achieving the goal is what we want the agent to do, there are many different actions that can be taken to get there. And those different actions can affect how "happy" or "unhappy" the agent will be. This level of "happiness" is referred to as utility.

Learning agents

The preferred way to build agents (model-based, goal-based, utility-based, etc.) is to build them as a learning agent and then teach them.

A learning agent can be divided into four conceptual components: the learning element, the performance element, the critic, and the problem generator. The learning element is responsible for making improvements. The performance element is responsible for selecting actions. The critic provides feedback on how the agent is doing and determines how the performance element should be modified to do better.

The problem generator is responsible for suggesting actions that will lead to new and informative experiences. This allows the agent to explore some suboptimal actions in the short run that may become much better actions in the long run.

---

For now, we'll assume that the environments are episodic, single agent, fully observable, deterministic, static, discrete, and known.

---

Problem-Solving Agents

If the agent doesn't know what the correct action to take should be, it should do some problem solving:

1. Goal formulation: figure out what the goal is to limit the number of actions that need to be considered
2. Problem formulation: describe the states and actions (come up with an abstract model of the world)
3. Search: try different sequences of actions to find one (the solution) that achieves the goal
4. Execution: just do it

Search problems and solutions

Formally, a search problem can be defined by specifying:

• the state space: the set of possible states that the environment can be in
• the initial state that the agent starts in
• a set of one or more goal states
• the actions available to the agent
• a transition model that describes what each action does
• an action cost function that describes the cost of performing an action
  • the cost should reflect the agent's performance measure, such as distance, time, or monetary cost

A sequence of actions forms a path, and a solution is a path from the initial state to a goal state. The cost of a path is the sum of the costs of each action on that path, so an optimal solution is the path with the lowest cost among all solutions. Everything can be represented as a graph where the vertices are the states and the edges are the actions.

Example Problems

Standardized problems

A grid world problem is an array of cells where agents can move from cell to cell and each cell can contain objects. Our little vacuum example is an example of a grid world problem.

• states: there are `8` different states depending on which objects are in which cells
  • for each of the two cells, it can contain the vacuum or not and it can contain dirt or not (`2*2*2=8`)
• initial state: any state can be chosen as the initial state
• actions: move left, move right, clean
• transition model: cleaning removes dirt from the agent's cell and move left/right are self-explanatory
• goal states: all the states where every cell is clean
  • both cells are clean and the vacuum ends up in the left cell
  • both cells are clean and the vacuum ends up in the right cell
• action cost: each action costs `1`

Real-world problems

A common type of real-world problem is the route-finding problem (finding an optimal path from point A to point B). For example, airline travel:

• states: location and current time
• initial state: our home airport
• actions: take any flight from the current location
• transition model: the flight's destination will become our new current location and the flight's arrival time will become our new current time
• goal state: our destination
  • the goal can also be "arrive at the destination on a nonstop flight"
• action cost: combination of monetary cost, waiting time, flight time, seat quality, time of day, type of airplane, frequent-flyer reward points, etc.

Search Algorithms

Search problems can be represented as a search tree, where a node represents a state and the edges represent the actions. For Knuth's conjecture:

When we're at a node, we can expand the node to consider the available states that are possible (generate nodes). The nodes that have not been expanded yet make up the frontier of the search tree.

Best-first search

So how do we decide which path to take? A good general approach is to perform best-first search. In this type of search, we define an evaluation function, which, in a sense, is a measure of how close we are to reaching the goal state. When we apply the evaluation function to each frontier node, the node with the minimum value of the evaluation function should be the next node to go to.

Search data structures

We can implement a node by storing:

• state: the state of the node
• parent: the node that generated this node
• action: the action that was applied to the parent to generate this node
• path-cost: the total cost of the path from the initial state to this node

We can store the frontier using a queue. A queue is good because it provides us with the operations to check if a frontier is empty, take the top node from the frontier, look at the top node of the frontier, and add a node to the frontier.

Redundant paths

As we traversing the tree, it's possible to get stuck in a cycle (loopy path), i.e., go around in circles through repeated states. Here's an example of a cycle:

A cycle is a type of redundant path, which is a path that has more steps than necessary. Here's an example of a redundant path:

There are three ways to handle the possibility of running into redundant paths. The preferred way is to keep track of all the states we've been to. That way, if we see it again, then we know not to go that way. (The best-first search pseudocode does this.)

The bad part about doing this is that there might not be enough memory to keep track of all this info. So we can check for cycles instead of redundant paths. We can do this by following the chain of parent pointers ("going up the tree") to see if the state at the end has appeared earlier in the path.

Or we can choose to not even worry about choosing redundant paths if it's rare or impossible to have them. From this point on, we'll use graph search for search algorithms that check redundant paths and tree-like search for ones that don't.

Uninformed Search Strategies

The uninformed means that as the agent is performing the search algorithm, it doesn't know how close the current state is to the goal.

Breadth-first search

In breadth-first search, all the nodes on the same level are expanded first before going further down any paths. This is generally a good strategy to consider when all the actions have the same cost.

Dijkstra's algorithm or uniform-cost search

If actions have different costs, then uniform-cost search is a better consideration. The main idea behind this is that the least-cost paths are explored first. (I go into more step-by-step detail about how Dijkstra's algorithm works in my Computer Networking resource.)

Uniform-cost search will always find the optimal solution, but the main problem with it is that it's inefficient. It will expand a lot of nodes.

Depth-first search

In depth-first search, the deepest node in the frontier is expanded first. Basically, one path at a time is picked and followed until it ends. So if a goal state is found, then that path is chosen as the solution. This also means that the path chosen may not be the cheapest path available. (What if we had gone down that path instead?)

Depth-limited and iterative deepening search

Another problem with depth-first search is that it can keep going down one path infinitely. To prevent this, we can decide to stop going down a path once we reach a certain point. This is depth-limited search.

But how far is too far? If we stop too early, we may not find a solution and if we choose to stop very late, it will take a long time. Iterative deepening search keeps trying different stopping points until a solution is found or until no solution is found (if this is the case, then we have gone deep enough to the point where all paths can be fully explored).

Iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and the depth of the solution is not known.

Bidirectional search

So far, all the algorithms started at the initial state and moved towards a goal state. But what we can also do is start from the initial state and the goal state(s) and hope that we meet somewhere in the middle. This is bidirectional search.

We need to keep track of two frontiers and two tables of reached states. There is a solution when the two frontiers meet.

Informed (Heuristic) Search Strategies

Informed means that information is provided about how close the current state is to a goal state.

For the next few algorithms, we'll be using this maze, where the goal is to find the shortest path from `S` to `G`. The number in each square is the number of squares it is away from the goal (ignoring walls). That is the heuristic we'll be using.

Greedy best-first search

If we know how close each node is to a goal, then it seems to makes sense to choose the node that seems closest to the goal.

Since we're being greedy, we'll move to the square that looks like it's `11` squares away from the goal instead of the square that looks like it's `13` squares away from the goal.

Now obviously, this is not the optimal path. But being greedy is not always a good thing.

A* search

The reason greedy best-first search failed is because it didn't take into consideration the cost of going to each node -- it only looked at how far away each node was to the destination. Intuitively, if it takes a long time to get to a destination that is close to your goal, is it really worth going to that destination? A* search looks at both the cost to get to each node and the estimated cost from each node to the destination.

Now, the numbers in each square represent the cost of going to that square plus the estimated distance to the goal, i.e., the number of squares it is away from the goal (ignoring walls).

Just like in greedy search, we'll be going up again. But don't worry, things will be different this time.

At this point, we see that it's no longer worth continuing on this path because there is a cheaper option (`19`) at the fork. So we'll start going that way instead.

Even though we wasted some time going down the longer path, we still found the optimal solution.

Satisficing search: Inadmissible heuristics and weighted A*

Even though A* is complete, cost-optimal, and optimally efficient, the one big problem with A* is that it expands a lot of nodes, which takes time and uses up space. We can expand fewer nodes by using an inadmissible heuristic, which may overestimate the estimated cost to the goal. Intuitively, if the estimated costs of some of the nodes are higher, then there will be fewer nodes that look favorable to expand. Of course, if we overestimate, then there's a chance we might miss an optimal path, but this is the price to pay for expanding fewer nodes. We might end up with suboptimal, but "good enough" solutions (satisficing solutions).

Inadmissible heuristics are potentially more accurate. Consider a heuristic that uses a straight-line distance to estimate the distance of a road between two cities. The path between two cities is almost never a straight line, so the length of the actual path will be greater than the length of the straight line. Meaning that overestimating the straight-line distance by a little bit will make it closer to the length of the actual path.

We don't actually need an inadmissible heuristic to take advantage of the faster speed and lower memory usage. We can simulate an inadmissible heuristic by adding some weight to the heuristic.

This is weighted A* search.

Memory-bounded search

Beam search keeps only `k` nodes with the best `f`-scores in the frontier. This means that we may be excluding cost-optimal paths (and even solutions), but it's the price to pay to limit the number of expanded nodes. Though for many problems, it can find near-optimal solutions.

Iterative-deepening A* search (IDA*) is a commonly used algorithm for problems with limited memory. Where iterative deepening search uses depth as the cutoff, iterative-deepening A* search uses `f`-cost as the cutoff. Specifically, the cutoff value is the smallest `f`-cost of any node that exceeded the cutoff on the previous iteration.

Once the cutoff is reached, IDA* starts over from the beginning. Recursive best-first search (RBFS) also uses `f`-values to determine how far down a path it should go, but once the cutoff is reached, it steps back and takes another path (the one with the second-lowest `f`-value) instead of starting over.

Bidirectional heuristic search

Bidirectional search is sometimes more efficient than unidirectional search, sometimes not. If we're using a very good heuristic, then A* search will perform well and adding bidirectional search won't add any more value. If we're using an average heuristic, bidirectional search tends to expand fewer nodes. If we're using a bad heuristic, then both directional and unidirectional search will be equally bad.

Heuristic Functions

Here, we'll look at how the accuracy of a heuristic affects search performance and how we can come up with heuristics in the first place. We'll use the 8-puzzle as our main example. The 8-puzzle is a `3xx3` sliding-tile puzzle with `8` tiles and `1` blank space. We move tiles horizontally and vertically into the blank space until the goal state is reached (each move has a cost of `1`).

Two commonly-used heuristics are

• `h_1=` the number of misplaced tiles (blank space not included)
  • for our example, `h_1=8` because all `8` tiles are misplaced
  • this is admissible because the number of moves needed to reach a goal state will always be `ge` the number of misplaced tiles
    • if all `8` misplaced tiles need just `1` move to get to the correct spot, then the estimated cost is still not overestimated
• `h_2=` the sum of the distances of the tiles from their goal positions
  • for our example, `h_2=3+1+2+2+2+3+3+2=18`
    • `1` is `3` squares away from its destination, `2` is `1` square away from its destination, `3` is `2` squares away from its destination, ...
  • this is sometimes called the city-block distance or Manhattan distance
  • this is admissible because the calculation of the distance doesn't take obstacles into account
    • `8` is `2` squares away from its destination, but it may actually need `ge 2` moves

The effect of heuristic accuracy on performance

One way to assess the quality of a heuristic is to look at the effective branching factor `b^(**)`. It can loosely be thought of as the average number of nodes that are generated at each depth. A good heuristic would have `b^(**)` close to `1`, which means that not a lot of nodes are being generated the farther we go down a path (we're fairly successful in finding good paths).

It turns out that `h_2` (the Manhattan distance) is always better than `h_1` (the number of misplaced tiles). This means that `h_2` dominates `h_1`. Because of this, A* search using `h_2` will never expand more nodes than A* using `h_1` (except for when there are ties).

Generating heuristics from relaxed problems

So how do we come up with heuristics like `h_1` and `h_2` in the first place? (Perhaps more importantly, is it possible for a computer to come up with such a heuristic?)

Let's make the 8-puzzle simpler so that tiles can be moved anywhere, even if there's another tile occupying the spot. Notice now that `h_1` would give the exact length of the shortest solution.

Let's consider another simplified version where the tiles can still only move `1` square but, now, in any direction, even if the square is occupied. Notice that `h_2` would give the exact length of the shortest solution.

These simplified versions, where there are fewer restrictions on the actions, are relaxed problems. The state-space graph of a relaxed problem is a supergraph of the original state space because the removal of restrictions allows for more possible states, resulting in more edges being added. This means that an optimal solution in the original problem is also an optimal solution in the relaxed problem. But the relaxed problem may have better solutions (this happens when the added edges provide shortcuts).

That last part is how we can come up with heuristics. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. (Also, if the heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality, making it consistent.)

So how can we come up with relaxed problems systematically?

Let's describe the 8-puzzle actions as follows: a tile can move from square `X` to square `Y` if `X` is adjacent to `Y` and `Y` is blank. From this, we can generate three relaxed problems simply by removing one or both of the conditions:

• A tile can move from square `X` to square `Y` if `X` is adjacent to `Y`
• A tile can move from square `X` to square `Y` if `Y` is blank
• A tile can move from square `X` to square `Y`

From the first one, we can derive `h_2` (the Manhattan distance) and from the third one, we can derive `h_1` (the number of misplaced tiles).

Generating heuristics from subproblems: Pattern databases

Let's consider a subproblem of the 8-puzzle, where the goal is to get only tiles `1,2,3,4,` and the blank space into the correct spots.

Since there are fewer tiles that have to be in a certain spot, the cost of the optimal solution of this subproblem is a lower bound on the cost of the complete problem, meaning that this could make a good admissible heuristic.

For every possible subproblem, we can store the exact costs of their solutions in a pattern database. So when we're trying to solve the complete problem, we could look in our database for the subproblem that matches our current state and use the exact cost of the subproblem as the heuristic for the complete problem.

We could have multiple databases for each subproblem type. For example, one database could be all the subproblem instances with tiles `1,2,3,4`. Another database could be all the subproblem instances with tiles `5,6,7,8`. Another database could be all the subproblem instances with tiles `2,4,6,8`. And so on. Then the heuristics from these databases can be combined by taking the maximum value. Doing this turns out to be more accurate than the Manhattan distance.

Generating heuristics with landmarks

This is kinda similar to using pattern databases, but kinda makes more sense when viewed in the context of route-finding problems.

We can pick a few landmark points and precompute the optimal costs to these landmarks. More formally, for each landmark `L` and for each other vertex `v` in the graph, we compute and store `C^(**)(v,L)`. This may sound time-consuming, but it only needs to be done once and it will be infinitely useful.

So if we're trying to estimate the cost to the goal, we can look at the cost to get there from a landmark.

A good way to decide landmark points are by looking at user requests for frequently requested landmarks.

Learning heuristics from experience

Sometimes, we can just develop an intuition for something if we do it many times. From the perspective of computers, they can pick up on patterns in past data and come up with a heuristic that seems to align with those patterns. A lot of this seems to depend on luck, so the heuristics are not expected to be admissible (much less consistent).

---

Earlier, we assumed that the environments are episodic, single agent, fully observable, deterministic, static, discrete, and known. Now we'll start relaxing these constraints to get closer to the real world.

---

Local Search and Optimization Problems

There are some search problems where we only care about what a goal state looks like (and we don't care what the path looks like). For example, the 8-queens problem is to find a valid placement of 8 queens such that no queens are attacking each other. Once we know what a solution looks like, it's trivial to reconstruct the steps to get there.

Local search algorithms work without keeping track of the paths or the states that have been reached. This means that they don't explore the whole search space systematically, i.e., they are not complete and may not find a solution. However, they use very little memory and can find reasonable solutions in problems with large or infinite state spaces.

Local search also works for optimization problems, where the goal is to find the best state according to some objective function. The objective function represents what we're trying to maximize/minimize.

Hill-climbing search

Let's take a look at a sample state-space landscape.

One goal might be to find the highest peak, which is the global maximum. This process is called hill climbing.

The hill climbing search algorithm is pretty simple. It keeps moving forward until the next state it finds has a smaller value than the value of the current state.

There are some situations where the hill climbing algorithm can get stuck before finding a solution. One situation is when a local maximum is reached. In this situation, every possible move results in a worser state.

Another situation is when a plateau is reached. A plateau can be a flat local maximum or a shoulder, where there is an uphill exit. In this situation, every possible move doesn't result in a better state (except if the plateau is a shoulder and we're right at the edge of the uphill exit).

Let's look at the problem of positioning hospitals so that they are as close as possible to every house.

The cost is the sum of the distances from each house to the nearest hospital.

We can see that this is the best way to place the hospitals, but in order to achieve this position, the algorithm has to make the move below first.

Since this move doesn't result in a better state, the hill climbing algorithm won't consider that move. And as a result, the best configuration will never be reached. This is an example of a plateau.

One way to get unstuck is to allow sideways moves, i.e., to allow the algorithm to keep moving as long as the next state isn't worse. The idea is to hope that the plateau is a shoulder. This won't work if the plateau is a local maximum though, in which case we really are stuck.

Another way (kinda) is to just start over, but from a different starting point. This is random-restart hill climbing.

Simulated annealing

Sometimes, it's necessary to make worse moves that put us in a temporarily worse state so that we can get to a better position.

In the simulated-annealing algorithm, we pick moves randomly instead of picking the best move. If the move puts us in a better situation, then we'll accept it. But if the move puts us in a worse position, then we'll consider it, depending on how bad of a move it is (measured by `DeltaE`). And as time goes on, we'll be less accepting of bad moves.

Local beam search

Local beam search starts with `k` randomly generated states, generates all their successors (if one of them is a goal, then we're done), selects the best `k` successors, and repeats.

Evolutionary algorithms

Evolutionary algorithms are based on the ideas of natural selection in biology. There is a population of individuals (states), and the fittest (highest valued) individuals produce offspring (successor states). And just like in real life, the successor states contain properties of the parent states that produced them.

The process of combining the parent states to produce successor states is called recombination. One common way of implementing this is to split each parent at a crossover point and use the four resulting pieces to form two children.

Below is an example of how an evolutionary algorithm can be used for the 8-queens problem. We can encode each queen's positions as a number from `1-8`.

Local Search in Continuous Spaces

Most real-world problems take place in a continuous environment, not in a discrete one like the examples we've seen so far. A continuous environment can have a continuous action space (e.g., a robotic arm moving anywhere between `0` and `180` degrees), a continuous state space (e.g., the current position of a robot in a room), or both.

One way to deal with a continuous state space is to discretize it.

For example, suppose we want to place three new airports in an area such that each city is as close as possible to its nearest airport. The state space is defined by the coordinates of the three airports: `(x_1, y_1),(x_2, y_2),(x_3, y_3)`. To discretize this, we could predefine fixed points on a grid and only allow the airports to be at those fixed points.

One way to deal with a continuous action space is to choose successor states randomly by moving in a random direction by a small amount. As we move, we look at how the value of the objective function changes to see if we're going in the right direction. This is empirical gradient search.

Search with Nondeterministic Actions

Now, we'll look at nondeterministic environments. When the environment is nondeterministic, the agent doesn't know for sure what state it will end up in after performing an action. So the agent will be thinking something like, "If I do action `a` I'll end up in state `s_2`, `s_4`, or `s_5`. The states that the agent believes are possible are called belief states.

Instead of a sequence of states, the solution to a problem is a conditional plan that specifies what to do depending on the situation.

The erratic vacuum world

We're going back to our vacuum world! But this time, our vacuum is a little unpredictable. When it cleans a dirty square, it can sometimes clean an adjacent square as well. If it cleans a clean square, it can sometimes deposit dirt on it.

AND-OR search trees

Notice that there's no single sequence of actions that can solve the problem. But this conditional plan does:

As the name suggests, an AND-OR search tree has OR nodes and AND nodes. OR nodes (represented as rectangles in the example above) are thought of as, "at this node, I can do this or that". AND nodes (represented as circles) are thought of as, "at this node, this and this can happen".

Try, try again

Forget our erratic vacuum for a moment. Let's go back to our normal vacuum, but this time, the floor is slippery. So sometimes, when the vacuum tries to move, it stays in place instead.

Here, if we're in state `5` and the vacuum moves right, it can either move right or stay in place. If it stays in place, we still want it to move right. So the solution here is to keep moving right until it works.

This is a cyclic plan that happens to also be a solution, i.e., a cyclic solution.

Search in Partially Observable Environments

Now, we'll look at what happens when the environment is partially observable. When the environment is partially observable, the agent doesn't know for sure what state it's in. So the agent will be thinking something like, "I'm either in state `s_1` or `s_3`".

Searching with no observation

If the agent has no sensors at all, then the problem that the agent is trying to solve is called a sensorless problem. It might seem impossible for an agent to be able to do anything without sensors, but, in fact, there are sensorless solutions that are common and useful because they don't rely on sensors working properly.

So let's go back to when the vacuum was working normally. Except, the vacuum now has no sensors, so it doesn't know its own location or which squares have dirt (including the square it's currently on). But let's say the vacuum knows what all the possible states look like.

When it starts out, the vacuum's initial belief state is `{1, 2, 3, 4, 5, 6, 7, 8}`. No matter what state it's in, if the vacuum moves right, then it will be in one of the states `{2, 4, 6, 8}`. After cleaning, it will be in `{4,8}`. Then after moving left and cleaning, it will be in state `7`. So no matter what state the vacuum starts in, we can coerce the world into state `7` with [Right, Clean, Left, Clean].

The solution to a sensorless problem is a sequence of actions, not a conditional plan. This is because the agent can't sense anything, and thus, can't tell when it needs to go with another plan.

So the solutions can be found by using the informed and uninformed search algorithms from before. We just have to search in the space of belief states instead of physical states.

If we transform a physical problem `P` (with `text(Actions)_P`, `text(Result)_P`) into a belief-state problem, we have:

• states: every possible subset of physical states
  • if `P` has `N` states, then the belief-state problem has `2^N` belief states
    • note that this is not saying that a belief state has `2^N` physical states
• initial state: usually, the belief state consisting of all states in `P`
• goal test: all states in the current belief state must be a goal state
• action cost: to simplify things, we'll assume the cost of an action is the same in all states

Defining the actions is a little more involved. A belief state can have multiple physical states, so there can be multiple actions available from each state. Inherently, there can be some actions that are possible in some of the states but not others. If illegal actions don't have an effect on the environment, then we can combine all the actions from each state and say that those are the available actions for the current belief state. Otherwise, we can find the actions that are common in all the states and say that those are the available actions.

For example, in our vacuum world, let's say the belief state is `{s_1, s_2}`. All the possible actions from both states are to move left, move right, and clean. However, it's not really useful for a vacuum in `s_1` to move left. We've been assuming that if the vacuum can't move in a certain direction, it just stays still. So in this case, it's okay to combine all the actions and say that the available actions for `{s_1,s_2}` are to move left, move right, and clean.

On the other hand, if the vacuum can fall off the edge, then we don't want it to move left if it's in `s_1`. Likewise, we don't want it to move right if it's in `s_2`. The only action in common from all states is to clean, so the available actions for the belief state in this case would be to just clean.

Defining the transition model is also a little more involved depending on whether the actions are deterministic or not. For deterministic actions, there is one result state for each of the states in the belief state. For nondeterministic actions, it's the combination of all the possible result states for each of the states.

By transforming a physical problem into a belief-state problem with these definitions, we can use the informed and uninformed search algorithms to find a solution. The operative word being "can". As mentioned earlier, there are a total of `2^N` possible belief states to search through. Furthermore, a belief state can have up to `N` states, so it can be hard to store multiple belief states in memory.

An alternative is to use incremental belief-state search algorithms. For example, if the initial belief state is `{1,2,3,4,5,6,7,8}`, we can start by finding a solution for state `1` and see if it works for every other state. If it doesn't, then we go back to state `1`, find another solution, and repeat until the solution works for all `8` states.

Searching in partially observable environments

Now we'll upgrade our vacuum to have local sensors that can tell it which square it's on and whether it's clean or dirty. Suppose the vacuum gets the information [L, Dirty] from its sensors. From this, the vacuum can either be in state `1` or state `3`. So it's belief state will be `{1,3}`.

The transition model between belief states can be seen as a three-stage process:

• prediction stage: see what states are possible from performing on action on the current belief state
• possible percepts stage: see what percepts are possible from each of the states
• update stage: compute the belief states that are possible based on the possible percepts

Solving partially observable problems

Because the current belief state can yield multiple belief states as the next possible states, we can treat the multiple belief states as if they were the result of a nondeterministic action and, therefore, use the AND-OR search algorithm. As a result, the solution is a conditional plan. For example, [Clean, Right, if state == 6 then Clean else []] is a solution to the search tree below.

Online Search Agents and Unknown Environments

In this context, online isn't referring to the Internet. An online search agent makes an action, observes the environment, and computes the next action. As opposed to an offline search agent that computes a complete solution first before taking any action. Mostly everything we've seen so far has been offline search algorithms.

Online search is good for (semi-)dynamic environments where the agent can't sit around doing nothing for too long. It's also good for nondeterministic environments because it allows the agent to focus on the percepts that it actually receives rather than the percepts that it can receive.

On the flip side, more planning reduces the chances of things going wrong.

---

We'll briefly return to deterministic and fully observable environments here.

---

Online search problems

The agent only knows the actions that are available in the current state, the cost of going to the next state (once the next available states have been computed), and whether or not the current state is a goal state. The agent cannot know the result of going to another state until it's in that state. The agent might have access to a heuristic function.

An online algorithm can only generate successors for the state that it's currently in. On the other hand, offline algorithms, such as A* search, can expand a node in one part of the space and then immediately expand a node in a distant part of the space.

Online explorers are vulnerable to dead ends, which are states from which no goal state is reachable. Dead ends are a result of irreversible actions, i.e., actions that prevent returning to the previous state.

An environment with no dead ends is safely explorable, which means that a goal state is reachable from every reachable state. Any environment with only reversible actions are safely explorable.

Online local search

Since hill-climbing search just keeps the current state in memory, it's actually already an online search algorithm. It's not a very good one though because it can result in agents getting stuck at a local maximum. And random-restart hill climbing is not an option to get unstuck because the agent can't teleport to a new start state.

A random walk can be used to explore an environment. The agent selects an action at random and performs it.

Instead of telling the agent to do random things, we can have the agent learn about its environment as it explores it. One way to do this is to store a "current best estimate" of the cost to reach the goal from each state that has been visited.

Consider this sample state space. `(a),(b),(c),(d),(e)` are five iterations of an algorithm called learning real-time A* (LRTA*) search that implements this current best estimate idea. If we look at `(a)`, we see that the agent is currently stuck in a local minimum.

At `(a)`, there are two actions: move left or move right. The estimated cost to reach a goal if we move left is `1+9=10` and the estimated cost to reach a goal if we move right is `1+2=3`. So we move right. Importantly, we also update the previous state's estimated cost with the lowest one (`3` vs `10`).

At `(b)`, the estimated cost to the goal if we move left is `1+3=4` and the estimated cost to the goal if we move right is `1+4=5`. We move left and update the previous state's estimated cost (`4` vs `5`).

We can eventually see that we get unstuck (and "flatten out" the local minimum in the process).

Constraint Satisfaction Problems

Oftentimes, many problems have restrictions/conditions that need to be satisfied. For example, the rules of sudoku require that all numbers in any row, column, and square have to be different. Another general example might be that a solution needs to run in under 1 minute.

More formally, a problem has a set of variables that represent different parts of a problem. A value is assigned to a variable. If all the variables are assigned a value, then that is a complete assignment. A constraint satisfaction problem (CSP) is solved when each variable has a value that satisifies all the constraints on the variable, i.e., the solution to a CSP is a consistent and complete assignment.

If some of the variables are unassigned, then that is a partial assignment. A partial solution is a partial assignment that satisifies all the constraints.

Example problem: Map coloring

As trivial as this sounds, suppose we had a map of a region and we wanted to color each region red, green, or blue. But we have a constraint that no two neighboring regions can have the same color, e.g., a red region can't be next to another red region.

We formally define our CSP as:

One solution is `{H=text(red),J=text(green),K=text(blue),L=text(red),M=text(green),N=text(red),P=text(blue)}`.

While it may seem like adding constraints to a problem might make it harder to solve, it actually makes things a lot easier for our algorithms. By adding constraints, the number of possible states are reduced. For example, once we've decided that we want `K` to be blue, that eliminates all the states where `H`, `J`, `L`, `M`, and `N` are blue.

Constraint Propagation: Inference in CSPs

This idea of reducing the number of possible states is constraint propagation, which means using the constraints to reduce the number of valid values for a variable, which in turn can reduce the number of valid values for other variables.

Before we can begin searching for a solution, we need the graph to be consistent with the constraints. This is referred to as local consistency.

Node consistency

A unary constraint is a constraint that only affects one variable at a time. For example, `P ne text(green)`.

A variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints. A graph is node-consistent if every variable is node-consistent.

Arc consistency

A binary constraint is a constraint that affects two variables at a time. `K ne H` is a binary constraint.

A variable is arc-consistent if all the values in the variable's domain satisfy the variable's binary constraints.

Path consistency

Path consistency makes sure three variables are consistent with each other. The name comes from the idea that the path between two variables is consistent with a third variable in the middle of the path.

Global constraints

A global constraint is a constraint that affects any number of variables at a time. It doesn't need to, but a global constraint can affect all of the variables at a time. In fact, one of the most common constraints is that each variable must have a different value (this constraint is referred to as an "Alldiff" constraint).

A resource constraint is a constraint resulting from the limited number of resources available (this is sometimes referred to as an "Atmost" constraint). For example, suppose there are `4` tasks and only `10` people available to do them. If each task needs at least `3` people, then there is no solution.

For problems that deal with larger numbers of resources, limiting the range of values a variable can have is more appropriate. This is bounds propagation.

For example, suppose there are two airplanes where one can carry `165` people and the other can carry `385`. So the initial domains are

Let's say our constraint is that the two flights together must carry `420` people. Using bounds propagation, we now have the domains

Backtracking Search for CSPs

After applying the constraints to a CSP, we then have to search for a solution (if applying the constraints didn't already give us a solution for free).

The basic idea behind backtracking search is that it repeatedly chooses an unassigned variable and tries different values in the domain of that variable. If a solution isn't found, the algorithm backtracks and tries again with different values. It's kinda like "Let's try this. Then let's try this. Then let's try this. Oops, that didn't work! Let's try this instead."

Variable and value ordering

Going back to our map, let's say we arbitrarily start at `H` and arbitrarily choose red for it. Then we arbitrarily choose green for `J`. From these two decisions, we can see that `K` is now forced to be blue. This in turn, forces `L`, `M`, and `N` to be red, green, and red respectively.

If we had instead decided to pick a color for `L` before looking at `K`, we would not have had it this easy. In fact, if we had decided `L` to be blue, there would have been no valid value for `K` and we would have had to start over.

This highlights that when deciding which unassigned variable to look at next, we should look at the variable with the fewest valid values. This strategy is the minimum-remaining-values (MRV) heuristic. It is also called the "fail-first" heuristic because it picks a variable that is most likely to cause a failure, which allows the tree to be pruned. In our example, picking blue for `L` caused a failure, so all the possible map configurations where `L` is blue (and `H` is red and `J` is green) can be pruned away.

But notice how we were still making arbitrary decisions for the first two moves. The MRV heuristic isn't really helpful in the beginning because all the variables have the same number of valid values. So another heuristic that helps us pick a variable at the start is the degree heuristic. It selects the variable that is involved in the most constraints with other unassigned variables. In our map, `K` has a constraint with `5` other variables (i.e. it has degree `5`), so it should be picked first. It just so happens that starting with `K` guarantees that a solution will be found right away.

So we have heuristics for deciding which variable to look at first, but there is one more choice to think about and that is which value to assign first. Let's say we picked `H` to be red and `J` to be green, and we decided to look at `L` (despite knowing that looking at `K` first was better). We know that picking blue for `L` is not a good idea since it leaves no choices available for `K`, so we choose red instead.

Instead of picking a value that will cause a failure, we want to pick a value that will work. More specifically, we want to pick a value that will rule out the fewest choices for the neighboring variables, giving them as much flexibility as possible. This is the least-constraining-value heuristic.

Interleaving search and inference

As we saw before, inference (using AC-3) can reduce the size of a variable's domain before the search starts. But we can do this during the search as well by doing forward checking. Whenever a value is assigned to a variable, we look at the other variables involved in a constraint with this variable and remove inconsistent values from their domains.

Let's say we start with `H` red. Once we have this, we know that `K` and `J` can't be red, so we remove red from their domains.

Then we choose `L` green. Once we have this, we know that `J`, `K`, and `M` can't be green, so we remove green from their domains.

Then we choose `N` blue. Once we have this, we know that `K` and `M` can't be blue, so we remove blue from their domains.

At this point, we can see that there are no valid values left for `K`. So we have to backtrack and try a different value for `N`.

Intelligent backtracking: Looking backward

Whenever an inconsistency is found, the backtracking algorithm goes up one level to the previous variable and tries a different value. This is called chronological backtracking because the most recent decision point is revisited.

This is simple, but it can be a little inefficient.

Let's say we started with `L` red, `M` green, `N` blue, and `P` red in that order. Now we see that there is no valid color for `K`, so we backtrack and consider a different value for `P`. Unfortunately, we can see that choosing a different value for `P` won't change anything since `P` wasn't causing the problem; we would have to backtrack one more level to `N`. But the algorithm will be inefficient and try different values of `P` until none of them work and then backtrack to `N`.

Since the set `{L=text(red),M=text(green),N=text(blue)}` was responsible for `K` not having any valid values, we call this set the conflict set for `K`. If we keep track of this set, we can backjump to the most recent assignment in the conflict set, which would be `N` in this case.

Constraint learning

If we reach an inconsistency, we can remember what the conflict set was that led to the inconsistency so we don't run into it again. This set is aptly called a no-good.

Local Search for CSPs

The local search algorithms we saw before can be used to solve CSPS. The idea is to assign a value to every variable at the beginning, even if they're inconsistent. Then we randomly choose a variable that is violating one or more constraints and change its value to something that violates fewer constraints. And we keep doing this until we find a solution. (Or keep going forever if there is no solution. 😏)

The min-conflicts heuristic chooses the value that results in the minimum number of violated constraints with other variables.

---

Now, we'll look at multi-agent environments. In particular, competitive environments where two or more agents have conflicting goals. Problems in these environments are called adversarial search problems.

---

Game Theory

Apparently, chess, Go, and poker are popular games to study in the AI community.

Two-player zero-sum games

Game theorists call these types of games deterministic, two-player, turn-taking, perfect information, zero-sum games. "Perfect information" means "fully observable" and "zero-sum" means that what is good for one player is just as bad for the other. A move is an "action" and a position is a "state".

A game can be formally defined by specifying:

• the initial state, which describes how the game is set up at the start
  • `S_0`
• the player whose turn it is to move in state `s`
  • `text(TO-MOVE)(s)`
• the set of legal moves in state `s`
  • `text(ACTIONS)(s)`
• the transition model, which defines the state resulting from taking action `a` in state `s`
  • `text(RESULT)(s,a)`
• a terminal test, which is true when the game is over
  • states where the game has ended are called terminal states
  • `text(IS-TERMINAL)(s)`
• a utility function, which assigns numerical values to the outcome of the game
  • in chess, a win is `1`, a loss is `0`, and a draw is `1/2`
  • `text(UTILITY)(s,p)`

Instead of using a search tree like the one we saw earlier, we'll be using a game tree, which takes into account that there are multiple players. And speaking of players, we'll be calling our two players MAX and MIN.

Here's an example of a (partial) game tree for tic-tac-toe:

Optimal Decisions in Games

Since each player is responding to each other's moves, the strategy for both players is a conditional plan (if that player does this, I'll do this).

Consider the simple game above where MAX is trying to reach one of the bottom-row nodes with the highest value and MIN is trying to have MAX end up at the node with the lowest value (depending on MAX's first move). MAX moves first and gets to pick a path `a_1`, `a_2`, or `a_3`. Then it is MIN's turn to decide which bottom-row node MAX ends up at.

For example, MAX might want to reach the node with `14`, so MAX will choose `a_3`. At this point, MIN has three options `d_1`, `d_2`, `d_3`. Since MIN wants MAX to have the lowest score possible, MIN will choose `d_3`, so MAX will end up with a score of `2`.

That strategy didn't really go so well for MAX, so let's look at another one. This time, MAX wants `12`, so MAX will choose `a_1`. MIN will then choose `b_1` so that MAX ends up with `3`, the lowest out of the three choices.

We can see that `3` is the highest score MAX can hope to get if MIN plays optimally. And if you took the time to verify that, then you'll notice that you played the game backwards (starting from the bottom and moving up) to check.

This is essentially the idea behind the minimax search algorithm.

Each node is assigned a minimax value that represents how "good" that position/move is for a player, assuming the other player plays optimally. In this game, MAX wants to choose the node with the maximum minimax value and MIN wants to choose the node with the minimum minimax value.

The minimax value of the terminal nodes are just the values defined by the game's `text(UTILITY)` function (for terminal nodes, their utility is the score we get when the game ends). Then the minimax values are propagated up the game tree using the same reasoning we used to analyze the game above.

Optimal decisions in multiplayer games

To create game trees for games with more than two players, we assign a group of values (one value for each player) to each node. Consider a game (similar to the one before) where all players are trying to get to the node that will give them (individually) the highest score possible.

Let's say we have three players `A`, `B`, and `C`. So each node will have a group of minimax values `(a,b,c)` where `a` is the minimax value for `A`, `b` is the minimax value for `B`, and `c` is the minimax value for `C`. `A` is trying to get to the node with the highest `a` value, `B` is trying to get to the node with the highest `b` value, and `C` is trying to get to the node with the highest `c` value.

Suppose `A` wants to get to the node `(7,4,1)`, so `A` moves left. At this point, `B` would also want to get to the node `(7,4,1)`, so `B` moves right. From the remaining options, `C` wants to get to the node `(6,1,2)`, so `C` moves left. So the final score for all three players is `A:6`, `B:1`, `C:2`.

This is the game tree assuming everyone plays optimally:

Again, the terminal nodes have their minimax values defined by the game's `text(UTILITY)` function, and the values are passed up the tree depending on which player's turn it is.

Alpha-Beta Pruning

We can actually sometimes deduce the minimax value of a node without having to fully expand it. This means that we can optimize the algorithm by not examining all the nodes. If we can deduce that it is not optimal for a player to go down a certain path, we can skip it, which resultingly prunes the tree.

Suppose we're running the algorithm and we've already discovered the minimax value of `B`. And now when we're calculating the minimax value of `C`, we find that its first child has a value of `2`. We don't need to look at the minimax values of the other two children because the minimax value of `C` will be at most `2`. If the other two children have minimax values higher than `2`, then MIN will move to the node with minimax value `2`. If the other two children have minimax values lower than `2`, then MIN will move to those nodes, making MAX's score even lower. No matter what those two children of `C` are, it's not in MAX's best interest to move to `C` because moving to `B` is a better option.

We do however, need to explore all of `D`'s children though. The minimax values of the first two children are `14` and `5`, both of which are higher than `3`, so MAX would still want to go down this path. It's not until we look at the last child that we can determine that this path is not optimal for MAX.

Move ordering

Notice that if the last child of `D` (the one with minimax value `2`) had been generated first, then we could've pruned `D`'s other children. This means that, if possible, we should try to examine successors that allow us to prune the tree.

A move that prunes a tree when examined is called a killer move. Examining those moves first is called the killer move heuristic. It's not examining the node and then finding out that it prunes the tree; it's knowing ahead of time that examining that node will prune the tree. This information comes from past experience. Maybe we have a collection of winning moves and we find a move at our current state in that collection.

Heuristic Alpha-Beta Tree Search

Even with alpha-beta pruning and good move ordering, there are still too many states to explore for games like chess. One way to deal with this is to use a Type A strategy, which considers all possible moves until a certain depth. Then it uses a heuristic function to estimate the utility of the rest of the states.

There's a cutoff test to determine when to stop searching and start estimating. This effectively treats nonterminal nodes as if they were terminal nodes.

Evaluation functions

A heuristic evaluation function gives us an estimate of a state's expected utility.

Evaluation functions work by calculating various features of the state. The information from those features is used to assign a numerical value to that state. A good evaluation function should not take too long to compute (obviously). More importantly, the evaluation function should be strongly correlated with the actual chances of winning.

For example, one feature we could use is the number of pieces that each player (white vs black) has remaining. If there's a move that results in white having more pieces, then that state should have a high evaluation function value for white.

Of course, simply having more pieces doesn't necessarily mean it's better. It depends on what types of pieces they are. For example, a queen is much more valuable than having eight pawns and no queen. We take things like this into account by adding weight to certain features that are more important than other features.

Cutting off search

Using an evaluation function that just counts the number of pieces is very simple and can lead to errors. For example, suppose the algorithm stops at the cutoff and finds a state where black has more pieces than white, so black moves to that state. But then white moves to capture black's queen! If the algorithm had been able to look ahead, then it would've known that it was not a favorable position after all.

Positions where a pending move can wildly swing the evaluation are called nonquiescent positions. The evaluation function should be used only for quiescent positions, and search should continue until quiescent positions are reached.

Forward pruning

Alpha-beta pruning prunes parts of the tree that were for sure bad moves. Forward pruning prunes parts of the tree that look like they have bad moves.

One way to implement forward pruning is to use beam search, which considers a "beam" of `n` moves. Of course, there's a chance that we miss the the best move by doing this.

Monte Carlo Tree Search

Monte Carlo tree search (MCTS) goes through many simulations to determine which moves are good. Basically, the algorithm plays out many games of "what if I do this and what if they do this?" and sees which choices led to wins and losses. So instead of using a heuristic evaluation function to assign values to states, it uses an average utility score (defined by the number of wins/losses and games) to assign values to states.

While it's not possible to know exactly how an opponent is going to respond to a move in a simulation, there are almost always certain moves that are better than others, and we can create playout policies that tell the algorithm what these moves are so they can prioritize those moves in the simulations.

Let's suppose we have this tree for a game played by pink and brown. Each fraction in the node is the number of simulations won over the number of simulations played. Our current state is the pink `37//100`, so from here, there are `3` possible moves we can consider. One move won `60` out of the `79` simulations; the second move won `1` out of `10` simluations; and the third move won `2` out of `11` simulations.

It makes sense to choose the move that had the highest win percentage, but this doesn't necessarily mean the other two moves are bad. This is because we only had `10` and `11` simluations for those moves; it's possible that they could have performed even better if more simluations had been played out.

This decision about which state to go to next is decided by a selection policy, i.e., the selection policy tells the algorithm which state to go to next. There are two factors that influence the selection policy: exploitation and exploration. Exploitation is choosing states that have performed well (e.g., choosing the move with the highest win percentage) and exploration is choosing states that have had only a few simulations (to gather more information and to take a chance on it turning out to be a good move).

So now the search has progressed three moves later and our current state is at the brown `27//35`. It's time to run a simulation. (The moves that are played in this simulation are decided by the playout policy.)

Let's say that the simulation resulted in a loss for pink. Now we have to update the tree with this new information. This step is called back-propagation.

To summarize the process:

• Selection: keep choosing moves (guided by the selection policy) until we reach a leaf
• Expansion: generate a new child
• Simulation: play out a simulation (guided by the playout policy)
• Back-propagation: update all the search tree nodes with the new information

Stochastic Games

Stochastic games are ones that involve randomness and luck. Like games that involve rolling dice. In backgammon, the possible moves that a player can make is determined by the result of the dice rolls. So we can't really build the game tree the same way we did before because we don't know what the possible moves will be.

We have to include chance nodes, which represent a possible outcome from the random aspect of the game. So if a die can have `6` different values, then there will be `6` chance nodes for each value of the die and then we list all the possible moves for each chance node. If we're rolling two dice, then there will be a chance node for every possible pair of values.

Since we don't know for sure that a chance node will be reached, they don't have definite minimax values. Instead, each chance node has an expectiminimax value, which is the sum of the minimax values of each action weighted by the probability of that action (this is the expected value of the chance node).

Evaluation functions for games of chance

Recall that in heuristic alpha-beta search, we kept searching until a certain point, then used a heuristic function to estimate the rest of the minimax values. For stochastic games, we can do the same, but we need a slightly different heuristic function.

Let's go back to the game where MAX is trying to reach the node with the highest value and MIN is trying to have MAX end up at the node with the lowest value. Suppose we have this game tree:

We can see that the left chance node has a higher expectiminimax value, so MAX should go left (move `a_1`). We can also see that this is the optimal move for MAX since moving right means that there is a `90%` chance that MIN will be able to go to the node with `1`.

But let's look at what happens if the heuristic function had assigned different values to each of the nodes at the cutoff point.

Now, the right chance node has a higher expectiminimax value, so MAX will go right (move `a_2`). But we can see that this is not the optimal choice because there is a `90%` chance that MIN will be able to go to the node with `1`.

From this, we can see that the heuristic function must also take into account the probabilities when calculating the utility. (I might go into more detail on this? Let's see where the class goes.)

Partially Observable Games

Kriegspiel: Partially observable chess

Kriegspiel is an interesting version of chess where each player has their own board, and each player's board has only their own pieces. Each player proposes a move and a referee (who can see both players' boards) tells them if the move is legal or illegal. If the move is illegal, that player keeps proposing moves until a legal one is found. If the move is legal, the referee announces captures, checks, and mates if any of those happened.

Using belief states helps here. In the context of games, a belief state is the set of all board states that are logically possible based on the moves that have happened so far. With this, we can use the AND-OR search algorithm we saw before.

Knowledge-Based Agents

So far, all we've seen are problem-solving agents. As powerful as they are, they aren't able to reason or adapt to new information.

Knowledge-based agents are able to use logic to make decisions. They have a knowledge base of sentences, which are the facts that are known by the agent. They use the sentences in their knowledge base to come up with new sentences (conclusions). This process is called inference.

The Wumpus World

Here, we'll go over an example of how a knowledge-based agent works.

The wumpus world is a cave with a monster (wumpus), a pile of gold, and a bunch of bottomless pits. The goal of the agent is to find the gold while avoiding the pits and the wumpus. The wumpus can be killed with an arrow, but the agent has only one arrow to use.

Let's say our agent (denoted as `A`) starts in the lower-left corner. It doesn't detect a stench or a breeze so the two squares next to it are safe.

After moving right, the agent detects a breeze. The breeze could be coming from the square above or from the right. (Bear with me here, the agent can't lick its finger to see which direction the breeze is blowing.) There is only one square that is for sure safe, so the agent decides to go back and move there.

Here, the agent detects a stench. Theoretically, the stench could be coming from the square above or from the right. But since the agent didn't detect a stench in the previous state (image above), it knows the wumpus can't be in the square to the right.

Also, since the agent is not detecting a breeze, that means the square to the right is not a pit.

Avoiding the wumpus, the agent finds the gold!

Logic

In order for a knowledge-based agent to be able to reason and make inferences, it needs to understand logic.

A sentence has a truth value, i.e., it can either be true or false. Its truth value depends on the world (model) it's in.

If a sentence `alpha` is true in model `m`, then `m` satisfies `alpha` (or `m` is a model of `alpha`).

The truth value of a sentence can depend on the truth value of another one. We say that a sentence can follow logically from another sentence.

Let's see how this can be applied to the wumpus world. Suppose the agent is at `[2,1]` (the second step when it detected a breeze).

`KB` is the agent's knowledge base. There are three possible models based on the knowledge that it feels a breeze on its current square (either the pit is in the square above, to the right, or both).

Let `alpha_1` be the sentence, "There is no pit in `[1,2]`." There are four possible models based on this sentence.

Notice that in every model in which `KB` is true, `alpha_1` is also true. That is, if you pick any model in `KB` and say "There is no pit in `[1,2]`", the sentence is true. This means that `KB` entails `alpha_1`, and the agent can conclude that there is no pit in `[1,2]`.

Now let `alpha_2` be the sentence, "There is no pit in `[2,2]`."

There are some models in `KB` where if we say "There is no pit in `[2,2]`", the sentence is false. So `KB` does not entail `alpha_2`, meaning that the agent cannot conclude that there is no pit in `[2,2]`.

Whether you realized it or not, we were running an algorithm to check entailment. The inference algorithm is called model checking.

An inference algorithm is sound or truth-preserving if it derives only entailed sentences. That is, the results of running the algorithm are all sentences that follow logically. An unsound algorithm makes things up.

An inference algorithm is complete if it can derive any sentence that is entailed. That is, all sentences that follow logically can be derived using the algorithm.

Propositional Logic: A Very Simple Logic

Syntax

A proposition is a sentence (that can be true or false). We use a symbol (typically a letter) to represent a proposition. For example, `W_(1,3)` can be the symbol for "there is a wumpus at `[1,3]`" and `P_(3,1)` can be the symbol for "there is a pit at `[3,1]`."

We can use logical connectives to turn sentences into complex sentences. The most common connectives are

• `not` (not). `not W_(1,3)` (the negation of `W_(1,3)`) means "there is no wumpus at `[1,3]`."
• `^^` (and). `W_(1,3) ^^ P_(3,1)` means "there is a wumpus at `[1,3]` and there is a pit at `[3,1]`."
  • a sentence of this form is called a conjunction
• `vv` (or). `W_(1,3) vv P_(3,1)` means "there is a wumpus at `[1,3]` or there is a pit at `[3,1]`."
  • a sentence of this form is called a disjunction
• `implies` (implies). `W_(1,3) implies not W_(2,2)` means "if there is a wumpus at `[1,3]`, then there is no wumpus at `[2,2]`."
  • a sentence of this form is called an implication
• `iff` (if and only if). `W_(1,3) iff not W_(2,2)` means "there is a wumpus at `[1,3]` if and only if there is no wumpus at `[2,2]`."
  • a sentence of this form is called a biconditional

Semantics

The semantics of propositional logic defines the rules for determining the truth of a sentence. Here's a truth table that defines the connectives:

`P`	`Q`	`not P`	`P^^Q`	`PvvQ`	`P implies Q`	`P iff Q`
false	false	true	false	false	true	true
false	true	true	false	true	true	false
true	false	false	false	true	false	false
true	true	false	true	true	true	true

A simple knowledge base

Using all of this, we can build a knowledge base for the wumpus world. For the symbols, we have:

• `P_(x,y)` is true if there is a pit in `[x,y]`
• `W_(x,y)` is true if there is a wumpus in `[x,y]`
• `B_(x,y)` is true if there is a breeze in `[x,y]`
• `S_(x,y)` is true if there is a stench in `[x,y]`
• `L_(x,y)` is true if the agent is in `[x,y]`

With these symbols, we can create sentences that describe what the agent saw (and knows) in the wumpus world. (Each sentence will be labeled with `R_i`. The `R_i`s themselves are not symbols.)

• There is no pit in `[1,1]`
  • `R_1`: `not P_(1,1)`
• A square is breezy if and only if there is a pit in a neighboring square
  • `R_2`: `B_(1,1) iff (P_(1,2) vv P_(2,1))`
  • `R_3`: `B_(2,1) iff (P_(1,1) vv P_(2,2) vv P_(3,1))`
• There is no breeze in `[1,1]`
  • `R_4`: `not B_(1,1)`
• There is a breeze in `[2,1]`
  • `R_5`: `B_(2,1)`

A simple inference procedure

We can now perform the model-checking algorithm a little more formally. The relevant symbols are `B_(1,1),B_(2,1),P_(1,1),P_(1,2),P_(2,1),P_(2,2),P_(3,1)`. A model is an assignment of true or false to each symbol.

For example, here are the assignments for each of the three models in `KB` from top to bottom:

• `B_(1,1)=F,B_(2,1)=T,P_(1,1)=F,P_(1,2)=F,P_(2,1)=F,P_(2,2)=F,P_(3,1)=T`
• `B_(1,1)=F,B_(2,1)=T,P_(1,1)=F,P_(1,2)=F,P_(2,1)=F,P_(2,2)=T,P_(3,1)=F`
• `B_(1,1)=F,B_(2,1)=T,P_(1,1)=F,P_(1,2)=F,P_(2,1)=F,P_(2,2)=T,P_(3,1)=T`

Can `not P_(1,2)` (there is no pit in `[1,2]`) be derived from `KB`? Well, in all three models, `P_(1,2)` is false, meaning there is no pit in `[1,2]`. So yes, `not P_(1,2)` is entailed by `KB`.

Propositional Theorem Proving

If there are a lot of models in the knowledge base, then it's not efficient to check each model to determine entailment.

Theorem proving is a method of deriving a sentence by applying the rules of inference to the sentences in the knowledge base.

Inference and proofs

To derive a sentence, we have to apply inference rules to come up with a proof.

Modus Ponens is a rule that says if we have the sentence `alpha implies beta` and we know `alpha` is true, then we can conclude `beta` is true.

And-Elimination is a rule that says if we have a conjunction that is true, then both of the individual sentences by themselves are true.

With these inference rules, we can prove a sentence is true without having to check each model in the knowledge base. Let's see how we can prove `not P_(1,2)` using these rules.

We have these sentences in our knowledge base:

• `R_1`: `not P_(1,1)`
• `R_2`: `B_(1,1) iff (P_(1,2) vv P_(2,1))`
• `R_3`: `B_(2,1) iff (P_(1,1) vv P_(2,2) vv P_(3,1))`
• `R_4`: `not B_(1,1)`
• `R_5`: `B_(2,1)`

The only sentence that involves `P_(1,2)` is `R_2`, so we'll start there.

Apply biconditional elimination to `R_2` to get

Apply And-Elimination to `R_6` to get

Use the logical equivalence for contrapositives to get

Apply Modus Ponens with `R_8` and `R_4` to get

Apply De Morgan's rule to get

Apply And-Elimination to `R_10` to get

Proof by resolution

Resolution is another inference rule. It can be loosely thought of as a "cancellation", like in math. Let's say we have two sentences `alpha vv beta` and `not alpha`. Then the `alpha` and `not alpha` "cancel out" (the technical term is "resolves with") and we can conclude `beta`.

Let's see how we can use resolution to prove that there is a pit in `[3,1]`.

We'll add some more sentences to the knowledge base:

• `R_12`: `not B_(1,2)`
• `R_13`: `B_(1,2) iff (P_(1,1) vv P_(2,2) vv P_(1,3))`

Using the exact same rules in the proof above, we can derive

• `R_14`: `not P_(2,2)`
• `R_15`: `not P_(1,3)`

We can use biconditional elimination and And-Elimination on `R_3` (which is `B_(2,1) iff (P_(1,1) vv P_(2,2) vv P_(3,1))`) to get

Then we can use Modus Ponens with `R_5` (which is `B_(2,1)`) to get

Now we can use our new resolution rule. We have `not P_(1,1)` (from `R_1`), which resolves with the `P_(1,1)` in `R_16` to get

We also have `not P_(2,2)` (from `R_14`), which resolves with the `P_(2,2)` in `R_17` to get

Conjunctive normal form

The resolution rule only works for clauses (a.k.a. disjunctions of literals) though. So how is this helpful for sentences that aren't clauses? Well, it turns out that every sentence is logically equivalent to a conjunction of clauses. That is, any sentence can be converted into a combination of clauses.

A sentence that is a conjunction of clauses is in conjunctive normal form or CNF.

Let's look at how to convert `B_(1,1) iff (P_(1,2) vv P_(2,1))` into CNF.

A resolution algorithm

Resolution algorithms are based on the idea of proving a contradiction. Recall that proving `KB |== alpha` is the same as proving `(KB ^^ not alpha)` is unsatisfiable. So if we assume `(KB ^^ not alpha)` is true and arrive at a contradiction, then `KB |== alpha`.

First, `(KB ^^ not alpha)` is converted into CNF. Then the resolution rule is applied to the resulting clauses. Each pair that contains complementary literals is resolved to produce a new clause, which is added to new.

This keeps going until one of two things happens:

• there are no new clauses that can be added, which means `KB` does not entail `alpha`
• two clauses resolve to yield the empty clause, which means `KB` does entail `alpha`
  • if the empty clause is yielded, then there is a contradiction

Let's go back to the first step in the wumpus world and look at this algorithm in action. The agent is in `[1,1]` and there is no breeze. How do we use resolution to prove there is no pit in `[1,2]`?

The relevant knowledge base is

and `alpha` is

When we convert `(KB ^^ not alpha)` into CNF, we get

This gives us five clauses. For each pair of clauses, we apply resolution to get new clauses. For example,

We can see that if we were to continue, we would eventually apply the resolution rule to `P_(1,2)` and `not P_(1,2)` to get the empty clause. This means that `alpha = not P_(1,2)` is proven.

Horn clauses and definite clauses

A definite clause is a disjunction of literals where exactly one of them is positive. For example, `alpha vv not beta vv not gamma` is a definite clause.

So what's the point of definite clauses? It turns out that having a knowledge base of definite clauses allows us to use another set of inference algorithms called forward-chaining and backward-chaining.

Forward and backward chaining

Suppose we had the implication `(alpha ^^ beta) implies gamma`. Forward chaining says that if we know `alpha` and `beta` are true, then we can add `gamma` to the knowledge base, i.e., we can conclude that `gamma` is true. (Forward chaining is essentially an implementation of Modus Ponens.)

Let's say we had these statements in the knowledge base:

and let's say we wanted to prove that `Q` is true.

With forward chaining, we start with the facts that we know are true (which are `A` and `B` in this case) and see if we can reach the goal.

1. `A` and `B` give us `L`
2. `B` and `L` give us `M`
3. `L` and `M` give us `P`
4. `P` gives us `Q`

Backward chaining is kind of the same thing, just with a different mindset. With backward chaining, we start with what we want to prove (`Q` in this case) and see if we have enough information to prove it.

1. If we want to prove `Q`, we need to show `P` is true.
2. In order to show `P` is true, we need to show `L` and `M` are true.
3. In order to show `M` is true, we need to show `B` and `L` are true.
   • Well, we already have `B`, so we just need `L`.
4. In order to show `L` is true, we need to show `A` and `B` are true.
   • Well, we already have `A` and `B`, so we can get `L`.
5. Now that we have `B` and `L`, we can get `M`.
6. Now that we have `L` and `M`, we can get `P`.
7. Now that we have `P`, we can get `Q`.

But wait, forward chaining and backward chaining are algorithms for implications. What do they have to do with definite clauses?

Definite clauses can be converted into implications. Recall implication elimination:

We can use this (in the other direction) to convert definite clauses into implications.

First-Order Logic

As much as we can do with propositional logic, there are some limitations to it. The biggest limitation is that we need a lot of propositions to represent some basic ideas.

For example, to represent the idea that there is a breeze next to a pit, we use

To represent the idea that there is exactly one wumpus, we use

and

First-order logic solves this problem by dealing with objects and relations instead of propositions. For the wumpus world, objects would be things like squares, pits, and wumpuses. Relations would be properties or descriptions of those objects, like "is breezy", "is adjacent to", and "shoots".

Syntax and Semantics of First-Order Logic

Symbols and interpretations

Constant symbols are used to represent objects and predicate symbols are used to represent relations. Some examples of constant symbols are `text(Wumpus)`, `text(Square)`, and `text(Agent)`. Some examples of predicate symbols are `text(Breezy)` (for "is breezy"), `text(Pit)` (for "is a pit"), and `text(Adjacent)` (for "is adjacent to").

Atomic sentences

We combine constant symbols and predicate symbols to form atomic sentences.

`text(Alive(Wumpus))` is a sentence that stands for "The wumpus is alive", and this sentence can be either true or false.

Complex sentences

We can use the same connectives we saw in propositional logic here as well. For example, `not text(Alive(Wumpus)) implies not text(HasArrow(Agent))`.

Quantifiers

Now that we have the concept of objects, we can make general statements about a whole collection of objects (instead of enumerating each object one by one like we did earlier) using quantifiers.

Universal quantification

The universal quantifier `AA` is pronounced "for all". A sentence using this quantifier looks like

The `x` is a variable.

Existential quantification

The existential quantifier `EE` is pronounced "there exists".

Using First-Order Logic

The wumpus world

The agent can perceive a stench (from the wumpus), a breeze (from a pit), a glitter (from the gold), a bump (when walking into a wall), and a scream (when the wumpus is killed). An example of a percept sentence then could look like

To transform the percept into a fact about the wumpus world, we can do things like

We can implement simple reflex behavior with

We can describe the environment concisely with

If we have a function `text(At)(x,s,t)` to mean object `x` is at square `s` at time `t`, then we can say things like

Propositional vs. First-Order Inference

So how do we prove statements when these new quantifiers are involved? Well, we can convert sentences in first-order logic into sentences in propositional logic by eliminating the quantifiers.

Eliminating universal quantifiers is fairly simple; we just replace the variables with objects. For example, let's say we have the sentence "All greedy kings are evil.":

Then we can create new sentences for all people that exist:

This is Universal Instantiation.

Existential Instantiation is similar except we replace the variables with a new constant symbol. For example, the sentence

becomes

by replacing `x` with `C_1`, where `C_1` is a symbol that represents an object.

Reduction to propositional inference

Then we replace predicate symbols (that have no variables) with proposition symbols. So `text(King)(text(John))` becomes something like `text(JohnIsKing)`.

This whole process is called propositionalization.

Forward Chaining

First-order definite clauses

Like we saw before, a definite clause in first-order logic is a disjunction of literals where exactly one of the literals is positive (they can be in the form of an implication after conversion). Existential quantifiers are not allowed, but universal quantifiers are. So `text(King)(x) ^^ text(Greedy)(x) implies text(Evil)(x)` is a definite clause, where the `AA x` is implicit.

Let's look at the following problem: The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of America, has some missiles, and all of its missiles were sold to it by Colonel West, who is American. We can use forward chaining to prove that West is a criminal.

First we populate the knowledge base with definite clauses. "... it is a crime for an American to sell weapons to hostile nations" becomes

"Nono ... has some missles" is `EE x` `text(Owns)(text(Nono), x) ^^ text(Missle)(x)`. Using Existential Instantiation, we get

"All of its missles were sold to it by Colonel West" becomes

"West, who is an American" becomes

"The country Nono, an enemy of America" becomes

We also need to establish that a missle is a weapon:

and an enemy of America is hostile:

A simple forward-chaining algorithm

To prove that West is a criminal, we need to show `text(American)(text(West)) ^^ text(Weapon)(M_1) ^^ text(Sells)(text(West), M_1, text(Nono)) ^^ text(Hostile)(text(Nono)) implies text(Criminal)(text(West))`.

• `text(American)(text(West))` is given
• `text(Weapon)(M_1)`
  • `text(Owns)(text(Nono),M_1) ^^ text(Missle)(M_1)` gives us `text(Missle)(M_1)`
  • `text(Missle)(M_1) implies text(Weapon)(M_1)` gives us `text(Weapon)(M_1)`
• `text(Sells)(text(West), M_1, text(Nono))`
  • `text(Owns)(text(Nono),M_1) ^^ text(Missle)(M_1)` gives us `text(Sells)(text(West), M_1, text(Nono))`
• `text(Hostile)(text(Nono))`
  • `text(Enemy)(text(Nono), text(America))` and `text(Enemy)(x, text(America)) implies text(Hostile)(x)` give us `text(Hostile)(text(Nono))`

Now that we have shown the four premises are true, we can use forward chaining to get `text(Criminal)(text(West))`.

Resolution

Conjunctive normal form for first-order logic

Like we saw before, a sentence in conjunctive normal form (CNF) is a conjunction of clauses (recall that a clause is a disjunction of literals). The literals can contain variables, which are assumed to be universally quantified.

The sentence `AA x,y,z` `text(American)(x) ^^ text(Weapon)(y) ^^ text(Sells)(x,y,z) ^^ text(Hostile)(z) implies text(Criminal)(x)` becomes

Every sentence of first-order logic can be converted into a CNF sentence.

Converting a sentence to CNF is similar to the propositional case; we just need to handle the quantifiers and the variables.