Berta Sándor

Elkerülhetők a robotautók összeüt­közései

Mindez a nem központi vezérlést alkalmazó algoritmusok segítségével valósítható meg.

Az Északnyugati Egyetem kutatói kifejlesztették az első decentralizált algoritmust, amellyel lehetővé válik az ütközések elkerülése. A programot 1024 virtuális gépkocsival és egy 100 kis méretű robotjárműből álló rajjal tesztelték laboratóriumi körülmények között. A robotautók kevesebb, mint egyetlen perc alatt összeálltak egy előre meghatározott minta szerint.

Michael Rubenstein, az egyetem munkatársa elmondta, hogy ha sok autonóm gépkocsi közlekedik, akkor fontos, hogy ne ütközzenek össze egymással vagy ne kerüljenek dugóba. Amennyiben lehetőség van egy raj olyan jellegű irányítására, hogy egy előre meghatározott formációt vegyenek fel, akkor egy flottányi önállóan közlekedő járművet is rá lehet venni arra, hogy kommunikáljanak egymással.


A megalkotott algoritmus gondoskodik arról, hogy a flotta egyik autójának hibája a lehető legkisebb károkat okozza. A jelenlegi rendszereknél, ha egy gépkocsi kiesik, akkor a teljes rendszer összedől. Egy decentralizált hálózatban viszont minden autonóm jármű saját döntéseket hozhat. Amennyiben a raj egyik tagja kiesik, akkor a formáció többi tagja még mindig képes teljesíteni a feladatait.

Az algoritmus azt a területet, amelyen az autók közlekednek, rácshálóként kezeli. Egy GPS-szerű navigációs rendszernek köszönhetően mindegyik gépkocsi pontosan tudja, hogy éppen hol tartózkodik. A következő mozgás előtt mindegyik robot kommunikál a szomszédjával és ellenőrzi azt, hogy az a hely, ahová igyekszik, szabadon van-e. Rubenstein rámutatott, hogy egyetlen jármű sem megy egy olyan helyre, amelyről nem tudja, hogy szabadon van és ahová nem tart másik autó. A megalkotott algoritmus nem csupán zökkenőmentes navigációt biztosít a közutakon, hanem lehetővé teszi azt is, hogy például a targoncák megbízhatóan közlekedjenek a nagy csarnokokban.

Hozzászólások

A témához csak regisztrált és bejelentkezett látogatók szólhatnak hozzá!
Bejelentkezéshez klikk ide
(Regisztráció a fórum nyitóoldalán)
  • kvp #7
    "Másik probléma: a videójátékok teljesen más eset, mert ott egy központi algoritmus vezérli le a mozgásokat. A cikkben említett célnál meg pont a decentralizáció a lényeg."

    Nem minden jatek eseten igaz. Ahol a kozponti algoritmus csak a celokert felel (mondjuk azert mert a jatekos iranyit minden egyseget), ott az egysegek sajat maguk donthetik el, hogy milyen modon jutnak el a celjukhoz.

    Ez ket reszbol all, egyreszt meg kell beszelniuk, hogy ha ok lepnek egy uj mezore, akkor mas ne akarjon odaallni. Ezt jellemzoen egy kozponti foglaltsagi tablaval szoktak megoldani, de kivalthato egy mindenki beszel a mellette levo kinezett ures mezo kornyezeteben levo osszes egyseggel algoritmussal. Map mark/unmark helyett egy dupla for cikus, utkozes (azonos igenyek) eseten meg aki elobb keri, az kapja.

    A bonyolultabb resze az, hogy megkerjek egymast, hogy engedjek be oket. Ez a fenti demoban sincs meg, ehelyett a feladatokat adjak at. Tehat ha van egy robot aki nem tud bemenni a kinezett helyere, mert mar korbealltak a tobbiek a lyukat, akkor szol a legkozelebbinek, hogy menjen odebb eggyel, az szol a mellette levonek, hogy menjen odebb eggyel, stb. mig a vegen befer a kezdemenyezo robot a mellette allo helyere. Ez a mindenki uljon beljebb egy szekkel algoritmus amit egyetemi eloadotermek megtoltesekor is latni (neha). Ez egy onszervezodo megoldas, de csak azt biztositja, hogy minden helyre keruljon egy egyseg, nem azt, hogy minden egyseg a sajat kinezett helyere keruljon. Tehat autok eseten kevesbe mukodik, egyforma jarmuvek igeny szerinti kiosztasahoz tokeletes.

    Az lenne a nagy szam, ha meg tudnak beszelni, hogy felreall mindenki es beengedi az adott egyseget az adott helyre. Mindezt onszervezodo modon, mint amikor a repulon felallnak es felreallnak az emberek, hogy beengedjek a legbelso szekre kesve erkezo embert. Ez kell a tenyleges automata autok vagy cellal rendelkezo raktari robotok kezelesehez. (a gyakorlatban persze tobb hely van, mint amennyi jarmu, tehat nem egy mar beallt grid lock-ot kell feloldani)
  • M2 #6
    A videó pont egy olyan "steril" esetet mutat be, mint egy videójáték belső környezete. Kiegészítve némi valós fizikával.

    Csak egy példa: kövess a szemeddel egy robotot, aztán képzeld el, hogy beültetted Mariska nénit. Végén kinyitod az ajtót és kiborul a hányadékkal és bolti bevásárlás maradékával beterített néni, három szívinfarktus után.

    Másik probléma: a videójátékok teljesen más eset, mert ott egy központi algoritmus vezérli le a mozgásokat. A cikkben említett célnál meg pont a decentralizáció a lényeg.
  • tom_pika #5
    "Teljesen más szint például egy számítógépes játékban a entitások mozgatása, mint valós környezetben a gépjárművek mozgatása."

    Ez akkor lehetne valamennyire igaz, ha a valós környezet teljesen ismeretlen, felderítetlen lenne. Egyébként nem értem mitől lenne "teljesen más". A videó éppen hogy nem a 'teljesen más" esetet mutaja be, hanem a tök hasonlót.
  • M2 #4
    Az benne az újdonság, hogy új területen használják. Minden új felhasználási terület új kihívásokat jelent, amikhez új megoldásokat kell kifejleszteni.

    Teljesen más szint például egy számítógépes játékban a entitások mozgatása, mint valós környezetben a gépjárművek mozgatása.
  • gosub #3
    Magam se értem mi ebben az újdonság. Számgépek közti kommunikáció és egymás pótlása, egymás ellenőrzése, hibafelderítése, ha éppen nem is egyidős a számítógéppel, de az eljárások elég korán kialakultak. Még csak óriási nagy kapacitás se kell hozzá.
  • tom_pika #2
    De ezek komoly felnőtt emberek, nem játékkal csesztél el az eddigi idejüket, ezért ezek az algoritmusok számukra még újak :-)
  • kvp #1
    Az, hogy ket robot ne utkozzon ossze kozponti koordinacio nelkul azert eleg trivialis feladat, egyszeruen nem mennek egymasnak. Ha kepesek kommunikalni, akkor azt is meg tudjak beszelni, hogy melyik menjen elore egy ajtoban.

    Ebbol mar felepitheto egy olyan onszervezodo rendszer, hogy az adott mintat megnezi minden robot es kivalasztja a legkozelebbi helyet maganak. Aztan mindenki korbekerzedi a rendszert, hogy valaki mas bejelentkezett-e mar arra a helyre. Ha van legalabb ket jelentkezo, akkor kisorsoljak vagy aki kozelebb van az megy oda. A zart alakzat belsejebe bemenni igyekvo pedig vagy megkerheti az elotte levoket, hogy uljenek eggyel odebb es akkor o beall a szelere vagy alljanak fel addig (alljanak odebb) es akkor be tud menni a helyere. Ezek nagyon jol ismert szabalyok, kb. a dune2-es korai RTS jatek (1992-ben) is ezeket hasznalta az egysegek mozgatasara, csak ott a mozgasi celokat a jatekos adta meg az egerrel es aztan az egysegek megbeszeltek egymassal, hogy hogyan is mennek oda a nelkul, hogy kereszul esnenek egymason. Azota az osszes RTS-nek alapja a csoport mozgatas alakzatban. (a microsoft-on kivul meg nem lattam olyan komolyabb RTS fejleszot ahol ezt nagyon el tudtak volna szurni)