Che cosa sono i formati per archiviare le mappe geografiche di un robot per percorrere il punto A al punto B

Per spostare robot o calcolare percorsi da spostare dal punto A al punto B, devi utilizzare una struttura grafica . Un grafico è un insieme di nodi e un insieme di spigoli che mettono in relazione i nodi. Un percorso è una sequenza di segmenti (cioè due nodi e il bordo usato per andare dal primo al secondo). Un algoritmo di individuazione dei percorsi consente quindi di calcolare un percorso ottimale tra 2 punti.

Se il tuo robot si muove su un'area piatta e limitata (un piano, un edificio), è sufficiente una mappa 2D con coordinate X e Y per ciascun nodo. I nodi rappresenterebbero i punti chiave per i possibili percorsi (entrambe le estremità di un corridoio, un centro di porte, ecc. Se necessario, potrebbe essere utilizzata una struttura 3D per rappresentare il livello del pavimento.

Se il tuo robot si muove su una scena più grande, allora devi usare le coordinate GPS (latitudine, longitudine). Dal punto di vista dell'algoritmo del grafico, non cambia molto, è solo che il calcolo della distanza tra i punti diventerà più complesso.

In quest'ultimo caso, potresti essere interessato all'utilizzo di formati di dati in cui puoi facilmente ottenere dati, come OpenStreetMap . Utilizza diversi formati di dati, ma uno di questi è XML OSM o il suo OSM JSON variante. Ma prima di reinventare la ruota, potresti prendere in considerazione librerie / framework esistenti .

Infine, nota che nella vita reale i nodi sono punti astratti e un segmento di strada o corridoio è più grande della linea teorica tra due nodi. Qui una possibilità è creare una griglia di nodi strettamente interconnessi. L'altro consiste nell'utilizzare i nodi per calcolare il percorso, ma lasciare che il robot si discosti dalla traiettoria teorica ideale, all'interno di alcune tolleranze, in base alla topologia nota e ad alcuni sensori per evitare collisioni.

Ma ora stiamo entrando in aspetti molto complessi con un ampio set di soluzioni.

Si prega di definire la mappa dell'area. È questo l'insieme di punti in cui il robot può potenzialmente spostarsi o stai pensando a qualcos'altro?

Direi che i punti sono davvero tutto ciò che importa. Immagino che la "mappa" sia un insieme di punti con ciascun punto che ha riferimenti ad altri punti che possono essere percorsi da quel punto. Questo sarà tipicamente solo altri due punti (avanti e indietro). I punti di congiunzione avrebbero più di due punti di riferimento.

Quando calcoli il percorso migliore da A a B hai un numero di opzioni. Posso pensarne due dalla cima della mia testa:

• Forza bruta: basta fare un percorso con le giuste curve fino a quando non colpisci il bersaglio o non può andare oltre (devi girare e rivisitare un punto sei già passato). Se non puoi andare oltre, torna al ultimo svincolo e prova la prossima uscita. Continua a fare questo fino a te hanno avuto tutti i percorsi possibili. Se colpisci il bersaglio (B) segni o salva quella rotta. Quando hai finito, potresti avere diversi percorsi da A a B da cui puoi scegliere il più breve e chiamarlo il migliore. Questo è costoso, naturalmente. È fondamentalmente la fuga generica del labirinto algoritmo

• Smart: dall'inizio, vai al punto che ti porta più vicino a B e ripetere. Se incontri un vicolo cieco, scarta l'ultima mossa e riprova con il prossimo passaggio migliore e continua fino a raggiungere B.

Una volta implementato, probabilmente incontrerai casi che richiedono un processo decisionale speciale. È qui che inizia il divertimento e probabilmente quello che spera il tuo insegnante accadrà, che ti verrà in mente un approccio unico e intelligente.