Ricerca di un bersaglio immobile o mobile su una rete

1. Introduzione 1.1 Introduzione In tale capitolo iniziale si presenta la dissertazione medesima, introducendone i suoi argomenti, 
delineando i suoi contenuti e chiarendo altresì le ragioni della sua stesura.
Si considera ora in dettaglio ciò che viene trattato nei prossimi paragrafi: 
Nel secondo paragrafo "Argomento della Dissertazione", dopo aver esposto le motivazioni della 
stesura, si presentano il soggetto dell'elaborato, i giochi di ricerca, ed il loro ambito di studio.
Nel terzo paragrafo “ Analisi della Letteratura ”, si espone una breve bibliografia sull'argomento 
della dissertazione, accennando lo sviluppo assiomatico; si forniscono inoltre alcuni campi 
applicativi.
Nel quarto paragrafo " Scopo e Articolazione della Dissertazione", si trattano le f inalità previste 
dell'elaborato e si prende in esame la sua articolazione, analizzando in dettaglio i distinti capitoli 
ed i loro contenuti,  tracciando in tal modo un percorso logico di svolgimento.
Nell'ultimo paragrafo “ Conclusioni ”, mediante considerazioni ed osservazioni si esamina il 
capitolo terminato e si espone la  metodica con cui prosegue la dissertazione .
1.2 Argomento della Dissertazione Nel seguito, dopo aver motivato la stesura dell'elaborato, si espone in modo sintetico la materia in 
oggetto dei capitoli seguenti. 
Le ragioni della stesura della disertazione sono di carattere puramente personali e riguardano il 
crescente interesse nell'approfondimento della materia trattata dalla teoria dei giochi in un differente 
contesto. Dopo aver appurato lo sviluppo delle recenti ricerche, la consapevolezza della vasta 
applicabilità e adattabilità scaturita dall'integrazione di tale teoria con un insieme di riferimento 
come il grafo, ha stimolato e motivato ancor più l'analisi e l'esposizione. 
Si considera che nelle iniziali analisi della Teoria della Ricerca si studiano problemi in cui viene 
formalizzata una situazione in cui un cercatore desidera minimizzare il tempo richiesto per trovare un 
oggetto nascosto (chiamato nascosto, ricercato, fuggitivo o semplicemente “bersaglio”). In genere il 
cercatore sceglie un percorso nello “spazio di ricerca” e trova il bersaglio quando è sufficientemente 
vicino ad esso. Tradizionalmente, il bersaglio si assume non avere motivi personali riguardanti il tempo 
1
di cattura; è semplicemente stazionario e nascosto in accordo ad una nota distribuzione (es. petrolio), o 
il suo movimento è determinato stocasticamente mediante regole note (es. volpe nella foresta).
Risultati recenti assumono, al contrario, che il “bersaglio” è un giocatore indipendente di eguale status 
del cercatore, che si preoccupa quindi in maniera contrastante del tempo di cattura.
Per questo nella letteratura attualmente si distinguono due diversi atteggiamenti del bersaglio: si 
considera il gioco a somma nulla che risulta quando non vuole essere trovato; oppure si valuta 
l'obiettivo opposto, cioè che voglia essere trovato. In quest'ultimo caso il cercatore ed il nascosto 
possono essere pensati come una squadra di agenti (giocatore I e giocatore II) con identici obiettivi, ed 
il problema di coordinamento che affrontano congiuntamente è chiamato Problema di Ricerca di 
Rendez-vous. In un gioco di ricerca il nascosto desidera massimizzare il tempo di cattura, laddove in un 
Problema di Rendez-vous, è suo obiettivo minimizzarlo. Ogni problema di ricerca così concepito è 
tuttavia presentato come un gioco a due persone a somma nulla.
1.3Analisi della Letteratura Nel paragrafo in esame si espone una concisa bibliografia, presentando una breve e sintetica 
relazione sugli studi riguardanti l'ambito della dissertazione stessa , accennandone in tal modo lo 
sviluppo assiomatico.
I giochi di ricerca hanno origine in parte dall'esempio “La Principessa e il Mostro”, proposto in un 
testo sui Giochi Differenziali.
1
 Nelle successive analisi tuttavia, lo stesso modello viene rielaborato 
con un approccio del tutto differente ed innovativo, nel momento in cui vi si individuano elementi 
della preesistente T eoria di Ricerca ( Search Theory) e si utilizzano misure di probabilità 
assegnandogli un ruolo predominante. 
I Giochi Differenziali sono modelli matematici di sistemi dinamici costituiti da equazioni 
differenziali e rappresentanti una situazione di inseguimento in uno spazio di riferimento continuo, 
tra due giocatori con distinti parametri quali la posizione iniziale, la velocità e il raggio di sterzata. 
L'obiettivo è analizzare e trovare la funzione della traiettoria ottimale per la cattura o la fuga del 
giocatore inseguito. Il principale sistema di risoluzione è basato sul metodo Jacobi-Hamilton 2
.
Per quanto riguarda la Teoria di Ricerca, si rileva che essa ha origine principalmente per conseguire 
la maniera più efficiente ed efficace per condurre operazioni militari di individuazione del nemico o 
di alleati dispersi
3
. In tale ambito si studia quindi il modo di trovare la distribuzione di probabilità 
[1] Isaacs R., Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and 
Optimization, 1965, John Wiley & Sons, New  York. 
[2] Friedman A., Differential Games, 1974 , American Mathematical Society, Rhode Island. 
[3] Koopman B. O., Search and screening, 1946, Operations Evaluation Group Rep. no. 56, Center for Naval 
  2
ottimale nella ricerca
4
.
Nella letteratura si è affrontata inizialmente l'analisi di un gioco di ricerca con nascosti mobili
5
, in 
seguito si sono determinate le soluzioni su reti e regioni nello spazio euclideo 6
. Infine si è formulato 
un riordinamento organico di tali concetti
7
, stimolando lo sviluppo di ulteriori ricerche, incluse 
applicazioni di informatica, economia e biologia.
La maggior parte delle analisi
8
 nella fase di transizione tuttavia concerne ancora aspetti di traiettorie 
di ricerca ottimale, tipici dei giochi differenziali, con un approccio molto differente dall'attuale 
evoluzione dei giochi di ricerca, costituente l'oggetto della dissertazione . In un articolo 9
 viene 
mostrato infatti come la determinazione di tali traiettorie dovesse essere esaminata più 
approfonditamente, mentre sono congiuntamente in fase di sviluppo distinte casistiche
10
. 
Benché solo in ulteriori studi si introducano degli aspetti teorici di gioco 11
, gran parte dei concetti 
fondamentali vengono presentati con una struttura più completa e formale
12
 ed è su questi ultimi 
contributi che ci si basa principalmente nel prosieguo.
Dal punto di vista applicativo i giochi di ricerca, come d'altronde il loro insieme di riferimento, in 
questo caso i grafi, possono rappresentare strutture onnipresenti. I grafi orientati sono anche 
utilizzati per rappresentare le macchine a stati finiti e molti altri formalismi, come ad esempio 
diagrammi di flusso, catene di Markov, schemi entità-relazione, reti di Petri. Molti problemi di 
interesse pratico possono essere formulati come questioni relative a grafi, per esempio: cartine 
stradali, planimetrie, progetti tecnici, circuiti elettrici, reti informatiche, rappresentazioni economiche, 
finanziarie e sociali. Infatti è comune l'applicazione dei modelli: 
– Nell'analisi dell'erogazione di energia e servizi in genere, nella gestione del traffico, nei 
Analysis, Rosslyn, Virginia.
[4] Stone L. D., Theory of Optimal Search, 1989 2n d ed. Operations Research Society of America, Arlington, VA.
[5] Alpern S., The search game with mobile hider on the circle, In Differential Games and Control Theory (E. O 
Roxin, P. T. Liu, and R. L. Sternberg, eds), 1974, Dekker, New York, pp. 181–200.
Foreman J. G., The princess and the monster on the circle. In Differential Games and Control Theory (E. O. 
Roxin, P. T. Liu, and R. L. Sternberg, eds), 1974. Dekker, New York, pp. 231–240.
Zelikin M. 1., On a differential game with incomplete information. 1972, Soviet Math. Dokl. 13, pp. 228–231.
[6] Gal S., Search games with mobile and immobile hide r. 1979, SIAM J. Control Optim. 17, pp. 99–122.
[7] Gal S., Search Games. 1980, Ac ademic Press, New York.
[8] Dobbie, J. M., A survey of search theory. 1968, Oper. Res. 16, pp. 525–537.
[9] Benkoski, S., Monticino M. e Weisinger J., A survey of the search theory literature. 1991, Naval Res. Logist. 
38,  pp. 469– 494.
[10] Ahlswede R. e Wegener I., Search Problems. 1987, Wiley.
Haley B. K. e Stone L. D, Search Theory and Applications, eds 1980, Plenum Press, New York.
Iida K., Studies in the Optimal Search Plan. Lect. Notes Statist. 1992, (J. Berger et al., eds) 70, Springer-Verlag.
Chudnovsky D. V. e Cudnovsky G. V., Search Theory: Some Recent Developments. eds 1989, Marcel Dekker, 
New York.
[11] Ruckle W. H., Geometric Games and Their Applications. 1983, Pitman, Boston.
Ruckle W. H., Pursuit on a cyclic graph. 1983, Int. J. Game Theory 10, pp. 91–99.
[12] Garnaev A. Y., Search Games and Other Applications of Game Theory. 2000, Springer-Verlag, Berlin.
Gal e Alpern, The theory of search games and rendezvous, 2003, Kluwer Academic Publishers.
3
rifornimenti di materiale per stabilire percorsi ottimali con obiettivi prefissati.
– In informatica, nello studio di reti locali e in siti web, per localizzare intrusi o determinati 
software. 
– Nel campo militare o più specificatamente in quello delle forze dell'ordine per intercettare 
strutture avversarie o alleate.
– In sociologia per individuare in una rete sociale dei partecipanti o esplorare i meccanismi di 
diffusione di un determinato fenomeno. 
1.4 Scopo e Articolazione della Dissertazione Nel presente paragrafo si espongono le f inalità della dissertazione medesima e si prende in 
esame la sua articolazione, delineando i distinti capitoli ed i loro contenuti, per tracciare in tal 
modo un percorso logico di svolgimento.
L'obiettivo dell'intera trattazione è di presentare in modo sintetico ed esauriente la Teoria dei Giochi 
di Ricerca, come accennato nel precedente paragrafo, basandosi su testi contenenti risultati recenti e 
sufficientemente completi. 
I contenuti nel dettaglio dei distinti capitoli, costituenti la dissertazione, sono i seguenti:
Nel secondo capitolo “Caratterizzazione dei Giochi di Ricerca”, s i considerano degli spazi di 
ricerca che sono sottoinsiemi chiusi e vincolati di uno spazio euclideo. Sono di solito una regione 
compatta in uno spazio euclideo con due o più dimensioni, oppure una rete (grafo).
Ogni arco nella rete avrà una data lunghezza ed una funzione di distanza associata definita su esso. Si 
definiscono quindi le quantità fondamentali per tali formalizzazioni, quali la distanza tra 
qualsiasi due punti, le traiettorie, il tempo atteso di cattura, il tasso di scoperta, le strategie e il 
payoff.
Per evitare complicazioni non si considerano i giochi di ricerca con nascosto mobile o immobile in 
regioni compatte multidimensionali, ma solo nei grafi.
Nel terzo capitolo “Ricerca di un Nascosto Immobile”, s i definisce una rete Euleriana e la strategia 
uniforme, definita come scelta casuale del punto di occultamento. Si forniscono i valori corrispondenti. 
Si utilizza la programmazione dinamica per trovare traiettorie di ricerca con reazione ottimale, 
mediante  lo schema numerico di ottimizzazione, basato su un principio ricorsivo, che si applica in 
genere ai problemi di ricerca.
13
Nel quarto capitolo “Ricerca di un Nascosto Mobile”, si considera l 'interesse dei giochi di ricerca 
[13] Bellman R., An optimal search problem. 1963 , SIAM Rev. 5, 274.
  4
con un nascosto mobile generato dal modello di gioco “La Principessa e il Mostro”. In questo gioco, il 
Mostro cerca la Principessa in una stanza completamente buia, entrambi coscienti del suo confine. La 
cattura avviene quando la distanza tra il Mostro e la Principessa è minore o uguale ad una data quantità. 
Un passo intermedio è risolvere il gioco di ricerca con un nascosto mobile in una rete consistente di k 
archi che connettono due punti. Si presentano, nell'iniziale formalizzazione, le strategie del cercatore e 
del nascosto; si osserva quindi il vantaggio delle strategie miste rispetto a quelle pure; si risolve 
successivamente la ricerca su k archi di un grafo; infine si trova il vincolo superiore del valore 
caratteristico del gioco per la ricerca nelle reti.
Nel quinto capitolo “ Estensioni ed Applicazioni ”, si esaminano differenti argomentazioni di 
complemento:
- Si considera l'eventualità che il cercatore possa attendere, con determinata distribuzione di probabilità, 
il nascosto mobile in un dato nodo tendendogli una sorta di agguato, definendo tali strategie come 
erratiche.
- Si esaminano gli spazi di ricerca non omogenei, in cui si permette che la velocità massima del 
cercatore dipenda dalla sua posizione ed il raggio di individuazione dipenda dalla posizione del 
nascosto.
- Infine si tratta il problema della ricerca di un nascosto immobile in una rete finita connessa, 
deprivandolo della vista dell'intera rete e permettendogli invece di conoscere, e registrare, solo quella 
parte che ha già attraversato. Il punto iniziale è noto come entrata e la posizione del nascosto è nota 
come uscita. Una rete siffatta è definita come labirinto. Si presenta l'algoritmo casualizzato 14
 per 
minimizzare il tempo atteso per il cercatore di trovare l'uscita nel peggior caso, in confronto alla scelta 
della rete e il posizionamento della sua entrata e uscita. 
Si considerano distinti modelli applicativi:
- Il nascosto sceglie un punto di un intervallo ed il cercatore tenta di avvicinarsi ad esso mediante una 
sequenza di supposizioni ricevendo come risposta se è troppo alto o troppo basso rispetto al valore da 
individuare.
- Un infiltrato entra in un insieme attraverso un punto noto nel suo confine e si muove al suo interno. Il 
cercatore ha l'obiettivo di difendere una “zona sensibile”, catturandolo prima che la raggiunga. 
- Un oggetto stazionario è nascosto in una locazione etichettata, in cui è possibile accumulare delle 
risorse.
Nel sesto capitol o “Algoritmi Risolutivi”, si presentano delle classiche procedure per determinare la 
soluzione nel caso di un nascosto immobile, tra cui l'algoritmo di Floyd, di Dijkstra e di Fleury. Inoltre 
[14] Gal S., Anderson E.J., Search in a maze. 1990, Probab. Eng. Inf. Sci. 4, pp. 311-318.
5
si trattano algoritmi di nuovo sviluppo per il caso di un nascosto mobile basati uno sul tipo 
coordinazione necessaria ai cercatori per diminuire il tempo di ricerca e l'altro in considerazione della 
visibilità dai singoli nodi per determinare i percorsi ottimali di cattura.
Si termina la dissertazione mediante il capitolo delle “Conclusioni”, in cui si presentano delle 
considerazioni finali e dei suggerimenti per percorsi futuri di ricerca.   
1.5 Conclusioni In definitiva, con il presente capitolo introduttivo si ritiene di aver fornito concetti utili per 
rendere chiaro l'intento espositivo nella trattazione e il succesivo sviluppo della dissertazione.
Si sono precisate difatti le origini, le applicazioni ed i diversi ambiti della teoria matematica dei 
giochi di ricerca, poichè sarà questa la prospettiva da cui si analizzeranno i giochi nei seguenti 
capitoli. Si è infine presentata la struttura dettagliata dell'elaborato, fornendone un sommario 
netto e  completo.
In virtù di ciò, nel prossimo capitolo si introduce l'impianto formale fondamentale, mediante la 
trattazione di definizioni, assunzioni, teoremi e risultati alla base della Teoria dei Giochi di Ricerca, per 
essere in grado nel prosieguo di affrontare i formalismi assiomatici e definitori dei modelli di gioco in 
contesti specifici. 
  6