Newsgroup: it.hobby.robotica
Titolo: Pathfinding

Ciao a tutti!
Allora, adesso sto ingegnandomi per trovare una qualche soluzione per
permettere al robot di muoversi per la casa...
In memoria il robot ha una mappa piuttosto dettagliata dell'appartamento
con tutti gli "ostacoli fissi" (es: tavoli, ciarpame che sta sempre li,
armadi, etc.).
Il tutto con una risoluzione che puo' arrivare al centimetro, pensavo
pero' di ridurla fino ad una risoluzione di 5 cm.
OK! Ora si tratta di implementare un algoritmo di pathfinding che mi
consenta di far muovere il robot dal punto A al punto B, evitando di
passare sopra agli ostacoli o di cercare di sfondare i muri...
Avrei anche trovato qualcosa, ma il problema e' che questo algoritmo (come
tutti gli altri che ho trovato in giro sulla rete!) non tiene conto della
dimensione del robot...
In pratica, se io ho la mappa in quadrati da 5cm di lato, anche il robot
deve avere la stessa dimensione, altrimenti e' sicuro che andra' a
sbattere da qualche parte.
Il robot, invece, avra' un lato di 50 cm...
Certo: potrei diminuire drasticamente la risoluzione della mappa, ma non
mi sembra un'idea furba... Sopratutto se io volessi usare (come voglio!)
la stessa mappa anche per guidare il braccio meccanico che avra' uno
spostamento molto minore...
In alternativa potrei segnare come ostacoli tutti gli ostacoli con una
certa distanza minima pari ad un po' di piu' della meta' dello spessore
del robot.
In tal maniera il robot non andrebbe piu' a sbattre un quanto avrebbe gia'
impostato come "ostacoli" anche le parti effettivamente libere che pero'
sono "troppo vicine" agli ostacoli...
Entrambe le soluzioni NON mi piacciono per niente.
L'ideale sarebbe un algoritmo di ricerca di percorsi che mi consenta di
dire "tieni pero' presente che sei largo TOT".
Domanda: qualcuno conosce qualche libreria o programma (in C o PERL) che
faccia al caso mio?
In alternativa, qualcuno sa darmi qualche suggerimento per
l'implementazione?
Mille grazie
Luca Bertoncello
(
luca...@lucabert.de
)
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

Per il tuo problema (dimensioni del robot), gli algoritmi di
pathfinding che funzionano su griglia sono semplici da adattare: per
calcolare se una casella e' percorribile, non guardi solo se ha un
valore che indica "percorribile", ma anche che tutte le caselle vicine
entro un certo raggio ce l'abbiano.
Ad esempio c'e' l'algoritmo A* che e' abbastanza semplice da
implementare. Lo trovi su google (prova "+A star algorithm" per far
presa :P).
Praticamente lavora su una griglia, dove ogni casella ha un valore che
indica se e' percorribile o no. Dovresti sapere in ogni momento in
quale casella si trova il robot (diciamo il centro del robot) e
ovviamente qual'e' la destinazione.
A quel punto applichi l'algoritmo. Ti dico subito che e' un po'
dispendioso in fatto di risorse.. se hai una mappa molto grande puo'
avere molte iterazioni e metterci un bel po' soprattutto se hai una cpu
limitata.
Eventualmente qui trovi un po' di info generiche:
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Quello che vorrei sapere è che configurazione hardware ha il tuo robot. Che
tipo di sensori utilizza per evitare ostacoli? Cha cpu e di quanta memoria
dispone? Che linguaggio usi e conosci? Che sensori hai usato per far sapere
al robot di quanti cm si è spostato?
ciao
Fabio

 al robot di quanti cm si č spostato?
Al momento e' ancora in fase di progettazione!
Come "CPU" uso un vecchio Laptop con Fedora Core 3. I programmi saranno
scritti in C e in PERL.
Per sapere di quanto si sposta usero' le rotelle di un vecchio Mouse e un
software apposito che scrivero'.
Come sensori per gli ostacoli pensavo di usare uno "rotante" a infrarossi
per stabilire il punto dove il robot si trova e uno a ultrasuoni puntato
davanti per sapere che davanti c'e' un ostacolo.
Pero' devo ancora fare quasi tutto!
Ciao
Luca Bertoncello
(lucabert@lucabert.)de
