Prírodou inšpirované algoritmy

Rozpoznávanie obrazu

Autonómny systém riadenia vozidla

Rozpoznávanie obrazu alebo písma je doménou neurónových sietí. Boli vyvinuté špeciálne topológie na báze konvolučných sietí. Ďalej si ukážeme aj iný prístup, ktorý využíva genetický algoritmus a jeho implementáciu do podoby EHW čipu.

Už niekoľko rokov sa vyvíjajú systémy, ktoré by vedeli riadiť automobil bez ľudského zásahu. Taký autonómny systém musí mať kamery, ktoré zabezpečujú neustále snímanie okolia a sú vstupom do systému. Obraz je ďalej predspracovaný a rozpoznávaný, na základe čoho sa generujú rozhodnutia o vedení vozidla, brzdení a zrýchľovaní. Systém by mal byť spoľahlivý, vedieť pracovať v rôznych poveternostných podmienkách, spracovať veľké množstvo informácií naraz a to všetko za rozumný čas. Hlavné funkcie systému sú detekcia prekážok a sledovanie cesty (resp. čiary).

Na predspracovaný obraz (cesta, ktorú sníma kamera odfiltrovaná od prekážok) sa aplikuje genetický algoritmus, ktorý rozpoznáva orientáciu vodiacich čiar a jeho výstupom je vektor otáčania riadenia.

Na obrázku sú silne zredukované vstupy po predspracovaní, ktoré znázorňujú cestu z perspektívy vodiča. Reprezentujeme to napríklad maticou 1 a 0. Výstupom bude reťazec, ktorého pozícia s hodnotou 1 určuje smer jazdy.

Samotný EHW čip je postavený na digitálnych logických hradlách (LG). Vstup a výstup sú vektory popísané skôr. Hradlá sú rozdelené do vrstiev (Layers) a hradlá vo všetkých vrstvách okrem 1. vrstvy majú 2 vstupy, ktoré sú spojené s dvoma hradlami z predchádzajúcej vrstvy. Funkcia každého hradla je určená evolúciou, ktorá je vykonaná off-line softwarom. Ak je na výstupe aktivované len 1 hradlo považuje sa to za slabý výstup. Prax ukázala, že lepšie výsledky sa dosiahnu, ak je na výstupe vektor so 4 aktivovanými hradlami. Keďže reálne musí systém spracovávať obraz vo veľkom rozlíšení, používa sa metóda divide-and-conquer. Úloha sa rozdelí na podúlohy (rozdelenie vstupných vektorov) a GA prehľadáva menší podpriestor.

Výhodou subsystému je menšie pole hradiel, ktoré pracujú paralelne a ako ukazuje nasledujúci graf aj neporovnateľne rýchlejšie.

Na grafe je vidieť, koľko je potrebných generácií na správnu klasifikáciu všetkých vzoriek z testovacej množiny ak sa vyžaduje, aby na výstupe boli aktivované 4 hradlá.

Implementácia čipu na HW úrovni je jednoduchá, pretože pozostáva len z navzájom prepojených logických hradiel. Počet generácií sa dá rapídne znížiť použitím subsystémov a použitím metódy divide-and-conquer. Pre kvalitnejší výstup je dobré uvažovať o množine aktivovaných výstupných hradiel, nielen jednom aktivovanom hradle.