Artificial Intelligence — An introduction
--
This is some short notes about my Artificial Intelligence Nanodegree at Udacity.
Navigation Algorithms
The navigation is one of the main problems of AI. How can we find the best (or the shortest) path from one place to another?
We cannot search for all paths until we find our destiny. If we do that, we will take too long time and we will not find the optimal path! So, we need a Heuristic!
Heuristic
Some additional piece of information — a rule, function or constraint — that informs an otherwise brute-force algorithm to act in a more optimal manner.
In our navigation problem, a good heuristic is the smallest direct distance. We can look at every path, exploring it which satisfies the better our heuristic. The current next step that seems like the best choice may not turn out to be on the optimal path. The heuristic is used to decide which step we should explore next.
A* Search
Now, with our heuristic we can explore the paths. One of most used and effective algorithms is A* Search.
Game Playing
Another AI problem is Game Playing. How can We teach a computer to play Tic Tac Toe?
Here we need two things: a board representation and a heuristic!
The board representation will help us to search in a tree of all possible solutions. The heuristic will lead us to the best choice. With a good heuristic we will not explore movements that will lead us to bad solution. It is wast of time search for movements that will neve contribute to a winning combination. This is know as Pruning the search tree.
Mini-Max Algorithm
You are trying to maximize your changes of winning on your turn, and your opponent is trying to minimize your change of winning on their turn.
Probability Theory
Probability is a necessary tool for AI.
It gives us a formal mechanism to capture uncertainty in the real world. And lets us make sensible decisions, even when we are not fully sure about something.
To explain how probability could help us, let see the Monty Hall Problem.
Monty Hall Problem
Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say №1, and the host, who knows what’s behind the doors, opens another door, say №3, which has a goat. He then says to you, “Do you want to pick door №2?” Is it to your advantage to switch your choice?
If you look for the solution of this problem, you will see that if you continue with the same door, you have less change of winning than if you change the door. This occurs because the door that the host open is any port. The host know in with door the car is, so this knowledge affects his decision.
Defining Intelligence
The question about what is intelligence is central in AI. We use the word intelligence when we don’t understand how the thing works, when we know we just use the name algorithm or formulas. But we can define intelligence the ability to solve problems like human can solve.
Agent, Environment and State
Intelligent systems can interact with the environment. It can precept it with sensors and act with ir with effectors.
The agent is all the software and hardware that are relevant in the system.
The state is all information that the agent need to complete the task. And the goal state is the objective that the agent should reach.
Perception, Action and Cognition
The perception is know as the ability of sensing the properties of the environment.
Actions are the useful outputs from the agent that changes the environment.
The cognition is the ability of decide which action should be execute based on the perception.
Types of AI Problems
AI problems can be classified as the following categories:
- Fully Observable: the environment can be fully observable, like chess game.
- Partially Observable: the environment cannot be fully observable, like battleship
- Deterministic: we know the results of each action
- Stochastic: the is uncertainty
- Discrete: there is a finite number of states
- Continuous: the number os states is infinite
- Benign: the agent is the only one taking actions that affect the goal
- Adversarial: there are more than one agents taking actions that affect the goal.
Rational Behavior And Bounded Optimality
The agent has a rational behavior when it takes actions to maximize its expected utility given a desired goal.
When it exists some limitations as partially observable environment, limited computational resources such as memory or processing speed, or rules imposed as given deadline, we cannot expect that the agent behave optimally. In that case we create a desired bound for the agent reach.
