Поиск в пространстве стратегий. AI водитель

в 12:59, , рубрики: AI, machine learning, автопилот, математика, математическое моделирование, машинное обучение, эксперимент
Поиск в пространстве стратегий. AI водитель - 1

Выкладываю отчёт о своём эксперименте в области машинного обучения. В этот раз темой эксперимента было создание AI для управления моделькой автомобиля.

Как написано на умных сайтах, существует два основных способа сделать, чтобы объект управления максимизировал некую функцию оценки:

1) Запрограммировать обучение с подкреплением (привет собакам Павлова)
2) Провести прямой поиск в пространстве стратегий

Я решил выбрать второй вариант.

AI-водитель

В качестве модельной задачи я выбрал подзадачу из одного чемпионата по ИИ (когда я её решал впервые, я ещё не умел machine learning).

Есть объект. Он может поворачиваться вправо-влево и ускоряться вперёд-назад (вперёд – побыстрее, назад – помедленнее). Как быстрее всего добраться этим объектом из пункта А в пункт Б?

Поиск в пространстве стратегий. AI водитель - 2

Программный код симуляции на Matlab

function q = evaluateNN(input,nn)
    unit.angle=0;
    unit.x=0;
    unit.y=0;
    trg.x=input(1);
    trg.y=input(2);
    
    q=0;
    rmin=1e100;
    for i=1:20 %машина "живёт" 20 тактов
       %работа сенсоров
        tangle=180*atan2(-unit.y+trg.y,-unit.x+trg.x)/3.141-unit.angle;
        if(tangle>180)
            tangle=tangle-360;
        end;
        if(tangle<-180)
            tangle=tangle+360;
        end;
        r=sqrt((unit.y-trg.y)^2+(unit.x-trg.x)^2);
       %принятие решений
        answArr=fastSim(nn,[tangle;r]);
        
        answArr(1)=(10+(-2))/2+ answArr(1)*(10-(-2))/2;
        answArr(2)=(30+(-30))/2+ answArr(2)*(30-(-30))/2;
        %механика
        vx=answArr(1)*cos(3.141*unit.angle/180);
        vy=answArr(1)*sin(3.141*unit.angle/180);
        unit.x=unit.x+vx;
        unit.y=unit.y+vy;
        unit.angle=unit.angle+answArr(2);
       %да, машина у нас довольно простенькая.
        if(r<rmin)
            rmin=r;
        end;
    end;
    q=-rmin;
    if(q>0)
        q=0;
    end;
end

Вообще-то задачу можно решить, записав дифференциальное уравнение движения и решив его… Но я в диффурах не силён. Поэтому регулярно сталкивался с такими проблемами:
Поиск в пространстве стратегий. AI водитель - 3
Юнит повёрнут к цели спиной. Ему лучше развернуться и доехать, или доехать задним ходом?
Поиск в пространстве стратегий. AI водитель - 4
Юнит повёрнут к цели под 70 градусов. Мне лучше ускоряться и одновременно поворачивать, или сначала повернуть, а потом ускоряться? Как выбрать порог, отделяющий одну стратегию от другой?
Теперь, когда у меня есть эффективный оптимизирующий алгоритм и скоростные нейросети, я решил задачу перебором стратегий. То есть я представил нашу задачу как функцию, где входные величины — это веса и сдвиги нейронов, а выходная величина — это численная оценка эффективности данной стратегии (эта численная оценка называется функцией качества или метрикой качества).

Входные данные нейросети:

1) Направление на цель (от -180 до 180 градусов)
2) Расстояние до цели
3) Курсовая скорость объекта управления
4) Боковая скорость объекта управления

Курсовая и боковая скорости – это вот эти штуки:

Поиск в пространстве стратегий. AI водитель - 5

Выходные величины – положение руля (от -30 до +30 градусов за такт) и ускорение от движка (от -2 до +10 клеток/ход за ход).

В качестве функции качества в единичном испытании я выбрал q=(-минимальное расстояние до цели). Q всегда отрицательна, но чем больше Q, тем выше мы оцениваем качество алгоритма. Так как испытаний я провожу несколько, надо вывести из них какую-то единую метрику качества.

Я взял в качестве метрики наихудшее значение качества по всем испытаниям — то есть бот стремиться улучшить не средний, а худший из результатов. Я так сделал, чтобы AI не стремился оптимизировать результаты одних испытаний в ущерб результатам других испытаний.

Моя нейросеть состояла из 2 слоёв по 7 нейронов каждый, функция активации каждого нейрона – арктангенс.

Несколько минут обучения и…

Поиск в пространстве стратегий. AI водитель - 6

AI стал наводиться на цель вот так. Красная стрелочка – это ориентация машины. То есть бот давал задний ход, одновременно разворачивался, а затем переходил с заднего хода на передний. При этом цели он достигал быстрее, чем стратегия «сначала хотя бы частично развернуться, потом ехать» и чем стратегия «ехать задом».

AI-собиратель

Немного меняем постановку задачи. Всё та же плоскость, всё те же возможности ускоряться/поворачивать (на этот раз ускорение от -3 до 7, а поворот от -30 до 30 градусов за ход). Каждое испытание ограничено 100 ходами.

Но теперь целей несколько. Каждая цель неподвижна. AI видит их таким образом:

Поиск в пространстве стратегий. AI водитель - 7

Нейросети доступен угол обзора в 200 градусов, который разбит на 9 равных секторов (22 градуса каждый). Если в один из секторов попадает цель, то на соответствующий сенсор нейросети попадает число, равное расстоянию до цели. Если цели в секторе нет, то на сенсор попадает число 1000 (практически все расстояния в симуляции меньше этого числа).

Поиск в пространстве стратегий. AI водитель - 8

Если управляемый объект подъезжает к цели на расстояние 10 или меньше, цель уничтожается, а AI получает 10 очков (типа съел цель).

Начальные координаты объекта управления нулевые (0,0). Координаты целей в первом испытании такие:

[50,100] [10,30] [100,-120] [60,75]

Это типичные координаты. Всего испытаний 6, и координаты примерно такого порядка. Целей всегда 4.

Ставлю ИИ на обучение. ИИ безуспешно пытается обучиться в течение нескольких часов. Он в среднем захватывает одну цель за испытание (даже чуть меньше). Полагаю, проблема в том, что функция зависимости награды от коэффициентов кусочно-постоянная.

Поиск в пространстве стратегий. AI водитель - 9

В таких случаях мой оптимизатор работает довольно плохо (да и эволюция в таких случаях не особенно справляется).

Поэтому я совершаю небольшое читерство. Я делаю, чтобы каждый ход AI получал число очков, обратно пропорциональное расстоянию до каждой из неподобранных целей. Он получает по 0.1/r очков за каждую цель. То есть на расстоянии в 10 он будет получать 0.001 очко за цель, а «съедание» этой цели будет давать 10 очков. Число очков, получаемое AI, меняется очень слабо, но функция становится кусочно-переменной, то есть у неё появляется ненулевая производная.

Поиск в пространстве стратегий. AI водитель - 10

Исходный код симуляции с водителем, находящим ключевые точки

function q = evaluateNN(input,nn)
    unit.angle=0;
    unit.x=0;
    unit.y=0;
    unit.vx=0;
    unit.vy=0;
    trg=[];
    trg(1).x=input(1);
    trg(1).y=input(2);
    trg(1).pickable=1;
    trg(2).x=input(3);
    trg(2).y=input(4);
    trg(2).pickable=1;
    trg(3).x=input(5);
    trg(3).y=input(6);
    trg(3).pickable=1;
    trg(4).x=input(7);
    trg(4).y=input(8);
    trg(4).pickable=1;
    tsz=size(trg);
    
    tangle=[];
    r=[];
    sensor=[];
    sensorMax=5;
    sensorBound=70;
    sectorSize=2*sensorBound/sensorMax;

    q=-100;
    rmin=1e100;
    for i=1:200
%работа сенсоров
        for j=1:sensorMax
            sensor(j)=1e4;
        end;
        for j=1:tsz(2)
            tangle(j)=180*atan2(-unit.y+trg(j).y,-unit.x+trg(j).x)/3.141-unit.angle;
            if(tangle>180)
                tangle=tangle-360;
            end;
            if(tangle<-180)
                tangle=tangle+360;
            end;
            r(j)=sqrt((unit.y-trg(j).y)^2+(unit.x-trg(j).x)^2);
            if(tangle(j)>-sensorBound && tangle(j)<sensorBound && trg(j).pickable==1)
                %target in field of view
                index=floor((tangle(j)+sensorBound)/sectorSize)+1;
                if(sensor(index)>r(j))
                    sensor(index)=r(j);
                end;
            end;
            %даём подкрепление за подбор награды
            if(r(j)<10 && trg(j).pickable==1)
                %picked up
                q=q+10;
                trg(j).pickable=0;
            end;
%даём подкрепление за близость к награде
            if(r(j)<50 && trg(j).pickable==1)
                q=q+1/r(j);
            end;
        end;
%сенсоры скорости: боковой и курсовой
        vangle=180*atan2(unit.vy,unit.vx)/3.141;
        vr=unit.vy*sin(3.141*unit.angle/180)+unit.vx*cos(3.141*unit.angle/180);%v-radial. Scalar multing
        vb=-unit.vx*sin(3.141*unit.angle/180)+unit.vy*cos(3.141*unit.angle/180);%v-back. vx*(-y)+vy*x
       %принятие решений
        answArr=fastSim(nn,[sensor'';vr;vb]);

        answArr(1)=(4+(-1))/2+ answArr(1)*(4-(-1))/2;
        answArr(2)=(30+(-30))/2+ answArr(2)*(30-(-30))/2;
        %механическая модель
        ax=answArr(1)*cos(3.141*unit.angle/180);
        ay=answArr(1)*sin(3.141*unit.angle/180);
        unit.vx=unit.vx+ax;
        unit.vy=unit.vy+ay;
        unit.x=unit.x+unit.vx;
        unit.y=unit.y+unit.vy;
        unit.angle=unit.angle+answArr(2);
    end;
    if(q>0)
        q=0;
    end;
end

При этом результаты нескольких испытаний я объединял следующим образом: я брал средний результат и наихудший, и брал от них среднее.

nnlocal=ktonn(nn,k);
arr=[1,2,3,4,1,2,3,4];
input=[[50,100,10,30,100,-120,60,75];[-50,50,-100,100,10,0,20,-90];[100,-60,-100,15,20,0,15,4];[-100,-10,-25,15,60,-5,-80,10];[-10,-70,0,-40,0,40,20,22];          [20,-100,-20,22,-30,0,100,-10];];
for (i=1:6)
	nncopy=nnlocal;
	val=evaluateNN(input(i,:),nncopy);
	sum_=sum_+val;
	arr(i)=val;
	countOfPoints=countOfPoints+1;
end;
q=sum_/countOfPoints- sum(abs(k))*0.00001;

Работа пошла бодрее. Несколько десятков минут – и вуаля:

Поиск в пространстве стратегий. AI водитель - 11

Так мы проходим 1-ое испытание. Все цели (синие крестики) успешно захвачены.

Поиск в пространстве стратегий. AI водитель - 12

Так мы проходим 2-ое испытание. Захвачено 3 цели (для захвата той первой цели пришлось чуть проехать вперёд, а затем развернуться. Крупным планом это выглядит так:

Поиск в пространстве стратегий. AI водитель - 13

В 3-ем испытании тоже 4 из 4:

Поиск в пространстве стратегий. AI водитель - 14

И в 4-ом:

Поиск в пространстве стратегий. AI водитель - 15

И в 5-ом:

Поиск в пространстве стратегий. AI водитель - 16

А вот в 6-ом у нас уже 3 из 4.

Поиск в пространстве стратегий. AI водитель - 17

Зададим теперь новые испытания – такие, которых не было в обучающей выборке (проведём кроссвалидацию).

Поиск в пространстве стратегий. AI водитель - 18

3 из 4! Признаться, я до последнего сомневался, что AI сможет перенести опыт обучающей выборки на тестовую.

Поиск в пространстве стратегий. AI водитель - 19

Отработал 3 цели, и мимо одной чуть-чуть промазал.

Поиск в пространстве стратегий. AI водитель - 20

Ну а тут AI совсем облажался. Отработал 2 цели из 4.

Вывод

Отчёт об эксперименте должен заканчиваться выводами. Выводы следующие:

1) Обучение методом перебора пространства стратегий — многообещающая методика. Но она требовательна к оптимизатору — я применял довольно замороченный алгоритм для подбора параметров.
2) Кусочно-постоянная функция качества — это зло. Если у функции нет чего-то, хоть отдалённо напоминающего производную, её очень тяжело будет оптимизировать.
3) 2 слоя по 7 нейронов — это достаточно, чтобы сделать простенький автопилот. Обычно 14 нейронов — это пшик, из которого не собрать никакую полезную функцию.

Буду благодарен за комментарии, товарищи!

Если статья понравится, я расскажу, как делал аналогичный AI для игры типа Mortal Kombat.

Автор: Kilorad

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js