Alberi di ricerca AND-OR

Gli alberi di ricerca AND-OR sono una rappresentazione delle sequenze decisionali. Gli alberi di ricerca AND-OR sono conosciuti anche come alberi di decisione ( alberi decisionali ) e, grazie alla loro semplicità di implementazione, sono utilizzati in molte applicazioni pratiche nell'informatica, nei sistemi esperti e nell'intelligenza artificiale. In un ambiente non deterministico l'agente razionale non è in grado di prevedere con certezza l'esito delle proprie azioni. In questi casi l'agente deve necessariamente rilevare lo stato dell'ambiente esterno sia prima che dopo l'azione La prima rilevazione ( percezione ex-ante ) è utile per elaborare la decisione ossia l'azione da intraprendere. La seconda rilevazione ( percezione ex-post ) è, invece, utile per verificare gli effetti dell'azione intrapresa sull'ambiente esterno.

AMBIENTE NON DETERMINISTICO

Ad esempio, un sistema di guida automatica non è in grado di determinare con precisione lo spostamento del veicolo soltanto misurando il tempo, l'angolo di spostamento del volante e la velocità del veicolo. Esistono altri parametri esogeni che possono influenzare notevolmente il movimento effettivo del veicolo ( es. vento laterale, pendenza manto stradale, buca improvvisa ecc. ). In questo caso l'analisi dei feedback è di fondamentale importanza per determinare una sequenza decisionale corretta. I tempi di elaborazione e di analisi continua dell'ambiente potrebbero, tuttavia, rallentare notevolmente l'operato dell'agente razionale. Per ridurre i tempi di elaborazione è possibile ricorrere a degli appositi schemi decisionali, detti alberi decisionali o alberi di ricerca AND-OR, che permettono di analizzare alcuni aspetti contingenti dell'ambiente esterno al fine di rendere quasi istantanea la decisione finale ( decisione "meccanica" ). Un semplice esempio di albero AND-OR è il seguente:

ALBERO DI RICERCA AND-OR

Nell'esempio precedente le condizioni OR sono le contingenze orizzontali ( es. corsia di sorpasso libera o ( OR ) occupata? veicolo al centro della corsia di sorpasso ( OR ) oppure no? Mentre le condizioni AND sono le contingenze verticali. Ad esempio, accelera se la corsia di sorpasso è libera e ( AND ) dopo aver portato il veicolo al centro della corsia di sorpasso. Ovviamente si tratta di uno schema semplificato e banale per rendere l'idea. Per rendere veramente efficace l'albero decisionale sarebbe opportuno aggiungere altri controlli prima di eseguire l'accelerazione: controllare se il veicolo che precede ha iniziato anch'esso l'operazione di sorpasso, se la strada dinnanzi al veicolo è libera, se la strada sta per curvare o se è prossima a un incrocio, ecc. Gli alberi di ricerca AND-OR si presentano solitamente come delle routine o delle sotto-routine ( subroutine ). Le strategie di contingenza delineate negli alberi di ricerca AND-OR possono essere rigide o flessibili.

  • Strategia rigida. Si parla di strategie rigide quando le strategie sono programmate nel codice dell'agente razionale in fase di progettazione e non sono modificabili dal software. Le strategie rigide sono utilizzate nei videogiochi, nei prodotti dell'elettronica di consumo quali i robot per la pulizia della casa, ecc. Essendo basata soltanto sulla programmazione iniziale l'efficacia della strategia rigida è fortemente dipendente alla qualità del lavoro svolto nella fase di progettazione.
  • Strategia flessibile. Si parla di strategie flessibili quando l'agente razionale può autonomamente modificare o creare nuove strategie sulla base dell'esperienza maturata. Le strategie flessibili sono alla base dei sistemi esperti e delle applicazioni più avanzate di intelligenza artificiale. Essendo delle regole e delle strategie modificabili via software, nel corso del proprio lavoro l'agente razionale può anche correggere le eventuali sviste e gli errori compiuti dai progettisti nella programmazione iniziale.

Rapidità delle risposte. Il principale vantaggio dell'albero di ricerca AND-OR è quello di fornire all'agente razionale delle risposte rapide in base a specifiche contingenze senza dover elaborare completamente lo stato generale dell'ambiente esterno. In tali circostanze lo studio completo dell'ambiente per individuare una sequenza di azioni potrebbe essere inefficace e inefficiente. È invece preferibile adottare una strategia ossia un piano di contingenza sulla base delle informazioni percepite dall'esterno ( feedback ) e interpretate seguendo un determinato schema di riferimento. Gli alberi di ricerca AND-OR sono particolarmente utile per fornire delle risposte rapide alle contingenze più frequenti e alle situazioni di impasse dell'agente razionale ( es. loop ).

Schemi predeterminati. Gli algoritmi decisionali non sono veri e propri sistemi intelligenti. Si tratta perlopiu di schemi predeterminati da utilizzare in particolari situazioni. Inoltre, sono fortemente dipendenti dalla capacità del progettista di prevedere tutte le possibili situazioni di contingenza e sulla conoscenza delle migliori azioni possibili. Ciò causa un forte allungamento dei tempi della progettazione iniziale della base di conoscenza e un elevato rischio di presenza di errori e omissioni. Sono particolarmente interessanti, invece, quando è lo stesso agente razionale a scrivere gli alberi decisionali sulla base dell'esperienza passata e dell'analisi dei feedback.

Cammino ciclico. Un albero di ricerca AND-OR è soggetto al rischio dei cammini ciclici ( loop ). Il cammino ciclico si verifica quando uno stato corrente è uguale a uno degli stati precedenti del cammino. In tali casi l'agente razionale cade in un ragionamento ciclico che, molto spesso, può anche diventare infinito. Per evitare questo rischio è consigliabile inserire in un albero di ricerca AND-OR una funzione di controllo che eviti la ripetizione continua degli stati in un medesimo cammino. La funzione di controllo può evitare qualsiasi ripetizione degli stati oppure accettarli soltanto entro una soglia di tolleranza massima di tentativi, oltre la quale far scattare una routine di contingenza ( es. soluzione ciclica ) per uscire dall'impasse.

https://www.okpedia.it/alberi_di_ricerca_and_or




Agente razionale