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


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

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

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

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

    AI-водитель


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

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


    Программный код симуляции на 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
    


    Вообще-то задачу можно решить, записав дифференциальное уравнение движения и решив его… Но я в диффурах не силён. Поэтому регулярно сталкивался с такими проблемами:

    Юнит повёрнут к цели спиной. Ему лучше развернуться и доехать, или доехать задним ходом?

    Юнит повёрнут к цели под 70 градусов. Мне лучше ускоряться и одновременно поворачивать, или сначала повернуть, а потом ускоряться? Как выбрать порог, отделяющий одну стратегию от другой?
    Теперь, когда у меня есть эффективный оптимизирующий алгоритм и скоростные нейросети, я решил задачу перебором стратегий. То есть я представил нашу задачу как функцию, где входные величины — это веса и сдвиги нейронов, а выходная величина — это численная оценка эффективности данной стратегии (эта численная оценка называется функцией качества или метрикой качества).

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

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

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



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

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

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

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

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



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

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


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

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



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



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

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

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

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

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



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

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


    Исходный код симуляции с водителем, находящим ключевые точки
    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;
    

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



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



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



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



    И в 4-ом:



    И в 5-ом:



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



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



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



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



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

    Вывод


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

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

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

    Если статья понравится, я расскажу, как делал аналогичный AI для игры типа Mortal Kombat.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 10
    • 0
      Извините за наивный вопрос, но давно хочу спросить, а обученную нейросеть можно копировать, и использовать на другой машине?
      • 0
        Вопрос хороший)
        Можно. Но работать будет лишь в том случае, если модели машин похожие (мощность, масса, сцепление с дорогой, тип шасси). С колёсной на гусеничную перенести нейронку вряд ли получится.
        А можно сделать нейронку и обучить её под разные машины с разными физическими параметрами — тогда нейронке будет более-менее пофиг на свойства машины — она к любой приспособится.
        • 0
          ггггг, отличный коммент :-)
        • 0

          В любом случае, на другое железо перенести нейросеть можно, и она будет реализовывать тот же алгоритм.

        • +3
          Диф ур было бы конечно получше )
          • 0
            Может, вы и правы. В случае той первой задачи с разворотом ДУ и правда лучше. Но как записать в виде ДУ и решить задачу с попаданием с 4 точки — не знаю =) Вы смогли бы?
          • +2
            Судя по графику у вас получилась функция интерполяции по точкам по времени ( с ограничением №-производных)
            Имхо, если математику развить — то от НС можно отказаться и поведение машины будет соотвествовать минимизации целевой функции.
            • 0
              Функция интерполяции? Чтобы провести интерполяцию, нужно записать уравнение регрессии. Типа такого: k0+k1*y+k2*y^2+...=l0+l1*x+l2*x^2+… где k и l — коэффициенты регрессии. У меня подобного в явном виде не было — у меня все функции от времени и притом рекуррентные (зависят от предыдущих условий).
              Поэтому — да, в каком-то смысле интерполяция. Но из такой интерполяции очень неявным образом следует алгоритм управления.
              Да, и ещё не стоит забывать, что локатор видит не все точки. Их ещё найти надо. Интерполяция этого никак не учитывает.
            • 0
              http://2014.russianaicup.ru/
              Схожие задачи решал во время участия в этом турнире
              • 0
                Вы правильно угадали, откуда я взял задачу =)

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.