polimd/Artificial Intelligence/lesson_03.md

AI - lesson 03

Francesco Arrigoni

14 October 2015

Goal Oriented agents

Historically called problem-solving agents

Steps involved:

1. Formulate a problem
   Usually performed by the designer
2. Search for a solution
   Usually performed by the agent itself
3. Execute the actions that compose the solution.
   Performed by the agent

This is different from usual systems in which step 2 (formulate the algorithm) is performed by a human.

The types of algorithms created by the agents are usually simple, without IF statements.

Formulating the problem:

The environment we have to interact with is:

• static
• deterministic
• fully observable
• known
• discrete

The problem can be formulated defining the following five elements:
(example problem is the reduced version of 15 puzzle: 8 puzzle)

1. The initial state: a description of the initial situation of the problem
2. Actions (s) = {actions that are applicable is s} Return the legal moves from the state s.

The state s₀ is

7	2	3
1	4	8
6	5	4

Actions(s₀)={$\leftarrow,\uparrow$}

1. Result (s,a) = s' have the chosen move as argument and returns the new state.
   $a \in Action(s)$
   The result function is also called transition function (model)

We are considering a deterministic model, so that the result of a given action is fixed

I can state that initial state, actions and result are elements of a graph named state space

In our state space graph:

• vertices correspond to states
  
• arcs correspond to actions.

The graph is implicitly defined, it's not represented with an incidence matrix.
For example the state space of chess game is estimated to be $10^{120}$.
It is almost impossible to represent, but we can build algorithm that can win a game exploring only a very small portion of the graph.

The agents viewed at lesson are in a sense less powerful than Operating Research algoritms, but they don't require knowing the totality of the graph, and this is an advantage.

A path on a graph is a sequence of states that are connected on the graph.

1. Goal test: returns true or false, it is a test to check if the case is final or not.
   • explicit goal test: list of all the final states ex: 8 puzzle
   • implicit goal test: condition that characterizes final states ex: chess

Every path in the state space should be associate to a cost (number), that is the sum of the costs of the action composing the path.

1. Path cost: is the sum of the costs of the action composing the path.

The solution of the problem is defined as

The path in the state space that brings from the initial state to any state satisfying the goal test

The optimal solution is the solution with minimum path cost.

Our model is limited to the relevant aspects of the problem, for example it doesn't comprehend the color of the tiles in the 8 puzzle.

The 8 queens problem

-	1	2	3	4	5	6	7	8
1	Q
2
3
4							Q
5
6
7
8

We have to place the 8 queens so that no two queens are in the same row, column or diagonal.

first problem formulation:

1. initial state: empty board
2. actions(s)= {add a queen in an empty cell}
3. result(s,a)=
   
4. goal test: are there 8 queens on the board and no one is attacked?
5. step cost
   

state space: $64\times63\times...\times57=1.8\times10^{44}$

second formulation:

1. initial state: empty board
2. actions(s)= {add a queen in the left most empty column such that the queen is not attacked}
3. result(s,a)=
   
4. goal test: are there 8 queens on the board?
5. step cost state space: $2057$

In the first formulation all the rules of the game were embedded in the goal test,
In the second formulation, all the knowledge is embedded in the action function,
so the check of a legal step is made every action and not in the end.

In general is smarter to embed as much knowledge as possible in the action function, and leave as little as possible to the goal test, doing this we reduce the size of the state space, which can make difference between practically solving a problem and impossible to solve problems.