[Gfoss] Percorso di minimo dislivello (positivo)

Amefad · April 8, 2019, 7:08pm

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

ludovico.frate · April 8, 2019, 7:17pm

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 <amefad@gmail.com> 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
_______________________________________________
Gfoss@lists.gfoss.it
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: *frateludovico@gmail.com*|*
ludovicofrate@hotmail.it
*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>\*

GiulianoC · April 8, 2019, 9:18pm

Il lun 8 apr 2019, 21:09 Amedeo Fadini <amefad@gmail.com> 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

Amefad · April 9, 2019, 7:20am

Ciao Giuliano,

Il lun 8 apr 2019, 23:19 Giuliano Curti <giulianc51@gmail.com> 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

Roberto_Marzocchi · April 9, 2019, 7:49am

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: 349-8786575
E-mail: mailto:roberto.marzocchi@gter.it
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 <amefad@gmail.com> wrote ----

Ciao Giuliano,

Il lun 8 apr 2019, 23:19 Giuliano Curti <mailto:giulianc51@gmail.com> 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:Gfoss@lists.gfoss.it

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

GiulianoC · April 9, 2019, 8:49am

Il mar 9 apr 2019, 09:20 Amedeo Fadini <amefad@gmail.com> ha scritto:

Ciao Giuliano,

Ciao Amedeo

Il lun 8 apr 2019, 23:19 Giuliano Curti <giulianc51@gmail.com> 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

GiulianoC · April 9, 2019, 11:12am

Il mar 9 apr 2019, 11:24 Roberto Marzocchi <roberto.marzocchi@gter.it> 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

Roberto_Marzocchi · April 9, 2019, 12:04pm

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: 349-8786575
E-mail: mailto:roberto.marzocchi@gter.it
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 <giulianc51@gmail.com> wrote ----

Il mar 9 apr 2019, 11:24 Roberto Marzocchi <mailto:roberto.marzocchi@gter.it> 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:Gfoss@lists.gfoss.it

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

GiulianoC · April 9, 2019, 7:17pm

Il mar 9 apr 2019, 14:04 Roberto Marzocchi <roberto.marzocchi@gter.it> 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

Amefad · April 10, 2019, 7:16am

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 <
roberto.marzocchi@gter.it> 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: 349-8786575
E-mail: roberto.marzocchi@gter.it
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 <amefad@gmail.com
<amefad@gmail.com>>* wrote ----

Ciao Giuliano,

Il lun 8 apr 2019, 23:19 Giuliano Curti <giulianc51@gmail.com> 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
_______________________________________________
Gfoss@lists.gfoss.it
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