A* search

[legacy]

esempi in lisp ne avete ?

come goal, poniamo pure la risoluzione ottima di un labirinto 2D

[deluca]

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

Come mai la scelta di lisp?

[legacy]

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]

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]

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]

@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 ?

[deluca]

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.

[legacy]

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:|###################|