# Cour 5 -- Introduction a l'Intelligence Artificielle et à la Theorie des Jeux

###### tags `cour` `M1 S1` `IA`
[Somaire](/8Sa-Z4QBS1ep0xPwtzigJA)\
[Precedent](/Lj3NskXUTea7kl21sp3EmQ)
> [time= 9 oct 2020]

[TOC]

## Recherche local
On a souvent pas besoin de savoir le chemin a empreinter.

Pour la recherche local:
- on maintienle noeud local (pas le chemin)
- on se déplace vers un voisin du noeud courant

il nous faut donc:
- un fonction de coût définie pour chaque noeud
- touver le noued de coût minimal

C'est don un probleme d'optimisation de la fonction de cout

## descente de gradient (steepest descent)
### normal

def steepest_descent(problem):
    """
    return minimum local
    """
    courant = Noeud(probleme.etat_initial)
    while(True):
        # voisin avec le cout minimal
        voisin = courant.get_voisin_cout_minimal()
        if voisin.cout >= courant.cout:
            return voisin
        courant = voisin

Steepest-descent appliquée à 8 reines (avec initialement 8 reines, une par ligne):
- bloqué dans 86% de cas sans qu'une solution soit trouvée
- 4 itérations en moyenne si une solution est trouvée
- 3 itérations en moyenne si une solution n'est pas trouvée et l'algorithme steepest-descent bloque
- le nombre d'état 8^8^
### steepest descent (variantes)
- steepest descent classique s'arrete si on trouve un plateau
- pour éviter le blocage dans ce cas: il faut permettre les mouvement latéraux (donc quand on arrive sur un plateau)
- il faudra limiter le neombre de mouvement latéraux consécutifs

Steepest-descent variantes appliquée à 8 reine:
- 94% de trouver une solution
- 21 itérations en moyenne si une solution est trouvée
- 64 itérations en moyenne avant bloquage

### steepest descent stochastique
- on selectionne un voisin avec un certaine **probabilité**
la proba peut dépendre de la pente (le coût)
\ plus élevé pour les voisin a coût petit\
propotionel à $\frac{1}{coût}$\
cela permet de passer les collines avoisinante et sortir d'un minimum local entouré de collines
- on peut **redémarrrer** et conduire plusieur rechercher à partir de **plusieurs points initiaux choisis aléatoirement**\
On fait des seauts vers d'autres zones de recherche

## recherche locale à faisceau (local beam search)
1. A chaque moment on maintient k noeud ($n_1, \cdots, n_k$)
2. On génrere tout les voisins V de ces noeuds
3. Si parmi ces voisins il y a une solution alors on termine
4. Sinon pour l'étapes suivante on choisit dans V k noeuds dont le coût est minimal

Notons qu'il est possible que pour l'étape suivant on garde plusieurs voisin d'un noeud et aucun voisin d'un autre (on choisit k noeud d'un ensemble de tous les voisins de {n1,...,nk}).


## algorithme génétiques
- Initialement k états générés aléatoirement (**population**)
- Un **état représenté** par une **chaine de caractères** sur un alphabet fini (souvent 0,1)
1. Un **état successeur** obtenu en **combinant deux états parents**

2. **La fonction d'évaluation** (fitness fonction) permet d'évaluer la qualité d'un état. Plus la valeur de la fonction est élevée plus l'état est mieux "adapté".
3. On produit donc un nouvelle génération d'états par la sélection:
- **croisement**
- **mutation**.


def genetic_algo(population, finess_fn):
    """
        population: set
            set of individual
        finess_fn: func
            a function that measures 
            the fitness of an indivudual
        return individu
    """
    while(individu_fit in population or times_up):
        new_population = {}
        for i in range(len(population)):
            # crée l'enfant
            x = random_selection(population, finess_fn)
            y = random_selection(population, finess_fn)
            child = reproduce(x, y)
            # fait les mutation
            if small_random_probalit():
                child = mutate(child)
                
            new_population.add(child)
            
        poupulation = new_population
        
    # meilleur individu dans la population 
    # avec la fitness function
    return max_with_fitness(population, finess_fn) 
        
def reproduce(x, y):
    """
    x, y: individu
        parent
    return individu
    """
    m = len(x)
    c = random.randint(1, n)
    return x[1: c] + y[c: n]

## algorithme online
Agent offline:
- agent cherche le probleme et apres s'exécute

Un agent online:
- le calcul va etre entrelacé avec l'exécution
- a chaque moment on peut visiter uniquement un voisin du sommet courant (recherche d'un chemin dans un labyrinthe)
- l'exploration -- il faut utiliser les actions pour découvrir l’environnement
- l’agent se déplace physiquement dans l’environnement et le découvre progressivement
- adapté à l'environnement dynamique qui change avec le temps ou un environnement inconnu (on ne connait pas quels sont les états)

La qualité de la recherche online mesurée par:
$$
\text{competitive ratio} = \frac{\text{compléxité en temps de l'algo online}}{\text{compléxité en temps de l'algo le plus efficace si l'environement est connu}}
$$

S'il y a des états sans issu l'algorithme peut rester bloqué (concerne le graphe orienté).

### parcour en profondeur (online)
- **delta(s,a)** \
l'état obtenu en appliquant l'action a dans l'état s
- Pour chaque action **a** et chaque état **s**, si **delta(s,a)=t** alors il existe une action **b** telle que **delta(t,b)=s** \
(on peut revenir sur ces pas). \
De plus b peut être trouvée si on connait **s**, **a**, **t**.
- Online depth-first search est un algorithme naturel de recherche dans un labyrinthe

algo:
- **s**\
un variable globale qui donne l'état précédent
- **a**
l'action exécutée dans s
- **result\[état, action]**\
une table indexées par l'état et l'action qui donne la valeur de delta(état,action).\
initialement la table est vide
- **untried\[état]**\
qui donne pour un état l'ensemble d'action qu'on a pas encore exécuté dans cet état
- **unbacktracked\[état]** donne pour chaque état visité la liste des actions "back" qu'on a pas encore exécuté\
initialement vide

s = None
a = None
result = {}
untried = {}
unbacktracked = {}
def online_DFS_agent(sp):
    """
    sp: 
        a percept that identifies the current state
    return: action
    --- 
    result: dict
        a table indexed by state and action, initially empty
    untried: dict
        a table that lists, for each state, the actions not yet tried unbacktracked: list
        a table that lists, for each state, the backtracks not yet tried s, a, the previous state and action, initially null
    """
    if goal_test(sp):
        return STOP
    if sp not in untried: # sp is a new state
        untried[sp] = sp.actions
    if s is not None:
        result[(s, a)] = sp
        unbacktracked[sp].push_front(s)
    if untried.get(sp) is None:
        if unbacktracked.get(sp) is None:
            return STOP
        else:
            # an action b such that result[s′,b] = POP(unbacktracked[s′])
            a = get_b(result, unbacktracked)
    else:
        a = untried[s_p].pop()
    s = sp
    return a

- Termine sur un espace d’état fini
- Peut être inefficace : explore inutilement des partie de l’espace d’état\
La version online DFS borné itéré atténue ce problème

### hill climbing
- Hill climbing (descente du gradient) est aussi « local »
- Mais pas pratique : blocages dans les min locaux, pas possible de redémarrer d’un autre point aléatoire

### hill climbing - random walk
1. Random walk : tirer un successeur aléatoirement
2. Si le but est accessible, il finira par le trouver

Il peut mettre un temps exponentiel d'étape.
A chaque état la probalité de reculer est 2 fois plus grande
A chaque étape il reviendra revoir tout ce qu'il a visité

### LRTA* - learning real time A*
Pour chaque sommet s, une heuristique admissible h(s).\

L'idée est **d'amélioré l'heuristique** au cours de l'exploration.

On peut alors sortir des pièges des min locaux.
Si l'environnement est sûr (il existe une solution accessible à partir de chaque sommet) alors LRTA* est complet.

Variables globales:
- résultat\
un tableau dynamique **(un map)** initialement vide indexé par les couple **(état, action)**\
Si résultat\[s,a] défini alors on a déjà visité s, on a exécuté a dans s et résultat\[s,a] — donne l'état obtenu en appliquant a dans s
- H\
un tableau dynamique **(un map)** indexé par les **états**, initialement vide\
H\[s] donne la valeur de heuristique pour l'état s. Pendant la première visite dans s on initialise H\[s]=h(s), où h une fonction heuristique admissible connue.

1. quand on entre dans un état t et si H\[t] non défini alors c'est la **première visite** dans t et on initialise **H\[t]=h(t)**
2. quand on **sort d'un état s** alors si tous les voisins des ont déjà été visités alors **on calcule**\
$w = \min coût(s, b, résultat[s, b] + H[résultat[s, b]])$ pour b dans Actions(s)
- si **H\[s] < w** alors **H\[s]=w**


s = None # etat précédent
a = None # action a executé pour aller de s vers l'état courant
H = {}
resultat = {}
def LRTA_star_cout(, a , t):
    """
    s: Etat
        etat précédent
    a: Action
        action a effectué pour aller de s a t
    t: Etat
        etat suivant
    """
    if t is None:
        return h(s)
    return cout(s, a, t) + H[t]
    
def LRTA_star(t):
    """
    t: Etat
        etat actuel
    """
    if t == etat_final:
        return STOP
    if H.get(t) is None:
        H[t] = h(t)
    if s is not None:
        resultat[(s, a)] = t
        w = min(map(lambda b: LRTA_star_cout(s, b, resultat[(s, b)]),
                    s.actions))
        H[s] = max(H[s], w)
    # action b qui minimise LRTA*coût(t,b,résultat[t,b])
    a = get_action_minimise(t, résultat, LRTA_star_cout)
    s = t
    return a


[suivant](/xN-48n6VT-yCosXIGuXs_A)