A* search

IA e Sistemi di Visione Artificiale per la Robotica

A* search

Postby legacy » 29 Sep 2013, 12:44

esempi in lisp ne avete ?

come goal, poniamo pure la risoluzione ottima di un labirinto 2D
legacy
 
Posts: 862
Joined: 12 Mar 2012, 11:30

Re: A* search

Postby deluca » 29 Sep 2013, 15:03

Penso che A* ti serva per un mobile-robot come maze resolver in qualche competizione.....

Come mai la scelta di lisp?
Ciao
Il mio sito: http://www.delucagiovanni.com ......e la chat: chat/
User avatar
deluca
Site Admin
 
Posts: 1104
Joined: 19 Jun 2011, 10:44
Location: 95123 - Catania (Italy)

Re: A* search

Postby legacy » 29 Sep 2013, 15:11

Si, esatto!

Perche' lisp ? Per programmazione funzionale, picoLisp gira da dio sui SoC dei router grazie a linux (al limite anche Rasp PI), e trovo che sia migliore della imperativa quando hai a che fare con algoritmi che fanno forte uso di ricorsione. Sono sempre possibili (anche solo per il teo di equivalenza dei computi secondo Turing) anche altre strade ma poi al pratico mi sembra che diventano + complicate da implementare e debuggare, io poi lisp lo sfrutto come trainer per erlang.
legacy
 
Posts: 862
Joined: 12 Mar 2012, 11:30

Re: A* search

Postby legacy » 29 Sep 2013, 15:16

In C tocca anche gestirsi le liste, e tutto il backtracker engine, un sacco di lavoro, con possibili stack overflow se non ci si sta attenti, quindi ci si scosta dal problema matematico concentrandosi sulla bassa manovalanza implementativa col risultato che i tempi umani per arrivare alla soluzione funzionante crescono in progressione geometrica.
legacy
 
Posts: 862
Joined: 12 Mar 2012, 11:30

Re: A* search

Postby legacy » 29 Sep 2013, 23:50

sto giocando con i labirinti, ho scritto un po' di cose sia in lisp che in C
niente A*, questi li risolvo con approccio ricorsivo condizionato da una heuristic function che suggerisce quale ramo seguire a seconda di quanto la mossa avvicina alla punto di uscita, il tutto facendo pagare delle penalita' se si cozza contro un muro o su una cella gia' esplorata senza successo.

'I' ingresso
'O' uscita
'#" muro
'@' deadlock (continuo a passare dagli stessi posti come una trottola -> da evitare dopo un po' lo stack esplode)
'.' bricciola di pane, ho gia' visitato questa cella


funzionicchia, ma .... e' molto grezzo e bovino, e non produce quasi mai soluzioni ottime, quasi sempre sempre sub-ottime, con diversi fenomeni oscillatori che dipendono fortemente dalla funzione suggeritrice

Code: Select all
     |0123456789012345678
   0:|######### #########|
   1:|#       #I#       #|
   2:|#                 #|
   3:|#     #######     #|
   4:|#                 #|
   5:|#       # #       #|
   6:|#       #O#       #|
   7:|###################|

     |0123456789012345678
   0:|######### #########|
   1:|#.......#O#OO.....#|
   2:|#........OOOOO....#|
   3:|#.....#######O....#|
   4:|#........OOOOO....#|
   5:|#.......#O#.OO....#|
   6:|#.......#O#.OO....#|
   7:|###################|



Code: Select all
     |0123456789012345678
   0:|######### #########|
   1:|#       #I#       #|
   2:|#                 #|
   3:|#                 #|
   4:|#       # #       #|
   5:|#       #        O#|
   6:|###################|

     |0123456789012345678
   0:|######### #########|
   1:|#       #O#       #|
   2:|#        O        #|
   3:|#        O        #|
   4:|#       #O#       #|
   5:|#       #OOOOOOOOO#|
   6:|###################|


Code: Select all
     |0123456789012345678
   0:|######### #########|
   1:|#       #I#       #|
   2:|#         #  #  # #|
   3:|# #########  #### #|
   4:|# #          #    #|
   5:|#       # #  # # O#|
   6:|###################|

     |0123456789012345678
   0:|######### #########|
   1:|#       #O# OOOOOO#|
   2:|#OOOOOOOOO#OO#  #O#|
   3:|#O#########OO####O#|
   4:|#O#....OOOOOO#  OO#|
   5:|#OOOOOOO#.#OO# #OO#|
   6:|###################|


Code: Select all
     |0123456789012345678
   0:|######### #########|
   1:|#   # ## I ## #   #|
   2:|# #   #     #   # #|
   3:|# ##### # # ##### #|
   4:|#        O        #|
   5:|# ##### # # ##### #|
   6:|# #   #     #   # #|
   7:|#   # ##   ## #   #|
   8:|###################|

     |0123456789012345678
   0:|######### #########|
   1:|#   # ##.O.##.#...#|
   2:|# #   #OOOOO#...#.#|
   3:|# #####O#O#O#####.#|
   4:|#      OOOOO......#|
   5:|# ##### #O#O#####.#|
   6:|# #   #  OOO#...#.#|
   7:|#   # ##   ##.#...#|
   8:|###################|


Quest'ultimo causava circular dead lock per un errore nella stima da parte della heuristic function
ed il fixup me lo tengo ancora commentato nel codice per ricordarmi cosa succede se si sbagliano a fare i conti =P
Code: Select all
/*
 * circular issue
 *
 * XXXXXXXXXIXXXXXXXXX
 * X...X.XX@@@XX.X...X
 * X.X...X@@ @@X...X.X
 * X.XXXXX@X X@XXXXX.X
 * X......@ O @......X
 * X.XXXXX@X X@XXXXX.X
 * X.X...X@@ @@X...X.X
 * X...X.XX@@@XX.X...X
 * XXXXXXXXXXXXXXXXXXX
 */


'.' significa che l'algoritmo ha dovuto valutare anche quella cella scartandola poi dalla soluzione
euristiche migliori danno efficienza migliore

Code: Select all
     |0123456789012345678
   0:|###################|
   1:|#   # ## I ## #   #|
   2:|# #   #     #   # #|
   3:|# ##### # # ##### #|
   4:|#        O        #|
   5:|# ##### # # ##### #|
   6:|# #   #     #   # #|
   7:|#   # ##   ## #   #|
   8:|###################|

     |0123456789012345678
   0:|###################|
   1:|#   # ## O ## #   #|
   2:|# #   #  O  #   # #|
   3:|# ##### #O# ##### #|
   4:|#        O        #|
   5:|# ##### # # ##### #|
   6:|# #   #     #   # #|
   7:|#   # ##   ## #   #|
   8:|###################|



A* produrrebbe sempre e comunque soluzioni ottime e non subottime.
legacy
 
Posts: 862
Joined: 12 Mar 2012, 11:30

Re: A* search

Postby legacy » 03 Oct 2013, 10:32

@giovanni
ho ripiegato al solito sul C, ho implementato uno smoother A* search modificato e NON ricorsivo (costa di meno in C)

Mi chiedevo, ma in contesto path-planning (e anche motion planning) cosa usate ?
legacy
 
Posts: 862
Joined: 12 Mar 2012, 11:30

Re: A* search

Postby deluca » 03 Oct 2013, 21:25

prova con wave-front......è molto semplice ed efficiente.

l'ho fatto implementare anche sui piccoli robot per le competizioni scolastiche e ha dato buoni risultati.
Ciao
Il mio sito: http://www.delucagiovanni.com ......e la chat: chat/
User avatar
deluca
Site Admin
 
Posts: 1104
Joined: 19 Jun 2011, 10:44
Location: 95123 - Catania (Italy)

Re: A* search

Postby legacy » 15 Oct 2013, 13:56

ummm ho implementato entrambi, pero' A* lo posso riutilizzare anche per la classe di algoritmi VFH -> {VFH, VFH-plus, VFH-star}.

Ho sistemato per bene le euristiche, ho aggiunto dei pesi che sfruttano una tripletta di posizioni, position(previous, current, next), in questo modo tengo contro anche della variazione di direzione e verso del path ed raggiungo risultati soddisfacenti!

Code: Select all

     |0123456789012345678
   0:|###################|
   1:|#   # ## I.## #   #|
   2:|# #   #    .#   # #|
   3:|# #  #      .#  # #|
   4:|# #  #  ### .#  # #|
   5:|# #  #      .#  # #|
   6:|# #   #    .#   # #|
   7:|# ##### ###.##### #|
   8:|#          .      #|
   9:|#          .      #|
  10:|#          .      #|
  11:|#          .      #|
  12:|#          .      #|
  13:|#          .      #|
  14:|#          .      #|
  15:|#          .      #|
  16:|#          .      #|
  17:|#          .      #|
  18:|# ######  . #######|
  19:|# #   #  .  #   # #|
  20:|# #  #  .    #  # #|
  21:|# #  #   .   #  # #|
  22:|# #  #   O   #  # #|
  23:|# #   #     #   # #|
  24:|#   # ### ### #   #|
  25:|###################|
legacy
 
Posts: 862
Joined: 12 Mar 2012, 11:30


Return to Intelligenza & Visione Artificiale

Who is online

Users browsing this forum: No registered users and 9 guests

cron