Percorso di minimo dislivello (positivo)

[Amedeo Fadini]

Salve a tutti,

mettiamo il caso che qualcuno debba programmare un robot per effettuare un
percorso che tocchi alcuni punti prestabiliti in qualunque ordine...

Per la durata delle batterie ha più rilevanza il percorso che il robot deve
effettuare in salita rispetto alla lunghezza del percorso in totale (anzi
se va in discesa consuma meno...)

Se tutti i punti hanno la loro quota qualemetodo usare per calcolare il
percorso con minore dislivello totale in salita?

Pg routing dovrebbe avere delle funzioni di costo integrate ma serve prima
un grafo... se ordino banalmente i punti per altitudine e distanza o
distanza e altitudine rischio un percorso troppo lungo...

Dovrei forse iterare n probabili percorsi per ogni punto e scegliere il
meno costoso ad ogni passaggio?

Qualche idea?Link?

Amefad
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[ludovico.frate]

Ciao, dovrebbe essere simile ad un problema di cammino di costo minimo
(Least cost path analysis). Nello specifico si utilizza un raster dei
"costi" dove ogni cella rappresenta un costo, e dei punti che rappresentano
la sorgente e la destinazione. L'algoritmo itera attraverso una serie di
cammini possibili e seleziona quello con il costo minore.
Ludovico

Il giorno lun 8 apr 2019 alle ore 21:09 Amedeo Fadini <[hidden email]> ha
scritto:

> Salve a tutti,
>
> mettiamo il caso che qualcuno debba programmare un robot per effettuare un
> percorso che tocchi alcuni punti prestabiliti in qualunque ordine...
>
> Per la durata delle batterie ha più rilevanza il percorso che il robot deve
> effettuare in salita rispetto alla lunghezza del percorso in totale (anzi
> se va in discesa consuma meno...)
>
> Se tutti i punti hanno la loro quota qualemetodo usare per calcolare il
> percorso con minore dislivello totale in salita?
>
> Pg routing dovrebbe avere delle funzioni di costo integrate ma serve prima
> un grafo... se ordino banalmente i punti per altitudine e distanza o
> distanza e altitudine rischio un percorso troppo lungo...
>
> Dovrei forse iterare n probabili percorsi per ogni punto e scegliere il
> meno costoso ad ogni passaggio?
>
> Qualche idea?Link?
>
> Amefad
> _______________________________________________
> [hidden email]
> http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
> Questa e' una lista di discussione pubblica aperta a tutti.
> I messaggi di questa lista non hanno relazione diretta con le posizioni
> dell'Associazione GFOSS.it.
> 796 iscritti al 28/12/2017

--
*Dott. For. Ludovico Frate, Ph.D.*

*Via Kennedy 80, 86170 - Isernia - ITALIA.*
*Via Montalto 17, 86087 - Rionero Sannitico (IS) - ITALIA.*
*Studio Tecnico Forestale e GIS ForGIS <http://www.forgis.it/>*
*Collaboratore presso Studio Associato Ecoview <http://www.ecoview.it/>*
*https://www.lezionigis.it* <https://www.lezionigis.it>
*Cel: ++39 3333767557*

*P.IVA 00960030948E-mail: *[hidden email]*|*
[hidden email]
*Research Gate
<https://www.researchgate.net/profile/Ludovico_Frate?ev=hdr_xprf&_sg=lGaI2daIBO6kPmtye069ckFfDExcPoNVKJHrqvQEPQmsmnHolvnRZzPQdcyxs1g7>*
|*Google Scholar
<https://scholar.google.it/citations?user=wGFhBrkAAAAJ&hl=it>*|*LinkedIn
<https://www.linkedin.com/in/ludovico-frate-a387aa57?trk=hp-identity-name>*
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[Giuliano Curti]

Il lun 8 apr 2019, 21:09 Amedeo Fadini <[hidden email]> ha scritto:

> Salve a tutti,
>

Ciao Amedeo

>
> mettiamo il caso che qualcuno debba programmare un robot per effettuare un
> percorso che tocchi alcuni punti prestabiliti in qualunque ordine...
>
> ......
>
> Se tutti i punti hanno la loro quota qualemetodo usare per calcolare il
> percorso con minore dislivello totale in salita?
>
> Pg routing dovrebbe avere delle funzioni di costo integrate ma serve prima
> un grafo... se ordino banalmente i punti per altitudine e distanza o
> distanza e altitudine rischio un percorso troppo lungo...
>
> .....
>
> Qualche idea?Link?
>

Azzardo:

>
1) non capisco bene cosa intendi con "punti prestabiliti"; un algoritmo di
percorso minimo congiunge due nodi comprendendo solo quelli che determinano
appunto il percorso minore. Se devi passare per forza da quei punti forse
ti serve l'algoritmo del commesso viaggiatore (mi spiace, non l'ho ancora
studiato :-( )

2) devi mettere come costo il dislivello; se vuoi tener conto anche della
lunghezza puoi usare come costo una combinazione dei due

3) ATTENZIONE: (non sono freschissimo di teoria dei grafi) mi sembra che
costi negativi non possono essere gestiti (danno problemi); forse nel tuo
caso puoi metterli a zero (forse anche prendere il valore assoluto).

Prova a pensarci con più calma e vedi se trovi qualcosa di utile in quello
che ho messo :-)


Amefad
>

Ciao,
Giuliano
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[Amedeo Fadini]

Ciao Giuliano,



Il lun 8 apr 2019, 23:19 Giuliano Curti <[hidden email]> ha scritto:

1) non capisco bene cosa intendi con "punti prestabiliti"; un algoritmo di
> percorso minimo congiunge due nodi comprendendo solo quelli che determinano
> appunto il percorso minore. Se devi passare per forza da quei punti forse
> ti serve l'algoritmo del commesso viaggiatore (mi spiace, non l'ho ancora
> studiato :-( )
>

Esatto i punti non sono solo due ma un centinaio... e non sono connessi da
un grafo ma raggiungibili con diverse combinazioni... serve una
combinazione dei due algoritmi (least cost e postman) perché se uso solo il
costo (anche integrato dalla lunghezza) iterando ogni punto rischio di non
completare il percorso...

Sto valutando di costruire un grafo con tutte le connessioni tra i punti.

I costi negativi non sono un problema si può usare un offset o allineare a
0...

Una strada interessante può essere quella di calcolare le curve di livello
e passare dal punto alla curva più vicina, seguire la curva fino al punto
più vicino e così via... si aggiunge il problema del verso della curva...

Amefad
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[Roberto Marzocchi]

Ciao Amedeo,



Anni addietro avevamo fatto diversi test e anche pubblicato un plugin per GRASS 6 [1] dal nome r.pastro che faceva quello che ti serve. 

Sfortunatamente le risorse per lavorarci non ci sono e il progetto è morto lì. Però trovi tutto il codice online (sono prevalentemente script bash forse avevo iniziato la traduzione di alcune parti in python)



Vedi se trovassi qualcosa di utile anche se temo sia una soluzione difficilmente pronta all'uso (come minimo è necessario il porting su GRASS 7).  



R


[1] https://grasswiki.osgeo.org/wiki/AddOns/GRASS_6 


Eng. Roberto Marzocchi, PhD
GIS Project Coordinator
Gter srl (Unige spin-off)
Piazza De Marini 3/61 - 16123 Genova
http://P.IVA/CF 01998770992
ph: 010-8694830 - mob: [phone]
E-mail: mailto:[hidden email]
skype: roberto.marzocchi84
http://www.gter.it

--
Gter social
http://www.twitter.com/Gteronline - http://www.facebook.com/Gteronline - https://plus.google.com/+GterIt/posts 
http://www.linkedin.com/company/gter-srl-innovazione-in-geomatica-gnss-e-gis

-----------------------------------------------------------------
Please consider the environment before printing this email!








---- On Tue, 09 Apr 2019 09:20:07 +0200 Amedeo Fadini <[hidden email]> wrote ----



Ciao Giuliano,







Il lun 8 apr 2019, 23:19 Giuliano Curti <mailto:[hidden email]> ha scritto:



1) non capisco bene cosa intendi con "punti prestabiliti"; un algoritmo di

> percorso minimo congiunge due nodi comprendendo solo quelli che determinano

> appunto il percorso minore. Se devi passare per forza da quei punti forse

> ti serve l'algoritmo del commesso viaggiatore (mi spiace, non l'ho ancora

> studiato :-( )

>



Esatto i punti non sono solo due ma un centinaio... e non sono connessi da

un grafo ma raggiungibili con diverse combinazioni... serve una

combinazione dei due algoritmi (least cost e postman) perché se uso solo il

costo (anche integrato dalla lunghezza) iterando ogni punto rischio di non

completare il percorso...



Sto valutando di costruire un grafo con tutte le connessioni tra i punti.



I costi negativi non sono un problema si può usare un offset o allineare a

0...



Una strada interessante può essere quella di calcolare le curve di livello

e passare dal punto alla curva più vicina, seguire la curva fino al punto

più vicino e così via... si aggiunge il problema del verso della curva...



Amefad

_______________________________________________

mailto:[hidden email]

http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss

Questa e' una lista di discussione pubblica aperta a tutti.

I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.

796 iscritti al 28/12/2017
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[Giuliano Curti]

Il mar 9 apr 2019, 09:20 Amedeo Fadini <[hidden email]> ha scritto:

> Ciao Giuliano,
>

Ciao Amedeo

Il lun 8 apr 2019, 23:19 Giuliano Curti <[hidden email]> ha scritto:

>
> 1) non capisco bene cosa intendi con "punti prestabiliti"; un algoritmo di
>> percorso minimo congiunge due .........
>
> ancora
>> studiato :-( )
>>
>
> Esatto i punti non sono solo due ma un centinaio... e non sono connessi da
> un grafo ma raggiungibili con diverse combinazioni...
>

Anche di queste "combinazioni" capisco poco; già l'algoritmo si occupa di
stabilire una combinazione (una sequenza di punti), quella di costo
inferiore; mi viene il dubbio che ti riferisci ad altro che mi sfugge; se
fosse compatibile con il tuo problema qualsiasi combinazione dovresti
partire da un grafo completo

Sto valutando di costruire un grafo con tutte le connessioni tra i punti.
>

Il grafo completo che ho appena detto

I costi negativi non sono un problema si può usare un offset o allineare a
> 0...
>

Sì, intendevo quello, forse mi sono spiegato male (ho qualche dubbio
sull'offset, ma ne riparliamo al momento opportuno)

Una strada interessante può essere quella di calcolare le curve di livello
> e passare dal punto alla curva più vicina, seguire la curva fino al punto
> più vicino e così via... si aggiunge il problema del verso della curva...
>

Temo otterresti un grafo non connesso (nessuno garantisce che il punto più
vicino alla curva di livello precedente sia quelli più vicino alla
successiva.

Ma faccio una critica più radicale: fra due curve di livello hai un salto
noto; non capisco come vuoi alimentare l'algoritmo di ottimizzazione.

Amefad
>

Ciao,
Giuliano
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[Giuliano Curti]

Il mar 9 apr 2019, 11:24 Roberto Marzocchi <[hidden email]> ha
scritto:

> Ciao Amedeo,
>
>
>
> Anni addietro avevamo fatto diversi test e anche pubblicato un plugin per
> GRASS 6 [1] dal nome r.pastro che faceva quello che ti serve.
>

Ciao Roberto,

Ho guardato il link che hai condiviso però non ho trovato nè l'abstract ne
l'algoritmo implementato; puoi fornire qualche fonte o spiegarli
direttamente qui, così di può capire l'utilità della tua proposta?

Grazie, ciao,
Giuliano
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[Roberto Marzocchi]

Il codice è sull'SVN di grass.

https://grasswiki.osgeo.org/wiki/AddOns/GRASS_6#r.pastro






Si trattava di una serie di script per GRASS 6 che calcolavano il percorso a minor energia.



Semplicemente riguardando al volo gli script posso dirvi che erano implementate le seguenti funzioni:

 

1 - Calcolo dell'area presidiata dall'attuale insieme di rifugi (SHELTGAR),

2 - Calcolo dell'area presidiata dall'attuale rete sentieristica (PATHGAR),

3 - Calcolo della porzione di territorio raggiungibile da un punto (STRAGFINDER),

4 - Calcolo del percorso ottimale tra due punti (POINT2POINT),

5 - Calcolo del percorso ottimale tra un punto e un sentiero (POINT2PATH)



Mi pare usasse i modulo r.cost/r.drain di GRASS GIS. 



Era un tool pensato per gli ambienti montani. In questo momento non ho molto tempo di riprendere in mano il lavoro, ma tutto il codice era pubblicato e se non ricordo male piuttosto commentato

R
 


Eng. Roberto Marzocchi, PhD
GIS Project Coordinator
Gter srl (Unige spin-off)
Piazza De Marini 3/61 - 16123 Genova
http://P.IVA/CF 01998770992
ph: 010-8694830 - mob: [phone]
E-mail: mailto:[hidden email]
skype: roberto.marzocchi84
http://www.gter.it

--
Gter social
http://www.twitter.com/Gteronline - http://www.facebook.com/Gteronline - https://plus.google.com/+GterIt/posts 
http://www.linkedin.com/company/gter-srl-innovazione-in-geomatica-gnss-e-gis

-----------------------------------------------------------------
Please consider the environment before printing this email!








---- On Tue, 09 Apr 2019 13:12:45 +0200 Giuliano Curti <[hidden email]> wrote ----



Il mar 9 apr 2019, 11:24 Roberto Marzocchi <mailto:[hidden email]> ha

scritto:



> Ciao Amedeo,

>

>

>

> Anni addietro avevamo fatto diversi test e anche pubblicato un plugin per

> GRASS 6 [1] dal nome r.pastro che faceva quello che ti serve.

>



Ciao Roberto,



Ho guardato il link che hai condiviso però non ho trovato nè l'abstract ne

l'algoritmo implementato; puoi fornire qualche fonte o spiegarli

direttamente qui, così di può capire l'utilità della tua proposta?



Grazie, ciao,

Giuliano

_______________________________________________

mailto:[hidden email]

http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss

Questa e' una lista di discussione pubblica aperta a tutti.

I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.

796 iscritti al 28/12/2017
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[Giuliano Curti]

Il mar 9 apr 2019, 14:04 Roberto Marzocchi <[hidden email]> ha
scritto:

Grazie Roberto della risposta;

..........
> 4 - Calcolo del percorso ottimale tra due punti (POINT2POINT),
>

Qui immagino sia un classico percorso di minor costo; come hai trattato i
dislivelli, in particolare quelli negativi?

5 - Calcolo del percorso ottimale tra un punto e un sentiero (POINT2PATH)
>

Qui invece puoi sintetizzare il criterio?


R
>
> Eng. Roberto Marzocchi, PhD
>
> Grazie, ciao,
Giuliano
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017

[Amedeo Fadini]

Grazie mille Roberto,
l'utilizzo di r.cost è senza dubbio la strada più promettente, il mio
problema è trovare un modo efficiente per iterare la distanza tra due punti
in maniera da poter toccare tutti i punti con il minor costo cumulato....
il rischio di analizzare 2 punti alla volta è che il robot sceglie sempre
il punto più in basso tra quelli disponibili e poi si trova troppo in basso
per toccare i rimanenti... probabilmente la strada è quella del grafo
completo, suddividere man mano i punti tra già visti e da vedere e fare in
modo che il costo cumulato dei punti "da vedere" scenda ad ogni passaggio

La domanda era puramente speculativa, ma se dovesse scapparci un incarico
potrebbe essere l'occasione di fare il porting del codige a grass 7 vi
terrò informati.

Amedeo



Il giorno mar 9 apr 2019 alle ore 09:49 Roberto Marzocchi <
[hidden email]> ha scritto:

> Ciao Amedeo,
>
> Anni addietro avevamo fatto diversi test e anche pubblicato un plugin per
> GRASS 6 [1] dal nome r.pastro che faceva quello che ti serve.
> Sfortunatamente le risorse per lavorarci non ci sono e il progetto è morto
> lì. Però trovi tutto il codice online (sono prevalentemente script bash
> forse avevo iniziato la traduzione di alcune parti in python)
>
> Vedi se trovassi qualcosa di utile anche se temo sia una soluzione
> difficilmente pronta all'uso (come minimo è necessario il porting su GRASS
> 7).
>
> R
>
> [1] https://grasswiki.osgeo.org/wiki/AddOns/GRASS_6
>
> Eng. Roberto Marzocchi, PhD
> GIS Project Coordinator
> Gter srl (Unige spin-off)
> Piazza De Marini 3/61 - 16123 GenovaP.IVA/CF 01998770992
> ph: 010-8694830 - mob: [phone]
> E-mail: [hidden email]
> skype: roberto.marzocchi84www.gter.it
>
> --
> Gter socialwww.twitter.com/Gteronline - www.facebook.com/Gteronline - https://plus.google.com/+GterIt/posts www.linkedin.com/company/gter-srl-innovazione-in-geomatica-gnss-e-gis
>
> -----------------------------------------------------------------
> Please consider the environment before printing this email!
>
>
>
>
> ---- On Tue, 09 Apr 2019 09:20:07 +0200 *Amedeo Fadini <[hidden email]
> <[hidden email]>>* wrote ----
>
> Ciao Giuliano,
>
>
>
> Il lun 8 apr 2019, 23:19 Giuliano Curti <[hidden email]> ha scritto:
>
> 1) non capisco bene cosa intendi con "punti prestabiliti"; un algoritmo di
> > percorso minimo congiunge due nodi comprendendo solo quelli che
> determinano
> > appunto il percorso minore. Se devi passare per forza da quei punti forse
> > ti serve l'algoritmo del commesso viaggiatore (mi spiace, non l'ho ancora
> > studiato :-( )
> >
>
> Esatto i punti non sono solo due ma un centinaio... e non sono connessi da
> un grafo ma raggiungibili con diverse combinazioni... serve una
> combinazione dei due algoritmi (least cost e postman) perché se uso solo il
> costo (anche integrato dalla lunghezza) iterando ogni punto rischio di non
> completare il percorso...
>
> Sto valutando di costruire un grafo con tutte le connessioni tra i punti.
>
> I costi negativi non sono un problema si può usare un offset o allineare a
> 0...
>
> Una strada interessante può essere quella di calcolare le curve di livello
> e passare dal punto alla curva più vicina, seguire la curva fino al punto
> più vicino e così via... si aggiunge il problema del verso della curva...
>
> Amefad
> _______________________________________________
> [hidden email]
> http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
> Questa e' una lista di discussione pubblica aperta a tutti.
> I messaggi di questa lista non hanno relazione diretta con le posizioni
> dell'Associazione GFOSS.it.
> 796 iscritti al 28/12/2017
>
>
>
>

_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
796 iscritti al 28/12/2017