02 - Architettura BDI: Belief, Desire, Intention

Il tuo agente è un corriere in un corridoio. Ha un piano di nove passi per consegnare un pacco, e al quarto passo la porta che deve attraversare si chiude. Che cosa fa? Può ricalcolare tutto a ogni passo, e allora spende il tempo a pensare mentre il mondo continua a cambiare; può eseguire il piano fino in fondo, e allora sbatte contro una porta chiusa; può smettere appena qualcosa cambia, e allora abbandona anche piani che sarebbero andati bene. Un'architettura BDI non elimina il dilemma: lo rende una scelta esplicita di progetto.

La risposta in breve: l'architettura Belief-Desire-Intention separa ciò che l'agente crede, ciò che vuole e ciò a cui si è impegnato, e il suo ciclo decide a ogni giro quando conviene abbandonare un impegno. Qui costruisci un interprete minimo, lo fai girare su tre strategie di impegno e leggi i numeri. Il risultato non è quello che ti aspetti: nello scenario della porta tutte e tre consegnano allo stesso istante, e la differenza sta negli sforzi sprecati, non nella velocità.

Tre stati mentali, e perché proprio tre

La fonte primaria di questo articolo è «BDI Agents: From Theory to Practice» di Anand Rao e Michael Georgeff, atti della prima International Conference on Multiagent Systems (ICMAS-95), AAAI 1995. L'ho scaricata e letta nelle parti su cui poggia il testo: l'abstract, l'introduzione, la sezione sul sistema e il suo ambiente, quella sulle strategie di impegno e l'architettura astratta. Le parti sull'applicazione al traffico aereo (il sistema chiamato OASIS) non le ho lette. Il modello mentale di partenza è di Michael Bratman, citato in quell'articolo: il suo libro non l'ho letto.

Gli autori ricavano i tre stati da sei caratteristiche del dominio, per esempio che l'ambiente si può osservare soltanto localmente e cambia in modo imprevedibile. Da lì discendono tre componenti dello stato del sistema.

• Credenze (beliefs): la componente informativa. Servono perché l'ambiente non si legge in un solo atto di percezione, e vanno aggiornate dopo ogni percezione; possono essere una variabile, una base di dati o un insieme di formule.
• Desideri (desires): la componente motivazionale, cioè gli obiettivi con le loro priorità. Gli autori li distinguono dai «goal» della letteratura sull'intelligenza artificiale perché possono essere molti nello stesso istante e incompatibili fra loro.
• Intenzioni (intentions): la componente deliberativa, cioè il corso d'azione scelto per ultimo dalla funzione di selezione.

Le prime due componenti rispondono a «che cosa so» e «che cosa vorrei»; la terza è quella che non ha un equivalente ovvio nei programmi comuni, ed è il motivo per cui l'architettura esiste. Un desiderio non vincola nessuno: puoi averne due in conflitto. Un'intenzione sì, perché è già stata scelta e limita ciò che l'agente considera nei passi successivi.

Il dilemma che giustifica le intenzioni

Rao e Georgeff spiegano perché serve la terza componente con un argomento che conviene rileggere, perché è il cuore dell'articolo. La teoria della decisione chiede di riapplicare la funzione di selezione ogni volta che l'ambiente cambia; i programmi comuni, una volta avviati, si aspettano di arrivare in fondo senza rivalutare nulla. Né l'una né l'altra va bene quando l'ambiente cambia mentre calcoli o mentre esegui: ricalcolare a ogni passo costa troppo e l'azione scelta può essere già invalida, mentre l'impegno incondizionato può far fallire l'obiettivo.

La via d'uscita che l'articolo indica è limitare la frequenza della riconsiderazione, cercando un equilibrio fra riconsiderare troppo e troppo poco, e rimanda a Kinny e Georgeff (1991) per i dettagli: quel lavoro è citato nell'articolo e io non l'ho letto. L'intenzione è lo stato in più che permette tutto questo: ricorda la scelta già fatta, e la riconsiderazione avviene solo quando un controllo esplicito lo decide. Nel tuo corridoio, quel controllo è la domanda «la porta è ancora aperta?».

Il ciclo dell'interprete

Rao e Georgeff descrivono un interprete astratto con una coda di eventi e le tre strutture di dati. A ogni ciclo, il generatore di opzioni legge la coda di eventi e restituisce un elenco di opzioni; il deliberatore ne sceglie un sottoinsieme e lo aggiunge alle intenzioni; se c'è un'intenzione di eseguire un'azione atomica, l'agente la esegue; gli eventi esterni accaduti nel frattempo vanno nella coda; infine l'agente toglie dai desideri e dalle intenzioni quelli riusciti e quelli diventati impossibili. Nel codice che segue ogni passo ha un metodo con lo stesso nome o un nome equivalente, nello stesso ordine.

Gli autori avvertono che questa architettura è un'idealizzazione: si fonda su insiemi di credenze, desideri e intenzioni logicamente chiusi, e le procedure di dimostrazione richieste non sono calcolabili. Il sistema pratico che descrivono semplifica le scelte di rappresentazione. Il listato che segue è una terza cosa ancora, più povera di entrambe: un interprete con un solo desiderio, un piano costruito a mano e un mondo di nove quadrati. Serve a far vedere il ciclo e le strategie di impegno, non a riprodurre il sistema degli autori.

Il primo blocco è il mondo: un corridoio con una porta sul quadrato 5 e una destinazione al quadrato 8. La porta chiusa fa fallire l'azione avanza verso il quadrato 5, e posa riesce solo nel quadrato 8. Gli eventi esterni arrivano a istanti fissi da un dizionario, così ogni scenario si ripete uguale.

"""Interprete BDI minimo: stesso ciclo dell'interprete astratto di Rao e Georgeff (1995)."""

DESTINAZIONE, PORTA = 8, 5


class Mondo:
    """Corridoio 0..8 con una porta sul quadrato 5. Eventi esterni per istante."""
    def __init__(self, eventi):
        self.pos, self.porta_aperta, self.consegnato = 0, True, False
        self.eventi = eventi          # {istante: nome evento}

    def applica_eventi(self, t):
        e = self.eventi.get(t)
        if e == "porta chiude":
            self.porta_aperta = False
        elif e == "porta apre":
            self.porta_aperta = True
        return e

    def agisci(self, azione):
        if azione == "avanza":
            if self.pos + 1 == PORTA and not self.porta_aperta:
                return False          # urta la porta chiusa
            self.pos += 1
            return True
        if azione == "posa":
            if self.pos != DESTINAZIONE:
                return False
            self.consegnato = True
            return True
        return True                   # "attendi"

Il secondo blocco contiene le tre strutture e i primi passi del ciclo. genera_opzioni produce l'opzione «consegna» solo se il desiderio esiste, il pacco non è già consegnato, la porta è creduta aperta e non c'è già un'intenzione per quello scopo: è la condizione per cui il piano si applica. delibera sceglie la prima opzione (ce n'è al più una), aggiorna_intenzioni costruisce il piano dalla posizione creduta, esegui estrae un'azione, oppure restituisce attendi se non c'è nessuna intenzione.

class AgenteBDI:
    def __init__(self, strategia):
        self.strategia = strategia    # "cieco", "singolo", "aperto"
        self.credenze = {"pos": 0, "porta_aperta": True, "consegnato": False}
        self.desideri = {"consegna"}
        self.intenzioni = []          # ogni intenzione: {"desiderio", "piano"}
        self.eventi = ["avvio"]       # coda degli eventi

    def genera_opzioni(self):
        c = self.credenze
        if "consegna" in self.desideri and not c["consegnato"] and c["porta_aperta"] \
                and not any(i["desiderio"] == "consegna" for i in self.intenzioni):
            return ["consegna"]
        return []

    def delibera(self, opzioni):
        return opzioni[:1]            # un solo desiderio: si sceglie il primo

    def aggiorna_intenzioni(self, scelte):
        for d in scelte:
            n = DESTINAZIONE - self.credenze["pos"]
            self.intenzioni.append({"desiderio": d, "piano": ["avanza"] * n + ["posa"]})

    def esegui(self):
        if not self.intenzioni:
            return "attendi"
        return self.intenzioni[0]["piano"].pop(0)

Il terzo blocco chiude il ciclo con due metodi. percepisci aggiorna le credenze dal mondo e, se arriva l'evento «ordine annullato», toglie il desiderio. lascia_atteggiamenti è il punto dove le tre strategie divergono: per ogni intenzione calcola se è riuscita, se è diventata impossibile secondo le credenze (porta chiusa prima del quadrato 5) e se il desiderio è caduto, e usa questi tre fatti in modi diversi a seconda della strategia. Togli quel metodo e l'agente non abbandona mai niente: le intenzioni si accumulano.

    def percepisci(self, mondo, evento):
        self.credenze.update(pos=mondo.pos, porta_aperta=mondo.porta_aperta,
                             consegnato=mondo.consegnato)
        if evento == "ordine annullato":
            self.desideri.discard("consegna")

    def lascia_atteggiamenti(self):
        c, restanti = self.credenze, []
        for i in self.intenzioni:
            riuscita = not i["piano"] or c["consegnato"]
            impossibile = (not c["porta_aperta"] and c["pos"] < PORTA)
            desiderio_caduto = i["desiderio"] not in self.desideri
            if self.strategia == "cieco":
                lasciare = riuscita                    # solo a piano finito
            elif self.strategia == "singolo":
                lasciare = riuscita or impossibile     # ascolta le credenze
            else:
                lasciare = riuscita or impossibile or desiderio_caduto
            if not lasciare:
                restanti.append(i)
        self.intenzioni = restanti

Tre strategie di impegno

La sezione sulla teoria di Rao e Georgeff definisce tre tipi di agente, in base a quando un impegno viene lasciato. Le definizioni che seguono sono le loro, in parole mie.

• Cieco (blindly committed): non ammette cambiamenti di credenze o desideri che contrastino con i suoi impegni.
• Di mente unica (single-minded): ammette i cambiamenti di credenze e lascia gli impegni di conseguenza.
• Di mente aperta (open-minded): ammette cambiamenti sia di credenze sia di desideri, che possono costringerlo ad abbandonare gli impegni.

Le tre definizioni sono ordinate per quanto l'agente è disposto a ripensarsi: dal cieco, che non si ripensa, all'aperto, che si ripensa per ogni cambiamento. Il mio codice ne è un'operazionalizzazione dichiaratamente semplice: lascia_atteggiamenti fa lasciare l'intenzione al cieco solo quando il piano è finito, al singolo anche quando la porta chiusa la rende impossibile, all'aperto anche quando il desiderio non c'è più. Non è la semantica formale degli autori, che sta nelle relazioni di accessibilità sui mondi possibili. Una differenza voluta: il mio cieco aggiorna comunque le credenze, e semplicemente non le usa per decidere, mentre nella definizione degli autori è l'agente che non ammette cambiamenti in conflitto. Un'altra differenza è un difetto: il cieco considera «riuscita» un'intenzione il cui piano è esaurito, anche se il pacco non è stato consegnato.

Che cosa dice la misura

Prima delle uscite, la linea del tempo dello scenario con la porta, fatta a mano. L'agente parte in 0 con un piano di otto avanza e una posa. Ai passi 1-4 avanza fino al quadrato 4. All'istante 4 la porta si chiude, ma l'agente lo scopre solo a fine istante. Il singolo di mente unica lascia l'intenzione e attende dall'istante 5 all'8; la porta riapre all'istante 8 e a fine istante lo scopre, e dal 9 al 13 fa quattro avanza e una posa: consegna all'istante 13, con zero azioni fallite e quattro attese. Il cieco non sa niente: ai passi 5, 6 e 7 urta la porta, all'8 passa, al 9 prova a posare nel quadrato 5 e fallisce, poi rifà il piano dal 5 e arriva all'istante 13 con quattro azioni fallite. Le assert del blocco verificano proprio questi numeri.

Il quarto blocco contiene il ciclo di simulazione, i quattro scenari e il confronto. Il ciclo segue l'ordine dell'interprete degli autori: opzioni, deliberazione, aggiornamento delle intenzioni, esecuzione, nuovi eventi dal mondo, abbandono delle intenzioni riuscite o impossibili. Non c'è casualità: l'uscita riportata è identica in due esecuzioni consecutive.

def simula(strategia, eventi, istanti=20):
    mondo, ag = Mondo(eventi), AgenteBDI(strategia)
    esito = {"consegna_a": None, "fallite": 0, "dopo_annullo": 0, "attese": 0}
    annullato = False
    for t in range(1, istanti + 1):
        evento = mondo.applica_eventi(t)
        opzioni = ag.genera_opzioni()                  # opzioni dalla coda e dai desideri
        ag.aggiorna_intenzioni(ag.delibera(opzioni))
        azione = ag.esegui()
        ok = mondo.agisci(azione)
        if azione == "attendi":
            if "consegna" in ag.desideri and not mondo.consegnato:
                esito["attese"] += 1       # attesa con un desiderio ancora aperto
        elif not ok:
            esito["fallite"] += 1
        elif annullato:
            esito["dopo_annullo"] += 1
        if mondo.consegnato and esito["consegna_a"] is None:
            esito["consegna_a"] = t
        ag.percepisci(mondo, evento)                   # nuovi eventi esterni
        annullato = annullato or evento == "ordine annullato"
        ag.lascia_atteggiamenti()                      # intenzioni riuscite o impossibili
    return esito


SCENARI = {
    "nessun evento":    {},
    "porta chiude t4, apre t8": {4: "porta chiude", 8: "porta apre"},
    "porta chiude t4, non riapre": {4: "porta chiude"},
    "ordine annullato t4":      {4: "ordine annullato"},
}

if __name__ == "__main__":
    risultati = {}
    for nome, eventi in SCENARI.items():
        print(nome)
        for s in ("cieco", "singolo", "aperto"):
            r = simula(s, eventi)
            risultati[(nome, s)] = r
            print(f"  {s:<8} consegna a t={r['consegna_a']}  fallite={r['fallite']}  "
                  f"attese={r['attese']}  azioni dopo l'annullo={r['dopo_annullo']}")
    # Controllo: i valori ricavati a mano sulla linea del tempo (vedi testo)
    assert risultati[("nessun evento", "cieco")]["consegna_a"] == 9
    assert risultati[("porta chiude t4, apre t8", "singolo")] == \
        {"consegna_a": 13, "fallite": 0, "dopo_annullo": 0, "attese": 4}
    assert risultati[("porta chiude t4, apre t8", "cieco")]["fallite"] == 4
    assert risultati[("porta chiude t4, non riapre", "cieco")]["fallite"] == 5
    assert risultati[("porta chiude t4, non riapre", "singolo")] == \
        {"consegna_a": None, "fallite": 0, "dopo_annullo": 0, "attese": 16}
    assert risultati[("ordine annullato t4", "aperto")]["dopo_annullo"] == 0
    assert risultati[("ordine annullato t4", "singolo")]["dopo_annullo"] == 5
    print("controlli sulla linea del tempo a mano: ok")

# Output (due esecuzioni identiche):
# nessun evento
#   cieco    consegna a t=9  fallite=0  attese=0  azioni dopo l'annullo=0
#   singolo  consegna a t=9  fallite=0  attese=0  azioni dopo l'annullo=0
#   aperto   consegna a t=9  fallite=0  attese=0  azioni dopo l'annullo=0
# porta chiude t4, apre t8
#   cieco    consegna a t=13  fallite=4  attese=0  azioni dopo l'annullo=0
#   singolo  consegna a t=13  fallite=0  attese=4  azioni dopo l'annullo=0
#   aperto   consegna a t=13  fallite=0  attese=4  azioni dopo l'annullo=0
# porta chiude t4, non riapre
#   cieco    consegna a t=None  fallite=5  attese=11  azioni dopo l'annullo=0
#   singolo  consegna a t=None  fallite=0  attese=16  azioni dopo l'annullo=0
#   aperto   consegna a t=None  fallite=0  attese=16  azioni dopo l'annullo=0
# ordine annullato t4
#   cieco    consegna a t=9  fallite=0  attese=0  azioni dopo l'annullo=5
#   singolo  consegna a t=9  fallite=0  attese=0  azioni dopo l'annullo=5
#   aperto   consegna a t=None  fallite=0  attese=0  azioni dopo l'annullo=0
# controlli sulla linea del tempo a mano: ok

Leggi l'uscita per scenario. Senza eventi i tre agenti consegnano a 9 e coincidono: la strategia di impegno non conta quando nulla cambia. Con la porta che riapre all'istante 8 tutti consegnano a 13, ma il cieco ha 4 azioni fallite contro 0: la velocità è la stessa perché la porta riapre proprio quando il cieco la raggiunge, una coincidenza di questo scenario e non una regola. Se la porta non riapre, il cieco fa 5 azioni fallite e non consegna, mentre gli altri due attendono senza urtare nulla. Con l'ordine annullato all'istante 4, cieco e di mente unica fanno 5 azioni inutili e consegnano un pacco che nessuno aspetta; solo l'aperto si ferma, e il suo «consegna a t=None» è l'esito voluto.

Due cose da non leggere nell'uscita. La prima: le tre strategie non si ordinano per qualità. Il cieco è il più costoso quando l'ambiente cambia, ma risparmia i controlli quando non cambia niente: nel mio codice questo risparmio non si vede perché i controlli non hanno prezzo, e in un sistema reale ce l'hanno, che è esattamente il dilemma di cui parlano gli autori. La seconda: lo scenario dell'ordine annullato dice che il singolo non riconsidera i desideri. Che sia un difetto dipende dall'applicazione: se i desideri cambiano solo per errore, è una virtù.

Dove la mappa non regge, e quando non usare BDI

Il mio interprete ha un solo desiderio e un solo piano, costruito su misura: non ha nulla di ciò che renderebbe un sistema pratico flessibile. L'articolo di Rao e Georgeff presenta il proprio sistema pratico come una versione semplificata del Procedural Reasoning System, e sul versante dei linguaggi esiste AgentSpeak(L) di Rao (1996). Di quest'ultimo ho verificato nel registro Crossref il titolo, la sede (Lecture Notes in Computer Science, Agents Breaking Away), l'anno e le pagine 42-55; il testo non l'ho letto, quindi non ti descrivo la sua sintassi né come tratta i piani.

BDI è un'impalcatura che costa codice e decisioni: hai una coda di eventi, tre strutture e un criterio per abbandonare. Se il mondo non cambia durante l'esecuzione del piano, una sequenza di azioni calcolata una volta e un controllo finale bastano; se cambia in modo che non puoi controllare a ogni passo, serve almeno la domanda «questo impegno vale ancora?». La strategia da scegliere dipende da quanto spesso cambia il mondo rispetto a quanto costa controllare, e solo una misura nel tuo dominio lo dice.

Domande frequenti

Che differenza c'è fra un desiderio e un'intenzione?

Un desiderio è un obiettivo che l'agente può avere insieme ad altri, anche incompatibili; un'intenzione è l'obiettivo che l'agente ha scelto e a cui si è impegnato. Nel listato il desiderio è l'elemento di desideri, l'intenzione è una voce di intenzioni con il suo piano.

Una strategia di impegno è sempre meglio delle altre?

No, e l'esperimento lo mostra: con la porta che riapre i tre agenti consegnano allo stesso istante, con la porta chiusa per sempre il cieco spreca cinque azioni, con l'ordine annullato solo l'agente di mente aperta si ferma. Dipende da che cosa cambia nel tuo ambiente.

Per usare BDI serve un modello di intelligenza artificiale?

No. L'interprete di questo articolo è Python senza librerie e senza modelli chiamati. L'architettura descrive come decidere e quando ripensarsi, non con quale tecnica generare i piani.

Che cosa sai fare adesso

Sai dire a che cosa servono i tre stati mentali e qual è il dilemma che rende necessaria l'intenzione. Sai scrivere un interprete BDI minimo con il ciclo degli autori e vedere dove cade la scelta della strategia di impegno. E sai leggere le sue uscite senza forzarle: la strategia non si sceglie per qualità, ma in funzione di quanto spesso il mondo cambia. L'articolo precedente ha definito l'agente, il successivo porta il comportamento di un agente su una piattaforma, e l'indice della serie elenca il resto.