Battaglia per l'Energia e Leader Election

In questo paragrafo sono esposti i due scenari applicativi che verranno analizzati all'interno della tesi. Si aggiungono le seguenti caratteristiche a quelle già viste nei punti precedenti:

• Inizio del conitto

 BpE: il conitto nasce nel momento in cui due o più veicoli richiedono l'accesso al punto di carica. Per il singolo agente, l'algoritmo inizia nel momento in cui si sta dirigendo verso il Target e rileva la presenza di uno o più avversari all'interno di una circonferenza di raggio noto attorno ad esso. Non è prevista nessuna fase di Inizializzazione;

 LE: il conitto nasce quando più agenti convengono di dover scegliere un Leader tra di loro. La fase di inizializzazione prevede che tutti gli agenti si dispongano a uguale distanza da un punto centrale, che sarà l'obbiettivo da raggiungere. Per fare ciò, si sfrutta un algoritmo di Rendez-Vous per denire il target, seguita da una fase in cui i veicoli si dispongono nello spazio circostante, lungo una circonferenza attorno a questo punto. Nel momento in cui gli agenti si posizionano su questa linea, l'algoritmo può passare alla seconda fase.

• priorità di accesso:

 BpE: la priorità di accesso è divisa in due parti, una pubblica e l'altra privata, come prevede l'algoritmo. La prima è costituita dalla Distanza dal Target, l'altra è l'Urgenza dovuta al livello interno di batteria. Più vicino al target e meno carica interna, più si ha diritto di accedere alla risorsa. Si propone, quindi, la seguente priorità di accesso

P a = Ea0+ Da0 (2.4)

dove si indica con Ea0 la dierenza tra il massimo di energia all'interno della batteria e il

livello al momento di inizio del conitto, ottenendo così una misura dell'energia residua, e Da0= RC − DT0, cioè una misura di quanto si è vicini al target al momento iniziale, in cui

RCè il raggio della circonferenza attorno all'obiettivo nel quale avviene il conitto e DT0è la

distanza dal target nel momento iniziale. Entrambi questi valori si considerano discreti. Nel primo caso si può usare un valore minimo di livello di energia di funzionamento del veicolo e considerare Ea0 multiplo di tale valore. Per la distanza si può suddividere il valore nel

numero di passi da percorrere per arrivare al target.

 LE: la priorità di accesso alla risorsa è, in questo caso, costituita solo da una parte privata. La distanza dal target non solo è nota, ma è anche un valore comune tra tutti gli agenti, in quanto si è richiesto che questi si posizionino lungo una circonferenza. La priorità privata è costituita da un valore che denisce l'importanza dell'agente, quale può essere il codice identicativo. Si propone quindi

dove, anche in questo caso, si richiede che il valore sia discretizzato.

• Acquisizione delle informazioni necessarie dal mondo circostante: in entrambi i casi sarà possibile acquisire le informazioni sulla distanze tra gli agenti e il Target tramite sensori di prossimità, di distanza o di movimento caricati su di essi.

In base alle priorità denite saranno strutturati i valori dei guadagni all'interno dei giochi e sarà in base a queste funzioni che verranno deniti i successi e i fallimenti degli algoritmi.

2.5.2.1 Algoritmo e dinamica degli agenti

In questa sezione saranno arontate alcune problematiche dell'algoritmo, relative alla traduzione in uno scenario reale di alcune grandezze riguardanti la dinamica dei veicoli in gioco, come velocità, unità di spazio e di tempo.

Con il termine Passo si denisce qui il lasso di tempo che serve al singolo agente per attuare una azione della strategia pianicata. Lo spazio percorso nell'unità di tempo verrà indicato come Spazio percorso in un passo. Tale grandezza è l'unità di distanza del percorso che deve compiere l'agente per arrivare al traguardo. Noto questo valore si potrà identicare una circonferenza attorno al target, con raggio pari ad un multiplo di questa unità. Tutti gli agenti all'interno di questa circonferenza saranno considerati coinvolti nel conitto. Nel caso in cui la dinamica del veicolo preveda di seguire un percorso più lungo (ad esempio nel caso di unicicli), la sua traiettoria sarà comunque divisa in parti di questa dimensione, quindi dovrà percorrere più segmenti e non lo stesso numero di segmenti di dimensione maggiore. Si può denire un valore minimo per lo Spazio percorso in un passo, in quanto i sensori a bordo degli agenti hanno dei valori minimi di risoluzione. Un movimento di entità inferiore a questi non è percepito.

Indicare i criteri sulla denizione del Passo è più complesso, in quanto, mentre questo viene eettuato, l'agente deve anche cercare di rilevare cosa sta facendo l'avversario, cioè conoscere la posizione di questi nel tempo, perché le azioni si suppongono (e devono avvenire) simultaneamente. Questo aspetto introduce due vincoli:

• L'acquisizione della posizione degli avversari avviene in tempo discreto, a causa delle caratteristiche dei sensori, ma anche perchè in alcuni scenari la velocità dei segnali usati per il rilevamento delle posizioni dipende in maniera improtante dalle caratteristiche del mezzo attraverso il quale viaggia, come nel caso di agenti sottomarini che sfruttano le onde sonore del Sonar per percerpire il mondo che lo circonda. Se non è possibile avere un valore costante della velocità del segnale nell'ambiente, si può usare il valore di tempo maggiore in maniera cautelativa. Sapere anche i tempi necessari per l'acquisizione delle posizioni non signica per forza aumentare le informazioni richieste agli agenti a causa dell'algoritmo, in quanto spesso sono già note.

• Gli agenti si spostano contemporaneamente, di conseguenza, in base al punto precedente, aspettare di vedere l'avversario eettuare tutta l'azione per capire se questo ha deciso di lasciare o di andare comporterebbe o un aumento del Passo, per aspettare l'arrivo (ma questo comporterebbe anche che l'altro agente dovrebbe fare lo stesso, aumentando senza limiti il tempo di arrivo), o dover analizzare l'azione dell'avversario in ritardo (al più durante l'azione successiva). Questo però farebbe sì che il Learning venga sfasato rispetto alla pianicazione, in quanto si ha il bisogno di tutta la strategia avversaria per poterla fare.

In base a questi due punti, è necessario imporre che gli agenti debbano decifrare l'azione dell'avversario in base ad una parte della traiettoria di questi durante il Passo. Indicando con X lo Spazio percorso in un passo, supposto noto, e con V la velocità degli agenti, è possibile dire quindi:

X/V > αX/V + t

Dove con α viene indicata la porzione del Passo che viene considerata come suciente per intuire l'azione di un avversario e con t una costante di tempo legata alla trasmissione dati. In essa si considerano sia i vincoli legati al mezzo, sia quelli legati all'acquisizione dati, che avviene a istanti discreti e non continui. Da questa relazione dei tempi si può ottenere.

X > V t/(1 − α) (2.6) Se il tempo di trasmissione dati è tale per cui questo valore è maggiore della risoluzione dati del sensore, sarà questo il limite inferiore dello Spazio.

In conclusione, è possibile dire che:

• la velocità deve essere la minima consentita dal mezzo e dall'ambiente;

• lo Spazio percorso in un passo è il valore più grande tra la risoluzione del sensore e precedente- mente indicata;

• il diametro della circonferenza attorno al target sarà quindi un multiplo ssato dello Spazio percorso in un passo.

• il Passo si ottiene quindi dal rapporto tra spazio e velocità.

In questo modo, supponendo agenti simili in simili condizioni, essi saranno capaci di denire in egual modo tutte le grandezze utili all'algoritmo in maniera autonoma. Nel caso di veicoli con range di velocità dierenti, è possibile richiedere un consenso tra gli agenti in un momento opportuno o implementare il dato di velocità e di spazio da usare in fase di preparazione dei robot.