Simpel robot med machine learning

Machine Learning er et skridt på vejen mod menneskelignende kunstig intelligens. Machine learning benytter store mængder data og kan inddeles i supervised, unsupervised og reinforcement learning.

Kendte anvendelser er søgemaskiner, genkendelse af tale, tekst og billeder, data-analyser, sygdoms-diagnoser og mange flere.

Jeg er p.t. interesseret i reinforcement learning, som efterligner dyrerigets brug af belønning og straf. Den er velegnet til at lære nogle robotter at bevæge sig, og kan gøres på flere måder.

Jeg har før skrevet om en simpel selvlærende robot. Her anden generation, med et eksempel på anvendelse af metoden Q-learning på en Arduino-baseret crawler-robot, som har to servo-motorer og dermed to frihedsgrader:

Robotten skal lære at bevæge sig fremad ved at modtage belønning (reward). Belønning uddeles på baggrund af en afstandsmåler, som måler afstanden til en bagvæg.

Jeg håber at eksemplet kan bruges, til at lege med nogle af de afgørende parametre i modellen, herunder alpha, epsilon og gamma.

Hver af de to servo-motorer har 6 stillinger (states). Det giver 6 x 6=36 mulige states. I hvert state er 2 mulige handlinger (actions) pr. motor: flyt en motor et trin op, eller flyt den et trin ned.

Belønningerne gemmes i en state og action matrice på 36 x 4 kaldet Q, deraf navnet Q learning. C++ sproget, som Arduino-programmering er baseret på, har (mig bekendt) ingen biblioteker til matrice-manipulationer, så det meste foregår manuelt. Fx initialiseres matricen med 10-taller a la:

for(int i=0; i<36; i++){ 
   for(int j=0; j<4; j++){ 
      Q[i][j] = 10.0; 
   } 
}

For hver tidsskridt gennemgår robotten en cyklus fra:

  1. state (s, start state),
  2. select action,
  3. get reward (baseret på afstandsmåler),
  4. go to state’ (s’, efterfølgende state),
  5. update Q.

Belønningerne i Q opdateres med en reward PLUS et vægtet gennemsnit af alle fremtidige forventede højeste belønninger. Fordelen er, at en action, som måske i sig selv er ufordelagtig (giver negativ belønning), kan vinde, fordi de efterfølgende actions giver en stor belønning. De fremtidige forventede belønninger bliver dog vægtet med gamma^n (n=trin), så jo senere belønningerne ligger, desto mindre betydning får de.

I koden ser opdateringen af Q sådan ud:

sample = r + gamma*lookAheadValue; 
Q[s][a] = Q[s][a] + alpha*(sample - Q[s][a]);

r er den reward, som afstandsmåleren giver for den action, som har fundet sted. Her er r afstanden i cm, som robotten har flyttet sig fra s til s’.
“lookAheadValue” giver den højest mulige belønning i state’, som findes i Q. I denne værdi er inkorporeret de efterfølgende forventede belønninger. På den måde kan systemet se fremad.
Alpha er learning-rate mellem 0 og 1, som afgør i hvor hurtigt systemet skal inddrage belønning OG de fremtidige forventede belønninger, mens Gamma afgør i hvor høj grad de fremtidige forventede belønninger skal inddrages.

[youtube https://www.youtube.com/watch?v=SfK9kOaqj6c?rel=0]

Under forløbet vil værdierne i Q ændres til nogle er meget fordelagtige, andre det modsatte:

Epsilon er sandsynligheden for om robotten vælger en tilfældig action eller en optimal action. Ved epsilon = 1 vælges kun tilfældige actions.

Epsilon aftager eksponentielt med tiden, hvorfor robotten bruger en epsilon-aftagende strategi, dvs. den begynder med at vælge tilfældige actions (random(0,4)), men vælger efterhånden de bedst mulige actions (aMax). Den går fra exploratorisk politik til at udnytte (exploitation) den bedste politik:

epsilon = exp(-float(t)/explorationConst);

Hele koden kan findes her. Stor tak til Andrew August, som har skrevet koden.

Next: 1) Variere gamma. 2) Udvide Q til dobbelt antal states. 3) Når antallet af actions og states udvides, kan Q ikke opdateres hurtigt nok, og skal i stedet approximeres vha. neurale netværk.

Dette indlæg blev udgivet i Arduino, Maker og DIY. Bogmærk permalinket.