[Algoritmi] Problema sui sensori sismici

Messaggioda gimasci99 » 28/10/2019, 23:29

Ciao a tutti.
Ho cercato qualcosa di simile ovunque ma non ho trovato nulla. Spero in una vostra dritta.
Il problema è il seguente:

Ho un campo militare quadrato di lato 10Km. L'origine è in basso a sinistra come per un piano cartesiano.
Sul suddetto campo sono presenti N sensori sismici S1, S2, ..., Sn
Ogni sensore sismico Si è caratterizzato dalle sue coordinate (xi,yi) sul suddetto campo.
Nell'istante t0 una bomba cade sul campo generando un'esplosione che a sua volta viene registrata dai sensori come le onde/vibrazioni di un sisma.
Quindi ogni sensore Si registra in un'istante ti>t0 il passaggio di quest'onda.
Considerando la velocità di propagazione delle vibrazioni/onde generate dall'esplosione uguale in tutte le direzioni e costante determinare il punto di impatto (x0,y0) e l'istante t0 dell'impatto della bomba.

Facciamo un esempio con 4 sensori ma possono essere di più:
il sensore S1 ha coordinate x1=303[m], y1=6874[m] e registra le vibrazioni nell'istante t1=69.957781641
il sensore S2 ha coordinate x2=1772[m], y2=9314[m] e registra le vibrazioni nell'istante t2=73.479878657
il sensore S3 ha coordinate x3=7946[m], y3=6024[m] e registra le vibrazioni nell'istante t3=78.055985299
il sensore S4 ha coordinate x4=8812[m], y4=157[m] e registra le vibrazioni nell'istante t4=82.230678694
Determinare il punto (x0,y0) e l'istante t0 di impatto della bomba considerando la velocità di propagazione, anch'essa incognita, costante e uguale in tutte le direzioni.

Voi come impostereste l'algoritmo per risolvere questo problema?
Ogni suggerimento è ben accetto.
Grazie,
Giovanni.
gimasci99
Starting Member
Starting Member
 
Messaggio: 12 di 26
Iscritto il: 13/09/2019, 14:27

Re: [Algoritmi] Problema sui sensori sismici

Messaggioda axpgn » 28/10/2019, 23:47

Boh, a me sembra banale ma evidentemente mi sbaglio … :-D

Hai tre incognite quindi ti bastano tre equazioni qualsiasi tra quelle …
Da quel che capisco ogni segnale rilevato si muove di moto rettilineo uniforme quindi $x_i-x_0=v(t_i-t_0)$ (e lo stesso per l'altra dimensione, la $y$) … tre di queste sono sufficienti … in teoria :-D ... perché dando in pasto a Wolfram queste equazioni con i tuoi numeri, mi dice che non ci sono soluzioni … :?

Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14387 di 40641
Iscritto il: 20/11/2013, 22:03

Re: [Algoritmi] Problema sui sensori sismici

Messaggioda axpgn » 29/10/2019, 00:05

Effettivamente basta fare due semplici conti (sottrarre la prima dalla seconda e dalla terza) per trovare due velocità completamente diverse (una doppia dell'altra).
Quindi il mio modello è troppo semplificato per il problema :D

Va modificato almeno così $x_i-x_0=v_(x_i)(t_i-t_0)$ cioè la velocità dipende dall'angolo il quale dipende da $(y_i-y_0)/(x_i-x_0)$
Questa è la tangente dal quale ricavare l'angolo per ogni sensore rispetto alla bomba … è un po' più complicato :-D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14390 di 40641
Iscritto il: 20/11/2013, 22:03

Re: [Algoritmi] Problema sui sensori sismici

Messaggioda apatriarca » 29/10/2019, 02:52

Sia \(B\) la posizione della bomba, \(t\) il tempo dell'esplosione, \(v\) la velocità di propagazione dell´onda, \(S_i\) le posizioni dei sensori e \(t_i\) i tempi di arrivo del segnale. Per ogni sensore hai
\[ v\,(t_i - t_B) = ||S_i - B|| \]
È un sistema di equazioni non lineare. Puoi ad esempio usare il metodo di Newton per risolverlo. In alternativa, puoi anche pensare di minimizzare il valore assoluto della differenza tra i due valori e usare un metodo di ottimizzazione.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5305 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Problema sui sensori sismici

Messaggioda gimasci99 » 29/10/2019, 07:51

apatriarca ha scritto:Sia \(B\) la posizione della bomba, \(t\) il tempo dell'esplosione, \(v\) la velocità di propagazione dell´onda, \(S_i\) le posizioni dei sensori e \(t_i\) i tempi di arrivo del segnale. Per ogni sensore hai
\[ v\,(t_i - t_B) = ||S_i - B|| \]
È un sistema di equazioni non lineare. Puoi ad esempio usare il metodo di Newton per risolverlo. In alternativa, puoi anche pensare di minimizzare il valore assoluto della differenza tra i due valori e usare un metodo di ottimizzazione.


Ciao apatriarca.
Il tuo suggerimento è l'approccio che ho effettivamente messo in piedi come algoritmo. Non ho detto nulla prima per non influenzare minimamente i suggerimenti. In pratica dal momento che la velocità di propagazione è la stessa in tutte le direzioni e che è costante devo avere che Vi=Vj per ogni i,j da cui f(x,ty,t)=|V1-V2|+|V1-V3|+|V1-V4|+|V2-V3|+|V2-V4|+|V3-V4|=0. Questa è in pratica la funzione obiettivo da minimizzare dove le velocità sono calcolabili come dici tu ossia Vi=sqrt[(xi-x)^2+(yi-y)^2]/(ti-t). Quindi quando trovo lo zero al variare di x,y,t ho trovato la soluzione.

L'algoritmo che ho messo in piedi funziona nella maggior parte dei casi ma nel caso in cui considero:
Si_|__x_|__y_|____t____
s1 |0640|7585|102.00265
s2 |6350|0369|102.65047
s3 |7244|3422|099.25444
s4 |5967|5190|096.27996

l'algoritmo che ho messo in piedi per minimizzare la funziona obiettivo fallisce miseramente perchè va a finire in un punto di minimo relativo anzichè quello assoluto che è la soluzione.

L'algoritmo messo in piedi ragiona così:
- criterio di stop err(f(x,y,t))<10^-3
- suddivido il campo in sottocampi di 100x100m
- per ognuno dei sottocampi di 100x100m prendo come punto iniziale quello al centro
- come istante iniziale il minimo tra i tempi dei sensori tanto quello di impatto sarà necessariamente inferiore
- considero il sottocampo 100x100m che mi da il valore minimo della funzione obiettivo e lo suddivido in campi di 10x10 e così via.

Arrivo velocemente alla soluzione in tutti i casi tranne quello su descritto.
Suggerimenti per migliorare il tutto ed arrivare alla soluzione?
Grazie,
Giovanni.
gimasci99
Starting Member
Starting Member
 
Messaggio: 13 di 26
Iscritto il: 13/09/2019, 14:27

Re: [Algoritmi] Problema sui sensori sismici

Messaggioda apatriarca » 03/11/2019, 19:53

Ciao, non mi è chiaro l'algoritmo che stai usando per trovare il minimo della funzione obiettivo. Tuttavia molti dei metodi di ottimizzazione si fermano a minimi relativi invece di trovare dei minimi globali. Non sono sinceramente un esperto di ottimizzazione per cui non ti saprei dire qual è il metodo migliore per risolvere il tuo problema.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5307 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Problema sui sensori sismici

Messaggioda vict85 » 05/11/2019, 10:56

La tua \(f\) può essere semplificata in \(f = \lvert V_1 - V_2 \rvert + \lvert V_2 - V_3 \rvert + \lvert V_3 - V_4\rvert\) oppure usando i quadrati che sono più facili da derivare \(f = ( V_1 - V_2 )^2 + ( V_2 - V_3 )^2 + ( V_3 - V_4 )^2\).

Detto questo, le funzioni \(V_i\) non sono definite nei punti \(S_i\). In particolare, questo è un problema per il \(V_i\) che ha il tempo minimo, che risulta essere un buon punto iniziale per la ricerca del minimo (e che potrebbe essere una soluzione).
vict85
Moderatore
Moderatore
 
Messaggio: 9953 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite